Question: Directed MST (Edmond's Algorithm)
0
5.6 years ago by
Forst, Christian90 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. thanks Christian
go graph rbgl • 1.4k views
modified 5.6 years ago by Steve Lianoglou12k • written 5.6 years ago by Forst, Christian90
0
5.6 years ago by
Denali
Steve Lianoglou12k wrote:
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
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]]
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
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]]
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