Re: [Boost-Users] Re: BGL and reversing / moving edges

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-25 15:03:19

Hi Josh,

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

Are you using internal property maps for the edges? Is so you, when you
removed, and then add an edge, you could first read out all the property
info, and then write it into the new edge.

If you are using an external map for edges... how are you doing the
lookup? You aren't using the edge_descriptor itself as the key are you?
That is bad... instead you could add an integer ID internal property for
edges, and then use that to do lookups.

joshro> Tracing through the implementation a bit of add_edge, I have an
joshro> idea on how to do this, but it involves a fair bit of hacking and
joshro> is not terribly clean (and probably doesn't work!):  you could
joshro> directly go into the edge_desc_impl class (really it's superclass
joshro> edge_base) [from detail/edge.hpp] and swap the m_source and
joshro> m_target members directly, then remove the edge from the source
joshro> vertex edge list, create a StoredEdge instance and insert it into
joshro> the target edge list.  But I'm not sure how to link this new
joshro> stored edge with the old edge_descriptor.

I suppose I could add the following function:

reverse_edge(edge_descriptor e, graph& g)

which would do what you are describing. However, if the property copying
solution described above works for you, I'd rather not add the
reverse_edge function.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------