remove_vertex, когда график vertexlist = vecs

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

Ваши края хранятся в STD :: вектор. Если у вас есть n вершин, то все вершины нумеруются от 0 до N. Если вы удалите одну, то ваши вершины будут перенуметыми от O до N - 1. Там, что ваш дескриптор будет недействительным.

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

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

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

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

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