Return a list of connected component subgraphs in Boost Graph

Question

I'm having problems in filtering the subgraphs with the same component in the original graph. I want to output them in a vector of subgraphs. Following the example in `connected_components I've tried to adapt it to me needs:

// 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
}

I'm totally stuck in the filtering of the graph, because I don't understand how an external property that is stored for the vertices in the vector component, can be exploited or passed to some functor needed to the filter the graph.

In particular, it seems that this question is very similar to my needs, but with no pieces of code I find it very difficult to figure out the problem.

splitting a boost graph into connected components

How can I output the induced subgraphs from the nodes in the same connected component?

Answer 1

You could use filtered_graph views of the main graph:

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;
}

Of course, this just begs the question how to implement the filter predicates. I opted to share the mapping vector:

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

I didn't want to assume that you could share a global or just copy it around. For example, the VertexInComponent predicate looks like:

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_;
    } 
};

Similarly, the EdgeInComponent can be implemented. In fact, you can probably shortcut it and use something like

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

for one of the two. Here's a sample 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";
}

And it prints:

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

Full Code

See it 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";
    }
}

Bonus: c++11

If you can use C++11 lambdas can make the code considerably shorter because you can define the filter predicates in-place:

See it 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;
}

Answer 2

Instead of filtered_graph, you can use subgraph as follows:

vector<int> comp(num_vertices(g));
size_t num = boost::connected_components(g, comp.data());

vector<Graph*> comps(num);
for(size_t i=0;i<num;++i) {
    comps[i] = & g.create_subgraph();
}

for(size_t i=0;i<num_vertices(g);++i) {
    add_vertex(i, *comps[comp[i]]);
}

where Graph is defined as:

using Graph = subgraph< adjacency_list<vecS, vecS, undirectedS, property<vertex_index_t, int>, property<edge_index_t, int>> >;

Note that you'll need to use local_to_global to map vertex descriptors from the subgraph to the root graph.

Running example: http://coliru.stacked-crooked.com/a/cebece41c0daed87

It would be interesting to know the merits of filtered_graph vs subgraph in this case.