促进BGL传递减少 [英] Boost BGL Transitive reduction

问题描述

我尝试使用boosting的transiveive_reduction，但我不知道如何使用它.

I try to use the transitive_reduction of boost, but I don't know how to use it.

我有一个用定义的图:

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"使用的类型.

I don't know the type I must use for "g_to_tr_map_stor" and "g_to_tc_map_stor".

根据我阅读的信息，它必须是来自顶点的地图
到整数.我尝试了多种地图，但没有成功.

According with information i readed , it must be a map from vertices
to integers. I try many kind of map but without success.

一些想法?

Thx

推荐答案

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

As far as my documentation tells me this is not public API. This implies that you can find the place where it's being used internally and use that as an example of how to use it.

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

Interestingly, this is not the case. This might lead one to think that the documentation is lagging/forgotten

注意，使用未公开的API表面可能会在升级时破坏您的代码，恕不另行通知.

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

这是满足接口的最简单的方法:

Here's the simplest thing I could think of to satisfy the 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映射，该映射只是为每个顶点增加ID.

So, it uses a std::map to pass as the g_to_tr vertex association map. And we pass and vertex id-map that is just increasing ids for each vertex.

• 请参阅将地图设置/获取请求C ++类/结构更改以获取属性图的更多背景

• See map set/get requests into C++ class/structure changes for more background on property maps

如果您打印结果:

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

您可能会了解它的作用.

You may get an idea of what it does.

在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;
}

以下是[Wikipedia示例]的转载:

Here is the [Wikipedia sample] reproduced:

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张图及其传递减少量的动画:

Here's an animation of 4 of the randomly generated graphs and their transitive reductions:

这篇关于促进BGL传递减少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！