Boost Graph Library
The Boost Graph library (BGL) is a part of the famous Boost library.
The BGL graph interface and graph components are generic, in the same sense as the Standard Template Library (STL).
As LEMON the BGL also relies on C++ templates and thus is a header-only library.
The list of provided graph algorithms is impressive. Its latest version 1.6.2 was updated in September 2016.
So we want to have a look into the API using the same agenda as in the previous article about the LEMON Graph Library:
- Prerequisites
- Populate a graph
- Setup a shortest path solver
- Solve it, get the cost and the path
1. Prerequisites
For simplicity I put all the code into a single file: main.cpp.
First we have to define a couple of includes in order to use the functionality of the BGL.
// c++ STL #include <vector> #include <map> #include <string> #include <iostream> // BGL #include "boost/graph/adjacency_list.hpp" #include "boost/graph/dijkstra_shortest_paths.hpp"
In my example I use the adjacency_list class of BGL because it’s a common graph representation in Boost.
You can choose between several graph representations with BGL – both directed and undirected ones.
Have a look in the BGL introduction for more information.
In BGL there is a similar concept as in LEMON that allows the store of additional attributes on a graph. You can choose between so called property maps and bundled properties.
As bundled properties are less verbose to write I will use them in my examples.
Now this time I start with a struct that represent an arc of the graph.
struct Arc
{
std::string sourceID;
std::string targetID;
double cost;
};
Next we define the the Graph for the shortest path problem. That’s where the bundled properties come into play.
// typedef of a templated directed adjacency_list
// with std::vector-Containers for nodes and arcs (=vecS)
// the nodes do not have any special properties (-> boost::no_property)
// while the arcs are defined with a bundled property
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS,
boost::no_property,
Arc > graph_t;
So now we can define the graph with our previously defined edge property: the struct Arc.
Now we’re ready to populate the graph.
2. Populate the graph
Basically we populate a graph with the method add_edge().
So we iterate over the arc vector, resolve the external node key to internal integer ids and call add_edge(). Next we add the costs of the arc with the use of the bundled property mechanism in BGL. Here we can access the property using the arc as a key to the graph object. In my opinion this is a really nice feature. Note also that we do not have to populate the nodes first as in LEMON.
//instantiate a directed graph
graph_t g;
//map to store the external node ID and the internal node index.
std::map<std::string, int> nodes = {
std::make_pair("A",0),
std::make_pair("B",1),
std::make_pair("C",2),
std::make_pair("D",3),
std::make_pair("E",4),
std::make_pair("F",5)
};
std::vector<Arc> arcs = { Arc {"A","B",4},
Arc {"A","C",2},
Arc {"B","D",10},
Arc {"B","C",5},
Arc {"C","E",3},
Arc {"E","D",4},
Arc {"D","F",11}
};
//populate graph
for (auto arcsIter = arcs.begin(); arcsIter != arcs.end(); ++arcsIter)
{
int srcID = nodes.at(arcsIter->sourceID);
int tgtID = nodes.at(arcsIter->targetID);
//add_edge() returns std::pair<edge_descriptor,bool>;
auto tmpArc = boost::add_edge(srcID, tgtID, g);
//add costs to arcs
g[tmpArc.first].cost = arcsIter->cost;
}
So now we are ready for #3: setup the shortest path solver.
3. Setup a shortest path solver
First we need a start and an end node, so let’s say we want to know the shortest path from node „A“ to „E“. In BGL nodes of a graph are accessed via so called vertex_descriptors which can be retrieved with the helper method vertex(). Then we have to define a predecessor map and a distance map for the results of the shortest path solver.
//add source & target
vertex_descriptor startV = boost::vertex( nodes.at("A"), g );
vertex_descriptor endV = boost::vertex( nodes.at("E"), g );
//predecessors
// Output for predecessors of each node in the shortest path tree result
std::vector predMap(boost::num_vertices(g));
//distMap
// Output for distances for each node with initial size
// of number of vertices
std::vector distMap(boost::num_vertices(g));
4. Solve it, get the cost and the path
Now we are ready to solve the Dijkstra shortest path problem. As we use bundled properties on the graph for the arc representations we have to tell the solver to use the cost member of the Arc struct for each arc as impedance attribute for the dijkstra algorithm. Additionally one has to pass the predecessor and distance map with another special BGL syntax: the property map style.
//solve shortest path problem
boost::dijkstra_shortest_paths(g, startV,
weight_map(boost::get(&Arc::cost, g)) //arc costs from bundled properties
.predecessor_map(boost::make_iterator_property_map(predMap.begin(),//property map style
boost::get(boost::vertex_index, g)))
.distance_map(boost::make_iterator_property_map(distMap.begin(),//property map style
boost::get(boost::vertex_index, g)))
);
In order to contruct the path and retrieving the cost from the shortest path solver you’ll have to walk in predecessor result map.
std::vector path;
vertex_descriptor current = endV;
while (startV != current)
{
path.push_back(current);
current = predMap[current];
}
// add start as last element (=start node) to path
path.push_back(startV);
Because the predecessor walks from the destination node of a shortest path tree to a start node one must reverse the order of the nodes.
//print out the path with reverse iterator
std::vector<vertex_descriptor>::reverse_iterator rit;
std::cout <<"Path from "<< startV << " to "<< endV << " is: "<< std::endl;
double totalCost = distMap[endV];
for (rit = path.rbegin(); rit != path.rend(); ++rit)
std::cout << *rit << " -> ";
std::cout << std::endl;
std::cout << "Total Cost: "<< totalCost << std::endl;
So what do you think If you compare LEMON to Boost Graph Library?
All the code is available on GitHub.