1 #ifndef VIENNACL_MISC_GIBBS_POOLE_STOCKMEYER_HPP
2 #define VIENNACL_MISC_GIBBS_POOLE_STOCKMEYER_HPP
50 for (std::size_t i = 0; i < l.size(); i++)
52 w = std::max(w, static_cast<int>(l[i].
size()));
60 template <
typename MatrixType>
62 std::vector<int>
const & rg)
64 std::vector< std::vector<int> > rgc;
65 std::vector< std::vector<int> > rgc_sorted;
66 std::vector< std::vector<int> > sort_ind;
67 std::vector<int> ind(2);
70 std::vector<bool> inr(n,
true);
73 for (std::size_t i = 0; i < rg.size(); i++)
80 for (
int i = 0; i < n; i++)
104 for (
typename MatrixType::value_type::const_iterator it = matrix[c].begin(); it != matrix[c].end(); it++)
106 if (it->first == c)
continue;
107 if (inr[it->first])
continue;
109 q.push_back(it->first);
116 for (std::size_t i = 0; i < rgc.size(); i++)
119 ind[1] = rgc[i].size();
120 sort_ind.push_back(ind);
123 for (std::size_t i = 0; i < rgc.size(); i++)
125 rgc_sorted.push_back(rgc[sort_ind[rgc.size()-1-i][0]]);
150 template <
typename MatrixType>
154 std::size_t n = matrix.size();
156 std::vector< std::vector<int> > rl;
160 std::vector< std::vector<int> > nodes;
161 std::vector<bool> inr(n,
false);
162 std::vector<bool> isn(n,
false);
163 std::vector<int> tmp(2);
166 std::vector< std::vector<int> > lg;
167 std::vector< std::vector<int> > lh;
168 std::vector< std::vector<int> > ls;
169 std::map< int, std::vector<int> > lap;
171 std::vector< std::vector<int> > rgc;
176 std::vector<int> wvs;
177 std::vector<int> wvsg;
178 std::vector<int> wvsh;
191 for (std::size_t i = 0; i < n; i++)
195 deg = matrix[i].size() - 1;
196 if (deg_min < 0 || deg < deg_min)
211 for (std::size_t i = 0; i < lg.back().size(); i++)
213 tmp[0] = lg.back()[i];
214 tmp[1] = matrix[lg.back()[i]].size() - 1;
215 nodes.push_back(tmp);
218 for (std::size_t i = 0; i < nodes.size(); i++)
220 lg.back()[i] = nodes[i][0];
225 for (std::size_t i = 0; i < lg.back().size(); i++)
229 if (lh.size() > lg.size())
236 if (m_min < 0 || m < m_min)
250 for (std::size_t i = 0; i < lg.size(); i++)
252 for (std::size_t j = 0; j < lg[i].size(); j++)
254 lap[lg[i][j]].resize(2);
255 lap[lg[i][j]][0] = i;
258 for (std::size_t i = 0; i < lh.size(); i++)
260 for (std::size_t j = 0; j < lh[i].size(); j++)
262 lap[lh[i][j]][1] = lg.size() - 1 - i;
267 ls.resize(lg.size());
268 for (std::map<
int, std::vector<int> >::iterator it = lap.begin();
269 it != lap.end(); it++)
271 if ((it->second)[0] == (it->second)[1])
273 ls[(it->second)[0]].push_back(it->first);
277 rg.push_back(it->first);
286 wvs.resize(ls.size());
287 wvsg.resize(ls.size());
288 wvsh.resize(ls.size());
289 for (std::size_t i = 0; i < rgc.size(); i++)
291 for (std::size_t j = 0; j < ls.size(); j++)
293 wvs[j] = ls[j].size();
294 wvsg[j] = ls[j].size();
295 wvsh[j] = ls[j].size();
297 for (std::size_t j = 0; j < rgc[i].size(); j++)
299 (wvsg[lap[rgc[i][j]][0]])++;
300 (wvsh[lap[rgc[i][j]][1]])++;
304 for (std::size_t j = 0; j < ls.size(); j++)
306 if (wvsg[j] > wvs[j])
308 k3 = std::max(k3, wvsg[j]);
310 if (wvsh[j] > wvs[j])
312 k4 = std::max(k4, wvsh[j]);
315 if (k3 < k4 || (k3 == k4 && k1 <= k2) )
317 for (std::size_t j = 0; j < rgc[i].size(); j++)
319 ls[lap[rgc[i][j]][0]].push_back(rgc[i][j]);
324 for (std::size_t j = 0; j < rgc[i].size(); j++)
326 ls[lap[rgc[i][j]][1]].push_back(rgc[i][j]);
333 rl.resize(ls.size());
346 for (std::size_t i = 0; i < rl[l-1].size(); i++)
348 isn.assign(n,
false);
349 for (std::map<int, double>::const_iterator it = matrix[rl[l-1][i]].begin();
350 it != matrix[rl[l-1][i]].end();
353 if (it->first == rl[l-1][i])
continue;
354 isn[it->first] =
true;
357 for (std::size_t j = 0; j < ls[l].size(); j++)
359 if (inr[ls[l][j]])
continue;
360 if (!isn[ls[l][j]])
continue;
362 tmp[1] = matrix[ls[l][j]].size() - 1;
363 nodes.push_back(tmp);
366 for (std::size_t j = 0; j < nodes.size(); j++)
368 rl[l].push_back(nodes[j][0]);
369 r.push_back(nodes[j][0]);
370 inr[nodes[j][0]] =
true;
375 for (std::size_t i = 0; i < rl[l].size(); i++)
377 isn.assign(n,
false);
378 for (std::map<int, double>::const_iterator it = matrix[rl[l][i]].begin();
379 it != matrix[rl[l][i]].end();
382 if (it->first == rl[l][i])
continue;
383 isn[it->first] =
true;
386 for (std::size_t j = 0; j < ls[l].size(); j++)
388 if (inr[ls[l][j]])
continue;
389 if (!isn[ls[l][j]])
continue;
391 tmp[1] = matrix[ls[l][j]].size() - 1;
392 nodes.push_back(tmp);
395 for (std::size_t j = 0; j < nodes.size(); j++)
397 rl[l].push_back(nodes[j][0]);
398 r.push_back(nodes[j][0]);
399 inr[nodes[j][0]] =
true;
407 for (std::size_t j = 0; j < ls[l].size(); j++)
409 if (inr[ls[l][j]])
continue;
410 deg = matrix[ls[l][j]].size() - 1;
411 if (deg_min < 0 || deg < deg_min)
417 rl[l].push_back(ind_min);
418 r.push_back(ind_min);