number of vertex in every component- boost library

Question

im kind of new with boost library (windows 7\ visual studio 2010). I followed this example code:

#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>


using namespace std;

int main(int , char* []) 
{
  using namespace boost;
  {
    typedef adjacency_list <vecS, vecS, undirectedS> Graph;

    Graph G;
    add_edge(0, 1, G);
    add_edge(1, 4, G);
    add_edge(4, 0, G);
    add_edge(2, 5, G);
    
    std::vector<int> component(num_vertices(G));

    int num = connected_components(G, &component[0]);
    
    std::vector<int>::size_type i;
    cout << "Total number of components: " << num << endl;
    for (i = 0; i != component.size(); ++i)
      cout << "Vertex " << i <<" is in component " << component[i] << endl;
    cout << endl;
  }
  return 0;
}

the code builds the graph and prints which vertex belongs to which component by the for loop.

is there an example of function that gets a graph and returns\ stores which vertex belongs to which component- in organized way(some kind of data structure)? and not with for loop?

I tried to search here, hope I didn't miss it.

thanks.

EDIT: the goal is to take measurements on every component (such as number of nodes, diameter, number of neighbors for every node in one component..)

score 0 · Answer 1 · edited May 23 '17 at 11:43

0

I'd suggest using an associative property map:

std::map<Graph::vertex_descriptor, Graph::vertices_size_type> map;

auto const num = connected_components(G, make_assoc_property_map(map));
std::cout << "Total number of components: " << num << std::endl;

for (auto& e : map)
    std::cout << "Vertex " << e.first << " is in component " << e.second << std::endl;

Of course, now the mystery is, how do you effectively get the reverse map?

^{(meanwhile, life happens...)}

Sorry ran out of steam writing this. Here's a link to an earlier write up that hopefully serves as inspiration to get the bidirectional associative writable property map (in the context of another BGL call, but you can hopefully imagine the connection).

Cut set of a graph, Boost Graph Library

Slightly related samples:

edited May 23 '17 at 11:43

Community

1
1

answered Apr 19 '15 at 20:29

sehe

374,641
47
450
633

Hi, thank you for your answer, the main issue is to take every component (component- connected sub graph) as input to function that returns number of nodes\ diameter\ number of neighbors for every node in one component etc... so i guess that component (connected sub graph) is supposed to be in some kind of BGL data structure (as input to other BGL function)? – user1673206 Apr 20 '15 at 19:14
I think you'll have to arragne for this data structure. The algorithm doesn't assume you wish to incur the "extra" cost. I suppose you could write a property map adaptor that directly writes the components into proper subgraphs, but I'd not optimize that far unless I were absolutely sure I needed it. And in that case I might consider optimizing the actual `connected_component` algorithm (adapting _it_ to your needs) to keep things simpler – sehe Apr 20 '15 at 20:58

number of vertex in every component- boost library

1 Answers1