#include "Instance.h"


Instance::Instance(const string& path, const string& name, const bool& isMedicalBenefit) {
	this->path = path;
	this->name = name;
	this->isMedicalBenefit = isMedicalBenefit;
	this->cyclesLength = 0;
	this->chainsLength = 0;
	this->altruisticDonorsNumber = 0;
	this->incompatiblePairsNumber = 0;
	this->dummyNodeId = -1;
	this->wordsNumber = 0;
	this->exchangesPerVertexInitialisation = -1;
}

Instance::Instance(const Instance& i) {
	this->path = i.path;
	this->name = i.name;
	this->isMedicalBenefit = i.isMedicalBenefit;
	this->cyclesLength = i.cyclesLength;
	this->chainsLength = i.chainsLength;
	this->altruisticDonorsNumber = i.altruisticDonorsNumber;
	this->incompatiblePairsNumber = i.incompatiblePairsNumber;
	this->compatibleMatrix = i.compatibleMatrix;
	this->FloydWarshallMatrix = i.FloydWarshallMatrix;
	this->vertices = i.vertices;
	this->altruisticDonors = i.altruisticDonors;
	this->incompatiblePairs = i.incompatiblePairs;
	this->dummyNodeId = i.dummyNodeId;
	this->wordsNumber = i.wordsNumber;
	this->exchangesPerVertexInitialisation = i.exchangesPerVertexInitialisation;
	this->pairsToProcess = i.pairsToProcess;
	this->arcsPerPairToProcess = i.arcsPerPairToProcess;
	this->nodesPerPairToProcess = i.nodesPerPairToProcess;
	this->IKEPdictionary = i.IKEPdictionary;
	this->IKEPperiodDictionary = i.IKEPperiodDictionary;
}

Instance::~Instance() {
}

bool operator==(const Instance& i1, const Instance& i2) {
	return false;
}

bool operator!=(const Instance& i1, const Instance& i2) {
	return !(i1 == i2);
}

Instance& Instance::operator=(const Instance& i) {
	this->path = i.path;
	this->name = i.name;
	this->isMedicalBenefit = i.isMedicalBenefit;
	this->cyclesLength = i.cyclesLength;
	this->chainsLength = i.chainsLength;
	this->altruisticDonorsNumber = i.altruisticDonorsNumber;
	this->incompatiblePairsNumber = i.incompatiblePairsNumber;
	this->compatibleMatrix = i.compatibleMatrix;
	this->FloydWarshallMatrix = i.FloydWarshallMatrix;
	this->vertices = i.vertices;
	this->altruisticDonors = i.altruisticDonors;
	this->incompatiblePairs = i.incompatiblePairs;
	this->dummyNodeId = i.dummyNodeId;
	this->wordsNumber = i.wordsNumber;
	this->exchangesPerVertexInitialisation = i.exchangesPerVertexInitialisation;
	this->pairsToProcess = i.pairsToProcess;
	this->arcsPerPairToProcess = i.arcsPerPairToProcess;
	this->nodesPerPairToProcess = i.nodesPerPairToProcess;
	this->IKEPdictionary = i.IKEPdictionary;
	this->IKEPperiodDictionary = i.IKEPperiodDictionary;
	return *this;
}

void Instance::read() {
	string comment;
	comment = this->path + this->name + ".txt";
	cout << "\n\nKEP INSTANCE: " << comment << "\n";

	ifstream stream;
	stream.open(comment.c_str());

	if (!stream) {
		cout << "Error opening the file" << endl;
		exit(1);
	}

	do {
		stream >> comment;
	} while (comment != "patient-donneur");

	stream >> this->incompatiblePairsNumber;

	do {
		stream >> comment;
	} while (comment != "altruistes");

	stream >> this->altruisticDonorsNumber;

	do {
		stream >> comment;
	} while (comment != "cycles");

	stream >> this->cyclesLength;

	do {
		stream >> comment;
	} while (comment != "chaines");

	stream >> this->chainsLength;

	do {
		stream >> comment;
	} while (comment != "realisable");

	int vertexNumber = this->altruisticDonorsNumber + this->incompatiblePairsNumber + 1;
	this->compatibleMatrix = vector<vector<int>>(vertexNumber, vector<int>(vertexNumber, -1));
	//vector<vector<int>> compatibleMatrix1(this->altruisticDonorsNumber + this->incompatiblePairsNumber, vector<int>(this->incompatiblePairsNumber, -1));

	for (int i = 0; i < this->altruisticDonorsNumber; i++) {
		this->compatibleMatrix.at(0).at(i + 1) = 0;
	}
	for (int i = 1; i < vertexNumber; i++) {
		for (int j = 1 + this->altruisticDonorsNumber; j < vertexNumber; j++) {
			stream >> this->compatibleMatrix.at(i).at(j);
			//compatibleMatrix1.at(i - 1).at(j - 1 - this->altruisticDonorsNumber) = this->compatibleMatrix.at(i).at(j);
		}
	}

	if (!this->isMedicalBenefit) {
		for (int i = 0; i < this->compatibleMatrix.size(); i++) {
			for (int j = 0; j < this->compatibleMatrix.at(i).size(); j++) {
				if (this->compatibleMatrix.at(i).at(j) >= 0) {
					this->compatibleMatrix.at(i).at(j) = 1;
				}
			}
		}
	}

	/*int nb_arcs = 0;
	for (int i = 0; i < this->compatibleMatrix.size(); i++) {
		for (int j = 0; j < this->compatibleMatrix.at(i).size(); j++) {
			if (this->compatibleMatrix.at(i).at(j) >= 0) {
				nb_arcs += 1;
			}
		}
	}
	cout << "NB_ARCS:\t" << nb_arcs << endl;
	cout << "NB_ARCS:\t" << nb_arcs << endl;*/

	/*for (int i = 0; i < vertexNumber; i++) {
		for (int j = 0; j < vertexNumber; j++) {
			cout << this->compatibleMatrix.at(i).at(j) << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	for (int i = 0; i < compatibleMatrix1.size(); i++) {
		for (int j = 0; j < compatibleMatrix1.at(i).size(); j++) {
			cout << compatibleMatrix1.at(i).at(j) << " ";
		}
		cout << "\n";
	}
	cout << "\n";*/

}

