#include <Graph.hh>
Public Member Functions | |
Graph (ABA_MASTER *master, int nodeNumber, int edgeNumber, bool weighted, char *fileName) | |
~Graph () | |
void | pushAdjacentNodes (int rightNode, int leftNode) |
void | pushWeight (int i, double weight) |
void | sortAdjacentList () |
int | numberOfNodes () const |
int | numberOfEdges () const |
vector< int > * | getAdjacentList (int i) |
int | adjacentListSize (int i) const |
int | adjacentListElement (int i, int j) const |
bool | isMemberOfAdjacentList (int index, int &begin, int node) const |
bool | weighted () const |
double | weight (int i) const |
void | initializeTranslator () |
int | translateNode (int index) const |
void | deleteNodesFromGraph (const vector< int > *nodesOfClique) |
void | deleteNodesFromGraph (const vector< int > *deleteNodes, vector< int > *visitedNodes) |
void | fixVariablesFirstLP (int numberOfFixedNodes) |
bool | allVariablesFixed () const |
char * | getFileName () |
double | getDensity () const |
void | printStatistic () const |
void | output () const |
Definition at line 41 of file Graph.hh.
|
Constructor.
Definition at line 38 of file Graph.cpp. 00039 : 00040 master_(master), 00041 numberOfNodes_(nodeNumber), 00042 numberOfEdges_(edgeNumber), 00043 weighted_(weighted), 00044 fixedVariablesFirstLP(0), 00045 fixedVariables(0) 00046 { 00047 adjacentList.resize(nodeNumber); 00048 if (weighted) { 00049 // Allocate weightsOfNodes. 00050 weightsOfNodes = new double[nodeNumber]; 00051 } 00052 calculateDensity(); 00053 00054 sprintf( theFileName, "%s", fileName ); 00055 }
|
|
Destructor. Definition at line 61 of file Graph.cpp. 00061 { 00062 00063 if (weighted_) { 00064 delete [] weightsOfNodes; 00065 } 00066 for (int i=adjacentList.size()-1; i>=0; i--) { 00067 adjacentList[i].clear(); 00068 } 00069 }
|
|
Get Element of adjacent list.
Definition at line 143 of file Graph.cpp.
|
|
Get size of adjacent list.
Definition at line 133 of file Graph.cpp. Referenced by deleteNodesFromGraph(), and StableSetSub::feasible().
|
|
Have all variables been fixed?
Definition at line 416 of file Graph.cpp.
|
|
Delete all nodes from the graph and return all nodes with changed neighborhood.
Definition at line 299 of file Graph.cpp. References adjacentListSize(). 00300 { 00301 00302 const int NUM_NODES = deleteNodes->size(); 00303 00304 int i, j, k; // Loop counter. 00305 int adjacentListSize; // Size of an adjacent list. 00306 int vertex; // A node. 00307 int size; 00308 00309 // 00310 // Update adjacent list. 00311 // 00312 // Go through the adjacent list of all nodes of the vector and delete 00313 // node deleteNodes[i] from its adjacent list 00314 for (i=0; i<NUM_NODES; i++) { 00315 adjacentListSize = adjacentList[(*deleteNodes)[i]].size(); 00316 for (j=0; j<adjacentListSize; j++) { 00317 vertex = adjacentList[(*deleteNodes)[i]][j]; 00318 // Do something only if this is NOT a member of the vector deleteNodes. 00319 00320 k = 0; 00321 while ((k < (NUM_NODES-1)) && ((*deleteNodes)[k] != vertex)) { 00322 k++; 00323 } 00324 00325 if((*deleteNodes)[k] == vertex) { 00326 continue; 00327 } 00328 00329 k = 0; 00330 // Find index of vertex deleteNodes[i] in the adjacent list. 00331 if (!isMemberOfAdjacentList(vertex, k, (*deleteNodes)[i])) { 00332 master_->err() << "ERROR in Graph::deleteNodesFrom"; 00333 master_->err() << "Graph:\n"; 00334 master_->err() << "Vertex " << (*deleteNodes)[i]; 00335 master_->err() << " could not be found in the adjacent list of"; 00336 master_->err() << " node " << vertex << " ." << endl; 00337 exit(master_->Fatal); 00338 } 00339 k--; 00340 // Remove this element 00341 adjacentList[vertex].erase(adjacentList[vertex].begin() +k); 00342 k = 0; 00343 while ((k < visitedNodes->size()) 00344 && ((*visitedNodes)[k] != vertex) 00345 ) { 00346 k++; 00347 } 00348 if (k == visitedNodes->size()) { 00349 visitedNodes->push_back(vertex); 00350 } 00351 numberOfEdges_--; 00352 00353 } 00354 adjacentList[(*deleteNodes)[i]].clear(); 00355 } 00356 numberOfEdges_ -= (NUM_NODES * (NUM_NODES - 1)) / 2; 00357 00358 00359 // 00360 // Remove the nodes from the graph. 00361 // 00362 for (i=NUM_NODES-1; i>=0; i--) { 00363 00364 adjacentList.erase(adjacentList.begin() + (*deleteNodes)[i]); 00365 numberOfNodes_--; 00366 00367 for (j=(*deleteNodes)[i]; j<translateNodes.size()-1; j++) { 00368 translateNodes[j] = translateNodes[j+1]; 00369 } 00370 translateNodes.pop_back(); 00371 00372 // Update all nodes of the graph and of the list of nodes to be checked. 00373 for (j=0; j<numberOfNodes_; j++) { 00374 size = adjacentList[j].size(); 00375 for (k=0; k<size; k++) { 00376 if (adjacentList[j][k] > (*deleteNodes)[i]) { 00377 adjacentList[j][k] -= 1; 00378 } 00379 } 00380 00381 } 00382 size = visitedNodes->size(); 00383 for (j=0; j<size; j++) { 00384 if ((*visitedNodes)[j] > (*deleteNodes)[i]) { 00385 (*visitedNodes)[j] -= 1; 00386 } 00387 } 00388 00389 00390 } 00391 00392 fixedVariables += NUM_NODES; 00393 00394 calculateDensity(); 00395 // output(); 00396 00397 }// void deleteNodesFromGraph(..)
|
|
Delete all nodes of the given vector from the graph.
Definition at line 221 of file Graph.cpp. References adjacentListSize(), and isMemberOfAdjacentList(). 00221 { 00222 00223 const int NUM_NODES = deleteNodes->size(); 00224 int i, j, k; // Loop counter. 00225 int adjacentListSize; // Size of an adjacent list. 00226 int vertex; // A node. 00227 bool found; // Flag which shows if a node is member of 00228 // vector nodesOfClique. 00229 int size; 00230 00231 // 00232 // Update adjacent list. 00233 // 00234 // Go through the adjacent list of all nodes of the vector and delete 00235 // node deleteNodes[i] from its adjacent list 00236 for (i=0; i<NUM_NODES; i++) { 00237 adjacentListSize = adjacentList[(*deleteNodes)[i]].size(); 00238 for (j=0; j<adjacentListSize; j++) { 00239 vertex = adjacentList[(*deleteNodes)[i]][j]; 00240 00241 k = 0; 00242 // Find index of vertex deleteNodes[i] in the adjacent list. 00243 if (!isMemberOfAdjacentList(vertex, k, (*deleteNodes)[i])) { 00244 master_->err() << "ERROR in Graph::deleteNodesFrom"; 00245 master_->err() << "Graph:\n"; 00246 master_->err() << "Vertex " << (*deleteNodes)[i]; 00247 master_->err() << " could not be found in the adjacent list of"; 00248 master_->err() << " node " << vertex << " ." << endl; 00249 exit(master_->Fatal); 00250 } 00251 k--; 00252 // Remove this element 00253 adjacentList[vertex].erase(adjacentList[vertex].begin() +k); 00254 numberOfEdges_--; 00255 00256 } 00257 adjacentList[(*deleteNodes)[i]].clear(); 00258 } 00259 00260 // 00261 // Remove the nodes from the graph. 00262 // 00263 for (i=NUM_NODES-1; i>=0; i--) { 00264 00265 adjacentList.erase(adjacentList.begin() + (*deleteNodes)[i]); 00266 numberOfNodes_--; 00267 00268 for (j=(*deleteNodes)[i]; j<translateNodes.size()-1; j++) { 00269 translateNodes[j] = translateNodes[j+1]; 00270 } 00271 translateNodes.pop_back(); 00272 00273 // Update all nodes of the graph and of the list of nodes to be checked. 00274 for (j=0; j<numberOfNodes_; j++) { 00275 size = adjacentList[j].size(); 00276 for (k=0; k<size; k++) { 00277 if (adjacentList[j][k] > (*deleteNodes)[i]) { 00278 adjacentList[j][k] -= 1; 00279 } 00280 } 00281 00282 } 00283 00284 } 00285 00286 calculateDensity(); 00287 // output(); 00288 00289 }// void deleteNodesFromGraph(..)
|
|
Update counter for fixed nodes.
Definition at line 405 of file Graph.cpp. 00405 { 00406 fixedVariables += numberOfFixedNodes; 00407 fixedVariablesFirstLP = numberOfFixedNodes; 00408 }
|
|
Get adjacent list.
Definition at line 123 of file Graph.cpp. Referenced by StableSetSub::feasible(), and CliqueHeuristicsSeparator::separate().
|
|
Get density of the graph.
Definition at line 432 of file Graph.cpp.
|
|
Get name of the file where all computed inequalities are stored.
Definition at line 424 of file Graph.cpp. Referenced by CliqueConstraint::CliqueConstraint(), StableSetSub::feasible(), GeneralConstraint::GeneralConstraint(), RankConstraint::RankConstraint(), and StableSetSub::separate().
|
|
Copy the current nodes in translator.
Definition at line 191 of file Graph.cpp. 00191 { 00192 00193 translateNodes.resize(numberOfNodes_); 00194 00195 for (int i=0; i<numberOfNodes_; i++) { 00196 translateNodes[i] = i; 00197 } 00198 00199 }
|
|
Check if two vertices are adjacent.
Definition at line 155 of file Graph.cpp. Referenced by deleteNodesFromGraph(), StableSetSub::feasible(), and CliqueHeuristicsSeparator::separate(). 00155 { 00156 00157 bool found = false; 00158 int size = adjacentList[index].size(); 00159 00160 while((begin < size) && (node > adjacentList[index][begin])) { 00161 begin++; 00162 } 00163 if ((begin < size) && (node == adjacentList[index][begin])) { 00164 found = true; 00165 begin++; 00166 } 00167 00168 return found; 00169 }
|
|
Get number of edges.
Definition at line 115 of file Graph.cpp.
|
|
Get number of nodes.
Definition at line 107 of file Graph.cpp. Referenced by LowerBoundHeuristic::computeSolution(), StableSetSub::feasible(), StableSetSub::generateBranchRules(), Preprocessing::preprocessing(), StableSetSub::separate(), CliqueHeuristicsSeparator::separate(), StableSetModKSeparator::StableSetModKSeparator(), and StableSetMaster::~StableSetMaster().
|
|
Print some information about the problem instance.
Definition at line 458 of file Graph.cpp. 00458 { 00459 00460 master_->out() << "\nGraph:\n"; 00461 master_->out() << "------------------------------------------------------"; 00462 master_->out() << "\nnNodes:\t" << numberOfNodes_; 00463 master_->out() << "\nnEdges:\t" << numberOfEdges_; 00464 master_->out() << "\nDensity:\t" << density; 00465 master_->out() << "\n\nEdges:\n"; 00466 for (int i=0; i<numberOfNodes_; i++) { 00467 master_->out() << " node[" << i << "]:\t"; 00468 for (int j=0; j<adjacentList[i].size(); j++) { 00469 master_->out() << adjacentList[i][j] << " "; 00470 } 00471 master_->out() << endl; 00472 } 00473 master_->out() << "------------------------------------------------------"; 00474 master_->out() << endl << endl; 00475 }
|
|
Print statistic about fixed nodes.
Definition at line 443 of file Graph.cpp. Referenced by StableSetMaster::output(). 00443 { 00444 00445 master_->out() << " Number of fixed variables according to LP\t: "; 00446 master_->out() << fixedVariablesFirstLP; 00447 master_->out() << "\n Number of fixed variables according to clique\t: "; 00448 master_->out() << fixedVariables - fixedVariablesFirstLP; 00449 00450 }// end: void printStatistic()
|
|
Store adjacent nodes.
Definition at line 75 of file Graph.cpp. 00075 { 00076 adjacentList[rightNode].push_back(leftNode); 00077 adjacentList[leftNode].push_back(rightNode); 00078 }
|
|
Set weight of a node.
Definition at line 86 of file Graph.cpp. 00086 { 00087 weightsOfNodes[i] = weight; 00088 }
|
|
Sort each adjazens list.
Definition at line 96 of file Graph.cpp. 00096 { 00097 00098 for (int i=0; i<numberOfNodes_; i++) { 00099 sort(adjacentList[i].begin(), adjacentList[i].end()); 00100 } 00101 }
|
|
Translate a node.
Definition at line 207 of file Graph.cpp. Referenced by CliqueConstraint::CliqueConstraint(), GeneralConstraint::GeneralConstraint(), StableSetMaster::output(), and RankConstraint::RankConstraint().
|
|
Get weight of node.
Definition at line 183 of file Graph.cpp.
|
|
Get type of problem.
Definition at line 175 of file Graph.cpp. Referenced by StableSetSub::improve().
|