Boost BGL 传递减少

Question

我尝试使用boost的transitive_reduction，但我不知道如何使用它。

我有一个定义为的图表：

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, IQsNode*> Graph;
typedef Graph::vertex_descriptor Vertex;

我想调用该方法：

Graph TC;
boost::transitive_reduction(_fullGraph, TC,g_to_tr_map_stor,g_to_tc_map_stor);

我不知道“g_to_tr_map_stor”和“g_to_tc_map_stor”必须使用的类型。

根据我读到的信息，它一定是从顶点
到整数的映射。我尝试了很多种地图但没有成功。

一些想法？

谢谢

Answer 1

据我的文档告诉我这不是公共 API。这意味着您可以找到内部使用它的地方，并将其用作如何使用它的示例。

有趣的是，事实并非如此。这可能会导致人们认为文档滞后/被遗忘

警告使用未记录的 API 表面可能会在升级时破坏您的代码，恕不另行通知。

这是我能想到的满足界面的最简单的方法：

Graph const g = make_random();

Graph tr;
std::map<Graph::vertex_descriptor, Graph::vertex_descriptor> g_to_tr;
std::vector<size_t> id_map(num_vertices(g));
std::iota(id_map.begin(), id_map.end(), 0u);

transitive_reduction(g, tr, make_assoc_property_map(g_to_tr), id_map.data());

所以，它使用astd::map作为顶点关联图来传递g_to_tr。我们传递顶点 id-map，它只是增加每个顶点的 id。

• 有关属性映射的更多背景信息，请参阅将 set/get 请求映射到 C++ 类/结构更改

如果打印结果：

print_graph(g);
std::cout << "----------------------------\n";
for (auto& e : g_to_tr)
    std::cout << "Mapped " << e.first << " to " << e.second << "\n";
std::cout << "----------------------------\n";
print_graph(tr);

您可能会了解它的作用。

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/transitive_reduction.hpp>
#include <iostream>

#include <boost/graph/graph_utility.hpp> // dumping graphs
#include <boost/graph/graphviz.hpp>      // generating pictures

using namespace boost;

struct IQsNode { };
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, IQsNode*> Graph;

Graph make_random();

int main() {
    Graph const g = make_random();

    Graph tr;
    std::map<Graph::vertex_descriptor, Graph::vertex_descriptor> g_to_tr;
    std::vector<size_t> id_map(num_vertices(g));
    std::iota(id_map.begin(), id_map.end(), 0u);

    transitive_reduction(g, tr, make_assoc_property_map(g_to_tr), id_map.data());

    print_graph(g);
    std::cout << "----------------------------\n";
    for (auto& e : g_to_tr)
        std::cout << "Mapped " << e.first << " to " << e.second << "\n";
    std::cout << "----------------------------\n";
    print_graph(tr);

    // generating graphviz files
    { std::ofstream dot("g.dot");  write_graphviz(dot, g); }
    { std::ofstream dot("tr.dot"); write_graphviz(dot, tr); }
}

// generating test data
#include <boost/graph/random.hpp>
#include <random>
Graph make_random() {
    Graph g;
    std::mt19937 prng (std::random_device{}());
    generate_random_graph(g, 10, 5, prng);

    return g;
}

这是复制的[维基百科样本]：

Graph make_wikipedia() {
    Graph g;
    enum {a,b,c,d,e};
    add_edge(a,b,g);
    add_edge(a,c,g);
    add_edge(a,d,g);
    add_edge(a,e,g);
    add_edge(b,d,g);
    add_edge(c,d,g);
    add_edge(c,e,g);
    add_edge(d,e,g);
    return g;
}

这是 4 个随机生成的图及其传递约简的动画：