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 | |

Re: Prims MST Algorithm by Old_Gray_Bear (Bishop) on Apr 22, 2013 at 18:40 UTC |

Back to
Meditations

Comment onPrims MST AlgorithmSelectorDownloadCode