-1

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
  • 20,880
  • 13
  • 75
  • 99
einpoklum
  • 102,731
  • 48
  • 279
  • 553
  • 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
  • 350,152
  • 45
  • 431
  • 590
  • 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