#include "BellmanFord.h"

BellmanFord::BellmanFord(Instance& instance, DualSolution* dual_variables, vector<Exchange>* rmp_columns, vector<Constraint<GRBConstr>*>* branching_constraints, vector<Constraint<GRBConstr>*>* cut_constraints)
	: PricingSubProblemAlgorithmAbstract(instance, dual_variables, rmp_columns, branching_constraints, cut_constraints), vertices(instance.getVertices()) {
	this->cyclesLength = instance.getCyclesLength();
	this->wordsNumber = instance.getWordsNumber();
	this->source = instance.getDummyNodeId();
	this->chainsLength = instance.getChainsLength();
	this->pairsAsSourcesToConsider = instance.getPairsToProcess();
	this->nodesPerPairToProcess = instance.getNodesPerPairToProcess();
}

BellmanFord::~BellmanFord() {
}

bool BellmanFord::can_solve(const string& request) const {
	return request == "EXACTGENERATOR" || request == "WHATEVER";
}

//vector<Exchange> BellmanFord::solve(const string& request) {
//
//	//clock_t ss, tt;
//
//	if (can_solve(request)) {
//
//		this->is_early_terminated = false;
//		this->solution_pool.clear();
//		this->value = ::OMEGA;
//		this->favourablyPricedVariablesCounter = 0;
//		//this->vertexCovered = vector<int>(this->instance.getVertices().size(), 0);
//
//		/*PRICE CYCLES*/
//		if (/*this->cyclesLength > ::CYCLESINITIALISATIONLENGTH*/true) {
//
//			this->value_chains = ::OMEGA;
//
//			buildVertices_chains();
//			buildDualPrices_chains();
//			buildActiveNonRobustCuts_chains();
//
//			//dynamic programming
//			list<Label> forwardLabels;
//			if (this->active_non_robust_cuts.empty()) {
//				forwardLabels = BellmanFord_chains();
//			}
//			else {
//				//forwardLabels = extendForward_non_robust_chains();
//			}
//
//			if (this->value_chains < -EPSILON) {
//				//build exchange object
//				addExchanges_chains(this->optimalLabel_chains, true);
//				for (list<Label>::const_iterator label = forwardLabels.begin(); label != forwardLabels.end(); label++) {
//					/*if (::isToPrint) {
//						cout << "LABEL " << label->toString() << "\n";
//					}*/
//					if (label->getCost() < -EPSILON && label->getLength() > 1) {
//						addExchanges_chains(*label, false);
//
//						if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
//							break;
//						}
//
//					}
//				}
//				/*cout << this->optimalLabel_chains.toString() << "\n";
//				cout << "\n\n";*/
//			}
//			
//
//		}
//
//
//		/*PRICE CHAINS*/
//		if (/*this->chainsLength > ::CHAINSINITIALISATIONLENGTH && */this->value_chains > -::EPSILON) {
//
//			this->value_cycles = ::OMEGA;
//
//			shuffle(this->pairsAsSourcesToConsider.begin(), this->pairsAsSourcesToConsider.end(), ::generator);
//
//			//buildVertices_cycles();
//			buildDualPrices_cycles();
//			buildActiveNonRobustCuts_cycles();
//
//			//dynamic programming
//			for (int i = 0; i < this->pairsAsSourcesToConsider.size(); i++) {
//				this->valuePerPricing = 0.0;
//				//cout << this->vertices.at(this->sourcesToConsider.at(i)).toString(false) << endl;
//				int source = this->pairsAsSourcesToConsider.at(i);
//
//				if (this->verticesToConsider.at(source) == 1 && this->tabuList.find(source) == this->tabuList.end()) {
//
//					////////////////////////////////////////////////////////////////////////BELLMAN FORD///////////////////////////////////////////////////
//					if (this->active_non_robust_cuts.empty()) {
//						//ss = clock();
//
//						//vector<list<Label>> forwardLabels = extendForward_cycles(source);
//
//						list<Label> forwardLabels = BellmanFord_cycles(source, this->cyclesLength + 1, this->instance.getArcsPerPairToProcess().at(source));
//						//tt = clock();
//						//cout << "SOURCE "<<source << "DUR " << (float)(tt - ss) / CLOCKS_PER_SEC << "\t" << this->valuePerPricing << "\n";
//						if (this->valuePerPricing < -EPSILON) {
//							addExchanges_cycles(this->optimalLabel_cycles);
//							//cout << this->solution_pool.back().toString() << endl;
//							/*for (list<Label>::const_iterator label = forwardLabels.at(source).begin(); label != forwardLabels.at(source).end(); label++) {
//								if (label->getLength() > 1) {
//									addExchanges_cycles(*label);
//									if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
//										break;
//									}
//								}
//							}*/
//							for (list<Label>::const_iterator label = forwardLabels.begin(); label != forwardLabels.end(); label++) {
//								if (label->getLength() > 1) {
//									addExchanges_cycles(*label);
//									if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
//										break;
//									}
//								}
//							}
//						}
//						else {
//							this->tabuList.insert(source);
//						}
//					}
//					else {
//
//						/*vector<list<Label>> forwardLabels = extendForward_non_robust_cycles(source);
//						if (this->valuePerPricing < -EPSILON) {
//							addExchanges_cycles(this->optimalLabel);
//							for (list<Label>::const_iterator label = forwardLabels.at(source).begin(); label != forwardLabels.at(source).end(); label++) {
//								if (label->getCost() < -EPSILON && label->getLength() > 1) {
//									addExchanges_cycles(*label);
//								}
//							}
//						}*/
//					}
//
//					if (::strictly_less(this->valuePerPricing, this->value_cycles)) {
//						this->value_cycles = this->valuePerPricing;
//						this->optimalLabel = this->optimalLabel_cycles;
//					}
//					if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
//						break;
//					}
//
//				}
//
//			}
//
//			if (this->value_cycles > -EPSILON) {
//
//				this->value_cycles = ::OMEGA;
//				vector<int> removeFromTabuList;
//				buildDualPrices_cycles();
//				buildActiveNonRobustCuts_cycles();
//
//				for (unordered_set<int>::const_iterator it = this->tabuList.begin(); it != this->tabuList.end(); it++) {
//
//					int source = *it;
//					this->valuePerPricing = 0.0;
//
//					if (this->verticesToConsider.at(source) == 1) {
//
//						////////////////////////////////////////////////////////////////////////BELLMAN FORD///////////////////////////////////////////////////
//						if (this->active_non_robust_cuts.empty()) {
//							//ss = clock();
//
//							list<Label> forwardLabels = BellmanFord_cycles(source, this->cyclesLength + 1, this->instance.getArcsPerPairToProcess().at(source));
//							//tt = clock();
//							//cout << "SOURCE "<<source << "DUR " << (float)(tt - ss) / CLOCKS_PER_SEC << "\t" << this->valuePerPricing << "\n";
//							if (this->valuePerPricing < -EPSILON) {
//								removeFromTabuList.push_back(source);
//								addExchanges_cycles(this->optimalLabel_cycles);
//								for (list<Label>::const_iterator label = forwardLabels.begin(); label != forwardLabels.end(); label++) {
//									if (label->getLength() > 1) {
//										addExchanges_cycles(*label);
//										if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
//											break;
//										}
//									}
//								}
//							}
//						}
//						else {
//
//							/*vector<list<Label>> forwardLabels = extendForward_non_robust_cycles(source);
//							if (this->valuePerPricing < -EPSILON) {
//								addExchanges_cycles(this->optimalLabel);
//								for (list<Label>::const_iterator label = forwardLabels.at(source).begin(); label != forwardLabels.at(source).end(); label++) {
//									if (label->getCost() < -EPSILON && label->getLength() > 1) {
//										addExchanges_cycles(*label);
//									}
//								}
//							}*/
//						}
//
//						if (::strictly_less(this->valuePerPricing, this->value_cycles)) {
//							this->value_cycles = this->valuePerPricing;
//							this->optimalLabel = this->optimalLabel_cycles;
//						}
//						if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
//							break;
//						}
//
//					}
//
//				}
//
//				for (int l = 0; l < removeFromTabuList.size(); l++) {
//					this->tabuList.erase(removeFromTabuList.at(l));
//				}
//
//			}
//			
//
//		}
//
//		this->value = min(this->value_chains, this->value_cycles);
//		if (::strictly_less(this->value_chains, this->value_cycles)) {
//			this->optimalLabel = this->optimalLabel_chains;
//		}
//		//cout << this->optimalLabel.toString() << "\n\n";
//
//		update_failed_to_find_favorably_priced_columns();
//
//		if (!has_failed_to_find_favorably_priced_columns()) {
//			return this->solution_pool;
//		}
//		else
//			return PricingSubProblemAlgorithmAbstract<Instance, vector<Exchange>, DualSolution, GRBConstr>::solve(request);
//
//	}
//	else
//		return PricingSubProblemAlgorithmAbstract<Instance, vector<Exchange>, DualSolution, GRBConstr>::solve(request);
//}

