1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – Henrik Schumacher Dec 16 '18 at 16:13
  • $\begingroup$ @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... $\endgroup$ – Kiril Danilchenko Dec 16 '18 at 16:26
1
$\begingroup$

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 SparseArray`SpanningTree can compute spanning trees directly from a SparseArray; unfortunately, it seems to be unable to compute a minimal spanning tree...

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Kiril Danilchenko Dec 16 '18 at 17:41
  • 1
    $\begingroup$ Have also a look into Szabolcs' "IGraphM" package. There is another algorithm IGSpanningTree that seems to be faster (but ignores direction of edges). $\endgroup$ – Henrik Schumacher Dec 16 '18 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.