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