Topological Sort/Ordering

The goal of a topological sort is given a list of items with dependencies, (ie. item 5 must be completed before item 3, etc.) to produce an ordering of the items that satisfies the given constraints. In order for the problem to be solvable, there can not be a cyclic set of constraints. (We can't have that item 5 must be completed before item 3, item 3 must be completed before item 7, and item 7 must be completed before item 5, since that would be an impossible set of constraints to satisfy.) Meaning we can model this problem with a directed unweighted acyclic graph. When all the vertices are topologically ordered in a row all the edges go from left to right.

Kahn's Algorithm

Kahn's algorithm describes a way in which we can find a topological order. In pseudocode the algorithm goes like this

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge so indeg(v)=0
 
while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
 !!!!!OR!!!!!
 for each node m with an edge e from n to m do
        reduce indeg(m) by one
        if indeg(m)==0
            insert m into S
 
if graph still has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

Depending on the order that the nodes n are removed from set S, a different solution is created. A possible solution with an Adjacent matrix could look something like this.

public int[] topsort(){
 int[] indeg = new int[n]; // calculate indegree
 for (int i=0; i<n;i++){
  for (int j=0; j<n; j++){
   indeg[i] += adjMatrix[j][i] ? 1:0;
  }
 }
 Queue S = new LinkedList(); // topsort init queue
 for (int i=0; i<n; i++){
  if(indeg[i]==0) S.add(i);
 }
 int[] result = new int[n]; // topsort step
 for(int i=0; i<n; i++){
  if(!S.isEmpty()){
   result[i] = (int) S.remove();
   for(int j=0; j<n; j++){
    if(adjMatrix[result[i]][j]) {
     indeg[j]--;
     if(indeg[j] == 0) S.add(j);
    }
   }
  }
  return null;
 }
 return result;
}

Or with an Adjacent list

public void sort() {
  StringBuffer sb = new StringBuffer();
  if (isDirected()) {
   LinkedList<Vertex<K>> queue = new LinkedList<Vertex<K>>();
   int counter = 0;
   for (Vertex<K> v : vertices.values()) {
    v.deg = v.indegree; // set indegree of each vertex
    if (v.deg == 0) queue.addFirst(v); // start set
   }
   while (!queue.isEmpty()) {
    Vertex<K> v = queue.removeLast();
    sb.append(v.data + "  ");
    counter++; // count processed vertices
    for (Vertex<K> w : v.adjList)
     if (--w.deg == 0) // decrease indegree of adjecent
     queue.addFirst(w); // Add to S
   }
   if (counter != vertices.size()) {
    sb.replace(0, sb.length(), "Cycle found");
   }
  } else {
   sb.append("Graph is not directed, TopSort not possible.");
  }
  System.out.println(sb);
 }

Time Complexity

If we have $n$ vertices with $m$ edges and have stored that graph in an Adjacency list.

To calculate all vertices indeg takes $O(n+m)$ .
Adding all vertices with indeg 0 to S takes worst case $O(n)$ .
Each edge is followed once to reduce the indeg of a vertex $O(m)$ .
Each node is added and removed once from S so $O(n)$

This then leads to a time complexity of $O(n+m)$ .

Link Prediction Shortest Path