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


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

 /**
  * \class ExactGenerator.
  * \brief  Defines our dynamic programming algorithm that solves our pricing subproblem.
  */
class BellmanFord :
	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;

	//CHAINS
	int source;
	int chainsLength;

	/**********************************************
	**			Solution Related to the dynamic programming
	***********************************************/
	double time;
	double valuePerPricing;
	Label optimalLabel;
	Label optimalLabel_chains;
	Label optimalLabel_cycles;
	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*
	 */
	BellmanFord(Instance& instance, DualSolution* dual_variables, vector<Exchange>* rmp_columns, vector<Constraint<GRBConstr>*>* branching_constraints, vector<Constraint<GRBConstr>*>* cut_constraints);

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

	/**
	* \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_cycles();

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

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

	void addExchanges_cycles(const Label& label);

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

	list<Label> BellmanFord_chains();

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

};

#endif // !BELLMANFORD_H
