Mercurial > hg-git

annotate hggit/toposort.py @ 253:505d7cdca198 0.1.0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
package with distutils (patch tweaked slightly by Augie Fackler)
author Kevin Bullock <kbullock@ringworld.org>
date Wed, 30 Sep 2009 14:39:49 -0500
parents toposort.py@312700177979
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
76
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
1 ''
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
2 """
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
3 Tarjan's algorithm and topological sorting implementation in Python
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
4 by Paul Harrison
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
5 Public domain, do with it as you will
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
6 """
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
7 class TopoSort(object):
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
8
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
9 def __init__(self, commitdict):
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
10 self._sorted = self.robust_topological_sort(commitdict)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
11 self._shas = []
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
12 for level in self._sorted:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
13 for sha in level:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
14 self._shas.append(sha)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
15
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
16 def items(self):
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
17 self._shas.reverse()
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
18 return self._shas
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
19
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
20 def strongly_connected_components(self, graph):
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
21 """ Find the strongly connected components in a graph using
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
22 Tarjan's algorithm.
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
23
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
24 graph should be a dictionary mapping node names to
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
25 lists of successor nodes.
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
26 """
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
27
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
28 result = [ ]
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
29 stack = [ ]
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
30 low = { }
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
31
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
32 def visit(node):
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
33 if node in low: return
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
34
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
35 num = len(low)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
36 low[node] = num
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
37 stack_pos = len(stack)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
38 stack.append(node)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
39
78
71b07e16004f fix, but im not sure its fixed yet
Scott Chacon <schacon@gmail.com>
parents: 76
diff changeset
40 for successor in graph[node].parents:
76
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
41 visit(successor)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
42 low[node] = min(low[node], low[successor])
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
43
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
44 if num == low[node]:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
45 component = tuple(stack[stack_pos:])
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
46 del stack[stack_pos:]
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
47 result.append(component)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
48 for item in component:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
49 low[item] = len(graph)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
50
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
51 for node in graph:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
52 visit(node)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
53
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
54 return result
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
55
93
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
56 def strongly_connected_components_non(self, G):
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
57 """Returns a list of strongly connected components in G.
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
58
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
59 Uses Tarjan's algorithm with Nuutila's modifications.
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
60 Nonrecursive version of algorithm.
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
61
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
62 References:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
63
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
64 R. Tarjan (1972). Depth-first search and linear graph algorithms.
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
65 SIAM Journal of Computing 1(2):146-160.
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
66
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
67 E. Nuutila and E. Soisalon-Soinen (1994).
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
68 On finding the strongly connected components in a directed graph.
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
69 Information Processing Letters 49(1): 9-14.
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
70
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
71 """
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
72 preorder={}
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
73 lowlink={}
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
74 scc_found={}
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
75 scc_queue = []
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
76 scc_list=[]
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
77 i=0 # Preorder counter
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
78 for source in G:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
79 if source not in scc_found:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
80 queue=[source]
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
81 while queue:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
82 v=queue[-1]
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
83 if v not in preorder:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
84 i=i+1
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
85 preorder[v]=i
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
86 done=1
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
87 v_nbrs=G[v]
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
88 for w in v_nbrs.parents:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
89 if w not in preorder:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
90 queue.append(w)
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
91 done=0
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
92 break
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
93 if done==1:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
94 lowlink[v]=preorder[v]
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
95 for w in v_nbrs.parents:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
96 if w not in scc_found:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
97 if preorder[w]>preorder[v]:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
98 lowlink[v]=min([lowlink[v],lowlink[w]])
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
99 else:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
100 lowlink[v]=min([lowlink[v],preorder[w]])
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
101 queue.pop()
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
102 if lowlink[v]==preorder[v]:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
103 scc_found[v]=True
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
104 scc=(v,)
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
105 while scc_queue and preorder[scc_queue[-1]]>preorder[v]:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
106 k=scc_queue.pop()
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
107 scc_found[k]=True
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
108 scc.append(k)
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
109 scc_list.append(scc)
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
110 else:
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
111 scc_queue.append(v)
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
112 scc_list.sort(lambda x, y: cmp(len(y),len(x)))
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
113 return scc_list
76
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
114
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
115 def topological_sort(self, graph):
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
116 count = { }
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
117 for node in graph:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
118 count[node] = 0
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
119 for node in graph:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
120 for successor in graph[node]:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
121 count[successor] += 1
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
122
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
123 ready = [ node for node in graph if count[node] == 0 ]
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
124
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
125 result = [ ]
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
126 while ready:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
127 node = ready.pop(-1)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
128 result.append(node)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
129
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
130 for successor in graph[node]:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
131 count[successor] -= 1
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
132 if count[successor] == 0:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
133 ready.append(successor)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
134
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
135 return result
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
136
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
137 def robust_topological_sort(self, graph):
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
138 """ First identify strongly connected components,
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
139 then perform a topological sort on these components. """
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
140
93
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
141 components = self.strongly_connected_components_non(graph)
312700177979 modified topological sort to be non-recursive
Scott Chacon <schacon@gmail.com>
parents: 78
diff changeset
142
76
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
143 node_component = { }
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
144 for component in components:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
145 for node in component:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
146 node_component[node] = component
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
147
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
148 component_graph = { }
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
149 for component in components:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
150 component_graph[component] = [ ]
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
151
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
152 for node in graph:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
153 node_c = node_component[node]
78
71b07e16004f fix, but im not sure its fixed yet
Scott Chacon <schacon@gmail.com>
parents: 76
diff changeset
154 for successor in graph[node].parents:
76
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
155 successor_c = node_component[successor]
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
156 if node_c != successor_c:
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
157 component_graph[node_c].append(successor_c)
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
158
aa2dadf04144 fixed the topo sorting and added a unit test
Scott Chacon <schacon@gmail.com>
parents:
diff changeset
159 return self.topological_sort(component_graph)