Home > Uncategorized > Boost graph library

Boost graph library

Boost is an incredibly large and powerful library and it is not seldom superior to alternatives outside the world of C++. The graph library is one example that really shines. This is one sample usage, assuming access to the csv parser from the previous post.

#include <fstream>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/dijkstra_shortest_paths.hpp>

#include "readcsv.hpp"

 

// http://projecteuler.net/index.php?section=problems&id=81

void Euler81()

{

    using namespace boost;

    using namespace std;

 

    // Load data

    vector<vector<int>> data;

    ReadCsv<int>(ifstream("matrix.txt"), data);

    int size = data.size();

 

    // Build graph

    typedef adjacency_list<listS, vecS, directedS, property<vertex_distance_t, int>, property<edge_weight_t, int>> Graph;

    Graph g(size*size);

    for(int i=0; i<size-1; i++)

    {

        for(int j=0; j<size-1; j++)

        {

            add_edge(i+size*j, i+1+size*j, data[j][i+1], g);

            add_edge(i+size*j, i+size*(j+1), data[j+1][i], g);

        }

    }

    int lastw = data[size-1][size-1];

    int lasti = size*size-1;

    add_edge(lasti-1, lasti, lastw, g);

    add_edge(lasti-size, lasti, lastw, g);

 

    // Optimize

    property_map<Graph, vertex_distance_t>::type d_map = get(vertex_distance, g);

    dijkstra_shortest_paths(g, 0, distance_map(d_map));

 

    // Print result

    cout << "result is " << d_map[num_vertices(g)-1] + data[0][0] << endl;

}

 

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: