3
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Woring within the Combinatorica package with Mma 7, Needs["Combinatorica"]` ShowGraph@MinimumSpanningTree@PetersenGraph and NumberOfSpanningTrees@PetersenGraph => 2000 $\endgroup$
    – user1066
    Jan 29, 2013 at 16:53
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 29, 2013 at 17:31
  • 1
    $\begingroup$ related post: mathematica.stackexchange.com/questions/13160/… $\endgroup$
    – halmir
    Jan 30, 2013 at 14:07
  • 1
    $\begingroup$ @JacobAkkerboom also related: mathematica.stackexchange.com/questions/33857/… and mathematica.stackexchange.com/a/33882/1997 $\endgroup$
    – ubpdqn
    Mar 13, 2014 at 12:40
  • $\begingroup$ @ubpdqn ah, thank you, maybe there is some duplication going on. If Combinatorica really is obsolete, then that is another argument to close. $\endgroup$ Mar 13, 2014 at 12:48

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 30, 2013 at 12:29
  • $\begingroup$ See also SetEdgeWeights $\endgroup$ Jan 30, 2013 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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