Connectivity in Graphs - The k Node Connectivity
(Page 4 of 4 )
When we talk about edge connectivity, we can no longer pass through the same vertex in the roads. We search for roads between two points that are built from a very different node sequence. Therefore, we cannot allow more than one road to pass through a vertex. This sounds like a vertex that has one capacity, and indeed, this is what it is.
Everything remains the same, but now we add a capacity of one to the vertexes. In the next step, we extract each node's vertex capacity to edge capacity, as explained in the previous pages. We need to make the same iteration only on the basic edge pairs, as those newly-introduced through the extraction are irrelevant.
With this method we will transform our graph with n vertexes and m edges to one with 2 * n nodes and 2*m + n edges. To travel only through the different vertex pairs, we will only take the points above the main diagonal in the neighbor matrix. Here "i" is always smaller than j, so we will start our second iteration from "i" + 1. Look at the code snippet.
void extractByPointGraph( Vertex**& neighborMatrix , int&n,Vertex**& toNeighborMatrix , Node*& toList )
{
int i =0;
int j =0;
// First allocate space for the items
toNeighborMatrix = (Vertex**) calloc(2*n+1, sizeof(Vertex*));
for( i = 1; i <= 2*n; ++i)
{
toNeighborMatrix[i] = (Vertex*) calloc(2*n+1, sizeof(Vertex));
}
for( i =1; i <= 2*n; ++i)
for( j =1; j <= 2*n; ++j)
toNeighborMatrix[i][j].capacity = -1;
toList = (Node*) calloc(2*n+1, sizeof(Node));
// fill the matrix and the list
for (i = 1; i <= n ; ++i) // divide
{
toNeighborMatrix[i][n+i].capacity = 1;
if( add(toList[n+i].neighbors, i ) )
{
++toList[n+i].vertexNr;
}
if( add(toList[i].neighbors, n+i ) )
{
++toList[i].vertexNr;
}
}
for (i = 1; i <= n ; ++i) // reconnect edges
for (j = 1; j <= n; ++j)
{
if (neighborMatrix[i][j].capacity != -1)
{
toNeighborMatrix[n+i][j].capacity = 1;
if( add(toList[n+i].neighbors, j ) )
{
++toList[n+i].vertexNr;
}
if( add(toList[j].neighbors, n+i ) )
{
++toList[j].vertexNr;
}
}
}
}
int kConnectedVertex( Vertex**& neighborMatrix , int&n )
{
Vertex** extendedNeighborMatrix = NULL;
Node* extendedList = NULL;
extractByPointGraph(neighborMatrix, n,extendedNeighborMatrix, extendedList);
int k = INFINITY, curKCon = 0;
int i= 0, j = 0;
for( i=1; i <= n-1; ++i)
for( j=i+1; j<= n; ++j)
{
int a =0, b = 0;
for (a = 1; a <= 2*n; ++a)
for (b = 1; b <= 2*n ; ++b)
{
extendedNeighborMatrix[a][b].flowValue = 0;
}
extendedNeighborMatrix[i][n+i].capacity = INFINITY;
curKCon = Ford_Fulkelson(extendedNeighborMatrix, extendedList, i , j, 2*n);
extendedNeighborMatrix[i][n+i].capacity = 1;
if (curKCon < k)
{
k = curKCon;
}
}
return k;
}
What remains is to mention is that, before we call the Ford-Fulkerson algorithm, we need to set the capacity of the current node to infinity. Otherwise, we could only take a single road to the vertex we introduced for the capacity extraction. However, the two nodes are the same, so between them countless roads can be possible.
The graph looks quite intriguing once we make the extraction:
Still the answer given by our algorithm is flawless:
The input graphs node connectivity is 1
The complexity of this algorithm, because of the many embedded loops, is quite high; it's O( n^3 * m^2). Still, the problem is solved in polynomial time. For the proof, you can search up the book Introduction to Algorithms from Cormen, Leiserson, and Rivest, as mentioned in the previous article.
Thank you for patience and for reading this article until the end. Please take the effort to rate it. Post your questions on the blog, or even better, join the
DevHardware community and ask your questions of our experts. Look for other articles related to the field of graphs, as we are coming to the end of this series. Until we meet again,
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. |
