Question: Directed MST (Edmond's Algorithm)
0
gravatar for Forst, Christian
6.0 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.6k views
ADD COMMENTlink modified 6.0 years ago by Steve Lianoglou12k • written 6.0 years ago by Forst, Christian90
Answer: Directed MST (Edmond's Algorithm)
0
gravatar for Steve Lianoglou
6.0 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
ADD COMMENTlink written 6.0 years ago by Steve Lianoglou12k
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 REPLYlink written 6.0 years ago by Vincent J. Carey, Jr.6.3k
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 REPLYlink written 6.0 years ago by Paul Shannon750
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 REPLYlink written 6.0 years ago by Vincent J. Carey, Jr.6.3k
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 REPLYlink written 6.0 years ago by Forst, Christian90
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 REPLYlink written 6.0 years ago by Forst, Christian90
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 16.09
Traffic: 291 users visited in the last hour