module to do euler path and topological sorting in python
Mike C. Fletcher
mcfletch at home.com
Sat Mar 17 22:01:10 EST 2001
Not sure what a euler path is, but here's two algos that do topological
sorting. Guts of the second (toposort) are from Tim Peters, first (sort) is
one I built myself, so expect it to have problems :) . I actually built the
second after the first without realising I was creating a toposort (I was
trying to determine parallelism in a "content compiler"), it's just included
for posterity :o) .
Enjoy,
Mike
8<______________ toposort.py _________________
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__":
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'
-----Original Message-----
From: cyberian bear [mailto:cyberian_bear at hotmail.com]
Sent: Saturday, March 17, 2001 8:08 PM
To: python-list at python.org
Subject: module to do euler path and topological sorting in python
can anyone suggest where i can find the modules which would do those two
things.
I have found a website which had a link to topological sorting but it says
that access is forbidden. www.python.org doesn't have any matching reuslts.
thanx
cb
--
http://mail.python.org/mailman/listinfo/python-list
More information about the Python-list
mailing list