Re: BGL and reversing / moving edges

Well, edge descriptors are std::pair of vertex descriptors, so they should stay stable unless you mutate the vertex_list. Mutating(erasing vertices) the vertex_list in BGL really doesn't make much sense. Independt from the vertex_list container, all vertex remove operations take O(N), where N is the number of vertices in your graph. Most of the time, it is better to unlink the vertex and create a new vertex with the same edges. Only now, the edge descriptor for all relinked edges changes. ----- Original Message ----- From: "joshrose" Newsgroups: gmane.comp.lib.boost.user Sent: Thursday, July 25, 2002 7:06 PM Subject: Re: BGL and reversing / moving edges

Quick clarification -- I really didn't mean to say that I want edge iterators to be stable -- that doesn't really make much sense, since I'm changing the link structure of the graph. Instead, I'm really focusing on having a stable edge_descriptor, since that is refered to by long-lived entities (e.g. property maps).

Thanks,

-Josh

...

This is an interesting idea -- I do have the requirement that

...

edges are allowed (think of the point of the algorithm as reducing a muti-graph to a standard graph, s.t. the sum of all edge weights is maximal), so neither hash_setS nor setS would work. But, multisets appear to be an option, using the mutisetS selector. I think you're suggesting that I can use one of these other edgelist implementatations, then remove and re-add the edge.

However, I'm not sure this is quite what I'm looking for, since in addition to not invalidating other iterators / descriptors (those other than the one I'm trying to reverse), it's critical that I not invalidate the edge descriptor for the edge I'm trying to reverse, since it's still going to be in the graph, and property maps will refer to it. What I think I really need is a way to move the edge within the graph (or at least remove the edge and re-add it, in a way that guarantees that the re-added edge has the same edge_descriptor as the original edge).

Tracing through the implementation a bit of add_edge, I have an idea on how to do this, but it involves a fair bit of hacking and is not terribly clean (and probably doesn't work!): you could directly go into the edge_desc_impl class (really it's superclass edge_base) [from detail/edge.hpp] and swap the m_source and m_target members

--- In Boost-Users@y..., "joshrose" wrote: parallel directly,

...

then remove the edge from the source vertex edge list, create a StoredEdge instance and insert it into the target edge list. But I'm not sure how to link this new stored edge with the old edge_descriptor.

Does this help clear things up?

Again, thanks for the reply.

-Josh

--- In Boost-Users@y..., "Matthias Kronenberger" wrote:

...

You could use hash_setS or setS for the Edge_list. This will allow you to remove edges and add edges without invalidating edge iterators or edge descriptors.