maxclique_dsatur_coloring.hpp File Reference

Boost-based implementation of an exact sequential coloring algorithm based on the work of Olivier Coudert and Daniel Brelaz. More...

#include <boost/config.hpp>
#include <boost/graph/properties.hpp>
#include <boost/version.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/limits.hpp>
#include <algorithm>
#include <boost/numeric/ublas/matrix.hpp>
#include <cassert>
#include <vector>
#include "custom_set.hpp"
#include <boost/graph/filtered_graph.hpp>

Include dependency graph for maxclique_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::heap_compare_functor< size_type >
struct	boost::select_vertex< SET_container >
	Predicate functor object used to select the proper set of vertices. More...
class	boost::maxclique_dsatur_coloring_helper< VertexListGraph, ColorMap, size_type, SET_container >

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<class VertexListGraph , class ColorMap >
property_traits< ColorMap >::value_type	boost::unsorted_coloring (const VertexListGraph &G, ColorMap color)
template<typename VertexListGraph , typename ColorMap >
property_traits< ColorMap >::value_type	boost::maxclique_dsatur_coloring (const VertexListGraph &G, ColorMap color)

Detailed Description

Boost-based implementation of an exact sequential coloring algorithm based on the work of Olivier Coudert and Daniel Brelaz.

As a starting point it has been used the exact sequential vertex coloring implementation of Michael A. Trick. For more details see

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

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