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
    // have already been visited.
    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;
    queue.addFirst(vertex);
  }

  // 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();
}