#8317 closed Patches (fixed)
Edge coloring
| Reported by: | Owned by: | Jeremiah Willcock | |
|---|---|---|---|
| Milestone: | To Be Determined | Component: | graph |
| Version: | Boost 1.52.0 | Severity: | Not Applicable |
| Keywords: | Cc: |
Description
Currently there is no edge coloring algorithm in boost. While it is possible to color line graph it is suboptimal as:
- It uses in worst case 2d-1 colors where d is maximum degree of graph
- It requires additional bookkeeping (creation of line graph, storing edge numbering, etc).
The attached patch allows to color in-place using at most d+1 colors.
Attachments (3)
Change History (11)
by , 10 years ago
| Attachment: | 0001-Added-edge-coloring-algorithm.patch added |
|---|
follow-ups: 2 3 comment:1 by , 9 years ago
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 asout_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 useBGL_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.
comment:2 by , 9 years ago
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.
by , 9 years ago
| Attachment: | 0001-Added-edge-coloring-algorithm.2.patch added |
|---|
0001-Added-edge-coloring-algorithm.patch
comment:3 by , 9 years ago
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 asout_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 useBGL_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.
comment:4 by , 9 years ago
| Resolution: | → fixed |
|---|---|
| Status: | new → closed |
follow-up: 6 comment:5 by , 9 years ago
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.
comment:6 by , 9 years ago
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)?
follow-up: 8 comment:7 by , 9 years ago
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.
comment:8 by , 9 years ago
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.
Patch adding edge coloring