sortedTopologicalOrdering property

List<Vertex<T>> sortedTopologicalOrdering

Returns a list of all vertices in topological order.

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

  • If a vertex comparator is specified, the sorting will be applied in addition to the topological order. If

  • 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 Kahn's algorithm.

Implementation

List<Vertex<T>> get sortedTopologicalOrdering {
  if (_comparator == null) return topologicalOrdering;

  final result = <Vertex<T>>[];

  // Get modifiable in-degree map.
  final inDegreeMap = this.inDegreeMap;

  // Add all sources (vertices with inDegree == 0) to queue.
  // Using a list instead of a queue to enable sorting of [sources].
  //
  // Note: In an acyclic directed graph there is at least
  //       one vertex with inDegree equal to zero.
  final sources = <Vertex<T>>[];
  for (final vertex in _edges.keys) {
    if (inDegreeMap[vertex] == 0) {
      sources.add(vertex);
    }
  }
  // Initialize count of visited vertices.
  var count = 0;

  // Note: In an acyclic directed graph at least
  // one vertex has outDegree zero.
  while (sources.isNotEmpty) {
    // Sort source vertices:
    sources.sort(_comparator);
    var current = sources.removeAt(0);
    result.add(current);

    // Simulate removing the current vertex from the
    //   graph. => Connected vertices with have inDegree = inDegree - 1.
    for (final vertex in _edges[current] ?? []) {
      inDegreeMap[vertex] -= 1;

      // Add new local source vertices of the remaining graph to the queue.
      if (inDegreeMap[vertex] == 0) {
        sources.add(vertex);
      }
    }
    // Increment count of visited vertices.
    count++;
  }
  return (count != _inDegreeMap.length) ? null : result;
}