Boost Strong components with listS

Question

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

#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;
}

But when I change from vecS to listS, it breaks. I know the problem is because of sometype of mismatch in the vertex index and the output vector index but I couldn't exactly come up with a way to solve it. The closest answer is Which VertexList types are valid for depth_first_search but this is for DFS and cannot extrapolate to 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"

The reason is that there's nothing specific to the algorithm you mention (connected components). The problem you're facing is that using listS loses the implicit vertex_index property. This breaks everything that requires it.

Specifically, you would notice that the add_edge call already fails to compile.

You need to add a vertex index. Much like doing any activity underwater requires a solution for oxygen management.

So look for examples for that e.g. here.

In fact... I immediately ran into a duplicate question that I answered in 2017:

Find connected components using Boost Graph library, with the vertex and edge type being boost::listS

Simplest Change:

Simplest change to your sample code:

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;
}

Prints

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