This project provides a simple implementation and example of finding the maximum flow of a network.
This implements the Edmonds-Karp algorithm for Ford-Fulkerson using breadth-first search and an adjacency matrix representation of the network.
Utility class: MaxFlowExample
JUnit 5 Test class: MaxFlowExampleTest
The first draft used side-effects in Java, where a method modifies
an object passed to it.
The residualGraph array was passed into the method as a mutable object
to be modified by the method.
It is a simple way to "return" multiple pieces of information,
in this case the int flow (return value) and the int[][] graph.
Most modern programming paradigms (especially Functional Programming) argue for immutability. When a method modifies an object passed into it:
-
Predictability decreases: A developer might not expect their residualGraph array to be changed by a method that looks like a simple calculation.
-
Debugging becomes harder: If the graph state is wrong, you have to hunt down which method modified it.
-
Thread Safety: If multiple threads access that array, side-effects can lead to race conditions.
There is a subtle but important distinction in how these two arrays function within the logic:
-
The
parentarray is "Transient": It is a temporary piece of scratchpad memory used only for a single iteration of a loop. It doesn't represent the "final result" of the algorithm; it's just a tool to get there. -
The
residualGraphis "Stateful": It represents the final state of the flow network. It is the data the user actually wants to inspect after the algorithm finishes.parent: Internal. Hidden inside the utility logic. The user of the class never sees it.residualGraph: External. User has to create this array just to call the method. User manages memory for the algorithm: Poor "encapsulation".
https://metrocs.github.io/NetworkFlow/
