Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- var files = {
- "f": {"dep": ["b", "c"]},
- "g": {"dep": ["e", "f"]},
- "a": {"dep": ["c", "b"]},
- "b": {"dep": ["d", "c"]},
- "c": {"dep": []},
- "d": {"dep": ["c"]},
- "e": {"dep": ["a"]}
- };
- //TODO -o :if we have e.g "a" depend on "b" and "b" depend on "a" this will lead to
- //TODO -o :infinite recursion - so we should handle this scenario.
- //Todo -o :It could be optimized by checking if the file is already visited.
- //stores all files in dependant order
- var filesInDependantOrder = [];
- //loop through all files
- for (var file in files)
- {
- //call the drillDownDependencies to drill down to all files
- drillDownDependencies( files[file] );
- //we exit from the recursion drillDownDependencies and add the file that we have passed
- //if not exists
- if (filesInDependantOrder.indexOf( file ) < 0) {
- filesInDependantOrder.push( file );
- }
- }
- function drillDownDependencies( root )
- {
- //loop through all dependencies of the given file
- for (var i = 0, ilen = root["dep"].length; i < ilen; i++)
- {
- //pass the dependency to check if the given
- //dependency has dependencies by its own
- drillDownDependencies( files[root["dep"][i]] );
- //we exit from the recursion if the dependency
- //don't have other dependencies
- if (filesInDependantOrder.indexOf( root["dep"][i] ) < 0)
- {
- //push the dependency that don't have
- //other dependencies if not exists
- filesInDependantOrder.push( root["dep"][i] );
- }
- }
- }
- console.log(filesInDependantOrder);
- L ← Empty list that will contain the sorted elements
- S ← Set of all nodes with no incoming edges
- while S is non-empty do
- remove a node n from S
- add n to tail of L
- for each node m with an edge e from n to m do
- remove edge e from the graph
- if m has no other incoming edges then
- insert m into S
- if graph has edges then
- return error (graph has at least one cycle)
- else
- return L (a topologically sorted order)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement