Directed MST (Edmond's Algorithm)
1
0
Entering edit mode
@forst-christian-5709
Last seen 9.6 years ago
I am looking for an implementation of Edmond's (or better) algorithm to calculated a directed minimum spanning tree from a directed graph. I found the edmondsOptimumBranching() function in the RBGL package but I am struggling in getting my graphs (from edge-lists) in the right format. I would guess using addEdge() is not the way to go to read large graphs. I am open for suggestions for other packages. thanks Christian
GO graph RBGL GO graph RBGL • 3.5k views
ADD COMMENT
0
Entering edit mode
@steve-lianoglou-2771
Last seen 13 months ago
United States
Hi, On Tue, Oct 22, 2013 at 9:13 AM, Forst, Christian <christian.forst at="" mssm.edu=""> wrote: > I am looking for an implementation of Edmond's (or better) algorithm to calculated a directed minimum spanning tree from a directed graph. I found the edmondsOptimumBranching() function in the RBGL package but I am struggling in getting my graphs (from edge-lists) in the right format. I would guess using addEdge() is not the way to go to read large graphs. > I am open for suggestions for other packages. The igraph package is usually a good place to look for algorithms over graphs: http://igraph.sourceforge.net There is a `minimum.spanning.tree` function in there: http://igraph.sourceforge.net/doc/R/minimum.spanning.tree.html HTH, -steve -- Steve Lianoglou Computational Biologist Bioinformatics and Computational Biology Genentech
ADD COMMENT
0
Entering edit mode
On Tue, Oct 22, 2013 at 12:24 PM, Steve Lianoglou <lianoglou.steve@gene.com>wrote: > Hi, > > On Tue, Oct 22, 2013 at 9:13 AM, Forst, Christian > <christian.forst@mssm.edu> wrote: > > I am looking for an implementation of Edmond's (or better) algorithm to > calculated a directed minimum spanning tree from a directed graph. I found > the edmondsOptimumBranching() function in the RBGL package but I am > struggling in getting my graphs (from edge-lists) in the right format. I > would guess using addEdge() is not the way to go to read large graphs. > > I am open for suggestions for other packages. > > The igraph package is usually a good place to look for algorithms over > graphs: > > http://igraph.sourceforge.net > > There is a `minimum.spanning.tree` function in there: > > http://igraph.sourceforge.net/doc/R/minimum.spanning.tree.html > > HTH, > -steve > > Do we need some investment in interoperability with igraph? Additionally, it seems to me that there has been little rallying around any given external format for representing graphs -- we had some GXL support in graph package but GXL seems to have gone stale (web site is dated 2002), and igraph does not handle it. Perhaps some tools for GraphML import/export would be worthwhile? > -- > Steve Lianoglou > Computational Biologist > Bioinformatics and Computational Biology > Genentech > > _______________________________________________ > Bioconductor mailing list > Bioconductor@r-project.org > https://stat.ethz.ch/mailman/listinfo/bioconductor > Search the archives: > http://news.gmane.org/gmane.science.biology.informatics.conductor > [[alternative HTML version deleted]]
ADD REPLY
0
Entering edit mode
On Oct 22, 2013, at 9:39 AM, Vincent Carey wrote: > Do we need some investment in interoperability with igraph? Maybe this is old news, or falls short of the mark, but two functions from igraph provide some interoperability: igraph.from.graphNEL(graphNEL, name = TRUE, weight = TRUE, unlist.attrs = TRUE) igraph.to.graphNEL(graph) - Paul
ADD REPLY
0
Entering edit mode
On Tue, Oct 22, 2013 at 1:23 PM, Paul Shannon <pshannon@fhcrc.org> wrote: > > On Oct 22, 2013, at 9:39 AM, Vincent Carey wrote: > > > Do we need some investment in interoperability with igraph? > > Maybe this is old news, or falls short of the mark, but two functions from > igraph provide some interoperability: > > > igraph.from.graphNEL(graphNEL, name = TRUE, weight = TRUE, > unlist.attrs = TRUE) > igraph.to.graphNEL(graph) > > - Paul missed them. thanks. perhaps import to igraph and convert to graphNEL is a solution for OP? [[alternative HTML version deleted]]
ADD REPLY
0
Entering edit mode
That may work - thanks. ________________________________________ From: bioconductor-bounces@r-project.org [bioconductor- bounces@r-project.org] on behalf of Vincent Carey [stvjc@channing.harvard.edu] Sent: Tuesday, October 22, 2013 13:31 To: Paul Shannon Cc: Steve Lianoglou; bioconductor at r-project.org Subject: Re: [BioC] Directed MST (Edmond's Algorithm) On Tue, Oct 22, 2013 at 1:23 PM, Paul Shannon <pshannon at="" fhcrc.org=""> wrote: > > On Oct 22, 2013, at 9:39 AM, Vincent Carey wrote: > > > Do we need some investment in interoperability with igraph? > > Maybe this is old news, or falls short of the mark, but two functions from > igraph provide some interoperability: > > > igraph.from.graphNEL(graphNEL, name = TRUE, weight = TRUE, > unlist.attrs = TRUE) > igraph.to.graphNEL(graph) > > - Paul missed them. thanks. perhaps import to igraph and convert to graphNEL is a solution for OP? [[alternative HTML version deleted]] _______________________________________________ Bioconductor mailing list Bioconductor at r-project.org https://stat.ethz.ch/mailman/listinfo/bioconductor Search the archives: http://news.gmane.org/gmane.science.biology.informatics.conductor
ADD REPLY
0
Entering edit mode
Thank you. Unfortunately Prim's algorithm only works for undirected graphs (AFAIK). Edmond's algorithm would be able to utilize directionality. Christian ________________________________________ From: mailinglist.honeypot@gmail.com [mailinglist.honeypot@gmail.com] on behalf of Steve Lianoglou [lianoglou.steve@gene.com] Sent: Tuesday, October 22, 2013 12:24 To: Forst, Christian Cc: bioconductor at r-project.org Subject: Re: [BioC] Directed MST (Edmond's Algorithm) Hi, On Tue, Oct 22, 2013 at 9:13 AM, Forst, Christian <christian.forst at="" mssm.edu=""> wrote: > I am looking for an implementation of Edmond's (or better) algorithm to calculated a directed minimum spanning tree from a directed graph. I found the edmondsOptimumBranching() function in the RBGL package but I am struggling in getting my graphs (from edge-lists) in the right format. I would guess using addEdge() is not the way to go to read large graphs. > I am open for suggestions for other packages. The igraph package is usually a good place to look for algorithms over graphs: http://igraph.sourceforge.net There is a `minimum.spanning.tree` function in there: http://igraph.sourceforge.net/doc/R/minimum.spanning.tree.html HTH, -steve -- Steve Lianoglou Computational Biologist Bioinformatics and Computational Biology Genentech
ADD REPLY

Login before adding your answer.

Traffic: 698 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6