root/branches/openlayers/2.5/tools/toposort.py

#
# 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'