The Boost Graph Library (BGL)

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.

The 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:

• Creating a directed graph
• Creating an undirected graph
• Print edge weights in undirected graphs
• Finding paths using Dijkstra's shortest path algorithm
• Finding minimal spanning trees using Kruskal's algorithm
• DIMACS maximum flow problems

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:

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;
 }

...

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;
 }

...

Print edge weights in undirected graphs

Consider the following spanning tree:

You may obtain the mapping between edges and their respective weights by using the boost_property_map:

And the full code listing is:

#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;
}

...

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

Here is the 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;
}

Finding minimal spanning trees using Kruskal's algorithm

Again I take an original example from the boost.org site (http://www.boost.org/doc/libs/1_55_0/libs/graph/example/kruskal-example.cpp) and make use of it here.

This is the graphical representation of example graph:

I have removed the Boost workarounds (BOOST_MSVC <= 1300 etc) and the outputting to the .dot file just to keep things more concise. I have also removed 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;
}

...

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;
}

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

Constructing a Graph

In this example we will use the BGL adjacency_list class to demonstrate the main ideas in the BGL interface. The adjacency_list class provides a generalized version of the classic adjacency list data structure. The adjacency_list is a template class with six template parameters, though here we only fill in the first three parameters and use the defaults for the remaining three. The first two template arguments (vecS, vecS) determine the data structure used to represent the out-edges for each vertex in the graph and the data structure used to represent the graph's vertex set (see section Choosing the Edgelist and VertexList for information about the tradeoffs of the different data structures).

The third argument, bidirectionalS, selects a directed graph that provides access to both out and in-edges. The other options for the third argument are directedS which selects a directed graph with only out-edges, and undirectedS which selects an undirected graph.

Once we have the graph type selected, we can create the graph in the figure by declaring a graph object and filling in edges using the add_edge() function of the MutableGraph interface (which adjacency_list implements). We use the array of pairs edge_array merely as a convenient way to explicitly create the edges for this example.

#include <iostream>                  // for std::cout
  #include <utility>                   // for std::pair
#include <algorithm>                 // for std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace boost;

int main(int,char*[])
{
  // create a typedef for the Graph type
  typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;

  // Make convenient labels for the vertices
  enum { A, B, C, D, E, N };
  const int num_vertices = N;
  const char* name = "ABCDE";

  // writing out the edges in the graph
  typedef std::pair<int, int> Edge;
  Edge edge_array[] =
  { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
      Edge(C,E), Edge(B,D), Edge(D,E)
  };
  const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

  // declare a graph object
  Graph g(num_vertices);

  // add the edges to the graph object
  for (int i = 0; i < num_edges; ++i)
    add_edge(edge_array[i].first, edge_array[i].second, g);
  ...
  return 0;
}

Instead of calling the add_edge() function for each edge, we could use the edge iterator constructor of the graph. This is typically more efficient than using add_edge(). Pointers to the edge_array can be viewed as iterators, so we can call the iterator constructor by passing pointers to the beginning and end of the array.

Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices);

Instead of creating a graph with a certain number of vertices to begin with, it is also possible to add and remove vertices with the add_vertex() and remove_vertex() functions, also of the MutableGraph interface.

Accessing the Vertex Set

Now that we have created a graph, we can use the graph interface to access the graph data in different ways. First we can access all of the vertices in the graph using the vertices() function of the VertexListGraph interface. This function returns a std::pair of vertex iterators (the first iterator points to the beginning of the vertices and the second iterator points past the end). Dereferencing a vertex iterator gives a vertex object. The type of the vertex iterator is given by the graph_traits class. Note that different graph classes can have different associated vertex iterator types, which is why we need the graph_traits class. Given some graph type, the graph_traits class will provide access to the vertex_iterator type.

The following example prints out the index for each of the vertices in the graph. All vertex and edge properties, including index, are accessed via property map objects. The property_map class is used to obtain the property map type for a specific property (specified by vertex_index_t, one of the BGL predefined properties) and function call get(vertex_index, g) returns the actual property map object.

// ...
  int main(int,char*[])
  {
    // ...

    typedef graph_traits<Graph>::vertex_descriptor Vertex;

    // get the property map for vertex indices
    typedef property_map<Graph, vertex_index_t>::type IndexMap;
    IndexMap index = get(vertex_index, g);

    std::cout << "vertices(g) = ";
    typedef graph_traits<Graph>::vertex_iterator vertex_iter;
    std::pair<vertex_iter, vertex_iter> vp;
    for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
      Vertex v = *vp.first;
      std::cout << index[v] <<  " ";
    }
    std::cout << std::endl;
    // ...
    return 0;
  }

The output is:

vertices(g) = 0 1 2 3 4

Accessing the Edge Set

The set of edges for a graph can be accessed with the edges() function of the EdgeListGraph interface. Similar to the vertices() function, this returns a pair of iterators, but in this case the iterators are edge iterators. Dereferencing an edge iterator gives an edge object. The source() and target() functions return the two vertices that are connected by the edge. Instead of explicitly creating a std::pair for the iterators, this time we will use the tie() helper function. This handy function can be used to assign the parts of a std::pair into two separate variables, in this case ei and ei_end. This is usually more convenient than creating a std::pair and is our method of choice for the BGL

// ...
  int main(int,char*[])
  {
    // ...
    std::cout << "edges(g) = ";
    graph_traits<Graph>::edge_iterator ei, ei_end;
    for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        std::cout << "(" << index[source(*ei, g)]
                  << "," << index[target(*ei, g)] << ") ";
    std::cout << std::endl;
    // ...
    return 0;
  }

The output is:

edges(g) = (0,1) (0,3) (2,0) (3,2) (2,4) (1,3) (3,4)

The Adjacency Structure

In the next few examples we will explore the adjacency structure of the graph from the point of view of a particular vertex. We will look at the vertices' in-edges, out-edges, and its adjacent vertices. We will encapsulate this in an exercise_vertex function, and apply it to each vertex in the graph. To demonstrate the STL-interoperability of BGL, we will use the STL for_each() function to iterate through the vertices and apply the function.

//...
  int main(int,char*[])
  {
    //...
    std::for_each(vertices(g).first, vertices(g).second,
                  exercise_vertex<Graph>(g));
    return 0;
  }

We use a functor for exercise_vertex instead of just a function because the graph object will be needed when we access information about each vertex; using a functor gives us a place to keep a reference to the graph object during the execution of the std::for_each(). Also we template the functor on the graph type so that it is reusable with different graph classes. Here is the start of the exercise_vertex functor:

template <class Graph> struct exercise_vertex {
    exercise_vertex(Graph& g_) : g(g_) {}
    //...
    Graph& g;
  };

Vertex Descriptors

