改变Boost拓扑排序

Question

我正在尝试调整 this git 页面，在拓扑排序的同时获取传入顶点的拓扑排序列表。我这样做的原因是为了比较 this 传递归约的实现与 boost 的 未记录版本。

我正在尝试编辑 boost 自己的拓扑排序。据我所知，我需要做的就是重写discover_vertex或exspect_edge函数以根据顶点将值附加到特定向量，但我正在努力这样做。

我应该将数据结构传递给访问者或另一个 OutputIterator 吗？我怎样才能正确地覆盖这些函数并更新这两个选项中的任何一个？

如果有人能提供一些线索，那就太好了。非常感谢。

Answer 1

我的我的评论有点错误。我记得

topological_sort

有一个更通用的界面。

那么，让我向您展示如何直接针对

depth_first_search

界面复制拓扑排序，这将使您可以轻松地根据自己的喜好修改行为。

template <typename G> auto my_algo(G const& g) {
    using V   = G::vertex_descriptor;
    using E   = G::edge_descriptor;
    using Out = std::deque<V>;

    struct Visitor : public boost::dfs_visitor<> {
        Out& o;
        Visitor(Out& o) : o(o) {}
        void back_edge(E, G const&) const { throw std::runtime_error("cycle"); }
        void finish_vertex(V u, G const&) const { o.push_front(u); }
    };

    Out order;
    depth_first_search(g, boost::visitor(Visitor{order}));

    return order;
}

此时它所做的只是原始的

topological_sort

。事实上，我们可以使用文档示例进行验证：

boost::adjacency_list<> g;
add_edge(0, 1, g);
add_edge(2, 4, g);
add_edge(2, 5, g);
add_edge(0, 3, g);
add_edge(1, 4, g);
add_edge(4, 3, g);

fmt::print("Order: {}\n", my_algo(g));

打印预期的内容：Live On Coliru

Order: [2, 5, 0, 1, 4, 3]