1
|
#
|
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
|
|
260
|
|