用listS增强强组分

Question

对于在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时，它就会崩溃。我知道问题是因为顶点指数和输出向量指数之间的不匹配类型，但我无法确切地想出解决方法。最接近的答案是搜索，但这是针对DFS的，不能外推到SCC。

Answer 1

对于在listS而不是vecS上做强连接组件的图，没有太多的示例。以下是vecS的等效示例

在水下而不是在陆地上玩棋盘游戏没有多少信息

原因是您提到的算法(连接组件)没有任何特定的内容。您面临的问题是，使用listS会丢失隐式vertex_index属性。这破坏了一切需要它的东西。

特别是，您会注意到add_edge调用已经无法编译。

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

因此，请为该例如这里寻找示例。

事实上..。我立刻遇到了一个重复的问题，我在2017年回答了这个问题：

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

最简单的改变：

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

住在Coliru

#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