Search and you will find. At least this is what everybody says whenever you are lost and you do not know what to do. This is as true in life as it is in graph theory. Today we're going to search for some answers concerning strong connectivity and circles inside graphs. When all is said and done, we'll find another way to use graphs to solve some complex algorithm-related problems. This is the fifth part of a multi-part series.
Contributed by Gabor Bernat Rating: / 3 May 19, 2009
Some wise mathematicians once embarked on a search to resolve certain problems and ultimately found the solution. This article is part of a series I am writing about these graphs, presenting various ways to use them and certain algorithms. This is a continuation of the article I wrote on the depth-first search algorithm.
I will try to explain how we can reuse searches to solve complex problems. If you missed the previous part I strongly recommend that you read it, as it contains information that will be necessary for you to comprehend this article. We have much ground to cover, so let us begun.
I already defined connectivity inside a graph during the introductory article to this saga entitled “An Insight into Graphs.” Connectivity can be illustrated in a graph which contains no directed edges; between any two vertexes, there exists a road. If a graph is not in the described state, we can talk about the components of it (sub graphs) that will satisfy this criteria.
Strong connectivity means the same as ordinary connectivity, but we translate everything to a graph with directed edges. If you read the previous article, it is easy to deduce that calculating the number of connected components in a graph is the same as counting the number of times we call the DFS search.
Every call will inform us of another connective sub-graph. However, when we go to graphs with directed edges, the problem becomes a little more complicated. Before we take a closer look at this difficulty, we first need to learn how to find the base circle system inside a graph.
By now you should have realized that determining whether a graph is inside a circle involves nothing more than simple search for the first backward-pointing edge. If at least one of these exists, you have a circle, as you have an edge to a point that is currently in the visited stack, while you came down to the current vertex on another path. You may use this edge to travel back, and you've formed a circle.
The Base circle system is composed of those circles that are not redundant and cannot be built with the combination of an arbitrary number of the base circle system. Imagine an equation system in mathematics. In high school, they already teach you that it that there are systems where one line -- for example, an equation -- may not tell you more than the other lines.
A simple example:
X + Y=0
2X+ 2Y =0
If we divide the second equation by two, we will get the first equation, so the second equation tells us nothing more than the first; in fact, it is just a different rendition of the first one.
When we take a walk inside a graph, the edges will represent the X and Y and so on, and when we finish the walk, we will get an equation to complete the analogy. Therefore, the basic circle system is composed only of those equations that cannot be built from mixing any of the other basic circles.
Finding this is quite simple. All we need to do is store the ancient of each vertex, and when we find a back-pointing edge, call an iteration on the ancient array coming down to the current vertex from the node to which our edge points. So add the following lines after the application determines that an edge is backward-pointing during the DFS we wrote in the last article.
isCircle = true;
// print the circle
printf(" n Circle: ");
int l = vertex;
while(l != p->value)
{
printf( " %d ", l);
l = ancient[l];
}
printf( " %d ", l);
We will extend the code from the DFS with this addition and run the program for the tree we used as an example in the Depth-First Search article (or the one you will find on the next page). Here is the result that will appear in the output file for the example on the previous page:
Here is the solution: build the inverse order of the DFS search for the vertexes. Make an inverse of the direction (by reversing the direction of the edges). Call the DFS on the vertexes in the inverse DFS order of the vertexes on the inverse graph. Each call will show you another strong connective component of the graph.
Now we need to understand why this is a solution. You can agree that, within a graph inside a strong connective component, there can be only vertexes that are on a circle, as otherwise there would not be a road between one and any of the other vertexes. Therefore, the points that are not in any of the circles will create a strong connective sub-graph on their own.
In the last article, we learned that the topological sort would place the items into an order such that all edges coming out from the vertexes point toward vertexes in the right direction. Now, inside graphs that contain circles, we can hardly talk about topological order, as by definition, topological order can be made only from circle-free graphs. However, we ignore this fact and build this so-called topological order (the inverse order of how we leave the vertexes during a Depth-First Search). Now we will reverse the direction of the edges inside the graph.
This way the edges that build the topological order are reversed, and all that will remain as edges pointing from left to right are those that, until now, were against the topological order, pointing from right to left. These edges formed the base circle system of the graph.
Now if we call the DFS in the so-called “topological order,” each DFS will sense a strong connective component. On the inverse graph, the search can go ahead on those edges that were on a circle, and show those vertexes that are on a circle, and in the end it will drop by at each of the vertexes that maintain the circle.
Quite ingenious, is it not? Moreover, here is our modified BFS algorithm. First, we call a simple DFS to tell us the inverse order of how we leave the vertexes; this will be saved inside the topological array, as shown in the previous article. Second, we invert the graph inside the inverseList array and finally call the DPS in the right order. Here is what this looks like when translated into C:
void DFS_inver(int vertex)
{
printf(" %d ", vertex);
pListIt p;
color[vertex] = GRAY;
for (p = inverseList[vertex]; p != NULL; p = p -> p_next)
if (!color[p -> value])
{
DFS_inver(p -> value);
}
}
…
for (i = 0 ; i < n; ++i)
if (!color[topological_order[i]])
{
callCount++;
printf("n%d) ", callCount);
DFS_inver(topological_order[i]);
}
This way we will get as result for the upper graph the result:
The strong connected components of the graph
1) 1 8 5 2 12 11 9 6 3 10 18 14 20 15 19
2) 4
3) 17
4) 13 22 16
5) 21
6) 7
With this, we have solved all the problems for today. Now if we want to tell what points on the map can be reached from a certain point, all we need to do is enter the map's information as input and read the result from the output file. Here is the C source file that contains all of the techniques discussed in this article. Feel free to explore it and try it out for different inputs.
I would like to thank you for reading through my article and invite you to tell me your thoughts related to it here on the blog or over at our friendly forum on Dev Hardware. The subject of our next article will be articulation edges and vertexes, so if you are interested make sure to come back. Until the next time we meet, Live With Passion!
Code Examples 
Articulation Edges and Vertexes
