Articulation Edges and Vertexes - Articulation Edges: Code Snippet
(Page 2 of 4 )
How will all this look in a programming language? Here is the answer:
int DFS_Articulation_edge(int vertex, int level)
{
color[vertex] = GRAY;
topological_order[vertex] = level;
int sTMinLevBaPE = INT_MAX;
int sTMinLevBaPECur = 0;
pListIt p;
for (p = adjacencyList[vertex]; p != NULL; p = p -> p_next)
{
if (!color[p -> value])
{
ancient[p->value] = vertex;
sTMinLevBaPECur =
DFS_Articulation_edge(p->value, level + 1);
}
if (sTMinLevBaPECur < level)
{
if (sTMinLevBaPECur < sTMinLevBaPE)
{
sTMinLevBaPE = sTMinLevBaPECur;
}
}
else
{
if (color[p->value] == 1 &&
topological_order[p->value] < level -1 && topological_order[p->value] < sTMinLevBaPE )
{
sTMinLevBaPE = topological_order[p->value];
}
}
}
color[vertex] = BLACK;
if (ancient[vertex] && sTMinLevBaPE == INT_MAX)
{
printf(" %d - %dn", ancient[vertex], vertex);
}
return sTMinLevBaPE;
}
Let there be the following graph as input:
-->Image Courtesy of Kátai Zoltán- Introduction to Graphs<--
If we execute our application we will get as a result the following edges, what are indeed correct. It's a job well done!
Cutting edges
5 - 7
16 - 21
14 - 17
1 - 4
Next: Articulation Vertexes: Theory >>
More Code Examples Articles
More By Gabor Bernat
