BGL and reversing / moving edges

From: joshrose (joshrose_at_[hidden])
Date: 2002-07-25 09:08:13

G'day,

I was hoping someone might be able to tell me if they've run into any
situations using BGL where they needed to move (or reverse (i.e. flip
the source and target)) an edge within a graph implemented as an
adjacency_list.  I'm working on an implementation of an algorithm for
max. weight bipartite matching ("the assignment problem"), and one of
the assumptions in the algorithm is that non-matched edges are
directed from one subgraph, A, to the other subgraph, B, and matched
edges are directed the other way.  Over the course of growing the
matching, a simple way to add and remove edges from the candidate set
is just to reverse the edge, thus the need for some way to reverse the
edge within BGL.

I don't think I can just remove and then re-add the edge in the other
direction, primarily because doing so will (I believe) invalidate any
edge_descriptors referring to that edge.  In particular, there are
property maps keeping track of the weight of edges, the predecessors
of certain nodes, etc. that use edge descriptors as keys.  I've spent
a fair bit of time reading the documentation and looking through the
implementation of adjacency_lists (incl. edge_list_impl), and I'm not
really sure of a way to either move an edge directly within a graph,
or even to create a new edge from another s.t. they have the same
edge_descriptor (in general a bad thing, probably).

Anyone have any thoughts on this?

Thanks,

-Josh