Boost logo

Boost :

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


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?



Boost list run by bdawes at, gregod at, cpdaniel at, john at