[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: 


and then extracting all STs from EG using Kapoor-Ramesh's algorithm:


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 ;-) )


reply via email to

[Prev in Thread] Current Thread [Next in Thread]