# Combinatorica vs Built-in functions: 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 $\mathbb{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 Jan 29, 2013 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. Jan 29, 2013 at 17:31
• related post: mathematica.stackexchange.com/questions/13160/… Jan 30, 2013 at 14:07
• @JacobAkkerboom also related: mathematica.stackexchange.com/questions/33857/… and mathematica.stackexchange.com/a/33882/1997 Mar 13, 2014 at 12:40
• @ubpdqn ah, thank you, maybe there is some duplication going on. If Combinatorica really is obsolete, then that is another argument to close. Mar 13, 2014 at 12:48

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. Jan 30, 2013 at 12:29