#include <SDPColoringCsdp.h>

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

Classes
class	FMGainCalcType

Public Types

typedef Coloring< GraphType >	base_type

typedef base_type::EdgeHashType	edge_hash_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
	SDPColoringCsdp (graph_type const &g)

virtual	~SDPColoringCsdp ()
	destructor

void	write_sdp_sol (std::string const &filename, struct blockmatrix const &X) const

void	print_blockrec (const char *label, blockrec const &block) 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 ()

void	construct_objectve_blockrec (blockmatrix &C, int32_t blocknum, int32_t blocksize, blockcat blockcategory) const

struct sparseblock *	construct_constraint_sparseblock (int32_t blocknum, int32_t blocksize, int32_t constraintnum, int32_t entrynum) const

void	set_sparseblock_entry (struct sparseblock &block, int32_t entryid, int32_t i, int32_t j, double value) const

void	round_sol (struct blockmatrix const &X)

void	coloring_merged_graph (graph_type const &mg, std::vector< int8_t > &vMColor) const

void	coloring_algos (graph_type const &g, std::vector< int8_t > &vColor) const

virtual void	coloring_by_backtrack (graph_type const &mg, std::vector< int8_t > &vColor) const

virtual void	coloring_by_FM (graph_type const &mg, std::vector< int8_t > &vColor) const

Protected Attributes
double	m_rounding_lb
	if SDP solution x < m_rounding_lb, take x as -0.5

double	m_rounding_ub
	if SDP solution x > m_rounding_ub, take x as 1.0

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

Static Protected Attributes
static const uint32_t	max_backtrack_num_vertices = 7
	maximum number of graph size that limbo::algorithms::coloring::BacktrackColoring can handle

Detailed Description

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

Thread control is not available as Csdp does not provide any API for that.
SDP formulation from Bei Yu's TCAD 2015 paper [6]

\begin{eqnarray*} & min. & C X, \\ & s.t. & x_{ii} = 1, \forall i \in V, \\ & & x_{ij} \ge -0.5, \forall (i, j) \in E, \\ & & X \succeq 0, \textrm{(PSD)}. \end{eqnarray*}

Note that Csdp only solves equality problem for constraints, so it is necessary to introduce slack variables for each conflict edge. The total number of variables are N = (vertex number + conflict edge number). The variable matrix has dimension NxN.

Based on the solution of X, we group vertices and construct merged graph. Then we color the merged graph.

Edge weight is used to differentiate conflict edge and stitch edge. Non-negative weight implies conflict edge. Negative weight implies stitch edge.

Template Parameters

GraphType graph_type

Definition at line 64 of file SDPColoringCsdp.h.

Constructor & Destructor Documentation

template<typename GraphType>

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

constructor

Parameters

g graph

Definition at line 186 of file SDPColoringCsdp.h.

Member Function Documentation

template<typename GraphType >

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

protectedvirtual

kernel coloring algorithm

Returns: objective value

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

Definition at line 194 of file SDPColoringCsdp.h.

template<typename GraphType >

void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::coloring_algos	(	graph_type const &	g,
		std::vector< int8_t > &	vColor
	)		const

protected

use different algorithms to color merged graph

Parameters

g	graph
vColor	coloring solutions

Definition at line 556 of file SDPColoringCsdp.h.

template<typename GraphType>

void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::coloring_by_backtrack	(	graph_type const &	mg,
		std::vector< int8_t > &	vColor
	)		const

protectedvirtual

use limbo::algorithms::coloring::BacktrackColoring to color merged graph

Parameters

mg	graph
vColor	coloring solutions

Definition at line 565 of file SDPColoringCsdp.h.

template<typename GraphType>

void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::coloring_by_FM	(	graph_type const &	mg,
		std::vector< int8_t > &	vColor
	)		const

protectedvirtual

use limbo::algorithms::partition::FMMultiWay to color merged graph

Parameters

mg	graph
vColor	coloring solutions

Definition at line 578 of file SDPColoringCsdp.h.

template<typename GraphType >

void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::coloring_merged_graph	(	graph_type const &	mg,
		std::vector< int8_t > &	vMColor
	)		const

protected

coloring merged graph

Parameters

mg	graph
vMColor	coloring solutions

Definition at line 508 of file SDPColoringCsdp.h.

template<typename GraphType >

struct sparseblock * limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::construct_constraint_sparseblock	(	int32_t	blocknum,
		int32_t	blocksize,
		int32_t	constraintnum,
		int32_t	entrynum
	)		const

protected

construct sparseblock for constraint

Parameters

blocknum	block number
blocksize	size of block
constraintnum	constraint number
entrynum	number of entries

Definition at line 400 of file SDPColoringCsdp.h.

template<typename GraphType >

void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::construct_objectve_blockrec	(	blockmatrix &	C,
		int32_t	blocknum,
		int32_t	blocksize,
		blockcat	blockcategory
	)		const

protected

helper functions construct blockrec in C for objective

Parameters

C	objective matrix C
blocknum	block number
blocksize	size of block
blockcategory	which type of compact representation, MATRIX or DIAG

Definition at line 378 of file SDPColoringCsdp.h.

template<typename GraphType >

void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::print_blockrec	(	const char *	label,
		blockrec const &	block
	)		const

print data in blockrec

Parameters

label	to mark what block is used for
block	compact representation of a matrix

Definition at line 643 of file SDPColoringCsdp.h.

template<typename GraphType >

void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::round_sol ( struct blockmatrix const & X )

protected

Round sdp solution. Based on the solution of X, we group vertices and construct merged graph. Then we color the merged graph.

Parameters

X	variable matrix X

Definition at line 429 of file SDPColoringCsdp.h.

template<typename GraphType >

void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::set_sparseblock_entry	(	struct sparseblock &	block,
		int32_t	entryid,
		int32_t	i,
		int32_t	j,
		double	value
	)		const

protected

set entry for sparseblock

Parameters

block	target block
entryid	entry id
i,j	indices
value	data value

Definition at line 421 of file SDPColoringCsdp.h.

template<typename GraphType >

void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::write_sdp_sol	(	std::string const &	filename,
		struct blockmatrix const &	X
	)		const

for debug write sdp solution to file

Parameters

filename	file name
X	variable matrix X

Definition at line 588 of file SDPColoringCsdp.h.

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

/Users/yibolin/Documents/Projects/Limbo/limbo/algorithms/coloring/SDPColoringCsdp.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

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