00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00015
00016
00017
00018
00020
00021 #include "Graph.hh"
00022 #include <iostream>
00023
00024 using namespace std;
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 Graph::Graph(ABA_MASTER *master, int nodeNumber, int edgeNumber, bool weighted,
00039 char *fileName):
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
00050 weightsOfNodes = new double[nodeNumber];
00051 }
00052 calculateDensity();
00053
00054 sprintf( theFileName, "%s", fileName );
00055 }
00056
00057
00058
00059
00060
00061 Graph::~Graph() {
00062
00063 if (weighted_) {
00064 delete [] weightsOfNodes;
00065 }
00066 for (int i=adjacentList.size()-1; i>=0; i--) {
00067 adjacentList[i].clear();
00068 }
00069 }
00070
00071
00072
00073
00074
00075 void Graph::pushAdjacentNodes(int rightNode, int leftNode) {
00076 adjacentList[rightNode].push_back(leftNode);
00077 adjacentList[leftNode].push_back(rightNode);
00078 }
00079
00080
00081
00082
00083
00084
00085
00086 void Graph::pushWeight(int i, double weight) {
00087 weightsOfNodes[i] = weight;
00088 }
00089
00090
00091
00092
00093
00094
00095
00096 void Graph::sortAdjacentList() {
00097
00098 for (int i=0; i<numberOfNodes_; i++) {
00099 sort(adjacentList[i].begin(), adjacentList[i].end());
00100 }
00101 }
00102
00103
00104
00105
00106
00107 int Graph::numberOfNodes() const {
00108 return numberOfNodes_;
00109 }
00110
00111
00112
00113
00114
00115 int Graph::numberOfEdges() const {
00116 return numberOfEdges_;
00117 }
00118
00119
00120
00121
00122
00123 vector<int> *Graph::getAdjacentList(int i) {
00124 return &adjacentList[i];
00125 }
00126
00127
00128
00129
00130
00131
00132
00133 int Graph::adjacentListSize(int i) const {
00134 return adjacentList[i].size();
00135 }
00136
00137
00138
00139
00140
00141
00142
00143 int Graph::adjacentListElement(int i, int j) const {
00144 return adjacentList[i][j];
00145 }
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155 bool Graph::isMemberOfAdjacentList(int index, int &begin, int node) const {
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 }
00170
00171
00172
00173
00174
00175 bool Graph::weighted() const {
00176 return weighted_;
00177 }
00178
00179
00180
00181
00182
00183 double Graph::weight(int i) const {
00184 return weightsOfNodes[i];
00185 }
00186
00187
00188
00189
00190
00191 void Graph::initializeTranslator() {
00192
00193 translateNodes.resize(numberOfNodes_);
00194
00195 for (int i=0; i<numberOfNodes_; i++) {
00196 translateNodes[i] = i;
00197 }
00198
00199 }
00200
00201
00202
00203
00204
00205
00206
00207 int Graph::translateNode(int index) const {
00208 return translateNodes[index];
00209
00210 }
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221 void Graph::deleteNodesFromGraph(const vector<int> *deleteNodes) {
00222
00223 const int NUM_NODES = deleteNodes->size();
00224 int i, j, k;
00225 int adjacentListSize;
00226 int vertex;
00227 bool found;
00228
00229 int size;
00230
00231
00232
00233
00234
00235
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
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
00253 adjacentList[vertex].erase(adjacentList[vertex].begin() +k);
00254 numberOfEdges_--;
00255
00256 }
00257 adjacentList[(*deleteNodes)[i]].clear();
00258 }
00259
00260
00261
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
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
00288
00289 }
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299 void Graph::deleteNodesFromGraph(const vector<int> *deleteNodes,
00300 vector<int> *visitedNodes) {
00301
00302 const int NUM_NODES = deleteNodes->size();
00303
00304 int i, j, k;
00305 int adjacentListSize;
00306 int vertex;
00307 int size;
00308
00309
00310
00311
00312
00313
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
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
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
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
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
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
00396
00397 }
00398
00399
00400
00401
00402
00403
00404
00405 void Graph::fixVariablesFirstLP(int numberOfFixedNodes) {
00406 fixedVariables += numberOfFixedNodes;
00407 fixedVariablesFirstLP = numberOfFixedNodes;
00408 }
00409
00410
00411
00412
00413
00414
00415
00416 bool Graph::allVariablesFixed() const {
00417 return (fixedVariables == numberOfNodes_);
00418 }
00419
00420
00421
00422
00423
00424 char *Graph::getFileName() {
00425 return theFileName;
00426 }
00427
00428
00429
00430
00431
00432 double Graph::getDensity() const {
00433 return density;
00434 }
00435
00436
00437
00438
00439
00440
00441
00442
00443 void Graph::printStatistic() const{
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 }
00451
00452
00453
00454
00455
00456
00457
00458 void Graph::output() const {
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 }
00476
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486
00487 void Graph::calculateDensity() {
00488 if (numberOfNodes_ == 0 || numberOfNodes_ == 1) {
00489 density = -1;
00490 }
00491 else {
00492 density = (1.0*numberOfEdges_) / numberOfNodes_;
00493 density = density / (numberOfNodes_ -1);
00494 density *= 2;
00495 }
00496 }
00497
00498