"""~ @h2{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. @i{listing prepared with lpy.py}@N """ __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: __Id__="$Id: tsort.py.txt,v 1.1 2005/02/02 06:32:35 u37519820 Exp $" '''~ @h3{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[]) ''' 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:""" nodes = {} for left, right in arcs: # add the successor node to predecessor's supports list t = nodes.get(left, None) if not t: nodes[left] = [0,[right]] else: t[1].append(right) # add the predecessor node to successor's requirements count t = nodes.get(right, None) if not t: nodes[right] = [1,[]] else: t[0] = t[0] + 1 #~ nodes is ready, get the keys and prep the output list keys = nodes.keys() # get the nodes list nItems = len(keys) # number of nodes out = [0]*nItems # output list outp = 0 # output point 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""" for k in keys: t = nodes[k] # t: [req count, sup list] if not t[0]: # no requirements out[outp] = k # add to output list 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""" while lo < outp: sups = nodes[out[lo]][1] lo = lo + 1 for k in sups: t = nodes[k] c = t[0] - 1 t[0] = c # no more requirements on supported item, # add it to the output list if not c: out[outp] = k outp = outp + 1 #~ if we output all the items, there is no loop, everything is ok if outp == nItems: return out """~ loop detected - try to locate the loop. find the first item with minimum nLeft, and report that as the loop: """ min = 0 item = 0 remainder = [] for k in keys: n = nodes[k][0] if n > 0: remainder.append(k) if not min or n < min: min = n item = k raise "Loop Detected", (item, out[:outp], remainder) #-------------------------------------------------------------- #~@h3{test()} test tsort, once without a loop, once with def test(): list = [ ('a','b'), ('c','d'), ('a','f'), ('f','c'), ('c','i'), ('d','b') ] # a correct order is ['a', 'f', 'c', 'd', 'i', 'b'] # but the order could be arbitrary: dictionary.keys() isn't ordered print "1: Expecting ['a', 'f', 'c', 'd', 'i', 'b'] (or similar):" print tsort(list) print list = [ ('a','b'), ('c','d'), ('a','f'), ('f','c'), ('b','c'), ('d','b') ] # loop : b c, c d, d b print "2: Expecting a loop at ('c', ['a', 'f'], ['c', 'b', 'd']):" print tsort(list) # kick it off if __name__ == "__main__": test()