Finding all paths between two nodes in a general graph is very hard.

If your graph is sparse you may be able to construct the list of paths

provided of course you take care not to get stuck in a cycle.

But for most practical purposes you may just need edge disjoint path

or vertex disjoint paths.

I am not sure about cycles. But I suppose you can just use the minimum

spanning tree and iteratively add the remaining edges to get the cycles.

Nikhil Kaza

Asst. Professor,

City and Regional Planning

University of North Carolina

[hidden email]
On May 4, 2010, at 7:34 AM, jcano wrote:

>

> 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.

>

> ______________________________________________

>

[hidden email] mailing list

>

https://stat.ethz.ch/mailman/listinfo/r-help> PLEASE do read the posting guide

http://www.R-project.org/posting-guide.html> and provide commented, minimal, self-contained, reproducible code.

______________________________________________

[hidden email] mailing list

https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide

http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.