8 #ifndef LIMBO_ALGORITHMS_COLORING_BACKTRACKCOLORING
9 #define LIMBO_ALGORITHMS_COLORING_BACKTRACKCOLORING
27 template <
typename GraphType>
33 using typename base_type::graph_type;
34 using typename base_type::graph_vertex_type;
35 using typename base_type::graph_edge_type;
36 using typename base_type::vertex_iterator_type;
37 using typename base_type::edge_iterator_type;
38 using typename base_type::edge_weight_type;
40 typedef typename boost::graph_traits<graph_type>::adjacency_iterator adjacency_iterator_type;
65 void coloring_kernel(vector<int8_t>& vBestColor, vector<int8_t>& vColor,
double& best_cost,
double& cur_cost, graph_vertex_type v,
double cost_lb,
double cost_ub)
const;
68 template <
typename GraphType>
71 vector<int8_t> vBestColor(this->m_vColor.begin(), this->m_vColor.end());
72 vector<int8_t> vColor (this->m_vColor.begin(), this->m_vColor.end());
73 double best_cost = this->init_coloring(vBestColor);
81 if (boost::num_vertices(this->m_graph) > 50 && best_cost > 0)
83 double cur_best_cost = best_cost;
85 for (
double tmp_best_cost = 0; tmp_best_cost < cur_best_cost; ++tmp_best_cost)
89 this->coloring_kernel(vBestColor, vColor, best_cost, cur_cost, 0, tmp_best_cost, tmp_best_cost);
95 if (best_cost <= tmp_best_cost)
99 vColor.assign(this->m_vColor.begin(), this->m_vColor.end());
103 else if (best_cost > 0)
104 this->coloring_kernel(vBestColor, vColor, best_cost, cur_cost, 0, 0, best_cost);
107 this->m_vColor.swap(vBestColor);
110 actual_cost = this->calc_cost(this->m_vColor);
111 assert_msg(best_cost == actual_cost,
"best_cost = " << best_cost <<
", actual cost = " << actual_cost);
116 template <
typename GraphType>
122 vertex_iterator_type vi, vie;
123 for (boost::tie(vi, vie) = boost::vertices(this->m_graph); vi != vie; ++vi)
125 graph_vertex_type v = *vi;
126 int8_t color = dc.
color(v);
127 if (vColor[v] >= 0 && vColor[v] < this->m_color_num)
129 else if (color >= this->m_color_num)
130 vColor[v] = this->m_color_num-1;
131 else vColor[v] = color;
132 assert(vColor[v] >= 0 && vColor[v] < this->m_color_num);
135 double cost = this->calc_cost(vColor);
139 template <
typename GraphType>
141 BacktrackColoring<GraphType>::graph_vertex_type v,
double cost_lb,
double cost_ub)
const
143 if (best_cost <= cost_lb)
145 if (cur_cost >= best_cost || cur_cost > cost_ub)
147 if (v == boost::num_vertices(this->m_graph))
149 if (cur_cost < best_cost)
151 best_cost = cur_cost;
152 vBestColor.assign(vColor.begin(), vColor.end());
157 int8_t color_begin = 0;
158 int8_t color_end = this->m_color_num;
159 if (this->m_vColor[v] >= 0 && this->m_vColor[v] < this->m_color_num)
161 color_begin = this->m_vColor[v];
162 color_end = color_begin+1;
164 for (int8_t c = color_begin; c < color_end; ++c)
167 double delta_cost = 0;
168 adjacency_iterator_type vi, vie;
169 for (boost::tie(vi, vie) = boost::adjacent_vertices(v, this->m_graph); vi != vie; ++vi)
171 graph_vertex_type u = *vi;
176 std::pair<graph_edge_type, bool> e = boost::edge(u, v, this->m_graph);
177 assert_msg(e.second,
"failed to find edge with " << u <<
"--" << v);
178 edge_weight_type w = boost::get(boost::edge_weight, this->m_graph, e.first);
179 assert_msg(w > 0,
"only support conflict edges with positive cost");
184 cur_cost += delta_cost;
185 this->coloring_kernel(vBestColor, vColor, best_cost, cur_cost, v+1, cost_lb, cost_ub);
186 cur_cost -= delta_cost;
double init_coloring(vector< int8_t > &vColor) const
ColorNumType
number of colors
virtual ~BacktrackColoring()
destructor
virtual double coloring()
coloring a graph with saturation degree based heuristics
base class for all graph coloring algorithms
void coloring_kernel(vector< int8_t > &vBestColor, vector< int8_t > &vColor, double &best_cost, double &cur_cost, graph_vertex_type v, double cost_lb, double cost_ub) const
BacktrackColoring(graph_type const &g)
int color(graph_vertex_type v) const
#define assert_msg(condition, message)
assertion with message