#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; } ##```## 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); } } ```