More trip planner testing with colors
[busui.git] / labs / openlayers / tools / toposort.py
blob:a/labs/openlayers/tools/toposort.py -> blob:b/labs/openlayers/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'