Combinatorica vs Built-in functions: Use of MinimumSpanningTree

Question

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 = System`PetersenGraph[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 Combinatorica`PetersenGraph 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.

Answer 1

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: