Login
Close
Register
Close Window

TDDE22 Fall 2021

Chapter 11 Graphs

Show Source |    | About   «  11.3. Graph Traversals   ::   Contents   ::   11.5. Shortest-Paths Problems  »

11.4. Topological Sort

11.4.1. Topological Sort

Assume that we need to schedule a series of tasks, such as classes or construction jobs, where we cannot start one task until after its prerequisites are completed. We wish to organize the tasks into a linear order that allows us to complete them one at a time without violating any prerequisites. We can model the problem using a DAG. The graph is directed because one task is a prerequisite of another – the vertices have a directed relationship. It is acyclic because a cycle would indicate a conflicting series of prerequisites that could not be completed without violating at least one prerequisite. The process of laying out the vertices of a DAG in a linear order to meet the prerequisite rules is called a topological sort.

Figure 11.4.1: An example graph for topological sort. Seven tasks have dependencies as shown by the directed graph.

Figure 11.4.1 illustrates the problem. An acceptable topological sort for this example is J1, J2, J3, J4, J5, J6, J7. However, other orders are also acceptable, such as J1, J3, J2, J6, J4, J5, J7.

11.4.1.1. Depth-first solution

A topological sort may be found by performing a DFS on the graph. When a vertex is visited, no action is taken (i.e., function PreVisit does nothing). When the recursion pops back to that vertex, function PostVisit prints the vertex. This yields a topological sort in reverse order. It does not matter where the sort starts, as long as all vertices are visited in the end. Here is implementation for the DFS-based algorithm.

void topsortDFS(Graph G) {
  int v;
  for (v=0; v<G.nodeCount(); v++)
    G.setValue(v, null); // Initialize
  for (v=0; v<G.nodeCount(); v++)
    if (G.getValue(v) != VISITED)
      tophelp(G, v);
}

void tophelp(Graph G, int v) {
  G.setValue(v, VISITED);
  int[] nList = G.neighbors(v);
  for (int i=0; i< nList.length; i++)
    if (G.getValue(nList[i]) != VISITED)
      tophelp(G, nList[i]);
  printout(v);
}

Using this algorithm starting at J1 and visiting adjacent neighbors in alphabetic order, vertices of the graph in Figure 11.4.1 are printed out in the order J7, J5, J4, J6, J2, J3, J1. Reversing this yields the topological sort J1, J3, J2, J6, J4, J5, J7.

Here is another example.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

11.4.1.2. Queue-based Solution

We can implement topological sort using a queue instead of recursion, as follows.

First visit all edges, counting the number of edges that lead to each vertex (i.e., count the number of prerequisites for each vertex). All vertices with no prerequisites are placed on the queue. We then begin processing the queue. When Vertex \(v\) is taken off of the queue, it is printed, and all neighbors of \(v\) (that is, all vertices that have \(v\) as a prerequisite) have their counts decremented by one. Place on the queue any neighbor whose count becomes zero. If the queue becomes empty without printing all of the vertices, then the graph contains a cycle (i.e., there is no possible ordering for the tasks that does not violate some prerequisite). The printed order for the vertices of the graph in Applying the queue version of topological sort to the graph of Figure 11.4.1 produces J1, J2, J3, J6, J4, J5, J7. Here is an implementation for the algorithm.

Here is the code to implement the queue-based topological sort:

void topsortBFS(Graph G) {          // Topological sort: Queue
  Queue Q = new LQueue(G.nodeCount());
  int[] Count = new int[G.nodeCount()];
  int[] nList;
  int v;
  for (v=0; v<G.nodeCount(); v++) Count[v] = 0; // Initialize
  for (v=0; v<G.nodeCount(); v++) { // Process every edge
    nList = G.neighbors(v);
    for (int i=0; i< nList.length; i++)
      Count[nList[i]]++;            // Add to v's prereq count
  }
  for (v=0; v<G.nodeCount(); v++)   // Initialize Queue
    if (Count[v] == 0)              // V has no prerequisites
      Q.enqueue(v);
  while (Q.length() > 0) {          // Process the vertices
    v = (Integer)Q.dequeue();
    printout(v);                    // PreVisit for Vertex V
    nList = G.neighbors(v);
    for (int i=0; i< nList.length; i++) {
      Count[nList[i]]--;            // One less prerequisite
      if (Count[nList[i]] == 0)     // This vertex is now free
        Q.enqueue(nList[i]);
    }
  }
}
Settings

Proficient Saving... Error Saving
Server Error
Resubmit

   «  11.3. Graph Traversals   ::   Contents   ::   11.5. Shortest-Paths Problems  »

nsf
Close Window