# 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];

weightedGraph=WeightedAdjacencyGraph[SparseArray[Most@arrayR, {1000, 1000}, ∞]];

weG = weightedGraph;
resMatrix = AdjacencyMatrix[weG];
Table[minST = FindSpanningTree[weG];
adjM1 = AdjacencyMatrix[minST];
adjWG1 = AdjacencyMatrix[weG];
weG = WeightedAdjacencyGraph[
SparseArray[
Most@ArrayRules[
Chop[(adjWG1 - adjM1)]*WeightedAdjacencyMatrix[weG]], {1000,
1000}, \[Infinity]]];, {3}];
Chop[resMatrix - AdjacencyMatrix[weG]]


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

## 1 Answer

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}
];
G0 = WeightedAdjacencyGraph[A0, 0.];

G = G0;
A = WeightedAdjacencyMatrix[G];

graphs = Table[
A = (SparseArray[
Unitize[A] - AdjacencyMatrix[FindSpanningTree[G]]]) A;
G = WeightedAdjacencyGraph[A, 0.],
{3}
]; // AbsoluteTiming // First


0.250941

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...

• A significant bottleneck in my competition is a using of WeightedAdjacencyGraph ( my graph is huge ~30k nodes 40 millions of edges). I am confused why I need to create a graph to calculate MST and cant calculate it directly from the adjacency matrix. Of cause it possible to implement the Kruskal's algorithm, but I prefer not to reinvent the wheel – Kiril Danilchenko Dec 16 '18 at 17:41
• 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