findCycles method

List<List<String>> findCycles()

Detects circular dependencies in the graph.

Returns each cycle as an ordered list of node IDs, with the first node repeated at the end to close the loop.

Implementation

List<List<String>> findCycles() {
  final cycles = <List<String>>[];
  final visited = <String>{};
  final stack = <String>{};
  final currentPath = <String>[];

  void dfs(String nodeId) {
    visited.add(nodeId);
    stack.add(nodeId);
    currentPath.add(nodeId);

    for (final dependency in getDependencies(nodeId)) {
      if (stack.contains(dependency)) {
        final cycleStart = currentPath.indexOf(dependency);
        if (cycleStart != -1) {
          cycles.add(
            List.from(currentPath.sublist(cycleStart))..add(dependency),
          );
        }
      } else if (!visited.contains(dependency)) {
        dfs(dependency);
      }
    }

    stack.remove(nodeId);
    currentPath.removeLast();
  }

  for (final nodeId in nodes.keys) {
    if (!visited.contains(nodeId)) {
      dfs(nodeId);
    }
  }

  return cycles;
}