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

...

refered to by long-lived entities (e.g. property maps).

Thanks,

-Josh

...

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

--- In Boost-Users@y..., "joshrose" wrote: 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

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@y..., "Matthias Kronenberger" wrote: that is 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@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.