8 #ifndef LIMBO_ALGORITHMS_COLORING_ILPCOLORING
9 #define LIMBO_ALGORITHMS_COLORING_ILPCOLORING
22 #include <boost/cstdint.hpp>
23 #include <boost/unordered_map.hpp>
24 #include <boost/graph/graph_concepts.hpp>
25 #include <boost/graph/subgraph.hpp>
26 #include <boost/property_map/property_map.hpp>
53 template <
typename GraphType>
59 using typename base_type::graph_type;
60 using typename base_type::graph_vertex_type;
61 using typename base_type::graph_edge_type;
62 using typename base_type::vertex_iterator_type;
63 using typename base_type::edge_iterator_type;
64 using typename base_type::edge_weight_type;
83 void write_graph_sol(
string const& filename, model_type
const& opt_model, std::vector<model_type::variable_type>
const& vVertexBit)
const;
91 template <
typename GraphType>
94 uint32_t vertex_num = boost::num_vertices(this->m_graph);
95 uint32_t edge_num = boost::num_edges(this->m_graph);
96 uint32_t vertex_variable_num = vertex_num<<1;
98 boost::unordered_map<graph_edge_type, uint32_t, edge_hash_type> hEdgeIdx;
101 edge_iterator_type ei, eie;
102 for (boost::tie(ei, eie) = boost::edges(this->m_graph); ei != eie; ++ei, ++cnt)
111 std::vector<model_type::variable_type> vVertexBit;
112 std::vector<model_type::variable_type> vEdgeBit;
115 if (this->m_color_num == base_type::THREE)
121 vVertexBit.reserve(vertex_variable_num);
122 for (uint32_t i = 0; i != vertex_variable_num; ++i)
124 uint32_t vertex_idx = (i>>1);
125 std::ostringstream oss;
127 if (this->m_vColor[vertex_idx] >= 0 && this->m_vColor[vertex_idx] < this->m_color_num)
130 if ((i&1) == 0) color_bit = (this->m_vColor[vertex_idx]>>1)&1;
131 else color_bit = this->m_vColor[vertex_idx]&1;
139 vEdgeBit.reserve(edge_num);
140 for (uint32_t i = 0; i != edge_num; ++i)
142 std::ostringstream oss;
149 for (boost::tie(ei, eie) = edges(this->m_graph); ei != eie; ++ei)
151 edge_weight_type w = boost::get(boost::edge_weight, this->m_graph, *ei);
153 obj += w*vEdgeBit[hEdgeIdx[*ei]];
155 obj += this->m_stitch_weight*(-w)*vEdgeBit[hEdgeIdx[*ei]];
161 uint32_t constr_num = 0;
162 for (boost::tie(ei, eie) = boost::edges(this->m_graph); ei != eie; ++ei)
164 graph_vertex_type s = boost::source(*ei, this->m_graph);
165 graph_vertex_type t = boost::target(*ei, this->m_graph);
167 uint32_t vertex_idx1 = s<<1;
168 uint32_t vertex_idx2 = t<<1;
170 edge_weight_type w = boost::get(boost::edge_weight, this->m_graph, *ei);
171 uint32_t edge_idx = hEdgeIdx[*ei];
174 string tmpConstr_name;
177 sprintf(buf,
"R%u", constr_num++);
179 vVertexBit[vertex_idx1] + vVertexBit[vertex_idx1+1]
180 + vVertexBit[vertex_idx2] + vVertexBit[vertex_idx2+1]
181 + vEdgeBit[edge_idx] >= 1
184 sprintf(buf,
"R%u", constr_num++);
186 - vVertexBit[vertex_idx1] + vVertexBit[vertex_idx1+1]
187 - vVertexBit[vertex_idx2] + vVertexBit[vertex_idx2+1]
188 + vEdgeBit[edge_idx] >= -1
191 sprintf(buf,
"R%u", constr_num++);
193 vVertexBit[vertex_idx1] - vVertexBit[vertex_idx1+1]
194 + vVertexBit[vertex_idx2] - vVertexBit[vertex_idx2+1]
195 + vEdgeBit[edge_idx] >= -1
198 sprintf(buf,
"R%u", constr_num++);
200 - vVertexBit[vertex_idx1] - vVertexBit[vertex_idx1+1]
201 - vVertexBit[vertex_idx2] - vVertexBit[vertex_idx2+1]
202 + vEdgeBit[edge_idx] >= -3
208 sprintf(buf,
"R%u", constr_num++);
210 vVertexBit[vertex_idx1] - vVertexBit[vertex_idx2] - vEdgeBit[edge_idx] <= 0
213 sprintf(buf,
"R%u", constr_num++);
215 vVertexBit[vertex_idx2] - vVertexBit[vertex_idx1] - vEdgeBit[edge_idx] <= 0
218 sprintf(buf,
"R%u", constr_num++);
220 vVertexBit[vertex_idx1+1] - vVertexBit[vertex_idx2+1] - vEdgeBit[edge_idx] <= 0
223 sprintf(buf,
"R%u", constr_num++);
225 vVertexBit[vertex_idx2+1] - vVertexBit[vertex_idx1+1] - vEdgeBit[edge_idx] <= 0
231 if (this->m_color_num == base_type::THREE)
234 for(uint32_t k = 0; k != vertex_variable_num; k += 2)
236 sprintf(buf,
"R%u", constr_num++);
237 opt_model.
addConstraint(vVertexBit[k] + vVertexBit[k+1] <= 1, buf);
243 int32_t opt_status = solver(&gurobiParams);
244 #ifdef DEBUG_ILPCOLORING
245 opt_model.
print(
"graph.lp");
250 cout <<
"ERROR: The model is infeasible... EXIT" << endl;
254 #ifdef DEBUG_ILPCOLORING
255 this->write_graph_sol(
"graph_sol", opt_model, vVertexBit);
259 for (uint32_t k = 0; k != vertex_variable_num; k += 2)
262 uint32_t vertex_idx = (k>>1);
264 assert(color >= 0 && color < this->m_color_num);
265 if (this->m_vColor[vertex_idx] >= 0 && this->m_vColor[vertex_idx] < this->m_color_num)
266 assert(this->m_vColor[vertex_idx] == color);
268 this->m_vColor[vertex_idx] = color;
275 template <
typename GraphType>
279 std::ofstream out((filename+
".gv").c_str());
280 out <<
"graph D { \n"
282 <<
" size=\"4, 3\"\n"
283 <<
" ratio=\"fill\"\n"
284 <<
" edge[style=\"bold\",fontsize=200]\n"
285 <<
" node[shape=\"circle\",fontsize=200]\n";
288 uint32_t vertex_num = boost::num_vertices(this->m_graph);
289 for(uint32_t k = 0; k < vertex_num; ++k)
291 out <<
" " << k <<
"[shape=\"circle\"";
298 edge_iterator_type ei, eie;
299 for (boost::tie(ei, eie) = boost::edges(this->m_graph); ei != eie; ++ei)
301 edge_weight_type w = boost::get(boost::edge_weight, this->m_graph, *ei);
302 graph_vertex_type s = boost::source(*ei, this->m_graph);
303 graph_vertex_type t = boost::target(*ei, this->m_graph);
310 out <<
" " << s <<
"--" << t <<
"[color=\"red\",style=\"solid\",penwidth=3]\n";
312 out <<
" " << s <<
"--" << t <<
"[color=\"black\",style=\"solid\",penwidth=3]\n";
315 out <<
" " << s <<
"--" << t <<
"[color=\"blue\",style=\"dotted\",penwidth=3]\n";
hasher class for graph_edge_type
Gurobi API with limbo::solvers::LinearModel.
void setNumThreads(int v)
set number of threads
variable_value_type variableSolution(variable_type const &var) const
Base class for custom Gurobi parameters.
ColorNumType
number of colors
bool printSolution(std::string const &filename) const
print solutions to file
bool addConstraint(constraint_type const &constr, std::string name="")
add a constraint
Basic utilities such as variables and linear expressions in solvers.
void reserveVariables(unsigned int n)
reserve space for variables
virtual ~ILPColoring()
destructor
void reserveConstraints(unsigned int n)
reserve space for constraints
void setOptimizeType(SolverProperty optType)
ILPColoring(graph_type const &g)
Gurobi API wrapper using its C API.
void setObjective(expression_type const &expr)
set objective
void setOutputFlag(int v)
set output flag
void write_graph_sol(string const &filename, model_type const &opt_model, std::vector< model_type::variable_type > const &vVertexBit) const
virtual double coloring()
base class for all graph coloring algorithms
Check string is integer, floating point, number... Convert string to upper/lower cases.
coefficient_value_type evaluateObjective(std::vector< variable_value_type > const &vVariableSol) const
evaluate objective
model to describe an optimization problem
variable_type addVariable(variable_value_type lb, variable_value_type ub, SolverProperty nt, std::string name="")
add one variable
bool print(std::string const &filename) const
print problem in lp format to file
void graphviz2pdf(std::string const &filename, const char *suffix=".gv")
convert graphviz format to pdf. The input filename should be filename+suffix