/*****************************************************************//**
 * \file   ExactGenerator.h
 * \brief  Defines our dynamic programming algorithm that solves our pricing subproblem.
 *
 * \author Matteo Petris
 * \date   February 2023
 *********************************************************************/
#ifndef ExactGeneratorCyclesChains_H
#define ExactGeneratorCyclesChains_H


#include "PricingSubProblemAlgorithmAbstract.h"
#include "PricingProblem.h"
#include "Label.h"
#include "ArcBranchConstraint.h"
#include "VisitBranchConstraint.h"
#include "SubsetRowConstraint.h"

 /**
  * \class ExactGenerator.
  * \brief  Defines our dynamic programming algorithm that solves our pricing subproblem.
  */
class ExactGeneratorCyclesChains :
	public PricingSubProblemAlgorithmAbstract<Instance, vector<Exchange>, DualSolution, GRBConstr> {

protected:

	//CYCLES
	const vector<Vertex>& vertices;
	vector<int> sourcesToConsider;
	vector<int> verticesToConsider;
	vector<vector<int>> outgoingArcsToConsider;
	int cyclesLength;
	int wordsNumber;
	vector<vector<double>> dualPrices;
	vector<int> active_non_robust_cuts;
	vector<double> active_non_robust_duals;
	unordered_set<int> tabuList;
	bool areCyclesToPrice;
	double dual_exchange_number_branch;

	//CHAINS
	int source;
	int chainsLength;
	bool isOneNegativeChainElementary;
	bool areChainsToPrice;

	double best_dual_price;			//used as completion bound only if there are no non-robust inequalities

	/**********************************************
	**			Solution Related to the dynamic programming
	***********************************************/
	double time;
	double valuePerPricing;
	Label optimalLabel;
	Label optimalLabel_cycles;
	Label optimalLabel_chains;
	vector<Exchange> solution_pool;
	double value_chains;
	double value_cycles;
	vector<int> pairsAsSourcesToConsider;
	vector<unordered_set<int>> nodesPerPairToProcess;

public:

	/**
	 * Constructor with pricing problem.
	 *
	 * \param instance: Instance&
	 * \param dual_variables: DualSolution*
	 */
	ExactGeneratorCyclesChains(Instance& instance, DualSolution* dual_variables, vector<Exchange>* rmp_columns, vector<Constraint<GRBConstr>*>* branching_constraints, vector<Constraint<GRBConstr>*>* cut_constraints);

	/**
	 * \brief Destructor.
	 *
	 */
	~ExactGeneratorCyclesChains();

	/**
	* \brief Evaluates if the handler (the algorithm) can handle (solve) the pricing sub-problem based on the code of request.
	*
	* \param request : string
	* \return True if the concrete algorithm can solve the pricing sub-problem, false otherwise.
	*/
	bool can_solve(const string& request) const override;

	/**
	 * Checks and updates failed_to_find_favorably_priced_columns after solving the pricing subproblem.
	 * \details If no negative reduced cost found, then it updates failed_to_find_favorably_priced_columns with true.
	 *
	 */
	void update_failed_to_find_favorably_priced_columns() override;

	/**
	 * Solves the pricing subproblem with dynamic programming with the request "DYNAMICPROGRAMMING".
	 *
	 * \param request: const string&
	 */
	vector<Exchange> solve(const string& request, const double time_limit) override;

	/*CYCLES*/
	void buildDualPrices_cycles();
	void buildVertices_cycles();
	void buildActiveNonRobustCuts();

	list<Label> BellmanFord_cycles(const int& source, const int& maxLength, const vector<vector<int>>& arcs);

	vector<list<Label>> extendForward_non_robust_cycles(const int& source, const unordered_set<int>& nodes, const vector<vector<int>>& arcs);
	void manage_extension_non_robust_cuts_cycles(Label& extension, const int& vertex_id, const int& vertex_word, const int& vertex_bit);
	bool dominationAndInsertion_non_robust_cycles(list<Label>& labels, const Label& current, Label& extension);

	void addExchanges_cycles(const Label& label);

	/*CHAINS*/
	void buildDualPrices_chains();
	void buildVertices_chains();
	void compute_best_dual_price();

	list<Label> BellmanFord_chains();

	vector<list<Label>> extendForward_chains();
	bool dominationAndInsertion_chains(list<Label>& labels, const Label& current, Label& extension);

	vector<list<Label>> extendForward_non_robust_chains();
	void manage_extension_non_robust_cuts_chains(Label& extension, const int& vertex_id, const int& vertex_word, const int& vertex_bit);
	bool dominationAndInsertion_non_robust_chains(list<Label>& labels, const Label& current, Label& extension);

	void addExchanges_chains(const Label& label, const bool& areSubpathsAdded);


	vector<list<Label>> extendForward(const int& source);
	bool dominationAndInsertion(list<Label>& labels, const Label& current, Label& extension);

	double priceVariable(const Exchange* exchange);

	double add_sri_dual_prices(const Label& label) const;


};

#endif // !ExactGeneratorCyclesChains_H
