Mercurial > hg-git

comparison 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
comparison
equal deleted inserted replaced
252:3e0eb85a83a7 253:505d7cdca198
1 ''
2 """
3 Tarjan's algorithm and topological sorting implementation in Python
4 by Paul Harrison
5 Public domain, do with it as you will
6 """
7 class TopoSort(object):
8
9 def __init__(self, commitdict):
10 self._sorted = self.robust_topological_sort(commitdict)
11 self._shas = []
12 for level in self._sorted:
13 for sha in level:
14 self._shas.append(sha)
15
16 def items(self):
17 self._shas.reverse()
18 return self._shas
19
20 def strongly_connected_components(self, graph):
21 """ Find the strongly connected components in a graph using
22 Tarjan's algorithm.
23
24 graph should be a dictionary mapping node names to
25 lists of successor nodes.
26 """
27
28 result = [ ]
29 stack = [ ]
30 low = { }
31
32 def visit(node):
33 if node in low: return
34
35 num = len(low)
36 low[node] = num
37 stack_pos = len(stack)
38 stack.append(node)
39
40 for successor in graph[node].parents:
41 visit(successor)
42 low[node] = min(low[node], low[successor])
43
44 if num == low[node]:
45 component = tuple(stack[stack_pos:])
46 del stack[stack_pos:]
47 result.append(component)
48 for item in component:
49 low[item] = len(graph)
50
51 for node in graph:
52 visit(node)
53
54 return result
55
56 def strongly_connected_components_non(self, G):
57 """Returns a list of strongly connected components in G.
58
59 Uses Tarjan's algorithm with Nuutila's modifications.
60 Nonrecursive version of algorithm.
61
62 References:
63
64 R. Tarjan (1972). Depth-first search and linear graph algorithms.
65 SIAM Journal of Computing 1(2):146-160.
66
67 E. Nuutila and E. Soisalon-Soinen (1994).
68 On finding the strongly connected components in a directed graph.
69 Information Processing Letters 49(1): 9-14.
70
71 """
72 preorder={}
73 lowlink={}
74 scc_found={}
75 scc_queue = []
76 scc_list=[]
77 i=0 # Preorder counter
78 for source in G:
79 if source not in scc_found:
80 queue=[source]
81 while queue:
82 v=queue[-1]
83 if v not in preorder:
84 i=i+1
85 preorder[v]=i
86 done=1
87 v_nbrs=G[v]
88 for w in v_nbrs.parents:
89 if w not in preorder:
90 queue.append(w)
91 done=0
92 break
93 if done==1:
94 lowlink[v]=preorder[v]
95 for w in v_nbrs.parents:
96 if w not in scc_found:
97 if preorder[w]>preorder[v]:
98 lowlink[v]=min([lowlink[v],lowlink[w]])
99 else:
100 lowlink[v]=min([lowlink[v],preorder[w]])
101 queue.pop()
102 if lowlink[v]==preorder[v]:
103 scc_found[v]=True
104 scc=(v,)
105 while scc_queue and preorder[scc_queue[-1]]>preorder[v]:
106 k=scc_queue.pop()
107 scc_found[k]=True
108 scc.append(k)
109 scc_list.append(scc)
110 else:
111 scc_queue.append(v)
112 scc_list.sort(lambda x, y: cmp(len(y),len(x)))
113 return scc_list
114
115 def topological_sort(self, graph):
116 count = { }
117 for node in graph:
118 count[node] = 0
119 for node in graph:
120 for successor in graph[node]:
121 count[successor] += 1
122
123 ready = [ node for node in graph if count[node] == 0 ]
124
125 result = [ ]
126 while ready:
127 node = ready.pop(-1)
128 result.append(node)
129
130 for successor in graph[node]:
131 count[successor] -= 1
132 if count[successor] == 0:
133 ready.append(successor)
134
135 return result
136
137 def robust_topological_sort(self, graph):
138 """ First identify strongly connected components,
139 then perform a topological sort on these components. """
140
141 components = self.strongly_connected_components_non(graph)
142
143 node_component = { }
144 for component in components:
145 for node in component:
146 node_component[node] = component
147
148 component_graph = { }
149 for component in components:
150 component_graph[component] = [ ]
151
152 for node in graph:
153 node_c = node_component[node]
154 for successor in graph[node].parents:
155 successor_c = node_component[successor]
156 if node_c != successor_c:
157 component_graph[node_c].append(successor_c)
158
159 return self.topological_sort(component_graph)