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

[Nikhil Kaza]

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

nikhil.list at gmail.com



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.
>
> ______________________________________________
> R-help at r-project.org 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.