How can I use `ListS` instead of `VecS` as underlying container and be able to do the same thing?

Question

I usually work with vecS as container for boost::adjacency_list:

struct myVertexType { std::vector<Stuff> vec; /* and more */ };
struct myEdgeType { /* some data too */ };
using Graph = boost::adjacency_list<
        boost::vecS,
        boost::vecS,
        boost::directedS,
        myVertexType,
        myEdgeType
    >;

However, I encountered a situation were that raised an issue: I was referencing some data stored as a bundled property of a vertex and when I created another vertex, that seemed to make my reference invalid (1).

At least that's what I understood from reading this page (section "Iterator and Descriptor Stability/Invalidation").

So I switched to listS, and all went fine:

using Graph = boost::adjacency_list<
        boost::listS,
        boost::listS,
        boost::directedS,
        myVertexType,
        myEdgeType
    >;

Until...

Until I noticed that with listS, boost::target( e1, g ) fails to compile! :

Graph g;
auto e1 = boost::add_edge(1, 0, g).first;
auto t = boost::target( e1, g );

This fails to build too: (see on coliru)

Graph g;
boost::add_edge(1, 0, g);
write_graphviz(std::cout, g );

So I searched a bit and found an answer by Sehe, stating that

vecS has an implicit vertex index. listS doesn't. Therefore it uses the internal property vertex_index_t

However, the given answer uses Inner properties (?) (or is it dynamic properties?) and I am using my own datatypes for vertices and edges.

So my question is:

How can I build a list-based graph type that enables me to do all the "regular stuff" allowed by VecS?

(1) to be clear, I was referencing a vector that was in a vertex, and when I created another vertex, the vector suddenly became empty!

Edit: clarified what is inside my nodes.

Answer 1

Background

"when I created another vertex, that seemed to make my reference invalid (1)."

Yes, that's possible.

You have to realize that there's are much bigger performance trade-offs underlying your choice of container selectors. Many algorithms can get very different efficiency characteristics.

Also, some semantics subtly change (e.g. when using setS as the edge container selector, you naturally cannot have duplicate edges anymore; this is also why add_edge returns a pair<descriptor, bool>).

Also realize that often you don't need reference or even iterator stability. The typical coding pattern in BGL is not to pass/hold references to property (bundles), but instead pass property maps by value.

Property maps abstract aways access to (mutable) properties.

You can usually pass descriptors which usually are stable (unless you're removing vertices "in the middle" in vecS, as the implied vertex index is obviously changing for all following vertices).

That said, let's move on to your problems:

Questions

Until I noticed that with listS, boost::target( e1, g ) fails to compile!

Nope. That compiles fine.

What ISN'T fine is that you call add_edge with integral arguments. The vertex descriptor isn't integral with lists/setS (node based containers).

Worse, vertices don't get automatically added for non-vecS adjacency_list so you'd be referring to vertices out-of-range anyways.

The general way to refer to these is:

V v0 = add_vertex(g);
V v1 = add_vertex(g);
auto [e1, inserted] = boost::add_edge(v0, v1, g);
assert(inserted);
[[maybe_unused]] V t = boost::target(e1, g);

The graphviz call is also fine, but fails for the same reason on add_edge...

Also, you need to add a vertex index. Either as interior property or passing a property map to the algorithm function.

Here's a complete test demo that shows all three flavours:

Live On Coliru

#include <boost/algorithm/string.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/core/demangle.hpp>
#include <iostream>
#include <numeric>
using boost::core::demangle;
using boost::algorithm::replace_all_copy;

struct myVertexType { /* some data */ };
struct myEdgeType { /* some data too */ };

template <typename containerS> void tests() {
    using Graph = boost::adjacency_list<
        containerS, containerS,
        boost::directedS,
        myVertexType,
        myEdgeType>;

    using V = typename Graph::vertex_descriptor;

    std::cout << "\n"
              << std::boolalpha << "tests() with "
              << demangle(typeid(containerS).name()) << " - "
              << "vertex_descriptor integral? " << std::is_integral<V>()
              << "\n";
    Graph g;

    V v0 = add_vertex(g);
    V v1 = add_vertex(g);
    auto [e1, inserted] = boost::add_edge(v0, v1, g);
    assert(inserted);
    [[maybe_unused]] V t = boost::target(e1, g);

    std::ostringstream dot;
    if constexpr (std::is_same<boost::vecS, containerS>()) {
        boost::write_graphviz(dot, g);
    } else {
        std::map<V, int> index;
        for (auto v : boost::make_iterator_range(vertices(g)))
            index.emplace(v, index.size());

        auto index_map = boost::make_assoc_property_map(index);

        boost::dynamic_properties dp;
        dp.property("node_id", index_map); // get(boost::vertex_index, g)

        boost::write_graphviz_dp(dot, g, dp);
    }

    std::cout << "dot: " << replace_all_copy(dot.str(), "\n", "") << "\n";
}

int main() {
    tests<boost::vecS>();
    tests<boost::setS>();
    tests<boost::listS>();
}

Prints

tests() with boost::vecS - vertex_descriptor integral? true
dot: digraph G {0;1;0->1 ;}

tests() with boost::setS - vertex_descriptor integral? false
dot: digraph G {0;1;0->1 ;}

tests() with boost::listS - vertex_descriptor integral? false
dot: digraph G {0;1;0->1 ;}