c++ - 使用 Boost Graph 编写图的连通分量

Question

我有一个文件，其中包含一长串加权边，格式如下

node1_id node2_id weight
node1_id node3_id weight

等等。因此每行一个加权边。

我想将此文件加载到 boost 图中并找到图中的连接组件。每个连接的组件都是一个子图。对于每个组件子图，我想编写一个包含上述格式的边的文件。我想使用 boost graph 来完成这一切。

这个问题原则上很简单，只是我不确定如何巧妙地实现它，因为我不知道 Boost Graph 的方法。我已经花了几个小时并编写了可以找到连接组件的代码，但我的版本肯定比必要的更长、更复杂——我希望有一个 boost-graph ninja 可以向我展示正确的，简单的方法。

因为有人要求，所以这是我到目前为止所拥有的代码。我不认为我在这里以最有效或最优雅的方式使用 boost，并且这个解决方案并不完整(我没有获取子图并将其每个边缘打印到单独的文件中)。 ＃包括 ＃包括 ＃包括 ＃包括 ＃包括 #包括

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

我使用Boost.Graph来构建Gnocchi .

学习曲线相当陡峭。我认为在这个图书馆获取这本书是至关重要的。帮助我了解这个库的是实际修改它以使其达到我想要的效果。后来我才知道如何正确使用它。我只接触了图书馆的一小部分，但他们做事的方式很有趣。还有Python的绑定(bind)，所以我认为花一些时间学习它是值得的。