|
# |
|
# According to <http://www.vrplumber.com/programming/> this file |
|
# is licensed under a BSD-style license. We only use the section |
|
# originally by Tim Peters. |
|
# |
|
# TODO: The use of this code needs to be okayed by someone. |
|
# |
|
|
|
class RecursionError( OverflowError, ValueError ): |
|
'''Unable to calculate result because of recursive structure''' |
|
|
|
|
|
def sort(nodes, routes, noRecursion=1): |
|
'''Passed a list of node IDs and a list of source,dest ID routes |
|
attempt to create a list of stages where each sub list |
|
is one stage in a process. |
|
''' |
|
children, parents = _buildChildrenLists(routes) |
|
# first stage is those nodes |
|
# having no incoming routes... |
|
stage = [] |
|
stages = [stage] |
|
taken = [] |
|
for node in nodes: |
|
if (not parents.get(node)): |
|
stage.append (node) |
|
if nodes and not stage: |
|
# there is no element which does not depend on |
|
# some other element!!! |
|
stage.append( nodes[0]) |
|
taken.extend( stage ) |
|
nodes = filter ( lambda x, l=stage: x not in l, nodes ) |
|
while nodes: |
|
previousStageChildren = [] |
|
nodelen = len(nodes) |
|
# second stage are those nodes |
|
# which are direct children of the first stage |
|
for node in stage: |
|
for child in children.get (node, []): |
|
if child not in previousStageChildren and child not in taken: |
|
previousStageChildren.append(child) |
|
elif child in taken and noRecursion: |
|
raise RecursionError( (child, node) ) |
|
# unless they are children of other direct children... |
|
# TODO, actually do that... |
|
stage = previousStageChildren |
|
removes = [] |
|
for current in stage: |
|
currentParents = parents.get( current, [] ) |
|
for parent in currentParents: |
|
if parent in stage and parent != current: |
|
# might wind up removing current... |
|
if not current in parents.get(parent, []): |
|
# is not mutually dependent... |
|
removes.append( current ) |
|
for remove in removes: |
|
while remove in stage: |
|
stage.remove( remove ) |
|
stages.append( stage) |
|
taken.extend( stage ) |
|
nodes = filter ( lambda x, l=stage: x not in l, nodes ) |
|
if nodelen == len(nodes): |
|
if noRecursion: |
|
raise RecursionError( nodes ) |
|
else: |
|
stages.append( nodes[:] ) |
|
nodes = [] |
|
return stages |
|
|
|
def _buildChildrenLists (routes): |
|
childrenTable = {} |
|
parentTable = {} |
|
for sourceID,destinationID in routes: |
|
currentChildren = childrenTable.get( sourceID, []) |
|
currentParents = parentTable.get( destinationID, []) |
|
if not destinationID in currentChildren: |
|
currentChildren.append ( destinationID) |
|
if not sourceID in currentParents: |
|
currentParents.append ( sourceID) |
|
childrenTable[sourceID] = currentChildren |
|
parentTable[destinationID] = currentParents |
|
return childrenTable, parentTable |
|
|
|
|
|
def toposort (nodes, routes, noRecursion=1): |
|
'''Topological sort from Tim Peters, fairly efficient |
|
in comparison (it seems).''' |
|
#first calculate the recursion depth |
|
|
|
dependencies = {} |
|
inversedependencies = {} |
|
if not nodes: |
|
return [] |
|
if not routes: |
|
return [nodes] |
|
for node in nodes: |
|
dependencies[ node ] = (0, node) |
|
inversedependencies[ node ] = [] |
|
|
|
|
|
for depended, depends in routes: |
|
# is it a null rule |
|
try: |
|
newdependencylevel, object = dependencies.get ( depends, (0, depends)) |
|
except TypeError: |
|
print depends |
|
raise |
|
dependencies[ depends ] = (newdependencylevel + 1, depends) |
|
# "dependency (existence) of depended-on" |
|
newdependencylevel,object = dependencies.get ( depended, (0, depended) ) |
|
dependencies[ depended ] = (newdependencylevel, depended) |
|
# Inverse dependency set up |
|
dependencieslist = inversedependencies.get ( depended, []) |
|
dependencieslist.append (depends) |
|
inversedependencies[depended] = dependencieslist |
|
### Now we do the actual sorting |
|
# The first task is to create the sortable |
|
# list of dependency-levels |
|
sortinglist = dependencies.values() |
|
sortinglist.sort () |
|
output = [] |
|
while sortinglist: |
|
deletelist = [] |
|
generation = [] |
|
output.append( generation) |
|
while sortinglist and sortinglist[0][0] == 0: |
|
number, object = sortinglist[0] |
|
generation.append ( object ) |
|
deletelist.append( object ) |
|
for inverse in inversedependencies.get(object, () ): |
|
try: |
|
oldcount, inverse = dependencies [ inverse] |
|
if oldcount > 0: |
|
# will be dealt with on later pass |
|
dependencies [ inverse] = (oldcount-1, inverse) |
|
else: |
|
# will be dealt with on this pass, |
|
# so needs not to be in the sorting list next time |
|
deletelist.append( inverse ) |
|
# just in case a loop comes through |
|
inversedependencies[object] = [] |
|
except KeyError: |
|
# dealing with a recursion-breaking run... |
|
pass |
|
del sortinglist [0] |
|
# if no elements could be deleted, then |
|
# there is something which depends upon itself |
|
if not deletelist: |
|
if noRecursion: |
|
raise RecursionError( sortinglist ) |
|
else: |
|
# hack so that something gets deleted... |
|
## import pdb |
|
## pdb.set_trace() |
|
dependencies[sortinglist[0][1]] = (0,sortinglist[0][1]) |
|
# delete the items that were dealt with |
|
for item in deletelist: |
|
try: |
|
del dependencies [ item ] |
|
except KeyError: |
|
pass |
|
# need to recreate the sortinglist |
|
sortinglist = dependencies.values() |
|
if not generation: |
|
output.remove( generation ) |
|
sortinglist.sort () |
|
return output |
|
|
|
|
|
|
|
|
|
|
|
if __name__ == "__main__": |
|
|
|
nodes = ['a', 'b', 'c', 'd', 'e', 'f'] |
|
route = [('a', 'b'), ('b', 'c'), ('b', 'd'), ('e','f')] |
|
|
|
for x in toposort( nodes, route): |
|
for a in x: |
|
print a |
|
|
|
raise SystemExit |
|
|
|
|
|
|
|
import pprint, traceback |
|
nodes= [ 0,1,2,3,4,5 ] |
|
testingValues = [ |
|
[ (0,1),(1,2),(2,3),(3,4),(4,5)], |
|
[ (0,1),(0,2),(1,2),(3,4),(4,5)], |
|
[ |
|
(0,1), |
|
(0,2), |
|
(0,2), |
|
(2,4), |
|
(2,5), |
|
(3,2), |
|
(0,3)], |
|
[ |
|
(0,1), # 3-element cycle test, no orphan nodes |
|
(1,2), |
|
(2,0), |
|
(2,4), |
|
(2,5), |
|
(3,2), |
|
(0,3)], |
|
[ |
|
(0,1), |
|
(1,1), |
|
(1,1), |
|
(1,4), |
|
(1,5), |
|
(1,2), |
|
(3,1), |
|
(2,1), |
|
(2,0)], |
|
[ |
|
(0,1), |
|
(1,0), |
|
(0,2), |
|
(0,3), |
|
], |
|
[ |
|
(0,1), |
|
(1,0), |
|
(0,2), |
|
(3,1), |
|
], |
|
] |
|
print 'sort, no recursion allowed' |
|
for index in range(len(testingValues)): |
|
## print ' %s -- %s'%( index, testingValues[index]) |
|
try: |
|
print ' ', sort( nodes, testingValues[index] ) |
|
except: |
|
print 'exception raised' |
|
print 'toposort, no recursion allowed' |
|
for index in range(len(testingValues)): |
|
## print ' %s -- %s'%( index, testingValues[index]) |
|
try: |
|
print ' ', toposort( nodes, testingValues[index] ) |
|
except: |
|
print 'exception raised' |
|
print 'sort, recursion allowed' |
|
for index in range(len(testingValues)): |
|
## print ' %s -- %s'%( index, testingValues[index]) |
|
try: |
|
print ' ', sort( nodes, testingValues[index],0 ) |
|
except: |
|
print 'exception raised' |
|
print 'toposort, recursion allowed' |
|
for index in range(len(testingValues)): |
|
## print ' %s -- %s'%( index, testingValues[index]) |
|
try: |
|
print ' ', toposort( nodes, testingValues[index],0 ) |
|
except: |
|
print 'exception raised' |
|
|
|
|
|
|
|
|