Ticket #10395: prim_boost.cpp

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