# Use of MinimumSpanningTree

What kind of argument is expected by MinimumSpanningTree (from the package Combinatorica)? Is it possible that I am providing the right kind of argument, but that conflict between usual definitions and definitions from the package Combinatorica prevents correct evaluation?

Note that, conform the documentation page of FindShortestPath,

graph=SystemPetersenGraph[4, 1, EdgeWeight -> {4, 0, 3, 1, 3, 2, 7, 8, 5, 2, 1, 6}]


Produces some weighted graph. We can then do

FindShortestPath[graph,1,3]


which works as expected. Note that if we use CombinatoricaPetersenGraph this will not work. Anyway, I would expect MinimumSpanningTree to work on at least one of the two graphs generated this way. Unfortunately, I cannot get it it to work. I have been unable to get MimimumSpanningTree to work on any graph so far.

Remarks

The documentation center provides very little information on MimimumSpanningTree. The PetersenGraph may not be a very nice example, as Mathematica seems to point out an error in the syntax even before the package Combinatorica is loaded. However, upon asking the FullForm of the result, everything seems to be as we expect it to be.

Edit: Can I assume there is no efficient way to let MinimumSpanningTree calculate a minimum spanning tree between many points in R^2? I suppose that for this one should refer to How to speed up Minimum Spanning Tree algorithm?. As a test I entered a huge graph in MinimumSpanningTree, but an Algorithm by Daniel Lichtblau was faster.

-
Woring within the Combinatorica package with Mma 7, Needs["Combinatorica"] ShowGraph@MinimumSpanningTree@PetersenGraph and NumberOfSpanningTrees@PetersenGraph => 2000 –  TomD Jan 29 '13 at 16:53
Nice, thanks! Note though that the graph that is displayed in the first case is not a minimum spanning tree in the sense that the Euclidean distance of all the edges is minimized. –  Jacob Akkerboom Jan 29 '13 at 17:31
related post: mathematica.stackexchange.com/questions/13160/… –  halmir Jan 30 '13 at 14:07

I am working within the Combinatorica package with Mma 7.

Also, I am not by any means an expert here, but I am interested in the question posed. What follows is an attempt at obtaining a minimum spanning tree from a weighted Petersen graph

Needs["Combinatorica"]


Generate a weighted Peterson graph (shown on the left below)

edgeRuleList = {#[[1]], EdgeWeight -> #[[2]]} & /@
Transpose[{Edges@PetersenGraph, {4, 0, 3, 1, 3, 2, 7, 8, 5, 2, 1,
6, 1, 1, 1}}];

myWeightedPetersonGraph =
SetGraphOptions[PetersenGraph, edgeRuleList];

ShowGraph[myWeightedPetersonGraph, VertexLabel -> True,
VertexLabelPosition -> Center, VertexStyle -> Disk[Large],
VertexColor -> LightYellow, EdgeColor -> Red,
VertexNumberColor -> Black, BaseStyle -> {FontSize -> 12}]


where

Edges@myWeightedPetersonGraph


=> {{1, 3}, {1, 4}, {2, 4}, {2, 5}, {3, 5}, {6, 7}, {7, 8}, {8, 9}, {9, 10}, {6, 10}, {1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}

and

GetEdgeWeights@myWeightedPetersonGraph


=> {4, 0, 3, 1, 3, 2, 7, 8, 5, 2, 1, 6, 1, 1, 1}

Generate the minimum spanning tree from weighted Peterson (shown on right below)

myMinSpanningTree =
ShowGraph[MinimumSpanningTree@myWeightedPetersonGraph,
VertexLabel -> True, VertexLabelPosition -> Center,
VertexStyle -> Disk[Large], VertexColor -> LightYellow,
EdgeColor -> Red, VertexNumberColor -> Black,
BaseStyle -> {FontSize -> 12}]
`

Graphs:

-
Thank you, this seems very nice and to the point. I am considering accepting it, but first let me see if I can get it to work for other graphs. –  Jacob Akkerboom Jan 30 '13 at 12:29