The main purpose of this file is to showcase how to use the BGL as cleanly as possible, reducing boilerplate code.

boost_graph_example.cpp

/** @author Romeo Valentin
 *  @date 19.09.2019
 *  @brief Clean usage of boost graph library
 *
 *  The main purpose of this file is to showcase how to use the BGL as cleanly as possible, reducing boilerplate code.
 *  Since I keep coming back to the BGL, I hope this will help me for future reference.
 *
 *  Compile with `g++ -lboost_graph -std=c++14 boost_graph_example.cpp`
 */

#include <iostream>
#include <string>
#include <array>
#include <boost/functional/hash.hpp>  // Necessary for adjacency_list
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>  // Seems to have worse support

#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>

// struct VertexProperty_t { using kind = boost::vertex_property_tag; };
// struct EdgeProperty_t { using kind = boost::edge_property_tag; };
using Name = boost::property<boost::vertex_name_t, std::string>;
using Weight = boost::property<boost::edge_weight_t, double>;

using Graph = boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, Name, Weight>;
// using Graph = boost::adjacency_matrix<boost::directedS, VertexProperty, EdgeProperty>;

namespace std {
// Define std::begin/end for easier looping over the graph using range-for
Graph::vertex_iterator begin(std::pair<Graph::vertex_iterator, Graph::vertex_iterator>& p) {
    return p.first;
}

Graph::vertex_iterator end(std::pair<Graph::vertex_iterator, Graph::vertex_iterator>& p) {
    return p.second;
}

Graph::edge_iterator begin(std::pair<Graph::edge_iterator, Graph::edge_iterator>& p) {
    return p.first;
}

Graph::edge_iterator end(std::pair<Graph::edge_iterator, Graph::edge_iterator>& p) {
    return p.second;
}
}

int main() {
    // Initialize graph
    Graph g(0);  // start with empty graph

    auto net = boost::add_vertex(Name{"Netherlands"}, g);
    auto bel = boost::add_vertex(Name{"Belgium"}, g);
    auto fra = boost::add_vertex(Name{"France"}, g);
    auto ger = boost::add_vertex(Name{"Germany"}, g);
    auto swi = boost::add_vertex(Name{"Switzerland"}, g);
    auto aus = boost::add_vertex(Name{"Austria"}, g);
    auto ita = boost::add_vertex(Name{"Italy"}, g);

    boost::add_edge(net, bel, Weight{15}, g);
    boost::add_edge(bel, net, Weight{ 0}, g);
    boost::add_edge(ger, net, Weight{ 0}, g);
    boost::add_edge(net, ger, Weight{15}, g);
    boost::add_edge(ger, bel, Weight{15}, g);
    boost::add_edge(bel, ger, Weight{15}, g);
    boost::add_edge(fra, bel, Weight{15}, g);
    boost::add_edge(bel, fra, Weight{10}, g);
    boost::add_edge(ger, fra, Weight{10}, g);
    boost::add_edge(fra, ger, Weight{15}, g);
    boost::add_edge(swi, fra, Weight{10}, g);
    boost::add_edge(fra, swi, Weight{ 0}, g);
    boost::add_edge(ita, fra, Weight{10}, g);
    boost::add_edge(fra, ita, Weight{ 0}, g);
    boost::add_edge(aus, ita, Weight{ 0}, g);
    boost::add_edge(ita, aus, Weight{ 0}, g);
    boost::add_edge(ger, aus, Weight{ 0}, g);
    boost::add_edge(aus, ger, Weight{15}, g);
    boost::add_edge(swi, aus, Weight{ 0}, g);
    boost::add_edge(aus, swi, Weight{ 0}, g);
    boost::add_edge(swi, ger, Weight{15}, g);
    boost::add_edge(ger, swi, Weight{ 0}, g);


    /* vector_property_map is vector-based container that can be indexed with verices and map to properties (in this case other vertices) 
     * predecesor_map fills the vector_property map with the predecessor for each node */
    boost::vector_property_map<Graph::vertex_descriptor> directions(boost::num_vertices(g));
    boost::dijkstra_shortest_paths(g, net, boost::predecessor_map(&directions[0]));  // The algorithm will use the edge_weight_t property by default.

    /* D holds is a 2D matrix containing the distance between any two vertices */
    const size_t N = boost::num_vertices(g);
    auto D = std::vector< std::vector<double> > (N, std::vector<double>(N));
    boost::johnson_all_pairs_shortest_paths(g, D);

    /* The following part is just for pretty-printing the results, but showcases how properties can be accessed */
    
    // Print best route from one country to another
    auto p = ita;
    while (p != net) {
        std::cout << boost::get(Name::tag_type(), g, p) << " -> ";
        p = directions[p];
    }
    std::cout << boost::get(Name::tag_type(), g, p) << std::endl;

    // Print all distances between countries in table format
    std::cout << "   ";
    for (auto v : boost::vertices(g)) {
        std::cout << boost::get(Name::tag_type(), g, v).substr(0,2) << " ";
    }
    std::cout << std::endl;
    for (auto row : D) {
        std::cout << boost::get(Name::tag_type(), g, i++).substr(0,2) << " ";
        for (auto col : row) {
            if (col < 10) std::cout << " ";
            std::cout << col << " ";
        }
        std::cout << std::endl;
    }
}