dsatur_coloring.hpp File Reference

Boost-based implementation of a heuristic sequential coloring algorithm based on the work of Daniel Brelaz (Version 1). More...

#include <boost/config.hpp>
#include <boost/graph/properties.hpp>
#include <boost/version.hpp>
#include <boost/property_map.hpp>
#include "custom_set.hpp"
#include <algorithm>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/limits.hpp>
#include <boost/tuple/tuple.hpp>
#include <vector>

Include dependency graph for dsatur_coloring.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	boost::dsatur_degree_compare_functor< size_type, VertexListGraph >
struct	boost::dsatur_degree_predicate_functor< size_type, VertexListGraph >
struct	boost::dsatur_d_list< size_type >
class	boost::dsatur_coloring_helper< VertexListGraph, ColorMap, size_type >

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

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

Detailed Description

Boost-based implementation of a heuristic sequential coloring algorithm based on the work of Daniel Brelaz (Version 1).

Some ideas come from the Joseph Culberson's implementation of DSATUR heuristic of Daniel Brelaz. For more details see

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

Author

Fabrizio Ferrandi fabri.nosp@m.zio..nosp@m.ferra.nosp@m.ndi@.nosp@m.polim.nosp@m.i.it $Revision$ $Date$ Last modified by $Author$

Definition in file dsatur_coloring.hpp.