Re: [igraph] All MSTs

[Csardi Gabor]

John, unfortunately none of the two algorithms are implemented in igraph,
but I guess you already knew this.

I'll happily add this feature request to the TODO list, but 
don't dare to promise anything, we already have made too many commitments,
some towards out collaborators, there is more pressure to do these 
first. 

If you decide to implement one/both of these, we are able to provide
some help/support in the form of answering questions about 
programming with igraph, and then (of course) putting the code
into igraph (and giving you the credit).

Best,
Gabor

ps. you can follow these issues here:
http://code.google.com/p/igraph/issues/detail?id=140
http://code.google.com/p/igraph/issues/detail?id=142

On Thu, Aug 07, 2008 at 12:47:23PM +0200, John Wiedenhoeft wrote:
> Dear all,
> 
> I'm trying to derive all MSTs from an undirected graph. As I didn't find a 
> function for this in igraph, I am about to write an R script that does this 
> (in the end, I'm interested in the sum of the adjacency matrices of all MSTs 
> divided by their number).
> 
> My approach is the following: creating a graph EG who's spanning trees 
> correspond 1:1 to the MSTs in G using Eppstein's algorithm: 
> 
> http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-50.pdf
> 
> and then extracting all STs from EG using Kapoor-Ramesh's algorithm:
> 
> http://citeseer.ist.psu.edu/kapoor95algorithms.html
> 
> Especially the second seems to be hard to implement, especially in R.
> 
> My question is: did someone by any chance implement at least one of these 
> algos before, or has even written something that extracts all MSTs and can be 
> used with R? BTW it would be great having Eppstein and Kapoor-Ramesh as 
> functions implemented directly in igraph (oh yes, this is a feature 
> request ;-) )
> 
> Cheers,
> John
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK