How to use boost graph algorithm on a named graph?

Question

I am trying to compile a simple code sample that uses BFS to traverse a named graph from and answer to my previous question.

I think the main problem is providing the correct index map to the algorithm.

The code (without named graph traits boilerplate) is as following:

Graph g;

// add a few named vertices
auto v1 = add_vertex(1111, g);
auto v2 = add_vertex(2222, g);  
auto v3 = add_vertex(3333, g);

// add 2 edges
add_edge(1111, 2222, g);
add_edge(2222, 3333, g);

simple_bfs_visitor bfs_visitor_instance{};
//boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance)); // fails to compile
//boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance).vertex_index_map(boost::get(&Vertex::id, g))); // compiles but fails with exception

Could someone provide an example on how to call a graph algorithm on the provided graph?

I'll appreciate an explanation on the concepts involved because I fail to understand how the various terms such as property map / index map come into play and how they are different when using named graph.

---

Here is the full (not working) code:

struct Vertex
{
    size_t      id;
    std::string other = "default-constructed";
};
// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = size_t;
        result_type const& operator()(Vertex const& bundle) const {
            return bundle.id;
        }
    };
};

template <> struct boost::graph::internal_vertex_constructor<Vertex> {
    struct type {
    private:
        using extractor = typename internal_vertex_name<Vertex>::type;
        using name_t = std::decay_t<typename extractor::result_type>;

    public:
        using argument_type = name_t;
        using result_type = Vertex;

        result_type operator()(const name_t& id) const { return { id }; }
    };
};

using Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, Vertex>;

class simple_bfs_visitor : public boost::default_bfs_visitor
{
public:
    void discover_vertex(const Graph::vertex_descriptor& v, const Graph& g) const
    {
        std::cout << "hi from bfs" << '\n';
    }
};

void Func()
{
    Graph g;

    // add a few named vertices
    auto v1 = add_vertex(1111, g);
    auto v2 = add_vertex(2222, g);  
    auto v3 = add_vertex(3333, g);

    // add 2 edges
    add_edge(1111, 2222, g);
    add_edge(2222, 3333, g);

    simple_bfs_visitor bfs_visitor_instance{};
    //boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance)); // fails to compile
    //boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance).vertex_index_map(boost::get(&Vertex::id, g))); // fails with exception
}

Answer 1

I warned you the other day:

1. I choose listS because it offers reference/descriptor stability. This however implies there is no implicit vertex_index_t property.
2. If you do make it vecS, then you'll have conflict with the id type (size_t) in overload resolution
3. In the PS. I remebered that that vertex_index is assumed (by BGL algorithms) to map to the contiguous domain [0, num_vertices(g)) so the given values would not satisfy the requirements, making it unsafe to actually use it as the vertex id.. This handsomely explains why if you force it like in your exampe (with get(&Vertex::id, g)) it will not go well.

Checking Some Things

Under 3., let's check the Documentation for breadth_first_search and yes, it explicitly states:

IN: vertex_index_map(VertexIndexMap i_map)

This maps each vertex to an integer in the range [0, num_vertices(g)).

So, don't do what you tried! It's going to lead to Undefined Behaviour. But read on:

This parameter is only necessary when the default color property map is used. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default: get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

The sad news: all your issues were exactly called out.

The good news: we have 3 options to fix it:

1. pass your own color map
2. pass an external vertex index
3. make adjacency_list use vecS again, but avoid the overload conflicts

1. Pass Your Own Color Map

You can look at the documentation to see the requirements. The simplest way to satisfy that:

std::map<V, boost::default_color_type> colors;
auto color_map = boost::make_assoc_property_map(colors);

Now you call it:

breadth_first_search(                    //
    g, v1,                               //
    boost::visitor(bfs_visitor_instance) //
        .vertex_color_map(color_map)     //
);

2. Pass Your Own Vertex Index

Instead you could supply an index. Very similarly:

std::map<V, int> index;
auto index_map = boost::make_assoc_property_map(index);

But this time you have to make sure the map is populated according to expectations!

// important: remember to make the data up-to-date!
for (auto v : boost::make_iterator_range(vertices(g)))
    index_map[v] = index.size();

And we call it again like:

breadth_first_search(                    //
    g, v1,                               //
    boost::visitor(bfs_visitor_instance) //
        .vertex_index_map(index_map)     //
);

2b. Intermezzo

Of course you could provide both, although that's not required. It might be an optimization if you call BFS a lot of times or want to use your own data structure (like a flat_map<V, color, small_vector<V, N> > so you can avoid all allocations there):

