c++ - 如何在 BGL 中按照(捆绑)属性提供的顺序迭代顶点和边？

Question

假设我有一些 boost 图

#include <boost/graph/adjacency_list.hpp>

struct Vertex {
    double property_1;
    int property_2;
};

using Graph_t = boost::adjacency_list<boost::listS,
                                      boost::listS,
                                      boost::undirectedS,
                                      Vertex,
                                      boost::no_property>;
Graph_t g(5);

现在想要以不同的顺序迭代顶点，例如:

1. 按其 ID
2. 随机顺序
3. 按 property_2 降序排列
4. 按 property_1 升序
5. 以通用方式按更多捆绑属性降序/升序。

如何以最有效的方式做到这一点？

到目前为止，我创建了带有属性的 std::vector 以及包含索引的 vector ，并按属性对它们进行了排序。但是，如果您有许多属性，会创建大量可以避免的结构。

我还查看了 boost::multi_index map ，如 this cplusplus.com question 所示，但这对我来说似乎也并不渺茫。

我该怎么做？对任何提示感到高兴!

Answer 1

这(显然)不是该库的功能。

但是，您可以使用范围或范围适配器，就像在任何其他情况下一样:

<强> Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <fmt/ranges.h>
#include <fmt/ostream.h>
#include <random>

struct Vertex {
    double property_1;
    int property_2;
};

static inline std::ostream& operator<<(std::ostream& os, Vertex const& v) {
    return os << "V(" << v.property_1 << ", " << v.property_2 << ")";
}

using Graph_t =
    boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
                          Vertex, boost::no_property>;

int main() {
    using boost::make_iterator_range;
    using namespace boost::adaptors;

    Graph_t g(5);

    int i = 0;
    for (auto& v : make_iterator_range(vertices(g))) {
        ++i;
        g[v] = {i / -.3, i * 11};
    }

    auto get_bundle = [&g](auto v) -> auto& { return g[v]; };

    fmt::print("Natural order: {}\n",
        make_iterator_range(vertices(g)));
    fmt::print("Natural order: {}\n",
        make_iterator_range(vertices(g) | transformed(get_bundle)));
    fmt::print(
        "Reverse natural order: {}\n",
        make_iterator_range(vertices(g) | transformed(get_bundle) | reversed));

    auto make_view = [=](auto range) {
        return std::vector<std::reference_wrapper<Vertex>>(
            begin(range), end(range));
    };

    auto view =
        make_view(make_iterator_range(vertices(g) | transformed(get_bundle)));
    boost::reverse(view);

    fmt::print("view: {}\n", view);

    boost::reverse(view);
    fmt::print("reversed: {}\n", view);

    auto less_by = [](auto member) {
        return [=, prj = std::mem_fn(member)](auto const& a, auto const& b) {
            return prj(a) < prj(b);
        };
    };
    boost::sort(view, less_by(&Vertex::property_1));
    fmt::print("less_by property_1: {}\n", view);

    boost::sort(view, less_by(&Vertex::property_2));
    fmt::print("less_by property_2: {}\n", view);

    {
        static std::random_device rd;
        static std::mt19937 randgen{rd()};

        std::shuffle(view.begin(), view.end(), randgen);
        fmt::print("random order: {}\n", view);
    }

    // just a loop is also fine, of course
    i = 0;
    for (Vertex& bundle : view) {
        bundle.property_2 = i++;
    }
    fmt::print("modified: {}\n", view);
}

打印

Natural order: {0x1467eb0, 0x1467f10, 0x1467f70, 0x1467fd0, 0x1468030}
Natural order: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
Reverse natural order: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}
view: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}
reversed: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
less_by property_1: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}
less_by property_2: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
random order: {V(-13.3333, 44), V(-3.33333, 11), V(-10, 33), V(-6.66667, 22), V(-16.6667, 55)}
modified: {V(-13.3333, 0), V(-3.33333, 1), V(-10, 2), V(-6.66667, 3), V(-16.6667, 4)}

更多，从这里开始

• std::ranges 可以为您提供其中大部分内容，但根据我的经验，还有一些限制。不过，它通常会更安全(因为 Boost Range V2 相当旧)。

• 要拥有“事件索引”(如数据库)，请使顶点容器选择器选择多索引容器。参见例如这里的建议https://marc.info/?l=boost&m=118835654637830

• 要建模您自己的图形数据结构，请参阅例如在这里寻找灵感

  • What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object *>)?

  • What is required for a custom BGL graph to work with topological sort?

更新使用 Boost PFR 生成代码

为了回应评论，您可以使用 Boost PFR 静态生成具有比较器简单类型的数组:

template <typename T, typename Op = std::less<> >
constexpr static inline auto make_field_comparers(Op op = {}) {
    namespace pfr = boost::pfr;
    auto constexpr N = pfr::tuple_size<T>::value;
    using A = std::array<std::function<bool(T const&, T const&)>, N>;

    auto lift = [op](auto prj) {
        return [=](T const& a, T const& b) { return op(prj(a), prj(b)); };
    };

    return [lift]<size_t... I>(std::index_sequence<I...>){
        return A{lift([](T const& v) { return pfr::get<I>(v); })...};
    }
    (std::make_index_sequence<N>{});
}

你可以使用像 Live On Compiler Explorer

std::vector orderings {
    std::pair { "asc", make_field_comparers<Vertex>() },
    std::pair { "desc", make_field_comparers<Vertex>(std::greater<>{}) },
};

for (auto const& [dir, fields] : orderings) {
    for (size_t field = 0; field < fields.size(); ++field) {
        boost::sort(view, fields[field]);
        fmt::print("by field #{} {}: {}\n", field, dir, view);
    }
}

打印

by field #0 asc: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}
by field #1 asc: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
by field #0 desc: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
by field #1 desc: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}