[BioC] Directed MST (Edmond's Algorithm)
Forst, Christian
christian.forst at mssm.edu
Tue Oct 22 18:56:33 CEST 2013
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 at gmail.com [mailinglist.honeypot at gmail.com] on behalf of Steve Lianoglou [lianoglou.steve at 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
More information about the Bioconductor
mailing list