shapeshifter
January 23rd, 2011, 01:32 PM
Here I have got a pseudocode of an algorithm that can find bridges, articulation points and contituents (a.k.a. biconnected components) in a graph. Can anyone help me, please, to get rid of the reccurence inside the Visit procedure?
{
N - number of vertices
D[1..N] - table of pre-order enumeration
Low[1..N] - table of Low function
C[edge] - table that should show to which contituent belongs some given edge
}
procedure Visit(v, father: Integer);
{vertex v that we are visiting, and vertex father from which we were going to v}
begin
D[v]:=time; {we save the number of v in pre-order notation}
Inc(time);
Low[v]:=D[v]; {Low[v] cannot be larger than D[v]}
for i:=Nieghbour(v) do {loop that is passing through every neighbour of v}
if i<>father then {except for the vertex from which we came to v}
if D[i]=-1 then {if vertex hasn't been visited yet...}
begin
Put_On_Stack(v<->i); {we put on stack the edge through which we were going}
Visit(i,v); {********* RECCURENCE!!! ************ }
if Low[v]>Low[i] then {and we check the value of Low for out vertex}
Low[v]:=Low[i];
if Low[i]>=D[v] then {we have found new constituent}
begin
Inc(No); {we increase number of constituents}
repeat
Get_From_Stack(e); {we take from stack edge that belong to that constituent}
C[e]:=No; {this means that the edge belongs to No contstituent}
until e=v<->i;
end;
end else {vertex i has been already visited}
begin
if D[v]>D[i] then {if i is predecessor of v in a tree}
Put_On_Stack(v<->i); {we put out edge on the stack }
if Low[v]>D[i] then {we check the pre-order numer of vertex i}
Low[v]:=D[i];
end;
end;
procedure FindConstituent;
begin
for i:=1 to N do
D[i]:=-1; {we mark all vertices as not visited yet}
time:=1; {this variable is needed to create pre-order enumeration}
No:=0; {this variable is used to number constituents}
for i:=1 to N do
if D[i]=-1 then {if vertex i hasn't been visited yet ...}
Visit(i,-1); {we go to the vertex i}
end;
I would be very greatful for your help! :)
{
N - number of vertices
D[1..N] - table of pre-order enumeration
Low[1..N] - table of Low function
C[edge] - table that should show to which contituent belongs some given edge
}
procedure Visit(v, father: Integer);
{vertex v that we are visiting, and vertex father from which we were going to v}
begin
D[v]:=time; {we save the number of v in pre-order notation}
Inc(time);
Low[v]:=D[v]; {Low[v] cannot be larger than D[v]}
for i:=Nieghbour(v) do {loop that is passing through every neighbour of v}
if i<>father then {except for the vertex from which we came to v}
if D[i]=-1 then {if vertex hasn't been visited yet...}
begin
Put_On_Stack(v<->i); {we put on stack the edge through which we were going}
Visit(i,v); {********* RECCURENCE!!! ************ }
if Low[v]>Low[i] then {and we check the value of Low for out vertex}
Low[v]:=Low[i];
if Low[i]>=D[v] then {we have found new constituent}
begin
Inc(No); {we increase number of constituents}
repeat
Get_From_Stack(e); {we take from stack edge that belong to that constituent}
C[e]:=No; {this means that the edge belongs to No contstituent}
until e=v<->i;
end;
end else {vertex i has been already visited}
begin
if D[v]>D[i] then {if i is predecessor of v in a tree}
Put_On_Stack(v<->i); {we put out edge on the stack }
if Low[v]>D[i] then {we check the pre-order numer of vertex i}
Low[v]:=D[i];
end;
end;
procedure FindConstituent;
begin
for i:=1 to N do
D[i]:=-1; {we mark all vertices as not visited yet}
time:=1; {this variable is needed to create pre-order enumeration}
No:=0; {this variable is used to number constituents}
for i:=1 to N do
if D[i]=-1 then {if vertex i hasn't been visited yet ...}
Visit(i,-1); {we go to the vertex i}
end;
I would be very greatful for your help! :)