boost graphs - 优先拓扑排序

Question

我想做一个改变的拓扑排序。在任何给定的级别，我们可以采取多种选择。

例如，该图的拓扑顺序可以是 1 -> 2 -> 3 或 2 -> 1 -> 3。

我的顶点具有关联的数据。

struct VertexData {
  int id;
  int weight;
}

我希望拓扑排序在遇到选择时首先优先考虑较高的权重。所以在这种情况下顺序总是 2 -> 1 -> 3。

我该怎么做？

Answer 1

一切都取决于这里图模型的选择。

该算法不提供初始顶点排序的扩展点。它只是使用香草概念获得外边缘：

boost::tie(ei, ei_end) = out_edges(u, g); // depth_first_search.hpp:L152

adjacency_list

的

OutEdgeList

参数的任何有序/散列容器选择器将仅根据边缘的目标进行比较。所有这些都是实现细节。

只要您不使用有序/散列容器选择器，您就可能会手动干扰和对这些边缘进行排序，就像我之前展示过。

在这种情况下，我可能会错，但看起来你可以在创建边之前对顶点进行排序：

住在Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <deque>
#include <ranges>
namespace r = std::ranges;
namespace v = std::views;

template <typename G> auto topo_order(G const& g) {
    using V = G::vertex_descriptor;
    std::map<V, size_t> idx;
    for (auto v : boost::make_iterator_range(vertices(g)))
        idx.emplace(v, idx.size());

    std::deque<V> order;

    topological_sort(             //
        g, front_inserter(order), //
        vertex_index_map(boost::make_assoc_property_map(idx)));

    return order;
}

#include <fmt/ranges.h>

template <typename Cmp> void demo() {
    struct VertexData {
        int id;
        int weight;
    };
    using G = boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, VertexData>;

    G g;
    auto v2 = add_vertex({2, 30}, g);
    auto v1 = add_vertex({1, 20}, g);
    auto v3 = add_vertex({3, 20}, g);

    g.m_vertices.sort([&g, cmp = Cmp{}](auto const& a, auto const& b) { //
        return cmp(g[a].weight, g[b].weight);
    });

    add_edge(v1, v3, g);
    add_edge(v2, v3, g);

    fmt::print("{} topo: {}\n", __PRETTY_FUNCTION__,
               topo_order(g) | v::transform([&g](auto v) { return g[v].id; }));
}

int main() {
    demo<r::less>();
    demo<r::greater>();
}

印刷

void demo() [with Cmp = std::ranges::less] topo: [2, 1, 3]
void demo() [with Cmp = std::ranges::greater] topo: [1, 2, 3]