The first thing we need to know in order to write the operator() method of the functor is the type for the vertex objects of the graph. The vertex type will be the parameter to the operator() method. To be precise, we do not deal with actual vertex objects, but rather with vertex descriptors. Many graph representations (such as adjacency lists) do not store actual vertex objects, while others do (e.g., pointer-linked graphs). This difference is hidden underneath the black-box of the vertex descriptor object. The vertex descriptor is something provided by each graph type that can be used to access information about the graph via the out_edges(), in_edges(), adjacent_vertices(), and property map functions that are described in the following sections. The vertex_descriptor type is obtained through the graph_traits class. The typename keyword used below is necessary because the type on the left hand side of the scope :: operator (the graph_traits<Graph> type) is dependent on a template parameter (the Graph type). Here is how we define the functor's apply method:

  template <class Graph> struct exercise_vertex {
    //...
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    void operator()(const Vertex& v) const
    {
      //...
    }
    //...
  };

Out-Edges, In-Edges, and Edge Descriptors

The out-edges of a vertex are accessed with the out_edges() function of the IncidenceGraph interface. The out_edges() function takes two arguments: the first argument is the vertex and the second is the graph object. The function returns a pair of iterators which provide access to all of the out-edges of a vertex (similar to how the vertices() function returned a pair of iterators). The iterators are called out-edge iterators and dereferencing one of these iterators gives an edge descriptor object. An edge descriptor plays the same kind of role as the vertex descriptor object, it is a black box provided by the graph type. The following code snippet prints the source-target pairs for each out-edge of vertex v.

template <class Graph> struct exercise_vertex {
    //...
    void operator()(const Vertex& v) const
    {
      typedef graph_traits<Graph> GraphTraits;
      typename property_map<Graph, vertex_index_t>::type
        index = get(vertex_index, g);

      std::cout << "out-edges: ";
      typename GraphTraits::out_edge_iterator out_i, out_end;
      typename GraphTraits::edge_descriptor e;
      for (tie(out_i, out_end) = out_edges(v, g);
           out_i != out_end; ++out_i) {
        e = *out_i;
        Vertex src = source(e, g), targ = target(e, g);
        std::cout << "(" << index[src] << ","
                  << index[targ] << ") ";
      }
      std::cout << std::endl;
      //...
    }
    //...
  };

For vertex 0 the output is:

out-edges: (0,1) (0,2) (0,3) (0,4)

The in_edges() function of the BidirectionalGraph interface provides access to all the in-edges of a vertex through in-edge iterators. The in_edges() function is only available for the adjacency_list if bidirectionalS is supplied for the Directed template parameter. There is an extra cost in space when bidirectionalS is specified instead of directedS.

template <class Graph> struct exercise_vertex {
    //...
    void operator()(const Vertex& v) const
    {
      //...
      std::cout << "in-edges: ";
      typedef typename graph_traits<Graph> GraphTraits;
      typename GraphTraits::in_edge_iterator in_i, in_end;
      for (tie(in_i, in_end) = in_edges(v,g);
           in_i != in_end; ++in_i) {
        e = *in_i;
        Vertex src = source(e, g), targ = target(e, g);
        std::cout << "(" << index[src] << "," << index[targ] << ") ";
      }
      std::cout << std::endl;
      //...
    }
    //...
  };

For vertex 0 the output is:

in-edges: (2,0) (3,0) (4,0)

Adjacent Vertices

Given the out-edges of a vertex, the target vertices of these edges are adjacent to the source vertex. Sometimes an algorithm does not need to look at the edges of the graph and only cares about the vertices. Therefore the graph interface also includes the adjacent_vertices() function of the AdjacencyGraph interface which provides direct access to the adjacent vertices. This function returns a pair of adjacency iterators. Dereferencing an adjacency iterator gives a vertex descriptor for an adjacent vertex.

  template <class Graph> struct exercise_vertex {
    //...
    void operator()(Vertex v) const
    {
      //...
      std::cout << "adjacent vertices: ";
      typename graph_traits<Graph>::adjacency_iterator ai;
      typename graph_traits<Graph>::adjacency_iterator ai_end;
      for (tie(ai, ai_end) = adjacent_vertices(v, g);
           ai != ai_end; ++ai)
        std::cout << index[*ai] <<  " ";
      std::cout << std::endl;
    }
    //...
  };

For vertex 4 the output is:

adjacent vertices: 0 1

Adding Some Color to your Graph

BGL attempts to be as flexible as possible in terms of accommodating how properties are attached to a graph. For instance, a property such as edge weight may need to be used throughout a graph object's lifespan and therefore it would be convenient to have the graph object also manage the property storage. On the other hand, a property like vertex color may only be needed for the duration of a single algorithm, and it would be better to have the property stored separately from the graph object. The first kind of property is called an internally stored property while the second kind is called an externally stored property. BGL uses a uniform mechanism to access both kinds of properties inside its graph algorithms called the property map interface, described in Property Map Concepts. In addition, the PropertyGraph concept defines the interface for obtaining a property map object for an internally stored property.

The BGL adjacency_list class allows users to specify internally stored properties through plug-in template parameters of the graph class. How to do this is discussed in detail in Internal Properties. Externally stored properties can be created in many different ways, although they are ultimately passed as separate arguments to the graph algorithms. One straightforward way to store properties is to create an array indexed by vertex or edge index. In the adjacency_list with vecS specified for the VertexList template parameter, vertices are automatically assigned indices, which can be accessed via the property map for the vertex_index_t. Edges are not automatically assigned indices. However the property mechanism can be used to attach indices to the edges which can be used to index into other externally stored properties.

In the following example, we construct a graph and apply dijkstra_shortest_paths(). The complete source code for the example is in examples/dijkstra-example.cpp. Dijkstra's algorithm computes the shortest distance from the starting vertex to every other vertex in the graph.

Dijkstra's algorithm requires that a weight property is associated with each edge and a distance property with each vertex. Here we use an internal property for the weight and an external property for the distance. For the weight property we use the property class and specify int as the type used to represent weight values and edge_weight_t for the property tag (which is one of the BGL predefined property tags). The weight property is then used as a template argument for adjacency_list.

The listS and vecS types are selectors that determine the data structure used inside the adjacency_list (see Choosing the Edgelist and VertexList). The directedS type specifies that the graph should be directed (versus undirected). The following code shows the specification of the graph type and then the initialization of the graph. The edges and weights are passed to the graph constructor in the form of iterators (a pointer qualifies as a RandomAccessIterator)

typedef adjacency_list<listS, vecS, directedS,
                         no_property, property<edge_weight_t, int> > Graph;
  typedef graph_traits<Graph>::vertex_descriptor Vertex;
  typedef std::pair<int,int> E;

  const int num_nodes = 5;
  E edges[] = { E(0,2),
                E(1,1), E(1,3), E(1,4),
                E(2,1), E(2,3),
                E(3,4),
                E(4,0), E(4,1) };
  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1};

  Graph G(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes);

For the external distance property we will use a std::vector for storage. BGL algorithms treat random access iterators as property maps, so we can just pass the beginning iterator of the distance vector to Dijkstra's algorithm. Continuing the above example, the following code shows the creation of the distance vector, the call to Dijkstra's algorithm (implicitly using the internal edge weight property), and then the output of the results.

// vector for storing distance property
  std::vector<int> d(num_vertices(G));

  // get the first vertex
  Vertex s = *(vertices(G).first);
  // invoke variant 2 of Dijkstra's algorithm
  dijkstra_shortest_paths(G, s, distance_map(&d[0]));

  std::cout << "distances from start vertex:" << std::endl;
  graph_traits<Graph>::vertex_iterator vi;
  for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
    std::cout << "distance(" << index(*vi) << ") = "
              << d[*vi] << std::endl;
  std::cout << std::endl;

