#include <EdgeProjection.hh>
Public Member Functions | |
EdgeProjection (vector< vector< int > > *adjacentList) | |
~EdgeProjection () | |
int | separate (double *lpValue) |
int | computeLargeInequality (double *lpValue, StableSetMaster *theMaster) |
vector< vector< int > * > * | getLHS () |
vector< int > * | getRHS () |
Definition at line 44 of file EdgeProjection.hh.
|
Constructor.
Definition at line 43 of file EdgeProjection.cpp. 00043 : 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
|
|
Destructor. Definition at line 93 of file EdgeProjection.cpp. 00093 { 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
|
|
This function computes one large rank inequality.
Definition at line 253 of file EdgeProjection.cpp. 00254 { 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(..)
|
|
This function returns the left hand side of all computed inequalities.
Definition at line 363 of file EdgeProjection.cpp. 00363 { 00364 00365 if (lhs.empty()) { 00366 return NULL; 00367 } 00368 else { 00369 return &lhs; 00370 } 00371 }
|
|
This function returns the right hand side of all computed inequalities.
Definition at line 379 of file EdgeProjection.cpp.
|
|
This function handles the hole edge projection.
Definition at line 116 of file EdgeProjection.cpp. 00116 { 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(..)
|