vector<vector<int>> Instance::preprocessingFloydWarshall() {

	clock_t startFW, endFW;
	startFW = clock();

	//Floyd-Warshall algorithm
	//Initialization
	int vertexNumber = this->altruisticDonorsNumber + this->incompatiblePairsNumber + 1;
	vector<vector<int>> distances(vertexNumber, vector<int>(vertexNumber, ::OMEGA));
	for (int i = 0; i < vertexNumber; i++) {
		for (int j = 0; j < vertexNumber; j++) {
			if (this->compatibleMatrix.at(i).at(j) != -1) {
				distances.at(i).at(j) = 1;
			}
			if (i == j) {
				distances.at(i).at(j) = 0;
			}
		}
	}
	//Iterations
	for (int k = 0; k < vertexNumber; k++) {
		for (int i = 0; i < vertexNumber; i++) {
			for (int j = 0; j < vertexNumber; j++) {
				if (distances.at(i).at(j) > distances.at(i).at(k) + distances.at(k).at(j)) {
					distances.at(i).at(j) = distances.at(i).at(k) + distances.at(k).at(j);
				}
			}
		}
	}
	/*cout << "DISTANCES\n";
	for (int i = 0; i < vertexNumber; i++) {
		for (int j = 0; j < vertexNumber; j++) {
			cout << "\t" << i << "\t" << j << "\t" << distances.at(i).at(j) << endl;
		}
	}*/
	endFW = clock();
	this->timeFloydWarshall = (float)(endFW - startFW) / CLOCKS_PER_SEC;
	return distances;

}

vector<vector<int>> Instance::detectArcsToRemove(const vector<vector<int>>& distances) {

	//Remove arcs
	this->removedArcsFW = 0;
	int vertexNumber = this->altruisticDonorsNumber + this->incompatiblePairsNumber + 1;
	vector<vector<int>> arcsToRemove(vertexNumber, vector<int>(vertexNumber, -1));
	for (int i = 0; i < vertexNumber; i++) {
		for (int j = 0; j < vertexNumber; j++) {
			if (this->compatibleMatrix.at(i).at(j) != -1 && distances.at(0).at(i) >= this->chainsLength + 1 && distances.at(i).at(j) >= this->cyclesLength) {
				arcsToRemove.at(i).at(j) = 1;
				this->removedArcsFW++;
			}
		}
	}
	return arcsToRemove;

}

vector<int> Instance::detectIsolatedVertices(const vector<vector<int>>& arcsToRemove) {
	
	//Remove isolated vertices
	int cc = 0;
	int vertexNumber = this->altruisticDonorsNumber + this->incompatiblePairsNumber + 1;
	vector<int> isolatedVertices(vertexNumber, 1);
	for (int i = 0; i < vertexNumber; i++) {
		for (int j = 0; j < vertexNumber; j++) {

			if (i < this->altruisticDonorsNumber + 1) {
				if (this->compatibleMatrix.at(i).at(j) != -1 && arcsToRemove.at(i).at(j) != 1) {
					//outgoing arc found, vertex not isolated
					isolatedVertices.at(i) = -1;
					cc++;
					break;
				}
			}
			else {
				if (this->compatibleMatrix.at(j).at(i) != -1 && arcsToRemove.at(j).at(i) != 1) {
					//ingoing arc found, vertex not isolated
					isolatedVertices.at(i) = -1;
					cc++;
					break;
				}
			}
		}
	}

	/*for (int i = 0; i < vertexNumber; i++) {
		if (isolatedVertices.at(i) == 1) {
			cout << "removed: " << i << endl;
		}
	}

	for (int i = 0; i < vertexNumber; i++) {
		if (this->compatibleMatrix.at(i).at(14) == 1) {
			cout << "inc: " << i << endl;
		}
	}*/

	this->removedNodesFW = vertexNumber - cc;
 	return isolatedVertices;

}