The output being:

 distances from start vertex:
  distance(0) = 0
  distance(1) = 6
  distance(2) = 1
  distance(3) = 4
  distance(4) = 5

Extending Algorithms with Visitors

Often times an algorithm in a library almost does what you need, but not quite. For example, in the previous section we used Dijkstra's algorithm to calculate the shortest distances to each vertex, but perhaps we also wanted to record the tree of shortest paths. One way to do this is to record the predecessor (parent) for each node in the shortest-paths tree.

It would be nice if we could avoid rewriting Dijkstra's algorithm, and just add that little bit extra needed to record the predecessors. In the STL, this kind of extensibility is provided by functors, which are optional parameters to each algorithm. In the BGL this role is fulfilled by visitors.

A visitor is like a functor, but instead of having just one apply method, it has several. Each of these methods get invoked at certain well-defined points within the algorithm. The visitor methods are explained in detail in Visitor Concepts. The BGL provides a number of visitors for some common tasks including a predecessor recording visitor. The user is encouraged to write his or her own visitors as a way of extending the BGL. Here we will take a quick look at the implementation and use of the predecessor recorder. Since we will be using the dijkstra_shortest_paths() algorithm, the visitor we create must be a Dijkstra Visitor.

The functionality of the record_predecessors visitor is separated into two parts. For the storage and access of the predecessor property, we will use a property map. The predecessor visitor will then only be responsible for what parent to record. To implement this, we create a record_predecessors class and template it on the predecessor property map PredecessorMap. Since this visitor will only be filling in one of the visitor methods, we will inherit from dijkstra_visitor, which will provide empty methods for the rest. The constructor of the predecessor_recorder will take the property map object and save it away in a data member.

template <class PredecessorMap>
  class record_predecessors : public dijkstra_visitor<>
  {
  public:
    record_predecessors(PredecessorMap p)
      : m_predecessor(p) { }

    template <class Edge, class Graph>
    void edge_relaxed(Edge e, Graph& g) {
      // set the parent of the target(e) to source(e)
      put(m_predecessor, target(e, g), source(e, g));
    }
  protected:
    PredecessorMap m_predecessor;
  };

The job of recording the predecessors is quite simple. When Dijkstra's algorithm relaxes an edge (potentially adding it to the shortest-paths tree) we record the source vertex as the predecessor of the target vertex. Later, if the edge is relaxed again the predecessor property will be overwritten by the new predecessor. Here we use the put() function associated with the property map to record the predecessor. The edge_filter of the visitor tells the algorithm when to invoke the explore() method. In this case we only want to be notified about edges in the shortest-paths tree so we specify tree_edge_tag.

As a finishing touch, we create a helper function to make it more convenient to create predecessor visitors. All BGL visitors have a helper function like this.

template <class PredecessorMap>
  record_predecessors<PredecessorMap>
  make_predecessor_recorder(PredecessorMap p) {
    return record_predecessors<PredecessorMap>(p);
  }

We are now ready to use the record_predecessors in Dijkstra's algorithm. Luckily, BGL's Dijkstra's algorithm is already equipped to handle visitors, so we just pass in our new visitor. In this example we only need to use one visitor, but the BGL is also equipped to handle the use of multiple visitors in the same algorithm (see Visitor ConceptsVisitor Concepts).

  using std::vector;
  using std::cout;
  using std::endl;
  vector<Vertex> p(num_vertices(G), graph_traits<G>::null_vertex()); //the predecessor array
  dijkstra_shortest_paths(G, s, distance_map(&d[0]).
                          visitor(make_predecessor_recorder(&p[0])));

  cout << "parents in the tree of shortest paths:" << endl;
  for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
    cout << "parent(" << *vi;
    if (p[*vi] == graph_traits<G>::null_vertex())
      cout << ") = no parent" << endl;
    else
      cout << ") = " << p[*vi] << endl;
  }

The output is:

parents in the tree of shortest paths:
  parent(0) = no parent
  parent(1) = 4
  parent(2) = 0
  parent(3) = 2
  parent(4) = 3

Bundled Properties

Note Bundled properties will only work properly on compilers that support class template partial specialization.

Class templates adjacency_list and adjacency_matrix support the introduction of named properties via internal properties. However, this method is cumbersome in many uses, where it would be more intuitive to just specify a structure or class that contains internal properties for edges or vertices. Bundled properties allow one to use adjacency_list and adjacency_matrix in this manner, providing a simple way to introduce and access any number of internal properties for vertices and edges.

One can introduce bundled properties into an either graph type by providing a user-defined class type for the VertexProperties or EdgeProperties template arguments. The user-defined class may alternatively be placed at the end of a property list, replacing the (implicit) boost::no_property argument.

struct City
{
  string name;
  int population;
  vector<int> zipcodes;
};

struct Highway
{
  string name;
  double miles;
  int speed_limit;
  int lanes;
  bool divided;
};

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City, Highway> Map;
      

Map map; // load the map
Map::vertex_descriptor v = *vertices(map).first;
map[v].name = "Troy";
map[v].population = 49170;
map[v].zipcodes.push_back(12180);
Map::edge_descriptor e = *out_edges(v, map).first;
map[e].name = "I-87";
map[e].miles = 10;
map[e].speed_limit = 65;
map[e].lanes = 4;
map[e].divided = true;

vector<double> distances(num_vertices(map));
dijkstra_shortest_paths(map, from,
      weight_map(get(edge_length, map)),
      distance_map(make_iterator_property_map(distances.begin(),
                                               get(vertex_index, map))));

vector<double> distances(num_vertices(map));
dijkstra_shortest_paths(map, from,
      weight_map(get(&Highway::miles, map)),
      distance_map(make_iterator_property_map(distances.begin(),
                                               get(vertex_index, map))));

Which Graph Class To Use

There are several BGL graph classes from which to choose. Since BGL algorithms are generic, they can also be used with any conforming user-defined graph class, but in this section we will restrict our discussion to BGL graph classes.

The principle BGL graph classes are the adjacency_list and adjacency_matrix classes. The adjacency list class is a good choice for most situations, particularly for representing sparse graphs. The file-dependencies graph has only a few edges per vertex, so it is sparse. The adjacency matrix class is a good choice for representing dense graphs, but a very bad choice for sparse graphs, unless a sparse matrix is used.

In this introductory section we shall be using the adjacency_list class exclusively. However, most of what is presented here will also apply directly to the adjacency_matrix class because its interface is almost identical to that of the adjacency_list.

Here we use the same variant of adjacency list as was used in §1.4.1.

typedef adjacency list<
  listS, // Store out-edges of each vertex in a std::list
  vecS,  // Store vertex set in a std::vector
  directedS // The file dependency graph is directed
            > file_dep_graph; // for file dependency graph, as introduced elsewhere

Constructing a Graph Using Edge Iterators

