#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(\$root, "X")); \$MST->set_vertex_attribute(\$root, "Y", \$G->get_vertex_attribute(\$root, "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_weight); \$MST->set_vertex_attribute(\$lw_vertex, "X", \$G->get_vertex_attribute(\$lw_vertex, "X")); \$MST->set_vertex_attribute(\$lw_vertex, "Y", \$G->get_vertex_attribute(\$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; }