The Ford-Fulkerson Algorithm

The world is full of problems. Everything around us works to cause or solve some problems for us. Solving problems is a daily necessity. Of course, we deal with problems that directly relate to us. An issue like this is the flow problem inside a flow network, so how do we solve it? The answer is “The Ford-Fulkerson algorithm,” and finding out just how it works will be our goal today.

Before I venture any deeper into this, the first and most important question is: what problems will this  solve? What benefit will you get from reading and understanding this article? You will be amazed by how many real life problems will gain an optimal and good solution from this algorithm. However, for a prime example consider this.

Let there be a water network system. The question is, how big we should make the water pipes so that everyone can receive at any time a given amount of water? Add to this the caveat that we do not want to spend extra money on pipes that are larger than required. From this problem, it’s just one step to find out if the elimination of a given military headquarters in Vietnam poses a major threat to us.

To debate every single aspect of network flow algorithms (we are talking manly about the Ford-Fulkerson algorithm and how to use it for solving different issues), we will split the topic into two articles. In this one, the central objective will be to just understand the algorithm; how to adapt it to more complex problems is the topic for the next article.

Furthermore, you should know that this is part of a larger article series of mine about graphs and algorithms; in fact, this is the eleventh article in a thirteen-part series. I already covered topics such as the definition of a graph, how we store graphs in memory, and the breadth-first search. I will not explain these areas again, and you need to know them to understand this article. If you missed those articles, and are not otherwise familiar with these concepts, read the articles at the links shown above before continuing. 

What is a flow network then? It is a connected graph with weighted edges that are directed. Additionally, flow networks have a single source vertex (from which there are only outgoing edges) and a single terminal vertex (a drain vertex, which will have only incoming edges). This way we can perceive it as a network system from which the source vertex is pumping water into the network, and the terminal is collecting it and draining it out.

{mospagebreak title=The Theory}

To help you understand this better, I will need to further explain the terms we will use. We will name a road a sequence of vertexes (and as a sequence of edges also) that do not contain the same vertex twice. The edges still connect one after another. However, we will ignore their direction.

On this road, we can differentiate between two types of edges. There are edges that point in the same direction in which we would walk the network (so they point ahead), and edges indicating the opposite direction (therefore pointing backward).

A road like this is called saturated if all of the forward-pointing edges along it have a capacity (weight of the edge), and the flow currently going through them is equal, and if the backward-pointing edges have a current flow greater than 0.

An improving road is one through which all of the edges are yet not saturated. Therefore, we can increase the overall flow of the network through this road while we also increase the same trait of the edges, and if we make the right amount of improvement, a single edge at least will be saturated.

Of course, while we make the improvement we need to decrease the current flow on the backward- pointing edges and increase it on the forward-pointing ones. What is the maximum amount by which we can increase this? Forward-pointing edges we can improve, at most, by the capacity of the edge minus the current flow, while backwards-pointing edges can be improved by the amount we can decrease that edge.

The final answer to our question will be the minimum of these maximum values. The fact that we can increase it by this amount is guaranteed by the fact that we can increase the amount coming out from the source by any value, and the rest will be at most saturated after we make the improvement.

How will the backward-pointing edges put their own share to increasing the overall flow that we can pump into a network? The answer lies in the observation that when the least comes back, the most will go ahead. Consider that the edge between u and v is backward-pointing. Think of it as if, at vertex u, the amount just vanishes and appears at vertex v.

In reality, of course this amount will have to make its road through the outgoing edges of the u vertex. Eventually, they will reach vertex v by the incoming edges of that node. 

Now we can state the Ford-Fulkerson algorithm. We start with a flow through all of its edges; the current flow value is zero. While we can find any improved road from the source vertex to the terminal node, repeat the following steps. Search for the improved road.

You will determine the maximum value by which we can improve on it. Make the enhancement. The maximum flow value that can handle the network is the sum of all the improvements.

{mospagebreak title=Implementation issues}

