我正在使用 boost::filtered_graph，但 print_graph 和 write_graphviz 的输出不同——知道为什么吗？

Question

我是 boost::graph 的新手（真的是 boost）。我想在同一个原始图上多次使用 boost::filtered_graph，并使用 write_graphviz 函数让我可视化结果。我想我的理解一定是错误的，因为下面的代码没有做我认为应该做的事情：用 print_graph 和 write_graphviz.

输出相同的图形

MWE（在 Ubuntu 20.04 上使用 C++14、gcc 9.3 编译；boost 版本 1.73）：

#include <cstdio>
#include <fstream>
#include <iostream>

#include <boost/graph/copy.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/graphviz.hpp>

using namespace std;

typedef boost::adjacency_list< boost::vecS, boost::vecS > Graph;

typedef boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Graph>::vertex_iterator vertex_iterator;

template <typename GraphType>
struct uniform_random_vertex_filter
{
    uniform_random_vertex_filter() : prob(1.0) {}   // default constructor is required
    uniform_random_vertex_filter(float p) : prob(p) {}
    bool operator()(const typename boost::graph_traits<GraphType>::vertex_descriptor& v) const
    {
        return drand48() < prob; // randomly select some vertices
    }
private:
    float prob;
};

int main(int argn, char **argc) {
    unsigned int n = 5;
    ofstream of;
    Graph g(n);
    vertex_iterator vit, uit, vend;
    // build a complete graph on n vertices (I'm sure there's a simpler command for this):
    for (boost::tie(vit,vend) = vertices(g); vit != vend; ++vit) {
        for (uit = vit; uit != vend; ++uit) {
            if (uit == vit) { continue; }
            add_edge(*vit, *uit, g);
        }
    }
    std::cout << "Original graph (OriginalGraph.dot):" << std::endl;
    boost::print_graph(g);
    of.open("OriginalGraph.dot", std::ios::trunc);
    boost::write_graphviz(of, g);
    of.close();

    uniform_random_vertex_filter<Graph> vfilter(0.5);

    boost::filtered_graph<Graph, boost::keep_all, uniform_random_vertex_filter<Graph> >
        filteredGraph(g, boost::keep_all(), vfilter);
    std::cout << "Filtered graph -- random selection of vertices (RandomVertexSelection.dot):" << std::endl;
    boost::print_graph(filteredGraph);
    Graph F;
    boost::copy_graph(filteredGraph,F);
    of.open("RandomVertexSelection.dot", std::ios::trunc);
    boost::write_graphviz(of, F);
    of.close();
    return 0;
}

产生此输出：

> Debug/BoostGraphFilter
Original graph:
0 --> 1 2 3 4 
1 --> 2 3 4 
2 --> 3 4 
3 --> 4 
4 --> 
Filtered graph -- random selection of vertices (RandomVertexSelection.dot):
0 --> 1 2 3 4 
1 --> 2 3 
2 --> 3 
>

--- 很好，但是点文件是：

> cat OriginalGraph.dot 
digraph G {
0;
1;
2;
3;
4;
0->1 ;
0->2 ;
0->3 ;
0->4 ;
1->2 ;
1->3 ;
1->4 ;
2->3 ;
2->4 ;
3->4 ;
}
> cat RandomVertexSelection.dot
digraph G {
0;
1;
2;
}

因此 打印的 filtered_graph 与写入 .dot 文件的内容不同（在这种情况下丢失了所有边缘） .

有人可以帮我理解我做错了什么吗？

Answer 1

您的过滤器是随机的。由于您没有保留任何状态来使其透明或确定，因此结果是随机的。就这么简单。

具有讽刺意味的是，同时你设法在运行秒内获得了完全确定的结果，因为你未能正确使用随机数（例如为生成器播种）。

对于您的情况，最简单的方法是在首次使用前复制：Live On Coliru

using Graph = boost::adjacency_list<boost::vecS, boost::vecS>;

Graph make_complete_graph(size_t n);
void  report(Graph const& g, std::string name);

struct uniform_random_vertex_filter {
    float prob = 1.0f;
    bool  operator()(auto v) const {
        return drand48() < prob;
    }
};

int main() {
    Graph g = make_complete_graph(5);

    report(g, "OriginalGraph");

    for (int pct = 30; pct < 100; pct+=10) {
        Graph F;

        boost::copy_graph(boost::filtered_graph( //
                              g,                 //
                              boost::keep_all{},
                              uniform_random_vertex_filter{pct / 100.0f}),
                          F);

        report(F, "RandomVertexSelection_" + std::to_string(pct));
    }
}

// build a complete graph on n vertices
Graph make_complete_graph(size_t n)
{
    Graph g(n);
    for (auto [vit, vend] = vertices(g); vit != vend; ++vit) {
        for (auto uit = vit; uit != vend; ++uit) {
            if (uit != vit)
                add_edge(*vit, *uit, g);
        }
    }
    return g;
}

void report(Graph const& g, std::string name) {
    boost::print_graph(g, std::cout << name << ":");

    std::ofstream of(name + ".dot");
    boost::write_graphviz(of, g);
}

如果您想要稳定图形的随机“切割”，请使过滤器有状态。这可能很方便，例如如果您的图表太大而无法复制。

修复随机数

作为旁注，将随机数固定为实际播种并可靠地统一：

Live On Coliru

#include <boost/graph/copy.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/graphviz.hpp>
#include <fstream>
#include <iostream>
#include <random>

using Graph = boost::adjacency_list<boost::vecS, boost::vecS>;
using Filter = std::function<bool(Graph::vertex_descriptor)>;

Graph make_complete_graph(size_t n);
void  report(Graph const& g, std::string name);

int main() {
    Graph g = make_complete_graph(5);

    report(g, "OriginalGraph");

    std::mt19937 urbg{std::random_device{}()};

    for (int pct = 30; pct < 100; pct += 10) {
        Graph F;
        std::bernoulli_distribution dist(pct / 100.);
        boost::copy_graph(
            boost::filtered_graph(g, boost::keep_all{},
                Filter([&](auto) { return dist(urbg); })),
            F);

        report(F, "RandomVertexSelection_" + std::to_string(pct));
    }
}

// build a complete graph on n vertices
Graph make_complete_graph(size_t n)
{
    Graph g(n);
    for (auto [vit, vend] = vertices(g); vit != vend; ++vit) {
        for (auto uit = vit; uit != vend; ++uit) {
            if (uit != vit)
                add_edge(*vit, *uit, g);
        }
    }
    return g;
}

void report(Graph const& g, std::string name) {
    boost::print_graph(g, std::cout << name << ":");

    std::ofstream of(name + ".dot");
    boost::write_graphviz(of, g);
}

现在每运行打印不同的随机剪切。

我正在使用 boost::filtered_graph，但 print_graph 和 write_graphviz 的输出不同——知道为什么吗？

I'm using boost::filtered_graph, but the output of print_graph and write_graphviz differ -- any idea why?

c++

boost-graph

修复随机数