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

From: hermann_at_[hidden]
Date: 2024-08-15 22:08:05

On 2024-08-12 02:36, Hermann Stamm-Wilbrandt via Boost wrote:
> --%<--
> 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().
> --%<--
> 
Vertical prototype implementation is complete.

I resolved storage problems in
class undirected_graph_constant_time_edge_add_and_remove
derived from undirected_graph by using private
std::list< std::pair< out_edge_iterator, out_edge_iterator > > storage;

Today I completed implementation of "planar_vertex_six_coloring()".
I learned much in the last 18 days I worked on this.
I use vertex properties for mapping from undirected graph types
with listS vertex selector and "make_container_vertex_map()" for
mapping from adjacency_list graphs with vecS vertex selector.

test/planar_vertex_coloring.cpp runs by default with k=15 and creates
a planar graph on 987 vertices and 1595 edges. On that graph new
planar_vertex_six_coloring() uses 6 colors, while Boost
sequential_vertex_coloring() uses 15 colors.

For initial timing analysis I switched to AMD 7950X CPU and
switched to k=35 in test. The created planar graph has
14.9million vertices and 24.2million edges, and creation alone takes
3.048s.

sequential_vertex_coloring() colors with 35 colors in time
3.346-3.048=0.298s.

planar_vertex_six_coloring() in its initial working version
with lots of validation assertion loops colors with 6 colors
in time 10.897-3.048=7.849s. Much slower than sequential
vertex coloring, but for 24.8million vertex graph not that bad.
More timing analysis and code improvement needed.

Find details here:
https://github.com/Hermann-SW/graph?tab=readme-ov-file#fork-mission-statement

Regards,

Hermann.