Confused by boost graph descriptor invalidation
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Dear list, I have a adjacency_list with OutEdgeList and VertexList as vecS and I do need to split edges. To split an edge is to remove it, replace with two edges with a new vertex in the middle. Since I am changing the graph I want to be sure how the invalidation works and so I read the page in[1], but I am confused by the table "Summary of Descriptor and Iterator Invalidation." The text states the table summarizes which operations cause descriptors and iterators to become invalid, said so what does "OK" means? My feeling is that iterators never become invalid, is that the case? And what "EL=vecS && Directed=directedS" means? It means that you are _fine_ only if you are working with a adjcency_list with OutEdgeList as vecS and Directed=directedS or the opposite (i.e., if you are using such adjcency_list then all iterators become invalid) Yours faithfully, Paolo [1] http://www.boost.org/doc/libs/release/libs/graph/doc/adjacency_list.html -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQEcBAEBCAAGBQJW78v4AAoJENxW6b8QprD6Aq4H/jXK9kfFy65yZzzzySsFteS6 V9PFvCyrjzgrbGojMZok3Xxz2fJBvfvomqnzEgDuFy7I1P73dkyL3gbwRoPINQpN Qu/0zqskpWf6gJjnu0/3QtSDRBQ1hvT/ZmfhfoUyh1CSQuxyH+/VQV5V4uaDxymQ /atbZWn8Ry1e4noHlS1l27FvEF+qsxOGaHsqBr1Of5KYvcdWmEqN2PJjqWF87Ev7 +sCY4/aD5rT0n+FLBa/Qk/opblbNYprjCmTgpWjKh4lnRmrHJAJNTQeKwZC+e8Hx SOqW2kAQMRW46/y+VcMnOOv+M5UOxqj0K+EgAWVLaoyAZTJzbSc2E9VQL3fB4AA= =xH7S -----END PGP SIGNATURE-----
On Mon, Mar 21, 2016 at 3:25 AM, Paolo Bolzoni < paolo.bolzoni.brown@gmail.com> wrote:
The text states the table summarizes which operations cause descriptors and iterators to become invalid, said so what does "OK" means? My feeling is that iterators never become invalid, is that the case?
That's correct -- descriptors/iterators marked "OK" remain valid after the associated function is called (besides descriptors/iterators to the removed element itself, of course).
And what "EL=vecS && Directed=directedS" means? It means that you are _fine_ only if you are working with a adjcency_list with OutEdgeList as vecS and Directed=directedS or the opposite (i.e., if you are using such adjcency_list then all iterators become invalid)
It means the latter -- if you are using such an adjacency_list, then all descriptors/iterators become invalid. I believe the current implementation of adjacency_list uses vector indices as descriptors and pointers into the vector as iterators, and since the implementation guarantees that the vector is contiguous, removing vertex 5 in a 10-vertex graph will cause vertices to be re-numbered, invalidating old descriptors. If you want descriptors/iterators to remain valid as the graph is changed, it is therefore advisable to choose a datastructure such as a list which does not suffer this problem. Cheers, - Chris
participants (2)
-
Chris Dellin -
Paolo Bolzoni