Algorithms

Algorithms from Boost.Graph resemble those from the standard library – they are generic and very flexible. However, it’s not always immediately clear how they should be used.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iterator>
#include <algorithm>
#include <iostream>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};

  boost::array<int, 4> distances{{0}};

  boost::breadth_first_search(g, topLeft,
    boost::visitor(
      boost::make_bfs_visitor(
        boost::record_distances(distances.begin(),
          boost::on_tree_edge{}))));

  std::copy(distances.begin(), distances.end(),
    std::ostream_iterator<int>{std::cout, "\n"});
}

Example 31.8 uses the algorithm boost::breadth_first_search() to visit points from inside to outside. The algorithm starts at the point passed as the second parameter. It first visits all points that can be reached directly from that point, working like a wave.

boost::breadth_first_search() doesn’t return a specific result. The algorithm just visits points. Whether data is collected and stored depends on the visitors passed to boost::breadth_first_search().

Visitors are objects whose member functions are called when a point is visited. By passing visitors to an algorithm like boost::breadth_first_search(), you decide what should happen when a point is visited. Visitors are like function objects that can be passed to algorithms of the standard library.

Example 31.8 uses a visitor that records distances. A distance is the number of lines that have to be crossed to get from one point to another, starting at the point passed to boost::breadth_first_search() as the second parameter. Boost.Graph provides the helper function boost::record_distances() to create the visitor. A property map and a tag also have to be passed.

Property maps store properties for points or lines. Boost.Graph describes the concept of property maps. Since a pointer or iterator is taken as the beginning of a property map, it isn’t important to understand property maps in detail. In Example 31.8 the beginning of the array distances is passed with distances.begin() to boost::record_distances(). This is sufficient for the array distances to be used as a property map. However, it is important that the size of the array isn’t smaller than the number of points in the graph. After all, the distance to each and every point in the graph needs to be stored.

Please note that distances is based on boost::array and not on std::array. Using std::array would lead to a compiler error.

Depending on the algorithm, there are different events. The second parameter passed to boost::record_distances() specifies which events the visitor should be notified about. Boost.Graph defines tags that are empty classes to give events names. The tag boost::on_tree_edge in Example 31.8 specifies that a distance should be recorded when a new point has been found.

Events depend on the algorithm. You have to check the documentation on algorithms to find out which events are supported and which tags you can use.

A visitor created by boost::record_distances() is algorithm independent, so you can use boost::record_distances() with other algorithms. An adapter is used to bind an algorithm and a visitor. Example 31.8 calls boost::make_bfs_visitor() to create this adapter. This helper function returns a visitor as expected by the algorithm boost::breadth_first_search(). This visitor defines member functions that fit the events the algorithm supports. For example, the visitor returned by boost::make_bfs_visitor() defines the member function tree_edge(). If a visitor that is defined with the tag boost::on_tree_edge is passed to boost::make_bfs_visitor() (as in Example 31.8), the visitor is notified when tree_edge() is called. This lets you use visitors with different algorithms without those visitors having to define all of the member functions expected by all algorithms.

The adapter returned by boost::make_bfs_visitor() can’t be passed directly to the algorithm boost::breadth_first_search(). It has to be wrapped with boost::visitor() and then passed as a third parameter.

There are two variants of algorithms like boost::breadth_first_search(). One variant expects that every parameter the algorithm supports will be passed. Another variant supports something similar to named parameters. It’s typically easier to use this second variant because only the parameters you’re interested in have to be passed. Many parameters don’t have to be passed because algorithms use default values.

Example 31.8 uses the variant of boost::breadth_first_search() that expects named parameters. The first two parameters are the graph and the start point, which are required. However, the third parameter can be nearly everything. In Example 31.8 a visitor needs to be passed. For that to work, the adapter returned by boost::make_bfs_visitor() is named using boost::visitor(). Now, it’s clear that the third parameter is a visitor. You’ll see in the following examples how other parameters are passed by name to boost::breadth_first_search().

Example 31.8 displays the numbers 0, 1, 2, and 1. These are the distances to all points from the top left. The top right field – the one with the index 1 – is only one step away. The bottom right field – the one with the index 2 – is two steps away. The bottom left field – the one with the index 3 – is again only one step away. The number 0 which is printed first refers to the top left field. Since it’s the start point that was passed to boost::breadth_first_search(), zero steps are required to reach it.

boost::breadth_first_search() doesn’t set the elements in the array, it just increases the stored values. Therefore, you must initialize all elements in the array distances before you start.

