The Ford-Fulkerson Algorithm - The C Code
(Page 4 of 4 )
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!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
