0

In the Boost Graph Library documentation it says that when you remove a vertex from a graph (when its vertices are stored in a vector at least), all iterators (and descriptors) are invalidated.

This surprised me, as it seems not be semantically necessary to do so.

Is there a way to make adjacency_list work in a way that doesn't aggressively invalidate iterators in such a case? Can't I somehow just 'invalidate' the vertex and garbage-collect it at some convenient time?

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
einpoklum
  • 118,144
  • 57
  • 340
  • 684
  • 3
    You do know that happens because of the underlying vector? If you add or remove elements from a [`std::vector`](http://en.cppreference.com/w/cpp/container/vector) then all iterators might be invalidated. – Some programmer dude Mar 22 '16 at 09:16
  • 1
    Frankly, your question reads like an unconstructive rant. I can edit it for you, but perhaps you want to do so. – sehe Mar 22 '16 at 09:24
  • @sehe: Better? If not, feel free to edit. – einpoklum Mar 22 '16 at 10:00

1 Answers1

0

It's just the underlying container semantics: Iterator invalidation rules

It's also clearly a trade-off: you get O(1) vertex indexing for free.

If you want something else, use a different container selector (e.g. listS ) for the vertex container.

Isn't it (generally) better to just 'invalidate' the vertex in the vector and garbage-collect it when the next resize is necessary?

It's indeed a common pattern to mark vertices as deleted. boost::filtered_graph<> is a handy adaptor for such cases.

Community
  • 1
  • 1
sehe
  • 374,641
  • 47
  • 450
  • 633
  • 1. A different design choice than just passing the removal on to the container would have spared me the trade-off. 2. I take it a `filtered_graph` adds a 'deleted' boolean property to each vertex (or edge, or both), and overrides the removal operations? – einpoklum Mar 22 '16 at 09:58
  • It would have gotten you another, equally arbitrary, trade-off, obviously. Filtered graph just filters. No overriding done. You "logically" delete vertices by adding them to the filtered set. I (and some others) have answers on SO demonstrating this. – sehe Mar 22 '16 at 10:03