tsort.py

    topological sort orders a directed acyclic graph,
    in order to make sure nodes are only visited after
    all their required nodes have been visited.

listing prepared with lpy.py

  10    __Copyright__ = """
            Copyright (c) 2004 Dirck Blaskey
        
            Permission is granted to use this source for any purpose,
                provided that this notice remains.
            
            This software is provided 'as is' without express or implied warranty, 
                and with no claim as to its suitability for any purpose.
                
            (No lifeguard on duty, use at your own risk.)
        
            for more information, contact:
                Danbala Software
                http://www.danbala.com
        """

Last Modified:

  28    __Id__="$Id: tsort.py.html,v 1.1 2005/01/26 01:13:52 u37519820 Exp $"

tsort(arcs) - topological sort

    arcs is a list of pairs [(r,s), (r,s)]
    values in the pairs are any dictionary-keyable type

    returns the ordered list or
        raises "loop detected", (item, output[], remainder[])

  37    def tsort(arcs):

nodes is a dictionary of list[2]
[0] is requirement count
[1] is supports list

using a class might be slightly more readable

build the nodes from the graph description:

  48        nodes = {}
  49        for left, right in arcs:        
  50            # add the successor node to predecessor's supports list
  51            t = nodes.get(left, None)
  52            if not t:
  53                nodes[left] = [0,[right]]
  54            else:
  55                t[1].append(right)
  56            
  57            # add the predecessor node to successor's requirements count
  58            t = nodes.get(right, None)
  59            if not t:
  60                nodes[right] = [1,[]]
  61            else:
  62                t[0] = t[0] + 1

nodes is ready, get the keys and prep the output list

  66        keys   = nodes.keys() # get the nodes list
  67        nItems = len(keys)    # number of nodes
  68        out    = [0]*nItems   # output list
  69        outp   = 0            # output point
  70        lo     = 0            # calculation point

for all the keys
    set the number of requirements left
    find any with no requirements
        mark them done and add them to the output list

  78        for k in keys:
  79            t = nodes[k]        # t: [req count, sup list]
  80            if not t[0]:        # no requirements
  81                out[outp] = k   # add to output list
  82                outp = outp + 1

while there are unprocessed items in the output list
    pull the list of supported items from
        the next node on the input side of the output list
    release 1 requirement from all the supported items

  90        while lo < outp:
  91            sups = nodes[out[lo]][1]
  92            lo = lo + 1        
  93            for k in sups:
  94                t = nodes[k]
  95                c = t[0] - 1
  96                t[0] = c
  97                # no more requirements on supported item, 
  98                #   add it to the output list
  99                if not c:
 100                    out[outp] = k
 101                    outp = outp + 1

if we output all the items, there is no loop, everything is ok

 105        if outp == nItems:
 106            return out

loop detected - try to locate the loop.
find the first item with minimum nLeft,
and report that as the loop:

 113        min = 0
 114        item = 0
 115        remainder = []
 116        for k in keys:
 117            n = nodes[k][0]
 118            if n > 0:
 119                remainder.append(k)
 120                if not min or n < min:
 121                    min = n
 122                    item = k
 123        
 124        raise "Loop Detected", (item, out[:outp], remainder)

test()

test tsort, once without a loop, once with

 130    def test():    
 131        list = [ ('a','b'), ('c','d'), ('a','f'), 
 132                 ('f','c'), ('c','i'), ('d','b') ]
 133        
 134        # a correct order is ['a', 'f', 'c', 'd', 'i', 'b']
 135        #  but the order could be arbitrary: dictionary.keys() isn't ordered
 136        print "1: Expecting ['a', 'f', 'c', 'd', 'i', 'b'] (or similar):"
 137        print tsort(list)
 138        print
 139            
 140        list = [ ('a','b'), ('c','d'), ('a','f'), 
 141                 ('f','c'), ('b','c'), ('d','b') ]
 142        # loop : b c, c d, d b
 143        print "2: Expecting a loop at ('c', ['a', 'f'], ['c', 'b', 'd']):"
 144        print tsort(list)
 145    
 146    # kick it off
 147    
 148    if __name__ == "__main__":
 149        test()