dinicsAlgorithmDetailed<T> function

DinicsResult<T> dinicsAlgorithmDetailed<T>(Map<T, Map<T, num>> graph, T source, T sink)

Implementation

DinicsResult<T> dinicsAlgorithmDetailed<T>(
  Map<T, Map<T, num>> graph,
  T source,
  T sink,
) {
  final stopwatch = Stopwatch()..start();

  // Build flow network
  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);
        edgeMap['${from}_$to'] = edge;
      }
    }
  }

  // Add reverse edges
  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;
  final layeredNetworks = <Map<T, int>>[];
  final blockingFlows = <num>[];

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

    layeredNetworks.add(Map<T, int>.from(levels));

    // Find blocking flow
    final blockingFlow = _findBlockingFlow(flowNetwork, source, sink, levels);
    if (blockingFlow == 0) break;

    blockingFlows.add(blockingFlow);
    maxFlow += blockingFlow;
  }

  stopwatch.stop();

  return DinicsResult<T>(
    maxFlow: maxFlow,
    flowNetwork: flowNetwork,
    phasesCount: layeredNetworks.length,
    layeredNetworks: layeredNetworks,
    blockingFlows: blockingFlows,
    executionTime: stopwatch,
  );
}