Last active
August 14, 2024 23:02
-
-
Save Hermann-SW/cc583005925ad5598f1fb759be8985f9 to your computer and use it in GitHub Desktop.
create planar graph that forces arbitrary k colors being used by Boost "sequential_vertex_coloring()" with default order
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| f=challenge_sequential_vertex_coloring | |
| g++ -O3 -Wall -Wextra -pedantic $f.cpp -o $f | |
| cpplint --filter=-legal/copyright,-build/namespaces,-runtime/references $f.cpp | |
| ./$f 6 planar? writeLeda 2>C6.u | |
| GraphvizFiddle.py firefox <(straight_line_graphviz C6.u) | |
| */ | |
| #include <boost/graph/sequential_vertex_coloring.hpp> | |
| #include <boost/graph/adjacency_list.hpp> | |
| #include <boost/graph/graph_utility.hpp> | |
| #include <boost/graph/boyer_myrvold_planar_test.hpp> | |
| unsigned int fib(unsigned int n) { | |
| if (n <= 1) return n; | |
| return fib(n - 1) + fib(n - 2); | |
| } | |
| using namespace boost; | |
| typedef adjacency_list< listS, vecS, undirectedS > Graph; | |
| typedef graph_traits< Graph >::vertices_size_type vertices_size_type; | |
| typedef graph_traits< Graph >::vertex_descriptor vertex_descriptor; | |
| typedef graph_traits< Graph >::edge_descriptor edge_descriptor; | |
| typedef property_map< Graph, vertex_index_t >::const_type map_vertex_index; | |
| typedef iterator_property_map< vertices_size_type*, map_vertex_index, | |
| vertices_size_type, vertices_size_type& > color_iterator; | |
| /* | |
| creating C6 | |
| -5- | |
| /|\ | |
| ... | |
| from C5 | |
| / | |
| ---4 | |
| / /|\ / | |
| plus C3 / / | 3 | |
| / / / |/|\ | |
| plus C1 2 / / 2 | \ | |
| / / \ / / / / \| \ | |
| 0 0---1 0--1 0---1 0 | |
| */ | |
| edge_descriptor create(Graph& g, int k) { | |
| if (k < 4) { | |
| assert(k > 1); | |
| vertex_descriptor v = add_vertex(g); | |
| vertex_descriptor w = add_vertex(g); | |
| auto e = add_edge(v, w, g); | |
| if (k == 2) return e.first; | |
| vertex_descriptor x = add_vertex(g); | |
| add_edge(v, x, g); | |
| return add_edge(w, x, g).first; | |
| } | |
| std::vector<edge_descriptor> es; | |
| while (--k > 1) { | |
| es.push_back(create(g, k--)); | |
| } | |
| vertex_descriptor v = add_vertex(g); | |
| if (k == 1) { | |
| vertex_descriptor w = add_vertex(g); | |
| add_edge(v, w, g); | |
| v = w; | |
| } | |
| edge_descriptor e; | |
| for (auto ei = es.rbegin(); ei != es.rend(); ++ei) { | |
| add_edge(source(*ei, g), v, g); | |
| e = add_edge(target(*ei, g), v, g).first; | |
| } | |
| return e; | |
| } | |
| template <class graphType, class color_iterator> | |
| void | |
| write_leda_stderr(graphType& g, color_iterator color) { | |
| std::cerr << "LEDA.GRAPH\nint\nint" << std::endl; | |
| std::cerr << num_vertices(g) << std::endl; | |
| BGL_FORALL_VERTICES_T(v, g, Graph) { | |
| std::cerr << get(color, v) << std::endl; | |
| } | |
| std::cerr << num_edges(g) << std::endl; | |
| BGL_FORALL_EDGES_T(e, g, Graph) { | |
| std::cerr << source(e, g) + 1 << " " << target(e, g) + 1 | |
| << " " << 0 << std::endl; | |
| } | |
| } | |
| int main(int argc, char*argv[]) { | |
| int k = (argc > 1) ? atoi(argv[1]) : 2; | |
| Graph g; | |
| create(g, k); | |
| std::cout << num_vertices(g) << " vertices, " | |
| << num_edges(g) << " edges" << std::endl; | |
| assert(num_vertices(g) == fib(k+1)); | |
| assert(num_edges(g) == fib(k+2) - 2); | |
| std::cout << "#vertices == fib(" << k << "+1), #edges == fib(" | |
| << k << "+2)-2 asserted" << std::endl; | |
| std::vector< vertices_size_type > color_vec(num_vertices(g)); | |
| color_iterator color(&color_vec.front(), get(vertex_index, g)); | |
| vertices_size_type num_colors = sequential_vertex_coloring(g, color); | |
| std::cout << num_colors << " colors used by sequential_vertex_coloring()" | |
| << std::endl; | |
| if (argc > 2) { | |
| typedef std::vector< graph_traits< Graph >::edge_descriptor > vec_t; | |
| std::vector< vec_t > embedding(num_vertices(g)); | |
| assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
| boyer_myrvold_params::embedding = &embedding[0])); | |
| std::cout << "graph asserted to be planar" << std::endl; | |
| } | |
| if (argc > 3) write_leda_stderr(g, color); | |
| return 0; | |
| } |
Graph C6 per top comment demo, GraphvizFiddle share link (only graph size and node fontsize added manually):
pi@raspberrypi5:~ $ f=challenge_sequential_vertex_coloring
g++ -O3 -Wall -Wextra -pedantic $f.cpp -o $f
cpplint --filter=-legal/copyright,-build/namespaces,-runtime/references $f.cpp
./$f 6 planar? writeLeda 2>C6.u
GraphvizFiddle.py firefox <(straight_line_graphviz C6.u)
Done processing challenge_sequential_vertex_coloring.cpp
13 vertices, 19 edges
#vertices == fib(6+1), #edges == fib(6+2)-2 asserted
6 colors used by sequential_vertex_coloring()
graph asserted to be planar
pi@raspberrypi5:~ $
Corresponds to 2nd comment diagram:
/*
creating C6
-5-
/|\
...
from C5
/
---4
/ /|\ /
plus C3 / / | 3
/ / / |/|\
plus C1 2 / / 2 | \
/ / \ / / / / \| \
0 0---1 0--1 0---1 0
*/
The recursive algorithm is used in new boost graph library testcase with k=15:
https://github.com/Hermann-SW/graph/blob/develop/test/planar_vertex_coloring.cpp
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The created (recursive planar) graph forces k colors to be used by Boost sequential_vertex_coloring() with default order, and has fib(k+1) vertices and fib(k+2)-2 edges. So it is a sparse planar graph as average degree tends to two times the golden ratio (=3.236), while maximal planar graphs tend to 6 from below. This is just to demonstrate that the algorithm can use arbitrarily high number of colors, while planar graphs can always be colored with 4 colors. This is preparation of submitting new linear time six_coloring() for planar graphs to Boost, showing the potential value of the new function. On the other hand sequential_vertex_coloring() used always 6 colors for 1,000 random maximal planar graphs on 1 million vertices, though. Later new linear time five_coloring() will be provided as well, which will make a real difference. See list.booth.org posting and followup email for more details.
Maximal k=34 without and k=30 with planarity testing of the graph, on 4GB RAM Raspberry Pi5:
Maximal k=39 without and k=35 with planarity testing of the graph, on 32GB RAM AMD 7950X CPU: