remove_vertex, когда граф VertexList=vecS

У меня есть Boost Graph с VertexList=vecS.

typedef adjacency_list <listS, vecS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;

Теперь я хочу перебрать свои вершины и удалить те, которые имеют определенное свойство. Как я могу это сделать?

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


c++ boost boost-graph
person Dat Chu    schedule 06.07.2010    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Я не думаю, что это возможно (в разумные сроки) с vecS в качестве параметра шаблона. Посмотрите, что говорится в документации Boost:

Если параметр шаблона VertexList для adjacency_list был равен vecS, то эта операция делает недействительными все дескрипторы вершин, дескрипторы ребер и итераторы для графа. ‹...> Если вам нужно часто использовать функцию remove_vertex(), селектор listS является гораздо лучшим выбором для параметра шаблона VertexList.

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

person Kirill V. Lyadvinsky    schedule 06.07.2010
comment
Проблема с listS в том, что я не могу заставить connect_components работать с ним. stackoverflow .com/questions/3183186/ - person Dat Chu; 06.07.2010

arrow_upward
3
arrow_downward

Может быть, перед итерацией можно сделать специальную "мусорную" вершину, во время итерации вы подключаете все узлы-для-удаления к этой мусорной вершине, а после итерации удаляете все "мусорные" вершины?

person al.zatv    schedule 15.02.2011
comment
Это стоит исследовать. - person sehe; 07.02.2015
comment
Но как отслеживать мусорную вершину, когда удаление ее соседей делает недействительным vertex_descriptor? - person leezu; 07.06.2016

arrow_upward
3
arrow_downward

Ваши ребра хранятся в std::vector. Если у вас есть N вершин, то все вершины будут пронумерованы от 0 до N. Если вы удалите одну, то ваши вершины будут перенумерованы от o до N-1. Поэтому ваш дескриптор будет признан недействительным.

Тем не менее, может быть обходной путь: — итерация от N до 0 — проверка вашего узла и удаление его при необходимости

Это предполагает (и я не уверен, но скорее уверен), что будут перенумерованы только вершины после той, которую вы только что удалили.

Если вы часто выполняете эти манипуляции, это может быть довольно медленным в зависимости от размера вашего графика.

Если этот подход не работает, вам придется построить новый граф из старого (предварительно вычислив, сколько вершин и ребер у вас будет, это может быть достаточно быстро).

Итак, извините, нет реального ответа, но я надеюсь, что вам удастся что-то извлечь из этого.

person Tristram Gräbener    schedule 15.02.2011
comment
Было бы неплохо, если бы вы просто оперировали вектором. Но adjacency_list справляется с этим и все равно должен переиндексировать ребра. Он может выбрать перераспределение вектора после n удалений (опять же сделав недействительными все итераторы). Наконец, обратная итерация vertices(graph) не гарантирует эквивалентность обратной итерации внутреннего вектора вершин. - person sehe; 07.02.2015