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

#include <ILPColoring.h>

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

Public Types
typedef Coloring< GraphType >	base_type
typedef base_type::EdgeHashType	edge_hash_type
typedef limbo::solvers::LinearModel < float, int32_t >	model_type
typedef limbo::solvers::GurobiLinearApi < model_type::coefficient_value_type, model_type::variable_value_type >	solver_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
	ILPColoring (graph_type const &g)
virtual	~ILPColoring ()
	destructor
void	write_graph_sol (string const &filename, model_type const &opt_model, std::vector< model_type::variable_type > const &vVertexBit) const
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 ()

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::ILPColoring< GraphType >

ILP based graph coloring. Edge weight is used to differentiate conflict edge and stitch edge. Non-negative weight implies conflict edge, while negative weight implies stitch edge.

Template Parameters

GraphType

graph type

Definition at line 54 of file ILPColoring.h.

Constructor & Destructor Documentation

template<typename GraphType>

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

inline

constructor

Parameters

g

graph

Definition at line 73 of file ILPColoring.h.

Member Function Documentation

template<typename GraphType >

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

protectedvirtual

kernel coloring algorithm

Returns

objective value

ILP model

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

Definition at line 92 of file ILPColoring.h.

template<typename GraphType>

void limbo::algorithms::coloring::ILPColoring< GraphType >::write_graph_sol	(	string const &	filename,
		model_type const &	opt_model,
		std::vector< model_type::variable_type > const &	vVertexBit
	)		const

write raw solution of ILP

Parameters

filename	output file name
opt_model	problem model
vVertexBit	array of vertex bits that indicate coloring solutions; each vertex corresponds to two bits

Definition at line 276 of file ILPColoring.h.

---

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

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