[BioC] R graphs: all paths lengths between two nodes in a directed graph

[Victoria V Plamadeala]

Hi Li, 

I did look into all RBGL graph algorithms.  They appear useful for situations when one is interested in some optimal criteria, like the shortest path.  It seems that getting all possible paths between two nodes and their associated lengths would rely on some recursive method.  I can neither come up with a code in R for such a method nor do I see a way to apply the RBGL functions to my problem.  Would you have any more specific suggestions? 

Thanks, 

Victoria 

----- Original Message -----
From: Li Long <Li.Long at isb-sib.ch>
Date: Wednesday, April 22, 2009 7:26 am
Subject: Re: [BioC] R graphs: all paths lengths between two nodes in a directed graph

> 
> you can take a look at BioC/RBGL package, which contains quite a 
> number of
> often-used graph algorithms.
> 
> Li
> 
> > I would need help in obtaining all path lengths between two 
> nodes in a
> > directed graph.
> >
> > Suppose I have the following directed graph (below) called 
> "mygraph":>
> >> library(graph)
> >>
> >> y <- as.character(seq(1,6))
> >> rel <- list(c(2,4), c(3,5), 6, 5, 6, NULL)
> >> edgelength <- list(c(0,1), c(0,2), 3, 0, 0, "NA")
> >>
> >> edL=vector("list", length=(length(y)))
> >> names(edL)=y
> >> for(l in 1:(length(y)))
> > + {edL[[l]]=list(edges=rel[[l]], weights=edgelength[[l]])}
> >>
> >> mygraph=new("graphNEL", nodes = y, edgeL = edL, edgemode = 
> "directed")>> mygraph
> > A graphNEL graph with directed edges
> > Number of Nodes = 6
> > Number of Edges = 7
> >> edges(mygraph)
> > $`1`
> > [1] "2" "4"
> >
> > $`2`
> > [1] "3" "5"
> >
> > $`3`
> > [1] "6"
> >
> > $`4`
> > [1] "5"
> >
> > $`5`
> > [1] "6"
> >
> > $`6`
> > character(0)
> >
> >> edgeWeights(mygraph)
> > $`1`
> > 2 4
> > 0 1
> >
> > $`2`
> > 3 5
> > 0 2
> >
> > $`3`
> > 6
> > 3
> >
> > $`4`
> > 5
> > 0
> >
> > $`5`
> > 6
> > 0
> >
> > $`6`
> > numeric(0)
> >
> > I am striving to get the lengths of all possible paths between 
> nodes "1"
> > and "6", which are:
> >
> > 1 --> 2 --> 3 --> 6 : length 0+0+3=3
> > 1 --> 2 --> 5 --> 6 : length 0+2+0=2
> > 1 --> 4 --> 5 --> 6 : length 1+0+0=1
> >
> > What would be a clever way to accomplish this in R?  Thank you.
> >
> > _______________________________________________
> > Bioconductor mailing list
> > Bioconductor at stat.math.ethz.ch
> > https://stat.ethz.ch/mailman/listinfo/bioconductor
> > Search the archives:
> > http://news.gmane.org/gmane.science.biology.informatics.conductor
> >
> 
>