we have shown how the add_vertex() and add_edge() functions can be used to create a graph. Those functions add vertices and edges one at a time, but in many cases one would like to add them all at once. To meet this need the adjacency_list graph class has a constructor that takes two iterators that define a range of edges. The edge iterators can be any InputIterator that dereference to a std::pair of integers (i, j) that represent an edge in the graph. The two integers i and j represent vertices where 0 ≤ i < |V | and 0 ≤ j < |V |. The n and m parameters say how many vertices and edges will be in the graph. These parameters are optional, but providing them improves the speed of graph construction. The graph properties parameter p is attached to the graph object. The function prototype for the constructor that uses edge iterators is as follows:

template <var class='type'name EdgeIterator>
adjacency list(EdgeIterator first, EdgeIterator last,
               vertices_size_type n = 0, edges_size_type m = 0,
               const GraphProperties& p = GraphProperties())

The following code demonstrates the use of the edge iterator constructor to create a graph. The std::istream iterator is used to make an input iterator that reads the edges in from the file. The file contains the number of vertices in the graph, followed by pairs of numbers that specify the edges. The second default-constructed input iterator is a placeholder for the end of the input. The std::istream iterator is passed directly into the constructor for the graph.

std::ifstream file_in("makefile-dependencies.dat");
typedef graph_traits<file_dep_graph>::vertices_size_type size_type;
size_type n_vertices;
file_in >> n_vertices; // read in number of vertices
std::istream iterator<std::pair<size_type, size_type> > input_begin(file_in), input_end;
file_dep_graph g(input_begin, input_end, n_vertices);

Since the value type of the std::istream iterator is std::pair, an input operator needs to be defined for std::pair.

namespace std {
  template <var class='type'name T>
  std::istream& operator>>(std::istream& in, std::pair<T,T>& p) {
    in >> p.first >> p.second;
    return in;
  }
}

Compilation Order

The first question that we address is that of specifying an order in which to build all of the targets. The primary consideration here is ensuring that before building a given target, all the targets that it depends on are already built.

The Base Graph Interface

The Graph concept contains a few requirements that are common to all the graph concepts. These include some associated types for vertex_descriptor, edge_descriptor, etc. One should note that a model of Graph is not required to be a model of Assignable, so algorithms should pass graph objects by reference.

template <class G>
  struct GraphConcept
  {
    typedef typename boost::graph_traits<G>::vertex_descriptor vertex_descriptor;
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    typedef typename boost::graph_traits<G>::directed_category directed_category;
    typedef typename boost::graph_traits<G>::edge_parallel_category edge_parallel_category;
    typedef typename boost::graph_traits<G>::traversal_category traversal_category;

    void constraints() {
      function_requires< DefaultConstructibleConcept<vertex_descriptor> >();
      function_requires< EqualityComparableConcept<vertex_descriptor> >();
      function_requires< AssignableConcept<vertex_descriptor> >();
      function_requires< DefaultConstructibleConcept<edge_descriptor> >();
      function_requires< EqualityComparableConcept<edge_descriptor> >();
      function_requires< AssignableConcept<edge_descriptor> >();
    }
    G g;
  };

Refinements of the Graph Interface

The refinements of the graph are:

IncidenceGraph

The IncidenceGraph concept provides an interface for efficient access to the out-edges of each vertex in the graph.

The IncidenceGraph interface is further refined by BidirectionalGraph.

BidirectionalGraph

The BidirectionalGraph concept refines IncidenceGraph and adds the requirement for efficient access to the in-edges of each vertex.

AdjacencyGraph

The AdjacencyGraph concept provides and interface for efficient access of the adjacent vertices to a vertex in a graph. This is quite similar to the IncidenceGraph concept (the target of an out-edge is an adjacent vertex), though...

EdgeListGraph

The EdgeListGraph concept refines the Graph concept, and adds the requirement for efficient access to all the edges in the graph.

AdjacencyMatrix

The AdjacencyMatrix concept refines Graph concept and adds the requirement for efficient access to any edge in the graph given the source and target vertices.

VertexListGraph

The VertexListGraph concept refines the Graph concept, and adds the requirement for efficient traversal of all the vertices in the graph.

The IncidenceGraph Interface

The IncidenceGraph concept provides an interface for efficient access to the out-edges of each vertex in the graph.

Its associated types:

boost::graph_traits<G>::traversal_category

This tag type must be convertible to incidence_graph_tag.

boost::graph_traits<G>::out_edge_iterator

An out-edge iterator for a vertex v provides access to the out-edges of the vertex. As such, the value type of an out-edge iterator is the edge descriptor type of its graph. An out-edge iterator must meet the requirements of MultiPassInputIterator.

boost::graph_traits<G>::degree_size_type

The unsigned integral type used for representing the number out-edges or incident edges of a vertex.

Valid expressions (global functions) are:

source(e, g)

Returns the vertex descriptor for u of the edge (u,v) represented by e.

Return type: vertex_descriptor

target(e, g)

Returns the vertex descriptor for v of the edge (u,v) represented by e.

Return type: vertex_descriptor

out_edges(u, g)

Returns an iterator-range providing access to the out-edges (for directed graphs) or incident edges (for undirected graphs) of vertex u in graph g. The source vertex of an edge obtained via an out edge iterator is guaranteed (for both directed and undirected graphs) to be the vertex u used in the call to out_edges(u, g) and the target vertex must be a vertex adjacent to u.

Return type: std::pair<out_edge_iterator, out_edge_iterator>

out_degree(u, g)

Returns the number of out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex u in graph g.

Return type: degree_size_type

The BidirectionalGraph Interface

The BidirectionalGraph concept refines IncidenceGraph and adds the requirement for efficient access to the in-edges of each vertex. This concept is separated from IncidenceGraph because for directed graphs efficient access to in-edges typically requires more storage space, and many algorithms do not require access to in-edges. For undirected graphs this is not an issue, since the in_edges() and out_edges() functions are the same, they both return the edges incident to the vertex.

Its associated types:

boost::graph_traits<G>::traversal_category

This tag type must be convertible to bidirectional_graph_tag.

boost::graph_traits<G>::in_edge_iterator

An in-edge iterator for a vertex v provides access to the in-edges of v. As such, the value type of an in-edge iterator is the edge descriptor type of its graph. An in-edge iterator must meet the requirements of MultiPassInputIterator.

Valid expressions (global functions) are:

in_edges(v, g)

Returns an iterator-range providing access to the in-edges (for directed graphs) or incident edges (for undirected graphs) of vertex v in graph g. For both directed and undirected graphs, the target of an out-edge is required to be vertex v and the source is required to be a vertex that is adjacent to v.

Return type: std::pair<in_edge_iterator, in_edge_iterator>

in_degree(v, g)

Returns the number of in-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v in graph g.

Return type: degree_size_type

degree(v, g)

Returns the number of in-edges plus out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v in graph g.

Return type: degree_size_type

template <class G>
  struct BidirectionalGraphConcept
  {
    typedef typename boost::graph_traits<G>::in_edge_iterator
      in_edge_iterator;
    void constraints() {
      BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<G> ));
      BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<in_edge_iterator> ));

      p = in_edges(v, g);
      e = *p.first;
      const_constraints(g);
    }
    void const_constraints(const G& g) {
      p = in_edges(v, g);
      e = *p.first;
    }
    std::pair<in_edge_iterator, in_edge_iterator> p;
    typename boost::graph_traits<G>::vertex_descriptor v;
    typename boost::graph_traits<G>::edge_descriptor e;
    G g;
  };

