#include <LPColoring.h>

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

Classes
struct	NonIntegerInfo
	records the information of non-integer values More...
struct	ConstrVariableInfo
	information for a variable of a constraint More...

Public Types

typedef Coloring< GraphType >	base_type
typedef base_type::graph_type	graph_type
typedef base_type::graph_vertex_type	graph_vertex_type
typedef base_type::graph_edge_type	graph_edge_type
typedef base_type::vertex_iterator_type	vertex_iterator_type
typedef base_type::edge_iterator_type	edge_iterator_type
typedef base_type::edge_weight_type	edge_weight_type
typedef base_type::EdgeHashType	edge_hash_type
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
	LPColoring (graph_type const &g)
	constructor
	~LPColoring ()
	destructor
uint32_t	lp_iters () const
void	print_solution (vector< GRBVar > const &vColorBits) 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
double	coloring ()
void	apply_solution (vector< GRBVar > const &vColorBits)
void	initialize ()
	create the NoStitchGraph (this->m_graph) from the (m_conflict_graph)
void	set_optimize_model (vector< GRBVar > &vColorBits, vector< GRBVar > &vEdgeBits, GRBLinExpr &obj, GRBModel &optModel)
void	set_anchor (vector< GRBVar > &vColorBits) const
void	adjust_variable_pair_in_objective (vector< GRBVar > const &vColorBits, GRBLinExpr &obj) const
	tune objective for each color bit pair of vertex
void	adjust_conflict_edge_vertices_in_objective (vector< GRBVar > const &vColorBits, GRBLinExpr &obj) const
	tune objective for each color bit pair along conflict edges
void	add_odd_cycle_constraints (vector< GRBVar > const &vColorBits, GRBModel &optModel)
	odd cycle trick from Prof. Baldick
void	solve_model (GRBModel &optModel)
	solve model
void	get_odd_cycles (graph_vertex_type const &v, vector< vector< graph_vertex_type > > &vOddCyle)
graph_vertex_type	max_degree_vertex () const
void	rounding_with_binding_analysis (GRBModel &optModel, vector< GRBVar > &vColorBits, vector< GRBVar > &vEdgeBits)
uint32_t	post_refinement ()
	greedy final coloring refinement
bool	refine_color (graph_edge_type const &e)
void	non_integer_num (vector< GRBVar > const &vColorBits, vector< GRBVar > const &vEdgeBits, NonIntegerInfo &info) const
void	non_integer_num (vector< GRBVar > const &vVariables, uint32_t &nonIntegerNum, uint32_t &halfIntegerNum) const
bool	is_integer (double value) const
uint32_t	check_precolored_num (vector< LPColoring< GraphType >::graph_vertex_type > const &vVertex) const

Protected Attributes
boost::dynamic_bitset	m_vVertexHandledByOddCycle
	members
uint32_t	m_constrs_num
	record number of constraints
uint32_t	m_lp_iters
	record lp iterations
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::LPColoring< GraphType >

LP based graph coloring.

Template Parameters

GraphType graph type

Definition at line 67 of file LPColoring.h.

Member Typedef Documentation

◆ base_type

template<typename GraphType>

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

Definition at line 71 of file LPColoring.h.

◆ edge_hash_type

template<typename GraphType>

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

Definition at line 78 of file LPColoring.h.

◆ edge_iterator_type

template<typename GraphType>

typedef base_type::edge_iterator_type limbo::algorithms::coloring::LPColoring< GraphType >::edge_iterator_type

Definition at line 76 of file LPColoring.h.

◆ edge_weight_type

template<typename GraphType>

typedef base_type::edge_weight_type limbo::algorithms::coloring::LPColoring< GraphType >::edge_weight_type

Definition at line 77 of file LPColoring.h.

◆ graph_edge_type

template<typename GraphType>

typedef base_type::graph_edge_type limbo::algorithms::coloring::LPColoring< GraphType >::graph_edge_type

Definition at line 74 of file LPColoring.h.

◆ graph_type

template<typename GraphType>

typedef base_type::graph_type limbo::algorithms::coloring::LPColoring< GraphType >::graph_type

Definition at line 72 of file LPColoring.h.

◆ graph_vertex_type

template<typename GraphType>

typedef base_type::graph_vertex_type limbo::algorithms::coloring::LPColoring< GraphType >::graph_vertex_type

