Как boost::adjacency_list сохраняет действительные дескрипторы краев после удаления_края

Я пытаюсь примерно понять, как работает adjacency_list в boost, и не понимаю, как дескрипторы края могут оставаться действительными после вызова remove_edge при использовании EdgeList из std::vector.

Насколько я понимаю, дескрипторы вершин и ребер являются индексами в центральном хранилище вершин и ребер списка смежности (также каждый std::vector). Когда ребро удаляется, не должно ли это сделать недействительным дескриптор (индекс) всех ребер после удаления в хранилище? Или, по крайней мере, тот край, который был перемещен с конца, чтобы заполнить пробел?


person zennehoy    schedule 30.07.2015    source источник


Ответы (1)


Частичный ответ здесь:

выполнение remove_edge(u, v, g) всегда делает недействительным любой дескриптор края для (u,v) или итератор края, указывающий на (u,v), независимо от вида adjacency_list. В этом обсуждении аннулирования итераторов и дескрипторов нас интересует только влияние remove_edge(u, v, g) на дескрипторы ребер и итераторы, которые указывают на другие ребра (не (u, v)).

ускорить аннулирование итератора смежности

Дополнительную информацию можно найти в исходной документации.

person Kirell    schedule 30.07.2015
comment
Да, это таблица, которая меня смущает. Ни дескрипторы вершин, ни дескрипторы ребер не становятся недействительными с помощью remove_edge. remove_vertex делает все недействительным, как и ожидалось. - person zennehoy; 30.07.2015
comment
Я нашел соответствующий раздел в документе. Я предполагаю, что другие индексы ребер меняются местами, чтобы быть согласованными. Хотя я не уверен. - person Kirell; 30.07.2015