Boost logo

Boost :

Subject: Re: [boost] [gsoc] Min Cost Flow in Boost Graph library
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-04-03 07:17:51

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

There are a couple of max flow/min cut algorithms available in the BGL, but
it's not an active area of development. The library definitely needs good
partitioning algorithms - they were suggested as a Summer of Code project.

> 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
> case.

There is not. I'm not sure if a separate data structure is needed for this
implementation, but I can see where such a structure would be of great use.

Boost is always open for submissions. New algorithms and data structures
generally go through a review process before inclusion in the release. I
would definitely encourage you to contribute new algorithms or data
structures for review. If you have any questions, let us know.

Andrew Sutton

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