Boost Graph能否根据权重求连通分量？

Question

我成功地使用了 boost graph 的组件查找器来分配颜色，即组件的索引到我的图中的每个顶点，如下所示：

#include <boost/graph/connected_components.hpp>
#include <boost/graph/adjacency_list.hpp>

boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> g;

std::vector<int> compon_map(boost::num_vertices(g));

int number_of_components = boost::connected_components(g, &compon_map[0]);

这将在我的模拟（未显示）中的每次迭代后产生不同的 number_of_components，因为我这样做

boost::clear_vertex(v, g);

在两者之间根据某些条件擦除一些边缘。

问题是在我的模拟中我想写出所有边的一些属性（比如权重），并且边迭代器的长度需要保持不变（数据集限制）。

因此我的问题是：有没有办法像

那样通过一些边属性

int L = boost::num_edges(g);

std::vector<bool> is_still_existent(L); // or
std::vector<double> edge_weights(L);

到 boost::connected_components（然后仅根据属性对边进行计数）还是有另一种方法来欺骗边迭代器即使在删除边后仍保持初始长度？

提前感谢任何提示:)

Answer 1

是的。您可以使用带边缘过滤器的过滤图形适配器。我有几个答案 up on SO 展示了如何使用它，但我会看看我是否可以根据您的代码段创建一个有用的示例。

所以我做了一个独立的示例¹：Live On Coliru，

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/graphviz.hpp>
#include <random>

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;
using W = double;

int main(int argc, char** argv) {
    G g;
    auto seed = 9353; // fixed seed for demo
    if (argc > 1) {
        seed = atol(argv[1]);
        std::cerr << "Using PRNG seed: " << seed << "\n";
    }

    std::mt19937 engine(seed);
    auto weight_gen = bind(std::uniform_real_distribution<W>(0, 1), engine);
    boost::generate_random_graph(g, 10, 6, engine);

    std::map<E, W> weights;

    for (auto e : boost::make_iterator_range(edges(g)))
        weights[e] = weight_gen();
    
    std::vector<int> components(boost::num_vertices(g));
    auto cmap = boost::make_iterator_vertex_map(components.data());


    int n = boost::connected_components(g, cmap);

    std::cerr << n << " components\n";

    boost::dynamic_properties dp;
    dp.property("node_id", get(boost::vertex_index, g));
    dp.property("style", boost::make_constant_property<V>(std::string("filled")));
    dp.property("color",
                boost::make_transform_value_property_map(
                    [](int componentid) {
                        static std::array cc{"red",    "green", "yellow",
                                             "blue",   "brown", "black",
                                             "orange", "purple"};
                        return cc[componentid % cc.size()];
                    },
                    cmap));
    dp.property("label", boost::make_assoc_property_map(weights));

    boost::write_graphviz_dp(std::cout, g, dp);
}

生成伪随机图：

让我们添加一些过滤：

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/graphviz.hpp>
#include <random>

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;
using W = double;

struct NonRemoved {
    std::set<E> const* _ref;
    bool operator()(E e) const { return not _ref->contains(e); }
};

int main(int argc, char** argv)
{
    G g;
    auto seed = 9353; // fixed seed for demo
    if (argc > 1) {
        seed = atol(argv[1]);
        std::cerr << "Using PRNG seed: " << seed << "\n";
    }

    std::mt19937 engine(seed);
    auto weight_gen = bind(std::uniform_real_distribution<W>(0, 1), engine);
    boost::generate_random_graph(g, 10, 6, engine);

    std::map<E, W> weights;

    for (auto e : boost::make_iterator_range(edges(g)))
        weights[e] = weight_gen();
    
    std::vector<int> components(boost::num_vertices(g));
    auto cmap = boost::make_iterator_vertex_map(components.data());

    auto random_edges = [&g] {
        auto [f,l] = edges(g);
        std::deque<E> re(f,l);
        std::random_shuffle(begin(re), end(re));
        return re;
    }();

    std::set<E> removed;
    NonRemoved predicate{&removed};

    boost::filtered_graph<G, NonRemoved, boost::keep_all> f(g, predicate, {});
    do {
        int n = boost::connected_components(f, cmap);
        std::cerr << n << " components\n";

        boost::dynamic_properties dp;
        dp.property("node_id", get(boost::vertex_index, f));
        dp.property("style", boost::make_constant_property<V>(std::string("filled")));
        dp.property("color",
                    boost::make_transform_value_property_map(
                        [](int componentid) {
                            static std::array cc{"red",    "green", "yellow",
                                                 "blue",   "brown", "black",
                                                 "orange", "purple"};
                            return cc[componentid % cc.size()];
                        },
                        cmap));
        dp.property("color",
                    boost::make_function_property_map<E>([&removed](E e) {
                        return removed.contains(e) ? "red" : "blue";
                    }));
        dp.property("label",
            boost::make_function_property_map<E>([&removed, &weights](E e) {
                if (removed.contains(e))
                    return std::string("REMOVED");
                return std::to_string(weights.at(e));
            }));

        std::ofstream ofs("graph_" + std::to_string(random_edges.size()) + ".dot");
        boost::write_graphviz_dp(ofs, f, dp);

        removed.insert(random_edges.front());
        random_edges.pop_front();
    } while (not random_edges.empty());
}

现在写一系列 graph_XXX.dot 图表显示为：

¹（更改）

Boost Graph能否根据权重求连通分量？

Can Boost Graph Find Connected Components Based on Weight?

c++

boost

adjacency-list

boost-graph

connected-components