C++ Boost Graph算法超详细精讲
无水先生 人气:0Boost.Graph 中的算法类似于标准库中的算法——它们是通用的并且非常灵活。但是，并不总是很清楚应该如何使用它们。
示例 31.8。使用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"});
}示例 31.8 使用算法 boost::breadth_first_search() 从内部到外部访问点。该算法从作为第二个参数传递的点开始。它首先访问可以从该点直接到达的所有点，像波浪一样工作。
boost::breadth_first_search() 不返回特定结果。该算法只是访问点。是否收集和存储数据取决于传递给 boost::breadth_first_search() 的访问者。
访问者是在访问点时调用其成员函数的对象。通过将访问者传递给 boost::breadth_first_search() 之类的算法，您可以决定访问某个点时应该发生什么。访问者就像函数对象，可以传递给标准库的算法。
示例 31.8 使用记录距离的访问者。距离是从一个点到另一个点必须跨越的线数，从作为第二个参数传递给 boost::breadth_first_search() 的点开始。 Boost.Graph 提供了帮助函数 boost::record_distances() 来创建访问者。还必须传递属性图和标签。
属性映射存储点或线的属性。 Boost.Graph 描述了属性映射的概念。由于指针或迭代器被视为属性映射的开头，因此详细了解属性映射并不重要。在示例 31.8 中，数组距离的开头通过 distances.begin() 传递到 boost::record_distances()。这足以将数组距离用作属性映射。但是，重要的是数组的大小不小于图中的点数。毕竟，需要存储到图中每个点的距离。
请注意，距离基于 boost::array 而不是 std::array。使用 std::array 会导致编译器错误。
根据算法，有不同的事件。传递给 boost::record_distances() 的第二个参数指定应通知访问者哪些事件。 Boost.Graph 定义了空类的标签来给事件命名。示例 31.8 中的标签 boost::on_tree_edge 指定在找到新点时应记录距离。
事件取决于算法。您必须查看有关算法的文档，以了解支持哪些事件以及可以使用哪些标签。
由 boost::record_distances() 创建的访问者与算法无关，因此您可以将 boost::record_distances() 与其他算法一起使用。适配器用于绑定算法和访问者。示例 31.8 调用 boost::make_bfs_visitor() 来创建这个适配器。此帮助函数返回算法 boost::breadth_first_search() 所期望的访问者。此访问者定义适合算法支持的事件的成员函数。例如，boost::make_bfs_visitor() 返回的访问者定义了成员函数 tree_edge()。如果使用标签 boost::on_tree_edge 定义的访问者被传递给 boost::make_bfs_visitor()（如示例 31.8），则在调用 tree_edge() 时会通知访问者。这使您可以使用具有不同算法的访问者，而无需这些访问者定义所有算法所期望的所有成员函数。
boost::make_bfs_visitor() 返回的适配器不能直接传递给算法 boost::breadth_first_search()。它必须用 boost::visitor() 包装，然后作为第三个参数传递。
有两种算法变体，例如 boost::breadth_first_search()。一种变体期望算法支持的每个参数都将被传递。另一个变体支持类似于命名参数的东西。使用第二个变体通常更容易，因为只需要传递您感兴趣的参数。许多参数不必传递，因为算法使用默认值。
示例 31.8 使用了需要命名参数的 boost::breadth_first_search() 的变体。前两个参数是图形和起点，它们是必需的。然而，第三个参数几乎可以是一切。在示例 31.8 中，需要传递一个访问者。为此，boost::make_bfs_visitor() 返回的适配器使用 boost::visitor() 命名。现在，很明显第三个参数是访问者。您将在以下示例中看到其他参数如何按名称传递到 boost::breadth_first_search()。
示例 31.8 显示数字 0、1、2 和 1。这些是从左上角到所有点的距离。右上角的字段（索引为 1 的字段）仅一步之遥。右下方的字段（索引为 2 的字段）相距两步。左下方的字段——索引为 3 的字段——再次只有一步之遥。首先打印的数字 0 是指左上角的字段。由于它是传递给 boost::breadth_first_search() 的起点，因此需要零步才能到达它。
boost::breadth_first_search() 不设置数组中的元素，它只是增加存储的值。因此，您必须在开始之前初始化数组距离中的所有元素。
示例 31.9 说明了如何找到最短路径。
示例 31.9。使用 width_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';
}示例 31.9 显示 0、1 和 2。这是从左上角到右下角的最短路径。尽管左下场上的路径同样短，但它在右上场上方引导。
再次使用 boost::breadth_first_search() - 这次是为了找到最短路径。如您所知，此算法只是访问点。要获得最短路径的描述，必须使用适当的访问者。示例 31.9 调用 boost::record_predecessors() 来获取一个。
boost::record_predecessors() 返回一个访问者来存储每个点的前任。每当 boost::breadth_first_search() 访问一个新点时，前一个点就会存储在传递给 boost::record_predecessors() 的属性映射中。由于 boost::breadth_first_search() 从内部到外部访问点，因此找到了最短路径——从作为第二个参数传递给 boost::breadth_first_search() 的点开始。示例 31.9 找到从图中所有点到右下角的最短路径。
在 boost::breadth_first_search() 返回后，属性映射前驱包含每个点的前驱。为了在从左上角到右下角时找到第一个字段，索引为 0 的元素（左上角字段的索引）在前辈中被访问。在前辈中找到的值为 1，这意味着下一个字段位于右上角。访问索引为 1 的前辈会返回下一个字段。在示例 31.9 中，这是右下角的字段 - 索引为 2 的字段。这样就可以在巨大的图表中迭代地找到从起点到终点的点。
示例 31.10。使用 width_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';
}示例 31.10 显示了 boost::breadth_first_search() 如何用于两个访问者。要使用两个访问者，您需要使用 std::make_pair() 将它们配对。如果需要两个以上的访问者，则必须嵌套这些对。示例 31.10 与示例 31.8 和示例 31.9 一起执行相同的操作。
boost::breadth_first_search() 只能在每行具有相同权重的情况下使用。这意味着跨越点之间的任何线所花费的时间总是相同的。如果线是加权的，这意味着每条线可能需要不同的时间来遍历，那么您需要使用不同的算法来找到最短路径。
示例 31.11。使用 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';
}示例 31.11 使用 boost::dijkstra_shortest_paths() 来查找到右下角的最短路径。如果线被加权，则使用此算法。示例 31.11 假设从左上角到右上角越过线所需的时间是越过任何其他线所需的时间的两倍。
在使用 boost::dijkstra_shortest_paths() 之前，必须将权重分配给行。这是通过数组权重完成的。数组中的元素对应于图中的线条。因为从左上角到右上角的线是第一个，所以 weights 中的第一个元素被设置为所有其他元素的两倍大。
为了给线条分配权重，数组权重开头的迭代器作为第三个参数传递给图形的构造函数。这第三个参数可用于初始化线条的属性。这仅适用于已为线条定义属性的情况。
示例 31.11 将其他模板参数传递给 boost::adjacency_list。第四个和第五个模板参数指定点和线是否具有属性以及这些属性是什么。您可以为线和点指定属性。
默认情况下，boost::adjacency_list 使用 boost::no_property，这意味着点和线都没有属性。在示例 31.11 中，boost::no_property 作为第四个参数传递，用于指定点的无属性。第五个参数使用 boost::property 定义捆绑属性。
捆绑属性是内部存储在图表中的属性。因为可以定义多个捆绑属性，所以 boost::property 需要一个标签来定义每个属性。 Boost.Graph 提供了一些标签，例如 boost::edge_weight_t，来定义算法自动识别和使用的常用属性。传递给 boost::property 的第二个模板参数是属性的类型。在示例 31.11 中，权重是 int 值。
示例 31.11 有效，因为 boost::dijkstra_shortest_paths() 自动使用类型为 boost::edge_weight_t 的捆绑属性。
请注意，没有访问者被传递到 boost::dijkstra_shortest_paths()。该算法不只是访问点。它寻找最短路径——这就是为什么它被称为 boost::dijkstra_shortest_paths()。您无需考虑事件或访客。你只需要传递一个容器来存储每个点的前身。如果您使用需要命名参数的 boost::dijkstra_shortest_paths() 变体，如示例 31.11 中所示，则使用 boost::predecessor_map() 传递容器。这是一个辅助函数，它需要一个指向数组开头的指针或迭代器。
示例 31.11 显示 0、3 和 2：从左上角到右下角的最短路径通向左下角字段。右上角的路径比其他可能性具有更大的权重。
示例 31.12。使用 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';
}示例 31.12 的工作方式与上一个类似，并显示相同的数字，但它使用用户定义的类 edge_properties，而不是预定义的属性。
edge_properties 定义成员变量 weight 来存储线条的重量。如果需要其他属性，可以添加更多成员变量。
如果您使用线的描述符作为图形的索引，则可以访问用户定义的属性。因此，该图的行为类似于一个数组。您从 boost::edges() 返回的行迭代器中获取描述符。这样就可以为每一行分配一个权重。
为了让 boost::dijkstra_shortest_paths() 理解权重存储在 edge_properties 中的权重中，必须传递另一个命名参数。这是通过 weight_map() 完成的。请注意，weight_map() 是从 boost::predecessor_map() 返回的对象的成员函数。还有一个名为 boost::weight_map() 的独立函数。如果需要传递多个命名参数，则必须在第一个命名参数（独立函数返回的参数）上调用成员函数。这样，所有参数都被打包到一个对象中，然后传递给算法。
为了告诉 boost::dijkstra_shortest_paths() edge_properties 中的权重包含权重，传递了一个指向该属性的指针。它不会直接传递给 weight_map()。相反，它通过 boost::get() 创建的对象传递。现在调用已完成，并且 boost::dijkstra_shortest_paths() 知道要访问哪个属性来获取权重。
示例 31.13。在图形定义处初始化用户定义的属性
#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';
}定义图形时可以初始化用户定义的属性。您只需将迭代器作为第三个参数传递给 boost::adjacency_list 的构造函数，它引用用户定义属性类型的对象。因此，您不需要通过描述符访问行的属性。示例 31.13 的工作原理与前一个类似，并显示相同的结果。
示例 31.14。带有 random_spanning_tree() 的随机路径
示例 31.14 中介绍的算法会找到随机路径。 boost::random_spanning_tree() 类似于 boost::dijkstra_shortest_paths()。它返回通过 boost::predecessor_map 传递的容器中的点的前驱。与 boost::dijkstra_shortest_paths() 相比，起点不直接作为参数传递给 boost::random_spanning_tree()。它必须作为命名参数传递。这就是为什么在 boost::predecessor_map 类型的对象上调用 root_vertex()。示例 31.14 查找到左下角字段的随机路径。
因为 boost::random_spanning_tree() 正在寻找随机路径，所以必须将随机数生成器作为第二个参数传递。示例 31.14 使用 std::mt19937，它自 C++11 以来一直是标准库的一部分。您还可以使用 Boost.Random 中的随机数生成器。
示例 31.14 显示 1、0 和 3 或 1、2 和 3。1 是右上角的字段，3 是左下角的字段。从右上场到左下场只有两种可能的路径：通过左上场或通过右下场。 boost::random_spanning_tree() 必须返回这两个路径之一。
练习
为以下国家/地区创建具有顶点的图形：荷兰、比利时、法国、德国、瑞士、奥地利和意大利。用共同边界连接这些国家的顶点。找到从意大利到荷兰的最短路径——过境次数最少的路径。将所有国家/地区的名称写入您从意大利到荷兰的途中经过的标准输出。
扩展您的计划：现在进入法国花费 10 欧元，进入比利时 15 欧元，进入德国 20 欧元。跨越所有其他边界仍然是免费的。找到最短的路径——过境点最少的路径——这也是从意大利到荷兰的最便宜的路径。将所有国家/地区的名称写入您从意大利到荷兰的途中经过的标准输出。
加载全部内容