adjacency_list с VertexList отличается от vecS

Question

У меня есть две структуры, содержащие некоторые поля: struct MyNodeData и struct MyEdgeData. Когда я создаю граф с VertexList в качестве vecS, нет проблем с доступом к дескриптору вершин и т. Д. Например:

typedef adjacency_list<setS, vecS, undirectedS, MyNodeData, MyEdgeData> Graph;

typedef Graph::vertex_descriptor MyNodeDataID;
typedef Graph::edge_descriptor MyEdgeDataID;
typedef graph_traits < Graph >::vertex_iterator VertexIterator;
typedef graph_traits < Graph >::edge_iterator EdgeIterator;
typedef graph_traits < Graph >::adjacency_iterator AdjacencyIterator;
typedef property_map < Graph, vertex_index_t >::type IndexMap;

Graph g;
const IndexMap index = get(vertex_index, g);

/* Puis après avoir ajouté des vertex et edges, je peux accéder par exemple à la liste des vertex comme suite: */
pair<VertexIterator, VertexIterator> vi;
for(vi = vertices(g); vi.first != vi.second; ++vi.first)
{
   cout << "vertex: " << index[*vi.first] << endl;
   // or: cout << "vertex: " << *vi.first << endl;
}

Но мне обычно нужно добавлять / удалять ребра и вершины из моего графа. Поэтому я хочу использовать setS или listS в качестве VertexList вместо vecS, поскольку с vecS индексы становятся недействительными, когда мы удаляем один из них! Проблема в том, что если я определю VertexList как setS или listS, я не смогу просмотреть список вершин / ребер и получить доступ к дескрипторам, как я делал раньше!

Короче говоря, мой вопрос таков: так как adjacency_list, который использует listS или setS в качестве контейнера вершин, не предоставляет автоматически это свойство vertex_id, как я могу добавить его в приведенный выше код?

Answer 1

В настоящее время вам просто нужно предоставить ассоциативную карту свойств.

<...>
typedef Graph::vertex_descriptor NodeID;

typedef map<NodeID, size_t> IndexMap;
IndexMap mapIndex;
associative_property_map<IndexMap> propmapIndex(mapIndex);
<...>

// indexing all vertices
int i=0;
BGL_FORALL_VERTICES(v, g, Graph)
{
   put(propmapIndex, v, i++);
}

Answer 2

Но мне обычно нужно добавлять / удалять ребра и вершины из моего графа.

Удаление вершин и ребер возможно с помощью vecS, setS и listS. Просто вызовите remove_vertex\remove_edge с дескриптором вершины \ ребра. Во всех вышеперечисленных контейнерах удаление \ добавление вершины \ ребра сделает недействительным итератор. Это означает, что после того, как вы изменили график, вам придется снова вызывать вершины (g). В большинстве контейнеров изменение контейнера делает его недействительным. В listS добавление вершины не может сделать недействительным итератор, но это зависит от реализации и на него нельзя полагаться.

Вы можете добавить свойство vertex_id к графу, что позволит вам получить доступ к дескрипторам вершин в любое время.