-
-
Save Hermann-SW/5e74ee13fbf1d0103061e95d8a67c2f7 to your computer and use it in GitHub Desktop.
| #include <fstream> | |
| #include <boost/graph/sequential_vertex_coloring.hpp> | |
| #include <boost/graph/adjacency_list.hpp> | |
| #include <boost/graph/graph_utility.hpp> | |
| using namespace boost; | |
| template <class graphType> | |
| void | |
| read_leda_graph(graphType& g, char* gname) { | |
| int n, m; | |
| char line[200]; | |
| std::ifstream in(gname); | |
| assert(in); | |
| in >> line; | |
| in >> line; | |
| in >> line; | |
| in >> n; | |
| g = graphType(n); | |
| for (int i=1; i <= n; ++i) { | |
| in >> line; | |
| } | |
| in >> m; | |
| for (int i=1; i <= m; ++i) { | |
| int s, t, v; | |
| in >> s >> t >> v; | |
| add_edge(s-1, t-1, g); | |
| } | |
| } | |
| int main(int argc, char*argv[]) { | |
| typedef adjacency_list< listS, vecS, undirectedS > Graph; | |
| typedef graph_traits< Graph >::vertices_size_type vertices_size_type; | |
| typedef property_map< Graph, vertex_index_t >::const_type vertex_index_map; | |
| assert(argc == 2); | |
| Graph g; | |
| read_leda_graph(g, argv[1]); | |
| std::vector< vertices_size_type > color_vec(num_vertices(g)); | |
| iterator_property_map< vertices_size_type*, vertex_index_map, | |
| vertices_size_type, vertices_size_type& > | |
| color(&color_vec.front(), get(vertex_index, g)); | |
| vertices_size_type num_colors = sequential_vertex_coloring(g, color); | |
| std::cout << num_colors << std::endl; | |
| BGL_FORALL_VERTICES_T(v, g, Graph) { | |
| std::cerr << get(color, v) << " "; | |
| } | |
| std::cerr << std::endl; | |
| return 0; | |
| } |
Gist 7c.u has a constructed planar graph on 14 vertices and 31 edges on that sequential_vertex_coloring() needs 7 colors (every planar graph allows for a 4-coloring of its vertices). The second line is the assignment of the colors for vertex indices 0..13:
$ ./seqcol 7c.u
7
0 1 2 3 0 1 2 3 4 5 0 1 2 6
$
Using straight_line_graphviz.cpp this is planar embedding of graph 7c.u (the dotted lines are added triangulation edges needed for Boost chrobak_payne_straight_line_drawing() being able to determine the straight line drawing). Can be viewed with this GraphvizFiddle share link as well, or GraphvizFiddle.py gist:
$ GraphvizFiddle.py firefox <(~/straight_line_graphviz 7c.u)
$
Extending 7c.u, gist 8c.u is 22 vertices and 54 edges planar graph forcing sequential_vertex_coloring() with default ordering to use 8 colors:
$ ./seqcol 8c.u
8
0 1 2 3 0 1 2 3 4 5 0 1 2 6 0 1 2 3 0 4 5 7
$
Can be viewed with this GraphvizFiddle share link as well:
Using randomgraph tool to create random maximal planar graphs of various sizes the number of colors used by Boost
sequential_vertex_coloring()is evaluated.For 1000 random maximal planar graphs of 100 vertices, 79% did need 5 colors, while 21% needed 6 colors for vertex coloring.
For 1000 random maximal planar graphs of 1000 vertices, 8.2% did need 5 colors, while 91.8% needed 6 colors for vertex coloring.
For bigger random maximal planar graphs (10,000, 100,000 and 1,000,000 vertices) 100% of the graphs did need 6 colors.