Ford-Fulkerson algorithm

Solved the ford-fulkerson algorithm, which is too vast to explain it comprehensively here. Check Wikipedia for Ford-Fulkerson and Princeton lecture on Ford-Fulkerson.

Looking for code review, optimizations and best practices. Also I request you avoid mentioning renaming GraphFordFuklerson and unit tests not done in separate files as I am aware it's not good practices, but deliberately done for personal convenience.

/**
* A duplex edge is two edges(forward and reverse edge) combined into one.
* In ford-fulkerson algo, we have a concept of forward edge and a reverse edge.
*
* The forward edge is when the "from" node equals "from" node set by constructor
* and
* "to" node equals "to" node set by constructor.
*
* Duplex emulates both these edges by returning different values based on "to" and "from"
* ie, it behaves as both "forward edge" and "backward egde" based on its input parameters.
*
* @param <T>
*/
final class DuplexEdge<T> {
private final T from;
private final T to;
private final double capacity;
private double consumedCapacity;

public DuplexEdge (T from, T to, double capacity, double consumedCapacity) {
if (from == null  || to == null) {
throw new NullPointerException("Neither from nor to should be null.");
}

this.from = from;
this.to = to;
this.capacity = capacity;
this.consumedCapacity = consumedCapacity;
}

/**
* Returns the remaining capacity of that pipe/edge/channel.
* From from and to a determination is made if its a forward edge of backward edge.
* Depending on edge type the capacity is returned.
*
* @param from      the from/source node
* @param to        the to node.
* @return          the remaining capacity on determing if its a forward or reverse edge.
*/
public double getCapacity(T from, T  to) {
if (this.from.equals(from) && this.to.equals(to)) {
return capacity - consumedCapacity;
}

// indicates reverse flow.
if (this.from.equals(to) && this.to.equals(from)) {
return consumedCapacity;
}
throw new IllegalArgumentException("Both from: " + from + " and to : " + to + " should be part of this edge.");
}

/**
* Adjusts/modifies the remaining capacity of that pipe/edge/channel.
* From from and to a determination is made if its a forward edge of backward edge.
* Depending on edge type the capacity is adjusted.
*
* @param from      the from/source node
* @param to        the to node.
* @return          the remaining capacity on determing if its a forward or reverse edge.
*/
public double adjustCapacity(T from, T  to, double consumedCapacity) {
if (consumedCapacity > getCapacity(from, to)) {
throw new IllegalArgumentException("The consumedCapacity " + consumedCapacity + " exceeds limit.");
}

if (this.from.equals(from) && this.to.equals(to)) {
this.consumedCapacity = this.consumedCapacity + consumedCapacity;
}

// indicates reverse flow.
if (this.from.equals(to) && this.to.equals(from)) {
this.consumedCapacity = this.consumedCapacity - consumedCapacity;
}

throw new IllegalArgumentException("Both from: " + from + " and to : " + to + " should be part of this edge.");
}
}

class GraphFordFuklerson<T> implements Iterable<T> {

/* A map from nodes in the graph to sets of outgoing edges.  Each
* set of edges is represented by a map from edges to doubles.
*/
private final Map<T, Map<T, DuplexEdge<T>>> graph;

public GraphFordFuklerson() {
graph = new HashMap<T, Map<T, DuplexEdge<T>>>();
}

/**
*  Adds a new node to the graph. If the node already exists then its a
*  no-op.
*
* @param node  Adds to a graph. If node is null then this is a no-op.
* @return      true if node is added, false otherwise.
*/
if (node == null) {
throw new NullPointerException("The input node cannot be null.");
}
if (graph.containsKey(node)) return false;

graph.put(node, new HashMap<T, DuplexEdge<T>>());
return true;
}

