new planar_vertex_six_coloring() algorithm with examples, tests and doc

[Hermann-SW]

Why planar_vertex_six_coloring() is useful can be seen in the first of three tests for that algorithm. The existing sequential_vertex_coloring() can be forced to use $k$ colors for any $k$ (k=15 in test). Planar graphs can always be 4-colored, but algorithm for that has quadratic runtime. planar_vertex_six_coloring() has linear runtime.

For that runtime a copy of the graph needs to be used, that allows for constant time edge removal. For that purpose new class undirected_graph_constant_time_edge_add_and_remove derived from undirected_graph was implemented. To do its job a new protected member function removeedge() was added to undirected graph that allows for O(1) edge removal if both out_edge_iterator of an edge are passed (which the new class does).

The example for undirected_graph_constant_time_edge_add_and_remove does demonstrate quadratic runtime of undirected graph for a task needed for 6-coloring algorithm, while new class shows only linear time for that:

pi@raspberrypi5:~/graph/example $ g++ -O3 undirected_graph_constant_time_edge_add_and_remove.cpp 
pi@raspberrypi5:~/graph/example $ ./a.out 
Wn    ugraph_o1 ugraph     runtimes [s]
2000  0.000292  0.00743
4000  0.000917  0.04115
8000  0.002566  0.275956
16000  0.006217  1.69308
32000  0.016996  19.8986
pi@raspberrypi5:~/graph/example $ 

The planar_vertex_six_coloring() example creates a random maximal planar graph with 1million edges, and 6-colors it in few seconds:

pi@raspberrypi5:~/graph/example $ g++ -O3 planar_vertex_six_coloring.cpp 
pi@raspberrypi5:~/graph/example $ ./a.out 
simple_maximal_planar_random_graph(g, argc < 2 ? 333335 : atoi(argv[1])); 0.505189s
333335 vertices
999999 egdes
vertices_size_type num_colors = planar_vertex_six_coloring(g, color); 1.35317s
6 colors
vertex coloring verified
pi@raspberrypi5:~/graph/example $ 

Finally the test of new algorithm does compare sequential_vertex_coloring() and planar_vertex_six_coloring() on

1. crafted graph that forces sequential coloring to use 15 colors (on graph with 1000 vertices)
2. new planar_input_graphs/pentakis_dodecahedron.leda
3. new planar_input_graphs/maximal_planar_1000.leda

Without arguments passed it is just the needed test, with arguments "15 output" it does the same as test does and generates output:

pi@raspberrypi5:~/graph/test $ g++ -O3 planar_vertex_six_coloring.cpp 
pi@raspberrypi5:~/graph/test $ ./a.out 
No errors detected.
pi@raspberrypi5:~/graph/test $ ./a.out 15 output
create(g, k); 0.000174
vertices_size_type num_colors = sequential_vertex_coloring(g, color); 2e-05
vertices_size_type num_color6 = planar_vertex_six_coloring(g, color); 0.000472
987/1595 vertices/edges
15/6 colors used
read_leda_graph(g, "planar_input_graphs/pentakis_dodecahedron.leda"); 0.000285
num_colors = sequential_vertex_coloring(g, color); 4e-06
num_color6 = planar_vertex_six_coloring(g, color); 2.3e-05
32/90 vertices/edges
5/4 colors used
read_leda_graph(g, "planar_input_graphs/maximal_planar_1000.leda"); 0.000683
num_colors = sequential_vertex_coloring(g, color); 5.4e-05
num_color6 = planar_vertex_six_coloring(g, color); 0.000738
1000/2994 vertices/edges
6/6 colors used
No errors detected.
pi@raspberrypi5:~/graph/test $ 

This is my first pull request for boost. So I tried to provide clean code, with examples and test. And with new documentation for the derived class and the new algorithm. I used existing doc for undirected_graph and sequential_vertex_coloring as basis for new doc.

[Hermann-SW]

I need help. I tried to fix the issues in new code for the PR. Still CI is failing, but for code outside of my changes. With 1.86 Graph requires C++14.

Who will resolve these issues outside of my PR? If I should do, what steps are needed by me? Should they be part of this PR?

Examples from: https://drone.cpp.al/boostorg/graph/252/1/2

