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.

About these ads

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.

  2. 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 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:[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.

  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

    Oops! Made the link, but didn’t put in the address; my answer is here.

  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.[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]

  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.[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)]    
    
  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: [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 611 other followers

%d bloggers like this: