edgeConnectivity<V> function

int edgeConnectivity<V>({
  1. required Iterable<V> vertices,
  2. required Iterable<V> successorsOf(
    1. V vertex
    ),
  3. bool containsEdge(
    1. V source,
    2. V target
    )?,
  4. bool isDirected = false,
  5. V? source,
  6. V? target,
  7. StorageStrategy<V>? vertexStrategy,
})

Computes the edge connectivity of a graph or between source and target.

Edge connectivity is the minimum number of edges whose removal disconnects the graph (or disconnects source from target).

Uses unit max flow via Dinic's algorithm.

Implementation

int edgeConnectivity<V>({
  required Iterable<V> vertices,
  required Iterable<V> Function(V vertex) successorsOf,
  bool Function(V source, V target)? containsEdge,
  bool isDirected = false,
  V? source,
  V? target,
  StorageStrategy<V>? vertexStrategy,
}) {
  vertexStrategy ??= StorageStrategy.defaultStrategy();
  final vertexList = vertices.toList(growable: false);
  final n = vertexList.length;
  if (n <= 1) return 0;

  containsEdge ??= (u, v) => successorsOf(u).contains(v);

  if (source != null && target != null) {
    if (source == target) return 0;
    final dinic = DinicMaxFlow<V>(
      seedVertices: vertexList,
      successorsOf: successorsOf,
      edgeCapacity: (u, v) => containsEdge!(u, v) ? 1 : 0,
      vertexStrategy: vertexStrategy,
    );
    return dinic(source, target).toInt();
  }

  if (source != null || target != null) {
    throw ArgumentError('Both source and target must be provided, or neither');
  }

  // Global edge connectivity
  if (!isDirected) {
    // In undirected graph, min cut between a fixed vertex s and all other vertices t
    var minCut = n;
    final dinic = DinicMaxFlow<V>(
      seedVertices: vertexList,
      successorsOf: successorsOf,
      edgeCapacity: (u, v) => containsEdge!(u, v) ? 1 : 0,
      vertexStrategy: vertexStrategy,
    );
    final s = vertexList.first;
    for (var i = 1; i < n; i++) {
      final t = vertexList[i];
      final st = dinic(s, t).toInt();
      if (st < minCut) minCut = st;
      if (minCut == 0) return 0;
    }
    return minCut;
  } else {
    // Directed global edge connectivity: min flow over all pairs (s, t)
    var minCut = n;
    final dinic = DinicMaxFlow<V>(
      seedVertices: vertexList,
      successorsOf: successorsOf,
      edgeCapacity: (u, v) => containsEdge!(u, v) ? 1 : 0,
      vertexStrategy: vertexStrategy,
    );
    final s = vertexList.first;
    for (var i = 1; i < n; i++) {
      final t = vertexList[i];
      final st = dinic(s, t).toInt();
      if (st < minCut) minCut = st;
      final ts = dinic(t, s).toInt();
      if (ts < minCut) minCut = ts;
      if (minCut == 0) return 0;
    }
    return minCut;
  }
}