Circles and Connectivity in Graphs - Circles and the Base Circle System
(Page 2 of 4 )
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:
Circle: 8 5 2 1
Circle: 8 5 2
Circle: 11 9 6 3
Circle: 19 15 12
Circle: 20 15 12 11
Circle: 22 16 13
Circle: 18 14 11 9
Circle: 10 6 3
Next: Strong connective components >>
More Code Examples Articles
More By Gabor Bernat
/ 2 
