openlayers/tools/toposort.py

   1 #
   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.
   5 #
   6 # TODO: The use of this code needs to be okayed by someone.
   7 #
   8
   9 class RecursionError( OverflowError, ValueError ):
  10     '''Unable to calculate result because of recursive structure'''
  11
  12
  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.
  17     '''
  18     children, parents = _buildChildrenLists(routes)
  19     # first stage is those nodes
  20     # having no incoming routes...
  21     stage = []
  22     stages = [stage]
  23     taken = []
  24     for node in nodes:
  25         if (not parents.get(node)):
  26             stage.append (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])
  31     taken.extend( stage )
  32     nodes = filter ( lambda x, l=stage: x not in l, nodes )
  33     while nodes:
  34         previousStageChildren = []
  35         nodelen = len(nodes)
  36         # second stage are those nodes
  37         # which are direct children of the first stage
  38         for node in 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
  47         removes = []
  48         for current in stage:
  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 )
  59         stages.append( stage)
  60         taken.extend( stage )
  61         nodes = filter ( lambda x, l=stage: x not in l, nodes )
  62         if nodelen == len(nodes):
  63             if noRecursion:
  64                 raise RecursionError( nodes )
  65             else:
  66                 stages.append( nodes[:] )
  67                 nodes = []
  68     return stages
  69
  70 def _buildChildrenLists (routes):
  71     childrenTable = {}
  72     parentTable = {}
  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
  83
  84
  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
  89
  90     dependencies = {}
  91     inversedependencies = {}
  92     if not nodes:
  93         return []
  94     if not routes:
  95         return [nodes]
  96     for node in nodes:
  97         dependencies[ node ] = (0, node)
  98         inversedependencies[ node ] = []
  99
 100
 101     for depended, depends in routes:
 102         # is it a null rule
 103         try:
 104             newdependencylevel, object = dependencies.get ( depends, (0, depends))
 105         except TypeError:
 106             print depends
 107             raise
 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()
 120     sortinglist.sort ()
 121     output = []
 122     while sortinglist:
 123         deletelist = []
 124         generation = []
 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, () ):
 131                 try:
 132                     oldcount, inverse = dependencies [ inverse]
 133                     if oldcount > 0:
 134                         # will be dealt with on later pass
 135                         dependencies [ inverse] = (oldcount-1, inverse)
 136                     else:
 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] = []
 142                 except KeyError:
 143                     # dealing with a recursion-breaking run...
 144                     pass
 145             del sortinglist [0]
 146         # if no elements could be deleted, then
 147         # there is something which depends upon itself
 148         if not deletelist:
 149             if noRecursion:
 150                 raise RecursionError( sortinglist )
 151             else:
 152                 # hack so that something gets deleted...
 153 ##                import pdb
 154 ##                pdb.set_trace()
 155                 dependencies[sortinglist[0][1]] = (0,sortinglist[0][1])
 156         # delete the items that were dealt with
 157         for item in deletelist:
 158             try:
 159                 del dependencies [ item ]
 160             except KeyError:
 161                 pass
 162         # need to recreate the sortinglist
 163         sortinglist = dependencies.values()
 164         if not generation:
 165             output.remove( generation )
 166         sortinglist.sort ()
 167     return output
 168
 169
 170
 171
 172
 173 if __name__ == "__main__":
 174
 175     nodes = ['a', 'b', 'c', 'd', 'e', 'f']
 176     route = [('a', 'b'), ('b', 'c'), ('b', 'd'), ('e','f')]
 177
 178     for x in  toposort( nodes, route):
 179         for a in x:
 180             print a
 181
 182     raise SystemExit
 183
 184
 185
 186     import pprint, traceback
 187     nodes= [ 0,1,2,3,4,5 ]
 188     testingValues = [
 189         [ (0,1),(1,2),(2,3),(3,4),(4,5)],
 190         [ (0,1),(0,2),(1,2),(3,4),(4,5)],
 191         [
 192         (0,1),
 193         (0,2),
 194         (0,2),
 195                     (2,4),
 196                     (2,5),
 197                 (3,2),
 198         (0,3)],
 199         [
 200         (0,1), # 3-element cycle test, no orphan nodes
 201         (1,2),
 202         (2,0),
 203                     (2,4),
 204                     (2,5),
 205                 (3,2),
 206         (0,3)],
 207         [
 208         (0,1),
 209         (1,1),
 210         (1,1),
 211                 (1,4),
 212                 (1,5),
 213                 (1,2),
 214         (3,1),
 215         (2,1),
 216         (2,0)],
 217         [
 218             (0,1),
 219             (1,0),
 220             (0,2),
 221             (0,3),
 222         ],
 223         [
 224             (0,1),
 225             (1,0),
 226             (0,2),
 227             (3,1),
 228         ],
 229     ]
 230     print 'sort, no recursion allowed'
 231     for index in range(len(testingValues)):
 232 ##        print '    %s -- %s'%( index, testingValues[index])
 233         try:
 234             print '        ', sort( nodes, testingValues[index] )
 235         except:
 236             print 'exception raised'
 237     print 'toposort, no recursion allowed'
 238     for index in range(len(testingValues)):
 239 ##        print '    %s -- %s'%( index, testingValues[index])
 240         try:
 241             print '        ', toposort( nodes, testingValues[index] )
 242         except:
 243             print 'exception raised'
 244     print 'sort, recursion allowed'
 245     for index in range(len(testingValues)):
 246 ##        print '    %s -- %s'%( index, testingValues[index])
 247         try:
 248             print '        ', sort( nodes, testingValues[index],0 )
 249         except:
 250             print 'exception raised'
 251     print 'toposort, recursion allowed'
 252     for index in range(len(testingValues)):
 253 ##        print '    %s -- %s'%( index, testingValues[index])
 254         try:
 255             print '        ', toposort( nodes, testingValues[index],0 )
 256         except:
 257             print 'exception raised'
 258
 259
 260