help in the Donalds B. Johnson's algorithm, i cannot understand the pseudo code (PART II)
- by Pitelk
Hi all ,
i cannot understand a certain part of the paper published by Donald Johnson about finding cycles (Circuits) in a graph.
More specific i cannot understand what is the matrix Ak which is mentioned in the following line of the pseudo code :
Ak:=adjacency structure of strong component K with least
vertex in subgraph of G induced by {s,s+1,....n};
to make things worse some lines after is mentins " for i in Vk do " without declaring what the Vk is...
As far i have understand we have the following:
1) in general, a strong component is a sub-graph of a graph, in which for every node of this sub-graph there is a path to any node of the sub-graph (in other words you can access any node of the sub-graph from any other node of the sub-graph)
2) a sub-graph induced by a list of nodes is
a graph containing all these nodes plus all the edges connecting these nodes.
in paper the mathematical definition is " F is a subgraph of G induced by W if W is subset of V and F = (W,{u,y)|u,y in W and (u,y) in E)}) where u,y are edges , E is the set of all the edges in the graph, W is a set of nodes.
3)in the code implementation the nodes are named by integer numbers 1 ... n.
4) I suspect that the Vk is the set of nodes of the strong component K.
now to the question. Lets say we have a graph G= (V,E) with V = {1,2,3,4,5,6,7,8,9} which it can be divided into 3 strong components the SC1 = {1,4,7,8} SC2= {2,3,9} SC3 = {5,6} (and their edges)
Can anybody give me an example for s =1, s= 2, s= 5 what if going to be the Vk and Ak according to the code?
The pseudo code is in my previous question in
http://stackoverflow.com/questions/2908575/help-in-the-donalds-b-johnsons-algorithm-i-cannot-understand-the-pseudo-code
and the paper can be found at
http://stackoverflow.com/questions/2908575/help-in-the-donalds-b-johnsons-algorithm-i-cannot-understand-the-pseudo-code
thank you in advance
