**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

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:

Hi.. Its really very useful.. and could please share more details about how to install it in ubuntu..

Hi try this link for installing the boost C++ libraries in Ubuntu Linux:

http://www.technical-recipes.com/2012/getting-started-with-the-boost-libraries-in-ubuntu-linux/

Hi thank u.. Ill try..

How come the vertex id from the output does not match the input dimacs.txt, for instance, there’s no vertex 0 in dimacs.txt?

Hi Lawrence not sure why Boost chooses to do zero based indexing in spite of the graph node numberings.