# help in the Donalds B. Johnson's algorithm, i cannot understand the pseudo code (PART II)

Posted
by Pitelk
on Stack Overflow
See other posts from Stack Overflow
or by Pitelk

Published on 2010-05-30T18:50:47Z
Indexed on
2010/05/30
18:52 UTC

Read the original article
Hit count: 424

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

© Stack Overflow or respective owner