Topological sorting

Topological sorting in a graph

Given a directed acyclic graph G (V,E), list all vertices such that for all edges (v,w), v is listed before w. Such an ordering is called topological sorting and vertices are in topological order. For example, topological sort for below graph would be: 1,2,3,5,4,6

topological sort

A topological ordering is not unique and a DAG can have more than one topological sort. For example, for above graph, 1,5,2,3,6,4 is also correct topological sort.

How to do a topological sort on a graph?

To start topological sort, we need a node which has zero incoming edges. If there is no such node in the graph, the graph is not directed acyclic graph, DAG. DAG will have at least one such node. Let’s G0 is the graph and V0 is the vertex with zero incoming node. So, V0 becomes the first vertex in order.
Now if we take out V0 and all the edges coming out from it, it leaves a graph G1, there must be a vertex V1 in G1 which has zero incoming edges. V1 is added to topological order.
TheV1 is removed from G1 which leaves us with G2 with TheV2 as candidate node. This goes on until there is no nodes remaining in the original graph G.

At any point in time, we cannot move forward, when there is no node with zero incoming nodes, it means there is a cycle in the graph and given graph is not a DAG.

Above description actually gives away the implementation detail too. We look for a vertex with zero incoming edges and take that. Then we remove all the edges coming out of that node from the graph, which will decrease the number of edges coming on to the neighbor nodes. Again select a node which has zero incoming edges and continues by removing edges.

Let’s take an example and work it out.

topological sorting

Topological sort: implementation

package com.company.Graphs;

import java.util.*;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyMatrix {
    private boolean [][] G;
    private boolean isDirected;

    public AdjacencyMatrix(int numNodes, boolean isDirected){
        this.G  = new boolean[numNodes+1][numNodes+1];
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){
        this.G[start][dest] = true;
        if(!isDirected){
            this.G[dest][start] = true;
        }
    }

    public boolean isEdge(int start, int dest){
        return this.G[start][dest];
    }

    public ArrayList<Integer> topologicalSort(){

        int[] inDegree = new int[this.G.length];
        boolean[] visited = new boolean[this.G.length];
        ArrayList<Integer> toplogicalOrder = new ArrayList<>();

        //Complexity of O(n^2)
        for(int i=1; i<this.G.length; i++) {
            for (int j = 1; j < this.G.length; j++) {
                if (this.G[i][j]) {
                    inDegree[j] += 1;
                }
            }
        }
        /* We will traverse each node */
        for(int i=1; i<this.G.length; i++){
            /* find a node with zero in degree */
            int u  = findNextNode(inDegree, visited);
            /* If there is no node with zero in degree,
            topological sort not possible */
            if(u != -1){
                toplogicalOrder.add(u);
                visited[u] = true;
                /* decrease in degree of each node adjacent
                to node wih zero in degree */
                for(int v=1; v<this.G.length; v++) {
                    if (this.G[u][v]) {
                        inDegree[v]--;
                    }
                }
            }
            else{
                System.out.println("\n Topological sort no possible");
                return toplogicalOrder;
            }
        }
        return toplogicalOrder;
    }

    private int findNextNode(int indegree[], boolean[] visited){
        for( int i=1; i< this.G.length; i++){
            if(indegree[i] == 0 && !visited[i]){
                return i;
            }
        }
        return -1;
    }
}

The complexity of topological sort implementation with adjacency matrix representation is O(V2). For each vertex we find the vertex with zero in-degree, hence the quadratic time.

Topological sort adjacency list represented graph

package com.company.Graphs;

import java.util.*;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyList {
    private Map<Integer, ArrayList<Integer>> G;
    boolean isDirected;

    public AdjacencyList(boolean isDirected){
        this.G = new HashMap<>();
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){

        if(this.G.containsKey(start)){
            this.G.get(start).add(dest);
        }else{
            this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
        }

        if(!this.G.containsKey(dest)) {
            this.G.put(dest, new ArrayList<>());
        }
        //In case graph is undirected
        if(!this.isDirected) {
                this.G.get(dest).add(start);
        }
    }

    public boolean isEdge(int start, int dest){
        if(this.G.containsKey(start)){
            return this.G.get(start).contains(dest);
        }

        return false;
    }

    public ArrayList<Integer> topologicalSort(){

        int[] inDegree = new int[this.G.size()+1];
        boolean[] visited = new boolean[this.G.size()+1];
        ArrayList<Integer> topologicalOrder = new ArrayList<>();

        //Complexity of O(V + E)
        for(int u: this.G.keySet()){
            for (int v : this.G.get(u)){
                    inDegree[v] += 1;
            }
        }


        /* We will traverse each node */
        for(int i=1; i<this.G.size()+1; i++){
            /* find a node with zero in degree */
            int u  = findNextNode(inDegree, visited);
            /* If there is no node with zero in degree,
            topological sort not possible */
            if(u != -1){
                topologicalOrder.add(u);
                visited[u] = true;
                /* decrease in degree of each node adjacent
                to node wih zero in degree */
                for(int v : this.G.get(u)) {
                    inDegree[v]--;
                }
            }
            else{
                System.out.println("\n Topological sort no possible");
                return topologicalOrder;
            }
        }
        return topologicalOrder;
    }

    private int findNextNode(int inDegree[], boolean[] visited){
        for( int i=1; i< this.G.size()+1; i++){
            if(inDegree[i] == 0 && !visited[i]){
                return i;
            }
        }
        return -1;
    }
}

The complexity of this implementation is also O(V2) as still we scan all vertices to find the vertex with zero indegree.

Whenever we are updating the in-degree of all the adjacent node, we can store all the vertices for which in-degree becomes zero in a queue. So we don’t need to separately search for the node with zero in-degree, we can simply take the front of the queue, which will reduce the time complexity to O(V + E) with an additional space complexity of O(V). This is called Kahn’s algorithm.

Below is the code for topological sorting using Depth First traversal. We are using a global variable here count. Idea is that all the nodes which are descendant of node u will come after vertex u in topological order. If we fill the array in reverse order, all the descendants will be filled up first and then the starting node.

    private void topologicalSortDFS( int u, boolean[] visited,
                                    int[] topologicalOrder) {
        // Do a DFS starting from u
        if ( ! visited[u] ) {
            visited[u] = true;
            for (int v: this.G.get(u)) {
                topologicalSortDFS(v, visited, topologicalOrder);
            }
            this.count++;
            topologicalOrder[ this.G.size() + 1 - this.count ] = u;
        }
    }

    public void topologicalOrder() {

        boolean[] visited = new boolean[this.G.size() + 1];
        int[] topologicalOrder = new int[this.G.size() + 1];

        for (int i = 1; i < this.G.size() + 1; i++) {
            if (!visited[i]) {
                topologicalSortDFS(i, visited, topologicalOrder);
            }
        }
        Arrays.stream(topologicalOrder).forEach(i -> System.out.println(i));
    }

The complexity of above implementation is O(V + E) with adjacency list represented graph.

Please share if there is something wrong or missing. If you are preparing for an interview and want to have personalized coaching for your preparation, please signup for free demo class.