This algorithm is to find coloring of a graph Algorithm: Let G = (V,E) be a graph with vertices v_1, v_2, ..., v_n. More...

Data Structures
struct	degree_compare_functor
	degree compare functor More...

class	dsatur2_coloring_helper
	helper used to color the graph. More...

struct	dsatur2_heap_compare_functor
	heap compare functor More...

class	dsatur_coloring_helper

struct	dsatur_d_list

struct	dsatur_degree_compare_functor

struct	dsatur_degree_predicate_functor

struct	heap_compare_functor

class	maxclique_dsatur_coloring_helper

struct	select_vertex
	Predicate functor object used to select the proper set of vertices. More...

Functions
template<class VertexListGraph , class ColorMap >
property_traits< ColorMap >::value_type	degree_coloring (const VertexListGraph &G, ColorMap color)
	coloring of a graph following the descandant degree of vertices More...

template<typename VertexListGraph , typename ColorMap >
property_traits< ColorMap >::value_type	dsatur2_coloring (const VertexListGraph &G, ColorMap color)
	coloring of a graph following the DSATUR heuristic (version2) More...

template<typename VertexListGraph , typename ColorMap >
property_traits< ColorMap >::value_type	dsatur_coloring (const VertexListGraph &G, ColorMap color)
	coloring of a graph following the DSATUR heuristic (version1) More...

template<class VertexListGraph , class ColorMap >
property_traits< ColorMap >::value_type	unsorted_coloring (const VertexListGraph &G, ColorMap color)

template<typename VertexListGraph , typename ColorMap >
property_traits< ColorMap >::value_type	maxclique_dsatur_coloring (const VertexListGraph &G, ColorMap color)

Detailed Description

This algorithm is to find coloring of a graph Algorithm: Let G = (V,E) be a graph with vertices v_1, v_2, ..., v_n.

It is like the sequential algorithm, except that the order in which vertices are chosen is determined statically following the descendant degree coloring.

The color of the vertex v will be stored in color[v]. i.e., vertex v belongs to coloring color[v]

It is like the sequential algorithm, except that the order in which vertices are chosen is determined dynamically based on the number of colors that cannot be used because of conflicts with previously colored vertices. Vertices with the fewest available colors are colored first. The degree of vertices is dynamically modified during the coloring (as in the Michael A. Trick's implementation) while the order of vertices is based on a heap data structure. This implementation corrects an error in the first loop: j start has to start from 0 not from 1. Reference:

http://mat.gsia.cmu.edu/COLOR/color.html
New Methods to Color the Vertices of a Graph, Daniel Brelaz, CACM 22, 251–256, 1979.

The color of the vertex v will be stored in color[v]. i.e., vertex v belongs to coloring color[v]

It is like the sequential algorithm, except that the order in which vertices are chosen is determined dynamically based on the number of colors that cannot be used because of conflicts with previously colored vertices. Vertices with the fewest available colors are colored first. Instead of a circular lists data structure based on arrays I have preferred a vector of double linked lists. Reference:

http://web.cs.ualberta.ca/~joe/Coloring/index.html
New Methods to Color the Vertices of a Graph, Daniel Brelaz, CACM 22, 251–256, 1979.

The color of the vertex v will be stored in color[v]. i.e., vertex v belongs to coloring color[v]

It is like the sequential algorithm, except that the order in which vertices are chosen is determined dynamically based on the number of colors that cannot be used because of conflicts with previously colored vertices. Vertices with the fewest available colors are colored first. The degree of vertices is dynamically modified during the coloring (as in the Michael A. Trick's implementation) while the order of vertices is based on a heap data structure. This implementation corrects an error in the first loop: j start has to start from 0 not from 1. Reference:

http://mat.gsia.cmu.edu/COLOR/color.html
New Methods to Color the Vertices of a Graph, Daniel Brelaz, CACM 22, 251–256, 1979.
Olivier Coudert, "Exact Coloring of Real-Life Graphs is Easy". DAC 1997.

The color of the vertex v will be stored in color[v]. i.e., vertex v belongs to coloring color[v]