vector<Exchange> BellmanFord::solve(const string& request, const double time_limit) {

	//clock_t ss, tt;

	if (can_solve(request)) {

		this->is_early_terminated = false;
		this->solution_pool.clear();
		this->value = ::OMEGA;
		this->favourablyPricedVariablesCounter = 0;
		//this->vertexCovered = vector<int>(this->instance.getVertices().size(), 0);

		/*PRICE CYCLES*/
		if (/*this->cyclesLength > ::CYCLESINITIALISATIONLENGTH*/true) {

			this->value_cycles = ::OMEGA;

			shuffle(this->pairsAsSourcesToConsider.begin(), this->pairsAsSourcesToConsider.end(), ::generator);

			//buildVertices_cycles();
			buildDualPrices_cycles();
			buildActiveNonRobustCuts_cycles();

			//dynamic programming
			for (int i = 0; i < this->pairsAsSourcesToConsider.size(); i++) {
				this->valuePerPricing = 0.0;
				//cout << this->vertices.at(this->sourcesToConsider.at(i)).toString(false) << endl;
				int source = this->pairsAsSourcesToConsider.at(i);

				if (this->verticesToConsider.at(source) == 1 && this->tabuList.find(source) == this->tabuList.end()) {

					////////////////////////////////////////////////////////////////////////BELLMAN FORD///////////////////////////////////////////////////
					if (this->active_non_robust_cuts.empty()) {
						//ss = clock();

						//vector<list<Label>> forwardLabels = extendForward_cycles(source);

						list<Label> forwardLabels = BellmanFord_cycles(source, this->cyclesLength + 1, this->instance.getArcsPerPairToProcess().at(source));
						//tt = clock();
						//cout << "SOURCE "<<source << "DUR " << (float)(tt - ss) / CLOCKS_PER_SEC << "\t" << this->valuePerPricing << "\n";
						if (this->valuePerPricing < -EPSILON) {
							addExchanges_cycles(this->optimalLabel_cycles);
							//cout << this->solution_pool.back().toString() << endl;
							/*for (list<Label>::const_iterator label = forwardLabels.at(source).begin(); label != forwardLabels.at(source).end(); label++) {
								if (label->getLength() > 1) {
									addExchanges_cycles(*label);
									if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
										break;
									}
								}
							}*/
							for (list<Label>::const_iterator label = forwardLabels.begin(); label != forwardLabels.end(); label++) {
								if (label->getLength() > 1) {
									addExchanges_cycles(*label);
									if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
										break;
									}
								}
							}
						}
						else {
							this->tabuList.insert(source);
						}
					}
					else {

						/*vector<list<Label>> forwardLabels = extendForward_non_robust_cycles(source);
						if (this->valuePerPricing < -EPSILON) {
							addExchanges_cycles(this->optimalLabel);
							for (list<Label>::const_iterator label = forwardLabels.at(source).begin(); label != forwardLabels.at(source).end(); label++) {
								if (label->getCost() < -EPSILON && label->getLength() > 1) {
									addExchanges_cycles(*label);
								}
							}
						}*/
					}

					if (::strictly_less(this->valuePerPricing, this->value_cycles)) {
						this->value_cycles = this->valuePerPricing;
						this->optimalLabel = this->optimalLabel_cycles;
					}
					if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
						break;
					}

				}

			}

		}


		/*PRICE CHAINS*/
		if (/*this->chainsLength > ::CHAINSINITIALISATIONLENGTH && */this->value_cycles > -::EPSILON) {

			this->value_chains = ::OMEGA;

			buildVertices_chains();
			buildDualPrices_chains();
			buildActiveNonRobustCuts_chains();

			//dynamic programming
			list<Label> forwardLabels;
			if (this->active_non_robust_cuts.empty()) {
				forwardLabels = BellmanFord_chains();
			}
			else {
				//forwardLabels = extendForward_non_robust_chains();
			}

			if (this->value_chains < -EPSILON) {
				//build exchange object
				addExchanges_chains(this->optimalLabel_chains, true);
				for (list<Label>::const_iterator label = forwardLabels.begin(); label != forwardLabels.end(); label++) {
					/*if (::isToPrint) {
						cout << "LABEL " << label->toString() << "\n";
					}*/
					if (label->getCost() < -EPSILON && label->getLength() > 1) {
						addExchanges_chains(*label, false);
						
						if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
							break;
						}

					}
				}
				/*cout << this->optimalLabel_chains.toString() << "\n";
				cout << "\n\n";*/
			}
			else {

				this->value_cycles = ::OMEGA;
				vector<int> removeFromTabuList;
				buildDualPrices_cycles();
				buildActiveNonRobustCuts_cycles();

				for (unordered_set<int>::const_iterator it = this->tabuList.begin(); it != this->tabuList.end(); it++) {

					int source = *it;
					this->valuePerPricing = 0.0;

					if (this->verticesToConsider.at(source) == 1) {

						////////////////////////////////////////////////////////////////////////BELLMAN FORD///////////////////////////////////////////////////
						if (this->active_non_robust_cuts.empty()) {
							//ss = clock();

							list<Label> forwardLabels = BellmanFord_cycles(source, this->cyclesLength + 1, this->instance.getArcsPerPairToProcess().at(source));
							//tt = clock();
							//cout << "SOURCE "<<source << "DUR " << (float)(tt - ss) / CLOCKS_PER_SEC << "\t" << this->valuePerPricing << "\n";
							if (this->valuePerPricing < -EPSILON) {
								removeFromTabuList.push_back(source);
								addExchanges_cycles(this->optimalLabel_cycles);
								for (list<Label>::const_iterator label = forwardLabels.begin(); label != forwardLabels.end(); label++) {
									if (label->getLength() > 1) {
										addExchanges_cycles(*label);
										if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
											break;
										}
									}
								}
							}
						}
						else {

							/*vector<list<Label>> forwardLabels = extendForward_non_robust_cycles(source);
							if (this->valuePerPricing < -EPSILON) {
								addExchanges_cycles(this->optimalLabel);
								for (list<Label>::const_iterator label = forwardLabels.at(source).begin(); label != forwardLabels.at(source).end(); label++) {
									if (label->getCost() < -EPSILON && label->getLength() > 1) {
										addExchanges_cycles(*label);
									}
								}
							}*/
						}

						if (::strictly_less(this->valuePerPricing, this->value_cycles)) {
							this->value_cycles = this->valuePerPricing;
							this->optimalLabel = this->optimalLabel_cycles;
						}
						if (this->solution_pool.size() > ::PROMISINGVARIABLESPERITERATION) {
							break;
						}

					}

				}

				for (int l = 0; l < removeFromTabuList.size(); l++) {
					this->tabuList.erase(removeFromTabuList.at(l));
				}

			}

		}

		this->value = min(this->value_chains, this->value_cycles);
		if (::strictly_less(this->value_chains, this->value_cycles)) {
			this->optimalLabel = this->optimalLabel_chains;
		}
		//cout << this->optimalLabel.toString() << "\n\n";

		update_failed_to_find_favorably_priced_columns();

		if (!has_failed_to_find_favorably_priced_columns()) {
			return this->solution_pool;
		}
		else
			return PricingSubProblemAlgorithmAbstract<Instance, vector<Exchange>, DualSolution, GRBConstr>::solve(request, time_limit);

	}
	else
		return PricingSubProblemAlgorithmAbstract<Instance, vector<Exchange>, DualSolution, GRBConstr>::solve(request, time_limit);
}