breadth_first_search(                    //
    g, v1,                               //
    boost::visitor(bfs_visitor_instance) //
        .vertex_color_map(color_map)     //
        .vertex_index_map(index_map)     //
);

3. Use VecS...

This has implications for descriptor stability, but let's at least show. I'd suggest using a wrapper type for the id:

struct Id {
    size_t _val;
    Id(size_t v = {}) : _val(v) {}

    // relay some common operations
    friend std::ostream& operator<<(std::ostream& os, Id const& id) { return os << "Id:" << id._val; }
    friend size_t hash_value(Id const& id) { return boost::hash_value(id._val); }
    auto operator<=>(Id const&) const = default;
};

We need hash/equality for the name lookups and operator<< for printing the graph. Of course, the implementation is trivial.

With that in place, everything "just works" because Graph has an internal implicit vertex_index:

boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance));

Live Listing Of All The Above

Live On Coliru

Compiled twice, with or without USE_VCES defined:

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

#ifndef USE_VECS
    using VertexS = boost::listS;
    using Id      = size_t;
#else
    using VertexS = boost::vecS;
    struct Id {
        size_t _val;
        Id(size_t v = {}) : _val(v) {}

        // relay some common operations
        friend std::ostream& operator<<(std::ostream& os, Id const& id) { return os << "Id:" << id._val; }
        friend size_t hash_value(Id const& id) { return boost::hash_value(id._val); }
        auto operator<=>(Id const&) const = default;
    };
#endif

struct Vertex {
    Id id;
    std::string other = "default-constructed";
};

using Graph =
    boost::adjacency_list<boost::vecS, VertexS, boost::directedS, Vertex>;

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = decltype(Vertex::id);
        result_type const& operator()(Vertex const& bundle) const {
            return bundle.id;
        }
    };
};

template <> struct boost::graph::internal_vertex_constructor<Vertex> {
    struct type {
      private:
        using extractor = typename internal_vertex_name<Vertex>::type;
        using name_t    = std::decay_t<typename extractor::result_type>;

      public:
        using argument_type = name_t;
        using result_type = Vertex;

        result_type operator()(const name_t& id) const { return {id}; }
    };
};

using V = Graph::vertex_descriptor;

struct simple_bfs_visitor : boost::default_bfs_visitor {
    void discover_vertex(V, const Graph&) const {
        std::cout << "hi from bfs" << '\n';
    }
};

int main() {
    Graph g;

    V v1 = add_vertex(1111, g);
    /*V v2 =*/ add_vertex(2222, g);
    /*V v3 =*/ add_vertex(3333, g);

    add_edge(Id{1111}, Id{2222}, g);
    add_edge(Id{2222}, Id{3333}, g);

    print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
    print_graph(g, get(&Vertex::other, g), std::cout << "---\n");

    simple_bfs_visitor bfs_visitor_instance{};

    // 1. bring your own colors
    std::map<V, boost::default_color_type> colors;
    auto color_map = boost::make_assoc_property_map(colors);

    breadth_first_search(                    //
        g, v1,                               //
        boost::visitor(bfs_visitor_instance) //
            .vertex_color_map(color_map)     //
    );

    // 2. bring your own index
    std::map<V, int> index;
    auto index_map = boost::make_assoc_property_map(index);

    // important: remember to make the data up-to-date!
    for (auto v : boost::make_iterator_range(vertices(g)))
        index_map[v] = index.size();

    breadth_first_search(                    //
        g, v1,                               //
        boost::visitor(bfs_visitor_instance) //
            .vertex_index_map(index_map)     //
    );

    // 2b. bring your own
    breadth_first_search(                    //
        g, v1,                               //
        boost::visitor(bfs_visitor_instance) //
            .vertex_color_map(color_map)     //
            .vertex_index_map(index_map)     //
    );

#ifdef USE_VECS
    // 3. use vecS but not `size_t` as the Id:
    boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance));
#endif
}

Compile and run:

g++ -std=c++20 -O2 -Wall -pedantic -pthread main.cpp -DUSE_VECS -o vecS.exe
g++ -std=c++20 -O2 -Wall -pedantic -pthread main.cpp -o listS.exe
set -x
./vecS.exe
./listS.exe

Prints

./vecS.exe
./listS.exe
+ ./vecS.exe
---
Id:1111 --> Id:2222 
Id:2222 --> Id:3333 
Id:3333 --> 
---
default-constructed --> default-constructed 
default-constructed --> default-constructed 
default-constructed --> 
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
+ ./listS.exe
---
1111 --> 2222 
2222 --> 3333 
3333 --> 
---
default-constructed --> default-constructed 
default-constructed --> default-constructed 
default-constructed --> 
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs