## Topological Sort

### November 19, 2010 A graph G is a collection of its vertices V and the edges E between them: G(V, E); the interstate highway system is an example of a graph, with cities as vertices and highways as edges. A directed graph is a graph in which each edge is identified with a from vertex and a to vertex; the roads in some city centers can be considered a directed graph, because one-way roads only allow traffic in a single direction (Venice has one-way canals, which blew my mind the first time I saw a sensico unico sign). A directed acyclic graph, sometimes called a DAG, is a directed graph in which there are no cycles, that is, by following the successors of a vertex you can never return to that vertex; the tasks involved in building a house form a DAG, in which the framing must be done before drywall can be installed, and the modules of a program library form a DAG, in which some modules must be compiled before others that depend on them.

A topological sort is an ordering of the vertices of a DAG in which each vertex appears before any of the vertices that depend on it. Topological sorts are typically messy, with multiple right answers; a fireman can spray water on a burning building even while his colleagues are searching for anyone still inside. There are many possible topological sorts of the sample graph; one of them is 7 5 11 2 3 8 9 10.

There are many ways to perform a topological sort. Perhaps the simplest is to pick a vertex that has no incoming edges; put it at the head of the sorted output, delete it and all the edges that come from it, and recur until no vertices remain. If there is more than one vertex that has no incoming edges, any of them may be chosen.

Your task is to write functions to identify cyclic graphs and perform topological sort of a graph. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 10 Responses to “Topological Sort”

1. Graham said

Funny timing. In my graduate Algorithms & Data Structues class (I’m a math Ph.D. student, learning programming on the side), we’re to implement a program that takes in a DAG and uses Dijkstra’s Algorithm for shortest paths.

```import Data.List

with :: (a -> b) -> [a] -> (b -> b -> Bool) -> b -> [a]
with t xs eq x = filter ((eq x) . t) xs

noIncoming :: Eq a => [(a, a)] -> [a] -> Maybe a
noIncoming es = find (null . with snd es (==))

isCyclic :: Eq a => [(a, a)] -> Bool
isCyclic = not . null . until (\x -> remove x == x) remove where
remove es = maybe es (with fst es (/=)) . noIncoming es \$ map fst es

tsort :: Eq a => [(a, a)] -> [a]
tsort xs = if isCyclic xs then error "cannot sort cyclic list"
else f xs . nub . uncurry (++) \$ unzip xs where
f es vs = maybe [] (\v -> v : f (with fst es (/=) v) (delete v vs)) \$
noIncoming es vs
```
3. Graham said

Quick answer, if the Python module “networkx.py” is installed:

```#!/usr/bin/env python2.6

import networkx as nx
G1 = nx.DiGraph({2:[], 3:[8, 10], 5:, 7:[8,11], 8:, 9:[], 10:[],
11:[2, 9, 10]})
G1.name = 'G1'
G2 = nx.DiGraph({2:[], 3:[8, 10], 5:, 7:[8,11], 8:, 9:[], 10:,
11:[2, 9, 10]})
G2.name = 'G2'
for G in [G1, G2]:
print "Graph: %s" % G
if nx.is_directed_acyclic_graph(G):
print "Topological sort:\n%s" % nx.topological_sort(G)
else:
print "Sorry, this graph is cyclic"
```

Currently working on my own answer.

4. Graham said

My own answer (though I got help from several sources, all mentioned in the comments). Too
long and cumbersome an answer for my taste, but I’m calling it a day.

5. Graham said

6. Khanh Nguyen said

In F#

//remove vertexes until there is no more edges
let rec remove_vertexs (edgelist: (int * int) list) =
match edgelist with
| [] -> []
| _ ->
let src_vertexs = List.unzip edgelist |> fst
let dst_vertexs = List.unzip edgelist |> snd
let all_vertexs = List.append src_vertexs dst_vertexs
let vertex_no_incoming = Set.difference (all_vertexs |> Set.ofList) (dst_vertexs |> Set.ofList) |> Set.toList
let new_edgelist = List.filter (fun (x,y) -> not (x = vertex_no_incoming.)) edgelist
vertex_no_incoming. :: (remove_vertexs new_edgelist)
//do a remove_vertexs, and append the result with the remaining isolated vertexs
let topologicalsort (edgelist: (int * int) list) =
let all_vertexs = List.append (List.unzip edgelist |> fst) (List.unzip edgelist |> snd)
let remove = remove_vertexs edgelist
let isolated = Set.difference (all_vertexs |> Set.ofList) (remove |> Set.ofList) |> Set.toList
List.append remove isolated

topologicalsort [(5,11);
(11,2);(11,10);(11,9);
(7,11);(7,8);
(8,9);
(3,10);(3,8)]
[/sourecode]

7. Khanh Nguyen said

In F#

