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

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

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

jcano
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
Reply | Threaded
Open this post in threaded view
|

Re: All possible paths between two nodes in a flowgraph using igraphs?

Nikhil Kaza-2
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-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.