Definition at line 73 of file LPColoring.h.

◆ vertex_iterator_type

template<typename GraphType>

typedef base_type::vertex_iterator_type limbo::algorithms::coloring::LPColoring< GraphType >::vertex_iterator_type

Definition at line 75 of file LPColoring.h.

Constructor & Destructor Documentation

◆ LPColoring()

template<typename GraphType>

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

constructor

Parameters

g graph

Definition at line 229 of file LPColoring.h.

◆ ~LPColoring()

template<typename GraphType>

limbo::algorithms::coloring::LPColoring< GraphType >::~LPColoring ( )

inline

destructor

Definition at line 135 of file LPColoring.h.

Member Function Documentation

◆ add_odd_cycle_constraints()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::add_odd_cycle_constraints	(	vector< GRBVar > const &	vColorBits,
		GRBModel &	optModel )

protected

odd cycle trick from Prof. Baldick

odd cycle constraints from Prof. Baldick

Parameters

vColorBits	vertex bits of LP
optModel	LP model

Definition at line 511 of file LPColoring.h.

◆ adjust_conflict_edge_vertices_in_objective()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::adjust_conflict_edge_vertices_in_objective	(	vector< GRBVar > const &	vColorBits,
		GRBLinExpr &	obj ) const

protected

tune objective for each color bit pair along conflict edges

for each color bit pair of vertices of an edge

Parameters

vColorBits	vertex bits of LP
obj	objective of LP

Definition at line 484 of file LPColoring.h.

◆ adjust_variable_pair_in_objective()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::adjust_variable_pair_in_objective	(	vector< GRBVar > const &	vColorBits,
		GRBLinExpr &	obj ) const

protected

tune objective for each color bit pair of vertex

for each color bit pair of a vertex

Parameters

vColorBits	vertex bits of LP
obj	objective of LP

Definition at line 466 of file LPColoring.h.

◆ apply_solution()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::apply_solution ( vector< GRBVar > const & vColorBits )

protected

apply coloring solution

Parameters

vColorBits LP solutions

Definition at line 675 of file LPColoring.h.

◆ check_precolored_num()

template<typename GraphType>

uint32_t limbo::algorithms::coloring::LPColoring< GraphType >::check_precolored_num ( vector< LPColoring< GraphType >::graph_vertex_type > const & vVertex ) const

protected

check number of precolored vertices

Parameters

vVertex vertices of the graph

Returns: number of precolored vertices

Definition at line 911 of file LPColoring.h.

◆ coloring()

template<typename GraphType>

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

protectedvirtual

kernel coloring algorithm; relaxed linear programming based coloring for the conflict graph (this->m_graph)

Returns: objective value

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

Definition at line 579 of file LPColoring.h.

◆ get_odd_cycles()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::get_odd_cycles	(	graph_vertex_type const &	v,
		vector< vector< graph_vertex_type > > &	vOddCyle )

protected

DFS to search for the odd cycles, stored in m_odd_cycles

Parameters

v	vertex
vOddCyle	container to store odd cycles

Definition at line 239 of file LPColoring.h.

◆ is_integer()

template<typename GraphType>

bool limbo::algorithms::coloring::LPColoring< GraphType >::is_integer ( double value ) const

inlineprotected

check if a variable is integer or not

Parameters

value target value to be checked

Returns: true if value is an integer

Definition at line 214 of file LPColoring.h.

◆ lp_iters()

template<typename GraphType>

uint32_t limbo::algorithms::coloring::LPColoring< GraphType >::lp_iters ( ) const

inline

Returns: number of LP iterations

Definition at line 138 of file LPColoring.h.

◆ max_degree_vertex()

template<typename GraphType>

LPColoring< GraphType >::graph_vertex_type limbo::algorithms::coloring::LPColoring< GraphType >::max_degree_vertex ( ) const

protected

Returns: the vertex with the largest degree

Definition at line 332 of file LPColoring.h.

◆ non_integer_num() [1/2]

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::non_integer_num	(	vector< GRBVar > const &	vColorBits,
		vector< GRBVar > const &	vEdgeBits,
		NonIntegerInfo &	info ) const

protected

compute number of non-integers and half-integers for both vertex variables and edge variables

Parameters

vColorBits	vertex bits of LP
vEdgeBits	edge bits of LP
info	non-integer information

