Modify

Ticket #8317 (closed Patches: fixed)

Opened 13 months ago

Last modified 8 months ago

Edge coloring

Reported by: uzytkownik2@… Owned by: jewillco
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

0001-Added-edge-coloring-algorithm.patch Download (7.1 KB) - added by uzytkownik2@… 13 months ago.
Patch adding edge coloring
0001-Added-edge-coloring-algorithm.2.patch Download (13.6 KB) - added by Maciej Piechotka <uzytkownik2@…> 9 months ago.
0001-Added-edge-coloring-algorithm.patch
0001-Add-tests-for-edge-coloring.patch Download (2.8 KB) - added by uzytkownik2@… 7 months ago.
Tests for edge coloring

Change History

Changed 13 months ago by uzytkownik2@…

Patch adding edge coloring

comment:1 follow-ups: ↓ 2 ↓ 3 Changed 11 months ago by 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:

  • 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.

comment:2 in reply to: ↑ 1 Changed 10 months ago by Maciej Piechotka <uzytkownik2@…>

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.

Changed 9 months ago by Maciej Piechotka <uzytkownik2@…>

0001-Added-edge-coloring-algorithm.patch

comment:3 in reply to: ↑ 1 Changed 9 months ago by Maciej Piechotka <uzytkownik2@…>

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.

comment:4 Changed 8 months ago by jewillco

  • Status changed from new to closed
  • Resolution set to fixed

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

comment:5 follow-up: ↓ 6 Changed 8 months ago by 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.

comment:6 in reply to: ↑ 5 Changed 8 months ago by Maciej Piechotka <uzytkownik2@…>

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)?

comment:7 follow-up: ↓ 8 Changed 8 months ago by 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.

comment:8 in reply to: ↑ 7 Changed 8 months ago by Maciej Piechotka <uzytkownik2@…>

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.

Changed 7 months ago by uzytkownik2@…

Tests for edge coloring

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.