if (this->O >= t_o && p != 0){

return best;

}

else{

t_o = this->O;

best = *this;

}

p++;

cout << "Bla = " << this->O << endl;

for(int i = 0; i < v; i++){

for(int j = 0; j < v; j++){

cout << edges[i][j] << " ";

}

cout << endl;

}

cout << endl;

for(int i = 0; i < v; i++){

for(int j = 0; j < v; j++){

cout << edges[i][j] << " ";

}

cout << endl;

}

cout << endl;

int min = INFINITY;

for (int i = 0; i < v; i++) {

for (int j = i; j < v; j++){

if (edges[i][j] != 0 && arr[i][j] == 2){

if (min > edges[i][j])

min = edges[i][j];

}

}

}

for (int i = 0; i < v; i++) {

for (int j = 0; j < v; j++){

if (edges[i][j] == min && arr[i][j] == 2){

deleteSymEdges(i, j);

}

}

}

}

}

//bab

void Graph::addEdge(int a, int b){

if (a >= 0 && b >= 0 && a < v && b < v){

if (arr[a][b] == 0){

arr[a][b] = 2;

arr[b][a] = 2;

degree[a]++;

degree[b]++;

}

}

}

void Graph::strictEdge(int a, int b){

if (a >= 0 && b >= 0 && a < v && b < v){

if (arr[a][b] == 0){

arr[a][b] = -1;

arr[b][a] = -1;

}

}

}

void Graph::unstrictEdge(int a, int b){

if (a >= 0 && b >= 0 && a < v && b < v){

if (arr[a][b] == -1){

arr[a][b] = 0;

arr[b][a] = 0;

}

}

}

void Graph::deleteEdge(int a, int b){

if (a >= 0 && b >= 0 && a < v && b < v){

if (arr[a][b] == 2){

arr[a][b] = 0;

arr[b][a] = 0;

degree[a]--;

degree[b]--;

}

}

}

void Graph::FindPathForBound(int a, int b){

inPath[a] = true;

if (a == b){

inSearch[a] = true;

return;

}

inSearch[a] = true;

int t = 0;

double* paths = new double[v];

int* indexes = new int[v];

for (int i = 0; i < v; i++){

if (arr[a][i] != -1){

if (arr[a][i] > 0)

inSearch[i] = true;

paths[t] = Distance(i, b);

indexes[t] = i;

t++;

}

else{

paths[t] = INFINITY;

indexes[t] = i;

t++;

}

}

int minI = 0;

double minV = paths[0];

for (int i = 1; i < v; i++){

if (paths[i] < minV && inPath[indexes[i]] == false){

minV = paths[i];

minI = i;

}

else{

switch(TYPE_V){

case 0:

if (paths[i] == minV && inPath[indexes[i]] == false){

if (degree[indexes[i]] < degree[indexes[minI]]){

minV = paths[i];

minI = i;

}

}

break;

case 1:

if (paths[i] == minV && inPath[indexes[i]] == false){

if (degree[indexes[i]] > degree[indexes[minI]]){

minV = paths[i];

minI = i;

}

}

break;

case 2:

if (paths[i] == minV && inPath[indexes[i]] == false){

if (rand()%2 == 0){

minV = paths[i];

minI = i;

}

}

break;

}

}

}

int next_vertix = indexes[minI];

delete[] paths;

delete[] indexes;

FindPathForBound(next_vertix, b);

return;

}

double Graph::LowBound(){

int* sum = new int[v];

for (int i = 0; i < v; i++){

sum[i] = 0;

for (int j = 0; j < v; j++){

FindPathForBound(i, j);

for (int t = 0; t < v; t++){

sum[i] += inSearch[t];

inSearch[t] = false;

inPath[t] = false;

}

}

}

int s = 0;

for (int i = 0; i < v; i++){

s += sum[i];

}

delete[] sum;

//O = s / v;

return s;

}

void Graph::BranchAndBoundAddOne(Graph* bestBB, int step, double* bestO){

double lb = LowBound();

// for (int c = 0; c < step-1; c++){

// cout << "\t";

// }

// cout << "LB = " << lb << endl;

if (lb > (*bestO)){

return;

}

// if (step == 0){

// calculateO();

// if (O <= *bestO){

//

// if (O < *bestO){

// bestest.clear();

// }

// (*bestBB) = (*this);

// (*bestO) = O;

// bestest.push_back(*bestBB);

//

//

// }

// }

int start = -1;

int finish = -1;

for (int i = 0; i < v; i++){

for (int j = i + 1; j < v; j++){

//if ((i <= n*m / 2) && (i <= n/ 2 + i / n)){

if (arr[i][j] == 0){

start = i;

finish = j;

break;

}

}

if (start == -1)

break;

}

if (start == -1){

calculateO();

/*if(O == 869){

bestBB->save("Dir_For_BaB_" + to_string(n) + "_" + to_string(m), "Out_" + to_string(int(bestBB->getO()))+"_" + to_string(counter) + ".txt");

counter++;

}*/

//calculateO();

// for (int c = 0; c < step; c++){

// cout << "\t";

// }

// cout << "Current O = " << O << endl;

if (O <= *bestO){

if (O < *bestO){

//cout << "OOOOOO = " << O << " BO = "<< bestO << endl;

bestest.clear();

}

(*bestBB) = (*this);

(*bestO) = O;

bestest.push_back(*bestBB);

//if(O == 869){

// bestBB->save("Dir_For_BaB_" + to_string(n) + "_" + to_string(m), "Out_" + to_string(int(bestBB->getO()))+"_" + to_string(bestest.size()) + ".txt");

//}

//bestBB->save("Dir_" + to_string(n) + "_" + to_string(m), "Out_" + to_string(int(bestBB->getO()))+".txt");

//cout << "Best O = " << bestBB->getO() << endl;

}

return;

}

// for (int c = 0; c < step; c++){

// cout << "\t";

// }

// cout << "Best O = " << bestBB->getO() << endl;

// for (int c = 0; c < step; c++){

// cout << "\t";

// }

// cout << "ADD - " << start << " " << finish << endl;

addEdge(start, finish);

BranchAndBoundAddOne(bestBB, step + 1, bestO);

// for (int c = 0; c < step; c++){

// cout << "\t";

// }

// cout << "STRICT - " << start << " " << finish << endl;

deleteEdge(start, finish);

strictEdge(start, finish);

BranchAndBoundAddOne(bestBB, step + 1, bestO);

unstrictEdge(start, finish);

//return bestO;

}

Graph::~Graph()

{

delete[] degree;

for (int i = 0; i < v; i++)

delete arr[i];

delete[] arr;

delete[] inSearch;

delete[] inPath;

strict.clear();

}

Размещено на Allbest.ru