Sequential Vertex Coloring
Computes a vertex coloring for the vertices in a graph using a greedy algorithm.
Complexity: O(V(d+k)) where d is max degree and k is the number of colors
Defined in: <boost/graph/sequential_vertex_coloring.hpp>
Example
// Sequential Vertex Coloring example
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/sequential_vertex_coloring.hpp>
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
int main() {
Graph g{5};
boost::add_edge(0, 1, g); boost::add_edge(0, 2, g);
boost::add_edge(1, 2, g); boost::add_edge(1, 3, g);
boost::add_edge(2, 4, g); boost::add_edge(3, 4, g);
std::vector<int> colors(boost::num_vertices(g));
auto color_map = boost::make_iterator_property_map(
colors.begin(), boost::get(boost::vertex_index, g));
int num_colors = boost::sequential_vertex_coloring(g, color_map);
std::cout << "Colors used: " << num_colors << "\n";
for (Vertex v = 0; v < boost::num_vertices(g); ++v) {
std::cout << " Vertex " << v << " -> color " << colors[v] << "\n";
}
}Colors used: 3
Vertex 0 -> color 0
Vertex 1 -> color 1
Vertex 2 -> color 2
Vertex 3 -> color 0
Vertex 4 -> color 1(1) With vertex ordering
template <class VertexListGraph, class OrderPA, class ColorMap>
typename property_traits<ColorMap>::value_type
sequential_vertex_coloring(
const VertexListGraph& g,
OrderPA order,
ColorMap color);| Direction | Parameter | Description |
|---|---|---|
IN |
|
The graph object on which the algorithm will be applied.
The type |
IN |
|
A mapping from integers in the range [0, num_vertices(g)) to the vertices of the graph. |
OUT |
|
This property map records the colors of each vertex. It must be a model of
Writeable Property Map
whose key type is the same as the vertex descriptor type of the graph and
whose value type is an integral type that can store all values of the
graph’s |
(2) Without vertex ordering
template <class VertexListGraph, class ColorMap>
typename property_traits<ColorMap>::value_type
sequential_vertex_coloring(
const VertexListGraph& g,
ColorMap color);| Direction | Parameter | Description |
|---|---|---|
IN |
|
The graph object on which the algorithm will be applied.
The type |
OUT |
|
This property map records the colors of each vertex. It must be a model of
Writeable Property Map
whose key type is the same as the vertex descriptor type of the graph and
whose value type is an integral type that can store all values of the
graph’s |
Description
Computes a vertex coloring for the vertices in the graph, using a simple algorithm [4]. Given vertices ordered v1, v2, … , vn, for k = 1, 2, …, n the algorithm assigns vk to the smallest possible color. The algorithm does not guarantee an optimum coloring.
Here is the coloring that would be produced on a graph given the vertex ordering A, B, C, D, E.
Overload (2) uses a default ordering that matches the order produced by vertices(g).
Example
typedef adjacency_list<listS, vecS, undirectedS> Graph;
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef property_map<Graph, vertex_index_t>::const_type vertex_index_map;
typedef std::pair<int, int> Edge;
enum nodes {A, B, C, D, E, n};
Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A),
Edge(E, B) };
int m = sizeof(edge_array) / sizeof(Edge);
Graph g(edge_array, edge_array + m, n);
// Test with the normal order
std::vector<vertices_size_type> color_vec(num_vertices(g));
iterator_property_map<vertices_size_type*, vertex_index_map>
color(&color_vec.front(), get(vertex_index, g));
vertices_size_type num_colors = sequential_vertex_coloring(g, color);