[boost] BGL Algorithm (Network Flow)

From: Tanton Gibbs (thgibbs_at_[hidden])
Date: 2004-07-06 14:16:32

I'm attempting to do a graph algorithm and am looking for a good BGL
algorithm to do this -- any advice would be appreciated.

Basically, I have a directed, weighted, bipartite graph.  I'll call the two
sets of nodes (V,W).  Every node in V connects to one or more nodes in W.
However, not every node in W is connected to.  When the algorithm ends, I
want every node in V to be connected to 0 or 1 node in W and no node in W
should have more than one connection to it.  I also want the total weight of
all the edges to be minimized (basically, prune the most costly edges to
create the graph), but no edge should be pruned unnecessarily (I want to
maximize the number of connected nodes).

It looks to me to be a pretty evil problem, but I'm hoping someone has a
good suggestion.

Thanks!

Tanton H. Gibbs, Ph.D.
Software Developer
Acxiom Corporation