void Instance::buildVertices(const vector<vector<int>>& distances, const vector<vector<int>>& arcsToRemove, const vector<int>& isolatedVertices, const int& ngSetSize) {

	int id = 0;
	unordered_map<int, int> mapIds;
	for (int i = 0; i < isolatedVertices.size(); i++) {
		if (isolatedVertices.at(i) != 1) {
			char type = 'A';
			if (i == 0) {
				this->dummyNodeId = 0;
				type = 'D';
			}
			else if (i >= this->altruisticDonorsNumber + 1) {
				type = 'I';
			}
			this->vertices.push_back(Vertex(id, type));
			mapIds.insert(make_pair(id, i));
			id++;
		}
	}

	this->altruisticDonorsNumber = 0;
	this->incompatiblePairsNumber = 0;
	for (int i = 0; i < this->vertices.size(); i++) {
		char type = this->vertices.at(i).getType();
		if (type == 'A') {
			this->altruisticDonors.push_back(i);
			this->altruisticDonorsNumber++;
		}
		else if (type == 'I') {
			this->incompatiblePairs.push_back(i);
			this->incompatiblePairsNumber++;
		}
	}

	for (int i = 0; i < this->vertices.size(); i++) {
		int originalId1 = mapIds.at(i);
		for (int j = 0; j < this->vertices.size(); j++) {
			int originalId2 = mapIds.at(j);
			int weight = this->compatibleMatrix.at(originalId1).at(originalId2);
			if (arcsToRemove.at(originalId1).at(originalId2) != 1 && weight != -1) {
				if (!this->isMedicalBenefit && this->vertices.at(i).getType() == 'D') {
					weight = 0;
				}
				if (this->vertices.at(j).getType() != 'A') {
					this->vertices.at(i).addOutGoingArc(j, weight);
					this->vertices.at(j).addInGoingArc(i, weight);
				}
				else if (this->vertices.at(i).getType() == 'D') {
					this->vertices.at(i).addOutGoingArc(j, weight);
					this->vertices.at(j).addInGoingArc(i, weight);
				}
			}
		}
	}

	addExtendedPredecessors(mapIds, distances);

	int word = -1;
	int key = 0;
	for (int i = 0; i < this->vertices.size(); i++) {
		if (i % 30 == 0) {
			word++;
			key = 0;
		}
		this->vertices.at(i).setWord(word);
		this->vertices.at(i).setBitKey(pow(2, key));
		key++;
	}

	this->wordsNumber = word + 1;
	this->bitDictionary = vector<unordered_map<int, int>>(this->wordsNumber);
	for (int i = 0; i < this->vertices.size(); i++) {
		this->bitDictionary.at(this->vertices.at(i).getWord()).insert(make_pair(this->vertices.at(i).getBitKey(), i));
		this->vertices.at(i).initializeNgSet(this->wordsNumber);
		if (ngSetSize > 0) {
			this->vertices.at(i).addNgNeighbour(this->vertices.at(i).getWord(), this->vertices.at(i).getBitKey());
			for (int j = 0; j < min(this->vertices.at(i).getExtendedPredecessors().size(), ngSetSize - 1); j++) {
				int predId = this->vertices.at(i).getExtendedPredecessors().at(j);
				this->vertices.at(i).addNgNeighbour(this->vertices.at(predId).getWord(), this->vertices.at(predId).getBitKey());
			}
		}
	}

	/*for (int i = 0; i < this->incompatiblePairs.size(); i++) {
		this->pairsToProcess.push_back(this->incompatiblePairs.at(i));
	}

	this->arcsPerPairToProcess = vector<vector<vector<int>>>(this->vertices.size(), vector<vector<int>>());
	this->nodesPerPairToProcess = vector<unordered_set<int>>(this->vertices.size(), unordered_set<int>());
	for (int i = 0; i < this->incompatiblePairs.size(); i++) {
		for (int j = 0; j < this->incompatiblePairs.size(); j++) {
			this->nodesPerPairToProcess.at(this->incompatiblePairs.at(i)).insert(this->incompatiblePairs.at(j));
		}
		vector<vector<int>> arcs(this->vertices.size());
		for (int j = 0; j < this->incompatiblePairs.size(); j++) {
			const Vertex* v = &this->vertices.at(this->incompatiblePairs.at(j));
			for (unordered_map<int, int>::const_iterator it = v->getOutGoingArcs().begin(); it != v->getOutGoingArcs().end(); it++) {
				arcs.at(v->getId()).push_back(it->first);
			}
		}
		this->arcsPerPairToProcess.at(this->incompatiblePairs.at(i)) = arcs;
	}*/

	preprocessingOmer(mapIds);

	double vertexToinit = this->altruisticDonorsNumber + this->pairsToProcess.size();
	this->exchangesPerVertexInitialisation = ::EXCHANGESINITIALISATION / (vertexToinit);

}

