# topologicalOrdering property

List<Vertex<T>> topologicalOrdering

Returns List<Vertex<T>>, a list of all vertices in topological order.

• For every directed edge: (vertex1 -> vertex2), vertex1 is listed before vertex2.

• Note: There is no topological ordering if the graph is cyclic. In that case the function returns null.

• Any self-loop (e.g. vertex1 -> vertex1) renders a directed graph cyclic.

• Based on a depth-first search algorithm (Cormen 2001, Tarjan 1976).

## Implementation

List<Vertex<T>> get topologicalOrdering {
final queue = Queue<Vertex<T>>();

// Marks [this] graph as cyclic.
var isCyclic = false;

// Recursive function
void visit(Vertex<T> vertex) {
// Graph is not a Directed Acyclic Graph (DAG).
// Terminate iteration.
if (isCyclic) return;

// Vertex has permanent mark.
// => This vertex and its neighbouring vertices
if (vertex._mark == _Mark.PERMANENT) return;

// A cycle has been detected. Mark graph as acyclic.
if (vertex._mark == _Mark.TEMPORARY) {
isCyclic = true;
return;
}

// Temporary mark. Marks current vertex as visited.
vertex._mark = _Mark.TEMPORARY;
for (final connectedVertex in _edges[vertex] ?? <Vertex<T>>[]) {
visit(connectedVertex);
}
// Permanent mark, indicating that there is no path from
// neighbouring vertices back to the current vertex.
// We tried all options.
vertex._mark = _Mark.PERMANENT;
}

// Main loop
// Note: Iterating in reverse order of [vertices]
// (approximately) preserves the
// sorting of vertices (on top of the topological sorting.)
// For a sorted topological ordering use
// the getter: [sortedTopologicalOrdering].
//
// Iterating in normal order of [vertices] yields a different
// valid topological sorting.
for (final current in vertices.reversed) {
if (isCyclic) break;
visit(current);
}

// Clearing vertex marks.
// Important! Otherwise method won't be idempotent.
for (final vertex in vertices) {
vertex._mark = null;
}

// Return null if graph is not a DAG.
return (isCyclic) ? null : queue.toList();
}