2

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」に使用するタイプがわかりません。


私が読んだ情報によると、それは頂点から整数へのマップでなければなりません。さまざまな種類のマップを試しましたが、成功しませんでした。

いくつかのアイデア？

どうも

4

1 に答える 1

4

私のドキュメントによると、これはパブリック 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());

そのため、a を使用して頂点関連付けマップstd::mapとして渡します。g_to_trそして、各頂点の ID を増やすだけの頂点 id-map を渡します。

結果を印刷する場合:

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 つのグラフとそれらの推移的還元のアニメーションです。

于 2015-03-22T22:17:25.147 に答える