The AdjacencyGraph Interface

The AdjacencyGraph concept provides and interface for efficient access of the adjacent vertices to a vertex in a graph. This is quite similar to the IncidenceGraph concept (the target of an out-edge is an adjacent vertex). Both concepts are provided because in some contexts there is only concern for the vertices, whereas in other contexts the edges are also important.

Its associated types:

boost::graph_traits<G>::traversal_category

This tag type must be convertible to adjacency_graph_tag.

boost::graph_traits<G>::adjacency_iterator

An adjacency iterator for a vertex v provides access to the vertices adjacent to v. As such, the value type of an adjacency iterator is the vertex descriptor type of its graph. An adjacency iterator must meet the requirements of MultiPassInputIterator.

Valid expressions (global functions) are:

adjacent_vertices(v, g)

Returns an iterator-range providing access to the vertices adjacent to vertex v in graph g.

Return type: std::pair<adjacency_iterator, adjacency_iterator>

The EdgeListGraph Interface

The EdgeListGraph concept refines the Graph concept, and adds the requirement for efficient access to all the edges in the graph.

Its associated types:

boost::graph_traits<G>::traversal_category

This tag type must be convertible to edge_list_graph_tag.

boost::graph_traits<G>::edge_iterator

An edge iterator (obtained via edges(g)) provides access to all of the edges in a graph. An edge iterator type must meet the requirements of MultiPassInputIterator. The value type of the edge iterator must be the same as the edge descriptor of the graph.

boost::graph_traits<G>::edges_size_type

The unsigned integer type used to represent the number of edges in the graph.

Valid expressions (global functions) are:

edges(g)

Returns an iterator-range providing access to all the edges in the graph g.

Return type: std::pair<edge_iterator, edge_iterator></dd>

num_edges(g)

Returns the number of edges in the graph g.

Return type: edges_size_type

source(e, g)

Returns the vertex descriptor for u of the edge (u,v) represented by e.

Return type: vertex_descriptor

target(e, g)

Returns the vertex descriptor for v of the edge (u,v) represented by e.

Return type: vertex_descriptor

template <class G>
  struct EdgeListGraphConcept
  {
    typedef typename boost::graph_traits<G>::edge_iterator
      edge_iterator;
    void constraints() {
      BOOST_CONCEPT_ASSERT(( GraphConcept<G> ));
      BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<edge_iterator> ));

      p = edges(g);
      E = num_edges(g);
      e = *p.first;
      u = source(e, g);
      v = target(e, g);
      const_constraints(g);
    }
    void const_constraints(const G& g) {
      p = edges(g);
      E = num_edges(g);
      e = *p.first;
      u = source(e, g);
      v = target(e, g);
    }
    std::pair<edge_iterator,edge_iterator> p;
    typename boost::graph_traits<G>::vertex_descriptor u, v;
    typename boost::graph_traits<G>::edge_descriptor e;
    typename boost::graph_traits<G>::edges_size_type E;
    G g;
  };

The AdjacencyMatrix Interface

The AdjacencyMatrix concept refines Graph concept and adds the requirement for efficient access to any edge in the graph given the source and target vertices. No Boost Graph Library algorithms currently use this concept. However there are algorithms not yet implemented such as Floyd-Warshall that would require this concept.

Its associated types:

boost::graph_traits<G>::traversal_category

This tag type must be convertible to adjacency_matrix_tag.

Valid expressions (global functions) are:

edge(u, v, g)

Returns a pair consisting of a flag saying whether there exists an edge between u and v in graph g, and consisting of the edge descriptor if the edge was found.

Return type: std::pair<edge_descriptor, bool>

template <class G>
  struct AdjacencyMatrix
  {
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    void constraints() {
      p = edge(u, v, g);
    }
    typename boost::graph_traits<G>::vertex_descriptor u, v;
    std::pair<bool, edge_descriptor> p;
    G g;
  };

The VertexListGraph Interface

The VertexListGraph concept refines the Graph concept, and adds the requirement for efficient traversal of all the vertices in the graph.

Its associated types:

boost::graph_traits<G>::traversal_category

This tag type must be convertible to vertex_list_graph_tag.

boost::graph_traits<G>::vertex_iterator

A vertex iterator (obtained via vertices(g)) provides access to all of the vertices in a graph. A vertex iterator type must meet the requirements of MultiPassInputIterator. The value type of the vertex iterator must be the vertex descriptor of the graph.

boost::graph_traits<G>::vertices_size_type

The unsigned integer type used to represent the number of vertices in the graph.

Valid expressions (global functions) are:

vertices(g)

Returns an iterator-range providing access to all the vertices in the graph g.

Return type: std::pair<vertex_iterator, vertex_iterator>

num_vertices(g)

Returns the number of vertices in the graph g.

Return type: vertices_size_type

MutableGraph

A MutableGraph is a graph that can be changed via the addition or removal of edges and vertices.

Refinement of

Graph

template <class G>
  struct MutableGraphConcept
  {
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    void constraints() {
      v = add_vertex(g);
      clear_vertex(v, g);
      remove_vertex(v, g);
      e_b = add_edge(u, v, g);
      remove_edge(u, v, g);
      remove_edge(e, g);
    }
    G g;
    edge_descriptor e;
    std::pair<edge_descriptor, bool> e_b;
    typename boost::graph_traits<G>::vertex_descriptor u, v;
    typename boost::graph_traits<G>::out_edge_iterator iter;
  };

  template <class edge_descriptor>
  struct dummy_edge_predicate {
    bool operator()(const edge_descriptor& e) const {
      return false;
    }
  };

  template <class G>
  struct MutableIncidenceGraphConcept
  {
    void constraints() {
      function_requires< MutableGraph<G> >();
      remove_edge(iter, g);
      remove_out_edge_if(u, p, g);
    }
    G g;
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    dummy_edge_predicate<edge_descriptor> p;
    typename boost::graph_traits<G>::vertex_descriptor u;
    typename boost::graph_traits<G>::out_edge_iterator iter;
  };

  template <class G>
  struct MutableBidirectionalGraphConcept
  {
    void constraints() {
      function_requires< MutableIncidenceGraph<G> >();
      remove_in_edge_if(u, p, g);
    }
    G g;
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    dummy_edge_predicate<edge_descriptor> p;
    typename boost::graph_traits<G>::vertex_descriptor u;
  };

  template <class G>
  struct MutableEdgeListGraphConcept
  {
    void constraints() {
      function_requires< MutableGraph<G> >();
      remove_edge_if(p, g);
    }
    G g;
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    dummy_edge_predicate<edge_descriptor> p;
  };

Vertex and Edge Descriptors

In the BGL, vertices and edges are manipulated through opaque handles called vertex descriptors and edge descriptors. Different graph types may use different types for their descriptors. For example, some graph types may use integers, whereas other graphs may use pointers. The descriptor types for a graph type are always accessible through the graph traits class.