void BellmanFord::update_failed_to_find_favorably_priced_columns() {
	this->fails_to_find_favorably_priced_columns = false;
	if (this->value > -EPSILON) {
		this->fails_to_find_favorably_priced_columns = true;
	}
}

void BellmanFord::buildVertices_cycles() {
	this->verticesToConsider.clear();
	this->sourcesToConsider.clear();
	this->outgoingArcsToConsider = vector<vector<int>>(this->instance.getVertexNumber(), vector<int>());
	vector<vector<bool>> arcsToDiscard(this->instance.getVertexNumber(), vector<bool>(this->instance.getVertexNumber(), false));
	vector<bool> verticesToDiscard(this->instance.getVertexNumber(), false);
	//cout << "ARCS DISCARDER:\n";
	for (int i = 0; i < this->branching_constraints->size(); i++) {
		if (this->branching_constraints->at(i)->get_name() == "ARCBRANCH" && this->branching_constraints->at(i)->get_rhs() == 0) {
			int id1 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().first;
			int id2 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().second;
			arcsToDiscard.at(id1).at(id2) = true;
			/*if (::isToPrint) {
				cout << "ARC DISCARDED " << id1 << "\t" << id2 << endl;
			}*/
		}
		if (this->branching_constraints->at(i)->get_name() == "VISITBRANCH" && this->branching_constraints->at(i)->get_rhs() == 0) {
			int id = dynamic_cast<VisitBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_item();
			verticesToDiscard.at(id) = true;
			/*if (::isToPrint) {
				cout << "VERTEX DISCARDED " << id << endl;
			}*/
		}
	}
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		if (!verticesToDiscard.at(v->getId())) {
			if (v->getType() == 'I') {
				this->verticesToConsider.push_back(v->getId());
				this->sourcesToConsider.push_back(v->getId());
				vector<int> outgoing;
				for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
					if (!arcsToDiscard.at(v->getId()).at(arc->first) && !verticesToDiscard.at(arc->first)) {
						outgoing.push_back(arc->first);
					}
				}
				this->outgoingArcsToConsider.at(v->getId()) = outgoing;
			}
		}
	}
}

