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< typenameboost::property_map< graph_type, boost::edge_weight_t >::const_type >::value_type	edge_weight_type
enum	ColorNumType
	number of colors More...
Public Types inherited from limbo::algorithms::coloring::Coloring< GraphType >
enum	ColorNumType { TWO = 2 , THREE = 3 , FOUR = 4 }
	number of colors More...
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::graph_traits< graph_type >::adjacency_iterator	adjacency_iterator
typedef boost::property_traits< typenameboost::property_map< graph_type, boost::edge_weight_t >::const_type >::value_type	edge_weight_type
typedef boost::property_traits< typenameboost::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
void	depth_first_search_stitch (graph_vertex_type v, std::vector< int32_t > &stitch_relation_set, std::vector< bool > &visited, uint32_t &stitch_edge_num, int32_t stitch_index)
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
int32_t	m_stitch_index
int32_t	m_big_edge_num
std::vector< int32_t >	m_stitch_relation_set
std::vector< int32_t >	m_edge_index_vector

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.

Member Typedef Documentation

base_type

template<typename GraphType>

typedef Coloring<GraphType> limbo::algorithms::coloring::ILPColoring< GraphType >::base_type

Definition at line 58 of file ILPColoring.h.

edge_hash_type

template<typename GraphType>

typedef base_type::EdgeHashType limbo::algorithms::coloring::ILPColoring< GraphType >::edge_hash_type

Definition at line 66 of file ILPColoring.h.

edge_iterator_type

template<typename GraphType>

typedef boost::graph_traits<graph_type>::edge_iterator limbo::algorithms::coloring::Coloring< GraphType >::edge_iterator_type

Definition at line 122 of file Coloring.h.

edge_weight_type

template<typename GraphType>

typedef boost::property_traits<typenameboost::property_map<graph_type,boost::edge_weight_t>::const_type>::value_type limbo::algorithms::coloring::Coloring< GraphType >::edge_weight_type

Definition at line 125 of file Coloring.h.

graph_edge_type

template<typename GraphType>

typedef boost::graph_traits<graph_type>::edge_descriptor limbo::algorithms::coloring::Coloring< GraphType >::graph_edge_type

Definition at line 120 of file Coloring.h.

graph_type

template<typename GraphType>

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

Definition at line 118 of file Coloring.h.

graph_vertex_type

template<typename GraphType>

typedef boost::graph_traits<graph_type>::vertex_descriptor limbo::algorithms::coloring::Coloring< GraphType >::graph_vertex_type

Definition at line 119 of file Coloring.h.

model_type

template<typename GraphType>

typedef limbo::solvers::LinearModel<float, int32_t> limbo::algorithms::coloring::ILPColoring< GraphType >::model_type

Definition at line 67 of file ILPColoring.h.

solver_type

template<typename GraphType>

typedef limbo::solvers::GurobiLinearApi<model_type::coefficient_value_type, model_type::variable_value_type> limbo::algorithms::coloring::ILPColoring< GraphType >::solver_type

Definition at line 68 of file ILPColoring.h.

vertex_iterator_type

template<typename GraphType>

typedef boost::graph_traits<graph_type>::vertex_iterator limbo::algorithms::coloring::Coloring< GraphType >::vertex_iterator_type

Definition at line 121 of file Coloring.h.

Member Enumeration Documentation

ColorNumType

template<typename GraphType>

enum limbo::algorithms::coloring::Coloring::ColorNumType

number of colors

Definition at line 134 of file Coloring.h.

Constructor & Destructor Documentation

ILPColoring()

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.

~ILPColoring()

template<typename GraphType>

virtual limbo::algorithms::coloring::ILPColoring< GraphType >::~ILPColoring ( )

inlinevirtual

destructor

Definition at line 77 of file ILPColoring.h.

Member Function Documentation

coloring()

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.

write_graph_sol()

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:

• /home/abuild/rpmbuild/BUILD/limbo-3.5.4-build/limbo-3.5.4/limbo/algorithms/coloring/ILPColoring.h