[R] All possible paths between two nodes in a flowgraph using igraphs?

jcano javier.cano at urjc.es
Tue May 4 13:34:53 CEST 2010

Hi all

Is there any systematic way to compute all possible paths, first-order loops
and j-th order loops between two given nodes in a flowgraph (directed graph
with cycles) - preferably using the igraph library in R? I have checked the
igraph documentation but I can't figure out any direct and systematic way to
do so. Any ideas?
I use the following definitions from Butler, R. and A. Huzurbazar (1997).
Stochastic Network Models for Survival Analysis. Journal of the American
Statistical Association 92 (437), 246-257.
- A path from node i to j is any possible sequence of nodes from i to j
which does not pass through any intermediate node more than once.
- A first-order loop is any closed path in the flowgraph that returns to the
initial node of the loop without passing through any intermediate node more
than once.
- A jth-order loop consists of j nontouching first-order loops.

For example, in the flowgraph below
there are 18 paths between nodes 1 and a:
- 1a;
- 12a, 124a, 1243a, 1245a, 12436a, 124365a, 12456a, 124563a;
- 13a, 134a, 136a, 1342a, 1345a, 13456a, 1365a, 13654a, 136542a.
6 first-order loops:
- 12431, 13421, 1245631, 1365421, 45634, 43654;
and no loops of order two or more.

Thanks in advance

jcano http://n4.nabble.com/file/n2125347/flowgraph_subsume.jpg 
View this message in context: http://r.789695.n4.nabble.com/All-possible-paths-between-two-nodes-in-a-flowgraph-using-igraphs-tp2125347p2125347.html
Sent from the R help mailing list archive at Nabble.com.

More information about the R-help mailing list