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

##</code><code>##

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