Topological Sort in Python

Apr. 2005

By Ofer Faigon
www.bitFormation.com

Articles

Recipe 18.18. Topological Sort

Problem

You 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.

Solution

Use 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. items is a list of items to be sorted. partial_order is a list of pairs. If pair (a,b) is in it, it means that item a should appear before item b. Returns a list of the items in one of the possible orders, or None if partial_order contains a loop. """ def add_node(graph, node): """Add a node to the graph if not already exists.""" if not graph.has_key(node): graph[node] = [0] # 0 = number of arcs coming into this node. def add_arc(graph, fromnode, tonode): """Add an arc to a graph. Can create multiple arcs. The end nodes must already exist.""" graph[fromnode].append(tonode) # Update the count of incoming arcs in tonode. graph[tonode][0] = graph[tonode][0] + 1 # step 1 - create a directed graph with an arc a->b for each input # pair (a,b). # The graph is represented by a dictionary. The dictionary contains # a pair item:list for each node in the graph. /item/ is the value # of the node. /list/'s 1st item is the count of incoming arcs, and # the rest are the destinations of the outgoing arcs. For example: # {'a':[0,'b','c'], 'b':[1], 'c':[1]} # represents the graph: c <-- a --> b # The graph may contain loops and multiple arcs. # Note that our representation does not contain reference loops to # cause GC problems even when the represented graph contains loops, # because we keep the node names rather than references to the nodes. graph = {} for v in items: add_node(graph, v) for a,b in partial_order: add_arc(graph, a, b) # Step 2 - find all roots (nodes with zero incoming arcs). roots = [node for (node,nodeinfo) in graph.items() if nodeinfo[0] == 0] # step 3 - repeatedly emit a root and remove it from the graph. Removing # a node may convert some of the node's direct children into roots. # Whenever that happens, we append the new roots to the list of # current roots. sorted = [] while len(roots) != 0: # If len(roots) is always 1 when we get here, it means that # the input describes a complete ordering and there is only # one possible output. # When len(roots) > 1, we can choose any root to send to the # output; this freedom represents the multiple complete orderings # that satisfy the input restrictions. We arbitrarily take one of # the roots using pop(). Note that for the algorithm to be efficient, # this operation must be done in O(1) time. root = roots.pop() sorted.append(root) for child in graph[root][1:]: graph[child][0] = graph[child][0] - 1 if graph[child][0] == 0: roots.append(child) del graph[root] if len(graph.items()) != 0: # There is a loop in the input. return None return sorted

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

Discussion

This problem had no known linear time solution until R. E. Tarjan presented it in 1972.

The algorithm consists of these steps:

  1. 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.
  2. Find all the root nodes (nodes with no incoming arcs, which represent items with no preceding items).
  3. 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 Also

Topological Sorting in any book on algorithms and data structures. For example:

Robert Sedgewick, Algorithms (Addison Wesley, 1983, ISBN 0-201-06672-6), Chapter 32: Directed Graphs.

Another approach by Bruno R. Preiss: http://www.brpreiss.com/books/opus7/html/page555.html

License

Permission 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