Minimal Spanning Tree with EdgeWeights

Question

Given a graph with EdgeWeights, I'm finding the minimal spanning tree:

g = Graph[{"A" <-> "B", "B" <-> "C", "C" <-> "A", "B" <-> "D", 
       "C" <-> "D"}, EdgeWeight -> {2, 3, 4, 1, 0}, 
      VertexLabels -> "Name", 
      EdgeLabels -> 
       Thread[{"A" <-> "B", "B" <-> "C", "C" <-> "A", "B" <-> "D", 
          "C" <-> "D"} -> {2, 3, 4, 1, 0}]]

t = FindSpanningTree[g]

But now the tree t and has no weights:

WeightedGraphQ@t (*False*)

Is there a better way to find the total weights in the subgraph than this?

Total@Table[PropertyValue[{g, e}, EdgeWeight], {e, EdgeList@t}]

Answer 1

You already show a solution to the problem, and you are asking if there are easier ways to accomplish the same.

The IGraph/M package has convenience functions to make some things that are already possible with builtins a bit easier.

The IGSpanningTree function will preserve edge weights:

<< IGraphM`

?IGSpanningTree

IGSpanningTree[graph] returns a minimum spanning tree of graph. Edge directions are ignored. Edge weights are taken into account and are preserved in the tree.

t = IGSpanningTree[g, VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"]

Here the VertexLabels -> "Name", EdgeLabels -> "EdgeWeight" options are standard for Graph, generally work in any function that returns a graph (both in builtins and in IGraph/M functions), and affect only the display of the graph.

IGraph/M also has property extractors which always return value lists. Thus, to sum the weights,

IGEdgeProp[EdgeWeight][t] // Total
(* 3 *)

?IGEdgeProp

IGEdgeProp[prop] is an operator that extracts the values of edge property prop from a graph.

For EdgeWeight specifically, we may have used the builtin PropertyValue to get the weight list:

PropertyValue[t, EdgeWeight]
(* {2, 1, 0} *)

However, with some other graph properties this will return a rule list instead of a value list. With custom properties this typically does not work at the level of the graph, and must be used at the level of individual edges (as you did in Table in your original post).

---

For completeness, here is a hopefully robust way to transfer weights from the original graph to the spanning tree, using builtins only:

t = FindSpanningTree[g]

weights = Association@Table[edge -> PropertyValue[{g, edge}, EdgeWeight], {edge, EdgeList[g]}]

t2 = SetProperty[t, EdgeWeight -> Lookup[weights, EdgeList[t]]]

This method does not work with multigraphs. When multiple weighted edges are running between the same vertices, we would need to pay special attention to select smaller weight and transfer that to the tree. This would make the code quite a bit more complex. IGraph/M takes care of this detail.