Limbo
|
#include <SDPColoringCsdp.h>
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 | |
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.
GraphType | graph_type |
Definition at line 64 of file SDPColoringCsdp.h.
limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::SDPColoringCsdp | ( | graph_type const & | g | ) |
|
protectedvirtual |
kernel coloring algorithm
Implements limbo::algorithms::coloring::Coloring< GraphType >.
Definition at line 194 of file SDPColoringCsdp.h.
|
protected |
use different algorithms to color merged graph
g | graph |
vColor | coloring solutions |
Definition at line 556 of file SDPColoringCsdp.h.
|
protectedvirtual |
use limbo::algorithms::coloring::BacktrackColoring to color merged graph
mg | graph |
vColor | coloring solutions |
Definition at line 565 of file SDPColoringCsdp.h.
|
protectedvirtual |
use limbo::algorithms::partition::FMMultiWay to color merged graph
mg | graph |
vColor | coloring solutions |
Definition at line 578 of file SDPColoringCsdp.h.
|
protected |
coloring merged graph
mg | graph |
vMColor | coloring solutions |
Definition at line 508 of file SDPColoringCsdp.h.
|
protected |
construct sparseblock for constraint
blocknum | block number |
blocksize | size of block |
constraintnum | constraint number |
entrynum | number of entries |
Definition at line 400 of file SDPColoringCsdp.h.
|
protected |
helper functions construct blockrec in C for objective
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.
void limbo::algorithms::coloring::SDPColoringCsdp< GraphType >::print_blockrec | ( | const char * | label, |
blockrec const & | block | ||
) | const |
print data in blockrec
label | to mark what block is used for |
block | compact representation of a matrix |
Definition at line 643 of file SDPColoringCsdp.h.
|
protected |
Round sdp solution. Based on the solution of X, we group vertices and construct merged graph. Then we color the merged graph.
X | variable matrix X |
Definition at line 429 of file SDPColoringCsdp.h.
|
protected |
set entry for sparseblock
block | target block |
entryid | entry id |
i,j | indices |
value | data value |
Definition at line 421 of file SDPColoringCsdp.h.
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
filename | file name |
X | variable matrix X |
Definition at line 588 of file SDPColoringCsdp.h.