c++ - 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”必须使用的类型。

根据我看的资料，应该是顶点映射
到整数。我尝试了多种 map 但没有成功。

一些想法？

谢谢

Answer 1

就我的文档而言，这不是公共(public) API。这意味着您可以找到内部使用它的地方，并将其用作如何使用它的示例。

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

CAVEAT Using undocumented API surface risks breaking your code on upgrade, without notice.

这是我能想到的满足接口(interface)的最简单的方法:

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());

因此，它使用 std::map 作为 g_to_tr 顶点关联映射传递。我们传递和顶点 id-map，它只是增加每个顶点的 id。

• 参见 map set/get requests into C++ class/structure changes有关属性图的更多背景信息

如果打印结果:

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 个随机生成的图形及其传递归约的动画: