[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[igraph] All MSTs
From: |
John Wiedenhoeft |
Subject: |
[igraph] All MSTs |
Date: |
Thu, 7 Aug 2008 12:47:23 +0200 |
User-agent: |
KMail/1.9.9 |
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] All MSTs,
John Wiedenhoeft <=