Re: BGL and reversing / moving edges

From: joshrose (joshrose_at_[hidden])
Date: 2002-07-25 11:49:29

This is an interesting idea -- I do have the requirement that parallel
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 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_at_y..., "Matthias Kronenberger" <mkronen_at_r...> 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.