void BellmanFord::buildActiveNonRobustCuts_cycles() {
	this->active_non_robust_cuts.clear();
	this->active_non_robust_duals.clear();
	for (int i = 0; i < this->cut_constraints->size(); i++) {
		if (this->dual_variables->get_sigma_i(i) > ::EPSILON) {
			this->active_non_robust_cuts.push_back(i);
			this->active_non_robust_duals.push_back(this->dual_variables->get_sigma_i(i));
		}
	}
}

vector<list<Label>> BellmanFord::extendForward_cycles(const int& source) {

	try {

		//bool isToprint = (source == 13);

		//INITIALIZATION
		int vSize = this->sourcesToConsider.size();
		vector<list<Label>> labels(this->vertices.size());
		Label sourceLabel(source, 0, 0, 0.0);
		sourceLabel.buildSequence({});
		labels.at(source).push_back(sourceLabel);

		//ITERATIONS
		bool termination = false;

		while (termination != true) {

			termination = true;

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

				int idV = this->sourcesToConsider.at(i);
				const Vertex* v = &this->vertices.at(idV);
				/*if (isToprint) {
					cout << v->toString(false) << "\n\tPOS " << i << endl;
				}*/

				for (list<Label>::iterator label = labels.at(idV).begin(); label != labels.at(idV).end(); label++) {

					if (!label->getIsExtended() && label->getLength() < this->cyclesLength) {

						/*if (isToprint) {
							cout << "LABEL\n" << label->toString() << endl;
						}*/

						//for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
						for (int j = 0; j < this->outgoingArcsToConsider.at(idV).size(); j++) {

							int idW = this->outgoingArcsToConsider.at(idV).at(j);
							const Vertex* w = &this->vertices.at(idW);

							/*if (isToprint) {
								cout << "TO REACH\n" << w->toString(false) << endl;
							}*/

							double redCost = label->getCost() + this->dualPrices.at(idV).at(idW);
							Label extension(idW, label->getLength() + 1, label->getWeight() + v->getOutGoingArcs().at(idW), redCost);
							//extension.buildNgMemory(label->getNgMemory(), w->getNgSet(), w->getWord(), w->getBitKey());

							//CHECK DOMINANCE+INSERT IN LIST
							bool isInserted = dominationAndInsertion_cycles(labels.at(idW), *label, extension);
							/*if (isToprint) {
								cout << extension.toString() << endl;
								cout << "\nISINSERTED " << isInserted << endl;
							}*/
							if (isInserted) {
								if (w->getId() == source && ::strictly_less(extension.getCost(), this->valuePerPricing) && extension.getLength() > 1) {
									this->optimalLabel_cycles = extension;
									this->valuePerPricing = extension.getCost();
									return labels;
								}
								termination = false;
							}

						}

					}

					label->setIsExtended(true);

				}

			}

		}

		/*if (isToprint) {
			for (int i = 0; i < labels.size(); i++) {
				cout << "\n\n\nLABELS OF " << i << "\n";
				for (list<Label>::const_iterator it = labels.at(i).begin(); it != labels.at(i).end(); it++) {
					cout << it->toString() << endl;
				}
			}
			cout << "VPP\t" << this->valuePerPricing << endl;
		}*/

		return labels;

	}
	catch (...) {
		cout << "[ExactGeneratorCycles] - Error during optimization" << endl;
	}

}

