HOG2
DVCBSQueue.h
Go to the documentation of this file.
1 //
2 // DVCBSQueue.h
3 // hog2 mac native demos
4 //
5 // Created by Shahaf S. Shperberg
6 //
7 
8 #ifndef DVCBSQueue_h
9 #define DVCBSQueue_h
10 
11 #include "DVCBSOpenClosed.h"
12 #include "DVCBSQueue.h"
13 #include <vector>
14 #include <climits>
15 #include <unordered_map>
16 #include <utility>
17 #include <algorithm>
18 
19 
20 template <typename state, int epsilon = 0, bool isAllSolutions = false>
21 class DVCBSQueue {
22 public:
23  bool getVertexCover(std::vector<uint64_t> &nextForward, std::vector<uint64_t> &nextBackward,int TieBreakingPolicy)
24  {
25 
26  while (true)
27  {
28  if (forwardQueue.OpenSize() == 0)
29  return false;
30  if (backwardQueue.OpenSize() == 0)
31  return false;
32 
33  // move items with f<CLowerBound to ready
34 
35  while (forwardQueue.OpenWaitingSize() != 0 && ((!isAllSolutions && fless(forwardQueue.getFirstKey(kOpenWaiting),CLowerBound)) || (isAllSolutions && !fgreater(forwardQueue.getFirstKey(kOpenWaiting),CLowerBound))))
36  {
37  forwardQueue.PutToReady();
38  }
39  while (backwardQueue.OpenWaitingSize() != 0 && ((!isAllSolutions && fless(backwardQueue.getFirstKey(kOpenWaiting), CLowerBound)) || (isAllSolutions && !fgreater(backwardQueue.getFirstKey(kOpenWaiting), CLowerBound))))
40  {
41  backwardQueue.PutToReady();
42  }
43 
44  if ((forwardQueue.OpenReadySize() != 0) && (backwardQueue.OpenReadySize() != 0) &&
45  (!fgreater(forwardQueue.getFirstKey(kOpenReady) + backwardQueue.getFirstKey(kOpenReady) + epsilon, CLowerBound)))
46  {
47  std::vector<std::pair<double,uint64_t> > forwardCluster;
48  std::vector<std::pair<double,uint64_t> > backwardCluster;
49  for (auto it = forwardQueue.getNodesMapBegin(kOpenReady); it != forwardQueue.getNodesMapEnd(kOpenReady) && it->first <= CLowerBound-backwardQueue.getFirstKey(kOpenReady) - epsilon+TOLERANCE; it++){
50  forwardCluster.push_back(std::make_pair(it->first,it->second.size()));
51  }
52  for (auto it = backwardQueue.getNodesMapBegin(kOpenReady); it != backwardQueue.getNodesMapEnd(kOpenReady) && it->first <= CLowerBound-forwardQueue.getFirstKey(kOpenReady) - epsilon+TOLERANCE; it++){
53  backwardCluster.push_back(std::make_pair(it->first,it->second.size()));
54  }
55  int minJ = INT_MAX;
56  int minI = INT_MAX;
57  int minValue = INT_MAX;
58  uint64_t NumForwardInVC = 0;
59  uint64_t NumBackwardInVC = 0;
60  std::vector<std::pair<int,int> > minimalVertexCovers;
61  for (int i = -1; i < ((int)forwardCluster.size()); i++){
62  if (i >= 0){
63  NumForwardInVC += forwardCluster[i].second;
64  }
65  else{
66  NumForwardInVC = 0;
67  }
68  bool skip = false;
69  for (int j = -1; j < ((int)backwardCluster.size()) && !skip; j++){
70  if (j >= 0){
71  NumBackwardInVC += backwardCluster[j].second;
72  }
73  else{
74  NumBackwardInVC = 0;
75  }
76  if (i == ((int)forwardCluster.size())-1){
77  if (NumForwardInVC < minValue){
78  minimalVertexCovers.clear();
79  }
80  if(NumForwardInVC <= minValue){
81  minimalVertexCovers.push_back(std::make_pair(i,j));
82  minValue = NumForwardInVC;
83  }
84  skip = true;
85  }
86  else if(j == ((int)backwardCluster.size())-1) {
87  if (NumBackwardInVC < minValue){
88  minimalVertexCovers.clear();
89  }
90  if(NumBackwardInVC <= minValue){
91  minimalVertexCovers.push_back(std::make_pair(i,j));
92  minValue = NumBackwardInVC;
93  }
94  skip = true;
95  }
96  else if(fgreater(backwardCluster[j+1].first+forwardCluster[i+1].first + epsilon, CLowerBound)){
97  if (NumBackwardInVC+NumForwardInVC < minValue){
98  minimalVertexCovers.clear();
99  }
100  if(NumBackwardInVC+NumForwardInVC <= minValue){
101  minimalVertexCovers.push_back(std::make_pair(i,j));
102  minValue = NumBackwardInVC+NumForwardInVC;
103  }
104  skip = true;
105  }
106  }
107  }
108 
109 
110 
111  std::pair<int,int> chosenVC = computeTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster,TieBreakingPolicy);
112 
113  for (int i = 0; i <= chosenVC.first;i++){
114  auto v = forwardQueue.getNodesMapElements(kOpenReady,forwardCluster[i].first);
115  nextForward.insert( nextForward.end(), v.begin(), v.end() );
116  }
117  for (int j = 0; j <= chosenVC.second;j++){
118  auto v = backwardQueue.getNodesMapElements(kOpenReady,backwardCluster[j].first);
119  nextBackward.insert( nextBackward.end(), v.begin(), v.end() );
120  }
121 
122 
123  return true;
124  }
125  else
126  {
127  bool changed = false;
128  if (/*backwardQueue.OpenReadySize() == 0 && */backwardQueue.OpenWaitingSize() != 0)
129  {
130  const auto i4 = backwardQueue.getFirstKey(kOpenWaiting);
131  if (!fgreater(i4, CLowerBound))
132  {
133  changed = true;
134  backwardQueue.PutToReady();
135  }
136  }
137  if (/*forwardQueue.OpenReadySize() == 0 && */forwardQueue.OpenWaitingSize() != 0)
138  {
139  const auto i3 = forwardQueue.getFirstKey(kOpenWaiting);
140  if (!fgreater(i3, CLowerBound))
141  {
142  changed = true;
143  forwardQueue.PutToReady();
144  }
145  }
146  if (!changed){
147  CLowerBound = DBL_MAX;
148  if (forwardQueue.OpenWaitingSize() != 0)
149  {
150  const auto i5 = forwardQueue.getFirstKey(kOpenWaiting);
151  CLowerBound = std::min(CLowerBound, i5);
152  }
153  if (backwardQueue.OpenWaitingSize() != 0)
154  {
155  const auto i6 = backwardQueue.getFirstKey(kOpenWaiting);
156  CLowerBound = std::min(CLowerBound, i6);
157  }
158  if ((forwardQueue.OpenReadySize() != 0) && (backwardQueue.OpenReadySize() != 0))
159  CLowerBound = std::min(CLowerBound, forwardQueue.getFirstKey(kOpenReady) + backwardQueue.getFirstKey(kOpenReady) + epsilon);
160  }
161 
162 
163  }
164 
165 
166  }
167  return false;
168  }
169 
170  void Reset()
171  {
172  CLowerBound = 0;
173  forwardQueue.Reset();
174  backwardQueue.Reset();
175  }
176  double GetLowerBound() { return CLowerBound; }
177  DVCBSOpenClosed<state> forwardQueue;
178  DVCBSOpenClosed<state> backwardQueue;
179 private:
180  double CLowerBound;
181  bool tieBreakCriteria(int i,int j,int minI,int minJ,std::vector<std::pair<uint64_t,uint64_t> > forwardCluster, std::vector<std::pair<uint64_t,uint64_t> > backwardCluster){
182  int iValue = 0;
183  int jValue = 0;
184  int minIValue = 0;
185  int minJValue = 0;
186  if (i > 0){
187  iValue += forwardQueue.Lookup(forwardCluster[i].first).g;
188  }
189  if (minI > 0){
190  minIValue += forwardQueue.Lookup(forwardCluster[minI].first).g;
191  }
192  if (j > 0){
193  jValue += backwardQueue.Lookup(backwardCluster[j].first).g;
194  }
195  if (minJ > 0){
196  minJValue += backwardQueue.Lookup(backwardCluster[minJ].first).g;
197  }
198  return (std::max(iValue,jValue) > std::max(minIValue,minJValue));
199  }
200  bool tieBreakCriteria(double currentSum,double minSum){
201  return (currentSum > minSum);
202  }
203 
204  std::pair<int,int> computeTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster, int TieBreakingPolicy){
205  switch(TieBreakingPolicy) {
206  case 1 : return computeFullMaxGTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
207  case 2 : return computeSingleClusterMaxGTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
208  case 3 : return computeSingleClusterMinGTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
209  case 4 : return computeSingleClusterMinNodesTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
210  case 5 : return computeSingleClusterMaxNodesTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
211  case 6 : return computeFullMinGTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
212  case 7 : return computeMajorityMaxTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
213  case 8 : return computeMajorityMinTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
214  case 9 : return computeMajorityMinNodesTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
215  case 10: return computeSingleClusterMinNodesMaxGFTieBreaking(minimalVertexCovers,forwardCluster,backwardCluster);
216  case 11 : return computeSingleClusterCardNoMVC(minimalVertexCovers,forwardCluster,backwardCluster);
217  case 12: return computeSingleClusterMinGNoMVC(minimalVertexCovers,forwardCluster,backwardCluster);
218  default: assert(false);
219  return std::make_pair(-1,-1);
220  }
221 
222  }
223 
224  std::pair<int,int> computeFullMaxGTieBreakingOld(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
225 
226  int maxValue = -1;
227  std::pair<int,int> maxPair;
228  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
229  int maxF = 0;
230  int maxB = 0;
231  if (it->first > 0){
232  maxF = forwardCluster[it->first].first;
233  }
234  if (it->second > 0){
235  maxB = backwardCluster[it->second].first;
236  }
237  if ((maxF > maxValue) || (maxB > maxValue)){
238  maxPair = *it;
239  maxValue = std::max(maxF,maxB);
240  }
241  }
242  return maxPair;
243  }
244 
245  std::pair<int,int> computeFullMaxGTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
246 
247  int maxValue = -1;
248  std::pair<int,int> maxPair;
249  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
250  int maxF = -1;
251  int maxB = -1;
252  if (it->first >= 0){
253  maxF = forwardCluster[it->first].first;
254  }
255  if (it->second >= 0){
256  maxB = backwardCluster[it->second].first;
257  }
258  if ((maxF > maxValue) || (maxB > maxValue)){
259  maxPair = *it;
260  maxValue = std::max(maxF,maxB);
261  }
262  }
263  return maxPair;
264  }
265 
266  std::pair<int,int> computeSingleClusterMaxGTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
267  int maxF = -1;
268  int maxB = -1;
269  std::pair<int,int> maxPair;
270  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
271  if (maxF > 0 && maxB > 0){
272  break;
273  }
274  if (it->first >= 0){
275  maxF = forwardCluster[0].first;
276  }
277  if (it->second >= 0){
278  maxB = backwardCluster[0].first;
279  }
280  }
281  if (maxF >= maxB){
282  return std::make_pair(0,-1);
283  }
284  else{
285  return std::make_pair(-1,0);
286  }
287  return maxPair;
288  }
289 
290  std::pair<int,int> computeSingleClusterMinGTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
291  int maxF = INT_MAX;
292  int maxB = INT_MAX;
293  std::pair<int,int> maxPair;
294  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
295  if (maxF < INT_MAX && maxB < INT_MAX){
296  break;
297  }
298  if (it->first >= 0){
299  maxF = forwardCluster[0].first;
300  }
301  if (it->second >= 0){
302  maxB = backwardCluster[0].first;
303  }
304  }
305  if (maxF < maxB){
306  return std::make_pair(0,-1);
307  }
308  else{
309  return std::make_pair(-1,0);
310  }
311  return maxPair;
312  }
313 
314  std::pair<int,int> computeSingleClusterMinNodesTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
315  int maxF = INT_MAX;
316  int maxB = INT_MAX;
317  std::pair<int,int> maxPair;
318  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
319  if (maxF < INT_MAX && maxB < INT_MAX){
320  break;
321  }
322  if (it->first >= 0){
323  maxF = forwardCluster[0].second;
324  }
325  if (it->second >= 0){
326  maxB = backwardCluster[0].second;
327  }
328  }
329  if (maxF < maxB){
330  return std::make_pair(0,-1);
331  }
332  else{
333  return std::make_pair(-1,0);
334  }
335  return maxPair;
336  }
337 
338  std::pair<int,int> computeSingleClusterCardNoMVC(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
339  int maxF = forwardCluster[0].second;
340  int maxB = backwardCluster[0].second;
341  if (maxF < maxB){
342  return std::make_pair(0,-1);
343  }
344  else{
345  return std::make_pair(-1,0);
346  }
347  }
348 
349  std::pair<int,int> computeSingleClusterMinGNoMVC(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
350  double maxF = forwardCluster[0].first;
351  double maxB = backwardCluster[0].first;
352  if (maxF < maxB){
353  return std::make_pair(0,-1);
354  }
355  else{
356  return std::make_pair(-1,0);
357  }
358  }
359 
360  std::pair<int,int> computeSingleClusterMinNodesMaxGFTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
361  int maxF = INT_MAX;
362  int maxB = INT_MAX;
363  std::pair<int,int> maxPair;
364  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
365  if (maxF < INT_MAX && maxB < INT_MAX){
366  break;
367  }
368  if (it->first >= 0){
369  maxF = forwardCluster[0].second;
370  }
371  if (it->second >= 0){
372  maxB = backwardCluster[0].second;
373  }
374  }
375  if (maxF < maxB){
376  return std::make_pair(0,-1);
377  }
378  else if (maxF > maxB){
379  return std::make_pair(-1,0);
380  }
381  else{
382  if (forwardCluster[0].first >= backwardCluster[0].first){
383  return std::make_pair(0,-1);
384  }
385  else{
386  return std::make_pair(-1,0);
387  }
388  }
389  return maxPair;
390  }
391 
392  std::pair<int,int> computeMajorityMinNodesTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
393 
394  int forwardCount = 0;
395  int backwardCount = 0;
396  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
397  if (it->first >= 0){
398  forwardCount++;
399  }
400  if (it->second >= 0){
401  backwardCount++;
402  }
403  }
404  if (forwardCount > backwardCount){
405  return std::make_pair(0,-1);
406  }
407  else if (forwardCount < backwardCount){
408  return std::make_pair(-1,0);
409  }
410  else{
411  int maxF = forwardCluster[0].second;
412  int maxB = backwardCluster[0].second;
413  if (maxF < maxB){
414  return std::make_pair(0,-1);
415  }
416  else{
417  return std::make_pair(-1,0);
418  }
419  }
420  }
421 
422  std::pair<int,int> computeSingleClusterMaxNodesTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
423  int maxF = -1;
424  int maxB = -1;
425  std::pair<int,int> maxPair;
426  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
427  if (maxF > 0 && maxB > 0){
428  break;
429  }
430  if (it->first >= 0){
431  maxF = forwardCluster[0].second;
432  }
433  if (it->second >= 0){
434  maxB = backwardCluster[0].second;
435  }
436  }
437  if (maxF >= maxB){
438  return std::make_pair(0,-1);
439  }
440  else{
441  return std::make_pair(-1,0);
442  }
443  return maxPair;
444  }
445 
446  std::pair<int,int> computeSingleClusterMinGTieBreakingWithSub(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
447  int maxF = INT_MAX;
448  int maxB = INT_MAX;
449  int minOpenForward = 0;
450  int minOpenBackward = 0;
451  if (forwardCluster.size() > 0){
452  minOpenForward = forwardCluster[0].first;
453  }
454  if (backwardCluster.size() > 0){
455  minOpenBackward = backwardCluster[0].first;
456  }
457  std::pair<int,int> maxPair;
458  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
459  if (maxF < INT_MAX && maxB < INT_MAX){
460  break;
461  }
462  if (it->first >= 0){
463  maxF = forwardCluster[0].first;
464  }
465  if (it->second >= 0){
466  maxB = backwardCluster[0].first;
467  }
468  }
469  if (maxF - minOpenBackward < maxB - minOpenForward){
470  return std::make_pair(0,-1);
471  }
472  else{
473  return std::make_pair(-1,0);
474  }
475  return maxPair;
476  }
477 
478  std::pair<int,int> computeSingleClusterMaxGTieBreakingWithSub(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
479  int maxF = -1;
480  int maxB = -1;
481  int minOpenForward = 0;
482  int minOpenBackward = 0;
483  if (forwardCluster.size() > 0){
484  minOpenForward = forwardCluster[0].first;
485  }
486  if (backwardCluster.size() > 0){
487  minOpenBackward = backwardCluster[0].first;
488  }
489  std::pair<int,int> maxPair;
490  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
491  if (maxF > 0 && maxB > 0){
492  break;
493  }
494  if (it->first >= 0){
495  maxF = forwardCluster[0].first;
496  }
497  if (it->second >= 0){
498  maxB = backwardCluster[0].first;
499  }
500  }
501  if (maxF - minOpenBackward >= maxB - minOpenForward){
502  return std::make_pair(0,-1);
503  }
504  else{
505  return std::make_pair(-1,0);
506  }
507  return maxPair;
508  }
509 
510  std::pair<int,int> computeFullMinGTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
511 
512  int minValue = INT_MAX;
513  std::pair<int,int> minPair;
514  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
515  int maxF = INT_MAX;
516  int maxB = INT_MAX;
517  if (it->first >= 0){
518  maxF = forwardCluster[it->first].first;
519  }
520  if (it->second >= 0){
521  maxB = backwardCluster[it->second].first;
522  }
523  if ((maxF < minValue) || (maxB < minValue)){
524  minPair = *it;
525  minValue = std::min(maxF,maxB);
526  }
527  }
528  return minPair;
529  }
530 
531 
532  std::pair<int,int> computeMinGTieBreakingWithSub(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
533  int minValue = INT_MAX;
534  int minOpenForward = 0;
535  int minOpenBackward = 0;
536  if (forwardCluster.size() > 0){
537  minOpenForward = forwardCluster[0].first;
538  }
539  if (backwardCluster.size() > 0){
540  minOpenBackward = backwardCluster[0].first;
541  }
542  std::pair<int,int> minPair;
543  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
544  int maxF = INT_MAX;
545  int maxB = INT_MAX;
546  if (it->first >= 0){
547  maxF = forwardCluster[it->first].first;
548  }
549  if (it->second >= 0){
550  maxB = backwardCluster[it->second].first;
551  }
552  if ((maxF - minOpenBackward < minValue) || (maxB - minOpenForward < minValue)){
553  minPair = *it;
554  minValue = std::min(maxF- minOpenBackward,maxB - minOpenForward);
555  }
556  }
557  return minPair;
558  }
559 
560  std::pair<int,int> computeMajorityMaxTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
561 
562  int forwardCount = 0;
563  int backwardCount = 0;
564  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
565  if (it->first >= 0){
566  forwardCount++;
567  }
568  if (it->second >= 0){
569  backwardCount++;
570  }
571  }
572  if (forwardCount > backwardCount){
573  return std::make_pair(0,-1);
574  }
575  else if (forwardCount < backwardCount){
576  return std::make_pair(-1,0);
577  }
578  else{
579 
580  int fVal = forwardCluster[0].first;
581  int bVal = backwardCluster[0].first;
582  if (fVal >= bVal){
583  return std::make_pair(0,-1);
584  }
585  else{
586  return std::make_pair(-1,0);
587  }
588  }
589  }
590 
591 
592  std::pair<int,int> computeMajorityMinTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
593 
594  int forwardCount = 0;
595  int backwardCount = 0;
596  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
597  if (it->first >= 0){
598  forwardCount++;
599  }
600  if (it->second >= 0){
601  backwardCount++;
602  }
603  }
604  if (forwardCount > backwardCount){
605  return std::make_pair(0,-1);
606  }
607  else if (forwardCount < backwardCount){
608  return std::make_pair(-1,0);
609  }
610  else{
611 
612  int fVal = forwardCluster[0].first;
613  int bVal = backwardCluster[0].first;
614  if (fVal < bVal){
615  return std::make_pair(0,-1);
616  }
617  else{
618  return std::make_pair(-1,0);
619  }
620  }
621  }
622 
623  std::pair<int,int> computeMajorityMaxWithSubTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
624 
625  int forwardCount = 0;
626  int backwardCount = 0;
627  int minOpenForward = 0;
628  int minOpenBackward = 0;
629  if (forwardCluster.size() > 0){
630  minOpenForward = forwardCluster[0].first;
631  }
632  if (backwardCluster.size() > 0){
633  minOpenBackward = backwardCluster[0].first;
634  }
635  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
636  if (it->first >= 0){
637  forwardCount++;
638  }
639  if (it->second >= 0){
640  backwardCount++;
641  }
642  }
643  if (forwardCount > backwardCount){
644  return std::make_pair(0,-1);
645  }
646  else if (forwardCount < backwardCount){
647  return std::make_pair(-1,0);
648  }
649  else{
650 
651  int fVal = forwardCluster[0].first - minOpenBackward;
652  int bVal = backwardCluster[0].first - minOpenForward;
653  if (fVal >= bVal){
654  return std::make_pair(0,-1);
655  }
656  else{
657  return std::make_pair(-1,0);
658  }
659  }
660  }
661 
662  std::pair<int,int> computeMajorityMinWithSubTieBreaking(std::vector<std::pair<int,int> >& minimalVertexCovers,std::vector<std::pair<double,uint64_t> >& forwardCluster, std::vector<std::pair<double,uint64_t> >& backwardCluster){
663 
664  int forwardCount = 0;
665  int backwardCount = 0;
666  int minOpenForward = 0;
667  int minOpenBackward = 0;
668  if (forwardCluster.size() > 0){
669  minOpenForward = forwardCluster[0].first;
670  }
671  if (backwardCluster.size() > 0){
672  minOpenBackward = backwardCluster[0].first;
673  }
674  for(std::vector<std::pair<int,int> >::iterator it = minimalVertexCovers.begin(); it != minimalVertexCovers.end(); ++it) {
675  if (it->first >= 0){
676  forwardCount++;
677  }
678  if (it->second >= 0){
679  backwardCount++;
680  }
681  }
682  if (forwardCount > backwardCount){
683  return std::make_pair(0,-1);
684  }
685  else if (forwardCount < backwardCount){
686  return std::make_pair(-1,0);
687  }
688  else{
689 
690  int fVal = forwardCluster[0].first - minOpenBackward;
691  int bVal = backwardCluster[0].first - minOpenForward;
692  if (fVal < bVal){
693  return std::make_pair(0,-1);
694  }
695  else{
696  return std::make_pair(-1,0);
697  }
698  }
699  }
700 
701 };
702 
703 #endif /* DVCBSQueue_h */
DVCBSOpenClosed< state >
kOpenWaiting
@ kOpenWaiting
Definition: BDOpenClosed.h:24
DVCBSQueue::computeMinGTieBreakingWithSub
std::pair< int, int > computeMinGTieBreakingWithSub(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:532
DVCBSQueue::computeSingleClusterMaxGTieBreakingWithSub
std::pair< int, int > computeSingleClusterMaxGTieBreakingWithSub(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:478
DVCBSQueue::computeMajorityMinNodesTieBreaking
std::pair< int, int > computeMajorityMinNodesTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:392
min
double min(double a, double b)
Definition: FPUtil.h:35
DVCBSQueue
Definition: DVCBSQueue.h:21
DVCBSQueue.h
DVCBSOpenClosed::getNodesMapElements
std::set< uint64_t > getNodesMapElements(stateLocation whichQueue, double key)
Definition: DVCBSOpenClosed.h:70
kOpenReady
@ kOpenReady
Definition: BDOpenClosed.h:23
DVCBSOpenClosed::PutToReady
void PutToReady()
Definition: DVCBSOpenClosed.h:288
DVCBSQueue::computeTieBreaking
std::pair< int, int > computeTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster, int TieBreakingPolicy)
Definition: DVCBSQueue.h:204
DVCBSQueue::computeMajorityMaxTieBreaking
std::pair< int, int > computeMajorityMaxTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:560
DVCBSOpenClosed::OpenSize
size_t OpenSize() const
Definition: DVCBSOpenClosed.h:66
DVCBSQueue::getVertexCover
bool getVertexCover(std::vector< uint64_t > &nextForward, std::vector< uint64_t > &nextBackward, int TieBreakingPolicy)
Definition: DVCBSQueue.h:23
DVCBSQueue::computeSingleClusterMinGNoMVC
std::pair< int, int > computeSingleClusterMinGNoMVC(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:349
DVCBSOpenClosed::OpenReadySize
size_t OpenReadySize() const
Definition: DVCBSOpenClosed.h:64
DVCBSQueue::computeSingleClusterMaxNodesTieBreaking
std::pair< int, int > computeSingleClusterMaxNodesTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:422
DVCBSQueue::computeSingleClusterCardNoMVC
std::pair< int, int > computeSingleClusterCardNoMVC(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:338
DVCBSQueue::computeFullMaxGTieBreaking
std::pair< int, int > computeFullMaxGTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:245
TOLERANCE
static const double TOLERANCE
Definition: FPUtil.h:26
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
DVCBSQueue::tieBreakCriteria
bool tieBreakCriteria(int i, int j, int minI, int minJ, std::vector< std::pair< uint64_t, uint64_t > > forwardCluster, std::vector< std::pair< uint64_t, uint64_t > > backwardCluster)
Definition: DVCBSQueue.h:181
DVCBSOpenClosed::getNodesMapBegin
std::map< double, std::set< uint64_t > >::iterator getNodesMapBegin(stateLocation whichQueue)
Definition: DVCBSOpenClosed.h:68
DVCBSOpenClosed.h
DVCBSQueue::computeMajorityMinWithSubTieBreaking
std::pair< int, int > computeMajorityMinWithSubTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:662
DVCBSQueue::computeFullMaxGTieBreakingOld
std::pair< int, int > computeFullMaxGTieBreakingOld(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:224
DVCBSOpenClosed::getFirstKey
double getFirstKey(stateLocation whichQueue) const
Definition: DVCBSOpenClosed.h:54
DVCBSQueue::computeSingleClusterMinGTieBreakingWithSub
std::pair< int, int > computeSingleClusterMinGTieBreakingWithSub(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:446
DVCBSQueue::computeMajorityMaxWithSubTieBreaking
std::pair< int, int > computeMajorityMaxWithSubTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:623
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
DVCBSQueue::computeFullMinGTieBreaking
std::pair< int, int > computeFullMinGTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:510
max
#define max(a, b)
Definition: MinimalSectorAbstraction.cpp:40
DVCBSQueue::forwardQueue
DVCBSOpenClosed< state > forwardQueue
Definition: DVCBSQueue.h:177
DVCBSOpenClosed::getNodesMapEnd
std::map< double, std::set< uint64_t > >::iterator getNodesMapEnd(stateLocation whichQueue)
Definition: DVCBSOpenClosed.h:69
DVCBSOpenClosed::Reset
void Reset()
Remove all objects from queue.
Definition: DVCBSOpenClosed.h:116
DVCBSQueue::backwardQueue
DVCBSOpenClosed< state > backwardQueue
Definition: DVCBSQueue.h:178
DVCBSQueue::tieBreakCriteria
bool tieBreakCriteria(double currentSum, double minSum)
Definition: DVCBSQueue.h:200
DVCBSQueue::CLowerBound
double CLowerBound
Definition: DVCBSQueue.h:180
DVCBSQueue::computeSingleClusterMinNodesMaxGFTieBreaking
std::pair< int, int > computeSingleClusterMinNodesMaxGFTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:360
DVCBSQueue::computeSingleClusterMinGTieBreaking
std::pair< int, int > computeSingleClusterMinGTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:290
DVCBSQueue::computeSingleClusterMaxGTieBreaking
std::pair< int, int > computeSingleClusterMaxGTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:266
DVCBSOpenClosed::Lookup
stateLocation Lookup(uint64_t hashKey, uint64_t &objKey) const
Definition: DVCBSOpenClosed.h:265
DVCBSOpenClosed::OpenWaitingSize
size_t OpenWaitingSize() const
Definition: DVCBSOpenClosed.h:65
DVCBSQueue::computeMajorityMinTieBreaking
std::pair< int, int > computeMajorityMinTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:592
DVCBSQueue::Reset
void Reset()
Definition: DVCBSQueue.h:170
DVCBSQueue::computeSingleClusterMinNodesTieBreaking
std::pair< int, int > computeSingleClusterMinNodesTieBreaking(std::vector< std::pair< int, int > > &minimalVertexCovers, std::vector< std::pair< double, uint64_t > > &forwardCluster, std::vector< std::pair< double, uint64_t > > &backwardCluster)
Definition: DVCBSQueue.h:314
DVCBSQueue::GetLowerBound
double GetLowerBound()
Definition: DVCBSQueue.h:176
Generated by   doxygen 1.8.17