Introduction
Some simple walk-throughs on how to use the Boost Graph Library. I find much of the documentation, both online and printed, to be a bit impenetrable. I am sure I am not alone, so I thought it might be worthwhile to post a few examples of its usage that actually compile and work (for me anyway, let me know if you see any problems) as well as being reasonably up to date.
Boost Graph Library is a header-only library that requires no separate compilation.
All that is usually required is to set the location of the additional include directories in your integrated development environment (IDE) and you’re ready to go. In Microsoft Visual Studio for example, just set the location of the Boost Library path in C/C++ > General > Additional Include Directories:
If you are developing in a Linux-based environment and have already installed Boost, there is good chance you don’t need to do anything else.
Shortcuts to examples covered in this boost graph library tutorial are as follows:
1. Creating a directed graph
2. Creating an undirected graph
3. Print edge weights in undirected graphs
4. Finding paths using Dijkstra’s shortest path algorithm
5. Finding minimal spanning trees using Kruskal’s algorithm
6. DIMACS maximum flow problems
The first thing you probably need to learn coding-wise, is the use of the adjacency list to create the graph edge connections. It’s probably worthwhile getting used to making liberal use of typedefs, given that Boost library declarations can end up somewhat lengthy.
To declare an adjacency list for a directed graph for example:
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> DirectedGraph;
Suppose we wish to build the following weighted directed graph:
We can do this by making repeated calls to add_edge to create the graph. The following code listing shows you how, and prints out the result:
#include <boost/graph/adjacency_list.hpp>
#include <iostream>
typedef boost::property<boost::edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, EdgeWeightProperty > DirectedGraph;
typedef boost::graph_traits<DirectedGraph>::edge_iterator edge_iterator;
int main()
{
DirectedGraph g;
boost::add_edge (0, 1, 8, g);
boost::add_edge (0, 3, 18, g);
boost::add_edge (1, 2, 20, g);
boost::add_edge (2, 3, 2, g);
boost::add_edge (3, 1, 1, g);
boost::add_edge (1, 3, 7, g);
boost::add_edge (1, 4, 1, g);
boost::add_edge (4, 5, 6, g);
boost::add_edge (2, 5, 7, g);
std::pair<edge_iterator, edge_iterator> ei = edges(g);
std::cout << "Number of edges = " << num_edges(g) << "\n";
std::cout << "Edge list:\n";
std::copy( ei.first, ei.second,
std::ostream_iterator<boost::adjacency_list<>::edge_descriptor>{
std::cout, "\n"});
std::cout << std::endl;
return 0;
}
Giving the following output:
2. Creating an undirected graph
Consider the following undirected graph:
Which we build in a similar way, but this time stipulating the use of the boost::undirectedS property:
#include <boost/graph/adjacency_list.hpp>
#include <iostream>
typedef boost::property<boost::edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::listS, boost::vecS,boost::undirectedS,boost::no_property,EdgeWeightProperty> UndirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::edge_iterator edge_iterator;
int main()
{
UndirectedGraph g;
boost::add_edge (0, 1, 8, g);
boost::add_edge (0, 3, 18, g);
boost::add_edge (1, 2, 20, g);
boost::add_edge (2, 3, 2, g);
boost::add_edge (1, 3, 7, g);
boost::add_edge (1, 4, 1, g);
boost::add_edge (4, 5, 6, g);
boost::add_edge (2, 5, 7, g);
std::pair<edge_iterator, edge_iterator> ei = edges(g);
std::cout << "Number of edges = " << num_edges(g) << "\n";
std::cout << "Edge list:\n";
for (edge_iterator it = ei.first; it != ei.second; ++it )
{
std::cout << *it << std::endl;
}
std::cout << std::endl;
return 0;
}
Edge list of undirected graph as follows:
3. Print edge weights in undirected graphs
Consider the following spanning tree:
Obtain the mapping between edges and their respective weights by using the boost_property_map:
boost::property_map<UndirectedGraph, boost::edge_weight_t>::type EdgeWeightMap = get(boost::edge_weight_t(), g);
Full code listing:
#include <iostream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
typedef boost::property<boost::edge_weight_t, double> EdgeWeight;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeight> UndirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::edge_iterator edge_iterator;
int main(int, char*[])
{
// 1. Undirected graph - print out the edge weights
UndirectedGraph g;
boost::add_edge(0, 1, 8, g);
boost::add_edge(0, 5, 2, g);
boost::add_edge(5, 6, 1, g);
boost::add_edge(4, 5, 5, g);
boost::add_edge(3, 5, 7, g);
boost::property_map<UndirectedGraph, boost::edge_weight_t>::type EdgeWeightMap = get(boost::edge_weight_t(), g);
std::pair<edge_iterator, edge_iterator> edgePair;
for (edgePair = edges(g); edgePair.first != edgePair.second; ++edgePair.first)
{
std::cout << *edgePair.first << " " << EdgeWeightMap[*edgePair.first] << std::endl;
}
return 0;
}
Giving the following output of the edges and their respective weights:
4. Finding paths using Dijkstra’s shortest path algorithm
The same “dijkstra-example.cpp” as used at the following link:
http://www.boost.org/doc/libs/1_55_0/libs/graph/example/dijkstra-example.cpp
Graphical representation of “dijkstra-example” example graph:
In this demonstration we use the dijkstra_shortest_paths method to obtain not only the shortest path tree, but output the path between a selected source-destination pair as well.
#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>
int main(int, char *[])
{
typedef boost::adjacency_list <boost::listS, boost::vecS, boost::directedS, boost::no_property,
boost::property<boost::edge_weight_t, int> > graph_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
typedef std::pair<int, int> Edge;
const int num_nodes = 5;
enum nodes { A, B, C, D, E };
char name[] = "ABCDE";
Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
};
int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
int num_arcs = sizeof(edge_array) / sizeof(Edge);
// Graph created from the list of edges
graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
// Create property_map from edges to weights
boost::property_map<graph_t, boost::edge_weight_t>::type weightmap = get(boost::edge_weight, g);
// Create vectors to store the predecessors (p) and the distances from the root (d)
std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<int> d(num_vertices(g));
// Create descriptor for the source node
vertex_descriptor s = vertex(A, g);
vertex_descriptor goal = vertex(E, g);
// Evaluate Dijkstra on graph g with source s, predecessor_map p and distance_map d
boost::dijkstra_shortest_paths(g, s,
boost::predecessor_map(&p[0]).distance_map(&d[0]));
//p[] is the predecessor map obtained through dijkstra
//name[] is a vector with the names of the vertices
//s and goal are vertex descriptors
std::vector<boost::graph_traits<graph_t>::vertex_descriptor > path;
boost::graph_traits<graph_t>::vertex_descriptor current = goal;
while(current!=s)
{
path.push_back(current);
current = p[current];
}
path.push_back(s);
// Prints the path obtained in reverse
std::cout << "Path from " << name[s] << " to " << name[goal] << std::endl;
std::vector<boost::graph_traits<graph_t>::vertex_descriptor >::reverse_iterator it;
for (it = path.rbegin(); it != path.rend(); ++it) {
std::cout << name[*it] << " ";
}
std::cout << std::endl;
return EXIT_SUCCESS;
}
Giving the following output showing the shortest path between nodes A and E:
5. Finding minimal spanning trees using Kruskal’s algorithm
Again I take an original example from the boost.org site and make use of it here:
http://www.boost.org/doc/libs/1_55_0/libs/graph/example/kruskal-example.cpp
Graphical representation of example graph:
I remove the Boost workarounds (BOOST_MSVC <= 1300 etc) and the outputting to the .dot file just to keep things more concise. I also remove use of the using boost namespace in my examples, but that’s just a personal preference:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>
#include <fstream>
int main()
{
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef boost::graph_traits <Graph>::edge_descriptor Edge;
typedef boost::graph_traits <Graph>::vertex_descriptor Vertex;
typedef std::pair<int, int> E;
const int num_nodes = 5;
E edge_array[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
E(3, 4), E(4, 0), E(4, 1)
};
int weights[] = { 1, 1, 2, 7, 3, 1, 1, 1 };
std::size_t num_edges = sizeof(edge_array) / sizeof(E);
Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
boost::property_map<Graph, boost::edge_weight_t >::type weight = get(boost::edge_weight, g);
std::vector < Edge > spanning_tree;
boost::kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));
std::cout << "Print the edges in the MST:" << std::endl;
for (std::vector < Edge >::iterator ei = spanning_tree.begin();
ei != spanning_tree.end(); ++ei)
{
std::cout << source(*ei, g)
<< " <--> "
<< target(*ei, g)
<< " with weight of "
<< weight[*ei]
<< std::endl;
}
return 0;
}
Giving the following set of edge-weight pairs making up the minimal spanning tree:
Graphical representation of minimal spanning tree as follows:
6. DIMACS maximum flow problems
DIMACS (Center for Discrete Mathematics and Theoretical Computer Science has formulated ‘challenges’ for problems involving network flows. See this link for more information:
http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm
The problem is to find the maximum possible flow from a given source node to a given sink node. Possible applications include finding the maximum flow of orders through a job shop, the maximum flow of water through a storm sewer system, and the maximum flow of product through a product distribution system.
Example DIMACS file:
c This is a simple example file to demonstrate the DIMACS c input file format for maximum flow problems. The solution c vector is [5,10,5,0,5,5,10,5] with cost at 15. c Problem line (nodes, links) p max 6 8 c source n 1 s c sink n 6 t c Arc descriptor lines (from, to, capacity) a 1 2 5 a 1 3 15 a 2 4 5 a 2 5 5 a 3 4 5 a 3 5 5 a 4 6 15 a 5 6 5 c c End of file
The lines beginning with ‘c’ are comment lines. The problem line begins with the letter ‘p’ and represents the problem designation (max, min etc), the number of edges (8) and the number of vertices (6). Lines beginning with ‘n’ are the node descriptors – node ID and whether the node is a source (‘s’) or a sink (‘t’). Finally the ‘a’ lines are descriptors giving the node interconnections and their weights.
The following graphical representation of the example network flow problem, shows not only the network interconnections and capacities but the flows on the links as well:
Code listing as applied to this problem (you have to supply it your sample DICOM file as described previously):
#include <boost/config.hpp>
#include <iostream>
#include <fstream>
#include <string>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/graph_utility.hpp>
int main()
{
typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS > Traits;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
boost::property<boost::vertex_name_t, std::string >,
boost::property<boost::edge_capacity_t, long,
boost::property<boost::edge_residual_capacity_t, long,
boost::property<boost::edge_reverse_t, Traits::edge_descriptor>>>> Graph;
Graph g;
boost::property_map<Graph, boost::edge_capacity_t>::type
capacity = get(boost::edge_capacity, g);
boost::property_map<Graph, boost::edge_reverse_t>::type rev = get(boost::edge_reverse, g);
boost::property_map<Graph, boost::edge_residual_capacity_t>::type
residual_capacity = get(boost::edge_residual_capacity, g);
Traits::vertex_descriptor s, t;
// Use a DIMACS network flow file as stdin:
std::ifstream is ("dimacs.txt", std::ios::in);
read_dimacs_max_flow(g, capacity, rev, s, t, is);
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
std::vector<default_color_type> color(num_vertices(g));
std::vector<Traits::edge_descriptor> pred(num_vertices(g));
long flow = edmunds_karp_max_flow
(g, s, t, capacity, residual_capacity, rev, &color[0], &pred[0]);
#else
long flow = edmonds_karp_max_flow(g, s, t);
#endif
std::cout << "c The total flow:" << std::endl;
std::cout << "s " << flow << std::endl << std::endl;
std::cout << "c flow values:" << std::endl;
boost::graph_traits<Graph>::vertex_iterator u_iter, u_end;
boost::graph_traits<Graph>::out_edge_iterator ei, e_end;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
if (capacity[*ei] > 0)
std::cout << "f " << *u_iter << " " << target(*ei, g) << " "
<< (capacity[*ei] - residual_capacity[*ei])
<< std::endl;
return EXIT_SUCCESS;
}
Giving the following result:
As anticipated the solution vector of the output variables is [5, 10, 5, 0, 5, 5, 10, 5].
Example DIMACS file “dimacs.txt” downloadable from here:
