c++ - 使用 Boost Graph 编写图形的连接组件

Question

我有一个文件是一长串加权边，格式如下

node1_id node2_id weight
node1_id node3_id weight

等等。所以每行一个加权边。

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

这个问题原则上很简单，只是我不确定如何巧妙地实现它，因为我不知道如何绕过 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)，所以我认为花一些时间学习它是值得的。