c++ - 返回 Boost Graph 中连接的组件子图的列表

Question

我在过滤原始图中具有相同组件的子图时遇到问题。我想将它们输出到子图的 vector 中。按照 `connected_components 中的示例，我尝试使其适应我的需要:

// Create a typedef for the Graph type
typedef adjacency_list<
vecS,
vecS,
undirectedS,
property<vertex_index_t,int >,
property<edge_index_t,int> > Graph;

//typedef subgraph < Graph > SubGraph;
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
typedef graph_traits<Graph> GraphTraits;

// Iterators
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef property_map<Graph, vertex_index_t>::type VertexIndexMap;
typedef property_map<Graph, edge_index_t>::type EdgeIndexMap;

std::vector<Graph> connected_components_subgraphs(const Graph &g)
{
    std::vector<int> component(num_vertices(g));
    int num = boost::connected_components(g, &component[0]);
    for (int i=0; i<component.size(); i++)
        cout << component[i] << endl;
    cout << "NUM=" << num << endl;

    // Something to output the induced subgraphs where every subgraph is in the same component
}

我完全陷入了图的过滤，因为我不明白为 vector 组件中的顶点存储的外部属性如何被利用或传递给过滤图所需的某些仿函数.

特别是，这个问题好像和我的需求很像，但是没有代码，我发现问题很难搞清楚。

splitting a boost graph into connected components

如何从同一连通分量中的节点输出导出的子图？

Answer 1

您可以使用主图的 filtered_graph View :

typedef filtered_graph<Graph, EdgeInComponent, VertexInComponent> ComponentGraph;

std::vector<ComponentGraph> connected_components_subgraphs(Graph const&g)
{
    vertex_component_map mapping = boost::make_shared<std::vector<unsigned long>>(num_vertices(g));
    size_t num = boost::connected_components(g, mapping->data());

    std::vector<ComponentGraph> component_graphs;

    for (size_t i = 0; i < num; i++)
        component_graphs.push_back(ComponentGraph(g, EdgeInComponent(mapping, i, g), VertexInComponent(mapping, i)));

    return component_graphs;
}

当然，这只是回避了如何实现过滤谓词的问题。我选择共享 mapping vector :

typedef boost::shared_ptr<std::vector<unsigned long>> vertex_component_map;

我不想假设您可以共享全局或只是复制它。例如，VertexInComponent 谓词如下所示:

struct VertexInComponent
{ 
    vertex_component_map mapping_;
    unsigned long which_;

    VertexInComponent(vertex_component_map m, unsigned long which)
        : mapping_(m), which_(which) {}

    template <typename Vertex> bool operator()(Vertex const&v) const {
        return mapping_->at(v)==which_;
    } 
};

同样可以实现EdgeInComponent。事实上，您可能可以将其快捷方式并使用类似的东西

struct AnyElement { 
    template <typename EdgeOrVertex> bool operator()(EdgeOrVertex const&) const { return true; }
};

两者之一。这是一个示例 main:

Graph g;

add_edge(0, 1, g);
add_edge(1, 4, g);
add_edge(4, 0, g);
add_edge(2, 5, g);

for (auto const& component : connected_components_subgraphs(g))
{
    std::cout << "component [ ";
    for (auto e :  make_iterator_range(edges(component)))
        std::cout << source(e, component) << " -> " << target(e, component) << "; ";
    std::cout << "]\n";
}

它打印:

component [ 0 -> 1; 1 -> 4; 4 -> 0; ]
component [ 2 -> 5; ]
component [ ]

完整代码

查看 Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/make_shared.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>

using namespace boost;

// Create a typedef for the Graph type
typedef adjacency_list<vecS, vecS, undirectedS, property<vertex_index_t, int>, property<edge_index_t, int>> Graph;

// typedef subgraph < Graph > SubGraph;
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
typedef graph_traits<Graph> GraphTraits;

// Iterators
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef property_map<Graph, vertex_index_t>::type VertexIndexMap;
typedef property_map<Graph, edge_index_t>::type EdgeIndexMap;

typedef boost::shared_ptr<std::vector<unsigned long>> vertex_component_map;

struct EdgeInComponent
{ 
    vertex_component_map mapping_;
    unsigned long which_;
    Graph const& master_;

    EdgeInComponent(vertex_component_map m, unsigned long which, Graph const& master) 
        : mapping_(m), which_(which), master_(master) {}

    template <typename Edge> bool operator()(Edge const&e) const {
        return mapping_->at(source(e,master_))==which_
            || mapping_->at(target(e,master_))==which_;
    } 
};

struct VertexInComponent
{ 
    vertex_component_map mapping_;
    unsigned long which_;

    VertexInComponent(vertex_component_map m, unsigned long which)
        : mapping_(m), which_(which) {}

    template <typename Vertex> bool operator()(Vertex const&v) const {
        return mapping_->at(v)==which_;
    } 
};

struct AnyVertex { 
    template <typename Vertex> bool operator()(Vertex const&) const { return true; }
};

typedef filtered_graph<Graph, EdgeInComponent, VertexInComponent> ComponentGraph;

std::vector<ComponentGraph> connected_components_subgraphs(Graph const&g)
{
    vertex_component_map mapping = boost::make_shared<std::vector<unsigned long>>(num_vertices(g));
    size_t num = boost::connected_components(g, mapping->data());

    std::vector<ComponentGraph> component_graphs;

    for (size_t i = 0; i < num; i++)
        component_graphs.push_back(ComponentGraph(g, EdgeInComponent(mapping, i, g), VertexInComponent(mapping, i)));

    return component_graphs;
}

int main()
{
    Graph g;

    add_edge(0, 1, g);
    add_edge(1, 4, g);
    add_edge(4, 0, g);
    add_edge(2, 5, g);

    for (auto const& component : connected_components_subgraphs(g))
    {
        std::cout << "component [ ";
        for (auto e :  make_iterator_range(edges(component)))
            std::cout << source(e, component) << " -> " << target(e, component) << "; ";
        std::cout << "]\n";
    }
}

奖励:c++11

如果您可以使用 C++11 lambda 可以大大缩短代码，因为您可以就地定义过滤器谓词:

查看 Live On Coliru

typedef filtered_graph<Graph, function<bool(Graph::edge_descriptor)>, function<bool(Graph::vertex_descriptor)> > ComponentGraph;

std::vector<ComponentGraph> connected_components_subgraphs(Graph const&g)
{
    vertex_component_map mapping = boost::make_shared<std::vector<unsigned long>>(num_vertices(g));
    size_t num = boost::connected_components(g, mapping->data());

    std::vector<ComponentGraph> component_graphs;

    for (size_t i = 0; i < num; i++)
        component_graphs.emplace_back(g,
            [mapping,i,&g](Graph::edge_descriptor e) {
                return mapping->at(source(e,g))==i
                    || mapping->at(target(e,g))==i;
            }, 
            [mapping,i](Graph::vertex_descriptor v) {
                return mapping->at(v)==i;
            });

    return component_graphs;
}