limbo::algorithms::coloring::BacktrackColoring< GraphType > Class Template Reference

#include <BacktrackColoring.h>

Inheritance diagram for limbo::algorithms::coloring::BacktrackColoring< GraphType >:

Public Types
typedef Coloring< GraphType >	base_type
typedef boost::graph_traits < graph_type > ::adjacency_iterator	adjacency_iterator_type
typedef GraphType	graph_type
typedef boost::graph_traits < graph_type > ::vertex_descriptor	graph_vertex_type
typedef boost::graph_traits < graph_type > ::edge_descriptor	graph_edge_type
typedef boost::graph_traits < graph_type > ::vertex_iterator	vertex_iterator_type
typedef boost::graph_traits < graph_type >::edge_iterator	edge_iterator_type
typedef boost::property_traits < typename boost::property_map < graph_type, boost::edge_weight_t > ::const_type >::value_type	edge_weight_type
enum	ColorNumType
	number of colors
Public Types inherited from limbo::algorithms::coloring::Coloring< GraphType >
enum	ColorNumType { THREE = 3, FOUR = 4 }
	number of colors
typedef GraphType	graph_type
typedef boost::graph_traits < graph_type > ::vertex_descriptor	graph_vertex_type
typedef boost::graph_traits < graph_type > ::edge_descriptor	graph_edge_type
typedef boost::graph_traits < graph_type > ::vertex_iterator	vertex_iterator_type
typedef boost::graph_traits < graph_type >::edge_iterator	edge_iterator_type
typedef boost::property_traits < typename boost::property_map < graph_type, boost::edge_weight_t > ::const_type >::value_type	edge_weight_type
typedef boost::property_traits < typename boost::property_map < graph_type, boost::edge_index_t > ::const_type >::value_type	edge_index_type

Public Member Functions
	BacktrackColoring (graph_type const &g)
virtual	~BacktrackColoring ()
	destructor
Public Member Functions inherited from limbo::algorithms::coloring::Coloring< GraphType >
	Coloring (graph_type const &g)
virtual	~Coloring ()
	destructor
virtual double	operator() ()
virtual void	color_num (ColorNumType cn)
virtual void	color_num (int8_t cn)
virtual ColorNumType	color_num () const
virtual void	precolor (graph_vertex_type v, int8_t c)
virtual bool	has_precolored () const
virtual double	stitch_weight () const
virtual void	stitch_weight (double w)
virtual void	threads (int32_t t)
virtual int8_t	color (graph_vertex_type v) const
virtual edge_weight_type	edge_weight (graph_edge_type const &e) const
virtual edge_weight_type	calc_cost (std::vector< int8_t > const &vColor) const
void	check_edge_weight (graph_type const &g, edge_weight_type lb, edge_weight_type ub) const
void	print_edge_weight (graph_type const &g) const
virtual void	write_graph (std::string const &filename) const
virtual void	write_graph (std::string const &filename, graph_type const &g, std::vector< int8_t > const &vColor) const

Protected Member Functions
virtual double	coloring ()
double	init_coloring (vector< int8_t > &vColor) const
void	coloring_kernel (vector< int8_t > &vBestColor, vector< int8_t > &vColor, double &best_cost, double &cur_cost, graph_vertex_type v, double cost_lb, double cost_ub) const

Additional Inherited Members
Protected Attributes inherited from limbo::algorithms::coloring::Coloring< GraphType >
graph_type const &	m_graph
	initial graph
std::vector< int8_t >	m_vColor
	coloring solutions
ColorNumType	m_color_num
	number of colors
double	m_stitch_weight
	stitch weight
int32_t	m_threads
	control number of threads for ILP solver
bool	m_has_precolored
	whether contain precolored vertices

Detailed Description

template<typename GraphType>
class limbo::algorithms::coloring::BacktrackColoring< GraphType >

Solve graph coloring with backtracking

Template Parameters

GraphType

graph type

Definition at line 28 of file BacktrackColoring.h.

Constructor & Destructor Documentation

template<typename GraphType>

limbo::algorithms::coloring::BacktrackColoring< GraphType >::BacktrackColoring ( graph_type const &  g )

inline

constructor

Parameters

g

graph

Definition at line 45 of file BacktrackColoring.h.

Member Function Documentation

template<typename GraphType >

double limbo::algorithms::coloring::BacktrackColoring< GraphType >::coloring ( )

protectedvirtual

Returns

objective value

Implements limbo::algorithms::coloring::Coloring< GraphType >.

Definition at line 69 of file BacktrackColoring.h.

template<typename GraphType>

void limbo::algorithms::coloring::BacktrackColoring< GraphType >::coloring_kernel ( vector< int8_t > &  vBestColor, vector< int8_t > &  vColor, double &  best_cost, double &  cur_cost, graph_vertex_type  v, double  cost_lb, double  cost_ub  ) const

protected

kernel function for recursive backtracking

Parameters

vBestColor	best coloring solution assignment
vColor	current coloring solution assignment
best_cost	best cost
cur_cost	current cost
v	current vertex
cost_lb	cost lower bound
cost_ub	cost upper bound

Definition at line 140 of file BacktrackColoring.h.

template<typename GraphType >

double limbo::algorithms::coloring::BacktrackColoring< GraphType >::init_coloring ( vector< int8_t > &  vColor ) const

protected

initial color assignment by greedy approach

Parameters

vColor

array to store coloring solution

Returns

cost

Definition at line 117 of file BacktrackColoring.h.

---

The documentation for this class was generated from the following file:

• /Users/yibolin/Documents/Projects/Limbo/limbo/algorithms/coloring/BacktrackColoring.h