Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
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); } }

Comment on Prims MST Algorithm
Select or Download Code
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?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (6)
As of 2014-11-23 21:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (134 votes), past polls