Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Prims MST Algorithm

by b_bot (Initiate)
on Apr 22, 2013 at 16:37 UTC ( #1029921=perlmeditation: print w/replies, xml ) Need Help??

I have been meditating on Prims MST algorithm and a pre-order walk of the MST. The code below is the solution that I generated. The code uses the Graph module for the data structure. There are a couple of assumptions with the solution. 1.)The vertexes have (x,y) coordinates 2.)The weighted edges are the euclidean distance between two edge connected vertices. 3.)The graph is complete and undirected

Let me know what you think and or suggestions for improvement

#Prims algorithm to calculate MST of $G sub prims{ my($G, $root, $output) = @_; my $MST = (ref $G)->new; $MST->add_vertex($root); $MST->set_vertex_attribute($root, "X", $G->get_vertex_attribute($r +oot, "X")); $MST->set_vertex_attribute($root, "Y", $G->get_vertex_attribute($r +oot, "Y")); my @MST; while($MST->vertices != $G->vertices){ my $edge_weight = 9**9**9; my $lw_vertex; my $compared_vertex; foreach my $vertex($MST->vertices){ foreach my $successor ($G->successors($vertex)){ ##Find the lowest cost safe edge if(($edge_weight > $G->get_edge_weight($vertex,$successor +)) && ! $MST->has_vertex($successor)){ $edge_weight = $G->get_edge_weight($vertex,$successor +); $lw_vertex = $successor; $compared_vertex = $vertex; } } } #add the vertex and edge to the cut $MST->add_vertex($lw_vertex); $MST->add_weighted_edge($compared_vertex, $lw_vertex, $edge_we +ight); $MST->set_vertex_attribute($lw_vertex, "X", $G->get_vertex_att +ribute($lw_vertex, "X")); $MST->set_vertex_attribute($lw_vertex, "Y", $G->get_vertex_att +ribute($lw_vertex, "Y")); push(@MST, "($compared_vertex, $lw_vertex)"); } ##Print out the set for assignment print "MST = {@MST} \n"; print {$output} "MST = {@MST} \n"; return $MST; }
our @preorder_memoized; sub preorder_tree_walk{ my ($G, $root, $output) = @_; print "$root \n"; print {$output} "$root \n"; my @edge_vertices; my $edge_numb = my @e = $G->edges_from($root); if($edge_numb < 1){return;} push(@preorder_memoized, $root); push(@edge_vertices, $_->[1]) foreach @e; #build the tree structure as it would be represented in Euclidean + space. my @sorted_vertices = sort {$G->get_vertex_attribute($a,"X") <=> +$G->get_vertex_attribute($b,"X") or $G->get_vertex_attribute($a,"Y") <=> +$G->get_vertex_attribute($b, "Y") } @edge_vertices; #print "sorted_ = @sorted_vertices \n"; foreach my $edge (@sorted_vertices){ if($edge ~~ @preorder_memoized){next;} preorder_tree_walk($G, $edge, $output); } }

Replies are listed 'Best First'.
Re: Prims MST Algorithm
by educated_foo (Vicar) on Apr 22, 2013 at 17:20 UTC
    If it works, use it. However, Prim's algorithm is O(E), so in a complete graph you will get worst-case performance. If you have a complete graph and Euclidean distances, I suspect you can do much better using some geometric algorithm, perhaps by sorting the vertices in one dimension and using a sweep-line algorithm.
    Just another Perler interested in Algol Programming.
Re: Prims MST Algorithm
by Old_Gray_Bear (Bishop) on Apr 22, 2013 at 18:40 UTC
    A note for the Mathematically Forgetful -- MST == Minimum Spanning Tree. (See Prims Algorithm).

    .oO(It's been a loooong time....)

    ----
    I Go Back to Sleep, Now.

    OGB

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://1029921]
Approved by Corion
help
Chatterbox?
[1nickt]: The best sign I have sign in a protest march was carried by a kid of about 10 years "If you build a wall my generation will tear it down."
[1nickt]: ... sign I have seen ...
[1nickt]: Now that one made me hopeful! First time not angry in a long time when I saw that kid.
[Discipulus]: i propend for removing: why? because we are so few that we must find i minimal common divisor, this is certainly Perl not our (anyway private) thougths. And i say this still wondering because i love a lot freedom of expression. And i say this not for roho
[1nickt]: Discipulus that was the point of my story of taking the sticker off my truck. I know there are lots of people in the world who if I knw their private beliefs I might want to argue with them. And they with me. But life cannot all be arguments!
[1nickt]: This is less than perfect ... but demanding perfection (from people or from life) is a sure way to unhappiness.
[Discipulus]: and anyway we have CB where every (democratic) opinion can be expressed
erix eat the rich!
[1nickt]: I do think it is sad that roho has received 3 downvotes for his polite request, as did I when I objected to the profanity in stonecolddevin's sig. I upvoted both him and Karl for the discussion. Way too much downvoting for inappropriate reasons here!
Discipulus learn that 'argue' has a little negative sense, he thought was a neutral sense, 'vox media'

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (7)
As of 2017-06-22 12:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    How many monitors do you use while coding?















    Results (519 votes). Check out past polls.