findCycles method

List<List<String>> findCycles()

Find cycles in the graph.

Returns a list of cycles, where each cycle is a list of node IDs.

Implementation

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

  void dfs(String nodeId) {
    visited.add(nodeId);
    recursionStack.add(nodeId);
    recursionSet.add(nodeId);

    final node = _nodes[nodeId];
    if (node != null) {
      for (final importId in node.imports) {
        if (recursionSet.contains(importId)) {
          // Found a cycle
          final cycleStart = recursionStack.indexOf(importId);
          cycles.add(recursionStack.sublist(cycleStart).toList());
        } else if (!visited.contains(importId)) {
          dfs(importId);
        }
      }
    }

    recursionStack.removeLast();
    recursionSet.remove(nodeId);
  }

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

  return cycles;
}