[BGL] Maximum Weight Matching
Hello, We wrote the attached code in c++ using Boost, Blossom V and Guido Shafer Reduction to compute Maximum-Weight-Matching (not necessarily perfect) of a graph. We want to contribute to Boost BGL library. We are not experts in boost BGL library but we think that this code can be improved and used in Boost. We wrote this code becouse we need this algorithm and it wasn't in Boost. Although it is in Lemon Library ( http://lemon.cs.elte.hu/pub/doc/1.2.3/a00537.html) we need other algorithms and functions that are only in Boost. Thank you very much
Hi, I'd be very glad to see this algorithm in boost bgl. I don't want to interfere with the library maintainer, but there are some issues that bother me - The code is not header-only what is one of the main assumptions of BGL. - The big issue is to adjust the algorithm to standard bgl design pattern (for example algorithms use named_parameters). I think it is a good idea to read carefully implementation of some simple algorithm from bgl and copy the patterns. This includes also trivial things like missing licenses, namespaces etc. - Functions should be templated to achieve appropriate level of genericity. - There are many big macros, many of them looks just like a function for example GET_PENULTIMATE_BLOSSOM(j) - There are many not-necessary heap allocation. For example there is often a pattern void f() { A * a = new A; ... delete a; } instead of just void f() { A a; } - There are c arrays instead of std::vector (generally the code looks like c-style c++) I'm hoping to see this algorithm in the next boost release! Regards, Piotr Wygocki On 8 October 2013 04:43, Pablo Madoery <madoerypablo@gmail.com> wrote:
Hello, We wrote the attached code in c++ using Boost, Blossom V and Guido Shafer Reduction to compute Maximum-Weight-Matching (not necessarily perfect) of a graph. We want to contribute to Boost BGL library. We are not experts in boost BGL library but we think that this code can be improved and used in Boost. We wrote this code becouse we need this algorithm and it wasn't in Boost. Although it is in Lemon Library ( http://lemon.cs.elte.hu/pub/doc/1.2.3/a00537.html) we need other algorithms and functions that are only in Boost.
Thank you very much
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Piotr Wygocki Thank you very much for your feedback. We Will try to make the changes you propose. 2013/10/9 Piotr Wygocki <vwygos@gmail.com>
Hi, I'd be very glad to see this algorithm in boost bgl. I don't want to interfere with the library maintainer, but there are some issues that bother me - The code is not header-only what is one of the main assumptions of BGL.
- The big issue is to adjust the algorithm to standard bgl design pattern (for example algorithms use named_parameters). I think it is a good idea to read carefully implementation of some simple algorithm from bgl and copy the patterns. This includes also trivial things like missing licenses, namespaces etc.
- Functions should be templated to achieve appropriate level of genericity.
- There are many big macros, many of them looks just like a function for example GET_PENULTIMATE_BLOSSOM(j)
- There are many not-necessary heap allocation. For example there is often a pattern void f() { A * a = new A; ... delete a; } instead of just void f() { A a; }
- There are c arrays instead of std::vector (generally the code looks like c-style c++)
I'm hoping to see this algorithm in the next boost release!
Regards,
Piotr Wygocki
On 8 October 2013 04:43, Pablo Madoery <madoerypablo@gmail.com> wrote:
Hello, We wrote the attached code in c++ using Boost, Blossom V and Guido Shafer Reduction to compute Maximum-Weight-Matching (not necessarily perfect) of a graph. We want to contribute to Boost BGL library. We are not experts in boost BGL library but we think that this code can be improved and used in Boost. We wrote this code becouse we need this algorithm and it wasn't in Boost. Although it is in Lemon Library ( http://lemon.cs.elte.hu/pub/doc/1.2.3/a00537.html) we need other algorithms and functions that are only in Boost.
Thank you very much
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, 9 Oct 2013, Piotr Wygocki wrote:
Hi, I'd be very glad to see this algorithm in boost bgl. I don't want to interfere with the library maintainer, but there are some issues that bother me - The code is not header-only what is one of the main assumptions of BGL.
- The big issue is to adjust the algorithm to standard bgl design pattern (for example algorithms use named_parameters). I think it is a good idea to read carefully implementation of some simple algorithm from bgl and copy the patterns. This includes also trivial things like missing licenses, namespaces etc.
- Functions should be templated to achieve appropriate level of genericity.
- There are many big macros, many of them looks just like a function for example GET_PENULTIMATE_BLOSSOM(j)
- There are many not-necessary heap allocation. For example there is often a pattern void f() { A * a = new A; ... delete a; } instead of just void f() { A a; }
- There are c arrays instead of std::vector (generally the code looks like c-style c++)
I'm hoping to see this algorithm in the next boost release!
I agree with your criticisms. Please follow the guidelines at <URL:http://www.boost.org/development/requirements.html> and its linked pages in terms of naming conventions, directory structure, license, etc. The license, in particular, is a show-stopper for inclusion in Boost. -- Jeremiah Willcock
participants (3)
-
Jeremiah Willcock -
Pablo Madoery -
Piotr Wygocki