While the algorithm presented on the previous page will indeed provide a correct answer, the order in which we take the improved roads to perfect our solution matters. The difference is in execution time and the number of steps required to solve it.

According to the Edmon-Karps Theorem, if at every step we make the enhancement through the roads that contain the minimum number of roads, the Ford-Fulkerson Algorithm will have its solution in a polynomial time. For the proof of this, look up the Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein book titled Introduction to Algorithms.

Therefore, we will store the data in two ways before we let the algorithm start. We will use a neighbor list with the modification that we will ignore the direction of the edges, and have another item showing us the sum of the incoming and outgoing edges to a specific vertex.

The second structure is a neighbor matrix where, at position u and v (representing in practice the edge from u to v), we will store first the current flow of the edge, and the capacity of the edge. While the capacity of the edge will be the read-in data if we have it, one, and otherwise minus one, the current flow value is, for all of them, zero.

We will do the minimum road search with a modified version of the breadth first search. The search will use the neighbor list that eliminates the direction of the edges; however, we will only consider edges that are not yet saturated. This assures us that we can make the enhancement through the found road.

To get the amount by which it can improve through an edge, the search will use the neighbor matrix. Inside of this we can deduce if the edge from u to v is incoming or outgoing. If a forward-pointing exists and it still has not reached its capacity, we can travel ahead on it.

The other valid option is that there exists an incoming edge. Moreover, this has a flow value greater than zero. If there exist both types, first consider the outgoing edges, and after that, the incoming ones. If we find an edge that is valid, we save its parent. The search will start out from the source and will end up in the terminal node. Now we can start a little recursion on this array to find and make the improvement at once.

While we go deeper on the recursion, we can calculate the maximum value for each vertex. Pick out of them the minimal value. On the back-pointing branch of the recursion, make the improvement as well. To the forward-pointing edges we will add it, and from the backward-indicating ones, subtract it. An example of improvement for the graph:

The first step is:

If the minimal value found with this approach is zero, there are no more roads that can provide improvement, and the Ford- Fulkerson Algorithm is finished. Add up all the values with which we enhanced our network, and the overall flow value is also given.

{mospagebreak title=The C Code}

The complexity of the algorithm, if you follow the guide presented on the previous page, is O (m^2*n), where m is the number of edges and n the number of vertexes. The solution of the algorithm, a little rephrased, sounds like this. The maximum flow value throughout a network is equal to the capacity of the minimum cut through the graph.

This was the original statement when the algorithm was first published about how to determine the maximum flow value through a network. Take a moment to think about why this is true.

Once you get it, you can view the code snippet below, implementing this in very C-styled code with just a little help from C++, considering the references. You will need all that we’ve learned about breadth-first search to fully comprehend it; that is why I said you need to know it in order to understand this article.

int Ford_Fulkelson(Vertex**& neighborMatrix, Node*& list,

int source, int terminal, const int& n)

{

int flowOverall =0 ;

int min = 0;

 

do

{

min = INFINITY;

searchAugmentation(neighborMatrix, list, source,terminal,min,n);

flowOverall += min;

}while(min);

 

return flowOverall;

}

 

void searchAugmentation( Vertex**& neighborMatrix,

Node*& list, int source, int terminal, int& min, const int& n)

