Re: BGL and reversing / moving edges

From: Matthias Kronenberger (mkronen_at_[hidden])
Date: 2002-07-25 12:16:52

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" <joshrose_at_[hidden]>
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
>
> --- In Boost-Users_at_y..., "joshrose" <joshrose_at_y...> wrote:
> > 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.
>
>
>