Topological Class

The Topological class is a GraphAlgorithm extension that illustrates an algorithm for finding a topological ordering of vertices in simple directed graphs. That is, it produces an ordering of the vertices such that for every edge , we have i<j. It can be shown that such an ordering exists if and only if G=(V,E) has no directed cycles.

Typically, a topological ordering is produced by iteratively identifying and then deleting vertices of in-degree 0. Because we wish to preserve the original edges and vertices, our version recolors rather than deletes vertices of adjusted in-degree 0. To support this, the algDegree array is used to maintain the adjusted in-degrees of vertices. The init() method uncolors the Graph, fetches an array of the Graph's Vertex objects, and creates/initializes the algDegree array. On each invocation, the step() method scans the algDegree array for a vertex of 0 in-degree. If no such vertex exists, then no topological ordering exists and the graph contains a cycle. Otherwise, the step() method updates the algDegree array and recolors the vertex and appropriate edges to indicate they are no longer considered as part of the graph.

Using this method in general would be inappropriate because it dramatically increases the time complexity. This algorithm is fairly simple, and the source code is included here to demonstrate how the GraphAlgorithm class may be extended.

package GraphStuff;

import MyUtil.*;

public final class Topological extends GraphAlgorithm {

   private int orgColorNum,vertexCount;

   private Vertex[] v;

   private int[] algDegree;

   private String ordering = "";

   private boolean p_completedInit=false;

   public int GraphType() {return GraphPanel.Simple;}

   public String title() {
     return "Topological Ordering - directed";
   }

   static public final String failedInit = "Error: Cannot Initialize\n";

   static public final String noEdges = 
   "This graph has no edges, so every ordering is topological.\n";

   static public final String noVertices = 
   "This graph has no vertices to order.\n";

   static public final String ready = "Press step to continue.\n";

   static public final String description =
   "This algorithm finds a topological ordering of the vertices. At each "
  +"step, we add a vertex of\n"
  +"`0 in-degree' to the ordering. The vertex and its edges are recolored "
  +"(instead of deleted) and\n"
  +" are no longer considered as part of the graph. ";

   public boolean showLabels() {return true;}

   public String init (GraphPanel gP) {
      if (gP==null)
         return failedInit;
      Graph g = gP.graph;
      if (g==null)
         return failedInit;
      if (g.numVertices()==0)
         return noVertices;
      if (g.numEdges()==0)
         return noEdges;
      orgColorNum=g.uncolor();
      v = g.vertices();
      algDegree = new int[v.length];
      for (int i=0;i<v.length;i++) {
          algDegree[i] = v[i].inDegree();
      }
      vertexCount=0;
      p_completedInit=true;
      return description + ready;
   }

   public String step(GraphPanel gP) {
      if (gP==null)
         return failedInit;
      Graph g = gP.graph;
      if (g==null || !p_completedInit)
         return failedInit;
      if (vertexCount>=v.length)
         return null;            // already finished
      int i;
      for(i=0;i<v.length && algDegree[i]!=0;i++);
      if (i==v.length)
         return "None of the vertices have `0 in-degree'.  This means the graph"
                +" contains a cycle,\n and so the vertices" 
                +" do not have a topological ordering.";
      v[i].colorNum(orgColorNum+1);      
      algDegree[i]--;
      if (vertexCount!=0)
         ordering=ordering+","+v[i].vName();
      else ordering = v[i].vName();
      vertexCount++;

      // cannot use the outEdges() method, since we need to update algDegree[j]
      // and v[j].vNum() might not equal j
      Edge E;
      for(int j=0;j<v.length;j++) {
         E = g.get(v[i].vNum(),v[j].vNum());
         if (E!=null) { 
            E.colorNum(orgColorNum+1);
            algDegree[j]--;
         }
      }
      String ret ="Vertex "+v[i].vName()+" has `0 in-degree', so we add it to"
      +" the ordering and no longer consider\n"
      +v[i].vName()+" and its edges as part of the graph.\n";

      if (vertexCount==g.numVertices())
         return ret +"The resulting topological ordering is: " + ordering;
      return ret+"The current ordering is: "+ordering;

   }

}