◆ non_integer_num() [2/2]

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::non_integer_num	(	vector< GRBVar > const &	vVariables,
		uint32_t &	nonIntegerNum,
		uint32_t &	halfIntegerNum ) const

protected

compute number of non-integers and half-integers with given variable array

Parameters

vVariables	variables
nonIntegerNum	number of non-integers
halfIntegerNum	number of half-integers

◆ post_refinement()

template<typename GraphType>

uint32_t limbo::algorithms::coloring::LPColoring< GraphType >::post_refinement ( )

protected

greedy final coloring refinement

Definition at line 798 of file LPColoring.h.

◆ print_solution()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::print_solution ( vector< GRBVar > const & vColorBits ) const

print solution

Parameters

vColorBits LP solutions

Definition at line 921 of file LPColoring.h.

◆ refine_color()

template<typename GraphType>

bool limbo::algorithms::coloring::LPColoring< GraphType >::refine_color ( graph_edge_type const & e )

protected

refine coloring solution of an edge

Parameters

e edge

Returns: true if found a coloring solution to resolve conflicts

Definition at line 819 of file LPColoring.h.

◆ rounding_with_binding_analysis()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::rounding_with_binding_analysis	(	GRBModel &	optModel,
		vector< GRBVar > &	vColorBits,
		vector< GRBVar > &	vEdgeBits )

protected

Optimal rounding based on binding constraints

Parameters

optModel	LP model
vColorBits	vertex bits of LP
vEdgeBits	edge bits of LP

optimal rounding based on the binding analysis but only a part of all vertices can be rounded

Definition at line 691 of file LPColoring.h.

◆ set_anchor()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::set_anchor ( vector< GRBVar > & vColorBits ) const

protected

set anchor vertex

Parameters

vColorBits vertex bits of LP

Definition at line 451 of file LPColoring.h.

◆ set_optimize_model()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::set_optimize_model	(	vector< GRBVar > &	vColorBits,
		vector< GRBVar > &	vEdgeBits,
		GRBLinExpr &	obj,
		GRBModel &	optModel )

protected

create basic variables, objective and constraints

Parameters

vColorBits	vertex bits of LP
vEdgeBits	edge bits of LP
obj	objective of LP
optModel	LP model

Definition at line 350 of file LPColoring.h.

◆ solve_model()

template<typename GraphType>

void limbo::algorithms::coloring::LPColoring< GraphType >::solve_model ( GRBModel & optModel )

protected

solve model

Parameters

optModel LP model

Definition at line 552 of file LPColoring.h.

Member Data Documentation

◆ m_constrs_num

template<typename GraphType>

uint32_t limbo::algorithms::coloring::LPColoring< GraphType >::m_constrs_num

protected

record number of constraints

Definition at line 223 of file LPColoring.h.

◆ m_lp_iters

template<typename GraphType>

uint32_t limbo::algorithms::coloring::LPColoring< GraphType >::m_lp_iters

protected

record lp iterations

Definition at line 224 of file LPColoring.h.

◆ m_vVertexHandledByOddCycle

template<typename GraphType>

boost::dynamic_bitset limbo::algorithms::coloring::LPColoring< GraphType >::m_vVertexHandledByOddCycle

protected

members

record whether a vertex has already been handled by an odd cycle

Definition at line 222 of file LPColoring.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/LPColoring.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ base_type

◆ edge_hash_type

◆ edge_iterator_type

◆ edge_weight_type

◆ graph_edge_type

◆ graph_type

◆ graph_vertex_type

◆ vertex_iterator_type

Constructor & Destructor Documentation

◆ LPColoring()

◆ ~LPColoring()

Member Function Documentation

◆ add_odd_cycle_constraints()

◆ adjust_conflict_edge_vertices_in_objective()

◆ adjust_variable_pair_in_objective()

◆ apply_solution()

◆ check_precolored_num()

◆ coloring()

◆ get_odd_cycles()

◆ is_integer()

◆ lp_iters()

◆ max_degree_vertex()

◆ non_integer_num() [1/2]

◆ non_integer_num() [2/2]

◆ post_refinement()

◆ print_solution()

◆ refine_color()

◆ rounding_with_binding_analysis()

◆ set_anchor()

◆ set_optimize_model()

◆ solve_model()

Member Data Documentation

◆ m_constrs_num

◆ m_lp_iters

◆ m_vVertexHandledByOddCycle