1

在 listS 而不是 vecS 上做强连通分量的图的例子并不多。这是 vecS 的等效示例

#include <boost/config.hpp>
#include <vector>
#include <iostream>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/adjacency_list.hpp>

int
main()
{
  using namespace boost;
  typedef adjacency_list < vecS, vecS, directedS > Graph;
  const int N = 6;
  Graph G(N);
  add_edge(0, 1, G);
  add_edge(1, 1, G);
  add_edge(1, 3, G);
  add_edge(1, 4, G);
  add_edge(3, 4, G);
  add_edge(3, 0, G);
  add_edge(4, 3, G);
  add_edge(5, 2, G);

  std::vector<int> c(N);

  int num = strong_components
    (G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));

    auto l=get(vertex_index, G);

  std::cout << "Total number of components: " << num << std::endl;
  std::vector < int >::iterator i;
  for (i = c.begin(); i != c.end(); ++i)
    std::cout << "Vertex " << i - c.begin()
      << " is in component " << *i << std::endl;
  return EXIT_SUCCESS;
}

但是当我从 vecS 更改为 listS 时，它会中断。我知道问题是由于顶点索引和输出向量索引中的某种类型的不匹配，但我无法完全想出解决它的方法。最接近的答案是哪些 VertexList 类型对 depth_first_search 有效，但这适用于 DFS，不能外推到 SCC。

4

1 回答 1

0

在 listS 而不是 vecS 上做强连通分量的图的例子并不多。这是 vecS 的等效示例

“在水下而不是在陆地上玩棋盘游戏的信息不多”

原因是您提到的算法没有任何特定内容（连接的组件）。您面临的问题是 usinglistS会丢失隐式vertex_index属性。这破坏了所有需要它的东西。

具体来说，您会注意到add_edge调用已经无法编译。

您需要添加一个顶点索引。就像在水下进行任何活动一样，需要氧气管理解决方案。

因此，请在此处查找示例。

事实上......我立即遇到了我在 2017 年回答的重复问题：

使用 Boost Graph 库查找连接的组件，顶点和边类型为 boost::listS

最简单的改变：

对示例代码进行最简单的更改：

住在科利鲁

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/strong_components.hpp>
#include <iostream>
#include <vector>
using boost::make_iterator_range;

int main() {
    typedef boost::adjacency_list<boost::vecS, boost::listS, boost::directedS,
            boost::property<boost::vertex_index_t, int>
        > Graph;

    Graph G(6);
    auto idmap = get(boost::vertex_index, G);
    {
        // initialize idmap
        int id = 0;
        for (auto& v : make_iterator_range(vertices(G)))
            idmap[v] = id++;
    }

    auto add_edge = [&](int i, int j) {
        return boost::add_edge(vertex(i, G), vertex(j, G), G);
    };

    add_edge(0, 1);
    add_edge(1, 1);
    add_edge(1, 3);
    add_edge(1, 4);
    add_edge(3, 4);
    add_edge(3, 0);
    add_edge(4, 3);
    add_edge(5, 2);

    std::vector<int> c(num_vertices(G));

    int num = strong_components(
        G, make_iterator_property_map(c.begin(), idmap, c[0]));

    //auto l = get(vertex_index, G);

    std::cout << "Total number of components: " << num << std::endl;
    std::vector<int>::iterator i;
    for (i = c.begin(); i != c.end(); ++i)
        std::cout << "Vertex " << i - c.begin() << " is in component " << *i
                  << std::endl;
}

印刷

Total number of components: 3
Vertex 0 is in component 0
Vertex 1 is in component 0
Vertex 2 is in component 1
Vertex 3 is in component 0
Vertex 4 is in component 0
Vertex 5 is in component 2
于 2020-05-08T12:42:34.377 回答