#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< 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
	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
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 ()
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
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

Static Protected Attributes
static const uint32_t	max_backtrack_num_vertices = 6
	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 [TPL_TCAD2015_Yu]

f{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)}. \f} 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.

Member Typedef Documentation

◆ base_type

template<typename GraphType>

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

Definition at line 68 of file SDPColoringCsdp.h.

◆ edge_hash_type

template<typename GraphType>

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

Definition at line 76 of file SDPColoringCsdp.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.

◆ 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

◆ SDPColoringCsdp()

template<typename GraphType>

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

constructor

Parameters

g graph

Definition at line 189 of file SDPColoringCsdp.h.

◆ ~SDPColoringCsdp()

template<typename GraphType>

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

inlinevirtual

destructor

Definition at line 126 of file SDPColoringCsdp.h.

Member Function Documentation

◆ coloring()

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 197 of file SDPColoringCsdp.h.

◆ coloring_algos()

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 594 of file SDPColoringCsdp.h.

◆ coloring_by_backtrack()

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 619 of file SDPColoringCsdp.h.

◆ coloring_by_FM()

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 632 of file SDPColoringCsdp.h.

◆ coloring_merged_graph()

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 521 of file SDPColoringCsdp.h.

◆ construct_constraint_sparseblock()

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 412 of file SDPColoringCsdp.h.

◆ construct_objectve_blockrec()

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 390 of file SDPColoringCsdp.h.

◆ print_blockrec()

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 704 of file SDPColoringCsdp.h.

◆ round_sol()

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 441 of file SDPColoringCsdp.h.

◆ set_sparseblock_entry()

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 433 of file SDPColoringCsdp.h.

◆ write_sdp_sol()

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 649 of file SDPColoringCsdp.h.

Member Data Documentation

◆ m_rounding_lb

template<typename GraphType>

double limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::m_rounding_lb

protected

if SDP solution x < m_rounding_lb, take x as -0.5

Definition at line 183 of file SDPColoringCsdp.h.

◆ m_rounding_ub

template<typename GraphType>

double limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::m_rounding_ub

protected

if SDP solution x > m_rounding_ub, take x as 1.0

Definition at line 184 of file SDPColoringCsdp.h.

◆ max_backtrack_num_vertices

template<typename GraphType>

const uint32_t limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::max_backtrack_num_vertices = 6

staticprotected

maximum number of graph size that limbo::algorithms::coloring::BacktrackColoring can handle

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

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Static 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

Member Enumeration Documentation

◆ ColorNumType

Constructor & Destructor Documentation

◆ SDPColoringCsdp()

◆ ~SDPColoringCsdp()

Member Function Documentation

◆ coloring()

◆ coloring_algos()

◆ coloring_by_backtrack()

◆ coloring_by_FM()

◆ coloring_merged_graph()

◆ construct_constraint_sparseblock()

◆ construct_objectve_blockrec()

◆ print_blockrec()

◆ round_sol()

◆ set_sparseblock_entry()

◆ write_sdp_sol()

Member Data Documentation

◆ m_rounding_lb

◆ m_rounding_ub

◆ max_backtrack_num_vertices