```//remove vertexes until there is no more edges
let rec remove_vertexs (edgelist: (int * int) list) =
match edgelist with
| []  -> []
| _   ->
let src_vertexs = List.unzip edgelist |> fst
let dst_vertexs = List.unzip edgelist |> snd
let all_vertexs = List.append src_vertexs dst_vertexs
let vertex_no_incoming =  Set.difference (all_vertexs |> Set.ofList) (dst_vertexs |> Set.ofList) |> Set.toList
let new_edgelist = List.filter (fun (x,y) -> not (x = vertex_no_incoming.)) edgelist
vertex_no_incoming. :: (remove_vertexs new_edgelist)
//do a remove_vertexs, and append the result with the remaining isolated vertexs
let topologicalsort (edgelist: (int * int) list) =
let all_vertexs = List.append (List.unzip edgelist |> fst) (List.unzip edgelist |> snd)
let remove = remove_vertexs edgelist
let isolated = Set.difference (all_vertexs |> Set.ofList) (remove |> Set.ofList) |> Set.toList
List.append remove isolated

topologicalsort [(5,11);
(11,2);(11,10);(11,9);
(7,11);(7,8);
(8,9);
(3,10);(3,8)]
```
8. Guillaume said

Language: Scheme (Gambit)

```; topological sort + cyclic graph detection

(define (topo-sort graph) ; graph is a list of (parent . child) pairs

(let ((t-v (make-table))
(nmax 0))

; init
(for-each (lambda (x)
(table-set! t-v (car x) 0)
(table-set! t-v (cdr x) 0)
)
graph)

; propagate until there is no change anymore
(let loop ()
(if (> nmax (table-length t-v))
#f  ; cyclic graph
(let ((change #f))
(for-each (lambda (x)
(let* ((par (car x))
(kid (cdr x))
(v-par (table-ref t-v par))
(v-kid (table-ref t-v kid))
(v     (max v-kid (+ 1 v-par))))
(and (> v v-kid)
(begin (table-set! t-v kid v)
(set! change #t)
(set! nmax (max nmax v))
))))
graph)
(if change
(loop)
(sort (lambda (x y) (< (cdr x) (cdr y)))
(table->list t-v))))))))

(topo-sort `((5 . 11) (11 . 2) (11 . 10) (11 . 9) (7 . 11) (7 . 8) (8 . 9) (3 . 8) (3 . 10)))
;; ((7 . 0) (5 . 0) (3 . 0) (8 . 1) (11 . 1) (10 . 2) (9 . 2) (2 . 2))

(topo-sort `((5 . 11) (11 . 2) (11 . 10) (11 . 9) (7 . 11) (7 . 8) (8 . 9) (3 . 8) (3 . 10) (10 . 5)))
;; #f
```
9. Guillaume said

The code I posted just above has the advantage of doing cycle detection + sorting in one go, but to the cost of a O(n^2) worst case, for an unlucky edge list order.

Here is a modified version that drastically reduces the worst case, by reordering the edges on the fly. I also made the code somewhat more functional.

Thanks for the stimulating problems!

```;; Language: Scheme (Gambit)
;; In one go: topological sort + cyclic graph detection

(define (topo-sort graph) ; graph is a list of (parent . child) pairs
(let ((t-v (make-table)))
;; init
(for-each (lambda (x)
(table-set! t-v (car x) 0)
(table-set! t-v (cdr x) 0))
graph)
(let ((n-node (table-length t-v)))

;; propagate until there is no change anymore
(let loop ((graph graph))

(let ((result2

;; loop through the graph's edges
(let loop2 ((rest graph) (new-g1 '()) (new-g2 '()) (change #f) (vmax 0) (prev 0))

(cond ((>= vmax n-node) #f) ; cyclic graph detected
((null? rest)   (cons change
(append new-g1 (reverse new-g2)))) ; all edges visited -> done, return new order

(else (let* ((x       (car rest))
(par     (car x))
(kid     (cdr x))
(v-par   (table-ref t-v par))
(v-kid   (table-ref t-v kid))
(v       (max v-kid (+ 1 v-par)))
(prop    (> v v-kid))
(improve (<= v prev))
)

(and prop (table-set! t-v kid v)) ; propagation

(loop2 (cdr rest)
;; The next two lines improve the edge order to reduce cost of the worst case
(if improve (cons x new-g1) new-g1)
(if improve new-g2 (cons x new-g2))
(or change prop)
(max vmax v)
v)))))
))

(and result2   ; in the cyclic case, return #f
(if (car result2)  ; (change)
(loop (cdr result2))  ; (new-graph)
(sort (lambda (x y) (< (cdr x) (cdr y))) ; finished -> return sorted result
(table->list t-v)))))))))

(pretty-print (topo-sort `((5 . 11) (11 . 2) (11 . 10) (11 . 9) (7 . 11) (7 . 8) (8 . 9) (3 . 8) (3 . 10))))
;; ((7 . 0) (5 . 0) (3 . 0) (8 . 1) (11 . 1) (10 . 2) (9 . 2) (2 . 2))

(pretty-print (topo-sort `((5 . 11) (11 . 2) (11 . 10) (11 . 9) (7 . 11) (7 . 8) (8 . 9) (3 . 8) (3 . 10) (10 . 5))))
;; #f

(pretty-print (topo-sort `((4 . 5)(3 . 4)(2 . 3)(1 . 2)(0 . 1))))
;; >> ((0 . 0) (1 . 1) (2 . 2) (3 . 3) (4 . 4) (5 . 5))
;; (3 loops)

(pretty-print (topo-sort `((4 . 5)(3 . 4)(2 . 3)(1 . 2)(0 . 1)(5 . 0))))
;; >> #f
;; (2 loops)
```
10. […] worked with directed graphs (“digraphs”) in a recent exercise. Today’s exercise is another graph theoretical procedure with many applications: […]