bool BellmanFord::dominationAndInsertion_cycles(list<Label>& labels, const Label& current, Label& extension) {

	if (labels.empty()) {
		extension.buildSequence(current.getSequence());
		labels.push_back(extension);
		return true;
	}

	//if the list is not empty iterate over the list to eventually check the insertion and the dominance
	list<Label>::iterator it = labels.begin();
	int comparison;

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = it->dominates_relaxed(extension))) {
		if (comparison == 2) {
			return false;
		}
		++it;
	}

	//until the cost of the current label is smaller than the candidate
	while (it != labels.end() && (comparison = it->equal_relaxed(extension))) {
		//labels are equal
		if (comparison == 2) {
			return false;
		}

		//candidate is dominated
		if (it->dominates_relaxed(extension) == 2) {
			return false;
		}

		//considered label dominance check
		if (extension.dominates_relaxed(*it) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	extension.buildSequence(current.getSequence());
	labels.insert(it, extension);

	while (it != labels.end()) {

		//considered label dominance check
		if (extension.dominates_relaxed(*it) == 2) {
			it = labels.erase(it);
		}
		else {
			++it;
		}

	}

	return true;

}

list<Label> BellmanFord::BellmanFord_cycles(const int& source, const int& maxLength, const vector<vector<int>>& arcs) {

	//preprocessing arcs
	//vector<vector<int>> arcs(this->vertices.size(), vector<int>());
	double best_dual_price = ::OMEGA;
	for (unordered_set<int>::const_iterator it = this->nodesPerPairToProcess.at(source).begin(); it != this->nodesPerPairToProcess.at(source).end(); it++) {
		for (int j = 0; j < arcs.at(*it).size(); j++) {
			best_dual_price = min(best_dual_price, this->dualPrices.at(*it).at(arcs.at(*it).at(j)));
		}
	}
	/*for (unordered_set<int>::const_iterator it = this->nodesPerPairToProcess.at(source).begin(); it != this->nodesPerPairToProcess.at(source).end(); it++) {
		for (int j = 0; j < this->outgoingArcsToConsider.at(*it).size(); j++) {
			int dest = this->outgoingArcsToConsider.at(*it).at(j);
			if (this->nodesPerPairToProcess.at(source).find(dest) != this->nodesPerPairToProcess.at(source).end()) {
				arcs.at(*it).push_back(dest);
				best_dual_price = min(best_dual_price, this->dualPrices.at(*it).at(dest));
			}
		}
	}*/

	//initialisation
	vector<vector<double>> weights(maxLength, vector<double>(this->vertices.size(), ::OMEGA));
	weights.at(0).at(source) = 0;
	vector<unordered_set<int>> vertexLists(maxLength, unordered_set<int>());
	vertexLists.at(0).insert(source);
	vector<vector<vector<int>>> walks(maxLength, vector<vector<int>>(this->vertices.size(), vector<int>()));
	walks.at(0).at(source).push_back(source);

	list<Label> negativeReducedCostPaths;

	//iterations
	for (int k = 1; k < maxLength; k++) {
		int previous = k - 1;
		for (unordered_set<int>::const_iterator it = vertexLists.at(previous).begin(); it != vertexLists.at(previous).end(); it++) {
			int id = *it;

			//completion bound
			double currentWeight = weights.at(previous).at(id);
			if (currentWeight + (this->cyclesLength - k) * best_dual_price < -EPSILON) {

				for (int j = 0; j < arcs.at(id).size(); j++) {
					int dest = arcs.at(id).at(j);
					double newCost = currentWeight + this->dualPrices.at(id).at(dest);
					if (::strictly_less(newCost, weights.at(k).at(dest))) {
						weights.at(k).at(dest) = newCost;
						vertexLists.at(k).insert(dest);
						walks.at(k).at(dest) = walks.at(k - 1).at(id);
						walks.at(k).at(dest).push_back(dest);
						if (newCost < -EPSILON && dest == source) {

							int weight = 0;
							for (int i = 0; i < walks.at(k).at(dest).size() - 1; i++) {
								int id1 = walks.at(k).at(dest).at(i);
								int id2 = walks.at(k).at(dest).at(i + 1);
								const Vertex* v = &this->vertices.at(id1);
								weight += v->getOutGoingArcs().at(id2);
							}
							Label extension(source, walks.at(k).at(dest).size() - 1, weight, newCost);
							extension.setSequence(walks.at(k).at(dest));
							//cout << extension.toString() << endl;
							negativeReducedCostPaths.push_back(extension);
							if (::strictly_less(newCost, this->valuePerPricing)) {
								this->valuePerPricing = newCost;
								this->optimalLabel_cycles = extension;
							}

							this->is_early_terminated = true;
							return negativeReducedCostPaths;
							this->favourablyPricedVariablesCounter++;
							if (this->favourablyPricedVariablesCounter > ::PROMISINGLABELSPERITERATION) {
								this->is_early_terminated = true;
								negativeReducedCostPaths.sort();
								return negativeReducedCostPaths;
							}

						}
					}
				}

			}

		}

	}

	negativeReducedCostPaths.sort();
	return negativeReducedCostPaths;

}

void BellmanFord::buildDualPrices_cycles() {
	this->dualPrices = vector<vector<double>>(this->instance.getVertexNumber(), vector<double>(this->instance.getVertexNumber(), 0.0));
	this->verticesToConsider = vector<int>(this->instance.getVertexNumber(), 1);
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
			this->dualPrices.at(v->getId()).at(arc->first) -= arc->second;
			this->dualPrices.at(v->getId()).at(arc->first) += this->dual_variables->get_pi_i(arc->first);
			if (v->getType() == 'D') {
				this->dualPrices.at(v->getId()).at(arc->first) += this->dual_variables->get_beta();
			}
		}
	}
	for (int i = 0; i < this->branching_constraints->size(); i++) {
		int rhs = this->branching_constraints->at(i)->get_rhs();
		double dual = ::OMEGA;
		if (rhs > 0) {
			dual = this->dual_variables->get_gamma_i(i);
		}
		if (this->branching_constraints->at(i)->get_name() == "ARCBRANCH") {
			int id1 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().first;
			int id2 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().second;
			this->dualPrices.at(id1).at(id2) += dual;
		}
		else if (this->branching_constraints->at(i)->get_name() == "VISITBRANCH") {
			int id = dynamic_cast<VisitBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_item();
			/*if (::isToPrint) {
				cout << "DUAL " << id << "\t" << this->dual_variables->get_gamma_i(i) << endl;
			}*/
			if (rhs == 0) {
				this->verticesToConsider.at(id) = 0;
			}
			for (int j = 0; j < this->instance.getVertexNumber(); j++) {
				this->dualPrices.at(j).at(id) += dual;
			}
		}
		else if (this->branching_constraints->at(i)->get_name() == "EXCHANGENUMBERBRANCH") {
			/*if (::isToPrint) {
				cout << "DUAL " << this->dual_variables->get_gamma_i(i) << endl;
			}*/
			for (int j = 1; j < this->instance.getVertexNumber(); j++) {
				this->dualPrices.at(0).at(j) += dual;
			}
		}
	}
	/*cout << "DUAL PRICIES \n";
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
			if (this->dualPrices.at(v->getId()).at(arc->first) != 0.0) {
				cout << "\t" << v->getId() << "\t" << arc->first << "\t" << arc->second << "\t" << this->dualPrices.at(v->getId()).at(arc->first) << endl;
			}
		}
	}
	cout << "\n";*/
}

