3

I am currently designing an application composed of both a Boost Graph (adjacency_list) and several classes referencing edges or vertices from this structure.

My question is: what is the recommended way to maintain a reference to a node or a vertex?

I guess that in the iterator case the object access is faster but the iterator can be invalidated by dynamic changes on the graph structure.

On the opposite, a descriptor is an id which means that a search is necessary to retrieve the data but may be less prone to trigger a memory error in case the graph changes.

Is it true?

Thomas Moulard
  • 5,151
  • 2
  • 21
  • 28

1 Answers1

4

Stability of iterators/descriptors and efficiency of iterators both depend on your vertex container.

For vectorS for example the vertex descriptor is just the index of the vertex in the vector, so lookups in the container are as fast as indexing into a vector. The descriptor is just as unstable as the iterator in this instance as insertions & deletions can cause elements to move around.

For listS I expect (read: 'guess') the descriptor is the address of the element, so both descriptor and iterator are likely to have the same stability guarantees. In this case, using the vertex descriptor to get access to the property may well be as efficient as the iterator.

For more information on adjacency_list iterator/descriptor stability read the section titled Iterator and Descriptor Stability/Invalidation on this page. With performance concerns you're best profiling the 2 to compare, and only when it seems to be a bottleneck in your application.

boycy
  • 1,473
  • 12
  • 25