Re: [Boost][BGL] new planar_vertex_coloring.hpp ?

From: hermann_at_[hidden]
Date: 2024-07-30 12:13:41

On 2024-07-28 23:51, hermann_at_[hidden] wrote:
> ...
> I would start by taking
> https://www.boost.org/doc/libs/1_85_0/libs/graph/doc/sequential_vertex_coloring.html
> as a template for "planar_vertex_coloring.hpp".
> 
> My plan is to first port my existing fast linear time "six_coloring()"
> https://github.com/Hermann-SW/planar_graph_playground/blob/main/c%2B%2B/undirected_graph.hpp#L306-L329
> and learn about the review process with it.
> 
I made some investigations regarding Boost sequential_vertex_coloring() 
use of colors
for random maximal planar graphs of various sizes:
https://gist.github.com/Hermann-SW/5e74ee13fbf1d0103061e95d8a67c2f7?permalink_comment_id=5138088#gistcomment-5138088

For graphs of 100 or 1,000 vertices (always 1,000 graphs tested) some 
graphs did need 5 colors.
But for random maximal planar graphs with 10,000 or 100,000 vertices 
always 6 colors were used.

So next I crafted 7c.u and 8c.u small maximal planar graphs that force 
sequential_vertex_coloring()
to use 7 or even 8 colors. Details in the next comments of the gist 
pointed to.

My six_coloring() uses sequential vertex coloring as well, but with a 
special order of
vertices with the help of 5-compaction of input graph. So instead of 
completely port
my existing code pointed to in last email, I will determine the vertex 
order and call
Boost sequential_vertex_coloring() to determine vertex coloring with 
maximally 6 colors.

> 
> I looked at commits in Boost graph directory and there is not that much 
> recent
> activity. Is my plan and the steps outlined the right way to start?
> 
Am I good to proceed as planned?

Regards,

Hermann Stamm-Wilbrandt.