gcc.compile.c++ ../../../bin.v2/libs/graph/test/gursoy_atun_layout_test.test/gcc-5/debug/x86_64/cxxstd-11-iso/threading-multi/visibility-hidden/gursoy_atun_layout_test.o
In file included from ../../../boost/math/constants/constants.hpp:11:0,
                 from ../../../boost/graph/topology.hpp:16,
                 from ../../../boost/graph/gursoy_atun_layout.hpp:34,
                 from gursoy_atun_layout_test.cpp:10:
../../../boost/math/tools/config.hpp:28:6: warning: #warning "Boost.Math requires C++14" [-Wcpp]
 #    warning "Boost.Math requires C++14"
      ^
In file included from ../../../boost/math/tools/mp.hpp:15:0,
                 from ../../../boost/math/policies/policy.hpp:11,
                 from ../../../boost/math/constants/constants.hpp:16,
                 from ../../../boost/graph/topology.hpp:16,
                 from ../../../boost/graph/gursoy_atun_layout.hpp:34,
                 from gursoy_atun_layout_test.cpp:10:
../../../boost/math/tools/type_traits.hpp:208:12: error: 'std::is_final' has not been declared
 using std::is_final;

 In file included from ../../../boost/math/tools/mp.hpp:15:0,
                 from ../../../boost/math/policies/policy.hpp:11,
                 from ../../../boost/math/constants/constants.hpp:16,
                 from ../../../boost/graph/topology.hpp:16,
                 from ../../../boost/graph/fruchterman_reingold.hpp:16,
                 from layout_test.cpp:16:
../../../boost/math/tools/type_traits.hpp:426:34: warning: variable templates only available with -std=c++14 or -std=gnu++14
 BOOST_MATH_INLINE_CONSTEXPR bool is_nothrow_default_constructible_v = boost::math::is_nothrow_default_constructible<T>::value;
                                  ^

The CI seems not to know that it should not test below C++14. Who can fix that?

https://www.boost.org/users/history/version_1_86_0.html

...
Graph:
Major update: C++14 is the new minimum standard; this was partly dictated 
by dependencies (at least to C++11) and partly by choice. If you require 
support for an older standard, please contact the maintainer.
...

[grisumbras]

C++11 CI jobs are launched due to lines like this: https://github.com/boostorg/graph/blob/develop/.drone.star#L17

If you remove those lines, those jobs will disappear.

[jeremy-murphy]

Thanks, and sorry, I'm a bit behind with updating the CI configuration.

[jeremy-murphy]

I fixed develop, so please update your branch to resolve the conflicts.

[jeremy-murphy]

Now, I forgot to say: thank you for a most interesting algorithm proposal. I'm not certain, but I imagine most algorithms and data structures in Boost.Graph are based on published literature, so although I am quite happy and even excited to accept novel algorithms and data structures, there is a higher burden of proof on the part of the contributor to demonstrate good theoretical design.

It will take some time to evaluate, and if there are any issues found then it may require several rounds of review and evolution, but don't be despondent, that's how we (try to) maintain high quality.

[Hermann-SW]

Sorry that I did not mention the literature, it is:

Marek Chrobak, David Eppstein "Planar orientations with low out-degree and compaction of adjacency matrices" Theoretical Computer Science 1991 https://dl.acm.org/doi/10.1016/0304-3975%2891%2990020-3

Without paywall from author: https://core.ac.uk/download/pdf/82533794.pdf

This code implements the determination of 5-bounded acyclic orientation of G, the order of vertices visited is in vector "visited": https://github.com/Hermann-SW/graph/blob/develop/include/boost/graph/planar_vertex_six_coloring.hpp#L80-L103

Before https://github.com/Hermann-SW/graph/blob/develop/include/boost/graph/planar_vertex_six_coloring.hpp#L55-L77 only creates a copy U of input graph G of new type undirected_graph_with_constant_time_edge_add_and_remove with linkage (diagram in source code) in both directions. Only graph U allows to determine the 5-bounded acyclic orientation of G in linear time (see quadratic runtime demo of undirected_graph for this task in initial comment of this PR).

Finally https://github.com/Hermann-SW/graph/blob/develop/include/boost/graph/planar_vertex_six_coloring.hpp#L106-L124 assigns the lowest possible color to vertex v, different to its at most 5 neighbors from the acyclic orientation. The vertices get colored in reverse order as visted while determining the 5-bounded acyclic orientation. This step guarantees to color the input graph with at most 6 colors.

