biconnectedComponents<V> function

Iterable<BiconnectedComponent<V>> biconnectedComponents<V>({ required Iterable<V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V>? vertexStrategy, })

Computes the biconnected components of an undirected graph.

Each biconnected component is returned as a record containing its vertices and edges.

Implementation

Iterable<BiconnectedComponent<V>> biconnectedComponents<V>({
  required Iterable<V> vertices,
  required Iterable<V> Function(V vertex) neighboursOf,
  StorageStrategy<V>? vertexStrategy,
}) {
  vertexStrategy ??= StorageStrategy.defaultStrategy();

  final components = <BiconnectedComponent<V>>[];
  final disc = vertexStrategy.createMap<int>();
  final low = vertexStrategy.createMap<int>();
  final stack = <(V, V)>[];
  var time = 0;

  void addComponent((V, V) boundaryEdge) {
    final componentEdges = <(V, V)>{};
    final componentVertices = vertexStrategy!.createSet();
    while (stack.isNotEmpty) {
      final edge = stack.removeLast();
      componentEdges.add(edge);
      componentVertices.add(edge.$1);
      componentVertices.add(edge.$2);
      if ((edge.$1 == boundaryEdge.$1 && edge.$2 == boundaryEdge.$2) ||
          (edge.$1 == boundaryEdge.$2 && edge.$2 == boundaryEdge.$1)) {
        break;
      }
    }
    components.add((vertices: componentVertices, edges: componentEdges));
  }

  // Iterative depth-first search to avoid stack overflows on deep graphs.
  final callStack =
      <
        ({
          V u,
          V? parent,
          Iterator<V> iter,
          int children,
          bool parentEdgeSkipped,
        })
      >[];
  for (final v in vertices) {
    if (!disc.containsKey(v)) {
      disc[v] = low[v] = ++time;
      callStack.add((
        u: v,
        parent: null,
        iter: neighboursOf(v).iterator,
        children: 0,
        parentEdgeSkipped: false,
      ));
      while (callStack.isNotEmpty) {
        final frame = callStack.last;
        final u = frame.u;
        if (frame.iter.moveNext()) {
          final w = frame.iter.current;
          if (w == frame.parent && !frame.parentEdgeSkipped) {
            callStack[callStack.length - 1] = (
              u: u,
              parent: frame.parent,
              iter: frame.iter,
              children: frame.children,
              parentEdgeSkipped: true,
            );
            continue;
          }
          if (disc.containsKey(w)) {
            // Back edge or self-loop
            if (disc[w]! < disc[u]!) {
              stack.add((u, w));
              low[u] = min(low[u]!, disc[w]!);
            }
          } else {
            // Tree edge
            callStack[callStack.length - 1] = (
              u: u,
              parent: frame.parent,
              iter: frame.iter,
              children: frame.children + 1,
              parentEdgeSkipped: frame.parentEdgeSkipped,
            );
            stack.add((u, w));
            disc[w] = low[w] = ++time;
            callStack.add((
              u: w,
              parent: u,
              iter: neighboursOf(w).iterator,
              children: 0,
              parentEdgeSkipped: false,
            ));
          }
        } else {
          callStack.removeLast();
          if (frame.parent case final p?) {
            low[p] = min(low[p]!, low[u]!);
            final pFrame = callStack.last;
            if ((pFrame.parent == null && pFrame.children > 1) ||
                (pFrame.parent != null && low[u]! >= disc[p]!)) {
              addComponent((p, u));
            }
          }
        }
      }
      if (stack.isNotEmpty) {
        final componentEdges = <(V, V)>{};
        final componentVertices = vertexStrategy.createSet();
        while (stack.isNotEmpty) {
          final edge = stack.removeLast();
          componentEdges.add(edge);
          componentVertices.add(edge.$1);
          componentVertices.add(edge.$2);
        }
        components.add((vertices: componentVertices, edges: componentEdges));
      } else if (neighboursOf(v).isEmpty) {
        // Isolated vertex forms its own component
        final componentVertices = vertexStrategy.createSet()..add(v);
        components.add((vertices: componentVertices, edges: <(V, V)>{}));
      }
    }
  }

  return components;
}