Vertex descriptors have very basic functionality. By themselves they can only be default constructed, copied, and compared for equality. Edge descriptors are similar, although they also provide access to the associated source and target vertex. The following function template shows an implementation a generic function that determines if an edge is a self-loop:

template <var class='type'name Graph>
bool is self loop(typename graph traits<Graph>::edge descriptor e, const Graph& g) {
  typename graph traits<Graph>::vertex descriptor u, v;
  u = source(e, g);
  v = target(e, g);
  return u == v;
}

Concept Checking

An important aspect of using a generic library is using appropriate classes as template arguments to algorithms (using classes that model the concepts specified by the requirements of the algorithm). If an improper class is used, the compiler will emit error messages, but deciphering these messages can present a significant hurdle to the user of a template library. The compiler may produce literally pages of difficult-to-decipher error messages for even a small error.

template <var class='type'name T>
struct LessThanComparableConcept {
  void constraints() {
    (bool) (a < b);
  };
  T a, b;
};

#include <boost/concept_check.hpp>
template <var class='type'name Iterator>
void safe_sort(Iterator first, Iterator last) {
  typedef typename std::iterator_traits<Iterator>::value_type T;
  function_requires< LessThanComparableConcept<T> >();
  // other requirements . . .
  std::sort(first, last);
};

#include <algorithm>
#include <boost/concept_archetype.hpp>
int main() {
  using namespace boost;
  typedef less_than_comparable_archetype<> T;
  random access_iterator_archetype<T> ri;
  std::sort(ri, ri);
}

null archetype(const null archetype<int> &) is private

template <var class='type'name Base = null_archetype<> >
class assignable_archetype : public Base {
  typedef assignable_archetype self ;
public:
  assignable archetype(const self &) {}
  self & operator=(const self &) { return *this; }
};

BFS Visitor

This concept defines the visitor interface for breadth_first_search(). Users can define a class with the BFS Visitor interface and pass and object of the class to breadth_first_search(), thereby augmenting the actions taken during the graph search.

Refinement of

Copy Constructible (copying a visitor should be a lightweight operation).

Notation

V: A type that is a model of BFS Visitor.
vis: An object of type V.
G: A type that is a model of Graph.
g: An object of type G.
e: An object of type boost::graph_traits<G>::edge_descriptor.
s,u: An object of type boost::graph_traits<G>::vertex_descriptor.

Valid Expressions

Initialize Vertex

vis.initialize_vertex(s, g)

return type: void

This is invoked on every vertex of the graph before the start of the graph search.

Discover Vertex

vis.discover_vertex(u, g)

return type: void

This is invoked when a vertex is encountered for the first time.

Examine Vertex

vis.examine_vertex(u, g)

return type: void

This is invoked on a vertex as it is popped from the queue. This happens immediately before examine_edge() is invoked on each of the out-edges of vertex u.

Examine Edge

vis.examine_edge(e, g)

return type: void

This is invoked on every out-edge of each vertex after it is discovered.

Tree Edge

vis.tree_edge(e, g)

return type: void

This is invoked on each edge as it becomes a member of the edges that form the search tree.

Non-Tree Edge

vis.non_tree_edge(e, g)

return type: void

This is invoked on back or cross edges for directed graphs and cross edges for undirected graphs.

Gray Target

vis.gray_target(e, g)

return type: void

This is invoked on the subset of non-tree edges whose target vertex is colored gray at the time of examination. The color gray indicates that the vertex is currently in the queue.

Black Target

vis.black_target(e, g)

return type: void

This is invoked on the subset of non-tree edges whose target vertex is colored black at the time of examination. The color black indicates that the vertex has been removed from the queue.

Finish Vertex

vis.finish_vertex(u, g)

return type: void

This invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before the out-edges of the adjacent vertices have been examined).

DFS Visitor*

Dijkstra Visitor*

Bellman Ford Visitor*

A* Visitor*

Event Visitor*

Planar Face Visitor*

TSP Tour Visitor*

adjacency_list

The main BGL component for representing graphs is the adjacency_list. This class generalizes the traditional adjacency-list representation for a graph. The graph is represented by a collection of vertices where, with each vertex, there is stored a collection of out-edges. The actual implementation of the collection of vertices and edges can vary to meet particular needs and is set through a container selector.

The adjacency_list class has several template parameters: EdgeList, VertexList, Directed, VertexProperties, EdgeProperties, and GraphProperties.

adjacency_list<OutEdgeList = vecS,
               VertexList = vecS,
               Directed = directedS,
               VertexProperties = no_property,
               EdgeProperties = no_property,
               GraphProperties = no_property,
               EdgeList = listS>

The adjacency_list class implements a generalized adjacency list graph structure. The template parameters provide many configuration options so that you can pick a version of the class that best meets your needs. An adjacency-list is basically a two-dimensional structure, where each element of the first dimension represents a vertex, and each of the vertices contains a one-dimensional structure that is its edge list.

The VertexList template parameter of the adjacency_list class controls what kind of container is used to represent the outer two-dimensional container. The OutEdgeList template parameter controls what kind of container is used to represent the edge lists. The choices for OutEdgeList and VertexList will determine the space complexity of the graph structure, and will determine the time complexity of the various graph operations. The possible choices and tradeoffs are discussed in Choosing the Edgelist and VertexList.

The Directed template parameter controls whether the graph is directed, undirected, or directed with access to both the in-edges and out-edges (which we call bidirectional). The bidirectional graph takes up twice the space (per edge) of a directed graph since each edge will appear in both an out-edge and in-edge list.

EdgeList and VertexList specify the classes used to store the vertex list and edge lists for the graph. These parameters allow tradeoffs between traversal speed and insertion/removal speed and tradeoffs in memory consumption. In addition, the EdgeList parameter determines whether parallel edges may be inserted into the graph.
Directed specifies whether the graph is directed, undirected, or bidirectional. By convention, a directed graph provides access to out-edges only, whereas a bidirectional graph provides access to in-edges as well as out-edges. These options are selected through directedS, undirectedS, and bidirectionalS
VertexProperties, EdgeProperties, and GraphProperties specify the property types that are attached to the vertices, edges, and to the graph itself. They default to no_property.

Internal Properties*

Bundled Properties

Class templates adjacency_list and adjacency_matrix support the introduction of named properties via internal properties. However, this method is cumbersome in many uses, where it would be more intuitive to just specify a structure or class that contains internal properties for edges or vertices. Bundled properties allow one to use adjacency_list and adjacency_matrix in this manner, providing a simple way to introduce and access any number of internal properties for vertices and edges.

One can introduce bundled properties into an either graph type by providing a user-defined class type for the VertexProperties or EdgeProperties template arguments. The user-defined class may alternatively be placed at the end of a property list, replacing the (implicit) boost::no_property argument.

Example: Route planning

Consider the implementation of a simple route planner that should find the shortest directions from one city to another via a set of highways. The vertices of the graph are cities, and we may wish to store several bits of information about the city within each vertex:

struct City
{
  string name;
  int population;
  vector<int> zipcodes;
};

The edges in the graph represent highways, which also have several interesting attributes:

struct Highway
{
  string name;
  double miles;
  int speed_limit;
  int lanes;
  bool divided;
};

