Class MaxFlow

java.lang.Object

org.episteme.core.mathematics.discrete.graph.flow.MaxFlow

public class MaxFlow
extends Object

Ford-Fulkerson algorithm for maximum flow.

Finds maximum flow from source to sink in flow network. Uses DFS to find augmenting paths. O(E * max_flow) complexity.

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Constructor Summary

Constructors

Constructor	Description
MaxFlow()

Method Summary

Modifier and Type	Method	Description
static <V> Real	edmondsKarp(WeightedGraph<V,Real> graph, V source, V sink)	Edmonds-Karp algorithm (Ford-Fulkerson with BFS).
static <V> Real	fordFulkerson(WeightedGraph<V,Real> graph, V source, V sink)	Computes maximum flow using Ford-Fulkerson with DFS.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MaxFlow

public MaxFlow()

Method Details

fordFulkerson

public static <V> Real fordFulkerson(WeightedGraph<V,Real> graph,
 V source,
 V sink)

Computes maximum flow using Ford-Fulkerson with DFS.

Type Parameters:

V - the type of vertices

Parameters:

graph - flow network (must be a WeightedGraph with Real weights)

source - source vertex

sink - sink vertex

Returns:

maximum flow value

edmondsKarp

public static <V> Real edmondsKarp(WeightedGraph<V,Real> graph,
 V source,
 V sink)

Edmonds-Karp algorithm (Ford-Fulkerson with BFS).

O(VE²) complexity - polynomial time. Guaranteed to terminate for irrational capacities.