Bipartite Graphs - The Solution
(Page 4 of 4 )
With this, we've made the distinction. For the final solution we will use the Ford-Fulkerson algorithm. The basic setup is simple. Consider that we needed to find out the maximum flow that can go through the network from set A to set B. We will make the edges directed, and all of them will come from the points of set A to set B.
Each vertex from set A will behave as a source node, while the vertexes from set b will be terminal nodes. We will remove the issue of multiple vertexes and multiple terminals by adding another virtual source (n+1) and a terminal (n+2). This virtual sources and terminals will be connected to all of the sources from set A, and respectively the terminals from set B. The capacity of the edges is one. What we get is something like this:
Image Courtesy of Grapy Theory Algorithms, Kátai Zoltán
Now we will call the Ford-Fulkerson algorithm to calculate for us the maximum amount of flow that the network can handle, and we are done. The improved roads that the algorithm uses, or more obviously stated, the individual alternative routes from the virtual source to the virtual terminal, will also say which one of these connections are advisable to use. Here it is translated into C code, given that you already saw the Ford-Fulkerson algorithm in my previous article:
int main()
{
//create the variables
Vertex** neigMatrix;
int n;
Node* list;
// Pairing in graphs
read2(neigMatrix, n , list);
print(neigMatrix, n, list);
int* color = ( int*) calloc ( n+1, sizeof(int));
int result = 0;
result = colorize(list,1, color, n);
printf("n The colored array: ");
// Now we will build from this a flow problem
for (int i =1 ; i <= n; ++i)
{
printf( " %d ", color[i]);
for ( int j = 1; j <= n; ++j)
neigMatrix[i][j].capacity = neigMatrix[i][j].flowValue =0;
}
// all point from left to right in the already existing system
pListIt at;
for (int i =1 ; i <= n; ++i)
{
at = list[i].neighbors;
if(color[i] == 1)
while (at)
{
neigMatrix[i][at->value].capacity = 1 ;
at = at->p_next;
}
}
// now add the source and the drain
// n+1 source
// n+2 drain
for (int i = 1; i <= n; ++i)
{
if (color[i] == 1 ) //connect the source to this
{
neigMatrix[n+1][i].capacity = 1;
if(add(list[i].neighbors, n+1))
list[i].vertexNr++; // count incoming edges if(add(list[n+1].neighbors, i))
list[n+1].vertexNr++; // count outgoing edges
}
else //connect this to the drain
{
neigMatrix[i][n+2].capacity = 1;
if(add(list[n+2].neighbors, i))
list[n+2].vertexNr++; // count incoming edges if(add(list[i].neighbors, n+2))
list[i].vertexNr++; // count outgoing edges
}
}
// now call on this the function
printf( "n Maximal parity: %dn", Ford_Fulkerson(neigMatrix, list, n+1, n+2, n+2 ));
return 0;
}
Given that you also defined the verbose variable, which tells the Ford-Fulkerson Algorithm to print the improved roads, the output for the upper graph should look like this (eliminate the virtual source and virtual terminal vertexes and you have the solutions):
The colored array: 1 2 1 2 1 2 1 1 2
-Negative: 10 1 2 11 ----> with 1
-Negative: 10 3 6 11 ----> with 1
-Negative: 10 5 4 11 ----> with 1
Maximal parity: 3
In this scenario we considered everyone to be equal, and to provide the same productivity; however, if this is not true, all you need to modify the graph is to add the respective capacity to that edge before you call the Ford-Fulkerson algorithm. In this case, the number of improvements will tell the number of pairings. In this way, the Ford-Fulkerson algorithm will tell the company's maximum productivity.
For those of you who still do not fully understand all of the traits of this problem, below you'll see a downloadable file with the full code for this implementation in C, with just a little extra C++ flourish via the references. Before I give you this, I should mention that there exists an alternative solution, called the Hungarian method, that solves the problem in O(n*(n+m)).
->Bipartite Graphs.zip<-
Thank you for reading through my article. I hope you found it to be worth the time you spent with it, and that you are willing to make the extra effort to rate it as well. With this, my article series related to graphs is rapidly reaching its end; as a bonus, I will later be covering the Euler and Hamilton graphs. Regardless, any kind of question you may have, you can ask it any time here on the blog or over at the friendly community under the name of DevHardware. 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. |