void BellmanFord::addExchanges_cycles(const Label& label) {
	Exchange exchange("cycle", label.getWeight(), label.getLength(), label.getSequence(), this->instance.getVertexNumber());
	//cout << exchange.toString() << endl;
	/*if (::isToPrint) {

	}*/
	/*if (::isToPrint && !check_labels_reduced_cost(label, exchange)) {
		cout << "stop\n";
	}*/
	this->solution_pool.push_back(exchange);
}

void BellmanFord::buildVertices_chains() {
	this->verticesToConsider.clear();
	this->outgoingArcsToConsider.clear();
	vector<vector<bool>> arcsToDiscard(this->instance.getVertexNumber(), vector<bool>(this->instance.getVertexNumber(), false));
	vector<bool> verticesToDiscard(this->instance.getVertexNumber(), false);
	//cout << "ARCS DISCARDER:\n";
	for (int i = 0; i < this->branching_constraints->size(); i++) {
		if (this->branching_constraints->at(i)->get_name() == "ARCBRANCH" && this->branching_constraints->at(i)->get_rhs() == 0) {
			int id1 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().first;
			int id2 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().second;
			arcsToDiscard.at(id1).at(id2) = true;
			/*if (::isToPrint) {
				cout << "ARC DISCARDED " << id1 << "\t" << id2 << endl;
			}*/
		}
		if (this->branching_constraints->at(i)->get_name() == "VISITBRANCH" && this->branching_constraints->at(i)->get_rhs() == 0) {
			int id = dynamic_cast<VisitBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_item();
			verticesToDiscard.at(id) = true;
			/*if (::isToPrint) {
				cout << "VERTEX DISCARDED " << id << endl;
			}*/
		}
	}
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		if (!verticesToDiscard.at(v->getId())) {
			this->verticesToConsider.push_back(v->getId());
			vector<int> outgoing;
			/*Vertex newVertex = Vertex(*v);
			for (unordered_map<int, int>::const_iterator arc = v->getInGoingArcs().begin(); arc != v->getInGoingArcs().end(); arc++) {
				if (arcsToDiscard.at(arc->first).at(v->getId()) || verticesToDiscard.at(arc->first)) {
					newVertex.removeInGoingArc(arc->first);
				}
			}*/
			for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
				if (!arcsToDiscard.at(v->getId()).at(arc->first) && !verticesToDiscard.at(arc->first)) {
					outgoing.push_back(arc->first);
				}
			}
			this->outgoingArcsToConsider.push_back(outgoing);
		}
	}
}

