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.l...@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@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.
______________________________________________
R-help@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.
