## Recipe 18.18. Topological Sort## ProblemYou have a collection of items and partial order information (i.e., an indication as to which items should appear before others). You want to arrange the items in a list that obeys the partial order information. ## SolutionUse the algorithm by R. E. Tarjan from 1972. The algorithm is a clever modification of depth first traversal over a directed graph. Here is a complete and self contained function to perform this task (don't be alrmed by its apparent length; there are only 25 real lines of code it in):
def topological_sort(items, partial_order):
"""Perform topological sort.
Here are a few sample calls and the output they produce: topological_sort([1,2,3], [(1,2),(1,3),(3,2)]) # --> [1,3,2] topological_sort([1,2], [(2,1),(2,1)]) # --> [2,1] topological_sort([1,2], [(1,2),(2,1)]) # --> None topological_sort([0,1,2], [(0,1),(1,2),(2,1)]) # --> None ## DiscussionThis problem had no known linear time solution until R. E. Tarjan presented it in 1972. The algorithm consists of these steps: - Convert the input into a directed graph that represents the partial order. The graph contains a node for each item in the list to be sorted and an arc a->b for every input pair (a,b) in the partial order list.
- Find all the root nodes (nodes with no incoming arcs, which represent items with no preceding items).
- Repeatedly output a root node and remove it from the graph.
Whenever removing a root from the graph converts some of its
direct children into roots, they are added to the list of
currently known roots.
The algorithm terminates when there are no root nodes left. At this point, if the graph is not empty, it means there is a loop in the partial order and it is impossible to produce the desired output.
The trick in doing this efficiently is in a graph representation that supports finding a root node in O(1) time. We achieve this by keeping the count of incoming arcs (a.k.a the input degree) with each node and maintaining a list of currently known roots. The incoming arcs count is easily generated while building the graph and easily updated when removing a node. In the Python implementation above we use a dictionary to represent the graph. It is not hard to see that the running time is O(V+E) (V is the number of vertices and E the number of nodes in the graph). When the order information is partial, there can be many orderings that satisfy it. The Tarjan algorithm generates one of the possible solutions by arbitrarily selecting the root to be output in each iteration. If your input has a different structure, you can easily modify the trivial first step (converting the input into a graph representation). For example, merging several chains while preserving their internal order can be done with this modification: def topological_sort(chains): ... # step 1 - create a directed graph representing the input. # ... graph = {} for chain in chains: add_node(graph, chain[0]) for i in range(len(chain)-1): add_node(graph, chain[i+1]) add_arc(graph, chain[i], chain[i+1]) ... Now the following code: chains = [[1,4,5], [6], [1,3,5,2], [3,7], [8,7]] print "merged:", topological_sort(chains) procuces this output: merged: [8, 6, 1, 3, 7, 4, 5, 2] Another useful variant is when you want to sort a collection of items of arbitrary types which cannot be used as keys in a dictionary (or can, but not efficiently). In this case you can put them in an array and pass their indexes to topological_sort(). The returned list will then contain the order in which to iterate over the array to satisfy the partial order information. It is also easy to convert the function into an iterator by replacing the line sorted.append(root) with yield root and making the appropriate changes wherever the 'sorted' list appears, plus raising an exception instead of returning None when we find a loop. This sort is not stable (items with no order information do not necessarily retain their relative order in the output). It can be made stable by storing the original item indexes in the graph and using a heap instead of a simple list for the collection of currently known roots. When choosing the root to output, it is then possible to output the root with the smallest original index. This modification will increase the run time from O(n) to O(n log(n)) [This is an upper bound; I did not do the actual analysis. It may be somewhat less than that]. In the above implementation I avoided using a class for the graph representation to keep the code short and focused on the algorithm. In addition, I refrained from relying on any external module, so that the code can be copied as is and run in any environment. If your code requires other graph traversals or calculations, you should consider using a full graph module (several are available on the Internet). ## See AlsoTopological Sorting in any book on algorithms and data structures. For example: Robert Sedgewick, Another approach by Bruno R. Preiss: http://www.brpreiss.com/books/opus7/html/page555.html ## LicensePermission is hereby granted to copy, modify and use the above source code for any purpose as long as the following comment line is included with it: # Original topological sort code written by Ofer Faigon (www.bitformation.com) and used with permission |