void Instance::addExtendedPredecessors(const unordered_map<int, int>& mapIds, const vector<vector<int>>& distances) {
	for (int i = 0; i < this->vertices.size(); i++) {
		int pos1 = mapIds.at(this->vertices.at(i).getId());
		for (int j = 0; j < this->vertices.size(); j++) {
			int pos2 = mapIds.at(this->vertices.at(j).getId());
			if (i != j) {
				if (distances.at(0).at(pos2) + distances.at(pos2).at(pos1) <= this->chainsLength || distances.at(pos2).at(pos1) <= this->cyclesLength) {
					this->vertices.at(i).addExtendedPredecessor(j);
				}
			}
		}
	}
	////cycles of size up to three are enumerated->need to consider only the paths
	//if (this->cyclesLength <= 3) {
	//	for (int i = 0; i < this->vertices.size(); i++) {
	//		int pos1 = mapIds.at(this->vertices.at(i).getId());
	//		for (int j = 0; j < this->vertices.size(); j++) {
	//			int pos2 = mapIds.at(this->vertices.at(j).getId());
	//			if (i != j && distances.at(0).at(pos2) + distances.at(pos2).at(pos1) <= this->chainsLength) {
	//				this->vertices.at(i).addExtendedPredecessor(j);
	//			}
	//		}
	//	}
	//}
	//else {
	//	for (int i = 0; i < this->vertices.size(); i++) {
	//		int pos1 = mapIds.at(this->vertices.at(i).getId());
	//		for (int j = 0; j < this->vertices.size(); j++) {
	//			int pos2 = mapIds.at(this->vertices.at(j).getId());
	//			if (i != j) {
	//				if (distances.at(0).at(pos2) + distances.at(pos2).at(pos1) <= this->chainsLength || distances.at(pos2).at(pos1) <= this->cyclesLength) {
	//					this->vertices.at(i).addExtendedPredecessor(j);
	//				}
	//			}
	//		}
	//	}
	//}
}

//bool Instance::can_j_be_in_an_exchange_after_i(const int& i, const int& j) const {
//	vector<int>::const_iterator finder = find(this->vertices.at(i).getExtendedPredecessors().begin(), this->vertices.at(i).getExtendedPredecessors().end(), j);
//	return ((finder != this->vertices.at(i).getExtendedPredecessors().end()) || (this->FloydWarshallMatrix.at(i).at(j) < this->cyclesLength));
//}

vector<int> Instance::BellmanFordPreprocessing_forward(const vector<vector<int>>& availableArcs, const int& source) {

	vector<int> distances(this->vertices.size(), ::OMEGA);
	distances.at(source) = 0;
	vector<unordered_set<int>> verticesPerIteration(this->cyclesLength + 1, unordered_set<int>());
	verticesPerIteration.at(0).insert(source);

	for (int k = 1; k < this->cyclesLength + 1; k++) {
		int previous = k - 1;
		for (unordered_set<int>::const_iterator it = verticesPerIteration.at(previous).begin(); it != verticesPerIteration.at(previous).end(); it++) {
			const Vertex* v = &this->vertices.at(*it);
			for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
				if (availableArcs.at(v->getId()).at(arc->first) && distances.at(v->getId()) + 1 < distances.at(arc->first)) {
					distances.at(arc->first) = distances.at(v->getId()) + 1;
					verticesPerIteration.at(k).insert(arc->first);
				}
			}
		}
	}
	return distances;

}

vector<int> Instance::BellmanFordPreprocessing_backward(const vector<vector<int>>& availableArcs, const int& sink) {

	vector<int> distances(this->vertices.size(), ::OMEGA);
	distances.at(sink) = 0;
	vector<unordered_set<int>> verticesPerIteration(this->cyclesLength + 1, unordered_set<int>());
	verticesPerIteration.at(0).insert(sink);

	for (int k = 1; k < this->cyclesLength + 1; k++) {
		int previous = k - 1;
		for (unordered_set<int>::const_iterator it = verticesPerIteration.at(previous).begin(); it != verticesPerIteration.at(previous).end(); it++) {
			const Vertex* v = &this->vertices.at(*it);
			for (unordered_map<int, int>::const_iterator arc = v->getInGoingArcs().begin(); arc != v->getInGoingArcs().end(); arc++) {
				if (availableArcs.at(arc->first).at(v->getId()) && distances.at(v->getId()) + 1 < distances.at(arc->first)) {
					distances.at(arc->first) = distances.at(v->getId()) + 1;
					verticesPerIteration.at(k).insert(arc->first);
				}
			}
		}
	}
	return distances;

}

vector<int> Instance::BreadthFirstSearchPreprocessing_forward(const vector<vector<int>>& availableArcs, const int& source) {

	vector<int> distances(this->vertices.size(), ::OMEGA);
	distances.at(source) = 0;
	vector<int> visited(this->vertices.size(), false);
	visited.at(source) = true;
	list<int> queue = { source };
	int level = 0;

	while (!queue.empty() && level <= this->cyclesLength) {
		int id = queue.front();
		queue.pop_front();
		const Vertex* v = &this->vertices.at(id);
		for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
			if (availableArcs.at(v->getId()).at(arc->first) && !visited.at(arc->first)) {
				visited.at(arc->first) = true;
				distances.at(arc->first) = distances.at(v->getId()) + 1;
				queue.push_back(arc->first);
				level = max(level, distances.at(v->getId()) + 1);
				if (level > this->cyclesLength) {
					break;
				}
			}
		}
	}

	return distances;

}

