Согласованность vertex_descriptor в dijkstra_shortest_paths() ⇐ C++

[Anonymous]

Во вводном примере BGL:

Код: Выделить всё

using namespace boost;

int main(int,char*[])
{
// create a typedef for the Graph type
typedef adjacency_list Graph;

// Make convenient labels for the vertices
enum { A, B, C, D, E, N };
const int num_vertices = N;
const char* name = "ABCDE";

// writing out the edges in the graph
typedef std::pair Edge;
Edge edge_array[] =
{ Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
Edge(C,E), Edge(B,D), Edge(D,E) };
const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

// declare a graph object
Graph g(num_vertices);

// add the edges to the graph object
for (int i = 0; i < num_edges; ++i)
add_edge(edge_array[i].first, edge_array[i].second, g);
...
return 0;
}

Вершины называются целочисленными индексами enum {a,B,C,D,E,N}.
В a аналогичный сценарий, без связанного свойства вершины (полный код в конце):

Код: Выделить всё

    struct Edge
{
int source;
int target;
float weight;
};

using Graph=boost::adjacency_list;
using GraphTraits=boost::graph_traits;
using VertexDescriptor=GraphTraits::vertex_iterator;

Graph graph(5); // 5 vertices

VertexDescriptor v=boost::vertex(1,graph);

Определение VertexDescriptor v не скомпилируется.
Моя среда IDE отслеживает определение в adjacency_list.hpp:

Код: Выделить всё

template < class Graph, class Config, class Base >
inline typename Config::vertex_descriptor vertex(
typename Config::vertices_size_type n,
const vec_adj_list_impl< Graph, Config, Base >&)
{
return n;
}

Чтобы заполнить график, я обнаружил, что использую VertexDescriptor

Код: Выделить всё

    for(auto const &e:edges)
{
boost::add_edge(boost::vertex(e.source,graph),boost::vertex(e.target,graph),e,graph);
}

или int

Код: Выделить всё

    for(auto const &e:edges)
{
boost::add_edge(e.source,e.target,e,graph);
}

оба могут заполнять граф.
Из dijkstra_shortest_paths() doc

OUT: previous_map(PredecessorMap p_map)
Карта предшественников записывает ребра в дереве кратчайшего пути, дереве, вычисленном при обходе графа. По завершении алгоритма ребра (p,u) для всех u из V оказываются в дереве. Кратчайший путь от вершины s до каждой вершины v в графе состоит из вершин v, p[v], p[p[v]] и так далее, пока не будет достигнута вершина s, в обратном порядке. Дерево не обязательно является минимальным остовным деревом. Если p = u, то u — либо исходная вершина, либо вершина, не достижимая из источника. Тип PredecessorMap должен быть картой свойств чтения/записи, типы ключей и значений которой совпадают с типом дескриптора вершины графа.

Там сказано: " Тип PredecessorMap должен быть картой свойств чтения/записи, типы ключей и значений которой совпадают с типом дескриптора вершины графа».
Однако, если Я создаю PredecessorMap, используя std::vector, код не удалось скомпилировать. Вместо этого мне придется использовать std::vector для его создания.
Полный код:

Код: Выделить всё

#include
#include
#include
#include
#include
#include
#include
#include

#include
#include
#include
#include
#include
#include
#include
//#include
#include
#include
#include
#include 

void test003()
{
std::cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/78751207/consistency-of-vertex-descriptor-in-dijkstra-shortest-paths[/url]