--- a/labs/openlayers/tools/toposort.py +++ b/labs/openlayers/tools/toposort.py @@ -1,1 +1,261 @@ - +# +# 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' + + + +