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

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