10 from datetime import datetime
11 from collections import defaultdict
13 # Assumes that there are no empty dependencies
14 # in the graph. E.g. Foo -> []
15 def dfs(graph, visit):
20 edge_nodes|=set(graph[n])
22 sinks = list(edge_nodes - set(nodes))
23 sources = list(set(nodes) - edge_nodes)
27 visited = set(sources)
32 for node in graph[current]:
33 if node not in visited:
41 # - Uses a stack instead of recursion
42 # - Forfeits optimization involving tracking currently visited nodes
43 def toposort(g, steps=None):
44 # Get set of all nodes, including those without outgoing edges
48 values=values | set(v)
50 all_nodes=list(keys|values)
57 # DFS stack, not using recursion
63 # visiting = [] - skip, don't expect 1000s of nodes, |E|/|V| is small
66 stack.insert(0,unmarked[0]) # push first unmarked
78 # Should not happen, if so there's a loop
88 noorder = list(set(steps) - set(order))
89 return order + noorder
92 graph_file=open('planetstack.deps').read()
93 g = json.loads(graph_file)
96 if (__name__=='__main__'):
99 #print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a'])