cycle property

List<Vertex<T>> cycle

Returns the first cycle detected or an empty list if the graph is acyclic.

Note: A cycle is a path that starts and ends with the same vertex.

Implementation

List<Vertex<T>> get cycle {
  /// Start vertex of the cycle.
  Vertex<T> start;

  // Marks [this] graph as acyclic.
  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) {
      start = vertex;
      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.
    vertex._mark = _Mark.PERMANENT;
  }

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

  // Reset vertex mark.
  // Important! Otherwise method is not idempotent.
  for (final vertex in vertices) {
    vertex._mark = null;
  }

  // Find cycle path.
  if (isCyclic) {
    final crawler = GraphCrawler<T>(edges: edges);
    final cycles = crawler.fastPaths(start, start);
    return (cycles.isNotEmpty) ? cycles.first : [];
  } else {
    return [];
  }
}