10 from datetime import datetime
11 from collections import defaultdict
15 # - Uses a stack instead of recursion
16 # - Forfeits optimization involving tracking currently visited nodes
17 def toposort(g, steps=None):
18 # Get set of all nodes, including those without outgoing edges
22 values=values | set(v)
24 all_nodes=list(keys|values)
31 # DFS stack, not using recursion
37 # visiting = [] - skip, don't expect 1000s of nodes, |E|/|V| is small
40 stack.insert(0,unmarked[0]) # push first unmarked
52 # Should not happen, if so there's a loop
62 noorder = list(set(steps) - set(order))
63 return order + noorder
66 graph_file=open('planetstack.deps').read()
67 g = json.loads(graph_file)
70 if (__name__=='__main__'):
73 #print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a'])