With bundled properties, we can directly use the City and Highway structures to define the graph:

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City, Highway>
  Map;

Without bundled properties, translating this example directly into an instantiation of adjacency_list would involve several custom properties and would result in a type like this:

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    // Vertex properties
    boost::property<boost::vertex_name_t, std::string,
    boost::property<population_t, int,
    boost::property<zipcodes_t, std::vector<int> > > >,
    // Edge properties
    boost::property<boost::edge_name_t, std::string,
    boost::property<boost::edge_weight_t, double,
    boost::property<edge_speed_limit_t, int,
    boost::property<edge_lanes_t, int,
    boost::property<edge_divided, bool> > > > > >
  Map;

Bundling vertex and edge properties greatly simplifies the declaration of graphs.

In addition to vertex and edge bundles, we can also bundle properties of the graph itself. Suppopse we extend the application to include a portfolio of route-planning maps for different countries. In addition to the City and Highway bundles above, we can declare a graph bundle, Country.

struct Country {
  string name;
  bool use_right;   // Drive on the left or right
  bool use_metric;  // mph or km/h
};

The graph type would now be declared as:

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City, Highway, Country>
  Map;

Map map; // load the map
Map::vertex_descriptor v = *vertices(map).first;
map[v].name = "Troy";
map[v].population = 49170;
map[v].zipcodes.push_back(12180);
Map::edge_descriptor e = *out_edges(v, map).first;
map[e].name = "I-87";
map[e].miles = 10.;
map[e].speed_limit = 65;
map[e].lanes = 4;
map[e].divided = true;

map[graph_bundle].name = "United States";
map[graph_bundle].use_right = true;
map[graph_bundle].use_metric = false;

adjacency_matrix

The adjacency_matrix is the BGL class for representing dense graphs. In an adjacency_matrix, access to an arbitrary edge (u, v) is efficient (constant time). The adjacency matrix can represent both directed and undirected graphs and provides a mechanism for attaching properties to the vertices and edges.

Graph Adaptors

The BGL also includes a large number of graph adaptors. This first group of classes adapts any BGL graph to provide new behavior.

reverse_graph is an adaptor that reverses the edge directions of a directed graph on the fly, so that in-edges behave like out-edges, and vice versa.
filtered_graph is an adaptor that creates a view of a graph where two predicate function objects control whether vertices and edges from the original graph appear in the adapted graph, or whether they are hidden.

BGL also provides support for objects and data structures that are not BGL graph classes. This support is provided via adaptor classes and overloaded functions. The following describes these interfaces.

edge list is an adaptor that creates a BGL graph out of an iterator range of edges.
Stanford GraphBase is supported by overloaded functions in the header file boost/- graph/stanford graph.hpp . As a result of these overloaded functions, the GraphBase type Graph* satisfies the BGL graph interface.
LEDA is a popular object-oriented package that includes graph data structures and algorithms. Overloaded functions in the header file boost/graph/leda graph.hpp allow the LEDA graph type GRAPH<vtype, etype> to satisfy the BGL graph interface.
The STL composite type std::vector< std::list<int> > is supported as a graph by overloaded functions in the header file boost/graph/vector_as_graph.hpp.

Each graph class implements some (or all) of these concepts. The adjacency_list class can be considered a canonical implementation (or model) of a BGL graph, as it illustrates all of the basic ideas and interfaces of the BGL graphs.

Building the Topological Sort Generic Algorithm from generic depth_first_search()

First, we shall look at using the topological_sort() function with two different graph types, and then we shall demonstrate the power of the generic depth_first_search() function by showing how it can be used to implement topological sort().

A topological ordering of a directed graph is an ordering of its vertices such that if there is an edge (u, v) in the graph, then vertex u appears before vertex v in the ordering. The BGL topological_sort() function template takes two arguments: the graph to be ordered and an output iterator. The algorithm writes vertices to the output iterator in reverse topological order.

One use for topological orderings is for scheduling tasks.

// "topo-sort1.cpp" 15a
#include <deque> // to store the vertex ordering
#include <vector>
#include <list>
#include <iostream>
#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/topological_sort.hpp>
int main()
{
  using namespace boost;
  // Create labels for each of the tasks 15b
  // Create the graph 15c
  // Perform the topological sort and output the results 16
  return EXIT_SUCCESS;
}

// Create labels for each of the tasks 15b ≡
const char* tasks[ ] =
{
  "pick up kids from school",
  "buy groceries (and snacks)",
  "get cash at ATM",
  "drop off kids at soccer practice",
  "cook dinner",
  "pick up kids from soccer",
  "eat dinner"
};
const int n_tasks = sizeof (tasks) / sizeof (char*);

// Create the graph 15c ≡
std::vector< std::list<int> > g(n tasks);
g[0].push back(3);
g[1].push back(3);
g[1].push back(4);
g[2].push back(1);
g[3].push back(5);
g[4].push back(6);
g[5].push back(6);

// Perform the topological sort and output the results 16 ≡
std::deque<int> topo_order;

topological sort(g, std::front_inserter(topo_order),
 vertex_index_map(identity_property_map()));

int n = 1;
for (std::deque<int>::iterator i = topo_order.begin();
     i != topo order.end();
     ++i, ++n)
  std::cout << tasks[*i] << std::endl;

get cash at ATM
buy groceries (and snacks)
cook dinner
pick up kids from school
drop off kids at soccer practice
pick up kids from soccer
eat dinner

// Create an adjacency list object 17a ≡
adjacency_list<listS, vecS, directedS> g(n_tasks);

// Add edges to the adjacency list 17b i ≡
  add_edge(0, 3, g);
  add_edge(1, 3, g);
  add_edge(1, 4, g);
  add_edge(2, 1, g);
  add_edge(3, 5, g);
  add_edge(4, 6, g);
  add_edge(5, 6, g);

// "topo-sort2.cpp" 18 ≡
#include <vector>
#include <deque>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/adjacency_list.hpp>
int main() {
  using namespace boost;
  // Create labels for each of the tasks 15bi
  // Create an adjacency list object 17ai
  // Add edges to the adjacency list 17bi
  // Perform the topological sort and output the results 16i
  return EXIT_SUCCESS;
}

The Depth-First Search Generic Algorithm

The BGL implementation of topological_sort() is only a few lines long because it can be implemented using the depth_first_search() function (and, in fact, the topological sort algorithm is typically presented this way in text books). The implementation consists of depth_first_search() used with a visitor that records the order in which vertices pass through the "finish vertex" event of the depth-first search.

The following code creates an algorithm visitor class that records vertices as they pass through the finish event point of a depth-first search. For added genericity, the vertex ordering is recorded in an output iterator, allowing the user to choose from a variety of output methods.

template <var class='type'name OutputIterator>
class topo_sort_visitor : public default_dfs_visitor { // inherit empty actions
public:
  topo_sort_visitor(OutputIterator iter) : m_iter(iter) { }
  template <var class='type'name Vertex, typename Graph>
  void finish_vertex(Vertex u, const Graph&) { *m_iter++ = u; }
private:
  OutputIterator m_iter;
};

Thus, topological_sort() is implemented by invoking depth_first_search() using the topo_sort_visitor as a parameter.

