adjacency_list с VertexList, отличным от vecS - PullRequest
Новая
       53

adjacency_list с VertexList, отличным от vecS

2 голосов
/ 14 октября 2011

У меня есть две структуры, содержащие некоторые поля: 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, я не смогу просмотреть список вершин / ребер и получить доступ к дескрипторам там, как я это делал раньше!

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

Ответы [ 2 ]

0 голосов
/ 18 мая 2017

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

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

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

0 голосов
/ 19 декабря 2011

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

<...>
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++);
}
...