{

int* ancient;

int* color;

pListIt Q;

ancient = (int*) malloc ((n+1)*sizeof(int));

color = (int*) malloc ((n+1)*sizeof(int));

 

memset(ancient, 0, (n+1)*sizeof(int) );

memset(color , WHITE , (n+1)*sizeof(int) );

 

color[source] = GRAY;

ancient[source] = 0;

 

Q = NULL;

 

// put source into the queue

Q = (pListIt) malloc ( sizeof( ListIt));

Q->value = source;

Q->p_next = NULL;

 

int u = 0, v = 0;

pListIt at;

pListIt endQSe;

 

while(Q)

{

u = Q->value;

 

for( at = list[u].neighbors; at; at = at->p_next)

{

v = at->value;

if (color[v] == WHITE)

{

if (neighborMatrix[u][v].capacity != -1 && neighborMatrix[u][v].flowValue <

neighborMatrix[u][v].capicity)

{

color[v] = GRAY;

ancient[v] = u;

 

if (v == terminal)

{

improvement(neighborMatrix, terminal,ancient, min);

return; // stop the search as we found it

free(ancient);

free(color);

}

 

// find the end of Q

for(endQSe = Q; endQSe->p_next;endQSe = endQSe->p_next);

 

// put v into the queue

endQSe->p_next = (pListIt) malloc ( sizeof( ListIt));

endQSe->p_next->value = v;

endQSe->p_next->p_next = NULL;

}

else

{

if (neighborMatrix[v][u].capacity != -1 && neighborMatrix[v][u].flowValue > 0)

{

color[v] = GRAY;

ancient[v] = -u;

if (v ==terminal)

{

improvement(neighborMatrix, terminal,ancient,min);

free(ancient);

free(color);

return;

}

// find the end of Q

for(endQSe = Q; endQSe->p_next;endQSe = endQSe->p_next);

 

// put v into the queue

endQSe->p_next = (pListIt) malloc ( sizeof( ListIt));

endQSe->p_next->value = v;

endQSe->p_next->p_next = NULL;

}

}

}

}

 

//delete first item -> we visited all of its neighbors

 

endQSe = Q;

Q = Q->p_next;

free(endQSe);

 

color[u] = BLACK; // paint it black

}

 

min = 0; // no improvement found, clean and return

free(ancient);

free(color);

}

 

void improvement(Vertex**& adiacentMatrix, int currentVertex, int*& ancient, int& minimal )

{

int vertexAt = 0;

 

if (ancient[currentVertex] < 0)

{

vertexAt = -ancient[currentVertex];

 

if (minimal > adiacentMatrix[currentVertex][vertexAt].flowValue)

{

minimal = adiacentMatrix[currentVertex][vertexAt].flowValue;

}

 

improvement(adiacentMatrix, vertexAt, ancient, minimal);

adiacentMatrix[currentVertex][vertexAt].flowValue -= minimal;

}

else

{

if (ancient[currentVertex] > 0 )

{

vertexAt = ancient[currentVertex];

 

if (minimal > (adiacentMatrix[vertexAt][currentVertex].capacity – adiacentMatrix[vertexAt][currentVertex].flowValue ))

{

minimal = adiacentMatrix[vertexAt][currentVertex].capacity – adiacentMatrix[vertexAt][currentVertex].flowValue;

}

 

improvement(adiacentMatrix, vertexAt, ancient, minimal);

 

adiacentMatrix[vertexAt][currentVertex].flowValue += minimal;

}

}

}

Here is the source code in a CPP, extending the upper snippets so that they will run and calculate the result if you give a correct input. Feel free to download and play around with it. It is heavily commented; coupled with this article, you should have no problem understanding it.  

–>Ford-Fulkerson algorithm.zip<–

Moreover, here is a little teaser for you. For the graph present on the previous page, the output looks like this:

-Negative: 1 5 7 12 —-> with 15

-Negative: 1 5 7 6 12 —-> with 9

-Negative: 1 5 4 8 9 12 —-> with 2

-Negative: 1 2 3 4 8 9 12 —-> with 7

-Negative: 1 2 3 4 8 9 10 11 12 —-> with 1

-Negative: 1 2 3 4 5 7 8 9 10 11 12 —-> with 1

Maximal flow is : 35

This will be all for today. Make sure you tune in next time, when we are going to find out how we can reuse what we just learned to solve a couple of complex problems that we can connect easily to real life issues.

Whether you liked this article or just hate it absolutely, please take the effort to rate it. You are welcome to ask any question you might have, as for this there exists two distinct places. First, the article’s blog, which follows the article itself, and the second option is to join our friendly ever-growing forum running under the name DevHardware and ask our community of experts. Until next week, Live With Passion!

[gp-comments width="770" linklove="off" ]