Example 31.9 illustrates how to find the shortest path.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <algorithm>
#include <iostream>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};

  boost::array<int, 4> predecessors;
  predecessors[bottomRight] = bottomRight;

  boost::breadth_first_search(g, bottomRight,
    boost::visitor(
      boost::make_bfs_visitor(
        boost::record_predecessors(predecessors.begin(),
          boost::on_tree_edge{}))));

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
  std::cout << p << '\n';
}

Example 31.9 displays 0, 1, and 2. This is the shortest path from top left to bottom right. It leads over the top right field although the path over the bottom left field would be equally short.

boost::breadth_first_search() is used again – this time to find the shortest path. As you already know, this algorithm just visits points. To get a description of the shortest path, an appropriate visitor must be used. Example 31.9 calls boost::record_predecessors() to get one.

boost::record_predecessors() returns a visitor to store the predecessor of every point. Whenever boost::breadth_first_search() visits a new point, the previous point is stored in the property map passed to boost::record_predecessors(). As boost::breadth_first_search() visits points from the inside to the outside, the shortest path is found – starting at the point passed as a second parameter to boost::breadth_first_search(). Example 31.9 finds the shortest paths from all points in the graph to the bottom right.

After boost::breadth_first_search() returns, the property map predecessors contains the predecessor of every point. To find the first field when travelling from the top left to the bottom right, the element with the index 0 – the index of the top left field – is accessed in predecessors. The value found in predecessors is 1, which means the next field is at the top right. Accessing predecessors with the index 1 returns the next field. In Example 31.9 that’s the bottom right field – the one with the index 2. That way it’s possible to find the points iteratively in huge graphs to get from a start to an end point.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <algorithm>
#include <iostream>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};

  boost::array<int, 4> distances{{0}};
  boost::array<int, 4> predecessors;
  predecessors[bottomRight] = bottomRight;

  boost::breadth_first_search(g, bottomRight,
    boost::visitor(
      boost::make_bfs_visitor(
        std::make_pair(
          boost::record_distances(distances.begin(),
            boost::on_tree_edge()),
          boost::record_predecessors(predecessors.begin(),
            boost::on_tree_edge{})))));

  std::for_each(distances.begin(), distances.end(),
    [](int d){ std::cout << d << '\n'; });

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
  std::cout << p << '\n';
}

Example 31.10 shows how boost::breadth_first_search() is used with two visitors. To use two visitors, you need to put them in a pair with std::make_pair(). If more than two visitors are needed, the pairs have to be nested. Example 31.10 does the same thing as Example 31.8 and Example 31.9 together.

boost::breadth_first_search() can only be used if every line has the same weight. This means the time taken to cross any line between points is always the same. If lines are weighted, meaning that each line may require a different amount of time to traverse, then you need to use a different algorithm to find the shortest path.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iostream>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    boost::property<boost::edge_weight_t, int>> graph;

  std::array<int, 4> weights{{2, 1, 1, 1}};

  graph g{edges.begin(), edges.end(), weights.begin(), 4};

  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()));

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

Example 31.11 uses boost::dijkstra_shortest_paths() to find the shortest paths to the bottom right. This algorithm is used if lines are weighted. Example 31.11 assumes that it takes twice as long to cross the line from the top left to the top right as it takes to cross any other line.

Before boost::dijkstra_shortest_paths() can be used, weights have to be assigned to lines. This is done with the array weights. The elements in the array correspond to the lines in the graph. Because the line from the top left to the top right is first, the first element in weights is set to a value twice as big as all others.

To assign weights to lines, the iterator to the beginning of the array weights is passed as the third parameter to the constructor of the graph. This third parameter can be used to initialize properties of lines. This only works if properties have been defined for lines.

Example 31.11 passes additional template parameters to boost::adjacency_list. The fourth and fifth template parameter specify if points and lines have properties and what those properties are. You can assign properties to both lines and points.

By default, boost::adjacency_list uses boost::no_property, which means that neither points nor lines have properties. In Example 31.11, boost::no_property is passed as a fourth parameter to specify no properties for points. The fifth parameter uses boost::property to define a bundled property.

Bundled properties are properties that are stored internally in a graph. Because it’s possible to define multiple bundled properties, boost::property expects a tag to define each property. Boost.Graph provides some tags, such as boost::edge_weight_t, to define frequently used properties that are automatically recognized and used by algorithms. The second template parameter passed to boost::property is the type of the property. In Example 31.11 weights are int values.

