Welcome, guest | Sign In | My Account | Store | Cart

Topological sorting is the answer to the following question : in a direct acyclic graph, how can I pick up nodes "in order", such as upstream nodes are always before downstream ones ? Many solutions may exists, many algorithms too.

Alas, it seems I'm too stupid to understand already proposed recipes on topological sorting. Hopefully I do grasp the "write once, read many" concept.

Here, you will find a plain algorithm, optimized only for code clarity, of a topological sorting for direct acyclic graphs, implemented in python from the pseudo code found on wikipedia:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Only tested with python3.2, should work with other versions. Be careful, code indented with tabs, since space is evil è_é

Python, 48 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!/usr/bin/env python3.2

def sort_direct_acyclic_graph(edge_list) :
	# edge_set is consummed, need a copy
	edge_set = set([tuple(i) for i in edge_list])
	
	# node_list will contain the ordered nodes
	node_list = list()
	
	# source_set is the set of nodes with no incomming edges
	node_from_list, node_to_list = zip(* edge_set)
	source_set = set(node_from_list) - set(node_to_list)
	
	while len(source_set) != 0 :
		# pop node_from off source_set and insert it in node_list
		node_from = source_set.pop()
		node_list.append(node_from)
		
		# find nodes which have a common edge with node_from
		from_selection = [e for e in edge_set if e[0] == node_from]
		for edge in from_selection :
			# remove the edge from the graph
			node_to = edge[1]
			edge_set.discard(edge)
			
			# if node_to don't have any remaining incomming edge :
			to_selection = [e for e in edge_set if e[1] == node_to]
			if len(to_selection) == 0 :
				# add node_to to source_set
				source_set.add(node_to)
				
	if len(edge_set) != 0 :
		raise IndexError # not a direct acyclic graph
	else :
		return node_list

u = [
	['a', 'b'], # a -> b, etc.
	['a', 'c'],
	['b', 'e'],
	['c', 'd'],
	['b', 'd'],
	['e', 'f'],
	['c', 'f'],
]

>>> sort_direct_acyclic_graph(u)
['a', 'c', 'b', 'e', 'd', 'f']
Created by yota on Mon, 7 Jan 2013 (GPL3)
Python recipes (4591)
yota's recipes (13)

Required Modules

  • (none specified)

Other Information and Tasks

  • Licensed under the GPL 3
  • Viewed 11998 times
  • Revision 9 (updated 8 years ago)