Topological ordering (topological sorting) of a graph is a sequence of its vertices, in which for each edge of the graph holds that precedes . 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 , where is number of vertices of the graph and 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.