12 #ifndef LIMBO_ALGORITHMS_COLORING_ILPCOLORINGLEMONCBC
13 #define LIMBO_ALGORITHMS_COLORING_ILPCOLORINGLEMONCBC
26 #include <boost/cstdint.hpp>
27 #include <boost/unordered_map.hpp>
28 #include <boost/graph/graph_concepts.hpp>
29 #include <boost/graph/subgraph.hpp>
30 #include <boost/property_map/property_map.hpp>
37 #include <lemon/cbc.h>
50 using std::ostringstream;
51 using boost::unordered_map;
64 template <
typename GraphType>
70 using typename base_type::graph_type;
71 using typename base_type::graph_vertex_type;
72 using typename base_type::graph_edge_type;
73 using typename base_type::vertex_iterator_type;
74 using typename base_type::edge_iterator_type;
75 using typename base_type::edge_weight_type;
88 boost::hash_combine(seed, e.m_source);
89 boost::hash_combine(seed, e.m_target);
107 template <
typename GraphType>
110 uint32_t vertex_num = boost::num_vertices(this->m_graph);
111 uint32_t edge_num = boost::num_edges(this->m_graph);
112 uint32_t vertex_variable_num = vertex_num<<1;
114 unordered_map<graph_vertex_type, uint32_t> hVertexIdx;
115 unordered_map<graph_edge_type, uint32_t, edge_hash_type> hEdgeIdx;
117 vertex_iterator_type vi, vie;
119 for (boost::tie(vi, vie) = boost::vertices(this->m_graph); vi != vie; ++vi, ++cnt)
120 hVertexIdx[*vi] = cnt;
121 edge_iterator_type ei, eie;
123 for (boost::tie(ei, eie) = boost::edges(this->m_graph); ei != eie; ++ei, ++cnt)
126 typedef lemon::MipSolver::Row Row;
127 typedef lemon::MipSolver::Col Col;
128 typedef lemon::MipSolver::Expr Expr;
131 lemon::CbcMip opt_model;
135 vector<Col> vVertexBit;
136 vector<Col> vEdgeBit;
139 vVertexBit.reserve(vertex_variable_num);
140 for (uint32_t i = 0; i != vertex_variable_num; ++i)
142 uint32_t vertex_idx = (i>>1);
145 if (this->m_vColor[vertex_idx] >= 0 && this->m_vColor[vertex_idx] < this->m_color_num)
148 if ((i&1) == 0) color_bit = (this->m_vColor[vertex_idx]>>1)&1;
149 else color_bit = this->m_vColor[vertex_idx]&1;
150 vVertexBit.push_back(opt_model.addCol());
151 Col
const& x = vVertexBit.back();
152 opt_model.colBounds(x, color_bit, color_bit);
154 opt_model.colName(x, oss.str());
158 vVertexBit.push_back(opt_model.addCol());
159 Col
const& x = vVertexBit.back();
160 opt_model.colBounds(x, 0, 1);
162 opt_model.colName(x, oss.str());
167 vEdgeBit.reserve(edge_num);
168 for (uint32_t i = 0; i != edge_num; ++i)
172 vEdgeBit.push_back(opt_model.addCol());
173 Col
const& x = vEdgeBit.back();
174 opt_model.colBounds(x, 0, 1);
175 opt_model.colType(x, lemon::MipSolver::REAL);
176 opt_model.colName(x, oss.str());
183 for (boost::tie(ei, eie) = edges(this->m_graph); ei != eie; ++ei)
185 edge_weight_type w = boost::get(boost::edge_weight, this->m_graph, *ei);
187 obj += w*vEdgeBit[hEdgeIdx[*ei]];
189 obj += this->m_stitch_weight*(-w)*vEdgeBit[hEdgeIdx[*ei]];
196 for (boost::tie(ei, eie) = boost::edges(this->m_graph); ei != eie; ++ei)
198 graph_vertex_type s = boost::source(*ei, this->m_graph);
199 graph_vertex_type t = boost::target(*ei, this->m_graph);
200 uint32_t sIdx = hVertexIdx[s];
201 uint32_t tIdx = hVertexIdx[t];
203 uint32_t vertex_idx1 = sIdx<<1;
204 uint32_t vertex_idx2 = tIdx<<1;
206 edge_weight_type w = boost::get(boost::edge_weight, this->m_graph, *ei);
207 uint32_t edge_idx = hEdgeIdx[*ei];
214 vVertexBit[vertex_idx1] + vVertexBit[vertex_idx1+1]
215 + vVertexBit[vertex_idx2] + vVertexBit[vertex_idx2+1]
216 + vEdgeBit[edge_idx] >= 1
221 1 - vVertexBit[vertex_idx1] + vVertexBit[vertex_idx1+1]
222 + 1 - vVertexBit[vertex_idx2] + vVertexBit[vertex_idx2+1]
223 + vEdgeBit[edge_idx] >= 1
228 vVertexBit[vertex_idx1] + 1 - vVertexBit[vertex_idx1+1]
229 + vVertexBit[vertex_idx2] + 1 - vVertexBit[vertex_idx2+1]
230 + vEdgeBit[edge_idx] >= 1
235 1 - vVertexBit[vertex_idx1] + 1 - vVertexBit[vertex_idx1+1]
236 + 1 - vVertexBit[vertex_idx2] + 1 - vVertexBit[vertex_idx2+1]
237 + vEdgeBit[edge_idx] >= 1
245 vVertexBit[vertex_idx1] - vVertexBit[vertex_idx2] - vEdgeBit[edge_idx] <= 0
250 vVertexBit[vertex_idx2] - vVertexBit[vertex_idx1] - vEdgeBit[edge_idx] <= 0
255 vVertexBit[vertex_idx1+1] - vVertexBit[vertex_idx2+1] - vEdgeBit[edge_idx] <= 0
260 vVertexBit[vertex_idx2+1] - vVertexBit[vertex_idx1+1] - vEdgeBit[edge_idx] <= 0
266 if (this->m_color_num == base_type::THREE)
269 for(uint32_t k = 0; k != vertex_variable_num; k += 2)
272 opt_model.addRow(vVertexBit[k] + vVertexBit[k+1] <= 1);
278 int32_t opt_status = opt_model.type();
281 cout <<
"ERROR: The model is infeasible... EXIT" << endl;
286 for (uint32_t k = 0; k != vertex_variable_num; k += 2)
288 int8_t color = (opt_model.sol(vVertexBit[k])*2) + opt_model.sol(vVertexBit[k+1]);
289 uint32_t vertex_idx = (k>>1);
291 assert(color >= 0 && color < this->m_color_num);
292 if (this->m_vColor[vertex_idx] >= 0 && this->m_vColor[vertex_idx] < this->m_color_num)
293 assert(this->m_vColor[vertex_idx] == color);
295 this->m_vColor[vertex_idx] = color;
299 return opt_model.solValue();
hasher class for graph_edge_type
ILPColoringLemonCbc(graph_type const &g)
ColorNumType
number of colors
virtual double coloring()
virtual ~ILPColoringLemonCbc()
destructor
std::size_t operator()(graph_edge_type const &e) const
base class for all graph coloring algorithms
Check string is integer, floating point, number... Convert string to upper/lower cases.