[boost] BGL and moving / reversing edges

From: Josh Rosenblum (joshrose_at_[hidden])
Date: 2002-07-24 19:27:23

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