void BellmanFord::buildActiveNonRobustCuts_chains() {
	this->active_non_robust_cuts.clear();
	this->active_non_robust_duals.clear();
	for (int i = 0; i < this->cut_constraints->size(); i++) {
		if (this->dual_variables->get_sigma_i(i) > ::EPSILON) {
			this->active_non_robust_cuts.push_back(i);
			this->active_non_robust_duals.push_back(this->dual_variables->get_sigma_i(i));
		}
	}
}

void BellmanFord::buildDualPrices_chains() {
	this->dualPrices = vector<vector<double>>(this->instance.getVertexNumber(), vector<double>(this->instance.getVertexNumber(), 0.0));
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
			this->dualPrices.at(v->getId()).at(arc->first) -= arc->second;
			this->dualPrices.at(v->getId()).at(arc->first) += this->dual_variables->get_pi_i(arc->first);
			if (v->getType() == 'D') {
				this->dualPrices.at(v->getId()).at(arc->first) += this->dual_variables->get_beta();
			}
		}
	}
	for (int i = 0; i < this->branching_constraints->size(); i++) {
		if (this->branching_constraints->at(i)->get_name() == "ARCBRANCH") {
			int id1 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().first;
			int id2 = dynamic_cast<ArcBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_items().second;
			this->dualPrices.at(id1).at(id2) += this->dual_variables->get_gamma_i(i);
		}
		else if (this->branching_constraints->at(i)->get_name() == "VISITBRANCH") {
			int id = dynamic_cast<VisitBranchConstraint<GRBConstr>*>(this->branching_constraints->at(i))->get_item();
			/*if (::isToPrint) {
				cout << "DUAL " << id << "\t" << this->dual_variables->get_gamma_i(i) << endl;
			}*/
			for (int j = 0; j < this->instance.getVertexNumber(); j++) {
				this->dualPrices.at(j).at(id) += this->dual_variables->get_gamma_i(i);
			}
		}
		else if (this->branching_constraints->at(i)->get_name() == "EXCHANGENUMBERBRANCH") {
			/*if (::isToPrint) {
				cout << "DUAL " << this->dual_variables->get_gamma_i(i) << endl;
			}*/
			for (int j = 1; j < this->instance.getVertexNumber(); j++) {
				this->dualPrices.at(0).at(j) += this->dual_variables->get_gamma_i(i);
			}
		}
	}
	/*cout << "DUAL PRICIES \n";
	for (int i = 0; i < this->instance.getVertexNumber(); i++) {
		const Vertex* v = &this->instance.getVertices().at(i);
		for (unordered_map<int, int>::const_iterator arc = v->getOutGoingArcs().begin(); arc != v->getOutGoingArcs().end(); arc++) {
			if (this->dualPrices.at(v->getId()).at(arc->first) != 0.0) {
				cout << "\t" << v->getId() << "\t" << arc->first << "\t" << arc->second << "\t" << this->dualPrices.at(v->getId()).at(arc->first) << endl;
			}
		}
	}*/
}