vector<int> Instance::BreadthFirstSearchPreprocessing_backward(const vector<vector<int>>& availableArcs, const int& sink) {

	vector<int> distances(this->vertices.size(), ::OMEGA);
	distances.at(sink) = 0;
	vector<int> visited(this->vertices.size(), false);
	visited.at(sink) = true;
	list<int> queue = { sink };
	int level = 0;

	while (!queue.empty() && level <= this->cyclesLength) {
		int id = queue.front();
		queue.pop_front();
		const Vertex* v = &this->vertices.at(id);
		for (unordered_map<int, int>::const_iterator arc = v->getInGoingArcs().begin(); arc != v->getInGoingArcs().end(); arc++) {
			if (availableArcs.at(arc->first).at(v->getId()) && !visited.at(arc->first)) {
				visited.at(arc->first) = true;
				distances.at(arc->first) = distances.at(v->getId()) + 1;
				queue.push_back(arc->first);
				level = max(level, distances.at(v->getId()) + 1);
				if (level > this->cyclesLength) {
					break;
				}
			}
		}
	}

	return distances;

}

void Instance::preprocessingOmer(const unordered_map<int, int>& mapIds) {

	clock_t startOP, endOP;
	startOP = clock();

	vector<vector<int>> availableArcs(this->vertices.size(), vector<int>(this->vertices.size(), false));
	vector<pair<int, int>> inOutDegPerVertex(this->vertices.size());
	for (int i = 0; i < this->vertices.size(); i++) {
		const Vertex* v = &this->vertices.at(i);
		for (unordered_map<int, int>::const_iterator it = v->getOutGoingArcs().begin(); it != v->getOutGoingArcs().end(); it++) {
			availableArcs.at(v->getId()).at(it->first) = true;
		}
		for (unordered_map<int, int>::const_iterator it = v->getInGoingArcs().begin(); it != v->getInGoingArcs().end(); it++) {
			availableArcs.at(it->first).at(v->getId()) = true;
		}
		inOutDegPerVertex.at(i) = make_pair(v->getInGoingArcs().size(), v->getOutGoingArcs().size());
	}

	//cout << "337\t" << inOutDegPerVertex.at(337).second << endl;

	//this->pairsToProcess = vector<int>(this->vertices.size(), false);
	//this->arcsPerPairToProcess = vector<vector<vector<int>>>(this->vertices.size(), vector<vector<int>>(this->vertices.size(), vector<int>(this->vertices.size(), false)));
	this->arcsPerPairToProcess = vector<vector<vector<int>>>(this->vertices.size(), vector<vector<int>>());
	this->nodesPerPairToProcess = vector<unordered_set<int>>(this->vertices.size(), unordered_set<int>());

	vector<pair<int, int>> sortedVertices;
	for (int i = 0; i < this->vertices.size(); i++) {
		const Vertex* v = &this->vertices.at(i);
		if (v->getType() == 'I' && !v->getOutGoingArcs().empty() && !v->getInGoingArcs().empty()) {
			int inc = v->getOutGoingArcs().size() + v->getInGoingArcs().size();
			sortedVertices.push_back(make_pair(inc, v->getId()));
		}
	}

	sort(sortedVertices.begin(), sortedVertices.end());
	
	int cc = 0;
	while (!sortedVertices.empty()) {

		int vId = sortedVertices.back().second;

		if (inOutDegPerVertex.at(vId).first > 0 && inOutDegPerVertex.at(vId).second > 0) {

			//int pos1 = mapIds.at(vId);
			vector<int> distancesForward = BellmanFordPreprocessing_forward(availableArcs, vId);
			//vector<int> distancesForward = BreadthFirstSearchPreprocessing_forward(availableArcs, vId);
			vector<int> distancesBackward = BellmanFordPreprocessing_backward(availableArcs, vId);
			//vector<int> distancesBackward = BreadthFirstSearchPreprocessing_backward(availableArcs, vId);


			//cout << "ID " << vId << "\t" << pos1 << endl;

			vector<int> vFromPair;
			for (int i = 0; i < sortedVertices.size(); i++) {
				int wId = sortedVertices.at(i).second;
				/*int pos2 = mapIds.at(wId);
				if (this->FloydWarshallMatrix.at(pos1).at(pos2) + this->FloydWarshallMatrix.at(pos2).at(pos1) <= this->cyclesLength) {
					vFromPair.push_back(wId);
				}*/
				if (distancesForward.at(wId) + distancesBackward.at(wId) <= this->cyclesLength) {
					vFromPair.push_back(wId);
				}
			}

			if (!vFromPair.empty()) {

				int ccArcs = 0;
				vector<vector<int>> arcs(this->vertices.size());

				for (int i = 0; i < vFromPair.size(); i++) {
					int idi = vFromPair.at(i);
					//int posi = mapIds.at(idi);
					for (int j = 0; j < vFromPair.size(); j++) {
						int idj = vFromPair.at(j);
						if (availableArcs.at(idi).at(idj) &&
							distancesForward.at(idi) + distancesBackward.at(idj) <= this->cyclesLength - 1) {
							arcs.at(idi).push_back(idj);
							this->nodesPerPairToProcess.at(vId).insert(idi);
							this->nodesPerPairToProcess.at(vId).insert(idj);
							ccArcs++;
						}
						//int posj = mapIds.at(idj);
						//if (availableArcs.at(idi).at(idj) &&
						//	this->FloydWarshallMatrix.at(pos1).at(posi) + this->FloydWarshallMatrix.at(posj).at(pos1) <= this->cyclesLength - 1) {
						//	//this->arcsPerPairToProcess.at(vId).at(idi).at(idj) = true;
						//	this->arcsPerPairToProcess.at(vId).insert(make_pair(idi, idj));
						//	ccArcs++;
						//}
					}
				}


				if (ccArcs > 0) {
					cc++;
					this->arcsPerPairToProcess.at(vId) = arcs;
					this->nodesPerPairToProcess.at(vId).insert(vId);
					this->pairsToProcess.push_back(vId);
					//this->pairsToProcess.at(vId) = true;
					this->avgNodesGraphsOP += this->nodesPerPairToProcess.at(vId).size();
					this->avgArcsGraphsOP += ccArcs;
					//cout << "PAIR " << vId << "\tSIZE: " << this->nodesPerPairToProcess.at(vId).size() << "\t" << ccArcs << endl;
				}
				else {
					this->arcsPerPairToProcess.at(vId).clear();
				}

			}

		}

		const Vertex* v = &this->vertices.at(vId);
		for (int i = 0; i < sortedVertices.size(); i++) {
			int idi = sortedVertices.at(i).second;
			if (v->getOutGoingArcs().find(idi) != v->getOutGoingArcs().end()) {
				sortedVertices.at(i).first--;
				availableArcs.at(v->getId()).at(idi) = false;
				inOutDegPerVertex.at(idi).first--;
			}
			if (v->getInGoingArcs().find(idi) != v->getInGoingArcs().end()) {
				sortedVertices.at(i).first--;
				availableArcs.at(idi).at(v->getId()) = false;
				inOutDegPerVertex.at(idi).second--;
			}
		}

		//cout << "337\t" << inOutDegPerVertex.at(337).second << endl;
		sortedVertices.pop_back();
		sort(sortedVertices.begin(), sortedVertices.end());

	}

	endOP = clock();
	this->timeOmerPreprocessing = (float)(endOP - startOP) / CLOCKS_PER_SEC;
	this->pairGraphsOP = this->pairsToProcess.size();
	this->avgArcsGraphsOP /= static_cast<double>(this->pairGraphsOP);
	this->avgNodesGraphsOP /= static_cast<double>(this->pairGraphsOP);
	//cout << "FINAL NUMBER OF PAIRS\t" << cc << endl;

}

