COP 3530
Section U03
Spring 2017


                   Topological Sort
                   ================



  The following 2 programs are from Mark Weiss's book, Data Structures and
Algoritm Analysis, Third Edition, Pearson 2012, pp 364, 365.

// the indegree of a vertex u in a directed graph is the number of edges
// thet have that u as their target, i.e. edges <v,u>
// the topological sort works on directed graphs with no cycles.
// the idea is that for all vertices u and v in the graph, if
// there is a path from u to v then u precedes v in the ordering
public void topSort() throws CycleFoundException
{

   // assign a number to each vertex
   for (int counter = 0; counter < NUM_VERTICES; counter++)
   {
       // findNewVertexOfIndegreeZero() returns a vertex 
       // of indegree 0, o null if there is none
       Vertex v = findNewVertexOfIndegreeZero();
       if (v == null)
          throw new CycleFoundException(); 
       v.topNum = counter;
       // w adjacent to n means that there is 
       for each vertex w adjacent to v
          w.indegree--;
   }

}  // end method

The Vertex object has the fields number, indegree, and topNum all, integers.
The field topNum indicates its position in the order.
If we represent the graph by adjacency lists (this time the list of v contains the nodes
<u,v>) this algorithm has complexity O(V X V), where V is the number of vertices.

If the vertices are put in a list we can delete those that already have 
been assigned a topNum.

We get the algorithm given below.

public void topSort() throws CycleFoundException
{
   // q contains the nodes that have indegree 0
   Queue<Vertex> q = new Queue<Vertex>(); 
   int counter = 0;

   // put all nodes with indegree 0 in the queue
   for each vertex v
      if (v.indegree == 0)
         q.enqueue(v);
 
   // process the queue
   while (!q.isEmpty())
   {
      vertex v = q.dequeue();
      v.topNum = ++counter; // assign the next number
      
      for each vertex w adjacent to v
         if (--w.indegree == 0)
            q.enqueue(w);

      if (counter != NUM_VERTICES)
            throw new CycleFoundException();
   }

}

The complexity of this algorithm is O( |V| + |E|) despite the double loop
because the for loop is executed only once for each edge.