cluster_dijkstra

dijkstra_time.cpp

#include <boost/config.hpp>
#include <iostream>
#include <fstream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>

using namespace boost;


typedef adjacency_list < listS, vecS, directedS,
        no_property, property < edge_weight_t, int > > graph_t;
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
typedef std::pair<int, int> Edge;

Edge RandomEdge( const int num_nodes )
{
    int n1,n2;
    n1 = n2 = 0;
    while( n1 == n2 )
    {
        n1 = rand() % num_nodes;
        n2 = rand() % num_nodes;
    }
    return Edge( n1, n2 );
}

void RandomGraph(
    Edge * edges,
    int * weights,
    const int num_nodes,
    const int num_arcs
)
{
    for( int k = 0; k < num_arcs; k++ )
    {
        edges[ k ] = RandomEdge( num_nodes );
        weights[k] = rand() % 5;
    }

}

int
main(int, char *[])
{
    // specify size of graph
    const int num_nodes = 20000;
    const int num_arcs = 2 * num_nodes - 1;

    // create random graph of edges and their weights
    Edge edge_array[ num_arcs];
    int weights[ num_arcs];
    RandomGraph(
        edge_array,
        weights,
        num_nodes,
        num_arcs
    );

    // construct boost graph
    graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
    property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
    std::vector<vertex_descriptor> p(num_vertices(g));
    std::vector<int> d(num_vertices(g));

    // starting node
    // ( since graph is random, might as well start at node 0
    vertex_descriptor start = vertex(0, g);

    // length of shortest path from start node to every reachable node
    dijkstra_shortest_paths(g, start,
                            predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, g))).
                            distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, g))));

    // print results
    // commented out for timing trial
//    std::cout << "distances:" << std::endl;
//    graph_traits < graph_t >::vertex_iterator vi, vend;
//    for (boost::tie(vi, vend) = vertices(g); vi != vend; ++vi)
//    {
//        std::cout << "distance(" << *vi << ") = " << d[*vi] << std::endl;
//    }
//    std::cout << std::endl;

    return EXIT_SUCCESS;
}