boost::filtered_graph调用时print_graph与write_graphviz输出不一致求助

核心错误 #

你定义的uniform_random_vertex_filter顶点过滤器是非确定性的：每次调用operator()判断同一个顶点时，都会重新执行drand48() < prob生成随机结果，无法保证同一个顶点的多次判断结果一致。
而Boost Graph库的不同工具函数（print_graph、copy_graph、write_graphviz）内部会多次调用过滤器判断同一个顶点/边的合法性，两次判断结果不同就会出现输出不一致的问题。

你遇到的现象解释 #

1. 执行print_graph时，遍历顶点和边的过程中对每个顶点的判断次数较少，本次运行时刚好判断边的起点、终点都返回true，因此打印出了完整的边列表。
2. 执行copy_graph时，第一步先遍历所有顶点筛选要保留的节点，本次运行时刚好0、1、2返回true被保留，3、4返回false被丢弃；后续遍历边筛选要复制的边时，会再次调用过滤器判断边的起点、终点是否合法，此时再次随机判断的结果与第一次不同，最终所有边都不满足“起点和终点都被保留”的条件，因此复制得到的图F只有顶点没有边。

修复方案 #

提前缓存每个顶点的随机筛选结果，保证同一个顶点每次调用过滤器返回的结果完全一致，修改后的过滤器代码如下：

template <typename GraphType>
struct uniform_random_vertex_filter
{
    uniform_random_vertex_filter() : prob(1.0) {}   // 保留要求的默认构造函数
    uniform_random_vertex_filter(float p, const GraphType& g) : prob(p) {
        // 提前为每个顶点生成随机筛选结果并缓存
        std::size_t v_cnt = boost::num_vertices(g);
        vertex_keep.reserve(v_cnt);
        for (std::size_t i = 0; i < v_cnt; ++i) {
            vertex_keep.push_back(drand48() < prob);
        }
    }
    bool operator()(const typename boost::graph_traits<GraphType>::vertex_descriptor& v) const
    {
        // 直接返回预先生成的缓存结果，保证多次调用结果一致
        return vertex_keep[v];
    }
private:
    float prob = 1.0;
    std::vector<bool> vertex_keep;
};

对应修改过滤器实例化的代码：

// 传入原始图g用于预生成筛选结果
uniform_random_vertex_filter<Graph> vfilter(0.5, g);

额外优化建议 #

如果不需要对过滤后的图做修改，完全可以跳过copy_graph步骤，直接把filtered_graph传给write_graphviz导出，性能开销更低，只要过滤器是确定性的，导出结果和print_graph输出完全一致。

内容的提问来源于stack exchange，提问作者mcharleston