Boost logo

Boost :

Subject: [boost] [gsoc] Min Cost Flow in Boost Graph library
From: shilp gupta (sublimehuman_at_[hidden])
Date: 2009-04-02 18:34:18


I am interested in contributing to the Boost Graph library with
algorithms. Some of my suggestions are,
- minimum cost flow
- weighted bupartite matching
- maximum flow (based on blocking flows)

I had a few questions to ask,
Is there any significant progress already in development or
implementation of minimum cost flow algorithms in Boost?

To the best of my knowledge, Boost does not have a structure for
bipartite graphs. Would it be appreciated if I work on one?
I know that these can be represented using standard graph structures
without much loss, but the simplicity (and scope) of bipartite graph's
can be used to reduce constants in the run times of algorithms on them
- maximum flow using blocking flows infact runs in O(sqrt(V)E) time
for calculating the maximum cardinality matching in the bipartite

Shilp Gupta

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