void Instance::processData(const int& ngSetSize) {

	read();
	this->FloydWarshallMatrix = preprocessingFloydWarshall();
	/*vector<vector<int>> arcsToRemove = detectArcsToRemove(this->FloydWarshallMatrix);
	vector<int> isolatedVertices = detectIsolatedVertices(arcsToRemove);*/
	int vertexNumber = this->altruisticDonorsNumber + this->incompatiblePairsNumber + 1;
	vector<vector<int>> arcsToRemove(vertexNumber, vector<int>(vertexNumber, -1));
	vector<int> isolatedVertices(vertexNumber, -1);
	if (this->altruisticDonorsNumber == 0) {
		isolatedVertices.at(0) = 1;
	}
	buildVertices(this->FloydWarshallMatrix, arcsToRemove, isolatedVertices, ngSetSize);

}

const int& Instance::getCyclesLength() const {
	return this->cyclesLength;
}
const int& Instance::getChainsLength() const {
	return this->chainsLength;
}
//const vector<vector<int>>& Instance::getCompatibleMatrix() const {
//	return this->compatibleMatrix;
//}
//const vector<vector<int>>& Instance::getFloydWarshallMatrix() const {
//	return this->FloydWarshallMatrix;
//}
const int& Instance::getAltruisticDonorsNumber() const {
	return this->altruisticDonorsNumber;
}
const int& Instance::getIncompatiblePairsNumber() const {
	return this->incompatiblePairsNumber;
}
const int& Instance::getVertexNumber() const {
	return this->vertices.size();
}
const int& Instance::getDummyNodeId() const {
	return this->dummyNodeId;
}
const vector<Vertex>& Instance::getVertices() const {
	return this->vertices;
}
const vector<int>& Instance::getAltruisticDonors() const {
	return this->altruisticDonors;
}
const vector<int>& Instance::getIncompatiblePairs() const {
	return this->incompatiblePairs;
}
const int& Instance::getWordsNumber() const {
	return this->wordsNumber;
}
const int& Instance::getExchangesPerVertexInitialisation() const {
	return this->exchangesPerVertexInitialisation;
}
const vector<int>& Instance::getPairsToProcess() const {
	return this->pairsToProcess;
}
const vector<vector<vector<int>>>& Instance::getArcsPerPairToProcess() const {
	return this->arcsPerPairToProcess;
}
const vector<unordered_set<int>>& Instance::getNodesPerPairToProcess() const {
	return this->nodesPerPairToProcess;
}
const double& Instance::getTimeFloydWarshall() const {
	return this->timeFloydWarshall;
}
const double& Instance::getTimeOmerPreprocessing() const {
	return this->timeOmerPreprocessing;
}
const int& Instance::getRemovedArcsFW() const {
	return this->removedArcsFW;
}
const int& Instance::getRemovedNodesFW() const {
	return this->removedNodesFW;
}
const int& Instance::getPairGraphsOP() const {
	return this->pairGraphsOP;
}
const double& Instance::getAvgNodesGraphsOP() const {
	return this->avgNodesGraphsOP;
}
const double& Instance::getAvgArcsGraphsOP() const {
	return this->avgArcsGraphsOP;
}
const unordered_map<int, int>& Instance::getIKEPdictionary() const {
	return this->IKEPdictionary;
}
const unordered_map<int, int>& Instance::getIKEPperiodDictionary() const {
	return this->IKEPperiodDictionary;
}

