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 print 'Edge nodes=',edge_nodes
25 sinks = list(edge_nodes - set(nodes))
26 sources = list(set(nodes) - edge_nodes)
29 print 'Sources =',sources
36 visited = set(sources)
41 for node in graph[current]:
42 if node not in visited:
47 # Topological sort + find connected components
49 # - Uses a stack instead of recursion
50 # - Forfeits optimization involving tracking currently visited nodes
52 def toposort_with_components(g, steps=None):
53 # Get set of all nodes, including those without outgoing edges
57 values=values | set(v)
59 all_nodes=list(keys|values)
66 # Index of newest component
69 # DFS stack, not using recursion
75 # visiting = [] - skip, don't expect 1000s of nodes, |E|/|V| is small
78 stack.insert(0,unmarked[0]) # push first unmarked
90 # Should not happen, if so there's a loop
100 noorder = list(set(steps) - set(order))
102 # Steps that do not have an order get pushed as
103 # separate components that run in parallel.
105 order['%d'%cidx] = [s]
108 return order + noorder
112 # - Uses a stack instead of recursion
113 # - Forfeits optimization involving tracking currently visited nodes
114 def toposort(g, steps=None):
115 # Get set of all nodes, including those without outgoing edges
119 values=values | set(v)
121 all_nodes=list(keys|values)
128 # DFS stack, not using recursion
134 # visiting = [] - skip, don't expect 1000s of nodes, |E|/|V| is small
137 stack.insert(0,unmarked[0]) # push first unmarked
149 # Should not happen, if so there's a loop
157 unmarked.remove(item)
159 noorder = list(set(steps) - set(order))
160 return order + noorder
163 graph_file=open('planetstack.deps').read()
164 g = json.loads(graph_file)
167 if (__name__=='__main__'):
170 #print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a'])