1 #ifndef VIENNACL_MISC_CUTHILL_MCKEE_HPP
2 #define VIENNACL_MISC_CUTHILL_MCKEE_HPP
51 inline bool comb_inc(std::vector<int> & comb,
int n)
59 while ( (k > 0) && ( ((k == m) && (comb[k-1] == n)) ||
60 ((k < m) && (comb[k-1] == comb[k] - 1) )) )
71 for (
int i = k; i < m; i++)
74 comb[i] = comb[k-1] + (i - k + 1);
83 template <
typename MatrixType>
85 std::vector< std::vector<int> > & l,
88 std::size_t n = matrix.size();
90 std::vector<bool> inr(n,
false);
91 std::vector<int> nlist;
100 for (std::vector<int>::iterator it = l.back().begin();
101 it != l.back().end();
104 for (
typename MatrixType::value_type::const_iterator it2 = matrix[*it].begin();
105 it2 != matrix[*it].end();
108 if (it2->first == *it)
continue;
109 if (inr[it2->first])
continue;
111 nlist.push_back(it2->first);
112 inr[it2->first] =
true;
116 if (nlist.size() == 0)
128 std::vector<int>
const & b)
130 return (a[1] < b[1]);
156 template <
typename MatrixType>
159 std::size_t n = matrix.size();
161 std::vector<bool> inr(n,
false);
163 std::vector< std::vector<int> > nodes;
164 std::vector<int> tmp(2);
178 for (std::size_t i = 0; i < n; i++)
182 deg = matrix[i].size() - 1;
183 if (deg_min < 0 || deg < deg_min)
203 for (
typename MatrixType::value_type::const_iterator it = matrix[c].begin(); it != matrix[c].end(); it++)
205 if (it->first == c)
continue;
206 if (inr[it->first])
continue;
209 tmp[1] = matrix[it->first].size() - 1;
210 nodes.push_back(tmp);
215 for (std::vector< std::vector<int> >::iterator it = nodes.begin(); it != nodes.end(); it++)
217 q.push_back((*it)[0]);
220 }
while (q.size() != 0);
221 }
while (r.size() < n);
262 double starting_node_param_;
263 std::size_t max_root_nodes_;
276 template <
typename MatrixType>
280 std::size_t n = matrix.size();
284 std::vector<int> r_tmp;
285 std::vector<int> r_best;
286 std::vector<int> r2(n);
287 std::vector<bool> inr(n,
false);
288 std::vector<bool> inr_tmp(n);
289 std::vector<bool> inr_best(n);
291 std::vector< std::vector<int> > nodes;
292 std::vector<int> nodes_p;
293 std::vector<int> tmp(2);
294 std::vector< std::vector<int> > l;
301 std::vector<int> comb;
316 for (std::size_t i = 0; i < n; i++)
325 for (std::vector< std::vector<int> >::iterator it = l.begin();
328 for (std::vector<int>::iterator it2 = it->begin();
329 it2 != it->end(); it2++)
332 tmp[1] = matrix[*it2].size() - 1;
333 nodes.push_back(tmp);
339 for (std::vector< std::vector<int> >::iterator it = nodes.begin();
340 it != nodes.end(); it++)
343 if (deg_min < 0 || deg < deg_min)
347 if (deg_max < 0 || deg > deg_max)
352 deg_a = deg_min + (int) (a * (deg_max - deg_min));
354 for (std::vector< std::vector<int> >::iterator it = nodes.begin();
355 it != nodes.end(); it++)
357 if ((*it)[1] <= deg_a)
359 nodes_p.push_back((*it)[0]);
375 for (std::vector<int>::iterator it = comb.begin();
376 it != comb.end(); it++)
378 q.push_back(nodes_p[(*it)-1]);
392 for (
typename MatrixType::value_type::const_iterator it = matrix[c].begin(); it != matrix[c].end(); it++)
394 if (it->first == c)
continue;
395 if (inr[it->first])
continue;
398 tmp[1] = matrix[it->first].size() - 1;
399 nodes.push_back(tmp);
402 for (std::vector< std::vector<int> >::iterator it =
403 nodes.begin(); it != nodes.end(); it++)
405 q.push_back((*it)[0]);
408 }
while (q.size() != 0);
412 for (std::size_t i = 0; i < r_tmp.size(); i++)
414 r2[r_tmp[i]] = r.size() + i;
417 for (std::size_t i = 0; i < r_tmp.size(); i++)
419 for (
typename MatrixType::value_type::const_iterator it = matrix[r_tmp[i]].begin();
420 it != matrix[r_tmp[i]].end();
423 bw = std::max(bw, std::abs(static_cast<int>(r.size() + i) - r2[it->first]));
428 if (bw_best < 0 || bw < bw_best)
440 if ( (gmax > 0 && g > gmax) || g > nodes_p.size())
445 for (std::size_t i = 0; i < g; i++)
453 for (std::vector<int>::iterator it = r_best.begin();
454 it != r_best.end(); it++)
460 }
while (r.size() < n);