00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00016
00017
00018
00019
00021
00022 #include "EdgeProjection.hh"
00023 #include <cstdlib>
00024
00025 #include "abacus/master.h"
00026 #include "StableSetMaster.hh"
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043 EdgeProjection::EdgeProjection(vector< vector<int> > *graph):
00044 currentNode(NULL)
00045 {
00046
00047 int i, j;
00048 int node;
00049
00050
00051 graphSize = graph->size();
00052
00053
00054 adjacentListSize = new int[graphSize];
00055
00056
00057 lowerAdjacentMatrix.resize(graphSize - 1);
00058 for (i=1; i<graphSize; i++) {
00059 lowerAdjacentMatrix[i-1].resize(i,0);
00060 }
00061
00062
00063 for (i=0; i<graphSize; i++) {
00064
00065 adjacentListSize[i] = (*graph)[i].size();
00066 for (j=0; j<adjacentListSize[i]; j++) {
00067 node = (*graph)[i][j];
00068
00069 if (i > node) {
00070 lowerAdjacentMatrix[i-1][node] = 1;
00071 }
00072 }
00073 }
00074
00075
00076
00077
00078
00079
00080
00081
00082 srand(1);
00083
00084
00085
00086
00087 }
00088
00089
00090
00091
00092
00093 EdgeProjection::~EdgeProjection() {
00094
00095 delete []adjacentListSize;
00096
00097 if (!lhs.empty()) {
00098
00099 for (int i=lhs.size()-1; i>=0; i--) {
00100 delete lhs[i];
00101 lhs[i] = NULL;
00102 }
00103 lhs.clear();
00104 }
00105
00106 }
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116 int EdgeProjection::separate(double *lpValue) {
00117
00118 int i;
00119 int numCut;
00120 int reducedGraphSize = graphSize;
00121 vector< vector<int> > theLhs;
00122 vector<int> theRhs;
00123 bool condition = true;
00124 bool separate = true;
00125
00126
00127
00128
00129 const int ENOUGH_INEQUALITIES = (int) .2 * graphSize;
00130
00131
00132
00133
00134 for (i=lhs.size()-1; i>=0; i--) {
00135 delete lhs[i];
00136 lhs[i] = NULL;
00137 }
00138 lhs.clear();
00139 rhs.clear();
00140 slack.clear();
00141
00142
00143
00144
00145
00146
00147 while (condition) {
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157 bool edgeFound = edgeSelection(lpValue);
00158
00159 if (!edgeFound) {
00160 break;
00161 }
00162
00163
00164
00165
00166 projection();
00167
00168
00169
00170
00171 reducedGraphSize = 0;
00172 for (i=0; i<graphSize; i++) {
00173 if (adjacentListSize[i] != 0) {
00174 reducedGraphSize++;
00175 }
00176 }
00177 if (reducedGraphSize <= 5) {
00178 separate = false;
00179 condition = false;
00180 }
00181
00182
00183
00184
00185 if (separate) {
00186
00187
00188
00189
00190
00191 numCut = separation(lpValue, &theLhs, &theRhs);
00192
00193
00194
00195
00196 if (numCut) {
00197
00198
00199
00200 lifting(&theLhs, &theRhs);
00201
00202
00203
00204
00205 storeInequalities(&theLhs, &theRhs, lpValue);
00206
00207
00208
00209
00210 if (lhs.size() >= ENOUGH_INEQUALITIES) {
00211 condition = false;
00212 }
00213 }
00214 }
00215
00216
00217
00218
00219 edge[0] = edge[1] = -1;
00220 deleteNodes.clear();
00221 for (i=deleteEdges.size()-1; i>=0; i--) {
00222 delete [] deleteEdges[i];
00223 }
00224 deleteEdges.clear();
00225 theLhs.clear();
00226 theRhs.clear();
00227
00228 }
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238 cleanUp();
00239
00240
00241 return 0;
00242
00243 }
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253 int EdgeProjection::computeLargeInequality(double *lpValue,
00254 StableSetMaster *theMaster) {
00255
00256 int i;
00257 int reducedGraphSize = graphSize;
00258 bool condition = true;
00259 vector<int> theLhs;
00260 int theRhs;
00261
00262
00263
00264
00265 const static int MAX_SIZE_OF_GRAPH = 45;
00266
00267
00268
00269
00270 for (i=lhs.size()-1; i>=0; i--) {
00271 delete lhs[i];
00272 lhs[i] = NULL;
00273 }
00274 lhs.clear();
00275 rhs.clear();
00276 slack.clear();
00277
00278
00279
00280
00281
00282 while (condition) {
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292 bool edgeFound = edgeSelection(lpValue);
00293
00294 if (!edgeFound) {
00295 break;
00296 }
00297
00298
00299
00300
00301 projection();
00302
00303
00304
00305
00306 reducedGraphSize = 0;
00307 for(i=0; i<graphSize; i++) {
00308 if (adjacentListSize[i] != 0) {
00309 reducedGraphSize++;
00310 }
00311 }
00312
00313
00314
00315
00316 if (reducedGraphSize <= MAX_SIZE_OF_GRAPH) {
00317
00318
00319
00320
00321 solveStableSet(&theLhs, theRhs, theMaster);
00322
00323
00324
00325
00326 liftAndStore(&theLhs, theRhs);
00327
00328
00329
00330
00331 condition = false;
00332 }
00333
00334
00335
00336
00337 edge[0] = edge[1] = -1;
00338 deleteNodes.clear();
00339 for (i=deleteEdges.size()-1; i>=0; i--) {
00340 delete [] deleteEdges[i];
00341 }
00342 deleteEdges.clear();
00343 theLhs.clear();
00344
00345 }
00346
00347
00348
00349
00350 cleanUp();
00351
00352
00353 return 0;
00354
00355 }
00356
00357
00358
00359
00360
00361
00362
00363 vector< vector<int>* >* EdgeProjection::getLHS() {
00364
00365 if (lhs.empty()) {
00366 return NULL;
00367 }
00368 else {
00369 return &lhs;
00370 }
00371 }
00372
00373
00374
00375
00376
00377
00378
00379 vector<int>* EdgeProjection::getRHS() {
00380 return &rhs;
00381 }
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393
00394
00395
00396
00397
00398 bool EdgeProjection::edgeSelection(double *lpValue) {
00399
00400 int i, j, k;
00401 int size;
00402
00403
00404
00405
00406 int stack;
00407 int startNodeOne;
00408 int startNodeTwo;
00409 int nodeOne;
00410 int nodeTwo;
00411 double weight;
00412 double bestWeight = 0;
00413
00414
00415
00416
00417
00418
00419
00420
00421 static const double ACCEPT_EDGE = .99;
00422
00423
00424 static const double NOT_ACCEPT_EDGE = .2;
00425
00426
00427
00428 startNodeOne = getRandomNumber(graphSize);
00429 startNodeTwo = getRandomNumber(graphSize);
00430 while (startNodeOne == startNodeTwo) {
00431 startNodeTwo = getRandomNumber(graphSize);
00432 }
00433
00434 if (startNodeOne < startNodeTwo) {
00435 stack = startNodeOne;
00436 startNodeOne = startNodeTwo;
00437 startNodeTwo = stack;
00438 }
00439
00440 nodeOne = startNodeOne;
00441 nodeTwo = startNodeTwo;
00442 do {
00443
00444 if (lowerAdjacentMatrix[nodeOne-1][nodeTwo]) {
00445
00446 weight = lpValue[nodeOne] + lpValue[nodeTwo];
00447
00448 if (weight > bestWeight) {
00449
00450 if (weight > ACCEPT_EDGE) {
00451
00452 bestWeight = weight;
00453 edge[0] = nodeOne;
00454 edge[1] = nodeTwo;
00455 break;
00456 }
00457 bestWeight = weight;
00458 edge[0] = nodeOne;
00459 edge[1] = nodeTwo;
00460 }
00461 }
00462
00463
00464 nodeTwo++;
00465 if (nodeTwo == nodeOne) {
00466 nodeOne++;
00467 nodeTwo = 0;
00468 if (nodeOne == graphSize) {
00469 nodeOne = 1;
00470 }
00471 }
00472 } while ((nodeOne != startNodeOne) || (nodeTwo != startNodeTwo));
00473
00474
00475 if (bestWeight < NOT_ACCEPT_EDGE) {
00476 return 0;
00477 }
00478
00479
00480
00481
00482
00483 int index = 0;
00484 if (adjacentListSize[edge[0]] > adjacentListSize[edge[1]]) {
00485 index = 1;
00486 }
00487
00488
00489
00490 vector<int> neighborhood;
00491 getNeighborhood(edge[index], &neighborhood);
00492
00493
00494 i = 0;
00495 size = neighborhood.size();
00496 while (i < size) {
00497 if (neighborhood[i] == edge[(index+1)%2]) {
00498 neighborhood.erase(neighborhood.begin()+i);
00499 size--;
00500 break;
00501 }
00502 i++;
00503 }
00504
00505
00506 if(i == size+1) {
00507 cout << "ERROR" << endl;
00508 exit(1);
00509 }
00510
00511 bool clique = true;
00512 for (i=0; i<size-1; i++) {
00513 for (j=i+1; j<size; j++) {
00514 if (!lowerAdjacentMatrix[neighborhood[j]-1][neighborhood[i]]) {
00515 clique = false;
00516 break;
00517 }
00518 }
00519 if (!clique) {
00520 break;
00521 }
00522 }
00523
00524 if (clique) {
00525
00526 for (i=0; i<size; i++) {
00527 if (neighborhood[i] > edge[(index+1)%2]) {
00528 if (lowerAdjacentMatrix[neighborhood[i]-1][edge[(index+1)%2]]) {
00529 deleteNodes.push_back(neighborhood[i]);
00530 }
00531 }
00532 else {
00533 if (lowerAdjacentMatrix[edge[(index+1)%2]-1][neighborhood[i]]) {
00534 deleteNodes.push_back(neighborhood[i]);
00535 }
00536 }
00537 }
00538 }
00539 else {
00540
00541
00542
00543
00544 vector< vector<int> > adjacentList(size);
00545 for (i=0; i<size-1; i++) {
00546 for (j=i+1; j<size; j++) {
00547 if (lowerAdjacentMatrix[neighborhood[j]-1][neighborhood[i]]) {
00548 adjacentList[i].push_back(j);
00549 adjacentList[j].push_back(i);
00550 }
00551 }
00552 }
00553
00554
00555 vector<int> *maxClique;
00556
00557 maxClique = computeMaximalClique(&adjacentList, &neighborhood);
00558
00559 if (maxClique == NULL) {
00560 cout << "ERROR with maximal clique computation." << endl;
00561 exit(1);
00562 }
00563
00564
00565 int cliqueSize = maxClique->size();
00566 for (i=0; i<cliqueSize; i++) {
00567 (*maxClique)[i] = neighborhood[(*maxClique)[i]];
00568 }
00569 sort(maxClique->begin(), maxClique->end());
00570 deleteEdges.resize(size - cliqueSize);
00571 int edgesCnt = 0;
00572 int *anEdge;
00573 j = 0;
00574 for (i=0; i<size; i++) {
00575
00576
00577 while (j < cliqueSize) {
00578 if ((*maxClique)[j] >= neighborhood[i]) {
00579 if ((*maxClique)[j] == neighborhood[i]) {
00580 if (neighborhood[i] > edge[(index+1)%2]) {
00581 if (lowerAdjacentMatrix[neighborhood[i]-1][edge[(index+1)%2]]) {
00582 deleteNodes.push_back(neighborhood[i]);
00583 }
00584 }
00585 else {
00586 if (lowerAdjacentMatrix[edge[(index+1)%2]-1][neighborhood[i]]) {
00587 deleteNodes.push_back(neighborhood[i]);
00588 }
00589 }
00590 }
00591 else {
00592 anEdge = new int[2];
00593 anEdge[0] = edge[index];
00594 anEdge[1] = neighborhood[i];
00595 deleteEdges[edgesCnt++] = anEdge;
00596 }
00597 break;
00598 }
00599 j++;
00600 }
00601 if (j == cliqueSize) {
00602 anEdge = new int[2];
00603 anEdge[0] = edge[index];
00604 anEdge[1] = neighborhood[i];
00605 deleteEdges[edgesCnt++] = anEdge;
00606 }
00607 }
00608
00609
00610 maxClique->clear();
00611 delete maxClique;
00612 }
00613
00614
00615 return 1;
00616
00617 }
00618
00619
00620
00621
00622
00623
00624
00625
00626 void EdgeProjection::projection() {
00627
00628
00629 vector<int*> falseEdges;
00630
00631
00632
00633
00634
00635
00636 updateGraph();
00637
00638
00639
00640
00641 computeFalseEdges(&falseEdges);
00642
00643
00644
00645
00646
00647 updateGraph(&falseEdges);
00648
00649
00650
00651
00652 addNode(&falseEdges);
00653
00654
00655 for (int i=falseEdges.size()-1; i>=0; i--) {
00656 delete [] falseEdges[i];
00657 falseEdges[i] = NULL;
00658 }
00659 falseEdges.clear();
00660
00661 }
00662
00663
00664
00665
00666
00667
00668
00669
00670
00671
00672
00673 int EdgeProjection::separation(double *lpValue, vector< vector<int> > *theLhs,
00674 vector<int> *theRhs) {
00675
00676 int i;
00677 int size;
00678
00679
00680
00681
00682 vector< vector<int> > reducedGraph;
00683 getReducedGraph(&reducedGraph);
00684
00685
00686
00687
00688 size = reducedGraph.size();
00689 double theLPValue[size];
00690 for (i=0; i<size; i++) {
00691 theLPValue[i] = lpValue[translator[i]];
00692 }
00693
00694
00695
00696
00697 int numberOfCuts = cliqueSeparation(&reducedGraph, theLPValue, theLhs);
00698
00699
00700
00701
00702 for (i=0; i<numberOfCuts; i++) {
00703 theRhs->push_back(1);
00704 }
00705
00706 return theLhs->size();
00707
00708 }
00709
00710
00711
00712
00713
00714
00715
00716
00717 void EdgeProjection::lifting(vector< vector<int> > *theLhs,
00718 vector<int> *theRhs) {
00719
00720 int i, j, k;
00721 int size;
00722 int nodeOne;
00723 int nodeTwo;
00724 int stack;
00725 int n_inequalities = theLhs->size();
00726 vector<int*>* theFalseEdges;
00727 vector<int>* theDeletedNodes;
00728 int deletedNodesSize;
00729 ProjectionNode* aNode;
00730
00731
00732
00733
00734 for (i=0; i<n_inequalities; i++) {
00735 size = (*theLhs)[i].size();
00736 for (j=0; j<size; j++) {
00737 (*theLhs)[i][j] = translator[(*theLhs)[i][j]];
00738 }
00739 }
00740
00741
00742
00743
00744
00745
00746 aNode = currentNode;
00747
00748 while (aNode != NULL) {
00749
00750 theFalseEdges = aNode->getFalseEdges();
00751
00752
00753 for (i=0; i<n_inequalities; i++) {
00754 j = 0;
00755 size = (*theLhs)[i].size();
00756 while (j < theFalseEdges->size()) {
00757 nodeOne = (*theFalseEdges)[j][0];
00758 nodeTwo = (*theFalseEdges)[j][1];
00759 j++;
00760
00761 if (nodeOne > nodeTwo) {
00762 stack = nodeOne;
00763 nodeOne = nodeTwo;
00764 nodeTwo = stack;
00765 }
00766 k = 0;
00767 while (k < size) {
00768 if( (*theLhs)[i][k] >= nodeOne ) {
00769 break;
00770 }
00771 k++;
00772 }
00773 if (k == size) {
00774
00775 continue;
00776 }
00777 if ((*theLhs)[i][k] != nodeOne) {
00778
00779 continue;
00780 }
00781 k++;
00782 while (k < size) {
00783 if( (*theLhs)[i][k] >= nodeTwo ) {
00784 break;
00785 }
00786 k++;
00787 }
00788 if (k == size) {
00789
00790 continue;
00791 }
00792 if ((*theLhs)[i][k] != nodeTwo) {
00793
00794 continue;
00795 }
00796
00797
00798
00799
00800
00801
00802 theDeletedNodes = aNode->getDeletedNodes();
00803 deletedNodesSize = theDeletedNodes->size();
00804 for (k=0; k<deletedNodesSize; k++) {
00805 (*theLhs)[i].push_back((*theDeletedNodes)[k]);
00806 }
00807
00808 (*theLhs)[i].push_back(aNode->getEdge(0));
00809 (*theLhs)[i].push_back(aNode->getEdge(1));
00810
00811 sort((*theLhs)[i].begin(), (*theLhs)[i].end());
00812
00813 (*theRhs)[i] += 1;
00814
00815
00816
00817
00818 break;
00819 }
00820 }
00821
00822 aNode = aNode->getPreviousNode();
00823 }
00824
00825 }
00826
00827
00828
00829
00830
00831
00832
00833
00834 void EdgeProjection::storeInequalities(vector< vector<int> > *theLhs,
00835 vector<int> *theRhs, double* lpValue) {
00836
00837 int i, j, k;
00838 int cnt = lhs.size();
00839 int size;
00840 int numberOfInequalities = theLhs->size();
00841 double value;
00842 vector<int> *inequality;
00843 bool newOne;
00844
00845
00846
00847
00848 static const double MIN_VIOLATION = .000001;
00849
00850
00851
00852
00853
00854 lhs.resize(numberOfInequalities + cnt);
00855 rhs.resize(numberOfInequalities + cnt);
00856 slack.resize(numberOfInequalities + cnt);
00857
00858
00859
00860
00861 for (i=0; i<numberOfInequalities; i++) {
00862 value = 0;
00863 size = (*theLhs)[i].size();
00864 for (j=0; j<size; j++) {
00865 value += lpValue[(*theLhs)[i][j]];
00866 }
00867
00868 if (value > ((*theRhs)[i] + MIN_VIOLATION)) {
00869
00870
00871
00872
00873 newOne = true;
00874 for (j=0; j<cnt; j++) {
00875 if ((*theLhs)[i].size() != lhs[j]->size()) {
00876 continue;
00877 }
00878 k = 0;
00879 while (k < lhs[j]->size()) {
00880 if ((*theLhs)[i][k] != (*lhs[j])[k]) {
00881 break;
00882 }
00883 k++;
00884 }
00885 if (k == lhs[j]->size()) {
00886 newOne = false;
00887 if (rhs[j] > (*theRhs)[i]) {
00888 rhs[j] = (*theRhs)[i];
00889 }
00890 break;
00891 }
00892 }
00893
00894
00895
00896
00897 if (newOne) {
00898 inequality = new vector<int>;
00899 inequality->resize(size);
00900 for (j=0; j<size; j++) {
00901 (*inequality)[j] = (*theLhs)[i][j];
00902 }
00903 lhs[cnt] = inequality;
00904 rhs[cnt] = (*theRhs)[i];
00905 slack[cnt] = value;
00906 cnt++;
00907 }
00908 }
00909 }
00910
00911
00912 lhs.resize(cnt);
00913 rhs.resize(cnt);
00914 slack.resize(cnt);
00915
00916 }
00917
00918
00919
00920
00921
00922
00923 struct InequalitiesAndWeights {
00924 int iinequality;
00925 double weight;
00926 };
00927
00928
00929
00930
00931
00932
00933 bool operator<(const InequalitiesAndWeights &a, const InequalitiesAndWeights &b) {
00934 return a.weight < b.weight;
00935 }
00936
00937
00938
00939
00940
00941
00942
00943 void EdgeProjection::cleanUpInequalities(double *lpValue) {
00944
00945
00946
00947
00948 const int MIN_NUMBER = 10;
00949 const int MAX_NUMBER = graphSize;
00950 const int MULTIPLICATOR = 10;
00951
00952 int size = lhs.empty() ? 0 : lhs.size();
00953
00954
00955
00956
00957
00958 if (size >= MIN_NUMBER) {
00959
00960 int i;
00961 int selectionNumber;
00962 double m;
00963 double c;
00964 vector<InequalitiesAndWeights> inequalities;
00965
00966
00967
00968
00969 for (i=0; i<size; i++) {
00970 InequalitiesAndWeights a;
00971 a.iinequality = i;
00972 a.weight = ( (double)(lhs[i]->size()) / rhs[i] ) * slack[i];
00973 inequalities.push_back(a);
00974 }
00975
00976
00977
00978
00979 sort(inequalities.begin(), inequalities.end());
00980
00981
00982
00983
00984 if (size >= (MAX_NUMBER * MULTIPLICATOR)) {
00985 selectionNumber = MAX_NUMBER;
00986 }
00987 else {
00988
00989 m = ((double)(MAX_NUMBER - MIN_NUMBER)) / (MAX_NUMBER * MULTIPLICATOR - MIN_NUMBER);
00990 c = MIN_NUMBER - m * MIN_NUMBER;
00991 selectionNumber = (int) (m * size + c);
00992 }
00993
00994
00995
00996 vector< vector<int>* > lhsCopy(selectionNumber);
00997 vector< int > rhsCopy(selectionNumber);
00998 for (i=0; i<selectionNumber; i++) {
00999 lhsCopy[i] = lhs[inequalities[i].iinequality];
01000 rhsCopy[i] = rhs[inequalities[i].iinequality];
01001 }
01002
01003 lhs.clear();
01004 rhs.clear();
01005 lhs = lhsCopy;
01006 rhs = rhsCopy;
01007 }
01008
01009 }
01010
01011
01012
01013
01014
01015
01016
01017
01018 void EdgeProjection::checkStrongProjectability() {
01019
01020 int i, j, k, l, m;
01021 int size;
01022 int node;
01023 int nodeU;
01024
01025 int nodeV;
01026
01027 vector<int> neighborhoodU;
01028 int sizeU;
01029 vector<int> neighborhoodV;
01030 int sizeV;
01031 vector<int> nUwnV;
01032 int sizeUV;
01033 vector<int> nVwnU;
01034 int sizeVU;
01035 vector<int> nUcutnV;
01036 int sizeUCV;
01037 bool clique;
01038 int *projectableEdge;
01039 bool bull = false;
01040 bool diamond = false;
01041
01042
01043
01044
01045 for (i=1; i<graphSize; i++) {
01046 for (j=0; j<i; j++) {
01047
01048 if (!lowerAdjacentMatrix[i-1][j]) {
01049
01050
01051 continue;
01052 }
01053
01054
01055
01056
01057
01058
01059
01060
01061
01062
01063
01064 nodeU = i;
01065 nodeV = j;
01066
01067 getNeighborhood(nodeU, &neighborhoodU);
01068 getNeighborhood(nodeV, &neighborhoodV);
01069 sizeU = neighborhoodU.size();
01070 sizeV = neighborhoodV.size();
01071
01072
01073
01074
01075
01076
01077
01078
01079
01080
01081 for (k=0; k<sizeU; k++) {
01082 node = neighborhoodU[k];
01083
01084 l = 0;
01085 while (l < sizeV) {
01086 if (node <= neighborhoodV[l]) {
01087 break;
01088 }
01089 l++;
01090 }
01091 if (l == sizeV) {
01092 break;
01093 }
01094 if (node == neighborhoodV[l]) {
01095
01096
01097
01098 size = nUcutnV.empty() ? 0 : nUcutnV.size();
01099 for (m=0; m<size; m++) {
01100
01101
01102 if (!lowerAdjacentMatrix[node-1][nUcutnV[m]]) {
01103
01104 diamond = true;
01105 break;
01106 }
01107 }
01108 if (diamond) {
01109 break;
01110 }
01111
01112
01113
01114 nUcutnV.push_back(node);
01115 }
01116 }
01117
01118 if (diamond) {
01119
01120
01121 diamond = false;
01122 nUcutnV.clear();
01123 neighborhoodU.clear();
01124 neighborhoodV.clear();
01125
01126
01127 continue;
01128 }
01129
01130 sizeUCV = !nUcutnV.empty() ? nUcutnV.size() : 0;
01131
01132
01133
01134
01135
01136
01137
01138
01139
01140
01141
01142
01143
01144
01145
01146
01147 l = 0;
01148 for (k=0; k<sizeU; k++) {
01149 node = neighborhoodU[k];
01150 if (node == nodeV) {
01151
01152 continue;
01153 }
01154
01155 while (l < sizeV) {
01156 if (node <= neighborhoodV[l]) {
01157 break;
01158 }
01159 l++;
01160 }
01161 if (l == sizeV) {
01162 nUwnV.push_back(node);
01163 continue;
01164 }
01165 if (node != neighborhoodV[l]) {
01166 nUwnV.push_back(node);
01167 }
01168 }
01169
01170 sizeUV = !nUwnV.empty() ? nUwnV.size() : 0;
01171
01172 clique = true;
01173 if (sizeUV) {
01174
01175 for (k=0; k<sizeUV-1; k++) {
01176 for (l=k+1; l<sizeUV; l++) {
01177 if (!lowerAdjacentMatrix[nUwnV[l]-1][nUwnV[k]]) {
01178 clique = false;
01179 break;
01180 }
01181 }
01182 if (!clique) {
01183 break;
01184 }
01185 }
01186 }
01187
01188
01189
01190
01191
01192 l = 0;
01193 for (k=0; k<sizeV; k++) {
01194 node = neighborhoodV[k];
01195 if (node == nodeU) {
01196
01197 continue;
01198 }
01199
01200 while (l < sizeU) {
01201 if (node <= neighborhoodU[l]) {
01202 break;
01203 }
01204 l++;
01205 }
01206 if (l == sizeU) {
01207 nVwnU.push_back(node);
01208 continue;
01209 }
01210 if (node != neighborhoodU[l]) {
01211 nVwnU.push_back(node);
01212 }
01213 }
01214
01215 sizeVU = !nVwnU.empty() ? nVwnU.size() : 0;
01216
01217
01218
01219
01220 if (!clique) {
01221 clique = true;
01222 if (sizeVU) {
01223
01224 for (k=0; k<sizeVU-1; k++) {
01225 for (l=k+1; l<sizeVU; l++) {
01226 if (!lowerAdjacentMatrix[nVwnU[l]-1][nVwnU[k]]) {
01227 clique = false;
01228 break;
01229 }
01230 }
01231 if (!clique) {
01232 break;
01233 }
01234 }
01235 if (!clique) {
01236
01237
01238
01239
01240
01241 nUwnV.clear();
01242 nVwnU.clear();
01243 nUcutnV.clear();
01244 neighborhoodU.clear();
01245 neighborhoodV.clear();
01246
01247
01248 continue;
01249 }
01250 }
01251 }
01252
01253
01254
01255
01256
01257
01258
01259
01260
01261
01262
01263
01264
01265
01266
01267
01268
01269
01270 if (!nUcutnV.empty() && !nUwnV.empty() && !nVwnU.empty()) {
01271
01272 for (k=0; k<sizeUV; k++) {
01273 for (l=0; l<sizeVU; l++) {
01274 for (m=0; m<sizeUCV; m++) {
01275
01276 if (nUwnV[k] > nVwnU[l]) {
01277 if (lowerAdjacentMatrix[nUwnV[k]-1][nVwnU[l]]) {
01278 break;
01279 }
01280 }
01281 else {
01282 if (lowerAdjacentMatrix[nVwnU[k]-1][nUwnV[l]]) {
01283 break;
01284 }
01285 }
01286
01287 if (nUwnV[k] > nUcutnV[m]) {
01288 if (lowerAdjacentMatrix[nUwnV[k]-1][nUcutnV[m]]) {
01289 break;
01290 }
01291 }
01292 else {
01293 if (lowerAdjacentMatrix[nUcutnV[m]-1][nUwnV[k]]) {
01294 break;
01295 }
01296 }
01297
01298 if (nVwnU[l] > nUcutnV[m]) {
01299 if (lowerAdjacentMatrix[nVwnU[l]-1][nUcutnV[m]]) {
01300 break;
01301 }
01302 }
01303 else {
01304 if (lowerAdjacentMatrix[nUcutnV[m]-1][nVwnU[l]]) {
01305 break;
01306 }
01307 }
01308 if (m == (sizeUCV - 1)) {
01309 bull = true;
01310 break;
01311 }
01312 }
01313 if (bull) {
01314 break;
01315 }
01316 }
01317 if (bull) {
01318 break;
01319 }
01320 }
01321 if (bull) {
01322
01323
01324
01325
01326 bull = false;
01327 nUwnV.clear();
01328 nVwnU.clear();
01329 nUcutnV.clear();
01330 neighborhoodU.clear();
01331 neighborhoodV.clear();
01332
01333
01334 continue;
01335 }
01336 }
01337
01338
01339
01340
01341
01342 projectableEdge = new int[2];
01343 projectableEdge[0] = nodeU;
01344 projectableEdge[1] = nodeV;
01345 projectable.push_back(projectableEdge);
01346
01347
01348 nUwnV.clear();
01349 nVwnU.clear();
01350 nUcutnV.clear();
01351 neighborhoodU.clear();
01352 neighborhoodV.clear();
01353
01354 }
01355 }
01356
01357 }
01358
01359
01360
01361
01362
01363
01364
01365
01366 vector<int>* EdgeProjection::computeMaximalClique(
01367 vector< vector<int> > *theAdjacentList, vector<int> *theTranslator) {
01368
01369 int i;
01370 int cnt = 0;
01371 int size = theAdjacentList->size();
01372 vector<int> clique(2);
01373 vector<int> adjacentNodes;
01374 vector<int> *maxClique;
01375
01376 maxClique = new vector<int>;
01377 int maxCliqueSize = 0;
01378 bool found;
01379
01380
01381
01382
01383 const int MAX_ITER = size * 2;
01384
01385
01386
01387
01388
01389 if (theAdjacentList->empty()) {
01390 return NULL;
01391 }
01392
01393 for (i=0; i<size; i++) {
01394 cnt += (*theAdjacentList)[i].size();
01395 if (cnt >= 1) {
01396 break;
01397 }
01398 }
01399 if (cnt < 1) {
01400 maxClique->push_back(0);
01401 return maxClique;
01402 }
01403
01404
01405
01406
01407 cnt = 0;
01408 while (cnt < MAX_ITER) {
01409
01410
01411
01412
01413 found = false;
01414 while (!found) {
01415 clique[0] = getRandomNumber(size);
01416 clique[1] = getRandomNumber(size);
01417 if (clique[0] != clique[1]) {
01418 if (clique[0] > clique[1]) {
01419
01420 if (lowerAdjacentMatrix[(*theTranslator)[clique[0]]-1][(*theTranslator)[clique[1]]]) {
01421 found = true;
01422 }
01423 }
01424 else {
01425 if (lowerAdjacentMatrix[(*theTranslator)[clique[1]]-1][(*theTranslator)[clique[0]]]) {
01426 found = true;
01427 }
01428 }
01429 }
01430 }
01431
01432
01433
01434
01435 adjacentNodes = (*theAdjacentList)[clique[0]];
01436 for (i=adjacentNodes.size()-1; i>=0; i--) {
01437 if (clique[1] == adjacentNodes[i]) {
01438 adjacentNodes.erase(adjacentNodes.begin()+i);
01439 continue;
01440 }
01441 if (clique[1] > adjacentNodes[i]) {
01442 if (!lowerAdjacentMatrix[(*theTranslator)[clique[1]]-1][(*theTranslator)[adjacentNodes[i]]]) {
01443 adjacentNodes.erase(adjacentNodes.begin()+i);
01444 }
01445 }
01446 else {
01447 if (!lowerAdjacentMatrix[(*theTranslator)[adjacentNodes[i]]-1][(*theTranslator)[clique[1]]]) {
01448 adjacentNodes.erase(adjacentNodes.begin()+i);
01449 }
01450 }
01451 }
01452
01453
01454
01455
01456
01457 while (!adjacentNodes.empty() && (adjacentNodes.size() + clique.size()) > maxCliqueSize) {
01458 clique.push_back(adjacentNodes.back());
01459 adjacentNodes.pop_back();
01460
01461 for (i=adjacentNodes.size()-1; i>=0; i--) {
01462 if (clique.back() > adjacentNodes[i]) {
01463 if (!lowerAdjacentMatrix[(*theTranslator)[clique.back()]-1][(*theTranslator)[adjacentNodes[i]]]) {
01464 adjacentNodes.erase(adjacentNodes.begin()+i);
01465 }
01466 }
01467 else {
01468 if(!lowerAdjacentMatrix[(*theTranslator)[adjacentNodes[i]]-1][(*theTranslator)[clique.back()]]) {
01469 adjacentNodes.erase(adjacentNodes.begin()+i);
01470 }
01471
01472 }
01473 }
01474 }
01475
01476
01477
01478
01479 if ((adjacentNodes.size() + clique.size()) > maxCliqueSize) {
01480
01481 maxClique->clear();
01482 (*maxClique) = clique;
01483 maxCliqueSize = maxClique->size();
01484 }
01485
01486 clique.clear();
01487 adjacentNodes.clear();
01488 clique.resize(2);
01489 cnt++;
01490 }
01491
01492 return maxClique;
01493
01494 }
01495
01496
01497
01498
01499
01500
01501
01502
01503
01504
01505
01506 void EdgeProjection::computeFalseEdges(vector<int*> *falseEdges) {
01507
01508
01509 vector<int> neighborhoodU;
01510 vector<int> neighborhoodV;
01511
01512
01513
01514
01515 getNeighborhood(edge[0], &neighborhoodU);
01516 getNeighborhood(edge[1], &neighborhoodV);
01517
01518
01519
01520
01521 int i, j;
01522 int nodeOne;
01523 int nodeTwo;
01524 int *falseEdge;
01525 int sizeU = neighborhoodU.size();
01526 int sizeV = neighborhoodV.size();
01527
01528 for (i=0; i<sizeU; i++) {
01529 for (j=0; j<sizeV; j++) {
01530 nodeOne = neighborhoodU[i];
01531 nodeTwo = neighborhoodV[j];
01532 if (nodeOne > nodeTwo) {
01533 if (!lowerAdjacentMatrix[nodeOne-1][nodeTwo]) {
01534 falseEdge = new int[2];
01535 falseEdge[0] = nodeOne;
01536 falseEdge[1] = nodeTwo;
01537 falseEdges->push_back(falseEdge);
01538 }
01539 }
01540 else {
01541 if (!lowerAdjacentMatrix[nodeTwo-1][nodeOne]) {
01542 falseEdge = new int[2];
01543 falseEdge[0] = nodeTwo;
01544 falseEdge[1] = nodeOne;
01545 falseEdges->push_back(falseEdge);
01546 }
01547 }
01548 }
01549 }
01550
01551 }
01552
01553
01554
01555
01556
01557
01558
01559
01560
01561 void EdgeProjection::getNeighborhood(int node, vector<int> *neighborhood) {
01562
01563 int i, j;
01564 int vertex;
01565
01566
01567
01568
01569 for (i=0; i<node; i++) {
01570 if (lowerAdjacentMatrix[node-1][i]) {
01571 neighborhood->push_back(i);
01572 }
01573 }
01574 for (j=i+1; j<graphSize; j++) {
01575 if (lowerAdjacentMatrix[j-1][node]) {
01576 neighborhood->push_back(j);
01577 }
01578 }
01579
01580 }
01581
01582
01583
01584
01585
01586
01587
01588
01589
01590
01591
01592
01593
01594 void EdgeProjection::updateGraph() {
01595
01596 int i, j, k, l;
01597 int node;
01598 int vertex;
01599 int size;
01600
01601
01602
01603
01604 if (edge[0] > edge[1]) {
01605 lowerAdjacentMatrix[edge[0]-1][edge[1]] = 0;
01606 }
01607 else {
01608 lowerAdjacentMatrix[edge[1]-1][edge[0]] = 0;
01609 }
01610
01611
01612
01613
01614
01615 size = deleteEdges.size();
01616 for (i=0; i<size; i++) {
01617 node = deleteEdges[i][0];
01618 vertex = deleteEdges[i][1];
01619 if (node > vertex) {
01620 lowerAdjacentMatrix[node-1][vertex] = 0;
01621 }
01622 else {
01623 lowerAdjacentMatrix[vertex-1][node] = 0;
01624 }
01625
01626 adjacentListSize[vertex] -= 1;
01627 }
01628
01629
01630
01631
01632 size = deleteNodes.size();
01633 for (i=0; i<size; i++) {
01634 node = deleteNodes[i];
01635 adjacentListSize[node] = 0;
01636
01637 for (j=0; j<node; j++) {
01638 if (lowerAdjacentMatrix[node-1][j]) {
01639 lowerAdjacentMatrix[node-1][j] = 0;
01640
01641 adjacentListSize[j] -= 1;
01642 if ((j!=edge[0]) && (j!=edge[1])) {
01643 for (k=0; k<i; k++) {
01644 if (j == deleteNodes[k]) {
01645 break;
01646 }
01647 }
01648 if (k == i) {
01649
01650 int *anEdge = new int[2];
01651 anEdge[0] = node;
01652 anEdge[1] = j;
01653 deleteEdges.push_back(anEdge);
01654 }
01655 }
01656 }
01657 }
01658 for (k=j+1; k<graphSize; k++) {
01659 if (lowerAdjacentMatrix[k-1][node]) {
01660 lowerAdjacentMatrix[k-1][node] = 0;
01661
01662 adjacentListSize[k] -= 1;
01663 if ((k!=edge[0]) && (k!=edge[1])) {
01664 for (l=i+1; l<size; l++) {
01665 if (k == deleteNodes[l]) {
01666 break;
01667 }
01668 }
01669 if (l == size) {
01670
01671 int *anEdge = new int[2];
01672 anEdge[0] = node;
01673 anEdge[1] = k;
01674 deleteEdges.push_back(anEdge);
01675 }
01676 }
01677 }
01678 }
01679 }
01680
01681 }
01682
01683
01684
01685
01686
01687
01688
01689
01690 void EdgeProjection::updateGraph(vector<int*> *falseEdges) {
01691
01692 int i, j, k;
01693 int node;
01694 int vertex;
01695 int size;
01696 int *anEdge;
01697
01698
01699
01700
01701 for (i=0; i<2; i++) {
01702 node = edge[i];
01703 adjacentListSize[node] = 0;
01704
01705 for (j=0; j<node; j++) {
01706 if (lowerAdjacentMatrix[node-1][j]) {
01707 lowerAdjacentMatrix[node-1][j] = 0;
01708
01709 adjacentListSize[j] -= 1;
01710
01711 anEdge = new int[2];
01712 anEdge[0] = node;
01713 anEdge[1] = j;
01714 deleteEdges.push_back(anEdge);
01715 }
01716 }
01717 for (k=j+1; k<graphSize; k++) {
01718 if (lowerAdjacentMatrix[k-1][node]) {
01719 lowerAdjacentMatrix[k-1][node] = 0;
01720
01721 adjacentListSize[k] -= 1;
01722
01723 anEdge = new int[2];
01724 anEdge[0] = k;
01725 anEdge[1] = node;
01726 deleteEdges.push_back(anEdge);
01727 }
01728 }
01729 }
01730
01731
01732
01733
01734
01735 size = falseEdges->size();
01736 for (i=0; i<size; i++) {
01737 node = (*falseEdges)[i][0];
01738 vertex = (*falseEdges)[i][1];
01739 if (vertex > node) {
01740 lowerAdjacentMatrix[vertex-1][node] = 1;
01741 }
01742 else {
01743 lowerAdjacentMatrix[node-1][vertex] = 1;
01744 }
01745 adjacentListSize[node] += 1;
01746 adjacentListSize[vertex] += 1;
01747 }
01748
01749 }
01750
01751
01752
01753
01754
01755
01756
01757 void EdgeProjection::addNode(vector<int*> *falseEdges) {
01758
01759
01760
01761
01762
01763
01764 if (currentNode == NULL) {
01765
01766 ProjectionNode *pN;
01767 pN = new ProjectionNode(edge, &deleteNodes, &deleteEdges, falseEdges,
01768 NULL);
01769
01770
01771 itsNodes.push_back(pN);
01772
01773 currentNode = pN;
01774 }
01775 else {
01776
01777
01778 currentNode = currentNode->addNode(edge, &deleteNodes, &deleteEdges,
01779 falseEdges);
01780 }
01781
01782 }
01783
01784
01785
01786
01787
01788
01789
01790
01791 void EdgeProjection::getReducedGraph(vector< vector<int> > *reducedGraph) {
01792
01793 int i, j;
01794 int cnt = 0;
01795 int cnt2 = 0;
01796 int reducedGraphSize;
01797
01798
01799
01800
01801 int translateNode[graphSize];
01802
01803 if (!translator.empty()) {
01804 translator.clear();
01805 }
01806
01807 translator.resize(graphSize);
01808 for (i=0; i<graphSize; i++) {
01809 if (adjacentListSize[i] != 0) {
01810 translateNode[i] = cnt;
01811
01812 translator[cnt] = i;
01813 cnt++;
01814 }
01815 else {
01816 translateNode[i] = -1;
01817 }
01818 }
01819
01820 translator.resize(cnt);
01821
01822
01823
01824
01825 reducedGraphSize = cnt;
01826 (*reducedGraph).resize(reducedGraphSize);
01827
01828 for (i=0; i<graphSize; i++) {
01829 if (adjacentListSize[i] != 0) {
01830 cnt = 0;
01831 (*reducedGraph)[cnt2].resize(adjacentListSize[i]);
01832 for (j=0; j<i; j++) {
01833 if (lowerAdjacentMatrix[i-1][j]) {
01834 (*reducedGraph)[cnt2][cnt] = translateNode[j];
01835 cnt++;
01836 }
01837 }
01838 for (j=i+1; j<graphSize; j++) {
01839 if (lowerAdjacentMatrix[j-1][i]) {
01840 (*reducedGraph)[cnt2][cnt] = translateNode[j];
01841 cnt++;
01842 }
01843 }
01844 cnt2++;
01845 }
01846 }
01847
01848 }
01849
01850
01851
01852
01853
01854 int EdgeProjection::cliqueSeparation(vector< vector<int> > *graph,
01855 double *lpValue,
01856 vector< vector<int> > *theLhs) {
01857
01858 int i, j;
01859 int index;
01860 double value;
01861 int numberOfCutsBeginning = theLhs->size();
01862 int numberOfCuts = numberOfCutsBeginning;
01863 vector<int> clique(2);
01864 vector<int> adjacentNodes;
01865 int size = graph->size();
01866 vector<int*> *falseEdges = currentNode->getFalseEdges();
01867 int falseEdgesCnt = 0;
01868
01869 int cnt = 0;
01870 bool found;
01871 bool newOne;
01872
01873 bool STOP = false;
01874 int theCnt = 0;
01875 int cutCnt = 0;
01876
01877
01878
01879
01880 static const int MAX_ITER_SEP = size * 2;
01881 static const int MAX_STEP = size / 5;
01882 static const int MAX_CUTS = size;
01883 static const double MIN_VIOLATION = .000001;
01884
01885
01886
01887
01888 while ( (cnt < MAX_ITER_SEP) ) {
01889
01890
01891
01892
01893 if (falseEdgesCnt < falseEdges->size()) {
01894 clique[0] = (*falseEdges)[falseEdgesCnt][0];
01895
01896 i = 0;
01897 while(i < size) {
01898 if (clique[0] == translator[i]) {
01899 clique[0] = i;
01900 break;
01901 }
01902 i++;
01903 }
01904 if (i == size) {
01905 cout << "ERROR" << endl;
01906 exit(1);
01907 }
01908
01909 clique[1] = (*falseEdges)[falseEdgesCnt++][1];
01910
01911 i = 0;
01912 while(i < size) {
01913 if (clique[1] == translator[i]) {
01914 clique[1] = i;
01915 break;
01916 }
01917 i++;
01918 }
01919 if (i == size) {
01920 cout << "ERROR" << endl;
01921 exit(1);
01922 }
01923 }
01924 else {
01925 found = false;
01926 while (!found) {
01927 clique[0] = getRandomNumber(size);
01928 clique[1] = getRandomNumber(size);
01929 if (clique[0] != clique[1]) {
01930 if (clique[0] > clique[1]) {
01931 if (lowerAdjacentMatrix[translator[clique[0]]-1][translator[clique[1]]]) {
01932 found = true;
01933 }
01934 }
01935 else {
01936 if (lowerAdjacentMatrix[translator[clique[1]]-1][translator[clique[0]]]) {
01937 found = true;
01938 }
01939 }
01940 }
01941 }
01942 }
01943
01944
01945
01946
01947 adjacentNodes = (*graph)[clique[0]];
01948 for (i=adjacentNodes.size()-1; i>=0; i--) {
01949 if (clique.back() == adjacentNodes[i]) {
01950 adjacentNodes.erase(adjacentNodes.begin()+i);
01951 continue;
01952 }
01953 if (clique.back() > adjacentNodes[i]) {
01954 if (!lowerAdjacentMatrix[translator[clique.back()]-1][translator[adjacentNodes[i]]]) {
01955 adjacentNodes.erase(adjacentNodes.begin()+i);
01956 }
01957 }
01958 else {
01959 if (!lowerAdjacentMatrix[translator[adjacentNodes[i]]-1][translator[clique.back()]]) {
01960 adjacentNodes.erase(adjacentNodes.begin()+i);
01961 }
01962 }
01963 }
01964
01965
01966
01967
01968 while(!adjacentNodes.empty()) {
01969 index = getRandomNumber(adjacentNodes.size());
01970 clique.push_back(adjacentNodes[index]);
01971 adjacentNodes.erase(adjacentNodes.begin() + index);
01972
01973 for (i=adjacentNodes.size()-1; i>=0; i--) {
01974 if (clique.back() > adjacentNodes[i]) {
01975 if (!lowerAdjacentMatrix[translator[clique.back()]-1][translator[adjacentNodes[i]]]) {
01976 adjacentNodes.erase(adjacentNodes.begin()+i);
01977 }
01978 }
01979 else {
01980 if (!lowerAdjacentMatrix[translator[adjacentNodes[i]]-1][translator[clique.back()]]) {
01981 adjacentNodes.erase(adjacentNodes.begin()+i);
01982 }
01983 }
01984 }
01985 }
01986
01987
01988
01989
01990 theCnt++;
01991 value = 0;
01992 for (i=0; i<clique.size(); i++) {
01993 value += lpValue[clique[i]];
01994 }
01995 if (value > 1 + MIN_VIOLATION) {
01996
01997 sort(clique.begin(), clique.end());
01998 newOne = true;
01999 for (i=numberOfCutsBeginning; i<numberOfCuts; i++) {
02000 if ((*theLhs)[i].size() != clique.size()) {
02001 continue;
02002 }
02003 j=0;
02004 while (j<(*theLhs)[i].size()) {
02005 if (clique[j] != (*theLhs)[i][j]) {
02006 break;
02007 }
02008 j++;
02009 }
02010 if (j == (*theLhs)[i].size()) {
02011 newOne = false;
02012 break;
02013 }
02014 }
02015 if (newOne) {
02016 numberOfCuts++;
02017 theLhs->resize(numberOfCuts);
02018 for (i=0; i<clique.size(); i++) {
02019 (*theLhs)[numberOfCuts-1].push_back(clique[i]);
02020 }
02021 theCnt = 0;
02022 cutCnt++;
02023 }
02024 }
02025
02026 clique.clear();
02027 adjacentNodes.clear();
02028 clique.resize(2);
02029 cnt++;
02030 }
02031
02032 return cutCnt;
02033
02034 }
02035
02036
02037
02038
02039
02040
02041
02042
02043
02044 void EdgeProjection::solveStableSet(vector<int> *theLhs,
02045 int &theRhs, StableSetMaster *theMaster) {
02046
02047 int i, j;
02048 char *graph = theMaster->getSmallGraphName();
02049 string theGraph("./");
02050 theGraph.append(graph);
02051 string inequalities(graph);
02052 inequalities.append("Ineq.txt");
02053
02054
02055
02056
02057 int numberOfNodes = 0;
02058 int numberOfEdges = 0;
02059 translator.clear();
02060 translator.resize(graphSize, -1);
02061
02062
02063 for (i=0; i<graphSize; i++) {
02064 if (adjacentListSize[i] != 0) {
02065 translator[i] = numberOfNodes;
02066 numberOfNodes++;
02067 numberOfEdges += adjacentListSize[i];
02068 }
02069 }
02070
02071 ofstream fout(graph);
02072 fout << "NNODES : " << numberOfNodes << endl;
02073 fout << "NEDGES : " << numberOfEdges/2 << endl;
02074 fout << "WEIGHTS : NO\n";
02075 fout << "\nEDGE_SECTION :" << endl;
02076 for (i=0; i<graphSize-1; i++) {
02077 for (j=i; j<graphSize-1; j++) {
02078 if (lowerAdjacentMatrix[j][i]) {
02079 fout << translator[i] << " " << translator[j+1] << endl;
02080 }
02081 }
02082 }
02083 fout.close();
02084
02085
02086
02087
02088
02089
02090 StableSetMaster *stableSet;
02091 stableSet = new StableSetMaster(theGraph.c_str(), inequalities.c_str(),
02092 "DUMMY");
02093
02094 stableSet->outLevel(ABA_MASTER::Silent);
02095 ABA_STRING theAbaString(stableSet, "00:00:01");
02096 stableSet->maxCpuTime(theAbaString);
02097
02098 ABA_MASTER::STATUS error = stableSet->optimize();
02099
02100
02101
02102
02103 if (error) {
02104 exit(1);
02105 }
02106
02107
02108
02109
02110
02111
02112
02113
02114
02115
02116
02117
02118
02119
02120
02121
02122
02123
02124
02125
02126
02127
02128
02129
02130
02131
02132
02133
02134 for (i=0; i<graphSize; i++) {
02135 if (adjacentListSize[i] != 0) {
02136 theLhs->push_back(i);
02137 }
02138 }
02139 theRhs = (int) stableSet->dualBound() + stableSet->fixedNodesToOne();
02140
02141
02142 delete stableSet;
02143
02144 }
02145
02146
02147
02148
02149
02150
02151
02152
02153 void EdgeProjection::liftAndStore(vector<int> *theLhs, int theRhs) {
02154
02155 int i, j, k;
02156 int size;
02157 int nodeOne;
02158 int nodeTwo;
02159 int stack;
02160 vector<int*>* theFalseEdges;
02161 vector<int>* theDeletedNodes;
02162 int deletedNodesSize;
02163 ProjectionNode* aNode;
02164
02165 rhs.resize(1);
02166 rhs[0] = theRhs;
02167
02168
02169
02170
02171
02172
02173
02174 aNode = currentNode;
02175
02176 while (aNode != NULL) {
02177
02178
02179 theFalseEdges = aNode->getFalseEdges();
02180
02181
02182 j = 0;
02183 size = theLhs->size();
02184 while (j < theFalseEdges->size()) {
02185 nodeOne = (*theFalseEdges)[j][0];
02186 nodeTwo = (*theFalseEdges)[j][1];
02187 j++;
02188
02189 if (nodeOne > nodeTwo) {
02190 stack = nodeOne;
02191 nodeOne = nodeTwo;
02192 nodeTwo = stack;
02193 }
02194 k = 0;
02195 while (k < size) {
02196 if( (*theLhs)[k] >= nodeOne ) {
02197 break;
02198 }
02199 k++;
02200 }
02201 if (k == size) {
02202
02203 continue;
02204 }
02205 if ((*theLhs)[k] != nodeOne) {
02206
02207 continue;
02208 }
02209 k++;
02210 while (k < size) {
02211 if( (*theLhs)[k] >= nodeTwo ) {
02212 break;
02213 }
02214 k++;
02215 }
02216 if (k == size) {
02217
02218 continue;
02219 }
02220 if ((*theLhs)[k] != nodeTwo) {
02221
02222 continue;
02223 }
02224
02225
02226
02227
02228
02229 theDeletedNodes = aNode->getDeletedNodes();
02230 deletedNodesSize = theDeletedNodes->size();
02231 for (k=0; k<deletedNodesSize; k++) {
02232 theLhs->push_back((*theDeletedNodes)[k]);
02233 }
02234
02235
02236 theLhs->push_back(aNode->getEdge(0));
02237 theLhs->push_back(aNode->getEdge(1));
02238
02239
02240 sort(theLhs->begin(), theLhs->end());
02241
02242 rhs[0] += 1;
02243
02244
02245
02246
02247 break;
02248 }
02249
02250
02251 aNode = aNode->getPreviousNode();
02252 }
02253
02254
02255
02256
02257 vector<int> *inequality = new vector<int>;
02258 inequality->resize(theLhs->size());
02259 for (j=0; j<theLhs->size(); j++) {
02260 (*inequality)[j] = (*theLhs)[j];
02261 }
02262 lhs.push_back(inequality);
02263
02264 }
02265
02266
02267
02268
02269
02270 int EdgeProjection::getRandomNumber(int bound) const {
02271 int aNumber = rand();
02272 double d = (double(aNumber)/RAND_MAX);
02273
02274 return (int)(d*bound);
02275 }
02276
02277
02278
02279
02280
02281 void EdgeProjection::cleanUp() {
02282
02283 int i, j;
02284 int nodeOne;
02285 int nodeTwo;
02286 int size;
02287 vector<int> *nodes;
02288 vector<int*> *edges;
02289
02290
02291
02292
02293
02294 while (currentNode != NULL) {
02295
02296
02297
02298
02299 nodeOne = currentNode->getEdge(0);
02300 nodeTwo = currentNode->getEdge(1);
02301 if (nodeOne > nodeTwo) {
02302 lowerAdjacentMatrix[nodeOne-1][nodeTwo] = 1;
02303 }
02304 else {
02305 lowerAdjacentMatrix[nodeTwo-1][nodeOne] = 1;
02306 }
02307 adjacentListSize[nodeOne] += 1;
02308 adjacentListSize[nodeTwo] += 1;
02309
02310
02311
02312
02313
02314 nodes = currentNode->getDeletedNodes();
02315 size = nodes->size();
02316 for (i=0; i<size; i++) {
02317
02318 if (nodeOne > (*nodes)[i]) {
02319 lowerAdjacentMatrix[nodeOne-1][(*nodes)[i]] = 1;
02320 }
02321 else {
02322 lowerAdjacentMatrix[(*nodes)[i]-1][nodeOne] = 1;
02323 }
02324 adjacentListSize[nodeOne] += 1;
02325 adjacentListSize[(*nodes)[i]] += 1;
02326
02327
02328 if (nodeTwo > (*nodes)[i]) {
02329 lowerAdjacentMatrix[nodeTwo-1][(*nodes)[i]] = 1;
02330 }
02331 else {
02332 lowerAdjacentMatrix[(*nodes)[i]-1][nodeTwo] = 1;
02333 }
02334 adjacentListSize[nodeTwo] += 1;
02335 adjacentListSize[(*nodes)[i]] += 1;
02336
02337
02338 for (j=i+1; j<size; j++) {
02339 if ((*nodes)[j] > (*nodes)[i]) {
02340 lowerAdjacentMatrix[(*nodes)[j]-1][(*nodes)[i]] = 1;
02341 }
02342 else {
02343 lowerAdjacentMatrix[(*nodes)[i]-1][(*nodes)[j]] = 1;
02344 }
02345 adjacentListSize[(*nodes)[i]] += 1;
02346 adjacentListSize[(*nodes)[j]] += 1;
02347 }
02348 }
02349
02350
02351
02352
02353 edges = currentNode->getDeletedEdges();
02354 size = edges->size();
02355 for (i=0; i<size; i++) {
02356 if ((*edges)[i][1] > (*edges)[i][0]) {
02357 lowerAdjacentMatrix[(*edges)[i][1]-1][(*edges)[i][0]] = 1;
02358 }
02359 else {
02360 lowerAdjacentMatrix[(*edges)[i][0]-1][(*edges)[i][1]] = 1;
02361 }
02362 adjacentListSize[(*edges)[i][0]] += 1;
02363 adjacentListSize[(*edges)[i][1]] += 1;
02364 }
02365
02366
02367
02368
02369 edges = currentNode->getFalseEdges();
02370 size = edges->size();
02371 for (i=0; i<size; i++) {
02372 if ((*edges)[i][1] > (*edges)[i][0]) {
02373 lowerAdjacentMatrix[(*edges)[i][1]-1][(*edges)[i][0]] = 0;
02374 }
02375 else {
02376 lowerAdjacentMatrix[(*edges)[i][0]-1][(*edges)[i][1]] = 0;
02377 }
02378 adjacentListSize[(*edges)[i][0]] -= 1;
02379 adjacentListSize[(*edges)[i][1]] -= 1;
02380 }
02381
02382
02383
02384
02385 currentNode = currentNode->getPreviousNode();
02386 }
02387
02388
02389 for (int i=itsNodes.size()-1; i>=0; i--) {
02390 delete itsNodes[i];
02391 itsNodes[i] = NULL;
02392 }
02393 itsNodes.clear();
02394
02395 }
02396
02397
02398
02399
02400
02401 void EdgeProjection::printRoot() {
02402
02403 cout << "\n\nReduction Graph:\n";
02404 for (int i=0; i<lowerAdjacentMatrix.size(); i++) {
02405 cout << "\t";
02406 for (int j=0; j<lowerAdjacentMatrix[i].size(); j++) {
02407 cout << lowerAdjacentMatrix[i][j] << " ";
02408 }
02409 cout << endl;
02410 }
02411
02412 cout << "\nAdjacent List sizes:\n\t";
02413 for (int i=0; i<graphSize; i++) {
02414 cout << adjacentListSize[i] << " ";
02415 }
02416 cout << endl << endl << endl;
02417
02418 }
02419
02420
02421
02422
02423
02424
02425
02426
02427
02428
02429
02430
02431
02432
02433
02434
02435
02436
02437
02438
02439
02440
02441
02442
02443
02444
02445
02446
02447
02448
02449
02450
02451
02452
02453
02454
02455
02456
02457
02458
02459
02460
02461
02462
02463
02464
02465
02466
02467
02468
02469
02470
02471
02472
02473
02474
02475
02476
02477
02478
02479
02480
02481
02482
02483
02484
02485
02486
02487
02488
02489
02490
02491
02492
02493
02494
02495
02496
02497
02498
02499
02500
02501
02502
02503
02504
02505
02506
02507
02508
02509
02510
02511
02512
02513
02514
02515
02516
02517
02518
02519
02520
02521
02522
02523
02524
02525
02526
02527
02528
02529
02530
02531
02532
02533
02534
02535
02536
02537
02538
02539
02540
02541
02542
02543
02544
02545
02546
02547
02548
02549
02550
02551
02552
02553
02554
02555
02556
02557
02558
02559
02560
02561
02562
02563
02564
02565
02566
02567
02568
02569
02570
02571
02572
02573
02574
02575
02576
02577
02578
02579
02580
02581
02582
02583
02584
02585
02586
02587
02588
02589
02590
02591
02592
02593
02594
02595
02596
02597
02598
02599
02600
02601
02602
02603
02604
02605
02606
02607
02608
02609
02610
02611
02612
02613
02614
02615
02616
02617
02618
02619
02620
02621
02622
02623
02624
02625
02626
02627
02628
02629
02630
02631
02632
02633
02634
02635
02636
02637
02638
02639
02640
02641
02642
02643
02644
02645
02646
02647
02648
02649
02650
02651
02652
02653
02654
02655
02656
02657
02658
02659
02660
02661
02662
02663
02664
02665
02666
02667
02668
02669
02670
02671
02672
02673
02674
02675
02676
02677
02678
02679
02680
02681
02682
02683
02684
02685
02686
02687
02688
02689
02690
02691
02692
02693
02694
02695
02696
02697
02698
02699
02700
02701
02702
02703
02704
02705
02706
02707
02708
02709
02710
02711
02712
02713
02714
02715
02716
02717
02718
02719
02720
02721
02722
02723
02724
02725
02726
02727
02728
02729
02730
02731
02732
02733
02734
02735
02736
02737
02738
02739
02740
02741
02742
02743
02744
02745
02746
02747
02748
02749
02750
02751
02752
02753
02754
02755
02756
02757
02758
02759
02760
02761
02762
02763
02764
02765
02766
02767
02768
02769
02770
02771
02772
02773
02774
02775
02776
02777
02778
02779
02780
02781
02782
02783
02784
02785
02786
02787
02788
02789
02790
02791
02792
02793
02794
02795
02796
02797
02798
02799
02800
02801
02802
02803
02804
02805
02806
02807
02808
02809
02810
02811
02812
02813
02814
02815
02816
02817
02818
02819
02820
02821
02822
02823
02824
02825
02826
02827
02828
02829
02830
02831
02832
02833
02834
02835
02836
02837
02838
02839
02840
02841
02842
02843
02844
02845
02846
02847
02848
02849
02850
02851
02852
02853
02854
02855
02856
02857
02858
02859
02860
02861
02862
02863
02864
02865
02866
02867
02868
02869
02870
02871
02872
02873
02874
02875
02876
02877
02878
02879
02880
02881
02882
02883
02884
02885
02886
02887
02888
02889
02890
02891
02892
02893
02894
02895
02896
02897
02898
02899
02900
02901
02902
02903
02904
02905
02906
02907
02908
02909
02910
02911
02912
02913
02914
02915
02916
02917
02918
02919
02920
02921
02922
02923
02924
02925
02926
02927
02928
02929
02930
02931
02932
02933
02934
02935
02936
02937
02938
02939
02940
02941
02942
02943
02944
02945
02946
02947
02948
02949
02950
02951
02952
02953
02954
02955
02956
02957
02958
02959
02960
02961
02962
02963
02964
02965
02966
02967
02968
02969
02970
02971
02972
02973
02974
02975
02976
02977
02978
02979
02980
02981
02982
02983
02984
02985
02986
02987
02988
02989
02990
02991
02992
02993
02994
02995
02996
02997
02998
02999
03000
03001
03002
03003
03004
03005
03006
03007
03008
03009
03010
03011
03012
03013
03014
03015
03016
03017
03018
03019
03020
03021
03022
03023
03024
03025
03026
03027
03028
03029
03030
03031
03032
03033
03034
03035
03036
03037
03038
03039
03040
03041
03042
03043
03044
03045
03046
03047
03048
03049
03050
03051
03052
03053
03054
03055
03056
03057