[Boost][BGL] new planar_vertex_coloring.hpp ?

From: hermann_at_[hidden]
Date: 2024-07-28 21:51:56

I have some experience in using BGL and porting my non-BGL graph code to 
BGL.

I want to create pull request for generating random maximal planar 
graphs.
I have 1994 technical report non-BGL implementation on gihub.

So before porting that, I want to get some experience on the Boost pull
request and review process.

I made use of the many planar graph algorithms in 
straight_line_graphviz.cpp gist:
https://gist.github.com/Hermann-SW/99d151a273d290ee0d843c79b2da26a8

So I thought on a providing planar graph vertex coloring algorthm(s) as 
handson.

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.

Later I would implement one of the several linear time "five_coloring()" 
algorithms:
https://en.wikipedia.org/wiki/Five_color_theorem#Linear_time_five-coloring_algorithm

And probably the quadratic time "four_coloring()" algorithm mentioned 
there as well.

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?

Regards,

Hermann Stamm-Wilbrandt.