#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>


int main(int argc, char* argv[]){
	using namespace boost;
	typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_distance_t, unsigned>, property < edge_weight_t, unsigned > > Graph;
	typedef std::pair < unsigned, unsigned >E;
 	typedef graph_traits < Graph >::edge_descriptor Edge;

	FILE *fp = fopen(argv[1], "r");
	if(!fp)
	{
		printf("Could not open file\n");
		return 1;
	}

	unsigned nedges, nnodes;
	char buffer[1000];
	while(fgets(buffer, 999,fp) != NULL)
	{
		if(buffer[0] != 'c') break;
	}

	if(strstr(buffer, "p sp") == NULL)
	{
		printf("Malformed file\n");
		return 1;
	}

	sscanf(buffer, "p sp %u %u\n", &nnodes, &nedges);
	printf("graph has %u %u\n", nnodes, nedges);

	while(fgets(buffer, 999,fp) != NULL)
	{
		if(buffer[0] != 'c') break;
	}


	E *edges = (E*)calloc(nedges, sizeof(E));
	unsigned *weights = (unsigned*)calloc(nedges, sizeof(unsigned));
	unsigned src, dst, wt;
	unsigned top_edge = 0;

	while(fscanf(fp, "a %u %u %u\n", &src, &dst, &wt) != EOF)
	{
		edges[top_edge] = E(src-1, dst-1);
		weights[top_edge] = wt;
		top_edge++;
	}


	Graph g(edges, &(edges[top_edge]), weights, nnodes);
	std::vector < graph_traits < Graph >::vertex_descriptor > p(num_vertices(g));
	std::vector<unsigned int> distances(num_vertices(g));
  	std::vector < Edge > spanning_tree;
	property_map < Graph, edge_weight_t >::type weight = get(edge_weight, g);

	prim_minimum_spanning_tree(g, &p[0], root_vertex(1).distance_map(&distances[0]));
	long unsigned int total_weight = 0;

	for (std::size_t i = 0; i != p.size(); ++i)
	{
		if (p[i] != i)
		{
			total_weight += distances[i];
		}	
	}
	printf("Prim total mst weight %lu\n", total_weight);


 	kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

 	total_weight = 0;
  	for(std::vector < Edge >::iterator ei = spanning_tree.begin(); ei != spanning_tree.end(); ++ei)
  	{
		total_weight += weight[*ei];
  	}
	printf("Kruskal total mst weight %lu\n", total_weight);

	return 0;
}