据我的文档告诉我,这不是公共 API。这意味着您可以找到内部使用它的地方,并将其用作如何使用它的示例。
有趣的是,事实并非如此。这可能会导致人们认为文档滞后/被遗忘
CAVEAT使用未记录的 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-map,它只是增加每个顶点的 id。
如果打印结果:
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 个随机生成的图形及其传递缩减的动画:
