Topologically ordered graph
Topologically ordered graph

Topological ordering (topological sorting) of a graph is a sequence of its vertices, in which for each edge (u,\\; v) of the graph holds that u precedes v. Hence only acyclic graph can be ordered topologically.

When a topologically ordered graph is plotted, than all of its edges are oriented exactly in one direction.

Usage of topological ordering

Topological ordering can be, for example, used for planning of mutually dependent events/activities. If we perform activities in their topological order, then each activity will be performed after all activities it is dependent on.

Algorithm

The algorithm for topological ordering is based on depth first search. More specifically it is the order of closing vertices in a inversely oriented graph. The asymptotic complexity of this procedure is O(\\vert V \\vert + \\vert E\\vert), where \\vert V \\vert is number of vertices of the graph and \\vert E \\vert is number of its edges.


Code

     /**
      * Prints out topological ordering of the graph given
      * @param graph graph
      */
     public static void orderTopologically(GraphIface graph) {
         //states of particular nodes
         List<Integer> roots = new ArrayList<Integer>();
         for (int i = 0; i < graph.getVertexCount(); i++) {
             //if it does not have any descendants in original graph
             //than it is a root in the inverse graph
             if(graph.getEdges(i).size() == 0) roots.add(i);
         }
         GraphIface inverted = graph.inverse(); //create inversly oriented graph
         int[] state = new int[inverted.getVertexCount()];
 
         for (int i = 0; i < state.length; i++) state[i] = FRESH;
         for (Integer i : roots) {
             doOrdering(inverted, i, state);
         }
     }
     /**
      * Perform the topological ordering (sorting)
      * @param graph graph
      * @param vertexNr number of the current node
      * @param state array of states
      */
     private static void doOrdering(GraphIface graph, int vertexNr, int[] state) {
         state[vertexNr] = OPENED;
         for (Integer i : graph.getEdges(vertexNr)) {
             if (state[i] == FRESH) doOrdering(graph, i, state);
             else if (state[i] == OPENED) throw new IllegalArgumentException("Graph contains cycles");
         }
         System.out.print(" -> " + vertexNr);
         state[vertexNr] = CLOSED;
     }
 

Sources

  • KOLÁŘ, Josef. Teoretická informatika. 2. ed. Praha : Česká informatická společnost, 2004. 205 p. ISBN 80-900853-8-5.







       
 

Place for your banner

Here is the position ready for our customer's banners.