使用 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

There aren't too many examples for graphs that do strongly connected components on listS rather than vecS. Here is an equivalent example for vecS

"There isn't much information for playing board games when underwater rather than on land"

原因是您提到的算法没有任何具体内容（连接组件）。您面临的问题是使用 listS 会丢失隐含的 vertex_index 属性。这会破坏所有需要它的东西。

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

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

因此请查找 e.g. here 的示例。

事实上...我立即运行进入我在 2017 年回答的重复问题：

最简单的更改：

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

Live On 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

使用 listS 增强强组件

Boost Strong components with listS

boost

boost-graph

strongly-connected-graph

最简单的更改：