/**
* Given the source and destination node it would add an arc from source
* to destination node. If an arc already exists then the value would be
* updated the new value.
*
* @param source                    the source node.
* @param destination               the destination node.
* @param capacity                    if length if
* @throws NullPointerException     if source or destination is null.
* @throws NoSuchElementException   if either source of destination does not exists.
*/
public void addEdge (T source, T destination, double capacity) {
if (source == null || destination == null) {
throw new NullPointerException("Source and Destination, both should be non-null.");
}
if (!graph.containsKey(source) || !graph.containsKey(destination)) {
throw new NoSuchElementException("Source and Destination, both should be part of graph");
}
DuplexEdge<T> duplexEdge = new DuplexEdge<T>(source, destination, capacity, 0);

/* A node would always be added so no point returning true or false */
graph.get(source).put(destination, duplexEdge);
graph.get(destination).put(source, duplexEdge);
}

/**
* Removes an edge from the graph.
*
* @param source        If the source node.
* @param destination   If the destination node.
* @throws NullPointerException     if either source or destination specified is null
* @throws NoSuchElementException   if graph does not contain either source or destination
*/
public void removeEdge (T source, T destination) {
if (source == null || destination == null) {
throw new NullPointerException("Source and Destination, both should be non-null.");
}
if (!graph.containsKey(source) || !graph.containsKey(destination)) {
throw new NoSuchElementException("Source and Destination, both should be part of graph");
}
graph.get(source).remove(destination);
graph.get(destination).remove(source);
}

/**
* Given a node, returns the edges going outward that node,
* as an immutable map.
*
* @param node The node whose edges should be queried.
* @return An immutable view of the edges leaving that node.
* @throws NullPointerException   If input node is null.
* @throws NoSuchElementException If node is not in graph.
*/
public Map<T, DuplexEdge<T>> edgesFrom(T node) {
if (node == null) {
throw new NullPointerException("The node should not be null.");
}
Map<T, DuplexEdge<T>> edges = graph.get(node);
if (edges == null) {
throw new NoSuchElementException("Source node does not exist.");
}
return Collections.unmodifiableMap(edges);
}

/**
* Returns the iterator that travels the nodes of a graph.
*
* @return an iterator that travels the nodes of a graph.
*/
@Override public Iterator<T> iterator() {
return graph.keySet().iterator();
}
}

public final class FordFulkerson<T> {

private final GraphFordFuklerson<T> graph;

/**
* Takes in a graph, which should not be modified by client.
* However client should note that graph object is going to be changed by
* FordFulkerson algorithm.
*
* @param graph the input graph.
*/
public FordFulkerson (GraphFordFuklerson<T> graph) {
if (graph == null) {
throw new NullPointerException("The graph should not be null");
}
this.graph = graph;
}

private void validate(T source, T destination) {
if (source == null || destination == null) {
throw new NullPointerException("Neither source nor destination should be null");
}

if (source.equals(destination)) {
throw new IllegalArgumentException("The source should not be the same as destination.");
}
}

/**
* Determines the max flow based on ford-fulkerson algorithm.
*
*
* @param source            the source node.
* @param destination       the destination node
* @return                  the max-flow
*/
public double maxFlow(T source, T destination) {
validate(source, destination);
double max = 0;
List<T> nodes = getPath(source, destination);
while (nodes.size() > 0) {
double maxCapacity = maxCapacity(nodes);
max = max + maxCapacity;
drainCapacity(nodes, maxCapacity);
nodes = getPath(source, destination);
}
return max;
}

/**
* Gets the path from source node to destination node, such that there is
* capacity > 0 at each edge from source to destination.
*
* @param source        the source node
* @param destination   the destination node
* @return              the path from source to destination,
*/
private List<T> getPath(T source, T destination) {
synchronized (graph) {
depthFind(source, destination, path);
return new ArrayList<T>(path);
}
}

private boolean depthFind(T current, T destination, LinkedHashSet<T> path) {

if (current.equals(destination)) {
return true;
}

for (Entry<T, DuplexEdge<T>> entry : graph.edgesFrom(current).entrySet()) {
// if not cycle and if capacity exists.
if (!path.contains(entry.getKey()) && entry.getValue().getCapacity(current, entry.getKey()) > 0) {
// if end has been reached.
if (depthFind(entry.getKey(), destination, path)) {
return true;
}
}
}

path.remove(current);
return false;
}

/**
* Returns the maximum capacity in the path.
* Maximum capacity is the minimim capacity available on the path
* from source to destination
*
* @param nodes     the nodes that contibute a path
* @return          the max capacity on the path.
*/
private double maxCapacity(List<T> nodes) {
double maxCapacity = Double.MAX_VALUE;
for (int i = 0; i < nodes.size() - 1; i++) {
T source = nodes.get(i);
T destination = nodes.get(i + 1);

DuplexEdge<T> duplexEdge = graph.edgesFrom(source).get(destination);
double capacity = duplexEdge.getCapacity(source, destination);
if (maxCapacity > capacity) {
maxCapacity = capacity;
}
}
return maxCapacity;
}

/**
* Reduces the capacity along the path from source to destination
*
* @param nodes           the nodes that contribute the path
* @param maxCapacity     the maximum capacity along the path.
*/
private void drainCapacity (List<T> nodes, double maxCapacity) {
for (int i = 0; i < nodes.size() - 1; i++) {
T source = nodes.get(i);
T destination = nodes.get(i + 1);

DuplexEdge<T> duplexEdge = graph.edgesFrom(source).get(destination);
}
}

public static void main(String[] args) {

final GraphFordFuklerson<String> graph = new GraphFordFuklerson<String>();

FordFulkerson<String> ff = new FordFulkerson<String>(graph);
double value = ff.maxFlow("A", "H");
assertEquals(28.0, value, 0);
}
}


