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

Robert Gentleman rgentlem at fhcrc.org
Thu Apr 23 06:37:07 CEST 2009



Victoria V Plamadeala wrote:
> 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? 
> 
  Hi,
    google suggests this method:
http://www.perlmonks.org/?node_id=522270
  should be relatively straightforward in R, or you can just use their perl code.
  One word of caution is that if the graph is at all large or dense the size of
the output can be enormous.

  best wishes
    Robert

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

-- 
Robert Gentleman, PhD
Program in Computational Biology
Division of Public Health Sciences
Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N, M1-B514
PO Box 19024
Seattle, Washington 98109-1024
206-667-7700
rgentlem at fhcrc.org



More information about the Bioconductor mailing list