Example 31.11 works because boost::dijkstra_shortest_paths() automatically uses the bundled property of type boost::edge_weight_t.

Note that no visitor is passed to boost::dijkstra_shortest_paths(). This algorithm doesn’t just visit points. It looks for shortest paths – that’s why it’s called boost::dijkstra_shortest_paths(). You don’t need to think about events or visitors. You only need to pass a container to store the predecessor of every point. If you use the variant of boost::dijkstra_shortest_paths() that expects named parameters, as in Example 31.11, pass the container with boost::predecessor_map(). This is a helper function which expects a pointer or an iterator to the beginning of an array.

Example 31.11 displays 0, 3, and 2: The shortest path from top left to bottom right leads over the bottom left field. The path over the top right field has a greater weight than the other possibilities.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iostream>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  struct edge_properties
  {
    int weight;
  };

  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    edge_properties> graph;

  graph g{edges.begin(), edges.end(), 4};

  graph::edge_iterator it, end;
  boost::tie(it, end) = boost::edges(g);
  g[*it].weight = 2;
  g[*++it].weight = 1;
  g[*++it].weight = 1;
  g[*++it].weight = 1;

  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()).
    weight_map(boost::get(&edge_properties::weight, g)));

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

Example 31.12 works like the previous one and displays the same numbers, but it uses a user-defined class, edge_properties, rather than a predefined property.

edge_properties defines the member variable weight to store the weight of a line. It is possible to add more member variables if other properties are required.

You can access user-defined properties if you use the descriptor of lines as an index for the graph. Thus, the graph behaves like an array. You get the descriptors from the line iterators that are returned from boost::edges(). That way a weight can be assigned to every line.

To make boost::dijkstra_shortest_paths() understand that weights are stored in weight in edge_properties, another named parameter has to be passed. This is done with weight_map(). Note that weight_map() is a member function of the object returned from boost::predecessor_map(). There is also a free-standing function called boost::weight_map(). If you need to pass multiple named parameters, you have to call a member function on the first named parameter (the one that was returned by the free-standing function). That way all parameters are packed into one object that is then passed to the algorithm.

To tell boost::dijkstra_shortest_paths() that weight in edge_properties contains the weights, a pointer to that property is passed. It isn’t passed to weight_map() directly. Instead it is passed in an object created with boost::get(). Now the call is complete, and boost::dijkstra_shortest_paths() knows which property to access to get the weights.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iostream>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  struct edge_properties
  {
    int weight;
  };

  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    edge_properties> graph;

  boost::array<edge_properties, 4> props{{2, 1, 1, 1}};

  graph g{edges.begin(), edges.end(), props.begin(), 4};

  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()).
    weight_map(boost::get(&edge_properties::weight, g)));

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

It’s possible to initialize user-defined properties when a graph is defined. You only have to pass an iterator as the third parameter to the constructor of boost::adjacency_list, which refers to objects of the type of the user-defined property. Thus, you don’t need to access properties of lines through descriptors. Example 31.13 works like the previous one and displays the same result.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random_spanning_tree.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <random>
#include <iostream>
#include <ctime>
#include <cstdint>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  struct edge_properties
  {
    int weight;
  };

  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS> graph;

  graph g{edges.begin(), edges.end(), 4};

  boost::array<int, 4> predecessors;

  std::mt19937 gen{static_cast<uint32_t>(std::time(0))};
  boost::random_spanning_tree(g, gen,
    boost::predecessor_map(predecessors.begin()).
    root_vertex(bottomLeft));

  int p = topRight;
  while (p != -1)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
}

The algorithm introduced in Example 31.14 finds random paths. boost::random_spanning_tree() is similar to boost::dijkstra_shortest_paths(). It returns the predecessors of points in a container that is passed with boost::predecessor_map. In contrast to boost::dijkstra_shortest_paths(), the starting point isn’t passed directly as a parameter to boost::random_spanning_tree(). It must be passed as a named parameter. That’s why root_vertex() is called on the object of type boost::predecessor_map. Example 31.14 finds random paths to the bottom left field.

Because boost::random_spanning_tree() is looking for a random path, a random number generator has to be passed as the second parameter. Example 31.14 uses std::mt19937, which has been part of the standard library since C++11. You could also use a random number generator from Boost.Random.

Example 31.14 displays either 1, 0, and 3 or 1, 2, and 3. 1 is the top right field, 3 the bottom left field. There are only two possible paths from the top right field to the bottom left field: through the top left field or through the bottom right field. boost::random_spanning_tree() must return one of these two paths.