I'm trying to implement the Ford Fulkerson algorithm in Java. So far I have a graph with Nodes and Edges. The nodes contains an ID string and an adjacencyList of edges. The edges contain the capacity and the node it leads to.
I'm trying to understand the psudo code on the Wikipedia page and how to implement it (I'm using Java). This is what I understand so far:
First I set the flow of all edges in the graph to zero.(What is a good way to represent flow? Directly in the edges of my graph as a variable?)
The second step is to create the residual graph which is a network where the edges have the residual capacity: capacity - flow (of the corresponding edges in the "normal graph"). Then you find a path from the source to the sink using this residual graph and find the minimal capacity along this path. (This is where stuff gets really tricky, should I create an entirely new graph for the residual graph or should I represent it somehow in the original graph? What is the best way?)
Step 2 is repeated until no path can be found but every time it is found you do step 3 and 4:
For each edge along the path you add the minimal value found in step 2.
For each edge in the opposite direction of the path you subtract the minimal value found in step 2.
Step 3 and 4 puzzles me since I feel like it is the same thing to add in one direction as it is to substracting in the opposite. These additions and substractions are made in the graph right, not the residual graph?
Would really appreciate some help, I have been trying to wrap my head around this for a couple of hours now but I just can't seem to understand it.
You should probably implement this first with a dense graph. That way, you can assume there's an edge in each direction between every pair of distinct vertices. You can represent functions on the edges as |V| x |V| matrices. In particular, declarations for capacity and flow are quite simple:
int[][] cap = new int[numverts][numverts];
int[][] flow = new int[numverts][numverts];
One useful trick is to represent a flow of k units along edge vw as a flow of a from v to w and a flow of -a from w to v. This way, you don't have to worry about whether each edge of your augmenting path is pushing more flow forward or less flow backward. If you do this, you can compute the residual capacity along vw by simply cap[v][w] - flow[v][w].
With this representation, finding an augmenting path becomes a breadth-first search in a dense graph where there is an edge from v to w exactly when cap[v][w] > flow[v][w]. This is fairly straightforwardly implemented.
Since you're using java, you should be mindful of its per-object overhead. The Edge structure you described contains not just two ints (or pointers) and two doubles, but also stuff like GC information, a klass pointer, and a monitor. This is a few dozen extra bytes, easily doubling or tripling the size of your object.
A better representation for static sparse graphs, when you get to making your code work with sparse graphs, is as follows:
int[] from = new int[numverts+1];
int[] to = new int[numedges];
Sort the edges by "from" vertex. The ith entry of the from array is the index of the first edge whose "from" vertex is the ith vertex or later. There's one extra entry at the end and you should set it to numedges; it comes in handy when you want to loop over all edges leaving a given vertex.
Since you're doing flow, you'll want to store backward edges as well, so have an
int[] rev = new int[numedges];
to store the edge index of the reverse of each edge. Now you can represent arbitrary functions, say cap and flow, on the edges like this:
int[] cap = new int[numedges];
int[] flow = new int[numedges];
So whether to store these attributes in the Edge structure is moot because the Edge structure has gone away.