Boost Graph 可以根据权重找到连通分量吗?

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

#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 (然后仅根据该属性计算边)还是有另一种方法来欺骗边迭代器即使在删除边后仍保持初始长度?

预先感谢您的任何提示:)

iCMS 回答:Boost Graph 可以根据权重找到连通分量吗?

是的。您可以使用带边缘过滤器的过滤图形适配器。我有几个答案 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);
}

生成伪随机图:

enter image description here

让我们为它添加一些过滤:

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::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,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",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","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 图形,显示为:

enter image description here


¹(更改 vertex container selector to vecS for simplicity

本文链接:https://www.f2er.com/451280.html

大家都在问