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.
6 # TODO: The use of this code needs to be okayed by someone.
9 class RecursionError( OverflowError, ValueError ):
10 '''Unable to calculate result because of recursive structure'''
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.
18 children, parents = _buildChildrenLists(routes)
19 # first stage is those nodes
20 # having no incoming routes...
25 if (not parents.get(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])
32 nodes = filter ( lambda x, l=stage: x not in l, nodes )
34 previousStageChildren = []
36 # second stage are those nodes
37 # which are direct children of the first 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
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 )
61 nodes = filter ( lambda x, l=stage: x not in l, nodes )
62 if nodelen == len(nodes):
64 raise RecursionError( nodes )
66 stages.append( nodes[:] )
70 def _buildChildrenLists (routes):
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
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
91 inversedependencies = {}
97 dependencies[ node ] = (0, node)
98 inversedependencies[ node ] = []
101 for depended, depends in routes:
104 newdependencylevel, object = dependencies.get ( depends, (0, depends))
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()
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, () ):
132 oldcount, inverse = dependencies [ inverse]
134 # will be dealt with on later pass
135 dependencies [ inverse] = (oldcount-1, inverse)
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] = []
143 # dealing with a recursion-breaking run...
146 # if no elements could be deleted, then
147 # there is something which depends upon itself
150 raise RecursionError( sortinglist )
152 # hack so that something gets deleted...
155 dependencies[sortinglist[0][1]] = (0,sortinglist[0][1])
156 # delete the items that were dealt with
157 for item in deletelist:
159 del dependencies [ item ]
162 # need to recreate the sortinglist
163 sortinglist = dependencies.values()
165 output.remove( generation )
173 if __name__ == "__main__":
175 nodes = ['a', 'b', 'c', 'd', 'e', 'f']
176 route = [('a', 'b'), ('b', 'c'), ('b', 'd'), ('e','f')]
178 for x in toposort( nodes, route):
186 import pprint, traceback
187 nodes= [ 0,1,2,3,4,5 ]
189 [ (0,1),(1,2),(2,3),(3,4),(4,5)],
190 [ (0,1),(0,2),(1,2),(3,4),(4,5)],
200 (0,1), # 3-element cycle test, no orphan nodes
230 print 'sort, no recursion allowed'
231 for index in range(len(testingValues)):
232 ## print ' %s -- %s'%( index, testingValues[index])
234 print ' ', sort( nodes, testingValues[index] )
236 print 'exception raised'
237 print 'toposort, no recursion allowed'
238 for index in range(len(testingValues)):
239 ## print ' %s -- %s'%( index, testingValues[index])
241 print ' ', toposort( nodes, testingValues[index] )
243 print 'exception raised'
244 print 'sort, recursion allowed'
245 for index in range(len(testingValues)):
246 ## print ' %s -- %s'%( index, testingValues[index])
248 print ' ', sort( nodes, testingValues[index],0 )
250 print 'exception raised'
251 print 'toposort, recursion allowed'
252 for index in range(len(testingValues)):
253 ## print ' %s -- %s'%( index, testingValues[index])
255 print ' ', toposort( nodes, testingValues[index],0 )
257 print 'exception raised'