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

From: hermann_at_[hidden]
Date: 2024-08-12 00:36:00

On 2024-07-30 14:13, hermann_at_[hidden] wrote:
> On 2024-07-28 23:51, hermann_at_[hidden] wrote:
--%<--
> 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.
> 
I made progress, new testcase creates a planar graph verifying that
sequential_vertex_coloring() has to use 15 colors (planar graphs
can always be vertex colored with 4 colors):
https://github.com/Hermann-SW/graph/blob/develop/test/planar_vertex_coloring.cpp

A needed operation for planar_vertex_six_coloring() to work is
O(1) remove_edge(). I was successful in implementing that, with
a single (later protected) new function in undirected_graph.h:
https://github.com/Hermann-SW/graph/commit/f7cff30d7d592c7b91d4cd33ea304b9b456df1b0

I will have to use "void remove_edge(std::pair< void*, void* > p)"
until I find a solution for working recursive type definitions of
undirected_graph with edge property and out_edge_iterator.

Plan is use derived class 
undirected_graph_constant_time_edge_add_and_remove
which does the needed additional stuff for add_edge() and remove_edge().
A non-class working example is here:
https://github.com/Hermann-SW/graph/blob/develop/example/undirected_graph_constant_time_edge_add_and_remove.cpp

$ f=undirected_graph_constant_time_edge_add_and_remove
$ g++ -Wall -Wextra -pedantic $f.cpp -o $f
$
$ f=undirected_graph_constant_time_edge_add_and_remove
$ cpplint --filter=-runtime/references,-whitespace/braces $f.cpp
Done processing undirected_graph_constant_time_edge_add_and_remove.cpp
$ g++ -Wall -Wextra -pedantic $f.cpp -o $f
$ ./$f
0 <--> 1 2 3
1 <--> 2 0 3
2 <--> 1 0 3
3 <--> 0 1 2
6 edges

0 <--> 3
1 <--> 3
2 <-->
3 <--> 0 1
2 edges
0--3
1--3
$

Regards,

Hermann Stamm-Wilbrandt.