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

Example 31.9. Finding paths with

`breadth_first_search()`

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

Example 31.10. Finding distances and paths with

`breadth_first_search()`

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

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

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

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

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