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

Question

У меня есть график повышения с VertexList = vecS.

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

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

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

Answer 1

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

Answer 2

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

Однако возможен обходной вариант: - итерация от N до 0 - проверка вашего узла и удаление его при необходимости

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

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

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

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

Answer 3

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

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

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