Now that you opened the discussion, the first two parts just determine the order for coloring the vertices with at most 6 colors. After having submitted I realized that the 3rd part can be replaced with a single call to sequential_vertex_coloring() with passing the order determined as 3rd argument:
https://www.boost.org/doc/libs/1_86_0/libs/graph/doc/sequential_vertex_coloring.html
If you agree, I can replace lines 106-124 with the call.

And add a comment "determine 5-bounded acyclic orientation" with link to literature for 2nd part.
And add a comment "determine copy U of G with linkage" to 1st part.

[Hermann-SW]

I asked myself whether new class undirected_graph_constant_time_edge_add_and_remove is really needed, and it is. Reason is that from user code only iterator of a vertices out_edges() can be accessed, but not the out_edges list itself. That list would be needed for calling std::list erase() from user code.

[Hermann-SW]

@jeremy-murphy There is an infrastructure problem making only Linux clang++ 9.17 eyerything fail, not my code according log. Can you help to get the CI run again?

[jeremy-murphy]

I've noticed a couple of odd things about the CI lately, I might have to ask someone with more intimate knowledge of it to have a look.

[jeremy-murphy]

Btw I don't think I can re-run the CI on the same commit. I think it requires a new commit to trigger it, or possibly closing and reopening the PR might work.

[grisumbras]

That's a transient error.

[grisumbras]

@jeremy-murphy if you can't rerun Drone builds, ask @sdarwin to give you the necessary permissions.

[Hermann-SW]

@jeremy-murphy @grisumbras Thanks for rerunning, again it is failing for clang++ 9.17 everything only. No indication that my code is responsible. Also with return code 0 and no error message. How to handle this now?

[grisumbras]

I don't think there was a rerun. If you follow the Drone link, you can see that the build is from the 2nd of November.

[sdarwin]

After re-running, the job succeeded.
You can either click 'restart' from the upper-right corner in drone, or push a small change to the pull request.

[Hermann-SW]

@grisumbras @jeremy-murphy This pull request consists of 14 new or changed files. Since I created the pull request 6 weeks ago I have learned much more on how to do things better with Boost graph.

Before I do the changes proposed, I want to ask you whether I should do the code improvement or not.

These 3 files are not needed anymore:

• doc/undirected_graph_constant_time_edge_add_and_remove.html
• example/undirected_graph_constant_time_edge_add_and_remove.cpp
• include/boost/graph/undirected_graph_constant_time_edge_add_and_remove.hpp

The changes in these two deep graph files can be reverted as they are not needed anymore:

• include/boost/graph/detail/adjacency_list.hpp
• include/boost/graph/undirected_graph.hpp

The pull request would then consist of these 9 files only:

• include/boost/graph/planar_vertex_six_coloring.hpp
• example/planar_vertex_six_coloring.cpp
• test/Jamfile.v2
• test/planar_vertex_six_coloring.cpp
• test/planar_input_graphs/pentakis_dodecahedron.leda
• test/planar_input_graphs/maximal_planar_1000.leda
• doc/table_of_contents.html
• doc/planar_vertex_six_coloring.html
• doc/figs/planar_vertex_coloring_with_5.png

So how does the simpification work? New class o1_edge_visitor derived from "edge_index_update_visitor" allows for the needed O(1) remove_edge(). I created a complete self-contained demo in this gist (with comments) for review: https://gist.github.com/Hermann-SW/539d2396e567a2ee26f4e0213f3b5fe7

1) There is only one use of "g.impl()" in new visit_edge() that removes an edge in O(1) by moving both out_edge_iterators of the edge to the fist positions in the out_edge_lists.

Use of "g.impl()" is essential, without no O(1) remove_edge is possible. Is that OK?

2) https://en.cppreference.com/w/cpp/iterator/prev states: "Although the expression --c.end() often compiles, it is not guaranteed to do so"

I tried to use "std::prev()" in line 49, but then the code just hangs indefinitely, so I cannot use it?

Thanks in advance for your help.

[jeremy-murphy]

After re-running, the job succeeded. You can either click 'restart' from the upper-right corner in drone, or push a small change to the pull request.

Thanks, Sam!

[jeremy-murphy]

@jeremy-murphy if you can't rerun Drone builds, ask @sdarwin to give you the necessary permissions.

@sdarwin, is that possible? It would sure come in handy some times.

[sdarwin]

It would sure come in handy some times.

Most drone permissions are based on github.

• Log into github in the browser.
• Then, visit https://drone.cpp.al and log in (with github)

The admin permissions will carry over.