使用Boost Graph库查找连接的组件，其顶点和边类型为boost :: listS [英] Find connected components using Boost Graph library, with the vertex and edge type being boost::listS

问题描述

我正在尝试在无向图中找到连接的组件.该图由boost::adjacency_list表示.对于我的应用程序，顶点和边类型必须为boost::listS.我尝试了以下代码，但无法编译.但是，如果将顶点和边类型更改为boost::vecS，则代码将正常工作.关于如何修复代码有任何想法吗?

I am trying to find connected components in an undirected graph. The graph is represented by boost::adjacency_list. For my application, the vertex and edge type have to be boost::listS. I tried the following code, which doesn't compile. However, if I change the vertex and edge type to boost::vecS, the code will just work fine. Any idea on how to fix the code?

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
typedef boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS> Cluster;
int main() {
    using namespace boost;
    Cluster A;
    add_vertex(A);
    add_vertex(A);
    add_vertex(A);
    add_vertex(A); // add 4 vertex to the graph

    for (int i=0; i<2; i++){
        for (int j=(i+1); j<3; j++){
            std::cout<<i<<"  "<<j<<"\n";
            add_edge(vertex(i,A), vertex(j,A), A);
        }
    } // add edge between 0-1, 0-2, 1-2.

    std::vector<int> subclusters(num_vertices(A));
    int nclusters=boost::connected_components(A, &subclusters[0]); // find the connected components
}    

推荐答案

文档说¹组件映射需要使用键vertex_descriptor为可写属性映射建模，并将组件ID存储为值.

The docs say¹ the component map needs to model a writable property map with key vertex_descriptor and storing the compoment id as value.

您可能应该在地图上使用make_assoc_property_map:

You should probably use make_assoc_property_map with a map:

在Coliru上直播

std::map<Cluster::vertex_descriptor, int> subclusters;
int nclusters = boost::connected_components(A, boost::make_assoc_property_map(subclusters)); // find the connected components


for (auto& p : subclusters) {
    std::cout << "Vertex " << boost::get(boost::vertex_index, A, p.first) << " is in cluster " << p.second << "\n";
}

打印:

0 -- 1
0 -- 2
1 -- 2
Vertex 0 is in cluster 0
Vertex 1 is in cluster 0
Vertex 2 is in cluster 0
Vertex 3 is in cluster 1

但是我想要一个向量

如果您坚持要使用向量BUT，则必须提供从vertex-descriptor到整数vertex id的映射:

But I Want A Vector

If you insist, you can still use a vector BUT you'll have to provide the mapping from vertex-descriptor to an integral vertex id:

typedef boost::adjacency_list<
        boost::listS,
        boost::listS,
        boost::undirectedS,
        boost::property<boost::vertex_index_t, int>
    > Cluster;

现在，您也必须填写该属性:

Now, you have to fill that property too:

Cluster A;
add_vertex(0, A);
add_vertex(1, A);
add_vertex(2, A);
add_vertex(3, A);

然后必须使用make_iterator_property_map代替，为间接提供顶点索引属性映射:

And then you have to use make_iterator_property_map instead, supplying a vertex index property-map for the indirection:

std::vector<int> subclusters(4);
auto comp_map = make_iterator_property_map(subclusters.begin(), get(boost::vertex_index, A));
int nclusters = connected_components(A, comp_map); // find the connected components

在Coliru上直播

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

typedef boost::adjacency_list<
        boost::listS,
        boost::listS,
        boost::undirectedS,
        boost::property<boost::vertex_index_t, int>
    > Cluster;

int main() {
    Cluster A;
    add_vertex(0, A);
    add_vertex(1, A);
    add_vertex(2, A);
    add_vertex(3, A);

    for (int i = 0; i < 2; i++) {
        for (int j = (i + 1); j < 3; j++) {
            std::cout << i << " -- " << j << "\n";
            add_edge(vertex(i, A), vertex(j, A), A);
        }
    } // add edge between 0-1, 0-2, 1-2.

    // NOTE: 4, not "num_vertices", but enough to accomodate the highest value
    // of the `vertex_index` property
    std::vector<int> subclusters(4);
    auto comp_map = make_iterator_property_map(subclusters.begin(), get(boost::vertex_index, A));
    int nclusters = connected_components(A, comp_map); // find the connected components

    for (size_t id = 0; id < subclusters.size(); ++id) {
        std::cout << "Vertex id " << id << " is in cluster " << subclusters.at(id) << "\n";
    }
}

打印

0 -- 1
0 -- 2
1 -- 2
Vertex id 0 is in cluster 0
Vertex id 1 is in cluster 0
Vertex id 2 is in cluster 0
Vertex id 3 is in cluster 1

---

¹

---

¹

这篇关于使用Boost Graph库查找连接的组件，其顶点和边类型为boost :: listS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！