Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
1  
Woring within the Combinatorica package with Mma 7, Needs["Combinatorica"]` ShowGraph@MinimumSpanningTree@PetersenGraph and NumberOfSpanningTrees@PetersenGraph => 2000 –  TomD Jan 29 '13 at 16:53
1  
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
1  
related post: mathematica.stackexchange.com/questions/13160/… –  halmir Jan 30 '13 at 14:07
1  
    
@ubpdqn ah, thank you, maybe there is some duplication going on. If Combinatorica really is obsolete, then that is another argument to close. –  Jacob Akkerboom Mar 13 at 12:48
show 1 more comment

1 Answer

up vote 3 down vote accepted

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:

enter image description here

share|improve this answer
    
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
    
See also SetEdgeWeights –  Jacob Akkerboom Jan 30 '13 at 12:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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