Ford-Fulkerson Algorithm Max flow algorithm - What is wrong with this Java implementation?
Question: I am trying to implement a java version of Ford-Fulkerson. I used the python
implementation from
[wikipedia](https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm#Python_implementation)
as a basis:

    
    
    class Edge(object):
        def __init__(self, u, v, w):
            self.source = u
            self.sink = v  
            self.capacity = w
        def __repr__(self):
            return "%s->%s:%s" % (self.source, self.sink, self.capacity)
    
    class FlowNetwork(object):
        def __init__(self):
            self.adj = {}
            self.flow = {}
    
        def add_vertex(self, vertex):
            self.adj[vertex] = []
    
        def get_edges(self, v):
            return self.adj[v]
    
        def add_edge(self, u, v, w=0):
            if u == v:
                raise ValueError("u == v")
            edge = Edge(u,v,w)
            redge = Edge(v,u,0)
            edge.redge = redge
            redge.redge = edge
            self.adj[u].append(edge)
            self.adj[v].append(redge)
            self.flow[edge] = 0
            self.flow[redge] = 0
    
        def find_path(self, source, sink, path):
            if source == sink:
                return path
            for edge in self.get_edges(source):
                residual = edge.capacity - self.flow[edge]
                if residual > 0 and edge not in path:
                    result = self.find_path( edge.sink, sink, path + [edge]) 
                    if result != None:
                        return result
    
        def max_flow(self, source, sink):
            path = self.find_path(source, sink, [])
            while path != None:
                residuals = [edge.capacity - self.flow[edge] for edge in path]
                flow = min(residuals)
                for edge in path:
                    self.flow[edge] += flow
                    self.flow[edge.redge] -= flow
                path = self.find_path(source, sink, [])
            return sum(self.flow[edge] for edge in self.get_edges(source))
    

This is my java implementation:

    
    
    import org.junit.Test;
    
    import java.util.*;
    
    import static org.hamcrest.CoreMatchers.is;
    import static org.hamcrest.MatcherAssert.assertThat;
    
    public class MaxFlowTest {
    
        @Test
        public void maxFlowTest() {
            FlowNetwork unit = new FlowNetwork(Arrays.asList(0, 1, 2, 3, 4, 5));
    
            unit.addEdge(0, 1, 16);
            unit.addEdge(0, 2, 13);
            unit.addEdge(1, 3, 12);
            unit.addEdge(1, 2, 10);
            unit.addEdge(2, 1, 4);
            unit.addEdge(2, 4, 14);
            unit.addEdge(3, 2, 9);
            unit.addEdge(4, 3, 7);
            unit.addEdge(3, 5, 20);
            unit.addEdge(4, 5, 4);
    
            assertThat(unit.maxFlow(0, 5), is(23)); //algorithm incorrectly returning 7
        }
    }
    
    class FlowNetwork {
        Map<Integer, List<Edge>> edges = new HashMap<>();
        Map<Edge, Integer> flow = new HashMap<>();
    
        public FlowNetwork(List<Integer> vertices) {
            vertices.forEach(v -> this.edges.put(v, new ArrayList<>()));
        }
    
        public Integer maxFlow(Integer source, Integer sink) {
            List<Edge> path = null;
            while (! (path=findAugmentedPath(source,sink,new ArrayList<>())).isEmpty()) {
                int flow = path.stream().mapToInt(e -> e.capacity - this.flow.get(e)).min().getAsInt();
                path.forEach(e -> {
                    this.flow.put(e, this.flow.get(e) + flow);
                    this.flow.put(e.reverseEdge, this.flow.get(e.reverseEdge) - flow);
                });
            }
            return edges.get(source).stream().mapToInt(e -> flow.get(e)).sum();
    
        }
    
        List<Edge> findAugmentedPath(Integer source, Integer sink, List<Edge> pathSoFar) {
            if (source == sink) {
                return pathSoFar;
            }
            for (Edge neighbourEdge : this.edges.get(source)) {
                int residual = neighbourEdge.capacity - flow.get(neighbourEdge);
                if (residual > 0 && !pathSoFar.contains(neighbourEdge)) {
                    pathSoFar.add(neighbourEdge);
                    List<Edge> path = findAugmentedPath(neighbourEdge.b, sink, pathSoFar);
                    if (!path.isEmpty()) {
                        return path;
                    }
                }
            }
            return Collections.emptyList();
        }
    
    
        public void addEdge(int source, int sink, int capacity) {
            Edge edge = new Edge(source, sink, capacity);
            Edge reverseEdge = new Edge(sink, source, 0);
    
            edge.reverseEdge = reverseEdge;
    
            reverseEdge.reverseEdge = edge;
    
            this.edges.get(source).add(edge);
            this.edges.get(sink).add(reverseEdge);
    
            flow.put(edge, 0);
            flow.put(reverseEdge, 0);
        }
    }
    
    
    class Edge {
    
        Integer capacity;
        Edge reverseEdge;
        int b;
        int a;
    
        public Edge(Integer a, Integer b, Integer capacity) {
            this.a = a;
            this.b = b;
            this.capacity = capacity;
        }
    }
    

The problem is the java algorithm is outputting 7, instead the correct 23 for
the example given in the test case. There are no errors when the code runs.
When debugging the algorithm I can't see any misbehavior. I am not sure how it
is going wrong.

My question is, can anyone help me understand how and why it is going wrong?

If it helps a visual representation of the example graph is available in this
pdf: <http://web.stanford.edu/class/cs97si/08-network-flow-problems.pdf>


Answer: I found the problem...I wasn't creating a copy of pathSoFar when calling
findAugmentedPath. Whoops!

    
    
    List<Edge> findAugmentedPath(Integer source, Integer sink, List<Edge> pathSoFar) {
        if (source == sink) {
            return pathSoFar;
        }
        for (Edge neighbourEdge : this.edges.get(source)) {
            int residual = neighbourEdge.capacity - flow.get(neighbourEdge);
            if (residual > 0 && !pathSoFar.contains(neighbourEdge)) {
                List<Edge> pathSoFarCopy = new ArrayList<>(pathSoFar);
                pathSoFarCopy.add(neighbourEdge);
                List<Edge> path = findAugmentedPath(neighbourEdge.b, sink, pathSoFarCopy);
                if (!path.isEmpty()) {
                    return path;
                }
            }
        }
        return Collections.emptyList();
    }
    

