Я предупреждал вас на днях:

1. Я выбираю listS, потому что он обеспечивает стабильность ссылок/дескрипторов. Это, однако, подразумевает отсутствие неявного свойства vertex_index_t.
2. Если вы сделаете это делатьvecS, то у вас будет конфликт с типом идентификатора (size_t) в разрешении перегрузки
3. В ПС. Я вспомнил, что что vertex_index предполагается (алгоритмами BGL) для сопоставления с непрерывным доменом [0, num_vertices(g)), поэтому данные значения не будут удовлетворять требованиям, что делает небезопасным фактическое использование его в качестве идентификатора вершины.. Это прекрасно объясняет, почему, если вы форсируете это, как в вашем примере (с get(&Vertex::id, g)), это не пойдет хорошо.

Проверка некоторых вещей

В разделе 3. давайте проверим документацию на breadth_first_search, и да, там прямо указано:

IN:vertex_index_map(VertexIndexMap i_map)

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

Итак, не делайте того, что вы пытались! Это приведет к Неопределенное поведение. Но читайте дальше:

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.

Печальная новость: все ваши выпуски были точно отозваны.

Хорошая новость: у нас есть 3 варианта исправить это:

1. пройти свою собственную цветную карту
2. передать внешний индекс вершины
3. заставьте adjacency_list снова использовать vecS, но избегайте конфликтов перегрузки

1. Передайте свою собственную цветовую карту

Вы можете посмотреть документацию, чтобы увидеть требования. Самый простой способ удовлетворить это:

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. Передайте свой собственный индекс вершины

Вместо этого вы можете указать 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)     //
);

2б. Интермеццо

Конечно, вы можете предоставить оба, хотя это не обязательно. Это может быть оптимизация, если вы много раз вызываете BFS или хотите использовать свою собственную структуру данных (например, flat_map<V, color, small_vector<V, N> >, чтобы вы могли избежать всех распределений там):

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

3. Используйте ВекС...

Это влияет на стабильность дескриптора, но давайте хотя бы покажем. Я бы предложил использовать тип оболочки для идентификатора:

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

Нам нужен хэш/равенство для поиска имен и operator<< для печати графика. Конечно, реализация тривиальна.

С этим все «просто работает», потому что Graph имеет внутреннюю неявную vertex_index:

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

Живой список всего вышеперечисленного

Жить на Колиру

Скомпилировано дважды, с определением USE_VCES или без него:

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

Скомпилируйте и запустите:

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

Отпечатки

./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