template <var class='type'name Graph, typename OutputIterator>
void topological sort(Graph& g, OutputIterator result iter) {
  topo_sort_visitor<OutputIterator> vis(result_iter);
  depth_first_search(g, visitor(vis));
}

BGL adjacency_list*

BGL adjacency_matrix*

BGL edge_list

BGL Edge List Graph*

Property Map Interface

The property map interface specifies that each property is accessed using a separate property map object. In the following example we show an implementation of the relax() function used inside of Dijkstra's shortest paths algorithm. In this function, we need to access the weight property of an edge, and the distance property of a vertex. We write relax() as a template function so that it can be used in many difference situations. Two of the arguments to the function, weight and distance, are the property map objects. In general, BGL algorithms explicitly pass property map objects for every property that a function will need. The property map interface defines several functions, two of which we use here: get() and put(). The get() function takes a property map object, such as distance and a key object. In the case of the distance property we are using the vertex objects u and v as keys. The get() function then returns the property value for the vertex.

template <class Edge, class Graph,
            class WeightPropertyMap,
            class DistancePropertyMap>
  bool relax(Edge e, const Graph& g,
             WeightPropertyMap weight,
             DistancePropertyMap distance)
  {
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    Vertex u = source(e,g), v = target(e,g);
    if ( get(distance, u) + get(weight, e) < get(distance, v)) {
      put(distance, v, get(distance, u) + get(weight, e));
      return true;
    } else
      return false;
  }

The function get() returns a copy of the property value. There is a third function in the property map interface, at(), that returns a reference to the property value (a const reference if the map is not mutable).

Similar to the iterator_traits class of the STL, there is a property_traits class that can be used to deduce the types associated with a property map type: the key and value types, and the property map category (which is used to tell whether the map is readable, writeable, or both). In the relax() function we could have used property_traits to declare local variables of the distance property type.

  {
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    Vertex u = source(e,g), v = target(e,g);
    typename property_traits<DistancePropertyMap>::value_type
      du, dv; // local variables of the distance property type
    du = get(distance, u);
    dv = get(distance, v);
    if (du + get(weight, e) < dv) {
      put(distance, v, du + get(weight, e));
      return true;
    } else
      return false;
  }

There are two kinds of graph properties: interior and exterior:

Interior Properties

are stored inside the graph object in some way, and the lifetime of the property value objects is the same as that of the graph object.

Exterior Properties

are stored outside of the graph object and the lifetime of the property value objects is independent of the graph. This is useful for properties that are only needed temporarily, perhaps for the duration of a particular algorithm such as the color property used in breadth_first_search(). When using exterior properties with a BGL algorithm a property map object for the exterior property must be passed as an argument to the algorithm.

  property_map<Graph, vertex_distance_t>::type d
    = get(vertex_distance, g);

  property_map<Graph, edge_weight_t>::type w
    = get(edge_weight, g);

dijkstra_shortest_paths(g, src, distance_map(get(vertex_distance, g)).
    weight_map(get(edge_weight, g)).
    color_map(get(vertex_color, g)).
    vertex_index_map(get(vertex_index, g)));

dijkstra_shortest_paths(g, src);

typedef adjacency_list<vecS, vecS, bidirectionalS,
  no_property, property<edge_index_t, std::size_t> > Graph;

const int num_vertices = 9;
Graph G(num_vertices);

int capacity_array[] = { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 };
int flow_array[] = { 8, 12, 12, 12, 12, 12, 16, 16, 16, 8 };

// Add edges to the graph, and assign each edge an ID number.
add_edge(0, 1, 0, G);
// ...

typedef graph_traits<Graph>::edge_descriptor Edge;
typedef property_map<Graph, edge_index_t>::type EdgeID_Map;
EdgeID_Map edge_id = get(edge_index, G);

iterator_property_map
  <int*, int, int&, EdgeID_Map>
    capacity(capacity_array, edge_id),
    flow(flow_array, edge_id);

print_network(G, capacity, flow);

namespace boost {
template <class T>
struct property_traits<T*> {
  typedef T value_type;
  typedef ptrdiff_t key_type;
  typedef lvalue_property_map_tag category;
};

template <class T>
void put(T* pa, std::ptrdiff_t key, const T& value) { pa[key] = value;  }

template <class T>
const T& get(const T* pa, std::ptrdiff_t key) { return pa[key]; }

template <class T>
const T& at(const T* pa, std::ptrdiff_t key) { return pa[key]; }

template <class T>
  T& at(T* pa, std::ptrdiff_t key) { return pa[key]; }
}

// Definition of city_visitor omitted...

int main(int,char*[])
{
  enum { SanJose, SanFran, LA, SanDiego, Fresno, LosVegas, Reno,
         Sacramento, SaltLake, Pheonix, N };

  // An array of vertex name properties
  std::string names[] = { "San Jose", "San Francisco",  "San Jose",
                          "San Francisco", "Los Angeles", "San Diego",
                          "Fresno", "Los Vegas", "Reno", "Sacramento",
                          "Salt Lake City", "Pheonix" };

  // Specify all the connecting roads between cities.
  typedef std::pair<int,int> E;
  E edge_array[] = { E(Sacramento, Reno), ... };

  // Specify the graph type.
  typedef adjacency_list<vecS, vecS, undirectedS> Graph;
  // Create the graph object, based on the edges in edge_array.
  Graph G(N, edge_array, edge_array + sizeof(edge_array)/sizeof(E));

  // DFS and BFS need to "color" the vertices.
  // Here we use std::vector as exterior property storage.
  std::vector<default_color_type> colors(N);

  cout << "*** Depth First ***" << endl;
  depth_first_search(G, city_visitor(names), colors.begin());
  cout << endl;

  // Get the source vertex
  boost::graph_traits<Graph>::vertex_descriptor
    s = vertex(SanJose, G);

  cout << "*** Breadth First ***" << endl;
  breadth_first_search(G, s, city_visitor(names), colors.begin());

  return 0;
}

template <class Iterator, class IDMap>
class iterator_map
{
public:
  typedef typename boost::property_traits<IDMap>::key_type key_type;
  typedef typename std::iterator_traits<Iterator>::value_type value_type;
  typedef boost::lvalue_property_map_tag category;

  iterator_map(Iterator i = Iterator(),
              const IDMap& id = IDMap())
    : m_iter(i), m_id(id) { }
  Iterator m_iter;
  IDMap m_id;
};

template <class Iter, class ID>
typename std::iterator_traits<Iter>::value_type
get(const iterator_map<Iter,ID>& i,
    typename boost::property_traits<ID>::key_type key)
{
  return i.m_iter[i.m_id[key]];
}
template <class Iter, class ID>
void
put(const iterator_map<Iter,ID>& i,
    typename boost::property_traits<ID>::key_type key,
    const typename std::iterator_traits<Iter>::value_type& value)
{
  i.m_iter[i.m_id[key]] = value;
}
template <class Iter, class ID>
typename std::iterator_traits<Iter>::reference
at(const iterator_map<Iter,ID>& i,
    typename boost::property_traits<ID>::key_type key)
{
  return i.m_iter[i.m_id[key]];
}