Getting started with the Boost Graph Library

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:

boostgraph1

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

1. Creating a directed graph

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:

BoostGraph3

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:

boostgraph2

2. Creating an undirected graph

Consider the following undirected graph:

BoostGraph5

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:

BoostGraph4

3. Print edge weights in undirected graphs

Consider the following spanning tree:

BoostGraph6

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:

BoostGraph7

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:

BoostGraph9

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:

BoostGraph8

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:

BoostGraph10

I remove the Boost workarounds (BOOST_MSVC BoostGraph11

Graphical representation of minimal spanning tree as follows:

BoostGraph12

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:

BoostMaxFlow1

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:

BoostMaxFlow2

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:

http://www.technical-recipes.com/Downloads/dimacs.txt

Latest Comments

  1. student 31 July 2016
  2. student 1 August 2016

Leave a Reply