const int& Instance::get_shortest_path_FW(const int& origin, const int& destination) const {
	return this->FloydWarshallMatrix.at(origin).at(destination);
}

const string Instance::toString(const bool& areArcsPrinted) const {
	
	string str;
	str.append("NUMBER OF INCOMPATIBLE PAIR: " + to_string(this->incompatiblePairsNumber) + "\tNUMBER OF ALTRUISTIC DONORS: " + to_string(this->altruisticDonorsNumber) +
		"\tMAX LENGTH CYCLES: " + to_string(this->cyclesLength) + "\tMAX LENGTH CHAINS: " + to_string(this->chainsLength) + "\nVERTICES\n");
	if (this->IKEPdictionary.empty()) {
		for (int i = 0; i < this->vertices.size(); i++) {
			str.append(this->vertices.at(i).toString(true) + "\n"/*"\n\t\tORIGNAL ID: " + to_string(this->IKEPdictionary.at(i))*/);
		}
	}
	else {
		for (int i = 0; i < this->vertices.size(); i++) {
			str.append(this->vertices.at(i).toString(true) + "\n\t\tORIGNAL ID: " + to_string(this->IKEPdictionary.at(i)) + "\n");
		}
	}
	return str;

}

void Instance::print(const string& filename) const {
	ofstream mystream;
	mystream.open(::solutionPath + filename + "_" + thread + ".txt", ios::app);

	mystream << "// P : Nombre de paires patient-donneur\n" << this->incompatiblePairsNumber << "\n\n";
	mystream << "// N : Nombre de donneurs altruistes\n" << this->altruisticDonorsNumber << "\n\n";
	mystream << "// K : Taille max cycles\n" << this->cyclesLength << "\n\n";
	mystream << "// L : Taille max chaines\n" << this->chainsLength << "\n\n";

	mystream << "// Matrice des benefices medicaux des echanges\n";
	mystream << "// Les N premieres lignes correspondent aux donneurs altruistes\n";
	mystream << "// Les P dernieres lignes correspondent aux paires patient-donneur\n";
	mystream << "// Sur chaque ligne i, on indique le benefice medical de la transplantation\n//\t du rein du donneur i au patient de la paire patient-donneur j\n";
	mystream << "// Une valeur -1 signifie que la transplantation n'est pas realisable\n";

	for (int i = 0; i < this->vertices.size(); i++) {
		if (this->vertices.at(i).getType() == 'A') {
			for (int j = 0; j < this->vertices.size(); j++) {
				if (this->vertices.at(j).getType() == 'I') {
					mystream << this->compatibleMatrix.at(i).at(j) << "\t";
				}
			}
			mystream << "\n";
		}
	}
	mystream << "\n";

	for (int i = 0; i < this->vertices.size(); i++) {
		if (this->vertices.at(i).getType() == 'I') {
			for (int j = 0; j < this->vertices.size(); j++) {
				if (this->vertices.at(j).getType() == 'I') {
					mystream << this->compatibleMatrix.at(i).at(j) << "\t";
				}
			}
			mystream << "\n";
		}
	}
	mystream << "\n";

	mystream.close();
}

