Boost Graph DFS（和其他算法）的 API 背后的动机是什么？

Question

一般问题

当我迈出进入 BGL 的第一步时，我很难理解为什么最小惊讶原则在这里有点被欺负。

背景

因此，经过大量的努力，我可以构建一个树图，并且我期望能够写出类似的东西

tree.dfs(visitor);

现在我知道 BGL 并不是一个面向对象的 API，我想写类似的东西是有意义的

depth_first_search(tree, visitor)

然后，由于我了解到 BGL 中没有 Tree 类，因此设计选择是使根的存在成为值属性而不是类型属性。所以我想这解释了为什么我们必须传递根描述符，比如

depth_first_search(graph_that_is_a_tree, visitor, root);

是什么让我困惑

到目前为止，我感觉我（或多或少）遵循了设计。但为了让我的代码编译，我实际上必须编写：

  auto [root, tree] = my_stuff::to_k_ary_tree<my_vertex, my_edge>(ast);

  auto indexmap = boost::get(boost::vertex_index, tree);
  auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);

  MyVisitor<my_stuff::k_ary_tree<my_vertex,my_edge>> vis;
  std::vector<boost::default_color_type> colors(num_vertices(tree));
  boost::depth_first_search(tree, vis, colormap, root);

这就是我失去它的地方（直觉）：即使我被警告​​大多数算法都需要颜色图，我也不理解/欣赏为什么我需要这个签名。

我的问题

为什么DFS算法不能负责处理这些细节呢？

我能想到什么

• 是因为 if tree 不是一种类型吗？如果树和图之间没有类型区别，那么 DFS 就不可能知道不存在循环，因此它需要对所有情况下探索过的顶点进行着色 - 即使您绝对确定它是一个树，有根，无环。
• 如果是这样，那么它并不能完全向我解释为什么 DFS 无法在我们不知情的情况下创建/访问/销毁此颜色图。

Answer 1

最好的解释就在文档的登陆页面上： https://www.boost.org/doc/libs/1_81_0/libs/graph/doc/index.html

它对比了STL [原文如此] 中的通用性与Boost Graph Library 中的通用性。第二部分最核心的简介：

[首先，]BGL 的图形算法被写入一个接口，该接口抽象出特定图形数据结构的细节。与 STL 一样，BGL 使用迭代器来定义数据结构遍历的接口。存在三种不同的图遍历模式：遍历图中的所有顶点、遍历所有边以及沿着图的邻接结构（从顶点到其每个邻居）。每种遍历模式都有单独的迭代器。

这个通用接口允许模板函数 breadth_first_search()处理多种图形数据结构，从使用指针链接节点实现的图形到以数组编码的图形。这种灵活性在图领域尤其重要。图数据结构通常是针对特定应用程序定制的。传统上，如果程序员想要重用算法实现，他们必须将其图形数据转换/复制到图形库规定的图形结构中。LEDA、GTL、Stanford GraphBase 等库就是这种情况；对于用 Fortran 语言编写的图算法尤其如此。这严重限制了其图算法的重用。

相比之下，定制的（甚至遗留的）图结构可以通过外部适配按原样与 BGL 的通用图算法一起使用（请参阅如何将现有图转换为 BGL 一节）。外部适配将新接口包装在数据结构周围，无需复制，也无需将数据放置在适配器对象内。BGL 界面经过精心设计，使这种适应变得容易。为了证明这一点，我们构建了在 BGL 图算法中使用各种图结构（LEDA 图、Stanford GraphBase 图，甚至 Fortran 风格的数组）的接口代码。

但是等等，还有更多！

相关的，Boost Geometry 有一个非常相似的设计原理部分，其中更详细地介绍了通用模板库设计如何演变为 BGL 也具有的形式。

当然，它通过示例来实现这一点，这非常好，即使这些示例来自计算几何领域。

辅助属性图

关于颜色图（和其他辅助算法状态），我将添加：

• 你可以默认它们

  • 使用标记属性 ( property<vertex_color_t, default_color_type>)
  • 使用特征特化将外部映射与图形类型相关联（特化graph_property<>）

• 让调用者提供它们可以在跨算法调用重用着色/存储时获得巨大的效率提升

• 请注意，大多数算法默认使用 aux 属性映射。事实上，DFS也可以！

简化样本

以下示例部分基于您之前的问题代码，展示了如何简化调用。

请注意，它使用 ADL 来避免boost::限定函数名称，并使用dfs 的命名参数重载：

住在科里鲁

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/random.hpp>
#include <iomanip>
#include <random>

struct MyVisitor : boost::default_dfs_visitor {
    auto discover_vertex(auto u, auto const& g) {
        std::cout << "Discover vertex " << u << " (" << g[u] << ")\n";
    }
};

template <class V, class E>
    requires std::constructible_from<V, std::string> && std::constructible_from<E, double>
auto foo(...) {
    using G = boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, V, E>;

    G g;
    std::mt19937 prng{std::random_device{}()};
    generate_random_graph(g, 10, 30, prng);

    for (auto e : make_iterator_range(edges(g)))
        g[e] = {std::uniform_real_distribution(1.0, 2.0)(prng)};

    for (int i = 0; i < 10; ++i)
        g[i] = {std::array{"zero", "one", "two", "three", "four", "five", "six", "seven",
                           "eight", "nine"}
                    .at(i)};

    return std::tuple(std::move(g), 3);
}

struct V { std::string  name; };
struct E { double length; };
static inline auto& operator<<(std::ostream& os, V const& v) { return os << quoted(v.name); }

int main() {
    auto [g, root] = foo<V, E>();
    depth_first_search(g, visitor(MyVisitor{}));
    print_graph(g);
}

打印，例如

Discover vertex 0 ("zero")
Discover vertex 5 ("five")
Discover vertex 1 ("one")
Discover vertex 2 ("two")
Discover vertex 4 ("four")
Discover vertex 6 ("six")
Discover vertex 8 ("eight")
Discover vertex 3 ("three")
Discover vertex 7 ("seven")
Discover vertex 9 ("nine")
0 --> 5 6 7 
1 --> 0 2 7 
2 --> 1 4 5 6 8 
3 --> 0 4 8 
4 --> 1 2 6 
5 --> 0 1 2 7 
6 --> 2 5 8 
7 --> 2 5 
8 --> 0 3 
9 --> 3 7