-
-
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.