Re: BGL and reversing / moving edges

From: joshrose (joshrose_at_[hidden])
Date: 2002-07-25 12:54:26

Thanks for the reply.  I'm not quite sure I understand -- are edge
descriptors guaranteed to be std::pairs of vertex descriptors? 
Perhaps I was looking in the wrong place, but tracing through a call
to add_edge, I wind up in detail/edge.hpp, in the definition of a
class called edge_desc_impl when a new edge is created.  (called from
add_edge (Config::vertex_descriptor, Config::vertex_descriptor, const
Config::edge_property_type&, directed_graph_helper<Config>&) in
adjacency_list.hpp)

Since this is a multigraph, though, memberwise comparison of the
source and target can't be enough to disambiguate one edge from
another.  (They could have the same source and target, but have quite
different properties associated with them by the property maps).  Is
an edge_descriptor, then, the address of the std::pair object, if that
is indeed what's representing edges?  If so, then I need to reuse the
existing edge descriptor object.  Changing the m_source and m_target
(or first and second, if it is indeed a non-const std::pair) is pretty
straightforward, but I feel that that's probably not all that needs to
be done -- somehow it needs to be removed from the old source edge
list and added to the old target edge list.  (On a somewhat related
note, I'm not exactly sure what the m_eproperty member of
edge_desc_impl is for, or if I'd need to update that in some way).

Just to try to clarify, I'm not changing the vertex set of the graph
in any way -- all I want to do is take an existing edge in the graph
and move it to a different source / target pair (reversing being an
example of this) in a way that doesn't invalidate property maps that
refer to this edge.  The non-invalidation of property maps is the most
crucial part -- if the new edge got a different edge descriptor, but
somehow all property maps were automagically updated to point to this
new value, it would be just as useful as just keeping the edge
descriptor the same (though I suspect not terribly realistic).

I'm sorry if I'm not being terribly clear on this and for having a bit
of trouble understanding, and I really appreciate the help.

-Josh

--- In Boost-Users_at_y..., "Matthias Kronenberger" <mkronen_at_r...> wrote:
> 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_y...>
> 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.
> >
> >
> >