Usage of boost::strong_component

Question

I have a problem using boost::strong_components to in a graph where the vertices are equiped with property. Here is my code:

#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/strong_components.hpp"
struct Vinfo
{
   int id;
};
using Graph = boost::adjacecy_list<boost::setS, boost::setS, boost::directedS, Vinfo>;
using vertex_t = boost::graph_traits<Graph>::vertex_descriptor;
using edge_t = boost::graph_traits<Graph>::edge_descriptor;

using namespace boost;
int main()
{
   Graph mygraph;
   vertex_t a = add_vertex({0}, mygraph);
   vertex_t b = add_vertex({2}, mygraph);
   vertex_t c = add_vertex({8}, mygraph);
   vertex_t d = add_vertex({10}, mygraph);
   
   add_edge(a, b, mygraph);
   add_edge(a, c, mygraph);
   add_edge(a, d, mygraph);
   add_edge(d, a, mygraph);
   add_edge(b, c, mygraph);
   add_edge(c, b, mygraph);

   int num_scc = strong_components(mygraph, make_iterator_property_map(component.begin(), get(vertex_index, mygraph)));
   cout << "there are " << num_scc << " strong components" << '\n';
   
   return 0;
}

This code works fine with both EdgeList and VertexList set to boost::vecS. However, I got compiling error while calling the strong_components when using boost::setS (or other associated container). There aren't too many examples about boost graph library usage online. Could someone tell me how to use strong_component with boost::setS as the EdgeList and VertexList?

Answer 1

As Christian Lehnert correctly teaches, you need a vertex index. Sadly his code wasn't tested.

The index map he came up ironically suffers from the exact same problem: it would require the vertex descriptor to be an integral index itself to use a vector as-if an associative property map.

Instead, make an actually associative container, keyed by vertex descriptor (as required per the docs), and also use it in both places required:

• as the index map for the component property map
• as the vertex_index_map for use by the algorithm

See it Live On Coliru

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

struct Vinfo
{
    int id;
};

using Graph = boost::adjacency_list<boost::setS, boost::setS, boost::directedS, Vinfo>;
using vertex_t = boost::graph_traits<Graph>::vertex_descriptor;
using edge_t = boost::graph_traits<Graph>::edge_descriptor;

int main()
{
    Graph mygraph;
    vertex_t a = add_vertex({0}, mygraph);
    vertex_t b = add_vertex({2}, mygraph);
    vertex_t c = add_vertex({8}, mygraph);
    vertex_t d = add_vertex({10}, mygraph);

    add_edge(a, b, mygraph);
    add_edge(a, c, mygraph);
    add_edge(a, d, mygraph);
    add_edge(d, a, mygraph);
    add_edge(b, c, mygraph);
    add_edge(c, b, mygraph);

    // Define the vertex index property map using boost::property_map and boost::associative_property_map
    std::map<vertex_t, std::size_t> index_map;

    for (auto v : boost::make_iterator_range(vertices(mygraph)))
        index_map.emplace(v, index_map.size());

    std::vector<std::size_t> component(num_vertices(mygraph));

    auto vi_map = boost::make_assoc_property_map(index_map);

    int num_scc = strong_components(                           //
        mygraph,                                               //
        make_iterator_property_map(component.begin(), vi_map), //
        boost::vertex_index_map(vi_map)                        //
    );

    std::cout << "There are " << num_scc << " strong components." << std::endl;
}

Prints

There are 2 strong components.