Graph Topological Sorting - Build System Order Example

November 20, 2020

Graph Topological Sorting
Build System Example
Code
Complexity

Graph Topological Sorting

This is a well known problem in graph world. Topological sort is to put vertices in order and output a list of vertices in such an order that vertices are in order of dependencies. i.e. The vertices comes first is the independent one, then list the one which are dependent on those.

Connected Graph

In above Directed Graph, following can be possible topological sort order:

A B C D E F G H
OR
A C B E G D F H
OR
B E G A D C F H

Build System Example

The usage of this sort is in the Build system. A build system is where there are different projects or modules are to built. And, it is to decide which module to build first so that updated module can be integrated in the dependent project or module.

Code

class Node {
  //to represent a Vertex
  public String name;
  public List<Node> connectedNodes;
  //...some other data
  public List<Node> adj() {
    return this.connectedNodes;
  }
}
class Graph {
  private List<Node> nodes;
  public List<Node> nodes() {
    return this.nodes;
  }
  
}

public Stack<Node> topological(Graph g) {
  //assumming Graph has method nodes() which gives list of all nodes.
  List<Node> nodes = g.nodes();

  //Set to keep track of visited nodes
  Set<Node> visited = new HashSet();

  //For keeping nodes in order
  Stack<Node> stack = new Stack();

  for (Node node : nodes) {
    helper(node, visited, stack);
  }
}

private void helper(Node node, Set visited, Stack stack) {
    if (visited.contains(node)) {
      continue;
    }
    //mark node visited
    visited.add(node);

    //visit all attached nodes with this vertices
    //Assumming there is a method adj() which gives connected nodes to a vertex
    for (Node n : node.adj()) {
      //recursively visit each node's connected vertices
      helper(n, visited, stack);
    }

    //all connected vertices are exhausted. 
    //Lets add this to our order list
    stack.add(node);
}

//main 
Stack<Node> stack = topological(graph);
//print stack