[Boost][BGL] new planar_vertex_coloring.hpp ?
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_color... 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/undi... 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_a... 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.
On 2024-07-28 23:51, hermann@stamm-wilbrandt.de wrote:
... I would start by taking https://www.boost.org/doc/libs/1_85_0/libs/graph/doc/sequential_vertex_color... 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/undi... 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?permalin... 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.
On 2024-07-30 14:13, hermann@stamm-wilbrandt.de wrote:
On 2024-07-28 23:51, hermann@stamm-wilbrandt.de 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... 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/f7cff30d7d592c7b91d4cd33ea304b9b4... 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_co... $ 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.
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-statemen... Regards, Hermann.
participants (1)
-
hermann＠stamm-wilbrandt.de