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

#include <Coloring.h>

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

Classes
struct	EdgeHashType
	hasher class for graph_edge_type More...

Public Types
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
	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 ()=0

Protected Attributes
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::Coloring< GraphType >

Base class for all coloring algorithms. All coloring algorithms support 3 and 4 colors.

Template Parameters

GraphType

graph type

Definition at line 114 of file Coloring.h.

Constructor & Destructor Documentation

template<typename GraphType>

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

(

graph_type const &

g

)

constructor

Parameters

g

graph

Definition at line 239 of file Coloring.h.

Member Function Documentation

template<typename GraphType >

Coloring< GraphType >::edge_weight_type limbo::algorithms::coloring::Coloring< GraphType >::calc_cost ( std::vector< int8_t > const &  vColor ) const

virtual

compute cost of coloring solutions

Parameters

vColor

coloring solutions

Returns

cost with a coloring solution

Definition at line 279 of file Coloring.h.

template<typename GraphType>

void limbo::algorithms::coloring::Coloring< GraphType >::check_edge_weight	(	graph_type const &	g,
		edge_weight_type	lb,
		edge_weight_type	ub
	)		const

check edge weight within lb and ub

Parameters

g	graph
lb	lower bound
ub	upper bound

Definition at line 300 of file Coloring.h.

template<typename GraphType>

virtual int8_t limbo::algorithms::coloring::Coloring< GraphType >::color ( graph_vertex_type  v ) const

inlinevirtual

retrieve coloring solution

Parameters

v

vertex

Returns

coloring solution

Definition at line 193 of file Coloring.h.

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::color_num ( ColorNumType  cn )

inlinevirtual

set number of colors

Parameters

cn	number of colors

Definition at line 165 of file Coloring.h.

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::color_num ( int8_t  cn )

inlinevirtual

set number of colors

Parameters

cn	number of colors

Definition at line 168 of file Coloring.h.

template<typename GraphType>

virtual ColorNumType limbo::algorithms::coloring::Coloring< GraphType >::color_num ( ) const

inlinevirtual

Returns

number of colors

Definition at line 170 of file Coloring.h.

template<typename GraphType>

virtual double limbo::algorithms::coloring::Coloring< GraphType >::coloring ( )

protectedpure virtual

Returns

objective value

Implemented in limbo::algorithms::coloring::LPColoring< GraphType >, limbo::algorithms::coloring::MISColoring< GraphType >, limbo::algorithms::coloring::SDPColoringCsdp< GraphType >, limbo::algorithms::coloring::ILPColoringLemonCbc< GraphType >, limbo::algorithms::coloring::ILPColoring< GraphType >, and limbo::algorithms::coloring::BacktrackColoring< GraphType >.

template<typename GraphType>

virtual edge_weight_type limbo::algorithms::coloring::Coloring< GraphType >::edge_weight ( graph_edge_type const &  e ) const

inlinevirtual

get edge weight

Parameters

e

edge

Returns

edge weight

Definition at line 199 of file Coloring.h.

template<typename GraphType>

virtual bool limbo::algorithms::coloring::Coloring< GraphType >::has_precolored ( ) const

inlinevirtual

Returns

true if contain precolored vertices

Definition at line 178 of file Coloring.h.

template<typename GraphType >

double limbo::algorithms::coloring::Coloring< GraphType >::operator() ( )

virtual

top API

Returns

objective value

Definition at line 249 of file Coloring.h.

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::precolor ( graph_vertex_type  v, int8_t  c  )

inlinevirtual

set precolored vertex

Parameters

v	vertex
c	color

Reimplemented in limbo::algorithms::coloring::MISColoring< GraphType >.

Definition at line 175 of file Coloring.h.

template<typename GraphType>

void limbo::algorithms::coloring::Coloring< GraphType >::print_edge_weight

(

graph_type const &

g

)

const

print edge weight

Parameters

g

graph

Definition at line 311 of file Coloring.h.

template<typename GraphType>

virtual double limbo::algorithms::coloring::Coloring< GraphType >::stitch_weight ( ) const

inlinevirtual

Returns

stitch weight

Definition at line 181 of file Coloring.h.

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::stitch_weight ( double  w )

inlinevirtual

set weight of stitch

Parameters

w

weight

Definition at line 184 of file Coloring.h.

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::threads ( int32_t  t )

inlinevirtual

set number of threads

Parameters

t	number of threads

Definition at line 188 of file Coloring.h.

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::write_graph ( std::string const &  filename ) const

virtual

write graph in graphviz format

Parameters

filename

output file name

template<typename GraphType>

virtual void limbo::algorithms::coloring::Coloring< GraphType >::write_graph ( std::string const &  filename, graph_type const &  g, std::vector< int8_t > const &  vColor  ) const

virtual

write graph in graphviz format

Parameters

filename	output file name
g	graph
vColor	coloring solutions

---

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

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