提升 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

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

有趣的是，事实并非如此。这可能会让人认为文档是 lagging/forgotten

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

这是我能想到的满足接口的最简单的东西：

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

提升 BGL 传递减少

Boost BGL Transitive reduction

c++

boost

graph-theory

boost-graph

transitive-closure