[C++] Write connected components of a graph using Boost Graph

Question

I have an file that is a long list of weighted edges, in the following form

node1_id node2_id weight
node1_id node3_id weight

and so on. So one weighted edge per line.

I want to load this file into boost graph and find the connected components in the graph. Each of these connected components is a subgraph. For each of these component subgraphs, I want to write a file that contains its edges in the above-described format. I want to do all this using boost graph.

This problem is in principle simple, it's just I'm not sure how to implement it neatly because I don't know my way around Boost Graph. I have already spent some hours and have code that will find the connected components, but my version is surely much longer and more complicated that necessary---I'm hoping there's a boost-graph ninja out there that can show me the right, easy way.

Because it was requested, here's the code I have so far. I don't think I'm using boost here in the most efficient or elegant way, and this solution is not complete (I don't take the subgraphs and print out each of their edges to separate files). #include #include #include #include #include #include

using namespace std;

typedef adjacency_list <vecS,
                        vecS,
                        undirectedS,
                        property<edge_weight_t float>
                        > AdjListGraph;

void writeConnectedComponents(char *filename)
{
  AdjListGraph G;
  ifstream inputFile;
  inputFile.open(filename);  
  unsigned int id1, id2;
  float weight;
  string lineread;
  stringstream ss;
  while(getline(inputFile, lineread))
    {
      ss.clear();
      ss.str("");
      ss << lineread;
      ss >> id1;
      ss >> id2;
      ss >> weight;
      add_edge(id1, id2, weight, G);
    }
  /* Following vector contains the component number of each node */
  vector<int> components(num_vertices(G));

Answer 1

I used Boost.Graph to build Gnocchi.

The learning curve is quite steep. Getting the book on this library is essential I think. What helped me learn about the library is to actually modify it to make it do what I wanted. Later I found out how to use it properly. I touched only a small part of the library but the way they did things is very interesting. There are also bindings for Python, so I think it is worth it to spend some time learning it.