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.
Programming Praxis 
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.
My Haskell solution (see http://bonsaicode.wordpress.com/2010/11/19/programming-praxis-topological-sort/ for a version with comments):
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 vsQuick 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:[11], 7:[8,11], 8:[9], 9:[], 10:[], 11:[2, 9, 10]}) G1.name = 'G1' G2 = nx.DiGraph({2:[], 3:[8, 10], 5:[11], 7:[8,11], 8:[9], 9:[], 10:[5], 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.
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.
Oops! Made the link, but didn’t put in the address; my answer is here.
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.[0])) edgelist
vertex_no_incoming.[0] :: (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]
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.[0])) edgelist vertex_no_incoming.[0] :: (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)]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))) ;; #fThe 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)[…] worked with directed graphs (“digraphs”) in a recent exercise. Today’s exercise is another graph theoretical procedure with many applications: […]