The Boost C++ Libraries

# 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.

Example 31.8. Visiting points from inside to outside with `breadth_first_search()`
``````#include <boost/graph/adjacency_list.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)
}};

boost::undirectedS> graph;
graph g{edges.begin(), edges.end(), 4};

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

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.

Example 31.9. Finding paths with `breadth_first_search()`
``````#include <boost/graph/adjacency_list.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)
}};

boost::undirectedS> graph;
graph g{edges.begin(), edges.end(), 4};

boost::array<int, 4> predecessors;
predecessors[bottomRight] = 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.

Example 31.10. Finding distances and paths with `breadth_first_search()`
``````#include <boost/graph/adjacency_list.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)
}};

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

Example 31.11. Finding paths with `dijkstra_shortest_paths()`
``````#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)
}};

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.

Example 31.12. User-defined properties with `dijkstra_shortest_paths()`
``````#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;
};

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.

Example 31.13. Initializing user-defined properties at graph definition
``````#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;
};

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.

Example 31.14. Random paths with `random_spanning_tree()`
``````#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;
};

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.

## Exercises

1. Create a graph with vertices for the following countries: Netherlands, Belgium, France, Germany, Switzerland, Austria and Italy. Connect the vertices of those countries with common borders. Find the shortest path – the path with fewest border crossings – to get from Italy to the Netherlands. Write the names of all countries to standard output which you cross on your way from Italy to the Netherlands.

2. Extend your program: Entering France now costs 10 Euro, entering Belgium 15 Euro and entering Germany 20 Euro. Crossing all other borders remains free. Find the shortest path – the path with fewest border crossings – which is also the cheapest path to get from Italy to the Netherlands. Write the names of all countries to standard output which you cross on your way from Italy to the Netherlands.