Hello all, I've implemented an algorithm for computing a maximum cardinality matching in an undirected graph for the BGL. A matching in an undirected graph is a set of edges such that no two meet in a common vertex. A maximum cardinality matching has the maximum number of edges over all matchings in the graph. I uploaded the source, some tests, and documentation to the boost sandbox file vault under the directory "maximum_cardinality_matching." Any feedback would be appreciated. I developed and tested under gcc 3.3.3 on cygwin and currently don't have access to any other C++ compilers, so I'd be particularly interested in feedback about whether the tests compile and run correctly under other compilers. Thanks, Aaron Windsor
Hi Aaron, On Sep 1, 2005, at 4:57 PM, Aaron Windsor wrote:
I uploaded the source, some tests, and documentation to the boost sandbox file vault under the directory "maximum_cardinality_matching." Any feedback would be appreciated. I developed and tested under gcc 3.3.3 on cygwin and currently don't have access to any other C++ compilers, so I'd be particularly interested in feedback about whether the tests compile and run correctly under other compilers.
I've read through the documentation and skimmed the implementation, and I think it's in good shape to go right into the BGL for the next major release (1.34.0). I'll integrate it into CVS tomorrow morning, and we should start getting feedback from other compilers within a day or so. Thanks for the contribution! Doug
On Sep 6, 2005, at 5:08 PM, Doug Gregor wrote:
I've read through the documentation and skimmed the implementation, and I think it's in good shape to go right into the BGL for the next major release (1.34.0). I'll integrate it into CVS tomorrow morning, and we should start getting feedback from other compilers within a day or so. Thanks for the contribution!
... and now it's integrated into CVS. Aaron, do you have the reference to Edmond's original algorithm? I'd like to add it to the bibliography. Doug
On Sep 6, 2005, at 5:08 PM, Doug Gregor wrote: ... and now it's integrated into CVS. Aaron, do you have the reference to Edmond's original algorithm? I'd like to add it to the bibliography.
Doug
Thanks, Doug. The missing reference is: J. Edmonds <i>Paths, trees, and flowers</i> Canadian Journal of Mathematics 17 (1965), pp. 449-467. -Aaron
participants (2)
-
Aaron Windsor -
Doug Gregor