dinicsAlgorithm<T> function

num dinicsAlgorithm<T>(Map<T, Map<T, num>> graph, T source, T sink)

Dinic's maximum flow algorithm implementation

graph represents the flow network as adjacency list with edge capacities source is the source node sink is the sink/target node

Returns the maximum flow value from source to sink.

Throws ArgumentError if source or sink nodes don't exist in the graph.

Implementation

num dinicsAlgorithm<T>(Map<T, Map<T, num>> graph, T source, T sink) {
  // Input validation
  if (!graph.containsKey(source)) {
    throw ArgumentError('Source node $source not found in graph');
  }
  if (!graph.containsKey(sink)) {
    throw ArgumentError('Sink node $sink not found in graph');
  }
  if (source == sink) {
    throw ArgumentError('Source and sink cannot be the same node');
  }

  // Build flow network with DinicsEdge objects
  final flowNetwork = <T, List<DinicsEdge<T>>>{};
  final edgeMap = <String, DinicsEdge<T>>{};

  for (final entry in graph.entries) {
    final from = entry.key;
    final neighbors = entry.value;

    flowNetwork[from] = <DinicsEdge<T>>[];

    for (final neighborEntry in neighbors.entries) {
      final to = neighborEntry.key;
      final capacity = neighborEntry.value;

      if (capacity > 0) {
        final edge = DinicsEdge<T>(from, to, capacity);
        flowNetwork[from]!.add(edge);

        // Store edge for reverse edge creation
        final edgeKey = '${from}_$to';
        edgeMap[edgeKey] = edge;
      }
    }
  }

  // Add reverse edges for residual graph
  for (final edges in flowNetwork.values) {
    for (final edge in edges) {
      final reverseKey = '${edge.target}_${edge.source}';
      if (!edgeMap.containsKey(reverseKey)) {
        final reverseEdge = DinicsEdge<T>(edge.target, edge.source, 0);
        flowNetwork[edge.target] ??= <DinicsEdge<T>>[];
        flowNetwork[edge.target]!.add(reverseEdge);
        edgeMap[reverseKey] = reverseEdge;
      }
    }
  }

  num maxFlow = 0;

  // Main Dinic's algorithm loop
  while (true) {
    // Build layered network using BFS
    final levels = _buildLayeredNetwork(flowNetwork, source, sink);
    if (levels[sink] == null) break; // No path exists

    // Find blocking flow in the layered network
    final blockingFlow = _findBlockingFlow(flowNetwork, source, sink, levels);
    if (blockingFlow == 0) break; // No more flow can be pushed

    maxFlow += blockingFlow;
  }

  return maxFlow;
}