C:/Programme/home/Administrator/CD/stableSetCode/EdgeProjection.cpp

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : EdgeProjection.cpp
00004 //  Description      : Separation through edge projection.
00005 //  Author           : Steffen Rebennack
00006 //  Email            : srebenac@ix.urz.uni-heidelberg.de;
00007 //                     steffen.rebennack@web.de
00008 //  Copyright        : (C) 2006 by the University of L'Aquvila and
00009 //                     University of Heidelberg
00010 //  Created on       : Wed Apr 05 08:35:12 2006
00011 //  Last modified by : -
00012 //  Last modified on : - 
00013 //  Update count     : 0
00014 //
00016 //
00017 //  Date        Name            Changes/Extensions
00018 //  ----        ----            ------------------
00019 //
00021 
00022 #include "EdgeProjection.hh"
00023 #include <cstdlib>                   // rand()
00024 
00025 #include "abacus/master.h"
00026 #include "StableSetMaster.hh"
00027 
00028 
00029 
00030 // -----------------------------------------------------------------------------
00031 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00032 // -----------------------------------------------------------------------------
00033 
00034 
00035 // -----------------------------------------------------------------------------
00036 // C o n s t r u c t o r
00037 //
00038 // Copy adjacent list of the graph.
00039 // Initialize the adjacent matrix as a lower triangular matrix storing if
00040 // an edge is in the reduced graph or not.
00041 // Initilaize the tree.
00042 // -----------------------------------------------------------------------------
00043 EdgeProjection::EdgeProjection(vector< vector<int> > *graph):
00044 currentNode(NULL)
00045 {
00046 
00047     int i, j;   // Loop variables.
00048     int node;   // Store a node.
00049 
00050     // Number of nodes of the graph.
00051     graphSize = graph->size();
00052 
00053     // Allocate memory for the adjacent list size counter.
00054     adjacentListSize = new int[graphSize];
00055 
00056     // Allocate memory for the adjacent matrix.
00057     lowerAdjacentMatrix.resize(graphSize - 1);
00058     for (i=1; i<graphSize; i++) {
00059         lowerAdjacentMatrix[i-1].resize(i,0);
00060     }
00061 
00062     // Copy graph and store each size of the adjacent list.
00063     for (i=0; i<graphSize; i++) {
00064         // Update the size of each adjacent list.
00065         adjacentListSize[i] = (*graph)[i].size();
00066         for (j=0; j<adjacentListSize[i]; j++) {
00067             node = (*graph)[i][j];
00068             // Store this edge in the adjacent matrix.
00069             if (i > node) {
00070                 lowerAdjacentMatrix[i-1][node] = 1;
00071             }
00072         }// for
00073     }// for
00074 
00075 
00076     // Check each edge if it is strong projectable.
00077 //    checkStrongProjectability();
00078 //    cout << "Number of strongly projectable edges: ";
00079 //    cout << projectable.size() << endl;
00080 
00081     // Initialize random counter.
00082     srand(1);
00083     
00084     // Print information of the root of the tree.    
00085     //printRoot();
00086 
00087 }// end constructor
00088 
00089 
00090 // -----------------------------------------------------------------------------
00091 // D e s t r u c t o r
00092 // -----------------------------------------------------------------------------
00093 EdgeProjection::~EdgeProjection() {
00094 
00095     delete []adjacentListSize;
00096 
00097     if (!lhs.empty()) {
00098         // Delete the inequalities.
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 }// end destructor
00107 
00108 
00109 // -----------------------------------------------------------------------------
00110 // s e p a r a t e
00111 //
00112 // This is the heart of the edge projection.
00113 // Until a stop criteria, it selects an edge and computes its projection.
00114 // Now, we have the freedom to call separation routines or to start again. 
00115 // -----------------------------------------------------------------------------
00116 int EdgeProjection::separate(double *lpValue) {
00117 
00118     int i;          // Loop variable.
00119     int numCut;     // The number of violated cuts found.
00120     int reducedGraphSize = graphSize;
00121     vector< vector<int> > theLhs;  // Store violated inequalities (lhs).
00122     vector<int> theRhs;            // Store violated inequalities (rhs).
00123     bool condition = true;  // Stop criteria for projection.
00124     bool separate  = true;  // Call separation or not.
00125     
00126     //
00127     // Parameter
00128     //
00129     const int ENOUGH_INEQUALITIES = (int) .2 * graphSize;
00130     
00131     // 
00132     // Clear all stored inequalities.
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     // Do edge projection until the graph is too small or enough cuts have
00145     // have been computed.
00146     //    
00147     while (condition) {
00148 
00149         //
00150         // Select a new projectable edge
00151         //
00152         // Includes:
00153         // + check if the edge is projectable
00154         // + store all edges to be deleted that the edge is strongly projectable
00155         // + compute all nodes to be removed
00156         //
00157         bool edgeFound = edgeSelection(lpValue);
00158 
00159         if (!edgeFound) {
00160             break;
00161         }
00162 
00163         //
00164         // Projection: update reduction graph
00165         //  
00166         projection();
00167 
00168         //
00169         // Update size of reduced graph to check if the graph is too small.
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         // Deside whether to start separation rountines or to project again.
00184         //   
00185         if (separate) {
00186             
00187             //
00188             // Call separation routines on the reduced graph.
00189             // theLhs and theRhs will store the information of the inequalities.
00190             //
00191             numCut = separation(lpValue, &theLhs, &theRhs);
00192 
00193             //
00194             // Check if a violated inequality has been found.
00195             //
00196             if (numCut) {
00197                 //
00198                 // Lift these inequalities.
00199                 //
00200                 lifting(&theLhs, &theRhs);
00201 
00202                 //
00203                 // Store these inequalities.
00204                 //
00205                 storeInequalities(&theLhs, &theRhs, lpValue);
00206         
00207                 //
00208                 // Check if enough inequalities have been computed.
00209                 //
00210                 if (lhs.size() >= ENOUGH_INEQUALITIES) {
00211                     condition = false;
00212                 }
00213             }
00214         }// if
00215 
00216         //
00217         // Clean up
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     }// while
00229     
00230     //
00231     // Select only the best inequalities.
00232     //
00233 //    cleanUpInequalities(lpValue);
00234     
00235     //
00236     // Clean up tree.
00237     //
00238     cleanUp();
00239 
00240     // Return: no error.
00241     return 0;
00242 
00243 }// end separate(..)
00244 
00245 
00246 // -----------------------------------------------------------------------------
00247 // c o m p u t e L a r g e I n e q u a l i t y
00248 //
00249 // Compute a large rank inequality. Project the graph until it is small enough
00250 // to solve a maximum stable set problem fast. Call the stable set solver for
00251 // that small graph and receive a large rank inequality.
00252 // -----------------------------------------------------------------------------
00253 int EdgeProjection::computeLargeInequality(double *lpValue,
00254                                            StableSetMaster *theMaster) {
00255 
00256     int i;  // Loop counter.
00257     int reducedGraphSize = graphSize;
00258     bool condition = true;      // Stop criteria for the projection.
00259     vector<int> theLhs;         // Store the rank inequality (lhs)
00260     int theRhs;                 // Store the rank inequality (rhs)
00261 
00262     //
00263     // Parameter.
00264     //
00265     const static int MAX_SIZE_OF_GRAPH = 45; //(int) graphSize / 5 ;  
00266   
00267     // 
00268     // Clear all stored inequalities.
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     // Project until the graph is small enough to solve a stable set problem
00280     // exact. After one cut has been computed stop the projection.
00281     //    
00282     while (condition) {
00283 
00284         //
00285         // Select a new projectable edge
00286         //
00287         // Includes:
00288         // + check if the edge is projectable
00289         // + store all edges to be deleted that the edge is strongly projectable
00290         // + compute all nodes to be removed
00291         //
00292         bool edgeFound = edgeSelection(lpValue);
00293 
00294         if (!edgeFound) {
00295             break;
00296         }
00297 
00298         //
00299         // Projection: update reduction graph
00300         //  
00301         projection();
00302 
00303         //
00304         // Update size of reduced graph.
00305         //        
00306         reducedGraphSize = 0;
00307         for(i=0; i<graphSize; i++) {
00308             if (adjacentListSize[i] != 0) {
00309                 reducedGraphSize++;
00310             }
00311         }
00312 
00313         //
00314         // Deside whether to start solve stable set or to project again.
00315         //   
00316         if (reducedGraphSize <= MAX_SIZE_OF_GRAPH) {
00317         
00318             //
00319             // Solve the stable set problem for that small graph exactly.
00320             //            
00321             solveStableSet(&theLhs, theRhs, theMaster);
00322 
00323             //
00324             // Lift these inequalities.
00325             //
00326             liftAndStore(&theLhs, theRhs);
00327         
00328             //
00329             // One cut has been computed: stop projection
00330             //
00331             condition = false;
00332         }// if
00333 
00334         //
00335         // Clean up
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     }// while
00346     
00347     //
00348     // Clean up tree.
00349     //
00350     cleanUp();
00351 
00352     // Return status.
00353     return 0;
00354 
00355 }// computeLargeInequality(..)
00356 
00357 
00358 // -----------------------------------------------------------------------------
00359 // g e t L H S
00360 //
00361 // Return lhs of all computed inequalities.
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 // g e t R H S
00376 //
00377 // Return ride hand side of all inequalities.
00378 // -----------------------------------------------------------------------------
00379 vector<int>* EdgeProjection::getRHS() {
00380     return &rhs;
00381 }
00382 
00383 
00384 
00385 // -----------------------------------------------------------------------------
00386 // -------------- M e t h o d s  ( p r i v a t e ) -----------------------------
00387 // -----------------------------------------------------------------------------
00388 
00389 
00390 // -----------------------------------------------------------------------------
00391 // e d g e S e l e c t i o n
00392 //
00393 // Choose randomly two nodes and and go through the adjacent matrix until a
00394 // "good" edge is found. Check if it is projectable. If the neighborhood of the 
00395 // endnode with smaller degree is not a clique, contruct a maximUM clique in
00396 // its neighborhood. 
00397 // -----------------------------------------------------------------------------
00398 bool EdgeProjection::edgeSelection(double *lpValue) {
00399     
00400     int i, j, k;      // Loop counter.
00401     int size;         // Store a size.
00402 
00403     // 
00404     // Select an edge as a candidate for the projection edge.
00405     //
00406     int stack;        // Store something temporarily.
00407     int startNodeOne; // First start node for search.
00408     int startNodeTwo; // Second start node for search.
00409     int nodeOne;
00410     int nodeTwo;
00411     double weight;    // Weight of an edge.
00412     double bestWeight = 0; // Highest weight of an edge.
00413 
00414 
00415     //
00416     // Parameter.
00417     //
00418     // If the sum of the weights of the endnodes of an edge are
00419     // greater than this number then it is a direct candidate for an
00420     // projection edge.
00421     static const double ACCEPT_EDGE = .99;
00422     // Don not accept an edge as projectable edge which as smaller weight
00423     // than NOT_ACCEPT_EDGE. 
00424     static const double NOT_ACCEPT_EDGE = .2;
00425 
00426     
00427     // Choose two random start nodes.
00428     startNodeOne = getRandomNumber(graphSize);
00429     startNodeTwo = getRandomNumber(graphSize);
00430     while (startNodeOne == startNodeTwo) {
00431         startNodeTwo = getRandomNumber(graphSize);
00432     }
00433     // Sort for the adjacent matrix.    
00434     if (startNodeOne < startNodeTwo) {
00435         stack = startNodeOne;
00436         startNodeOne = startNodeTwo;
00437         startNodeTwo = stack;
00438     }    
00439     // Walk through the adjacent matrix.
00440     nodeOne = startNodeOne;
00441     nodeTwo = startNodeTwo;
00442     do { 
00443         // Check if this two nodes are adjacent.
00444         if (lowerAdjacentMatrix[nodeOne-1][nodeTwo]) {
00445             // Calculate weight of edge.
00446             weight = lpValue[nodeOne] + lpValue[nodeTwo];
00447             // Higher weight?
00448             if (weight > bestWeight) {
00449                 // Already an acceptable weight?
00450                 if (weight > ACCEPT_EDGE) {
00451                    // This is our projection edge.
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         }// if
00462 
00463         // Select the next edge.
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     // Check if there was an edge with acceptable weight.
00475     if (bestWeight < NOT_ACCEPT_EDGE) {
00476         return 0;
00477     }
00478      
00479     // 
00480     // Check if this edge is strongly projectable   
00481     //
00482     // Find node with smaller degree.
00483     int index = 0;
00484     if (adjacentListSize[edge[0]] > adjacentListSize[edge[1]]) {
00485         index = 1;
00486     }
00487     // -> edge[index] has smaller degree.
00488     
00489     // Get neighborhood of edge[index]
00490     vector<int> neighborhood;
00491     getNeighborhood(edge[index], &neighborhood);
00492 
00493     // Delte edge[(index+1)%2] from the neighborhood
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     // Check if this node was found.
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         }// for
00519         if (!clique) {
00520             break;
00521         }
00522     }// for
00523 
00524     if (clique) {
00525         // We have found a strongly projectable edge!
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         // Make it a projectable edge.
00542         //
00543         // Construct induced subgraph of neighborhood.
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         // Compute maximAL clique in induced graph of neighborhood.
00555         vector<int> *maxClique;
00556         // This can be any maximAL/maximUM clique generator.
00557         maxClique = computeMaximalClique(&adjacentList, &neighborhood);
00558 
00559         if (maxClique == NULL) {
00560             cout << "ERROR with maximal clique computation." << endl;
00561             exit(1);
00562         }            
00563 
00564         // Tranlsate clique and fill vectors deleteNodes, deleteEdges
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             // Check if neighborhood[i] is in the clique. If it is contained
00576             // this node will be deleted. Otherwise we have to delete an edge.
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                         }// if
00585                         else {
00586                             if (lowerAdjacentMatrix[edge[(index+1)%2]-1][neighborhood[i]]) {
00587                                 deleteNodes.push_back(neighborhood[i]);
00588                             }
00589                         }// else
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             }// while
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         }// for
00608 
00609         // Clean up.
00610         maxClique->clear();
00611         delete maxClique;
00612     }// else
00613 
00614     // Return status.
00615     return 1;
00616 
00617 }// end edgeSelection()
00618 
00619 
00620 // -----------------------------------------------------------------------------
00621 // p r o j e c t i o n
00622 //
00623 // Generate new node of the tree and update the graph.
00624 // Compute all false edges.
00625 // -----------------------------------------------------------------------------
00626 void EdgeProjection::projection() {
00627 
00628     // Store all false edges and pass them to the new node.
00629     vector<int*> falseEdges;
00630 
00631     //
00632     // Update graph:
00633     // Delete projection edge and all nodes to be deleted.
00634     // The endnodes of the projection node will stay in the graph.
00635     //
00636     updateGraph();
00637 
00638     //
00639     // Compute all false edges.
00640     //
00641     computeFalseEdges(&falseEdges);
00642 
00643     //
00644     // Update graph:
00645     // Delete endnodes of the projection edge and add false edges.
00646     //
00647     updateGraph(&falseEdges);
00648 
00649     //
00650     // Add new node to the tree.
00651     //
00652     addNode(&falseEdges);
00653 
00654     // Clean up.
00655     for (int i=falseEdges.size()-1; i>=0; i--) {
00656         delete [] falseEdges[i];
00657         falseEdges[i] = NULL;
00658     }
00659     falseEdges.clear();
00660 
00661 }// end projection()
00662 
00663 
00664 // -----------------------------------------------------------------------------
00665 // s e p a r a t i o n
00666 //
00667 // Construct the graph corresponding to that node of the tree and call
00668 // separation routines for that graph.
00669 // !
00670 // ! The entries of each inequality have to be upwards sorted!!
00671 // !
00672 // -----------------------------------------------------------------------------
00673 int EdgeProjection::separation(double *lpValue, vector< vector<int> > *theLhs,
00674                                 vector<int> *theRhs) {
00675 
00676     int i;      // Loop counter.
00677     int size;
00678 
00679     //
00680     // Get reduced graph.
00681     //
00682     vector< vector<int> > reducedGraph;
00683     getReducedGraph(&reducedGraph);
00684 
00685     //
00686     // Adjust lpValue.
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     // Call separation routines...
00696     //
00697     int numberOfCuts = cliqueSeparation(&reducedGraph, theLPValue, theLhs);
00698 
00699     //
00700     // Update rhs for each inequality.
00701     //
00702     for (i=0; i<numberOfCuts; i++) {
00703         theRhs->push_back(1);
00704     }
00705 
00706     return theLhs->size();
00707 
00708 }// end separation(..)
00709 
00710 
00711 // -----------------------------------------------------------------------------
00712 // l i f t i n g
00713 //
00714 // This function computes the inequalities for the original graph.
00715 // The process is called anti-projection.
00716 // -----------------------------------------------------------------------------
00717 void EdgeProjection::lifting(vector< vector<int> > *theLhs,
00718                              vector<int> *theRhs) {
00719 
00720     int i, j, k;  // Loop variables.
00721     int size;     // Store a size.
00722     int nodeOne;  // One endnode of the false edges.
00723     int nodeTwo;  // The other endnode of the false edges.
00724     int stack;    // Store something temporarily.
00725     int n_inequalities = theLhs->size();  // Number of inequalities.
00726     vector<int*>* theFalseEdges;    // Get the false edges for each node.
00727     vector<int>* theDeletedNodes;   // Get the deleted nodes for each node.
00728     int deletedNodesSize;    // Size of vector 'theDeletedNodes'.
00729     ProjectionNode* aNode;   // A node of the tree.
00730 
00731     //
00732     // Translate this inequality to the labeling of the original graph.
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     // 'Lift' this inequality.
00743     // Therefore check for each node of the tree all false edges
00744     // if they are contained in this inequality.
00745     //
00746     aNode = currentNode;
00747     // Go the way back to the root.
00748     while (aNode != NULL) {
00749         // Get all false edges of tree node 'aNode'
00750         theFalseEdges = aNode->getFalseEdges();
00751 
00752         // Check for each inequality if one of this false edges are contained.
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                 // Check if this two nodes are part of the inequalities
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                 }// while
00773                 if (k == size) {
00774                     // This node is not contained in this inequality.
00775                     continue;
00776                 }
00777                 if ((*theLhs)[i][k] != nodeOne) {
00778                     // This node is not contained in this inequality.
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                     // This node is not contained in this inequality.
00790                     continue;
00791                 }
00792                 if ((*theLhs)[i][k] != nodeTwo) {
00793                     // This node is not contained in this inequality.
00794                     continue;
00795                 }
00796 
00797                 //
00798                 // This false edge is conained in the inequality
00799                 // -> 'lift' this inequality
00800                 //
00801                 // Add all deleted node.
00802                 theDeletedNodes = aNode->getDeletedNodes();
00803                 deletedNodesSize = theDeletedNodes->size();
00804                 for (k=0; k<deletedNodesSize; k++) {
00805                     (*theLhs)[i].push_back((*theDeletedNodes)[k]);
00806                 }
00807                 // Add the projection edge.
00808                 (*theLhs)[i].push_back(aNode->getEdge(0));
00809                 (*theLhs)[i].push_back(aNode->getEdge(1));
00810                 // Sort the inequality.
00811                 sort((*theLhs)[i].begin(), (*theLhs)[i].end());
00812                 // Update the right hand side.
00813                 (*theRhs)[i] += 1;
00814                                 
00815                 // The update of this inequality is finished for this node
00816                 // of the tree. Each edge projection step increases the rhs
00817                 // only by value 1.
00818                 break;
00819             }// end while
00820         }// for
00821         // Get previous node in the tree.
00822         aNode = aNode->getPreviousNode();
00823     }// while
00824 
00825 }// end lifting(..)
00826 
00827 
00828 // -----------------------------------------------------------------------------
00829 // s t o r e I n e q u a l i t i e s
00830 //
00831 // It checks if the new inequalities are still violated. The violated ones are
00832 // stored in the vectors lhs and rhs.
00833 // -----------------------------------------------------------------------------
00834 void EdgeProjection::storeInequalities(vector< vector<int> > *theLhs,
00835                              vector<int> *theRhs, double* lpValue) {
00836 
00837     int i, j, k;          // Loop variables.
00838     int cnt = lhs.size(); // Count the number of inequalities.
00839     int size;             // Store a size.
00840     int numberOfInequalities = theLhs->size();  // Number of inequalities.
00841     double value;         // Value of the LP solution for an inequality.
00842     vector<int> *inequality;  // Store a violated inequality.
00843     bool newOne;          // Indicate if an inequality is a new one.
00844 
00845     //
00846     // Parameter.
00847     //
00848     static const double MIN_VIOLATION = .000001;
00849 
00850 
00851     //
00852     // Overestimate the number of inequalities.
00853     //
00854     lhs.resize(numberOfInequalities + cnt);
00855     rhs.resize(numberOfInequalities + cnt);
00856     slack.resize(numberOfInequalities + cnt);
00857 
00858     //
00859     // Check each inequality and store it.
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         // Check if it is violated.
00868         if (value > ((*theRhs)[i] + MIN_VIOLATION)) {
00869             //
00870             // Check if this inequality was already computed during this
00871             // separation process.
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             }// for
00893 
00894             //
00895             // Store it if it is a new inequality.
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             }// if
00908         }
00909     }// for
00910 
00911     // Correct the size of the vectors.
00912     lhs.resize(cnt);
00913     rhs.resize(cnt);
00914     slack.resize(cnt);
00915 
00916 }// end storeInequalities(..)
00917 
00918 
00919 //
00920 // The struct inequalitiesAndWeights stores an index of an inequality and its
00921 // weight.
00922 //
00923 struct InequalitiesAndWeights {
00924     int    iinequality; // index of an inequality
00925     double weight;      // the weight of an inequality
00926 };
00927 
00928 
00929 //
00930 // This operator is used by the sort function in cleanUpInequalities to get
00931 // a sorted vector of inequalities with decreasing weight.
00932 //
00933 bool operator<(const InequalitiesAndWeights &a, const InequalitiesAndWeights &b) {
00934     return a.weight < b.weight;
00935 }
00936 
00937 
00938 // -----------------------------------------------------------------------------
00939 // c l e a n U p I n e q u a l i t i e s
00940 //
00941 // Select only the best computed inequalities to be stored.
00942 // -----------------------------------------------------------------------------
00943 void EdgeProjection::cleanUpInequalities(double *lpValue) {
00944         
00945     //
00946     // Parameters.
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     // Do not delete inequalities if the number of inequalities is too small.
00957     //
00958     if (size >= MIN_NUMBER) {
00959     
00960         int i;               // Loop counter.
00961         int selectionNumber; // Number of inequalities to be selected.
00962         double m;            // Slop of line.
00963         double c;            // y-intersect of line.
00964         vector<InequalitiesAndWeights> inequalities;
00965     
00966         //
00967         // Calculate weight for each inequality.
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         // Sort the inequalities.
00978         //
00979         sort(inequalities.begin(), inequalities.end());
00980     
00981         //
00982         // Calculate the number of the inequalities to be selected.
00983         //    
00984         if (size >= (MAX_NUMBER * MULTIPLICATOR)) {
00985             selectionNumber = MAX_NUMBER;
00986         }
00987         else {
00988             // Linear interpolation.
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     }// if
01008 
01009 }// end cleanUpInequalities()
01010 
01011 
01012 // -----------------------------------------------------------------------------
01013 // c h e c k S t r o n g P r o j e c t a b i l i t y
01014 //
01015 // Check each edge of the graph if it is strongy projectable.
01016 // All strongly projectable edges are stored in vector 'projectable'.
01017 // -----------------------------------------------------------------------------
01018 void EdgeProjection::checkStrongProjectability() {
01019    
01020     int i, j, k, l, m;// Loop counters.
01021     int size;         // A size of a vector.
01022     int node;         // A node.
01023     int nodeU;        // One endnode u of a candidate for a strongly
01024                       // projectable edge.   
01025     int nodeV;        // The other endnode v of a candidate for a strongly
01026                       // projectable edge.
01027     vector<int> neighborhoodU;  // The neighborhood of node u: N(u). 
01028     int sizeU;        // The size of N(u).
01029     vector<int> neighborhoodV;  // The neighborhood of node v: N(v). 
01030     int sizeV;        // The size of N(v).
01031     vector<int> nUwnV;          // N(u) \ ( N(v) unified v )
01032     int sizeUV;       // The size of N(u) \ ( N(v) unified v ).
01033     vector<int> nVwnU;          // N(v) \ ( N(u) unified u )
01034     int sizeVU;       // The size of N(v) \ ( N(u) unified u ).
01035     vector<int> nUcutnV;        // N(u) cut N(v)
01036     int sizeUCV;      // The size of N(u) cut N(v).
01037     bool clique;      // Indicate if a set is a clique.
01038     int *projectableEdge;     // Pointer to a projectable edge. 
01039     bool bull = false;        // Indicate if a set of nodes defines a bull.
01040     bool diamond = false;     // Indicate if a set of nodes defines a diamond.
01041     
01042     //
01043     // Check each edge if it is strongly projectable.
01044     // 
01045     for (i=1; i<graphSize; i++) {
01046         for (j=0; j<i; j++) {
01047             // Check if ij is an edge in the graph
01048             if (!lowerAdjacentMatrix[i-1][j]) {
01049                 // Consider the next pair of nodes and check if they are
01050                 // adjacent.
01051                 continue;
01052             }
01053             
01054             //
01055             // Check strong projectability of edge uv.
01056             //
01057             // We have to check that edge uv is not an central edge of an 
01058             // induced subgraph isomorphic to a
01059             // ~ diamond
01060             // ~ double fork
01061             // ~ bull
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             // Diamond
01074             //
01075             // Edge uv is NOT the central edge of a diamond, iff there are 
01076             // two nodes a,b which are adjacent to u and v and edge ab is 
01077             // contained in the graph.
01078             //             
01079             
01080             // Construct: N(nodeU) cut N(nodeV)
01081             for (k=0; k<sizeU; k++) {
01082                 node = neighborhoodU[k];
01083                 // Check if this node is contained in neighborhoodV.
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                     // Node is a candidate for the set nUcutnV.
01096                     // Check if 'node' is not adjacent to all other nodes of
01097                     // set nUcutnV.
01098                     size = nUcutnV.empty() ? 0 : nUcutnV.size();
01099                     for (m=0; m<size; m++) {
01100                         // nUcutnV[m] < node for all index m since
01101                         // neighborhoodU is sorted
01102                         if (!lowerAdjacentMatrix[node-1][nUcutnV[m]]) {
01103                             // Edge uv is a central edge of a diamond.
01104                             diamond = true;
01105                             break;
01106                         }
01107                     }
01108                     if (diamond) {
01109                         break;
01110                     }
01111                     // This node is part of N(u) cut N(v) and does not induce
01112                     // a diamond with central edge uv. 
01113                     // -> Store it.
01114                     nUcutnV.push_back(node);
01115                 }// if
01116             }// for
01117 
01118             if (diamond) {
01119                 // Edge uv is a central edge of a diamond.
01120                 // Clean up.
01121                 diamond = false;
01122                 nUcutnV.clear();
01123                 neighborhoodU.clear();
01124                 neighborhoodV.clear();
01125                 // Consider the next edge and check if it 
01126                 // strongly projectable.
01127                 continue; 
01128             }
01129             // Update size.
01130             sizeUCV = !nUcutnV.empty() ? nUcutnV.size() : 0;
01131             
01132             // At this point we know that edge uv is not the central edge of
01133             // a diamond. Therefore check the next condition.
01134                                                             
01135                                                               
01136             //
01137             // Double fork.
01138             //
01139             // Edge uv is NOT the central edge of a double fork, iff
01140             // one of the two sets 
01141             //   N(u) \ ( N(v) unified v ) or
01142             //   N(v) \ ( N(u) unified u )
01143             // defines a clique.
01144             //
01145                                         
01146             // Construct N(u) \ ( N(v) unified v )
01147             l = 0; 
01148             for (k=0; k<sizeU; k++) {
01149                 node = neighborhoodU[k];
01150                 if (node == nodeV) {
01151                     // Check the next node.
01152                     continue;
01153                 }
01154                 // Check if this node is contained in neighborhoodV.
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             }// for
01169             // Update size.
01170             sizeUV = !nUwnV.empty() ? nUwnV.size() : 0;
01171 
01172             clique = true;
01173             if (sizeUV) {
01174                 // Check if the set of nodes nUwnV is a clique.
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             // Now we have to check if set
01189             //   N(v) \ ( N(u) unified u ) 
01190             // is a clique.
01191             // Construct N(v) \ ( N(u) unified u )
01192             l = 0; 
01193             for (k=0; k<sizeV; k++) {
01194                 node = neighborhoodV[k];
01195                 if (node == nodeU) {
01196                     // Check the next node.
01197                     continue;
01198                 }
01199                 // Check if this node is contained in neighborhoodU.
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             }// for
01214             // Update size.
01215             sizeVU = !nVwnU.empty() ? nVwnU.size() : 0;            
01216 
01217             // If N(u) \ ( N(v) unified v ) is a clique, then we know that
01218             // this edge is not a central edge of a double fork. 
01219             // Therefore we have to check the next of the three graphs.   
01220             if (!clique) {
01221                 clique = true;
01222                 if (sizeVU) {
01223                     // Check if the set of nodes nVwnU is a clique.
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                         // At this point we know that edge uv is not
01238                         // strongly projectable since it is a central edge
01239                         // of a double fork.
01240                         // Clean up.
01241                         nUwnV.clear();
01242                         nVwnU.clear();
01243                         nUcutnV.clear();
01244                         neighborhoodU.clear();
01245                         neighborhoodV.clear();
01246                         // Consider the next edge and check if it 
01247                         // strongly projectable.
01248                         continue;
01249                     }
01250                 }
01251             }// if    
01252                 
01253             // At this point we know that edge uv is not a central edge of a
01254             // double fork. Therefor check the last criterion.
01255             
01256             //
01257             // bull
01258             //
01259             // Edge uv is NOT a central edge of a bull, iff there are NOT three 
01260             // nodes k,l,m with 
01261             //   k in N(u) \ ( N(v) unified v )
01262             //   l in N(v) \ ( N(u) unified u )
01263             //   m in N(u) cut N(v)
01264             // and all three edges
01265             //   kl, km, lm
01266             // are not contained in the graph.
01267             // 
01268             
01269             // Check if one of the three sets is empty.            
01270             if (!nUcutnV.empty() && !nUwnV.empty() && !nVwnU.empty()) {
01271                 // Check each combination of the three sets.
01272                 for (k=0; k<sizeUV; k++) {
01273                     for (l=0; l<sizeVU; l++) {
01274                         for (m=0; m<sizeUCV; m++) {
01275                             // Check kl 
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                             // Check km
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                             // Check lm
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                         } // for
01313                         if (bull) {
01314                            break;
01315                         }
01316                     } // for
01317                     if (bull) {
01318                         break;
01319                     }
01320                 }// for
01321                 if (bull) {
01322                     // At this point we know that edge uv is not
01323                     // strongly projectable since it is a central edge
01324                     // of a bull.
01325                     // Clean up.
01326                     bull = false;                
01327                     nUwnV.clear();
01328                     nVwnU.clear();
01329                     nUcutnV.clear();
01330                     neighborhoodU.clear();
01331                     neighborhoodV.clear();
01332                     // Consider the next edge and check if it 
01333                     // strongly projectable.
01334                     continue;
01335                 }
01336             } // if
01337             
01338             //
01339             // All the computational effort was not wasted and we have indeed
01340             // found a strongly projectable edge!
01341             //
01342             projectableEdge = new int[2];
01343             projectableEdge[0] = nodeU;
01344             projectableEdge[1] = nodeV;
01345             projectable.push_back(projectableEdge);
01346             
01347             // Clean up.   
01348             nUwnV.clear();
01349             nVwnU.clear();
01350             nUcutnV.clear();
01351             neighborhoodU.clear();
01352             neighborhoodV.clear();
01353             
01354         }// for
01355     }// for 
01356     
01357 }// end checkStrongProjectability()
01358 
01359 
01360 // -----------------------------------------------------------------------------
01361 // c o m p u t e M a x i m a l C l i q u e
01362 //
01363 // This function computes a maximAL clique. The graph is given through the 
01364 // parameters. This function is udes to make an edge strongly projectable.
01365 // -----------------------------------------------------------------------------
01366 vector<int>* EdgeProjection::computeMaximalClique(
01367             vector< vector<int> > *theAdjacentList, vector<int> *theTranslator) {
01368 
01369     int i;                      // Loop counter.
01370     int cnt = 0;
01371     int size = theAdjacentList->size();
01372     vector<int> clique(2);      // This will be increased to a maximAL clique.
01373     vector<int> adjacentNodes;  // All adjacent nodes to the clique.
01374     vector<int> *maxClique;     // Store a maximAL clique.
01375                                 // This will be the return value.
01376     maxClique = new vector<int>;
01377     int maxCliqueSize = 0;      // Size of maximAL clique.
01378     bool found;
01379 
01380     //
01381     // Parameter.
01382     //
01383     const int MAX_ITER = size * 2;
01384 
01385 
01386     //
01387     // Avoid degenerated cases.
01388     //
01389     if (theAdjacentList->empty()) {
01390         return NULL;
01391     }
01392     // Check if there is at least one edge.
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     // Construct maximal cliques.
01406     //
01407     cnt = 0;
01408     while (cnt < MAX_ITER) {
01409 
01410         //
01411         // Select edge to start from.
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                     // theTranslator is sorted!
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             }// if
01430         }// while
01431 
01432         //
01433         // Get list of adjacent nodes to this edge.
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         }// for
01452         
01453         
01454         //
01455         // Construct maximal clique
01456         //
01457         while (!adjacentNodes.empty() && (adjacentNodes.size() + clique.size()) > maxCliqueSize) {
01458             clique.push_back(adjacentNodes.back());
01459             adjacentNodes.pop_back();
01460             // Update adjacent nodes.
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         // Update max clique.
01478         //
01479         if ((adjacentNodes.size() + clique.size()) > maxCliqueSize) {
01480            // Update maximUM clique.
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     }// while
01491 
01492     return maxClique;
01493 
01494 }// end computeMaximalClique(..)
01495 
01496 
01497 // -----------------------------------------------------------------------------
01498 // c o m p u t e F a l s e E d g e s
01499 //
01500 // Let u and v denote the endnodes of the projection edge.
01501 // False edges of the projection of edge uv are between each two nodes of the
01502 // neighborhood of u and the neighborhood of v in the reduced graph.
01503 // This reduced graph contains nodes u and v but not the deleted nodes and not
01504 // the projection edge uv.
01505 // -----------------------------------------------------------------------------
01506 void EdgeProjection::computeFalseEdges(vector<int*> *falseEdges) {
01507 
01508     // Store the neighbothood of node u and of node v.
01509     vector<int> neighborhoodU;
01510     vector<int> neighborhoodV;
01511 
01512     //
01513     // Compute the neighborhoods of node u and v.
01514     //
01515     getNeighborhood(edge[0], &neighborhoodU);
01516     getNeighborhood(edge[1], &neighborhoodV);
01517 
01518     //
01519     // Now we are ready to compute all false edges.
01520     //
01521     int i, j;        // Loop variables.
01522     int nodeOne;
01523     int nodeTwo;
01524     int *falseEdge;  // Store a false edge.
01525     int sizeU = neighborhoodU.size();
01526     int sizeV = neighborhoodV.size();
01527     // Compute all combinations.
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     }// for
01550 
01551 }// end computeFalseEdges(..)
01552 
01553 
01554 // -----------------------------------------------------------------------------
01555 // g e t N e i g h b o r h o o d
01556 //
01557 // This function returns the neighborhood of node 'node' in the reduction graph.
01558 // Therefore it goes in the adjacent matrix trough the list of adjacent
01559 // nodes to 'node' and stores them.
01560 // -----------------------------------------------------------------------------
01561 void EdgeProjection::getNeighborhood(int node, vector<int> *neighborhood) {
01562 
01563     int i, j;    // Loop variable.
01564     int vertex;  // Store a node.
01565 
01566     //
01567     // Compute the neighborhood of node 'node'.
01568     //
01569     for (i=0; i<node; i++) {
01570         if (lowerAdjacentMatrix[node-1][i]) {
01571             neighborhood->push_back(i);
01572         }
01573     }// for
01574     for (j=i+1; j<graphSize; j++) {
01575         if (lowerAdjacentMatrix[j-1][node]) {
01576             neighborhood->push_back(j);
01577         }
01578     }// for
01579 
01580 }// end getNeighborhood(..)
01581 
01582 
01583 // -----------------------------------------------------------------------------
01584 // u p d a t e G r a p h
01585 //
01586 // This is an overloaded function.
01587 // Delete projection edge and all nodes to be deleted.
01588 // The endnodes of the projection node will stay in the graph. They are deleted
01589 // in the other function 'updateGraph'.
01590 // !
01591 // ! Important: The first node in vector deleteEdges is node u or v.
01592 // !
01593 // -----------------------------------------------------------------------------
01594 void EdgeProjection::updateGraph() {
01595 
01596     int i, j, k, l; // Loop variables.
01597     int node;       // Store a node.
01598     int vertex;     // Store another node.
01599     int size;       // Store a size.
01600 
01601     //
01602     // Delete the projection edge.
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     // Delete all edges of vector 'deleteEdges'.
01613     // This is done in order to get a strongly projectable edge.
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         // Update size of the adjacent list.
01626         adjacentListSize[vertex] -= 1;
01627     }// for
01628 
01629     //
01630     // Delete all nodes of vector 'deleteNodes'.
01631     //
01632     size = deleteNodes.size();
01633     for (i=0; i<size; i++) {
01634         node = deleteNodes[i];
01635         adjacentListSize[node] = 0;
01636         // Go through the neighborhood of node 'node'.
01637         for (j=0; j<node; j++) {
01638             if (lowerAdjacentMatrix[node-1][j]) {
01639                 lowerAdjacentMatrix[node-1][j] = 0;
01640                 // Update size of adjacent list
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                         // Add this edge to the deleted edges.
01650                         int *anEdge = new int[2];
01651                         anEdge[0] = node;
01652                         anEdge[1] = j;
01653                         deleteEdges.push_back(anEdge);
01654                     }
01655                 }// if
01656             }// if
01657         }// for
01658         for (k=j+1; k<graphSize; k++) {
01659             if (lowerAdjacentMatrix[k-1][node]) {
01660                 lowerAdjacentMatrix[k-1][node] = 0;
01661                 // Update size of adjacent list
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                         // Add this edge to the deleted edges.
01671                         int *anEdge = new int[2];
01672                         anEdge[0] = node;
01673                         anEdge[1] = k;
01674                         deleteEdges.push_back(anEdge);
01675                     }
01676                 }// if
01677             }
01678         }// for
01679     }// for
01680 
01681 }// end updateGraph()
01682 
01683 
01684 // -----------------------------------------------------------------------------
01685 // u p d a t e G r a p h
01686 //
01687 // This is an overloaded function.
01688 // Delete the two endnodes of the projection edge and add all false edges.
01689 // -----------------------------------------------------------------------------
01690 void EdgeProjection::updateGraph(vector<int*> *falseEdges) {
01691 
01692     int i, j, k; // Loop variables.
01693     int node;    // Store a node.
01694     int vertex;  // Store another node.
01695     int size;    // Store a size.
01696     int *anEdge; // A deleted egde.
01697 
01698     //
01699     // Delete both endnodes of the projection edge from the graph.
01700     //
01701     for (i=0; i<2; i++) {
01702         node = edge[i];
01703         adjacentListSize[node] = 0;
01704         // Go through the neighborhood of node 'node'.
01705         for (j=0; j<node; j++) {
01706             if (lowerAdjacentMatrix[node-1][j]) {
01707                 lowerAdjacentMatrix[node-1][j] = 0;
01708                 // Update size of adjacent list
01709                 adjacentListSize[j] -= 1;
01710                 // Add this edge to the deleted edges.
01711                 anEdge = new int[2];
01712                 anEdge[0] = node;
01713                 anEdge[1] = j;
01714                 deleteEdges.push_back(anEdge);
01715             }
01716         }// for
01717         for (k=j+1; k<graphSize; k++) {
01718             if (lowerAdjacentMatrix[k-1][node]) {
01719                 lowerAdjacentMatrix[k-1][node] = 0;
01720                 // Update size of adjacent list
01721                 adjacentListSize[k] -= 1;
01722                 // Add this edge to the deleted edges.
01723                 anEdge = new int[2];
01724                 anEdge[0] = k;
01725                 anEdge[1] = node;
01726                 deleteEdges.push_back(anEdge);
01727             }
01728         }// for
01729     }// for
01730 
01731 
01732     //
01733     // Add false edges.
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     }// for
01748 
01749 }// end updateGraph(..)
01750 
01751 
01752 // -----------------------------------------------------------------------------
01753 // a d d N o d e
01754 //
01755 // Add a new node to the tree.
01756 // -----------------------------------------------------------------------------
01757 void EdgeProjection::addNode(vector<int*> *falseEdges) {
01758 
01759     //
01760     // If currentNode == NULL
01761     // -> tree is empty
01762     // -> make new node
01763     //
01764     if (currentNode == NULL) {
01765         // New node.
01766         ProjectionNode *pN;
01767         pN = new ProjectionNode(edge, &deleteNodes, &deleteEdges, falseEdges,
01768                                 NULL);
01769 
01770         // Store it in the vector.
01771         itsNodes.push_back(pN);
01772         // Update pointer to current node.
01773         currentNode = pN;
01774     }
01775     else {
01776         // Make new node in the correct part of the tree
01777         // and update current node.
01778         currentNode = currentNode->addNode(edge, &deleteNodes, &deleteEdges,
01779                                            falseEdges);
01780     }
01781 
01782 }// end addNode(..)
01783 
01784 
01785 // -----------------------------------------------------------------------------
01786 // g e t R e d u c e d G r a p h
01787 //
01788 // Compute the reduced graph from the adjacent matrix.
01789 // Ignore isolated nodes!!
01790 // -----------------------------------------------------------------------------
01791 void EdgeProjection::getReducedGraph(vector< vector<int> > *reducedGraph) {
01792 
01793     int i, j;     // Loop variables.
01794     int cnt = 0;  // Loop counter.
01795     int cnt2 = 0; // Another loop counter.
01796     int reducedGraphSize; // Size of the new reduced graph.
01797 
01798     //
01799     // Translation for the construction of the graph
01800     //
01801     int translateNode[graphSize];
01802     // Clean this vector.
01803     if (!translator.empty()) {
01804         translator.clear();
01805     }
01806     // Overestimate size of graph
01807     translator.resize(graphSize);
01808     for (i=0; i<graphSize; i++) {
01809         if (adjacentListSize[i] != 0) {
01810             translateNode[i] = cnt;
01811             // Translator for restranslation of reduced graph to original graph
01812             translator[cnt] = i;
01813             cnt++;
01814         }
01815         else {
01816             translateNode[i] = -1;
01817         }
01818     }
01819     // Correct the vector size.
01820     translator.resize(cnt);
01821 
01822     //
01823     // Construct reduced graph
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     }// for
01847 
01848 }// end getReducedGraph(..)
01849 
01850 
01851 // -----------------------------------------------------------------------------
01852 // c l i q u e S e p a r a t i o n
01853 // -----------------------------------------------------------------------------
01854 int EdgeProjection::cliqueSeparation(vector< vector<int> > *graph,
01855                                      double *lpValue,
01856                                      vector< vector<int> > *theLhs) {
01857 
01858     int i, j;     // Loop counter.
01859     int index;
01860     double value; // Value of a computed clique.
01861     int numberOfCutsBeginning = theLhs->size();
01862     int numberOfCuts = numberOfCutsBeginning;
01863     vector<int> clique(2);     // Store the maximAL clique.
01864     vector<int> adjacentNodes; // All adjacent nodes to that clique.
01865     int size = graph->size();  // size of the current problem.
01866     vector<int*> *falseEdges = currentNode->getFalseEdges();
01867     int falseEdgesCnt = 0;     // Number of false edges in that node of the
01868                                // tree.
01869     int cnt = 0;
01870     bool found;
01871     bool newOne;               // Indicate if that inequality has not been
01872                                // generated.
01873     bool STOP = false;
01874     int theCnt = 0;
01875     int cutCnt = 0;
01876 
01877     //
01878     // Parameter.
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     // Construct maximal cliques.
01887     //
01888     while ( (cnt < MAX_ITER_SEP) ) { // || theCnt < MAX_STEP) && (cutCnt < MAX_CUTS) ) {
01889 
01890         //
01891         // Select edge to start from.
01892         //
01893         if (falseEdgesCnt < falseEdges->size()) {
01894             clique[0] = (*falseEdges)[falseEdgesCnt][0];
01895             // Translate this nodes:
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             // Translate this nodes:
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                 }// if
01941             }// while
01942         }
01943 
01944         //
01945         // Get list of adjacent nodes to this edge.
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         // Construct a maximAL clique containing this egde.
01967         //
01968         while(!adjacentNodes.empty()) {
01969             index = getRandomNumber(adjacentNodes.size());
01970             clique.push_back(adjacentNodes[index]);
01971             adjacentNodes.erase(adjacentNodes.begin() + index);
01972             // Update adjacent nodes.
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         // Check if this inequality is violated.
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             // Store this inequality if it is a new one.
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             }// if
02024         }// if
02025 
02026         clique.clear();
02027         adjacentNodes.clear();
02028         clique.resize(2);
02029         cnt++;
02030     }
02031 
02032     return cutCnt;
02033 
02034 }// end cliqueSeperation(..)
02035 
02036 
02037 // -----------------------------------------------------------------------------
02038 // s o l v e S t a b l e S e t
02039 //
02040 // Solve the maximum-cardinality stable set problem for that graph exact.
02041 // Call therefore the stable set solver and store the corresponding rank
02042 // inequality.
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     // Write file with information about the graph.
02056     //
02057     int numberOfNodes = 0;
02058     int numberOfEdges = 0;
02059     translator.clear();
02060     translator.resize(graphSize, -1);
02061 
02062     // Calculate number of nodes and number of edges.
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     // Generate new stable set object and solve the maximum
02088     // cardinality stable set problem for that small graph.
02089     //
02090     StableSetMaster *stableSet;  
02091     stableSet = new StableSetMaster(theGraph.c_str(), inequalities.c_str(),//
02092                                     "DUMMY");
02093     // No output on screan.
02094     stableSet->outLevel(ABA_MASTER::Silent);
02095     ABA_STRING theAbaString(stableSet, "00:00:01");
02096     stableSet->maxCpuTime(theAbaString);
02097     // Optimize.    
02098     ABA_MASTER::STATUS error = stableSet->optimize();
02099 
02100     //
02101     // Check optimality.
02102     //
02103     if (error) {
02104         exit(1);
02105     }
02106 /*
02107     string check("./CheckInequalities.exe ");
02108     check.append("~/Diplomarbeit/Abacus/Stable_Set/");
02109     check.append(graph);
02110     check.append(" ");
02111     check.append(inequalities);
02112 
02113     theMaster->stopTimer();
02114     theMaster->out() << "\n\nCheck inequalities:" << endl;
02115     theMaster->out() << "----------------------------";
02116     theMaster->out() << "------------------------\n" << endl;
02117 
02118     // Call program to check all inequalities.
02119     int notValid = system(check.c_str());
02120     check.clear(); 
02121 
02122     theMaster->out() << "----------------------------";
02123     theMaster->out() << "------------------------\n" << endl;
02124     theMaster->startTimer();
02125 
02126     if (notValid) {
02127         exit(1);
02128     }
02129 */
02130         
02131     //
02132     // Construct inequality.
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     // Clean up.
02142     delete stableSet;    
02143 
02144 }// end solveStableSet(..)
02145 
02146 
02147 // -----------------------------------------------------------------------------
02148 // l i f t A n d S t o r e
02149 //
02150 // Make the rank inequality valid for the whole graph which is called anti-
02151 // projection. Store the inequality after that.
02152 // -----------------------------------------------------------------------------
02153 void EdgeProjection::liftAndStore(vector<int> *theLhs, int theRhs) {
02154 
02155     int i, j, k;  // Loop variables.
02156     int size;     // Store a size.
02157     int nodeOne;  // One endnode of the false edges.
02158     int nodeTwo;  // The other endnode of the false edges.
02159     int stack;    // Store something temporarily.
02160     vector<int*>* theFalseEdges;    // Get the false edges for each node.
02161     vector<int>* theDeletedNodes;   // Get the deleted nodes for each node.
02162     int deletedNodesSize;    // Size of vector 'theDeletedNodes'.
02163     ProjectionNode* aNode;   // A node of the tree.
02164     
02165     rhs.resize(1);
02166     rhs[0] = theRhs;    
02167 
02168 
02169     //
02170     // 'Lift' this inequality.
02171     // Therefore check for each node of the tree all false edges
02172     // if they are contained in this inequality.
02173     //
02174     aNode = currentNode;
02175     // Go the way back to the root.
02176     while (aNode != NULL) {
02177 
02178         // Get all false edges of tree node 'aNode'
02179         theFalseEdges = aNode->getFalseEdges();
02180 
02181         // Check if one of this false edges are contained.
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             // Check if this two nodes are part of the inequalities
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             }// while
02201             if (k == size) {
02202                 // This node is not contained in this inequality.
02203                 continue;
02204             }
02205             if ((*theLhs)[k] != nodeOne) {
02206                 // This node is not contained in this inequality.
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                 // This node is not contained in this inequality.
02218                 continue;
02219             }
02220             if ((*theLhs)[k] != nodeTwo) {
02221                 // This node is not contained in this inequality.
02222                 continue;
02223             }
02224             //
02225             // This false edge is conained in the inequality
02226             // -> 'lift' this inequality
02227             //
02228             // Add all deleted node.
02229             theDeletedNodes = aNode->getDeletedNodes();
02230             deletedNodesSize = theDeletedNodes->size();
02231             for (k=0; k<deletedNodesSize; k++) {
02232                 theLhs->push_back((*theDeletedNodes)[k]);
02233             }
02234             
02235             // Add the projection edge.
02236             theLhs->push_back(aNode->getEdge(0));
02237             theLhs->push_back(aNode->getEdge(1));
02238             
02239             // Sort the inequality.
02240             sort(theLhs->begin(), theLhs->end());
02241                 // Update the right hand side.
02242                 rhs[0] += 1;
02243                                 
02244             // The update of this inequality is finished for this node
02245             // of the tree. Each edge projection step increases the rhs
02246             // only by value 1.
02247             break;
02248         }// end while
02249         
02250         // Get previous node in the tree.
02251         aNode = aNode->getPreviousNode();
02252     }// while
02253 
02254     //
02255     // Store this inequality
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 }// end lifting(..)
02265 
02266 
02267 // -----------------------------------------------------------------------------
02268 // g e t R a n d o m N u m b e r
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 // C l e a n U p
02280 // -----------------------------------------------------------------------------
02281 void EdgeProjection::cleanUp() {
02282 
02283     int i, j;               // Loop variables.
02284     int nodeOne;            // One endnode of the projection edge.
02285     int nodeTwo;            // The other endnode of the projection edge.
02286     int size;               // Store the size of a vector.
02287     vector<int> *nodes;     // Get some nodes.
02288     vector<int*> *edges;    // Get some edges.
02289 
02290     //
02291     // Reconstruct graph.
02292     // At the end of this loop is currentNode = NULL.
02293     //
02294     while (currentNode != NULL) {
02295 
02296         //
02297         // Add projection edge.
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         // Add clique build by all deleted nodes including the two endnodes
02312         // of the projection edge.
02313         //
02314         nodes = currentNode->getDeletedNodes();
02315         size = nodes->size();
02316         for (i=0; i<size; i++) {
02317             // Add edge to nodeOne.
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             // Add edge to node two.
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             // Add edges to all other deleted nodes.
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             }// for
02348         }// for
02349 
02350         //
02351         // Add all other deleted edges.
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         }// for
02365 
02366         //
02367         // Delete all false edges.
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         }// for
02381 
02382         //
02383         // Go one step back in the tree.
02384         //
02385         currentNode = currentNode->getPreviousNode();
02386     }// while
02387 
02388     // Call the destructor of each node.
02389     for (int i=itsNodes.size()-1; i>=0; i--) {
02390         delete itsNodes[i];
02391         itsNodes[i] = NULL;
02392     }
02393     itsNodes.clear();
02394 
02395 }// end cleanUp()
02396 
02397 
02398 // -----------------------------------------------------------------------------
02399 // p r i n t R o o t
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 }// end printRoot()
02419 
02420 
02421 
02422 
02423 // *****************************************************************************
02424 //
02425 // Old code fragments.
02426 //
02427 // *****************************************************************************
02428 
02429 /*
02430 // -----------------------------------------------------------------------------
02431 // e d g e S e l e c t i o n
02432 //
02433 // Select a projctable edge. Consider first the strongly projectable edges. 
02434 // If there is no good one, check randomly other edges and ???
02435 // -----------------------------------------------------------------------------
02436 void EdgeProjection::edgeSelection(double *lpValue) {
02437 cout << "Edge selection:" << endl;
02438     
02439     int i, j, k;      // Loop counter.
02440     int size;         // Store a size.
02441 
02442     int stack;        // Store something temporarily.
02443     int startNodeOne; // First start node for search.
02444     int startNodeTwo; // Second start node for search.
02445     int nodeOne;
02446     int nodeTwo;
02447     double weight;    // Weight of an edge.
02448     double bestWeight = 0; // Highest weight of an edge.
02449     bool edgeFound = true;
02450     
02451     
02452     //
02453     // Consider first the strongly projectable edges.
02454     //
02455 //    if (phase == 1) {
02456     if (!projectable.empty()) {
02457         // -> !projectable.empty()
02458         size = projectable.size();
02459         for (i=0; i<size; i++) {
02460             weight = lpValue[projectable[i][0]] + lpValue[projectable[i][1]];
02461             // Higher weight?
02462             if (weight > bestWeight) {
02463                 // Update edge and weight.
02464                 bestWeight = weight;
02465                 edge[0] = projectable[i][0];
02466                 edge[1] = projectable[i][1];
02467 
02468                 // Already an acceptable weight?
02469                 if (weight > ACCEPT_EDGE) {
02470                     break;
02471                 }
02472             }// if
02473         }// for
02474 
02475         if (weight > NOT_ACCEPT_EDGE) {
02476             // Delete this edge from vector 'projectable'.        
02477             delete[] projectable[i];
02478             projectable[i] = NULL;
02479             projectable.erase(projectable.begin() + i);
02480 //            projectableEdge = true;
02481         }
02482         else {
02483             edgeFound = false;
02484         }
02485     }// if
02486     
02487     
02488 //    if ((phase != 1) || !edgefound) {
02489     if (projectable.empty() || !edgeFound) {
02490         // Choose two random start nodes.
02491         startNodeOne = getRandomNumber(graphSize);
02492         startNodeTwo = getRandomNumber(graphSize);
02493         while (startNodeOne == startNodeTwo) {
02494             startNodeTwo = getRandomNumber(graphSize);
02495         }
02496         // Sort for the adjacent matrix.    
02497         if (startNodeOne < startNodeTwo) {
02498             stack = startNodeOne;
02499             startNodeOne = startNodeTwo;
02500             startNodeTwo = stack;
02501         }    
02502         // Walk through the adjacent matrix.
02503         nodeOne = startNodeOne;
02504         nodeTwo = startNodeTwo;
02505         do { 
02506             // Check if this two nodes are adjacent.
02507             if (lowerAdjacentMatrix[nodeOne-1][nodeTwo]) {
02508                 // Calculate weight of edge.
02509                 weight = lpValue[nodeOne] + lpValue[nodeTwo];
02510                 // Higher weight?
02511                 if (weight > bestWeight) {
02512                     // Already an acceptable weight?
02513                     if (weight > ACCEPT_EDGE) {
02514                        // This is our projection edge.
02515                        bestWeight = weight;
02516                        edge[0] = nodeOne;
02517                        edge[1] = nodeTwo;
02518                        break;
02519                     }
02520                     bestWeight = weight;
02521                     edge[0] = nodeOne;
02522                     edge[1] = nodeTwo;
02523                 }
02524             }// if
02525             // Select the next edge.
02526             nodeTwo++;
02527             if (nodeTwo == nodeOne) {
02528                 nodeOne++;
02529                 nodeTwo = 0;
02530                 if (nodeOne == graphSize) {
02531                     nodeOne = 1;
02532                 }
02533             }
02534         } while ((nodeOne != startNodeOne) || (nodeTwo != startNodeTwo)); 
02535     
02536         // Check if there was an edge with acceptable weight.
02537         if (bestWeight < NOT_ACCEPT_EDGE) {
02538             cout << "No projection edge could be found.";
02539             exit(1);
02540         }    
02541      
02542      
02543         // 
02544         // Check if this edge is strongly projectable.
02545         // In this case we only check if its neighborhood, without the other 
02546         // endnode of the projection edge, is a clique.   
02547         //
02548         
02549         // Find node with smaller degree.
02550         int index = 0;
02551         if (adjacentListSize[edge[0]] > adjacentListSize[edge[1]]) {
02552             index = 1;
02553         }
02554         // -> edge[index] has smaller degree.
02555     
02556         // Get neighborhood of edge[index]
02557         vector<int> neighborhood;
02558         getNeighborhood(edge[index], &neighborhood);
02559         // Delte edge[(index+1)%2] from the neighborhood
02560         i = 0;
02561         size = neighborhood.size();
02562         while (i < size) {
02563             if (neighborhood[i] == edge[(index+1)%2]) {
02564                 neighborhood.erase(neighborhood.begin()+i);
02565                 size--;
02566                 break;
02567             }
02568             i++;
02569         }
02570 //cout << "neighborhood of " << edge[index] << endl << "\t";
02571 //for (j=0; j<neighborhood.size();j++) cout << neighborhood[j] << " ";
02572 //cout << endl;
02573 
02574         // Check if neighborhood is a clique.
02575         bool clique = true;
02576         for (i=0; i<size-1; i++) {
02577             for (j=i+1; j<size; j++) {
02578                 if (!lowerAdjacentMatrix[neighborhood[j]-1][neighborhood[i]]) {
02579 //cout << "nodes " << neighborhood[j] << " and " << neighborhood[i] << " are not adjacent" << endl;
02580                     clique = false;
02581                     break;
02582                 }
02583             }// for
02584             if (!clique) {
02585                 break;
02586             }
02587         }// for
02588 
02589 //cout << "\tProjection edge:\t" << edge[0] << " " << edge[1] << endl;
02590         if (clique) {
02591             // We have found a strongly projectable edge!
02592             for (i=0; i<size; i++) {
02593                 if (neighborhood[i] > edge[(index+1)%2]) {
02594                     if (lowerAdjacentMatrix[neighborhood[i]-1][edge[(index+1)%2]]) {
02595                         deleteNodes.push_back(neighborhood[i]);
02596                     }
02597                 }
02598                 else {
02599                     if (lowerAdjacentMatrix[edge[(index+1)%2]-1][neighborhood[i]]) {
02600                         deleteNodes.push_back(neighborhood[i]);
02601                     }
02602                 }
02603             }
02604 cout << "\tNeighborhood of node " << edge[index] << " is a clique." << endl;
02605         }
02606         else {
02607             //
02608             // Make it a projectable edge.
02609             //
02610 cout << "\tNeighborhood of node " << edge[index] << " is NO clique." << endl;
02611             
02612             // Construct induced subgraph of neighborhood.
02613             vector< vector<int> > adjacentList(size);
02614             for (i=0; i<size-1; i++) {
02615                 for (j=i+1; j<size; j++) {
02616                     if (lowerAdjacentMatrix[neighborhood[j]-1][neighborhood[i]]) {
02617                         adjacentList[i].push_back(j);
02618                         adjacentList[j].push_back(i);
02619                     }
02620                 }                
02621             }        
02622 
02623             // Compute maximAL clique in induced graph of neighborhood.
02624             vector<int> *maxClique;
02625             // This can be any maximAL/maximUM clique generator.
02626             maxClique = computeMaximalClique(&adjacentList, &neighborhood);
02627 if (maxClique == NULL) {
02628     cout << "ERROR with maximal clique computation." << endl;
02629     exit(0);
02630 }            
02631             // Tranlsate clique and fill vectors deleteNodes, deleteEdges
02632             int cliqueSize = maxClique->size();
02633             for (i=0; i<cliqueSize; i++) {
02634                 (*maxClique)[i] = neighborhood[(*maxClique)[i]];
02635             }
02636             sort(maxClique->begin(), maxClique->end());
02637 cout << "\tMaximum clique:\t";
02638 for(i=0; i<maxClique->size(); i++) cout << (*maxClique)[i] << " ";
02639 cout << endl;
02640             deleteEdges.resize(size - cliqueSize);
02641             int edgesCnt = 0;
02642             int *anEdge;
02643             j = 0;
02644             for (i=0; i<size; i++) {
02645                 // Check if neighborhood[i] is in the clique. If it is contained
02646                 // this node will be deleted. Otherwise we have to delete an edge.
02647                 while (j < cliqueSize) {
02648                     if ((*maxClique)[j] >= neighborhood[i]) {
02649                         if ((*maxClique)[j] == neighborhood[i]) {
02650                             if (neighborhood[i] > edge[(index+1)%2]) {
02651                                 if (lowerAdjacentMatrix[neighborhood[i]-1][edge[(index+1)%2]]) {
02652                                     deleteNodes.push_back(neighborhood[i]);
02653                                 }
02654                             }// if
02655                             else {
02656                                 if (lowerAdjacentMatrix[edge[(index+1)%2]-1][neighborhood[i]]) {
02657                                     deleteNodes.push_back(neighborhood[i]);
02658                                 }
02659                             }// else
02660                         }
02661                         else {
02662                             anEdge = new int[2];
02663                             anEdge[0] = edge[index];
02664                             anEdge[1] = neighborhood[i];
02665                             deleteEdges[edgesCnt++] = anEdge;
02666                         }
02667                         break;
02668                     }
02669                     j++;
02670                 }// while
02671                 if (j == cliqueSize) {
02672                     anEdge = new int[2];
02673                     anEdge[0] = edge[index];
02674                     anEdge[1] = neighborhood[i];
02675                     deleteEdges[edgesCnt++] = anEdge;
02676                 }
02677             }// for
02678 
02679             // Clean up.
02680             maxClique->clear();
02681         }// else
02682     }// if
02683 
02684 cout << "\tDelete nodes:\t";
02685 for(i=0;i<deleteNodes.size();i++) cout << deleteNodes[i] << " ";
02686 cout << "\n\tDelete edges:\t";
02687 for(i=0;i<deleteEdges.size();i++) cout << deleteEdges[i][0] << " " << deleteEdges[i][1] << "; ";
02688 cout << endl << endl << endl;
02689 
02690 }// end edgeSelection()
02691 
02692 
02693 
02694 // -----------------------------------------------------------------------------
02695 // e d g e S e l e c t i o n
02696 //
02697 // Choose randomly two nodes and and go through the adjacent matrix until a "good"
02698 // edge is found. Check if it is projectable. If the neighborhood of the 
02699 // endnode with smaller degree is not a clique, contruct a maximUM clique in
02700 // its neighborhood. 
02701 // -----------------------------------------------------------------------------
02702 void EdgeProjection::edgeSelection(double *lpValue) {
02703 cout << "Edge selection:" << endl;
02704     
02705     int i, j, k;      // Loop variables.
02706     int size;         // Store a size.
02707 
02708     // 
02709     // Select an edge as a candidate for the projection edge.
02710     //
02711     int stack;        // Store something temporarily.
02712     int startNodeOne; // First start node for search.
02713     int startNodeTwo; // Second start node for search.
02714     int nodeOne;
02715     int nodeTwo;
02716     double weight;    // Weight of an edge.
02717     double bestWeight = 0; // Highest weight of an edge.
02718     
02719     // Choose two random start nodes.
02720     startNodeOne = getRandomNumber(graphSize);
02721     startNodeTwo = getRandomNumber(graphSize);
02722     while (startNodeOne == startNodeTwo) {
02723         startNodeTwo = getRandomNumber(graphSize);
02724     }
02725     // Sort for the adjacent matrix.    
02726     if (startNodeOne < startNodeTwo) {
02727         stack = startNodeOne;
02728         startNodeOne = startNodeTwo;
02729         startNodeTwo = stack;
02730     }    
02731     // Walk through the adjacent matrix.
02732     nodeOne = startNodeOne;
02733     nodeTwo = startNodeTwo;
02734     do { 
02735 //cout << nodeOne << " " << nodeTwo << " ";
02736         // Check if this two nodes are adjacent.
02737         if (lowerAdjacentMatrix[nodeOne-1][nodeTwo]) {
02738             // Calculate weight of edge.
02739             weight = lpValue[nodeOne] + lpValue[nodeTwo];
02740 //cout << weight;
02741             // Higher weight?
02742             if (weight > bestWeight) {
02743                 // Already an acceptable weight?
02744                 if (weight > ACCEPT_EDGE) {
02745                    // This is our projection edge.
02746                    bestWeight = weight;
02747                    edge[0] = nodeOne;
02748                    edge[1] = nodeTwo;
02749 //cout << endl;
02750                    break;
02751                 }
02752                 bestWeight = weight;
02753                 edge[0] = nodeOne;
02754                 edge[1] = nodeTwo;
02755             }
02756         }// if
02757 //cout << endl;
02758         // Select the next edge.
02759         nodeTwo++;
02760         if (nodeTwo == nodeOne) {
02761             nodeOne++;
02762             nodeTwo = 0;
02763             if (nodeOne == graphSize) {
02764                 nodeOne = 1;
02765             }
02766         }
02767     } while ((nodeOne != startNodeOne) || (nodeTwo != startNodeTwo)); 
02768 //cout << edge[0] << " " << edge[1] << " " << bestWeight << endl;
02769     
02770     // Check if there was an edge with acceptable weight.
02771     if (bestWeight < NOT_ACCEPTABLE) {
02772         cout << "No projection edge could be found.";
02773         exit(1);
02774     }    
02775      
02776     // 
02777     // Check if this edge is strongly projectable   
02778     //
02779     // Find node with smaller degree.
02780     int index = 0;
02781     if (adjacentListSize[edge[0]] > adjacentListSize[edge[1]]) {
02782         index = 1;
02783     }
02784     // -> edge[index] has smaller degree.
02785     
02786     // Get neighborhood of edge[index]
02787     vector<int> neighborhood;
02788     getNeighborhood(edge[index], &neighborhood);
02789 //cout << "neighborhood of " << edge[index] << endl << "\t";
02790 //for (j=0; j<neighborhood.size();j++) cout << neighborhood[j] << " ";
02791 //cout << endl;   
02792     // Delte edge[(index+1)%2] from the neighborhood
02793     i = 0;
02794     size = neighborhood.size();
02795     while (i < size) {
02796         if (neighborhood[i] == edge[(index+1)%2]) {
02797             neighborhood.erase(neighborhood.begin()+i);
02798             size--;
02799             break;
02800         }
02801         i++;
02802     }
02803 //cout << "neighborhood of " << edge[index] << endl << "\t";
02804 //for (j=0; j<neighborhood.size();j++) cout << neighborhood[j] << " ";
02805 //cout << endl;
02806     // Check if this node was found.
02807     if(i == size+1) {
02808         cout << "ERROR" << endl;
02809         exit(1);
02810     }
02811 
02812     // Check if neighborhood is a clique.
02813     bool clique = true;
02814     for (i=0; i<size-1; i++) {
02815         for (j=i+1; j<size; j++) {
02816             if (!lowerAdjacentMatrix[neighborhood[j]-1][neighborhood[i]]) {
02817 //cout << "nodes " << neighborhood[j] << " and " << neighborhood[i] << " are not adjacent" << endl;
02818                 clique = false;
02819                 break;
02820             }
02821         }// for
02822         if (!clique) {
02823             break;
02824         }
02825     }// for
02826 
02827 cout << "\tProjection edge:\t" << edge[0] << " " << edge[1] << endl;
02828     if (clique) {
02829         // We have found a strongly projectable edge!
02830         for (i=0; i<size; i++) {
02831             if (neighborhood[i] > edge[(index+1)%2]) {
02832                 if (lowerAdjacentMatrix[neighborhood[i]-1][edge[(index+1)%2]]) {
02833                     deleteNodes.push_back(neighborhood[i]);
02834                 }
02835             }
02836             else {
02837                 if (lowerAdjacentMatrix[edge[(index+1)%2]-1][neighborhood[i]]) {
02838                     deleteNodes.push_back(neighborhood[i]);
02839                 }
02840             }
02841         }
02842 cout << "\tNeighborhood of node " << edge[index] << " is a clique." << endl;
02843     }
02844     else {
02845         //
02846         // Make it a projectable edge.
02847         //
02848 cout << "\tNeighborhood of node " << edge[index] << " is NO clique." << endl;
02849         // Construct induced subgraph of neighborhood.
02850         vector< vector<int> > adjacentList(size);
02851         for (i=0; i<size-1; i++) {
02852             for (j=i+1; j<size; j++) {
02853                 if (lowerAdjacentMatrix[neighborhood[j]-1][neighborhood[i]]) {
02854                     adjacentList[i].push_back(j);
02855                     adjacentList[j].push_back(i);
02856                 }
02857             }                
02858         }        
02859 
02860         // Compute maximUM clique in induced graph of neighborhood.
02861         vector<int> *maxClique;
02862         // This can be any exact maximum clique generator!
02863         maxClique = computeMaximumClique(&adjacentList, &neighborhood);
02864 //cout << "maxClique:\t";
02865 //for(i=0; i<maxClique->size(); i++) cout << (*maxClique)[i] << " ";
02866 //cout << endl;
02867         // Tranlsate clique and fill vectors deleteNodes, deleteEdges
02868         int cliqueSize = maxClique->size();
02869         for (i=0; i<cliqueSize; i++) {
02870             (*maxClique)[i] = neighborhood[(*maxClique)[i]];
02871         }
02872         sort(maxClique->begin(), maxClique->end());
02873 cout << "\tMaximum clique:\t";
02874 for(i=0; i<maxClique->size(); i++) cout << (*maxClique)[i] << " ";
02875 cout << endl;
02876 //        deleteNodes.resize(cliqueSize);
02877 //cout << size - cliqueSize << endl;
02878         deleteEdges.resize(size - cliqueSize);
02879 //        int nodesCnt = 0;
02880         int edgesCnt = 0;
02881         int *anEdge;
02882         j = 0;
02883         for (i=0; i<size; i++) {
02884             // Check if neighborhood[i] is in the clique. If it is contained
02885             // this node will be deleted. Otherwise we have to delete an edge.
02886             while (j < cliqueSize) {
02887                 if ((*maxClique)[j] >= neighborhood[i]) {
02888                     if ((*maxClique)[j] == neighborhood[i]) {
02889                         if (neighborhood[i] > edge[(index+1)%2]) {
02890                             if (lowerAdjacentMatrix[neighborhood[i]-1][edge[(index+1)%2]]) {
02891                                 deleteNodes.push_back(neighborhood[i]);
02892                             }
02893                         }// if
02894                         else {
02895                             if (lowerAdjacentMatrix[edge[(index+1)%2]-1][neighborhood[i]]) {
02896                                 deleteNodes.push_back(neighborhood[i]);
02897                             }
02898                         }// else
02899                     }
02900                     else {
02901                         anEdge = new int[2];
02902                         anEdge[0] = edge[index];
02903                         anEdge[1] = neighborhood[i];
02904                         deleteEdges[edgesCnt++] = anEdge;
02905                     }
02906                     break;
02907                 }
02908                 j++;
02909             }// while
02910             if (j == cliqueSize) {
02911                 anEdge = new int[2];
02912                 anEdge[0] = edge[index];
02913                 anEdge[1] = neighborhood[i];
02914                 deleteEdges[edgesCnt++] = anEdge;
02915             }
02916         }// for
02917 
02918         // Clean up.
02919         delete maxClique;
02920 
02921     }// else
02922 
02923 cout << "\tDelete nodes:\t";
02924 for(i=0;i<deleteNodes.size();i++) cout << deleteNodes[i] << " ";
02925 cout << "\n\tDelete edges:\t";
02926 for(i=0;i<deleteEdges.size();i++) cout << deleteEdges[i][0] << " " << deleteEdges[i][1] << "; ";
02927 cout << endl << endl << endl;
02928 
02929 }// end edgeSelection()
02930 
02931 //
02932 // EXACT COMPUTATION:
02933 //
02934 // -----------------------------------------------------------------------------
02935 // c o m p u t e M a x i m u m C l i q u e
02936 // -----------------------------------------------------------------------------
02937 vector<int>* EdgeProjection::computeMaximumClique(
02938             vector< vector<int> > *theAdjacentList, vector<int> *theTranslator) {
02939 
02940     int i, j;
02941     int node;
02942     int vertex;
02943     vector<int> clique;         //
02944     vector<int> adjacentNodes;  //
02945     vector<int> *maxClique;     // Store a maximUM clique.
02946                                 // This will be the return value.
02947     int maxCliqueSize = 1;      // Size of maximUM clique.
02948 
02949     clique.push_back(0);
02950     maxClique = new vector<int>;
02951     maxClique->push_back(0);
02952     adjacentNodes = (*theAdjacentList)[0];
02953     bool stop = false;
02954 
02955     while (!stop) {
02956 //cout << "Clique:\t";
02957 //for(int l=0;l<clique.size();l++) cout << clique[l] << " ";
02958 //cout << endl;
02959 //cout << "Adjacent nodes:\t";
02960 //for(int l=0;l<adjacentNodes.size();l++) cout << adjacentNodes[l] << " ";
02961 //cout << endl;
02962        while(!adjacentNodes.empty() && (adjacentNodes.size() + clique.size()) > maxCliqueSize) {
02963            clique.push_back(adjacentNodes.back());
02964            adjacentNodes.pop_back();
02965            // Update adjacent nodes.
02966            for (i=adjacentNodes.size()-1; i>=0; i--) {
02967                if ((*theTranslator)[clique.back()] > (*theTranslator)[adjacentNodes[i]]) {
02968                    if(!lowerAdjacentMatrix[(*theTranslator)[clique.back()]-1][(*theTranslator)[adjacentNodes[i]]]) {
02969                        adjacentNodes.erase(adjacentNodes.begin()+i);
02970                    }
02971                }
02972                else {
02973                    if(!lowerAdjacentMatrix[(*theTranslator)[adjacentNodes[i]]-1][(*theTranslator)[clique.back()]]) {
02974                        adjacentNodes.erase(adjacentNodes.begin()+i);
02975                    }
02976 
02977                }
02978            }
02979        }
02980 //cout << "maximal Clique:\t";
02981 //for(int l=0;l<clique.size();l++) cout << clique[l] << " ";
02982 //cout << endl;
02983 
02984        if ((adjacentNodes.size() + clique.size()) > maxCliqueSize) {
02985 //cout << "New max clique:\t";
02986 //for(int l=0;l<clique.size();l++) cout << clique[l] << " ";
02987 //cout << endl;
02988            // Update maximUM clique.
02989            maxClique->clear();
02990            (*maxClique) = clique;
02991            maxCliqueSize = maxClique->size();
02992        }
02993 //cout << "vor Clique:\t";
02994 //for(int l=0;l<clique.size();l++) cout << clique[l] << " ";
02995 //cout << endl;
02996        node = clique.back();
02997        clique.pop_back();
02998 //cout << "Clique:\t";
02999 //for(int l=0;l<clique.size();l++) cout << clique[l] << " ";
03000 //cout << endl;
03001 
03002        if (clique.empty()) {
03003            if ((node+1) >= theAdjacentList->size()) {
03004                stop = true;
03005                continue;
03006            }
03007            clique.push_back(node +1);
03008            node = theAdjacentList->size();
03009        }
03010        adjacentNodes.clear();
03011 
03012        // Get adjacent list.
03013        i = 0;
03014        while (i<(*theAdjacentList)[clique[0]].size()){
03015            vertex = (*theAdjacentList)[clique[0]][i];
03016            if ( vertex >= node) {
03017                break;
03018            }
03019            j = 1;
03020            while (j < clique.size()) {
03021                if (clique[j] == vertex) {
03022                    break;
03023                }
03024                if ((*theTranslator)[vertex] > (*theTranslator)[clique[j]]) {
03025                    if (!lowerAdjacentMatrix[(*theTranslator)[vertex]-1][(*theTranslator)[clique[j]]]) {
03026                        break;
03027                    }
03028                }
03029                else {
03030                    if (!lowerAdjacentMatrix[(*theTranslator)[clique[j]]-1][(*theTranslator)[vertex]]) {
03031                        break;
03032                    }
03033                }
03034 //cout << "trans:\t" << (*theTranslator)[vertex] << "   " << (*theTranslator)[clique[j]] << endl;
03035                j++;
03036            }
03037            if (j == clique.size()) {
03038 //cout << "push " << vertex << endl;
03039                adjacentNodes.push_back(vertex);
03040            }
03041            else {
03042                if ((!adjacentNodes.size() + (*theAdjacentList)[clique[0]].size() - i + clique.size() + 1) < maxCliqueSize) {
03043                    break;
03044                }
03045            }
03046            i++;
03047        }// while
03048     }// while
03049 
03050     return maxClique;
03051 
03052 }// end computeMaximumClique(..)
03053 
03054 */
03055 
03056 
03057 

Generated on Fri Apr 28 15:49:59 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO