Connectivity in Graphs

Think outside the box. This is the motto for today. Today, using graphs, we will find out how much of a threat just the elimination of a military base poses to us. For a precise calculation of this, we will use the Ford-Fulkerson algorithm and modify it for our needs by using the motto of the day. This article is the twelfth part of a thirteen-part series that shows how to use graphs and algorithms to solve everyday problems.

Did I just mention the Ford-Fulkerson algorithm? If you arrived here to learn that, you are just a little late. In the previous article, I presented everything you should know about the algorithm itself.

In case you missed it, you absolutely have to dig it up and become familiar with the algorithm if you wish to understand this article. I mean that seriously; do not read on if you do not know the algorithm.

Take a break and come back later once you comprehend it. You are in danger of not understanding a word of mine if you ignore this.

Now that we have that straight, you can begin to see how we’ll use the lesson from the previous article. First, I am going to present how to bypass small obstacles, such as if we have many sources or many terminals, or what if the node itself has a given capacity?

I will follow up this presentation closely with the idea of solving the issue of k connectivity (related to edges) or k vertex connectivity, and illustrate this lesson with the scenario I alluded to in the introduction. 

{mospagebreak title=Back to the Basics}

When we work with flow networks, sometimes the requirements for the Ford-Fulkerson algorithm are simply not satisfied. To work with the algorithm, we need a single source and a single terminal. The vertexes are just connection points, and they cannot have capacities. Also, remember that we used directed edges.

However, if we make a little modification to our input graph, we can transform it into graphs that have all the upper traits. We can get rid of the issue with multiple sources and multiple drains if we add a new source and connect all the current sources to it. The capacity of the edges connected from the new point to the sources is infinity.

You can apply the same rule to the terminals also, but the direction of the edges is from the terminals to the new point. This way, we will have a single source and a single terminal. Run the algorithm on this graph and it will solve the problem for the multiple sources/terminals graph at the same time. Here is a picture to illustrate it:

 

Once we have a graph with edges that are not directed, the problem is easily solved by adding directed edges in both direction. However, once the equation includes nodes with capacity, this gets a little more complicated. Obviously we cannot call the algorithm with this input data, so we will first transform our graph into something that maintains the traits enumerated at the start of this page.

Consider that we have a graph with n vertexes. If every vertex has a capacity of c (v), all we need to do is extract the node out of an edge. To achieve this, add a new node to the graph. Connect an edge from the vertex in context to the newly-added one and let the capacity be equal to c (v).

It is a good idea to name the new vertex n+i, where “i” is the number of the node we just tried to extract. All of the incoming edges will maintain their connection to node I, while the outgoing edges will come from, instead of node “i,” vertex n+i. Here is a picture that shows how to handle this example, to make everything clear:

Apply this to all the edges and you are done. Now we will look into connectivity of the graphs and the war in Vietnam. For this, we will use what we just figured out on this page.

{mospagebreak title=K Connectivity}

There are two types of connectivity in graphs, connectivity of the edges and connectivity of the vertexes. Whenever we talk about connectivity, we first refer to it as of the edges. When we want to talk about vertexes, we need to talk about K Vertex Connectivity. What is covered under this name?

Connectivity refers to the fact that there exists a road between any two nodes. K Connectivity says that, if we eliminate any number less than k of that type of component (any one) from the graph, we will still get a connected graph. Of course, if we eliminate vertexes we also delete the edges related to them.

So how does this tie in with a war in Vietnam? Let there be n military bases. Each one of them can communicate with a specific number of other bases. The connections build up a graph with directed edges inside it. The connections can be mutual; if this is the case, we can just add an edge in both directions.

The information arrives at headquarters that the enemy has eliminated k military bases. The question is, can we remain calm, considering the way that our bases can connect with the other remaining bases? This is node connectivity. We can imagine a case when the edges are relevant. For instance, we talk about roads, and if k instances of them got bombed, could we still reach all the cities?

From the definition you can already see that the connectivity of nodes is a much more serious trait than of vertexes, and we will see immediately why this is true. From the definition of connectivity, we can sense that we are talking about individual roads. In order for us to still be able to reach a point when an edge or vertex is eliminated, we must have an alternative road we can use to get there. 

Connectivity in fact hides the number of individual roads between a point and all the rest inside the graph. In the case of edge connectivity we are talking about different edges, while in the case of node connectivity, the vertexes through which the road passes have to be different.

So the source will be the vertex itself, which we are observing, while the terminal handles all the ends. The algorithm is simple. Consider the graph and iterate through every different vertex pair. Let every edge have a capacity of one. Call the Ford-Fulkerson algorithm for each pair to calculate the number of different (alternative) roads.

If the capacity is the maximum flow that can travel through, the graph will be just like this. All that we have to do is to pick the smallest number from this, and that will tell us how many edges we can delete and still be able to contact any military base. Note that we can pick for removal any one of the edges, not just a collection of them, as long as we choose k number of them.

Here it is all this implemented in C code. We need to reset the current flow number to zero before each call.

int kConnectedEdge(Vertex**& neighborMatrix, Node*& list, const int& n)

{

 

int i = 0, j = 0, curKCon = 0;

int k = INFINITY;

 

for( i=1; i <= n-1; ++i)

for( j=i+1; j<= n; ++j)

{

int a =0, b = 0;

 

for (a = 1; a <= n; ++a)

for (b = 1; b <= n ; ++b)

{

neighborMatrix[a][b].flowValue = 0;

}

 

curKCon = Ford_Fulkelson(neighborMatrix, list, i , j, n);

 

if (curKCon < k)

{

k = curKCon;

}

}

 

return k;

}

Here is an example graph:

With our algorithm, all this will look as follows, as we need to double every edge and add the direction to them:

 

The result in the output file is correct:

The input graphs edge connectivity is 3

 {mospagebreak title=The k Node Connectivity} 

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! 
[gp-comments width="770" linklove="off" ]