Advertisement
Guest User

Untitled

a guest
Nov 28th, 2014
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.01 KB | None | 0 0
  1. var files = {
  2. "f": {"dep": ["b", "c"]},
  3. "g": {"dep": ["e", "f"]},
  4. "a": {"dep": ["c", "b"]},
  5. "b": {"dep": ["d", "c"]},
  6. "c": {"dep": []},
  7. "d": {"dep": ["c"]},
  8. "e": {"dep": ["a"]}
  9. };
  10.  
  11. //TODO -o :if we have e.g "a" depend on "b" and "b" depend on "a" this will lead to
  12. //TODO -o :infinite recursion - so we should handle this scenario.
  13.  
  14. //Todo -o :It could be optimized by checking if the file is already visited.
  15. //stores all files in dependant order
  16. var filesInDependantOrder = [];
  17.  
  18. //loop through all files
  19. for (var file in files)
  20. {
  21. //call the drillDownDependencies to drill down to all files
  22. drillDownDependencies( files[file] );
  23.  
  24. //we exit from the recursion drillDownDependencies and add the file that we have passed
  25. //if not exists
  26. if (filesInDependantOrder.indexOf( file ) < 0) {
  27. filesInDependantOrder.push( file );
  28. }
  29. }
  30.  
  31. function drillDownDependencies( root )
  32. {
  33. //loop through all dependencies of the given file
  34. for (var i = 0, ilen = root["dep"].length; i < ilen; i++)
  35. {
  36. //pass the dependency to check if the given
  37. //dependency has dependencies by its own
  38. drillDownDependencies( files[root["dep"][i]] );
  39.  
  40. //we exit from the recursion if the dependency
  41. //don't have other dependencies
  42. if (filesInDependantOrder.indexOf( root["dep"][i] ) < 0)
  43. {
  44. //push the dependency that don't have
  45. //other dependencies if not exists
  46. filesInDependantOrder.push( root["dep"][i] );
  47. }
  48. }
  49. }
  50.  
  51. console.log(filesInDependantOrder);
  52.  
  53. L ← Empty list that will contain the sorted elements
  54. S ← Set of all nodes with no incoming edges
  55. while S is non-empty do
  56. remove a node n from S
  57. add n to tail of L
  58. for each node m with an edge e from n to m do
  59. remove edge e from the graph
  60. if m has no other incoming edges then
  61. insert m into S
  62. if graph has edges then
  63. return error (graph has at least one cycle)
  64. else
  65. return L (a topologically sorted order)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement