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.

I'm trying to modify this algorithm: http://demonstrations.wolfram.com/ConnectingTownsUsingKruskalsAlgorithm/

The thing is that I want to receive a Graph (declared outside, with all its vertex, edges and weights) in the Kruskal's function and start from there, using maybe a WeightedAdjacencyMatrix[G] and sort the weights and returning them. It's just a practice I want to do, because I'm learning Mathematica, so I'm still a noob with this. To be more specific with my question, I just want to know where and how I can replace parts from the code, with the things I mentioned above. This is my idea, of course without the Kruskal's implementation:

G = Graph[{a \[UndirectedEdge] b, a \[UndirectedEdge] d, 
a \[UndirectedEdge] f, b \[UndirectedEdge] c, 
b \[UndirectedEdge] d, b \[UndirectedEdge] e, 
c \[UndirectedEdge] e, c \[UndirectedEdge] g, 
d \[UndirectedEdge] e, d \[UndirectedEdge] f, 
d \[UndirectedEdge] g, e \[UndirectedEdge] g, 
f \[UndirectedEdge] g}, 
EdgeWeight -> {5, 6, 7, 5, 5, 4, 3, 3, 2, 2, 3, 1, 2}, 
VertexLabels -> "Name", ImagePadding -> 10] 
Kruskal[G]
share|improve this question
    
Sorry José, but I can't understand "I just want to know where and how I can replace parts from the code" Can you explain that further? –  belisarius Oct 18 '12 at 2:58
1  
And welcome! I think you're our first Tico around! –  belisarius Oct 18 '12 at 3:00
    
Yeah sorry for not explaining it well, and thanks for your welcome. I think I did a mess actually. I want to change the implementation of the function, I want it to receive the Graph, with its vertex, edges, and weights. And find the MinimumSpanningTree. It's like implementing the MinimumSpanningTree function actually, step by step. I was looking for the Combinatorica implemntation but I need to have it into one same function. Sorry if I'm not explaining it well! Thanks for your time! –  José Del Valle Oct 18 '12 at 3:05
1  
Have you seen this? –  J. M. Oct 18 '12 at 3:47
1  
If you solve your own question, please remember to post the answer –  belisarius Oct 18 '12 at 4:15
show 3 more comments

1 Answer

I don't exactly know that I understand you correctly. You have some graph G in structure Graph. Then you want to use MST (Prim/Kruskal) algorithm to obtain changed G which is MST graph. I tried that but it didn't work in M8.

Here is how I did that the other way:

  1. I prepared graph in nested list graph (matrix nxn), where graph[[i,j]] are weights between i and j vertices. Of course that matrix, in principle, should be symmetric and weights graph[[i,i]] should be 0.
  2. I use MST algorithm on that matrix, for example Kruskal:

     kruskal[pts_] := 
      Module[{n = Length[pts[[2]]], vpairs, jj = 0, hh, pair, dist, c1, c2,
    c1c2}, Do[hh[k] = {k}, {k, n}];
    vpairs=Sort[Flatten[
     Table[{pts[[k, l]], {k, l}}, {k, 1, n - 1}, {l, k + 1, n}], 1]];
     First[Last[Reap[While[jj < Length[vpairs], jj++;
      {dist, pair} = vpairs[[jj]];
      {c1, c2} = {hh[pair[[1]]], hh[pair[[2]]]};
      If[c1 =!= c2, Sow[vpairs[[jj, 2]]];
       c1c2 = Union[c1, c2];
       Do[hh[c1c2[[k]]] = c1c2, {k, Length[c1c2]}];
       If[Length[hh[pair[[1]]]] == n, Break[]];];]]]]]
    
  3. Use that Kruskal function on your matrix: kruskal@graph. Function return list of pairs, something like: {{2,5},{5,7},...}

  4. Then you must change that list to object that can be understand by Graph function in Mathematica. Use that function:

    mstListToEdge[mstList_] := mstList /. {x_, y_} :> x \[UndirectedEdge] y
    
  5. In the end use list from 4. and graph matrix to generate Graph. You will obtain MST graph picture with weights.

    graphMst[edges_, graph_] :=
     Graph[edges, VertexLabels -> "Name", ImagePadding -> 10, 
      GraphLayout -> "SpringElectricalEmbedding",
      EdgeWeight -> 
       Array[graph[[edges[[#, 1]], 
          edges[[#, 2]]]] & (*mstWeights *), Length@edges]]
    
share|improve this answer
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.