cycleVertex property

T? cycleVertex

Returns the first vertex detected that is part of a cycle.

Returns null if the graph is acyclic.

Implementation

T? get cycleVertex {
  // Start vertex of the cycle.
  T? start;
  final temp = HashSet<T>();
  final perm = HashSet<T>();
  // Marks [this] graph as acyclic.
  var isCyclic = false;
  // Recursive function
  void visit(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 (perm.contains(vertex)) return;
    // A cycle has been detected. Mark graph as acyclic.
    if (temp.contains(vertex)) {
      start = vertex;
      isCyclic = true;
      return;
    }
    // Temporary mark. Marks current vertex as visited.
    temp.add(vertex);
    for (final connectedVertex in edges(vertex)) {
      visit(connectedVertex);
    }
    // Permanent mark, indicating that there is no path from
    // neighbouring vertices back to the current vertex.
    perm.add(vertex);
  }

  // Main loop
  for (final vertex in sortedVertices) {
    if (isCyclic) break;
    visit(vertex);
  }
  return start;
}