1

The question is about the Boost Graph Library.

Suppose that we store an object with each vertex of the graph and there is a one-to-one correspondence between the vertices and the objects. Suppose further that we maintain an std::map to enable looking up a vertex descriptor that corresponds to a given object.

However, this solution seems to be prone to invalidation of vertex descriptors in the case of a vertex being deleted. Is there a way to get around this problem?

In this question, the following sentence appears:

I want to store vertex descriptors in a way that they wont invalidate in case I remove a vertex, so I use boost::listS

It seems like the author of that question has a solution to the problem of vertex invalidation, but I do not understand what it is.

EDIT: to clarify the reason for maintaining a map. The need to look up a vertex based on an object arises in the following scenario. Suppose that we have generated an object. We need to look up a vertex that corresponds to an object that's equal (in the sense of operator==) to an object that we've just generated.

Community
  • 1
  • 1
AlwaysLearning
  • 7,257
  • 4
  • 33
  • 68

1 Answers1

2

Using a listS or setS for the vertex container selector makes the invalidation guarantees equal to the corresponding standard library container (Iterator invalidation rules).

In general, the node-based containers do not invalidate any iterators unless removed.

At this point I would like to suggest bundled properties too, where you don't have to maintain a mapping from object to vertex descriptor/index at all.

Sample (coming: https://www.livecoding.tv/sehe/)

Community
  • 1
  • 1
sehe
  • 374,641
  • 47
  • 450
  • 633
  • "where you don't have to maintain a mapping from object to vertex descriptor/index at all". I think bundled properties take care of the opposite direction. How do they help in looking up vertex descriptors by objects? – AlwaysLearning Nov 15 '15 at 19:48
  • The idea would be that you always go through the graph's vertex list, then – sehe Nov 15 '15 at 19:48
  • I guess a [sample of the bundled approach](http://coliru.stacked-crooked.com/a/542d84b6a3dfafe8) is a little late then, now :) Anyhoops, the `setS`/`listS` have a key: beware of possible performance implications and the need for (external?) vertex id maps for many algorithms – sehe Nov 15 '15 at 19:52
  • You can't always do this. Suppose that you generate a new object and want to get to a vertex in the graph that corresponds to an object that's equal (in the sense of `operator==`) to the new object, e.g. to connect it to a different vertex (object)... – AlwaysLearning Nov 15 '15 at 19:54
  • @AlwaysLearning you never mentioned these requirements. Next time, you might wish to be more concrete in the question _code_ – sehe Nov 15 '15 at 19:57
  • 1
    I missed the fact that this reply totally answers the question. This is because, for std::list, only the iterators to the erased element get invalidated. So, with listS, upon removing a vertex, only one vertex descriptor is affected, while the rest of the map stays valid! – AlwaysLearning Nov 15 '15 at 21:51