getCycles method

List<List<String>> getCycles()

Gets all cycles in the graph.

Returns a list of cycles, where each cycle is represented as a list of node IDs forming the cycle path.

Example:

final cycles = controller.getCycles();
for (final cycle in cycles) {
  print('Cycle: ${cycle.join(' -> ')}');
}

Implementation

List<List<String>> getCycles() {
  final visited = <String>{};
  final recursionStack = <String>{};
  final cycles = <List<String>>[];

  // Build adjacency list
  final adjacencyList = <String, List<String>>{};
  for (final connection in _connections) {
    adjacencyList
        .putIfAbsent(connection.sourceNodeId, () => [])
        .add(connection.targetNodeId);
  }

  void dfs(String nodeId, List<String> path) {
    visited.add(nodeId);
    recursionStack.add(nodeId);
    path.add(nodeId);

    final neighbors = adjacencyList[nodeId] ?? [];
    for (final neighbor in neighbors) {
      if (!visited.contains(neighbor)) {
        dfs(neighbor, List.from(path));
      } else if (recursionStack.contains(neighbor)) {
        // Found a cycle - extract the cycle path
        final cycleStartIndex = path.indexOf(neighbor);
        if (cycleStartIndex != -1) {
          final cyclePath = path.sublist(cycleStartIndex);
          cyclePath.add(neighbor); // Complete the cycle
          cycles.add(cyclePath);
        }
      }
    }

    recursionStack.remove(nodeId);
  }

  // Run DFS from each unvisited node
  for (final nodeId in _nodes.keys) {
    if (!visited.contains(nodeId)) {
      dfs(nodeId, []);
    }
  }

  return cycles;
}