list<Label> BellmanFord::BellmanFord_chains() {

	int chainLengthBF = this->chainsLength + 1;
	vector<vector<double>> weights(chainLengthBF, vector<double>(this->vertices.size(), ::OMEGA));
	weights.at(0).at(source) = 0;
	vector<unordered_set<int>> vertexLists(chainLengthBF, unordered_set<int>());
	vertexLists.at(0).insert(source);
	vector<vector<vector<int>>> walks(chainLengthBF, vector<vector<int>>(this->vertices.size(), vector<int>()));
	walks.at(0).at(source).push_back(source);

	list<Label> negativeReducedCostPaths;

	for (int k = 1; k < chainLengthBF; k++) {
		int previous = k - 1;
		for (unordered_set<int>::const_iterator it = vertexLists.at(previous).begin(); it != vertexLists.at(previous).end(); it++) {
			int id = *it;
			for (int j = 0; j < this->outgoingArcsToConsider.at(id).size(); j++) {
				int dest = this->outgoingArcsToConsider.at(id).at(j);
				double newCost = weights.at(previous).at(id) + this->dualPrices.at(id).at(dest);
				if (::strictly_less(newCost, weights.at(k).at(dest))) {
					weights.at(k).at(dest) = newCost;
					vertexLists.at(k).insert(dest);
					walks.at(k).at(dest) = walks.at(k - 1).at(id);
					walks.at(k).at(dest).push_back(dest);
					if (newCost < -EPSILON) {

						int weight = 0;
						for (int i = 0; i < walks.at(k).at(dest).size() - 1; i++) {
							int id1 = walks.at(k).at(dest).at(i);
							int id2 = walks.at(k).at(dest).at(i + 1);
							const Vertex* v = &this->vertices.at(id1);
							weight += v->getOutGoingArcs().at(id2);
						}
						Label extension(dest, walks.at(k).at(dest).size() - 1, weight, newCost);
						extension.setSequence(walks.at(k).at(dest));
						//cout << extension.toString() << endl;
						negativeReducedCostPaths.push_back(extension);
						if (::strictly_less(newCost, this->value_chains)) {
							this->value_chains = newCost;
							this->optimalLabel_chains = extension;
						}

						//return negativeReducedCostPaths;

						this->favourablyPricedVariablesCounter++;
						if (this->favourablyPricedVariablesCounter > ::PROMISINGLABELSPERITERATION) {
							this->is_early_terminated = true;
							negativeReducedCostPaths.sort();
							return negativeReducedCostPaths;
						}

					}
				}
			}

		}

	}

	negativeReducedCostPaths.sort();
	return negativeReducedCostPaths;

}

void BellmanFord::addExchanges_chains(const Label& label, const bool& areSubpathsAdded) {
	Exchange exchange("chain", label.getWeight(), label.getLength(), label.getSequence(), this->instance.getVertexNumber());
	//cout << exchange.toString() << endl;
	/*if (::isToPrint) {

	}*/
	/*if (::isToPrint && !check_labels_reduced_cost(label, exchange)) {
		cout << "stop\n";
	}*/
	this->solution_pool.push_back(exchange);
	if (areSubpathsAdded) {
		for (int i = 3; i < label.getSequence().size(); i++) {
			vector<int> subSequence;
			int weight = 0;
			int length = 0;
			for (int j = 0; j < i; j++) {
				subSequence.push_back(label.getSequence().at(j));
			}
			for (int j = 0; j < subSequence.size() - 1; j++) {
				length++;
				weight += this->vertices.at(subSequence.at(j)).getOutGoingArcs().at(subSequence.at(j + 1));
			}
			Exchange subExchange("chain", weight, length, subSequence, this->instance.getVertexNumber());
			//cout << subExchange.toString() << endl;
			this->solution_pool.push_back(subExchange);
		}
	}
}