Some small remarks:

• I would change the NullPointerException to IllegalArgumentException when you check for null in the arguments of the method.
• I would add an addNodes(T ...) convenience method.
• addNode(T node) javadoc: "returns false if the node is not added". It only does so when the node is already in your Graph. Better to add that to the docs too.
• What is the use of the synchronized block in the getPath method?

I don't think your implementation is bad, but I would have done things differently, so here is my implementation. I did not have much time to do it, so it is completely untested and probably not complete.

I am using Java 8, Google guava and I tried to make things as immutable as possible. I also made a bit of code multi-threaded (look for stream().parallel()). The only class that is mutable is Flow and if I had more time, I would look at making it immutable too. (I would have to check if it would impact the performance when the flow values are modified since a new Flow would have to be created each time we change one value in the flow.)

The Java 8 bits might be a bit hard to understand if you have never seen Java 8. However, I think you can look at my "high-level" design (Node, Edge, Graph, Path and Flow) and maybe get some inspiration from that. For example, I did not put the "consumed capacity" in the Edge class, but outside in class Flow.

import com.google.common.collect.HashMultimap;

/**
* Finds the maximum flow in a directed graph with capacity.
* http://codereview.stackexchange.com/questions/45729
*/
public class FordFulkersonMaximumFlowFinder {

public static Flow fordFulkersonFindMaximumFlow(Graph graph) {
Collection<Path> paths = Path.findPathsDepthFirst(graph);
Flow flow = Flow.createZeroFlow(graph);
Optional<Path> onePathWithSlackCapacity;
while ((onePathWithSlackCapacity = findOnePathWithSlackCapacity(paths, flow)).isPresent()) {
// Note: there is some slight inefficiency here since it would be
// possible to compute
// the slack capacity amount while the check for slack capacity is
// done.
Stream<Edge> pathEdges = onePathWithSlackCapacity.get().getEdges().stream();
DoubleStream slackCapacitiesPerEdge = pathEdges.mapToDouble(edge -> (edge.getCapacity() - flow.getFlow(edge)));
double slackCapacity = slackCapacitiesPerEdge.min().getAsDouble();
flow.subtractFlow(pathEdges, slackCapacity);
}
return flow;
}

private static Optional<Path> findOnePathWithSlackCapacity(Collection<Path> paths, Flow flow) {
// Parallelize code when there are many paths.
Stream<Path> pathsStream = paths.size() < 2000 ? paths.stream() : paths.stream().parallel();
return pathsStream.filter(path -> doesPathHaveSlackCapacity(path, flow)).findFirst();
}

/**
* @return true if each and every edge has a capacity which is strictly
*         greater than the flow on that edge.
*/
private static boolean doesPathHaveSlackCapacity(Path path, Flow flow) {
// Note: this could be parallelize using stream().parallel(), but it
// would slow things down unless the
// paths are very long.
return path.getEdges().stream().allMatch(edge -> edge.getCapacity() > flow.getFlow(edge));
}

/**
* Immutable.
*/
public static class Node {
private final String name;

/**
* Immutable.
*/
public Node(String name) {
super();
this.name = name;
}

public String getName() {
return name;
}

@Override
public String toString() {
return "Node[" + name + "]";
}
}

/**
* Immutable.
*/
public static class Edge {
private final Node start;
private final Node end;
private final double capacity;

public Edge(Node start, double capacity, Node end) {
this.start = start;
this.capacity = capacity;
this.end = end;
}

public Node getStart() {
return start;
}

public Node getEnd() {
return end;
}

public double getCapacity() {
return capacity;
}
}

/**
* Immutable.
*/
public static class Graph {
private final Multimap<Node, Edge> edges;
private final Node startNode;
private final Node endNode;

public Graph(Node startNode, Node endNode, Collection<Edge> allEdges) {
// TODO should check no incoming edge on startNode, no outgoing edge
// on endNode and no cycles.
// Also, check that it is connected, from start to end.
this.startNode = startNode;
this.endNode = endNode;
edges = HashMultimap.create();
{
allEdges.stream().forEach(edge -> edges.put(edge.getStart(), edge));
}
}

public Node getStartNode() {
return startNode;
}

public Node getEndNode() {
return endNode;
}

public Set<Node> getAllNodes() {
return edges.keySet();
}

/**
* @return empty collection if the node does not exist in the graph.
*/
public Collection<Edge> getEdgesFrom(Node node) {
return edges.get(node);
}
}

/**
* Immutable.
*/
public static class Path {
public static final Path EMPTY = new Path(ImmutableList.of());
private ImmutableList<Edge> edges;

public Path(List<Edge> edges) {
this.edges = ImmutableList.copyOf(edges);
}

public ImmutableList<Edge> getEdges() {
return edges;
}

}

public static Collection<Path> findPathsDepthFirst(Graph graph) {
return findPathsDepthFirstRecursive(graph.getStartNode(), Path.EMPTY, graph);
}

public static Collection<Path> findPathsDepthFirstRecursive(Node currentNode, Path pathSoFar, Graph graph) {
if (currentNode.equals(graph.getEndNode()))
return Arrays.asList(pathSoFar);
if (pathSoFar.getEdges().stream().anyMatch(edge -> currentNode.equals(edge.getStart())))
throw new IllegalStateException("Holy Molly!  There's a cycle.");
Stream<Path> paths = graph.getEdgesFrom(currentNode).stream().flatMap(edge -> {
Node nextNode = edge.getEnd();
return findPathsDepthFirstRecursive(nextNode, nextPathSoFar, graph).stream();
});
return paths.collect(Collectors.toList());
}
}

/**
* Mutable.
*/
// TODO make immutable? Subtract would take a collection of edges and one
// value. Is Guava ImmutableMap efficient enough for creating new
// ImmutableMaps when subtracting?
public static class Flow {
private final Map<Edge, Double> edgeFlows = new HashMap<>();

private Flow() {
}

public static Flow createZeroFlow(Graph graph) {
Flow zeroFlow = new Flow();
{
graph.edges.values().stream().forEach(edge -> zeroFlow.edgeFlows.put(edge, 0.0));
}
return zeroFlow;
}

public double getFlow(Edge edge) {
return edgeFlows.get(edge);
}

public void setFlow(Edge edge, double flowValue) {
edgeFlows.put(edge, flowValue);
}

public void subtractFlow(Stream<Edge> pathEdges, double amountToSubtract) {
pathEdges.forEach(edge -> edgeFlows.put(edge, edgeFlows.get(edge) - amountToSubtract));
}
}
}