我在过滤原始图中具有相同组件的子图时遇到问题。我想将它们输出到子图 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

如何从同一连接组件中的节点输出诱导子图?

最佳答案

您可以使用主图的 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; }
};

对于两者之一。这是一个示例主要:
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 lambdas 可以使代码显着缩短,因为您可以就地定义过滤谓词:

看到它 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;
}

关于c++ - 返回 Boost Graph 中连通分量子图的列表,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/26763193/

10-11 12:21