Ford Fulkerson Algorithm in Java

Ford Fulkerson Algorithm

Download

Download jar file or use maven. psjava requires Java 1.6 (or above)

<dependency>
    <groupId>org.psjava</groupId>
    <artifactId>psjava</artifactId>
    <version>0.1.19</version>
</dependency>

Example Code

// Construct a graph with capacities.

MutableCapacityGraph<String, Integer> capacityGraph = MutableCapacityGraph.create();
capacityGraph.insertVertex("A");
capacityGraph.insertVertex("B");
capacityGraph.insertVertex("C");
capacityGraph.insertVertex("D");
capacityGraph.addEdge("A", "B", 4);
capacityGraph.addEdge("A", "C", 2);
capacityGraph.addEdge("B", "C", 1);
capacityGraph.addEdge("B", "D", 4);
capacityGraph.addEdge("C", "D", 1);

// You should specify path finder. Basic one is finding by DFS.

MaximumFlowAlgorithm fordFulkerson = FordFulkersonAlgorithm.getInstance(DFSPathFinder.getInstance());
MaximumFlowAlgorithmResult<Integer, CapacityEdge<String, Integer>> result = fordFulkerson.calc(capacityGraph, "A", "D", IntegerNumberSystem.getInstance());

// Maximum flow is 5.
int flow = result.calcTotalFlow();

// Also, you can obtain the flows in each edges by retrieved flow function.

Function<CapacityEdge<String, Integer>, Integer> flowFunction = result.calcFlowFunction();
for (CapacityEdge<String, Integer> e : capacityGraph.getEdges("A"))
	flowFunction.get(e);

Implementation

FordFulkersonAlgorithm.java in GitHub