﻿ Topological ordering

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
}
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.