void Instance::print_PrefLib_format() const {

	int edgeNumber = 0;
	for (int i = 0; i < this->incompatiblePairs.size(); i++) {
		int id = this->incompatiblePairs.at(i);
		const Vertex* v = &this->vertices.at(id);
		edgeNumber += v->getOutGoingArcs().size();
	}
	for (int i = 0; i < this->altruisticDonors.size(); i++) {
		int id = this->altruisticDonors.at(i);
		const Vertex* v = &this->vertices.at(id);
		edgeNumber += v->getOutGoingArcs().size();
	}

	ofstream mystream;
	mystream.open(::solutionPath + this->name + ".wmd", ios::app);

	/*mystream << "# FILE NAME: " << this->name + ".wmd" << "\n";
	mystream << "# TITLE: Kidney Matching - " << this->incompatiblePairsNumber << " with " << this->altruisticDonorsNumber << "\n";
	mystream << "# DESCRIPTION:\n";
	mystream << "# DATA TYPE: wmd\n";
	mystream << "# MODIFICATION TYPE: synthetic\n";
	mystream << "# RELATES TO: \n";
	mystream << "# RELATED FILES: " << this->name + ".dat" << "\n";
	mystream << "# PUBLICATION DATE: 2023-08-23\n";
	mystream << "# MODIFICATION DATE: 2023-08-23\n";
	mystream << "# NUMBER ALTERNATIVES: " << this->incompatiblePairsNumber + this->altruisticDonorsNumber << "\n";
	mystream << "# NUMBER EDGES: " << edgeNumber << "\n";*/
	int counter = 1;
	unordered_map<int, int> dict;
	for (int i = 0; i < this->incompatiblePairs.size(); i++) {
		int id = this->incompatiblePairs.at(i);
		dict.insert(make_pair(id, counter));
		//mystream << "# ALTERNATIVE NAME " << counter << ": Pair " << counter << "\n";
		counter++;
	}
	for (int i = 0; i < this->altruisticDonors.size(); i++) {
		int id = this->altruisticDonors.at(i);
		dict.insert(make_pair(id, counter));
		//mystream << "# ALTERNATIVE NAME " << counter << ": Alturist " << counter << "\n";
		counter++;
	}
	mystream << this->incompatiblePairsNumber + this->altruisticDonorsNumber << "," << edgeNumber << "\n";
	for (int i = 0; i < this->incompatiblePairs.size(); i++) {
		int id = this->incompatiblePairs.at(i);
		mystream << dict.at(id) << ",Pair " << dict.at(id) << "\n";
	}
	for (int i = 0; i < this->altruisticDonors.size(); i++) {
		int id = this->altruisticDonors.at(i);
		mystream << dict.at(id) << ",Altruist " << dict.at(id) << "\n";
	}
	for (int i = 0; i < this->incompatiblePairs.size(); i++) {
		int id = this->incompatiblePairs.at(i);
		const Vertex* v = &this->vertices.at(id);
		for (unordered_map<int, int>::const_iterator it = v->getOutGoingArcs().begin(); it != v->getOutGoingArcs().end(); it++) {
			mystream << dict.at(id)-1 << "," << dict.at(it->first)-1 << "," << it->second << "\n";
		}
	}
	for (int i = 0; i < this->altruisticDonors.size(); i++) {
		int id = this->altruisticDonors.at(i);
		const Vertex* v = &this->vertices.at(id);
		for (unordered_map<int, int>::const_iterator it = v->getOutGoingArcs().begin(); it != v->getOutGoingArcs().end(); it++) {
			mystream << dict.at(id)-1 << "," << dict.at(it->first)-1 << "," << it->second << "\n";
		}
	}
	mystream.close();


	ofstream mystream_dat;
	mystream_dat.open(::solutionPath + this->name + ".dat", ios::app);

	mystream_dat << "Pair,Patient,Donor,Wife-P?,%Pra,Out-Deg,Altruist\n";
	for (int i = 0; i < this->incompatiblePairs.size(); i++) {
		int id = this->incompatiblePairs.at(i);
		const Vertex* v = &this->vertices.at(id);
		mystream_dat << dict.at(id) << ",A,B,0,0.05," << v->getOutGoingArcs().size() << ",0\n";
	}
	for (int i = 0; i < this->altruisticDonors.size(); i++) {
		int id = this->altruisticDonors.at(i);
		const Vertex* v = &this->vertices.at(id);
		mystream_dat << dict.at(id) << ",A,B,0,0.05," << v->getOutGoingArcs().size() << ",1\n";
	}
	mystream_dat.close();

}

void Instance::resetNgSet(const int& ngSetSize) {
	for (int i = 0; i < this->vertices.size(); i++) {
		this->bitDictionary.at(this->vertices.at(i).getWord()).insert(make_pair(this->vertices.at(i).getBitKey(), i));
		this->vertices.at(i).initializeNgSet(this->wordsNumber);
		if (ngSetSize > 0) {
			this->vertices.at(i).addNgNeighbour(this->vertices.at(i).getWord(), this->vertices.at(i).getBitKey());
			for (int j = 0; j < min(this->vertices.at(i).getExtendedPredecessors().size(), ngSetSize - 1); j++) {
				int predId = this->vertices.at(i).getExtendedPredecessors().at(j);
				this->vertices.at(i).addNgNeighbour(this->vertices.at(predId).getWord(), this->vertices.at(predId).getBitKey());
			}
		}
	}
}

void Instance::set_exchangesPerVertexInitialisation(const int& n) {
	this->exchangesPerVertexInitialisation = n;
}