Re: [boost] [gsoc] Min Cost Flow in Boost Graph library

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
andrew.n.sutton_at_[hidden]