Boost C++ Libraries: Ticket #8317: Edge coloring

attachment set

uzytkownik2@… — Wed, 20 Mar 2013 17:24:28 GMT

attachment → 0001-Added-edge-coloring-algorithm.patch

Patch adding edge coloring

Jeremiah Willcock — Thu, 23 May 2013 04:08:11 GMT

This code looks nice, and I'll put it into Boost.Graph when it is ready. Could you please write a documentation page for it and a simple test program? Also, here are some suggested changes to the code:

Please remove the boost:: qualifications on calls such as out_edges, put, etc. on generic types passed in by the user. The code needs to use argument-dependent lookup for those functions so that the user can define them in other namespaces. Uses of traits classes still need the namespaces, though.

Instead of BOOST_FOREACH, you can use BGL_FORALL_... from <boost/graph/iteration_macros.hpp> (don't worry about undefining the macros at the end of your file like some of the other parts of Boost.Graph do).

It appears that Phoenix is used once in the code. Wouldn't it be easier (and likely run faster) to use a manually-written function object? It seems like it would be short and quick to write.

Sun, 09 Jun 2013 13:22:19 GMT

Replying to jewillco:

This code looks nice, and I'll put it into Boost.Graph when it is ready. Could you please write a documentation page for it and a simple test program? Also, here are some suggested changes to the code:

Ok. I'll alter the code in a month when I'll have time to do it.

For anyone interested in using the code before it is upstreamed - there is small error in patch and graph is passed by value instead of by reference resulting in bad performance for large graphs AND crashing when run on subgraph. Changing ph::val(g) to ph::ref(g) should fix the issue.

attachment set

Mon, 15 Jul 2013 19:08:14 GMT

attachment → 0001-Added-edge-coloring-algorithm.2.patch

0001-Added-edge-coloring-algorithm.patch

Mon, 15 Jul 2013 19:11:45 GMT

Replying to jewillco:

This code looks nice, and I'll put it into Boost.Graph when it is ready. Could you please write a documentation page for it and a simple test program?

Done.

Also, here are some suggested changes to the code:

Please remove the boost:: qualifications on calls such as out_edges, put, etc. on generic types passed in by the user. The code needs to use argument-dependent lookup for those functions so that the user can define them in other namespaces. Uses of traits classes still need the namespaces, though.

Corrected. I didn't thought C++ is capable of 'namespace'-polymorphism.

Instead of BOOST_FOREACH, you can use BGL_FORALL_... from <boost/graph/iteration_macros.hpp> (don't worry about undefining the macros at the end of your file like some of the other parts of Boost.Graph do).

Done.

It appears that Phoenix is used once in the code. Wouldn't it be easier (and likely run faster) to use a manually-written function object? It seems like it would be short and quick to write.

Done. I would be surprised if there was a significant overhead due to creation of Phoenix objects on modern compilers with optimization turned on but I guess it was also to eliminate the dependency.

status changed; resolution set

Jeremiah Willcock — Sat, 31 Aug 2013 19:44:09 GMT

status new → closed
resolution → fixed

(In [85534]) Added edge coloring code from Maciej Piechotka; fixes #8317

Jeremiah Willcock — Sat, 31 Aug 2013 19:45:04 GMT

I added your code to the Boost trunk (with some fixes for Boost Inspection Tool warnings). Could you please write a test case (even something simple like testing on a random graph and making sure the result is a valid coloring)? Thank you.

Sat, 31 Aug 2013 19:48:09 GMT

Replying to jewillco:

I added your code to the Boost trunk (with some fixes for Boost Inspection Tool warnings). Could you please write a test case (even something simple like testing on a random graph and making sure the result is a valid coloring)? Thank you.

Thanks. What's wrong with libs/graph/example/edge_coloring.cpp from patch (and changeset)?

Jeremiah Willcock — Sat, 31 Aug 2013 20:12:26 GMT

It wasn't labeled as a test case, so I didn't know to put it into that directory. Also, it does not appear to do any validation of its results, so it would be hard to tell if your code broke at some point in the future.

Sat, 31 Aug 2013 20:14:08 GMT

Replying to jewillco:

It wasn't labeled as a test case, so I didn't know to put it into that directory. Also, it does not appear to do any validation of its results, so it would be hard to tell if your code broke at some point in the future.

Ups. Sorry - it's a bit late and I read 'example' instead of 'test case'. I will try to adopt it to test withing week.

attachment set

uzytkownik2@… — Sun, 29 Sep 2013 12:32:14 GMT

attachment → 0001-Add-tests-for-edge-coloring.patch

Tests for edge coloring