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@gmail.com