boost::adjacency_list<> and boost::listS

Question

the documentation says:

listS selects std::list

The same is being used in an example I'm trying to adapt.

I don't see anywhere in the example where the edge and the vertex type are being passed to boost::adjacency_list<>. And unsurprisingly constructing the graph using a begin-end pair into a container of edges does not compile for me.

How can one tell the graph library about the type of edges and vertices one intends to use?

Answer 1

Q. I don't see anywhere in the example where the edge and the vertex type are being passed to boost::adjacency_list<>.

You choose all the properties of the graph with the template arguments.

The first two choose how edges and vertexes are to be stored. For adjacency-lists, the adjacency-list is a given, but you can choose the edge container selector (which stores the adjacencies (out-edges) per source vertex) and the actual vertex container selector (which stores the vertices themselves).

The other template arguments include the vertex/edge and graph properties. So, where the container selectors choose how to store graph entities, the properties describe what should be stored.

HOW everything is being stored is ultimately an implementation detail.

Q. And unsurprisingly constructing the graph using a begin-end pair into a container of edges does not compile for me.

We can't say anything about that, because we don't know what you mean by "a container of edges". Do you already have your graph in some other format?¹

The constructor arguments are not required to build a graph. E.g.:

#include <boost/graph/adjacency_list.hpp>
using G = boost::adjacency_list<>;

int main() {
    G g(10);
}

Is the simplest possible program that creates a graph with 10, unconnected, vertices. To also print it: Live

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
using G = boost::adjacency_list<>;

int main() {
    G g(10);
    print_graph(g);
}

Output shows 10 vertices with no adjacencies:

0 --> 
1 --> 
2 --> 
3 --> 
4 --> 
5 --> 
6 --> 
7 --> 
8 --> 
9 --> 

How can one tell the graph library about the type of edges and vertices one intends to use?

Let me start with the "using", then modify the types a little:

Instead you can add edges/vertices after construction: Live

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

using G = boost::adjacency_list<>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;

int main() {
    G g;

    V v1 = add_vertex(g);
    V v2 = add_vertex(g);
    E e1 = add_edge(v1, v2, g).first;
    // or:
    auto [ed, inserted] = add_edge(v1, v2, g);

    std::cout << "Second insertion happened: " << std::boolalpha << inserted << "\n";

    print_graph(g);
}

Output:

Second insertion happened: true
0 --> 1 1 
1 --> 

Now, let's immediately show the effect of setS as edge storage:

using G = boost::adjacency_list<boost::setS>;

Output becomes - because the setS doesn't admit duplicate out-edges:

Second insertion happened: false
0 --> 1 
1 --> 

Now, let's also try a different vertex container selector?

using G = boost::adjacency_list<boost::setS, boost::listS>;

Uhoh, now there is trouble printing the graph, because, as you might have read already in the linked documentation:

If the VertexList of the graph is vecS, then the graph has a builtin vertex indices accessed via the property map for the vertex_index_t property. The indices fall in the range [0, num_vertices(g)) and are contiguous. When a vertex is removed the indices are adjusted so that they retain these properties. Some care must be taken when using these indices to access exterior property storage. The property map for vertex index is a model of Readable Property Map.

If you use listS then there is no implicit vertex index. Of course, we can add an index, but let's instead add a name property to our vertex.

There are many ways to add properties, but let me show you the more versatile/friendly version: bundled properties:

struct VertexProps {
    std::string name;
};

using G = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, VertexProps>;

Now, all we need to do is tell print_graph to use the name property from the bundle instead of the vertex index (which isn't usable for printing since listS):

print_graph(g, get(&VertexProps::name, g));

Of course, it becomes nicer when you actually give the vertices names:

V v1 = add_vertex(VertexProps{"v1"}, g);
V v2 = add_vertex(VertexProps{"v2"}, g);

But of course, names can be changed:

g[v2].name += "(changed)";

See it all together: Live

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

struct VertexProps {
    std::string name;
};

using G = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, VertexProps>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;

int main() {
    G g;

    V v1 = add_vertex(VertexProps{"v1"}, g);
    V v2 = add_vertex(VertexProps{"v2"}, g);
    E e1 = add_edge(v1, v2, g).first;
    // or:
    auto [ed, inserted] = add_edge(v1, v2, g);

    g[v2].name += "(changed)";
    std::cout << "Second insertion happened: " << std::boolalpha << inserted << "\n";

    print_graph(g, get(&VertexProps::name, g));
}

Prints

Second insertion happened: false
v1 <--> v2(changed) 
v2(changed) <--> v1 

---

¹ You may not need to copy anything at all, just adapt/use the existing graph)

Answer 2

I created a copy of the graph with plain std::size_t for vertices and std::pair<std::size_t, std::size_t> for edges.

I'm unclear why I have to do this, as the graph library is a template library.