1 |
3032
|
perry
|
#
|
2 |
|
|
# According to <http://www.vrplumber.com/programming/> this file
|
3 |
|
|
# is licensed under a BSD-style license. We only use the section
|
4 |
|
|
# originally by Tim Peters.
|
5 |
|
|
#
|
6 |
|
|
# TODO: The use of this code needs to be okayed by someone.
|
7 |
|
|
#
|
8 |
|
|
|
9 |
|
|
class RecursionError( OverflowError, ValueError ):
|
10 |
|
|
'''Unable to calculate result because of recursive structure'''
|
11 |
|
|
|
12 |
|
|
|
13 |
|
|
def sort(nodes, routes, noRecursion=1):
|
14 |
|
|
'''Passed a list of node IDs and a list of source,dest ID routes
|
15 |
|
|
attempt to create a list of stages where each sub list
|
16 |
|
|
is one stage in a process.
|
17 |
|
|
'''
|
18 |
|
|
children, parents = _buildChildrenLists(routes)
|
19 |
|
|
# first stage is those nodes
|
20 |
|
|
# having no incoming routes...
|
21 |
|
|
stage = []
|
22 |
|
|
stages = [stage]
|
23 |
|
|
taken = []
|
24 |
|
|
for node in nodes:
|
25 |
|
|
if (not parents.get(node)):
|
26 |
|
|
stage.append (node)
|
27 |
|
|
if nodes and not stage:
|
28 |
|
|
# there is no element which does not depend on
|
29 |
|
|
# some other element!!!
|
30 |
|
|
stage.append( nodes[0])
|
31 |
|
|
taken.extend( stage )
|
32 |
|
|
nodes = filter ( lambda x, l=stage: x not in l, nodes )
|
33 |
|
|
while nodes:
|
34 |
|
|
previousStageChildren = []
|
35 |
|
|
nodelen = len(nodes)
|
36 |
|
|
# second stage are those nodes
|
37 |
|
|
# which are direct children of the first stage
|
38 |
|
|
for node in stage:
|
39 |
|
|
for child in children.get (node, []):
|
40 |
|
|
if child not in previousStageChildren and child not in taken:
|
41 |
|
|
previousStageChildren.append(child)
|
42 |
|
|
elif child in taken and noRecursion:
|
43 |
|
|
raise RecursionError( (child, node) )
|
44 |
|
|
# unless they are children of other direct children...
|
45 |
|
|
# TODO, actually do that...
|
46 |
|
|
stage = previousStageChildren
|
47 |
|
|
removes = []
|
48 |
|
|
for current in stage:
|
49 |
|
|
currentParents = parents.get( current, [] )
|
50 |
|
|
for parent in currentParents:
|
51 |
|
|
if parent in stage and parent != current:
|
52 |
|
|
# might wind up removing current...
|
53 |
|
|
if not current in parents.get(parent, []):
|
54 |
|
|
# is not mutually dependent...
|
55 |
|
|
removes.append( current )
|
56 |
|
|
for remove in removes:
|
57 |
|
|
while remove in stage:
|
58 |
|
|
stage.remove( remove )
|
59 |
|
|
stages.append( stage)
|
60 |
|
|
taken.extend( stage )
|
61 |
|
|
nodes = filter ( lambda x, l=stage: x not in l, nodes )
|
62 |
|
|
if nodelen == len(nodes):
|
63 |
|
|
if noRecursion:
|
64 |
|
|
raise RecursionError( nodes )
|
65 |
|
|
else:
|
66 |
|
|
stages.append( nodes[:] )
|
67 |
|
|
nodes = []
|
68 |
|
|
return stages
|
69 |
|
|
|
70 |
|
|
def _buildChildrenLists (routes):
|
71 |
|
|
childrenTable = {}
|
72 |
|
|
parentTable = {}
|
73 |
|
|
for sourceID,destinationID in routes:
|
74 |
|
|
currentChildren = childrenTable.get( sourceID, [])
|
75 |
|
|
currentParents = parentTable.get( destinationID, [])
|
76 |
|
|
if not destinationID in currentChildren:
|
77 |
|
|
currentChildren.append ( destinationID)
|
78 |
|
|
if not sourceID in currentParents:
|
79 |
|
|
currentParents.append ( sourceID)
|
80 |
|
|
childrenTable[sourceID] = currentChildren
|
81 |
|
|
parentTable[destinationID] = currentParents
|
82 |
|
|
return childrenTable, parentTable
|
83 |
|
|
|
84 |
|
|
|
85 |
|
|
def toposort (nodes, routes, noRecursion=1):
|
86 |
|
|
'''Topological sort from Tim Peters, fairly efficient
|
87 |
|
|
in comparison (it seems).'''
|
88 |
|
|
#first calculate the recursion depth
|
89 |
|
|
|
90 |
|
|
dependencies = {}
|
91 |
|
|
inversedependencies = {}
|
92 |
|
|
if not nodes:
|
93 |
|
|
return []
|
94 |
|
|
if not routes:
|
95 |
|
|
return [nodes]
|
96 |
|
|
for node in nodes:
|
97 |
|
|
dependencies[ node ] = (0, node)
|
98 |
|
|
inversedependencies[ node ] = []
|
99 |
|
|
|
100 |
|
|
|
101 |
|
|
for depended, depends in routes:
|
102 |
|
|
# is it a null rule
|
103 |
|
|
try:
|
104 |
|
|
newdependencylevel, object = dependencies.get ( depends, (0, depends))
|
105 |
|
|
except TypeError:
|
106 |
|
|
print depends
|
107 |
|
|
raise
|
108 |
|
|
dependencies[ depends ] = (newdependencylevel + 1, depends)
|
109 |
|
|
# "dependency (existence) of depended-on"
|
110 |
|
|
newdependencylevel,object = dependencies.get ( depended, (0, depended) )
|
111 |
|
|
dependencies[ depended ] = (newdependencylevel, depended)
|
112 |
|
|
# Inverse dependency set up
|
113 |
|
|
dependencieslist = inversedependencies.get ( depended, [])
|
114 |
|
|
dependencieslist.append (depends)
|
115 |
|
|
inversedependencies[depended] = dependencieslist
|
116 |
|
|
### Now we do the actual sorting
|
117 |
|
|
# The first task is to create the sortable
|
118 |
|
|
# list of dependency-levels
|
119 |
|
|
sortinglist = dependencies.values()
|
120 |
|
|
sortinglist.sort ()
|
121 |
|
|
output = []
|
122 |
|
|
while sortinglist:
|
123 |
|
|
deletelist = []
|
124 |
|
|
generation = []
|
125 |
|
|
output.append( generation)
|
126 |
|
|
while sortinglist and sortinglist[0][0] == 0:
|
127 |
|
|
number, object = sortinglist[0]
|
128 |
|
|
generation.append ( object )
|
129 |
|
|
deletelist.append( object )
|
130 |
|
|
for inverse in inversedependencies.get(object, () ):
|
131 |
|
|
try:
|
132 |
|
|
oldcount, inverse = dependencies [ inverse]
|
133 |
|
|
if oldcount > 0:
|
134 |
|
|
# will be dealt with on later pass
|
135 |
|
|
dependencies [ inverse] = (oldcount-1, inverse)
|
136 |
|
|
else:
|
137 |
|
|
# will be dealt with on this pass,
|
138 |
|
|
# so needs not to be in the sorting list next time
|
139 |
|
|
deletelist.append( inverse )
|
140 |
|
|
# just in case a loop comes through
|
141 |
|
|
inversedependencies[object] = []
|
142 |
|
|
except KeyError:
|
143 |
|
|
# dealing with a recursion-breaking run...
|
144 |
|
|
pass
|
145 |
|
|
del sortinglist [0]
|
146 |
|
|
# if no elements could be deleted, then
|
147 |
|
|
# there is something which depends upon itself
|
148 |
|
|
if not deletelist:
|
149 |
|
|
if noRecursion:
|
150 |
|
|
raise RecursionError( sortinglist )
|
151 |
|
|
else:
|
152 |
|
|
# hack so that something gets deleted...
|
153 |
|
|
## import pdb
|
154 |
|
|
## pdb.set_trace()
|
155 |
|
|
dependencies[sortinglist[0][1]] = (0,sortinglist[0][1])
|
156 |
|
|
# delete the items that were dealt with
|
157 |
|
|
for item in deletelist:
|
158 |
|
|
try:
|
159 |
|
|
del dependencies [ item ]
|
160 |
|
|
except KeyError:
|
161 |
|
|
pass
|
162 |
|
|
# need to recreate the sortinglist
|
163 |
|
|
sortinglist = dependencies.values()
|
164 |
|
|
if not generation:
|
165 |
|
|
output.remove( generation )
|
166 |
|
|
sortinglist.sort ()
|
167 |
|
|
return output
|
168 |
|
|
|
169 |
|
|
|
170 |
|
|
|
171 |
|
|
|
172 |
|
|
|
173 |
|
|
if __name__ == "__main__":
|
174 |
|
|
|
175 |
|
|
nodes = ['a', 'b', 'c', 'd', 'e', 'f']
|
176 |
|
|
route = [('a', 'b'), ('b', 'c'), ('b', 'd'), ('e','f')]
|
177 |
|
|
|
178 |
|
|
for x in toposort( nodes, route):
|
179 |
|
|
for a in x:
|
180 |
|
|
print a
|
181 |
|
|
|
182 |
|
|
raise SystemExit
|
183 |
|
|
|
184 |
|
|
|
185 |
|
|
|
186 |
|
|
import pprint, traceback
|
187 |
|
|
nodes= [ 0,1,2,3,4,5 ]
|
188 |
|
|
testingValues = [
|
189 |
|
|
[ (0,1),(1,2),(2,3),(3,4),(4,5)],
|
190 |
|
|
[ (0,1),(0,2),(1,2),(3,4),(4,5)],
|
191 |
|
|
[
|
192 |
|
|
(0,1),
|
193 |
|
|
(0,2),
|
194 |
|
|
(0,2),
|
195 |
|
|
(2,4),
|
196 |
|
|
(2,5),
|
197 |
|
|
(3,2),
|
198 |
|
|
(0,3)],
|
199 |
|
|
[
|
200 |
|
|
(0,1), # 3-element cycle test, no orphan nodes
|
201 |
|
|
(1,2),
|
202 |
|
|
(2,0),
|
203 |
|
|
(2,4),
|
204 |
|
|
(2,5),
|
205 |
|
|
(3,2),
|
206 |
|
|
(0,3)],
|
207 |
|
|
[
|
208 |
|
|
(0,1),
|
209 |
|
|
(1,1),
|
210 |
|
|
(1,1),
|
211 |
|
|
(1,4),
|
212 |
|
|
(1,5),
|
213 |
|
|
(1,2),
|
214 |
|
|
(3,1),
|
215 |
|
|
(2,1),
|
216 |
|
|
(2,0)],
|
217 |
|
|
[
|
218 |
|
|
(0,1),
|
219 |
|
|
(1,0),
|
220 |
|
|
(0,2),
|
221 |
|
|
(0,3),
|
222 |
|
|
],
|
223 |
|
|
[
|
224 |
|
|
(0,1),
|
225 |
|
|
(1,0),
|
226 |
|
|
(0,2),
|
227 |
|
|
(3,1),
|
228 |
|
|
],
|
229 |
|
|
]
|
230 |
|
|
print 'sort, no recursion allowed'
|
231 |
|
|
for index in range(len(testingValues)):
|
232 |
|
|
## print ' %s -- %s'%( index, testingValues[index])
|
233 |
|
|
try:
|
234 |
|
|
print ' ', sort( nodes, testingValues[index] )
|
235 |
|
|
except:
|
236 |
|
|
print 'exception raised'
|
237 |
|
|
print 'toposort, no recursion allowed'
|
238 |
|
|
for index in range(len(testingValues)):
|
239 |
|
|
## print ' %s -- %s'%( index, testingValues[index])
|
240 |
|
|
try:
|
241 |
|
|
print ' ', toposort( nodes, testingValues[index] )
|
242 |
|
|
except:
|
243 |
|
|
print 'exception raised'
|
244 |
|
|
print 'sort, recursion allowed'
|
245 |
|
|
for index in range(len(testingValues)):
|
246 |
|
|
## print ' %s -- %s'%( index, testingValues[index])
|
247 |
|
|
try:
|
248 |
|
|
print ' ', sort( nodes, testingValues[index],0 )
|
249 |
|
|
except:
|
250 |
|
|
print 'exception raised'
|
251 |
|
|
print 'toposort, recursion allowed'
|
252 |
|
|
for index in range(len(testingValues)):
|
253 |
|
|
## print ' %s -- %s'%( index, testingValues[index])
|
254 |
|
|
try:
|
255 |
|
|
print ' ', toposort( nodes, testingValues[index],0 )
|
256 |
|
|
except:
|
257 |
|
|
print 'exception raised'
|
258 |
|
|
|
259 |
|
|
|