Metacat

#

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