network/ford_fulkerson library

🌊 Ford-Fulkerson Algorithm (Maximum Flow)

Computes the maximum flow from source to sink in a flow network using the Ford-Fulkerson method with depth-first search for finding augmenting paths.

• Time Complexity: O(VE²) where V is vertices, E is edges
• Space Complexity: O(V²) for residual graph storage
• Optimality: Guaranteed to find maximum flow
• Completeness: Always terminates for integer capacities

The algorithm works by finding augmenting paths in the residual graph and pushing flow along these paths until no more augmenting paths exist.

Example:

final graph = <String, Map<String, num>>{
  'S': {'A': 10, 'B': 10},
  'A': {'B': 2, 'T': 8},
  'B': {'T': 10},
  'T': {},
};
final maxFlow = fordFulkerson(graph, 'S', 'T');
// Result: 18 (maximum flow from S to T)

Classes

FlowEdge<T>

Represents a flow network edge with capacity and flow

FordFulkersonResult<T>

Ford-Fulkerson with detailed flow information

Functions

fordFulkerson<T>(Map<T, Map<T, num>> graph, T source, T sink) → num

Ford-Fulkerson maximum flow algorithm implementation

fordFulkersonDetailed<T>(Map<T, Map<T, num>> graph, T source, T sink) → FordFulkersonResult<T>

min<T extends num>(T a, T b) → T

Utility function for finding minimum of two numbers