# Calculation of non-overlapping set (ordering set ) of minimum spanning trees

I am interested in calculating a set of non-overlapping minimum spanning trees of a weighted graph. For example to calculate the set of size 3. I calculate the maximum spanning tree, remove its edges and repeating.

When I use EdgeDelete, it takes an eternity (the graph is huge around 30,000 nodes and 40 millions of edges). So currently, I calculate it in the following manner

SeedRandom[1]
arrayR = Append[Thread[RandomSample[Tuples[Range[1000], {2}], 5000] ->
RandomReal[1, 5000]], {_, _} -> 0];

weG = weightedGraph;
Table[minST = FindSpanningTree[weG];
SparseArray[
Most@ArrayRules[
1000}, \[Infinity]]];, {3}];


Any suggestion on how to speed up the calculation

• "I am interested in calculating a set of non-overlapping minimum spanning trees of a weighted graph." I don't get what your aim is. Would you please elaborate? – Henrik Schumacher Dec 16 '18 at 16:13
• @HenrikSchumacher Thank you.I have a graph, and I interested in calculating a forest of k nonoverlapping trees (maybe each tree is a forest too, but for simplicity, I will call it a tree). The order of each tree in this set equal to its weight (the minimum spanning tree is the first, the second one is a minimum spanning tree in the original graph after removing the edges of the minimum spanning tree... – Kiril Danilchenko Dec 16 '18 at 16:26

Very interesting. What took so long was the processing of ArrayRules; this generates an unpacked array of rules and this cannot be processed as quickly as the packed arrays of nonzero positions and nonzero values (see also how I generate the initial weighted adjacency matrix A0 below).

Moreover, I observed that you reconstruct the sparse array only to set the default values to ∞; this is seemingly required by WeightedAdjacencyGraph because it will generate a complete graph. As I just found out by pure chance, WeightedAdjacencyGraph, when called with a SparseArray as first argument allows for a second argument that allows us to specify that edges with weight 0. shall be treated as nonexistent. Hence, we may use SparseArrays without any ∞ as follows:

SeedRandom[1]
A0 = SparseArray[
RandomSample[Tuples[Range[1000], {2}], 5000] -> RandomReal[1, 5000],
{1000, 1000}
];

G = G0;

graphs = Table[
A = (SparseArray[

Usually, I prefer to avoid Graphs at all and stick to adjacency matrices. The undocumented routine SparseArraySpanningTree can compute spanning trees directly from a SparseArray; unfortunately, it seems to be unable to compute a minimal spanning tree...
• Have also a look into Szabolcs' "IGraphM" package. There is another algorithm IGSpanningTree` that seems to be faster (but ignores direction of edges). – Henrik Schumacher Dec 16 '18 at 17:50