15 #ifndef LIMBO_ALGORITHMS_COLORING_SDPCOLORINGCSDP
16 #define LIMBO_ALGORITHMS_COLORING_SDPCOLORINGCSDP
63 template <
typename GraphType>
69 using typename base_type::graph_type;
70 using typename base_type::graph_vertex_type;
71 using typename base_type::graph_edge_type;
72 using typename base_type::vertex_iterator_type;
73 using typename base_type::edge_iterator_type;
74 using typename base_type::edge_weight_type;
96 edge_weight_type
operator()(int32_t v, int8_t origp, int8_t newp, std::vector<int8_t>
const& vPartition)
const
98 typedef typename boost::graph_traits<graph_type>::out_edge_iterator out_edge_iterator_type;
99 out_edge_iterator_type ei, eie;
101 edge_weight_type gain = (origp >= 0)? 0 : boost::num_edges(graph)*boost::num_vertices(graph);
102 for (boost::tie(ei, eie) = boost::out_edges(v, graph); ei != eie; ++ei)
104 graph_vertex_type t = boost::target(*ei, graph);
105 int8_t pt = vPartition[t];
106 #ifdef DEBUG_SDPCOLORING
107 assert((int32_t)t != v);
110 if (pt < 0)
continue;
111 edge_weight_type w = boost::get(boost::edge_weight, graph, *ei);
113 gain += (pt == newp)? -w : (pt == origp)? w : 0;
129 void write_sdp_sol(std::string
const& filename,
struct blockmatrix
const& X)
const;
133 void print_blockrec(
const char* label, blockrec
const& block)
const;
157 void set_sparseblock_entry(
struct sparseblock& block, int32_t entryid, int32_t i, int32_t j,
double value)
const;
162 void round_sol(
struct blockmatrix
const& X);
170 void coloring_algos(graph_type
const& g, std::vector<int8_t>& vColor)
const;
178 virtual void coloring_by_FM(graph_type
const& mg, std::vector<int8_t>& vColor)
const;
185 template <
typename GraphType>
193 template <
typename GraphType>
206 assert_msg(!this->has_precolored(),
"SDP coloring does not support precolored layout yet");
208 struct blockmatrix C;
210 struct constraintmatrix *constraints;
212 struct blockmatrix X,Z;
217 vertex_iterator_type vi, vie;
218 edge_iterator_type ei, eie;
220 uint32_t num_vertices = boost::num_vertices(this->m_graph);
221 uint32_t num_edges = boost::num_edges(this->m_graph);
223 uint32_t num_conflict_edges = 0;
224 uint32_t num_stitch_edges = 0;
225 for (boost::tie(ei, eie) = boost::edges(this->m_graph); ei != eie; ++ei)
227 if (this->edge_weight(*ei) >= 0)
228 num_conflict_edges += 1;
230 num_stitch_edges += 1;
232 assert_msg(num_edges > 0 && num_conflict_edges > 0,
"no edges or conflict edges found, no need to solve SDP");
234 uint32_t num_variables = num_vertices+num_conflict_edges;
235 uint32_t num_constraints = num_conflict_edges+num_vertices;
239 C.blocks = (
struct blockrec *)malloc((C.nblocks+1)*
sizeof(
struct blockrec));
240 assert_msg(C.blocks,
"Couldn't allocate storage for C");
243 construct_objectve_blockrec(C, 1, num_vertices, MATRIX);
244 for (boost::tie(ei, eie) = boost::edges(this->m_graph); ei != eie; ++ei)
246 graph_vertex_type s = boost::source(*ei, this->m_graph);
247 graph_vertex_type t = boost::target(*ei, this->m_graph);
251 edge_weight_type alpha = (this->edge_weight(*ei) >= 0)? -1 : this->stitch_weight();
254 int32_t idx1 = ijtok(s,t,C.blocks[1].blocksize);
255 int32_t idx2 = ijtok(t,s,C.blocks[1].blocksize);
256 C.blocks[1].data.mat[idx1] = alpha;
257 C.blocks[1].data.mat[idx2] = alpha;
261 construct_objectve_blockrec(C, 2, num_conflict_edges, DIAG);
262 #ifdef DEBUG_SDPCOLORING
263 print_blockrec(
"C.blocks[1].data.mat", C.blocks[1]);
264 print_blockrec(
"C.blocks[2].data.vec", C.blocks[2]);
270 b = (
double *)malloc((num_constraints+1)*
sizeof(double));
271 assert_msg(b,
"Failed to allocate storage for right hand side of constraints b");
274 double beta = -2.0/(this->color_num()-1.0);
275 for (uint32_t i = 1, ie = num_constraints+1; i != ie; ++i)
277 if (i <= num_conflict_edges)
285 constraints=(
struct constraintmatrix *)malloc((num_constraints+1)*
sizeof(
struct constraintmatrix));
286 assert_msg(constraints,
"Failed to allocate storage for constraints");
289 for (boost::tie(ei, eie) = boost::edges(this->m_graph); ei != eie; ++ei)
291 if (this->edge_weight(*ei) >= 0)
293 graph_vertex_type s = boost::source(*ei, this->m_graph);
294 graph_vertex_type t = boost::target(*ei, this->m_graph);
299 struct constraintmatrix& constr = constraints[cnt];
301 constr.blocks = NULL;
304 for (uint32_t i = 2; i != 0; --i)
306 struct sparseblock* blockptr;
309 blockptr = construct_constraint_sparseblock(i, num_vertices, cnt, 1);
310 set_sparseblock_entry(*blockptr, 1, s, t, 1);
314 blockptr = construct_constraint_sparseblock(i, num_conflict_edges, cnt, 1);
315 set_sparseblock_entry(*blockptr, 1, cnt, cnt, -1);
318 blockptr->next = constr.blocks;
319 constr.blocks = blockptr;
325 for (boost::tie(vi, vie) = boost::vertices(this->m_graph); vi != vie; ++vi)
327 graph_vertex_type v = *vi;
329 struct constraintmatrix& constr = constraints[cnt];
331 constr.blocks = NULL;
332 struct sparseblock* blockptr = construct_constraint_sparseblock(1, num_vertices, cnt, 1);
333 set_sparseblock_entry(*blockptr, 1, v, v, 1);
335 blockptr->next = constr.blocks;
336 constr.blocks = blockptr;
340 #ifdef DEBUG_SDPCOLORING
341 write_prob((
char*)
"problem.sdpa", num_variables, num_constraints, C, b, constraints);
347 initsoln(num_variables, num_constraints, C, b, constraints, &X, &y, &Z);
350 struct paramstruc params;
352 initparams(¶ms, &printlevel);
360 int ret = limbo::solvers::easy_sdp_ext<int>(num_variables, num_constraints, C, b, constraints, 0.0, &X, &y, &Z, &pobj, &dobj, params, printlevel);
367 free_prob(num_variables, num_constraints, C, b, constraints, X, y, Z);
369 #ifdef DEBUG_LPCOLORING
374 return this->calc_cost(this->m_vColor);
377 template <
typename GraphType>
380 struct blockrec& cblock = C.blocks[blocknum];
381 cblock.blocksize = blocksize;
382 cblock.blockcategory = blockcategory;
383 if (blockcategory == MATRIX)
385 cblock.data.mat = (
double *)malloc(blocksize*blocksize*
sizeof(
double));
386 assert_msg(cblock.data.mat,
"Couldn't allocate storage for cblock.data.mat");
388 std::fill(cblock.data.mat, cblock.data.mat+blocksize*blocksize, 0);
390 else if (blockcategory == DIAG)
392 cblock.data.vec = (
double *)malloc((blocksize+1)*
sizeof(double));
393 assert_msg(cblock.data.vec,
"Couldn't allocate storage for cblock.data.vec");
395 std::fill(cblock.data.vec, cblock.data.vec+blocksize+1, 0);
399 template <
typename GraphType>
402 struct sparseblock* blockptr = (
struct sparseblock *)malloc(
sizeof(
struct sparseblock));
403 assert_msg(blockptr,
"Allocation of constraint block failed for blockptr");
404 blockptr->blocknum = blocknum;
405 blockptr->blocksize = blocksize;
406 blockptr->constraintnum = constraintnum;
407 blockptr->next = NULL;
408 blockptr->nextbyblock = NULL;
409 blockptr->entries = (
double *) malloc((entrynum+1)*
sizeof(double));
410 assert_msg(blockptr->entries,
"Allocation of constraint block failed for blockptr->entries");
411 blockptr->iindices = (
int *) malloc((entrynum+1)*
sizeof(int));
412 assert_msg(blockptr->iindices,
"Allocation of constraint block failed for blockptr->iindices");
413 blockptr->jindices = (
int *) malloc((entrynum+1)*
sizeof(int));
414 assert_msg(blockptr->jindices,
"Allocation of constraint block failed for blockptr->jindices");
415 blockptr->numentries = entrynum;
420 template <
typename GraphType>
423 block.iindices[entryid] = i;
424 block.jindices[entryid] = j;
425 block.entries[entryid] = value;
428 template <
typename GraphType>
431 #ifdef DEBUG_SDPCOLORING
432 write_sdp_sol(
"problem.sol", X);
435 std::vector<graph_vertex_type> vParent (boost::num_vertices(this->m_graph));
436 std::vector<uint32_t> vRank (vParent.size());
438 disjoint_set_type::SubsetHelper<graph_vertex_type, uint32_t> gp (vParent, vRank);
441 struct blockrec const& block = X.blocks[1];
442 assert_msg(block.blockcategory == MATRIX,
"mismatch of block category");
443 for (int32_t i = 1; i <= block.blocksize; ++i)
444 for (int32_t j = i+1; j <= block.blocksize; ++j)
446 double ent = block.data.mat[ijtok(i, j, block.blocksize)];
447 if (ent > m_rounding_ub)
448 disjoint_set_type::union_set(gp, i-1, j-1);
453 uint32_t mg_count = 0;
454 for (uint32_t i = 0, ie = vParent.size(); i != ie; ++i)
456 vG2MG[i] = mg_count++;
457 for (uint32_t i = 0, ie = vParent.size(); i != ie; ++i)
459 vG2MG[i] = vG2MG.at(disjoint_set_type::find_set(gp, i));
460 #ifdef DEBUG_SDPCOLORING
461 assert(mg_count == disjoint_set_type::count_sets(gp));
463 graph_type mg (mg_count);
465 edge_iterator_type ei, eie;
466 for (boost::tie(ei, eie) = boost::edges(this->m_graph); ei != eie; ++ei)
468 graph_edge_type
const& e = *ei;
469 graph_vertex_type s = boost::source(e, this->m_graph);
470 graph_vertex_type t = boost::target(e, this->m_graph);
471 graph_vertex_type ms = vG2MG.at(s);
472 graph_vertex_type mt = vG2MG.at(t);
473 std::pair<graph_edge_type, bool> me = boost::edge(ms, mt, mg);
475 edge_weight_type w = (this->edge_weight(e) >= 0)? 1 : -this->stitch_weight();
477 w += boost::get(boost::edge_weight, mg, me.first);
479 me = boost::add_edge(ms, mt, mg);
480 boost::put(boost::edge_weight, mg, me.first, w);
481 #ifdef DEBUG_SDPCOLORING
482 assert(boost::get(boost::edge_weight, mg, me.first) != 0);
485 #ifdef DEBUG_SDPCOLORING
489 this->check_edge_weight(mg, this->stitch_weight()/10, boost::num_edges(this->m_graph));
492 std::vector<int8_t> vMColor (mg_count, -1);
493 coloring_merged_graph(mg, vMColor);
496 vertex_iterator_type vi, vie;
497 for (boost::tie(vi, vie) = boost::vertices(this->m_graph); vi != vie; ++vi)
499 graph_vertex_type v = *vi;
500 this->m_vColor[v] = vMColor.at(vG2MG.at(v));
501 #ifdef DEBUG_SDPCOLORING
502 assert(this->m_vColor[v] >= 0 && this->m_vColor[v] < this->color_num());
507 template <
typename GraphType>
510 uint32_t num_vertices = boost::num_vertices(mg);
512 if (num_vertices <= max_backtrack_num_vertices || num_vertices == boost::num_vertices(this->m_graph))
513 coloring_algos(mg, vMColor);
518 graph_simplification_type gs (mg, this->color_num());
519 gs.simplify(graph_simplification_type::HIDE_SMALL_DEGREE);
524 std::vector<std::vector<int8_t> > mSubColor (gs.num_component());
525 std::vector<std::vector<graph_vertex_type> > mSimpl2Orig (gs.num_component());
526 for (uint32_t sub_comp_id = 0; sub_comp_id < gs.num_component(); ++sub_comp_id)
529 std::vector<int8_t>& vSubColor = mSubColor[sub_comp_id];
530 std::vector<graph_vertex_type>& vSimpl2Orig = mSimpl2Orig[sub_comp_id];
532 gs.simplified_graph_component(sub_comp_id, sg, vSimpl2Orig);
534 vSubColor.assign(boost::num_vertices(sg), -1);
536 #ifdef DEBUG_SDPCOLORING
537 this->
write_graph(
"initial_merged_graph", sg, vSubColor);
540 coloring_algos(sg, vSubColor);
541 #ifdef DEBUG_SDPCOLORING
542 this->
write_graph(
"final_merged_graph", sg, vSubColor);
548 gs.recover(vMColor, mSubColor, mSimpl2Orig);
551 gs.recover_hide_small_degree(vMColor);
555 template <
typename GraphType>
558 if (boost::num_vertices(g) <= max_backtrack_num_vertices)
559 coloring_by_backtrack(g, vColor);
561 coloring_by_FM(g, vColor);
564 template <
typename GraphType>
573 for (uint32_t i = 0, ie = vColor.size(); i != ie; ++i)
574 vColor[i] = bc.
color(i);
577 template <
typename GraphType>
583 for (uint32_t i = 0, ie = vColor.size(); i != ie; ++i)
587 template <
typename GraphType>
591 uint32_t matrix_size = 0;
592 for (int32_t blk = 1; blk <= X.nblocks; ++blk)
593 matrix_size += X.blocks[blk].blocksize;
596 std::vector<std::vector<double> > mSol (matrix_size, std::vector<double>(matrix_size, 0.0));
598 int32_t index_offset = 0;
599 for (int32_t blk = 1; blk <= X.nblocks; ++blk)
601 switch (X.blocks[blk].blockcategory)
604 for (int32_t i = 1; i <= X.blocks[blk].blocksize; ++i)
606 double ent = X.blocks[blk].data.vec[i];
608 mSol[index_offset+i-1][index_offset+i-1] = ent;
612 for (int32_t i = 1; i <= X.blocks[blk].blocksize; ++i)
613 for (int32_t j = i; j <= X.blocks[blk].blocksize; ++j)
615 double ent = X.blocks[blk].data.mat[ijtok(i, j, X.blocks[blk].blocksize)];
617 mSol[index_offset+i-1][index_offset+j-1] = ent;
623 index_offset += X.blocks[blk].blocksize;
627 std::ofstream out (filename.c_str());
628 assert_msg(out.good(),
"failed to open file " << filename <<
" for write");
629 for (std::vector<std::vector<double> >::const_iterator it1 = mSol.begin(), it1e = mSol.end(); it1 != it1e; ++it1)
631 const char* prefix =
"";
632 for (std::vector<double>::const_iterator it2 = it1->begin(), it2e = it1->end(); it2 != it2e; ++it2)
634 out << prefix << *it2;
642 template <
typename GraphType>
646 if (block.blockcategory == MATRIX)
649 for (int32_t i = 0, ie = block.blocksize*block.blocksize; i != ie; ++i)
650 printf(
"%g ", block.data.mat[i]);
652 else if (block.blockcategory == DIAG)
655 for (int32_t i = 0; i != block.blocksize; ++i)
656 printf(
"%g ", block.data.vec[i+1]);
static const uint32_t max_backtrack_num_vertices
maximum number of graph size that limbo::algorithms::coloring::BacktrackColoring can handle ...
hasher class for graph_edge_type
virtual double coloring()
signed char partition(int v) const
get partition of a vertex
simply used for scope control
ColorNumType
number of colors
void write_graph(std::ofstream &out, GraphType const &g, VertexLabelType const &vl, EdgeLabelType const &el)
write graph to graphviz format and convert to pdf. Although Boost.Graph has write_graphviz component...
A disjoint set structure and union-find utilities.
struct sparseblock * construct_constraint_sparseblock(int32_t blocknum, int32_t blocksize, int32_t constraintnum, int32_t entrynum) const
virtual double stitch_weight() const
virtual void coloring_by_backtrack(graph_type const &mg, std::vector< int8_t > &vColor) const
graph coloring by backtracking
FMGainCalcType(graph_type const &g)
void round_sol(struct blockmatrix const &X)
void coloring_algos(graph_type const &g, std::vector< int8_t > &vColor) const
edge_weight_type value_type
define edge_weight_type as value_type
double m_rounding_lb
if SDP solution x < m_rounding_lb, take x as -0.5
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
void set_partitions(Iterator first, Iterator last)
set partitions
Various graph simplification techniques for graph coloring. Some of them can also be used in other ap...
edge_weight_type operator()(int32_t v, int8_t origp, int8_t newp, std::vector< int8_t > const &vPartition) const
base class for all graph coloring algorithms
graph_type const & graph
graph
virtual ~SDPColoringCsdp()
destructor
void set_sparseblock_entry(struct sparseblock &block, int32_t entryid, int32_t i, int32_t j, double value) const
void construct_objectve_blockrec(blockmatrix &C, int32_t blocknum, int32_t blocksize, blockcat blockcategory) const
void coloring_merged_graph(graph_type const &mg, std::vector< int8_t > &vMColor) const
virtual void color_num(ColorNumType cn)
Check string is integer, floating point, number... Convert string to upper/lower cases.
this file is a modified version of easysdp.c in Csdp package. Original version does not provide contr...
void print_blockrec(const char *label, blockrec const &block) const
virtual int8_t color(graph_vertex_type v) const
SDPColoringCsdp(graph_type const &g)
void write_sdp_sol(std::string const &filename, struct blockmatrix const &X) const
double m_rounding_ub
if SDP solution x > m_rounding_ub, take x as 1.0
#define assert_msg(condition, message)
assertion with message
virtual void coloring_by_FM(graph_type const &mg, std::vector< int8_t > &vColor) const
Implementation of the Multi-way FM partitioning algorithm.