/*Header file of the PStep_ShortestPathAlgorithm class

Implementation of PStep_LayeredLabelingAlgorithm can be found in PStep_LayeredLabelingAlgorithm.cpp
Implementation of PStep_DoubleLayeredLabelingAlgorithm can be found in PStep_DoubleLayeredLabelingAlgorithm.cpp
Implementation of PStep_BiDirectionalLayeredLabelingAlgorithm can be found in PStep_BiDirectionalLayeredLabelingAlgorithm.cpp
Implementation of PStep_CompleteBiDirectionalLayeredLabeling can be found in PStep_CompleteBiDirectionalLayeredLabeling.cpp
Implementation of PStep_BiDirectionalLayeredLabelingWithCompletionBounds can be found in PStep_BiDirectionalLayeredLabelingWithCompletionBounds.cpp
Implementation of PStep_LocalSearchFixedArcs can be found in PStep_LocalSearchFixedArcs.cpp
Implementation of PStep_LocalSearchVaryingArcs can be found in PStep_LocalSearchVaringArcs.cpp

This class represents an algorithm to solve a shortest path problem as encountered as a pricing problem
when solving the CVRP using a p-step formulation.

This file also includes derived classes of PStep_ShortestPathAlgorithm.

*/

#ifndef _PSTEP_SHORTESTPATHALGORITHM_H
#define _PSTEP_SHORTESTPATHALGORITHM_H

#include "PStep_Extender.h"
#include "PStep_Dominator.h"
#include "PStep_Merger.h"
#include "PStep_PricingProblem.h"

//Class used to represent an algorithm to solve a shortest path problem as encountered as a pricing problem
//when solving the CVRP using a p-step formulation.
class PStep_ShortestPathAlgorithm{
public:

	//Pricing problem
	PStep_PricingProblem& PricingProblem;

	//Constructor functions
	//------------------------------------------------------------------------------------

	//Basic constructor
	PStep_ShortestPathAlgorithm(PStep_PricingProblem& NewPricingProblem)
		: PricingProblem(NewPricingProblem)
	{};

	//Solve the shortest path problem
	//------------------------------------------------------------------------------------
	void virtual Run(){};

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Class used to represent an algorithm to solve a shortest path problem as encountered as a pricing problem
//when solving the CVRP using a p-step formulation.
//The shortest path problem is solved using a labeling algorithm.
//In this labeling algorithm, dominance is only applied between labels that have the same end node
//and have visited exactly the same amount of locations.
//Labels, final and otherwise, are stored in PricingProblem.
class PStep_LayeredLabelingAlgorithm : public PStep_ShortestPathAlgorithm{
public:

	//Extenders:
	//Extender for normal use
	PStep_Extender& Extender;
	//Extender to the sink node
	PStep_FinalExtender& ExtenderToSink;

	//Dominator:
	PStep_Dominator& Dominator;

	//Indicator indicating whether a limited set of arcs should be used
	bool UseLimitedArcs;

	//Reference to a list that stores pointers to all solved pricing problems
	std::forward_list<PStep_PricingProblem*> &SolvedPricingProblems;

	//Constructor functions
	//------------------------------------------------------------------------------------

	//Basic constructor
	PStep_LayeredLabelingAlgorithm(PStep_PricingProblem& NewPricingProblem, PStep_Extender& NewExtender, PStep_FinalExtender& NewExtenderToSink, PStep_Dominator& NewDominator, bool NewUseLimitedArcs, std::forward_list<PStep_PricingProblem*> &NewSolvedPricingProblems)
		: PStep_ShortestPathAlgorithm(NewPricingProblem), Extender(NewExtender), ExtenderToSink(NewExtenderToSink), Dominator(NewDominator), UseLimitedArcs(NewUseLimitedArcs), SolvedPricingProblems(NewSolvedPricingProblems)
	{};
		
	//Solve the shortest path problem
	//------------------------------------------------------------------------------------

	//The shortest path problem is solved using a labeling algorithm.
	//In this labeling algorithm, dominance is only applied between labels that have the same end node
	//and have visited exactly the same amount of locations.
	//Labels, final and otherwise, are stored in PricingProblem.
	void virtual Run();

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Class used to represent an algorithm to solve a shortest path problem as encountered as a pricing problem
//when solving the CVRP using a p-step formulation.
//The shortest path problem is solved using a labeling algorithm.
//In this labeling algorithm, dominance is only applied between labels that have the same end node,
//the same load and have visited exactly the same amount of locations.
//Labels, final and otherwise, are stored in PricingProblem.
class PStep_DoubleLayeredLabelingAlgorithm : public PStep_LayeredLabelingAlgorithm{
public:

	//Constructor functions
	//------------------------------------------------------------------------------------

	//Basic constructor
	PStep_DoubleLayeredLabelingAlgorithm(PStep_PricingProblem& NewPricingProblem, PStep_Extender& NewExtender, PStep_FinalExtender& NewExtenderToSink, PStep_Dominator& NewDominator, bool NewUseLimitedArcs, std::forward_list<PStep_PricingProblem*> &NewSolvedPricingProblems)
		: PStep_LayeredLabelingAlgorithm(NewPricingProblem, NewExtender, NewExtenderToSink, NewDominator, NewUseLimitedArcs, NewSolvedPricingProblems)
	{};

	//Solve the shortest path problem
	//------------------------------------------------------------------------------------

	//The shortest path problem is solved using a labeling algorithm.
	//In this labeling algorithm, dominance is only applied between labels that have the same end node,
	//the same load and have visited exactly the same amount of locations.
	//Labels, final and otherwise, are stored in PricingProblem.
	void virtual Run();

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Class used to represent an algorithm to solve a shortest path problem as encountered as a pricing problem
//when solving the CVRP using a p-step formulation.
//The shortest path problem is solved using a bi-directional labeling algorithm.
//In this labeling algorithm, dominance is only applied between labels that have the same end node
//and have visited exactly the same amount of locations.
//Labels, MergeLabels and otherwise, are stored in PricingProblem.
class PStep_BiDirectionalLayeredLabelingAlgorithm : public PStep_LayeredLabelingAlgorithm{
public:

	//Merger:
	PStep_Merger &Merger;

	//The maximum number of merge labels.
	//The algorithm terminates after creating the first MaxNumberOfMergeLabels MergeLabels.
	int MaxMergeLabels;

	//Constructor functions
	//------------------------------------------------------------------------------------

	//Basic constructor
	//ADDED ON 2020-02-05: PStep_FinalExtender as input, because the compiler was complaining
	//					about PStep_FinalExtender(0, 0, 0) in the base class constructor.
	PStep_BiDirectionalLayeredLabelingAlgorithm(PStep_PricingProblem& NewPricingProblem, PStep_Extender& NewExtender, PStep_FinalExtender& NewFinalExtender, PStep_Dominator& NewDominator, PStep_Merger &NewMerger, bool NewUseLimitedArcs, int NewMaxMergeLabels, std::forward_list<PStep_PricingProblem*> &NewSolvedPricingProblems)
		: PStep_LayeredLabelingAlgorithm(NewPricingProblem, NewExtender, NewFinalExtender, NewDominator, NewUseLimitedArcs, NewSolvedPricingProblems), Merger(NewMerger), MaxMergeLabels(NewMaxMergeLabels)
	{};

	//Solve the shortest path problem
	//------------------------------------------------------------------------------------

	//The shortest path problem is solved using a bi-directional labeling algorithm.
	//In this labeling algorithm, dominance is only applied between labels that have the same end node
	//and have visited exactly the same amount of locations.
	//Labels, MergeLabels and otherwise, are stored in PricingProblem.
	void virtual Run();

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Class used to represent an algorithm to continue forward and backward labeling to make 
//a complete forward and backward pass, after having run the bi-directional layered labeling
//algorithm. As such, Labels should not be altered before running this algorithm.
//It makes use of (the second half of the) completion bounds.
//In this labeling algorithm, dominance is only applied between labels that have the same end node
//and have visited exactly the same amount of locations.
//Labels are stored in PricingProblem.
class PStep_CompleteBiDirectionalLayeredLabeling : public PStep_LayeredLabelingAlgorithm{
public:

	//Constructor functions
	//------------------------------------------------------------------------------------

	//Basic constructor
	//ADDED ON 2020-02-05: PStep_FinalExtender as input, because the compiler was complaining
	//					   about PStep_FinalExtender(0, 0, 0) in the base class constructor.
	//ADDED ON 2020-02-05: std::forward_list<PStep_PricingProblem*> as input, because the compiler was complaining
	//					   about std::forward_list<PStep_PricingProblem*>() in the base class constructor.
	PStep_CompleteBiDirectionalLayeredLabeling(PStep_PricingProblem& NewPricingProblem, PStep_Extender& NewExtender, PStep_FinalExtender& NewFinalExtender, PStep_Dominator& NewDominator, bool NewUseLimitedArcs, std::forward_list<PStep_PricingProblem*>& NewSolvedPricingProblems)
		:  PStep_LayeredLabelingAlgorithm(NewPricingProblem, NewExtender, NewFinalExtender, NewDominator, NewUseLimitedArcs, NewSolvedPricingProblems)
	{};

	//Continue labeling
	//------------------------------------------------------------------------------------

	//Continue forward and backward labeling to make a complete forward and backward pass,
	//after having run the bi-directional layered labeling algorithm. As such, Labels should
	//not be altered before running this algorithm. It makes use of (the second half of the)
	//completion bounds. In this labeling algorithm, dominance is only applied between labels
	//that have the same end node and have visited exactly the same amount of locations.
	//Labels are stored in PricingProblem.
	void virtual Run();

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Class used to represent an algorithm to solve a shortest path problem as encountered as a pricing problem
//when solving the CVRP using a p-step formulation.
//The shortest path problem is solved using a bi-directional labeling algorithm while making use of completion bounds.
//In this labeling algorithm, dominance is only applied between labels that have the same end node
//and have visited exactly the same amount of locations.
//Labels, MergeLabels and otherwise, are stored in PricingProblem.
class PStep_BiDirectionalLayeredLabelingWithCompletionBounds : public PStep_BiDirectionalLayeredLabelingAlgorithm{
public:

	//Constructor functions
	//------------------------------------------------------------------------------------

	//Basic constructor
	//ADDED ON 2020-02-05: PStep_FinalExtender as input, because the compiler was complaining
	//					about PStep_FinalExtender(0, 0, 0) in the base class constructor.
	PStep_BiDirectionalLayeredLabelingWithCompletionBounds(PStep_PricingProblem& NewPricingProblem, PStep_Extender& NewExtender, PStep_FinalExtender& NewFinalExtender, PStep_Dominator& NewDominator, PStep_Merger &NewMerger, bool NewUseLimitedArcs, int NewMaxMergeLabels, std::forward_list<PStep_PricingProblem*> &NewSolvedPricingProblems)
		: PStep_BiDirectionalLayeredLabelingAlgorithm(NewPricingProblem, NewExtender, NewFinalExtender, NewDominator, NewMerger, NewUseLimitedArcs, NewMaxMergeLabels, NewSolvedPricingProblems)
	{};

	//Solve the shortest path problem
	//------------------------------------------------------------------------------------

	//The shortest path problem is solved using a bi-directional labeling algorithm while making use of completion bounds.
	//In this labeling algorithm, dominance is only applied between labels that have the same end node
	//and have visited exactly the same amount of locations.
	//Labels, MergeLabels and otherwise, are stored in PricingProblem.
	void virtual Run();

};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Class used to represent an algorithm to solve a shortest path problem as encountered as a pricing problem
//when solving the CVRP using a p-step formulation.
//The shortest path problem is solved using a local search algorithm.
//It applies in case a p-step is created which does not start at the depot.
//All identified p-steps with nonegative reduced costs are stored in the forward list CandidatePSteps in PricingProblem.
class PStep_LocalSearchFixedArcs : public PStep_ShortestPathAlgorithm{
public:

	//Indicator indicating whether an initial p-step is provided.
	//If an initial solution is provided, it should be stored as CurrentPStep
	//and CurrentReducedCost and CurrentDemand should be set accordingly
	bool InitialPStepProvided;

	//Current Solution members:
	//Current p-step
	PStep CurrentPStep;
	//Current reduced costs
	double CurrentReducedCosts;
	//Current demand
	double CurrentDemand;

	//Pricing problem solve members:
	//List of customers that are not in the current p-step.
	//The first customer is 1.
	std::vector<short int> OutsideCustomers;
	//DemandIncrease[i][j] gives the increase in demand when adding
	//customer i to the p-step and removing j from the p-step (Demand[i]-Demand[j]).
	//i=0 is the first customer.
	double** (&DemandIncrease);
	//Candidate p-steps, representing identified p-steps with nonegative reduced costs.
	std::forward_list<PStep>& CandidatePSteps;
	//Indicator indicating whether minimal (true) or maximal (false) starting load is used.
	bool MinimalStartingLoad;
	//Tolerance
	double Tolerance;
	//Pointer to travel costs
	//TravelCosts[i][j] are the traveling costs from i to j.
	//The index 0 provides the depot.
	double** (&TravelCosts);

	//Copies of information already included in PricingProblem, for easy reference:
	//Number of locations
	short int NumberOfLocations;
	//Pointer to array indicating which arcs are in use.
	//ArcInUse[i][j] indicates whether the arc from i to j is in use.
	//The index 0 refers to the depot.
	bool** ArcInUse;
	//Source and Sink, 0 is the depot
	short int Source;
	short int Sink;
	//Maximum number of arcs on a p-step
	//This is usually p but for depot-customer p-steps this could be less.
	short int MaxNumberOfArcs;
	//Demand
	//Demand[i] is the demand of customer i, i=0 is the first customer.
	double* Demand;
	//Capacity on the partial path
	double Capacity;
	//The capacity plus some numerical tolerance.
	double CapacityPlusTolerance;
	//Pointer to reachability of customers in this pricing problem.
	//Reachable[i]=true indicates customer i can be reached, i=0 is the first customer.
	bool* Reachable;
	//Reduced arc costs
	//ReducedArcCosts[PStep_Arc::StartNode][Pstep_Arc::EndNode] should correspond to the costs of PStep_Arc.
	double** ReducedArcCosts;
	//Reduced cost constant
	double ReducedCostConstant;

	//Reference to a list that stores pointers to all solved pricing problems
	std::forward_list<PStep_PricingProblem*> &SolvedPricingProblems;

	//Constructor functions
	//------------------------------------------------------------------------------------

	//Basic constructor
	PStep_LocalSearchFixedArcs(PStep_PricingProblem& NewPricingProblem, double** (&NewDemandIncrease), double** (&NewTravelCosts), bool NewMinimumStartingLoad, double NewTolerance, std::forward_list<PStep_PricingProblem*> &NewSolvedPricingProblems)
		: PStep_ShortestPathAlgorithm(NewPricingProblem), InitialPStepProvided(false), DemandIncrease(NewDemandIncrease), CandidatePSteps(NewPricingProblem.CandidatePSteps), TravelCosts(NewTravelCosts), MinimalStartingLoad(NewMinimumStartingLoad), Tolerance(NewTolerance), SolvedPricingProblems(NewSolvedPricingProblems)
	{
		//Copy information
		NumberOfLocations = PricingProblem.NumberOfLocations;
		ArcInUse = PricingProblem.CurrentTreeNodeArcIsRelevant;
		Source = PricingProblem.Source;
		Sink = PricingProblem.Sink;
		MaxNumberOfArcs = PricingProblem.MaxNumberOfArcs;
		Demand = PricingProblem.Demand;
		Capacity = PricingProblem.Capacity;
		CapacityPlusTolerance = Capacity + Tolerance;
		Reachable = PricingProblem.Reachable;
		ReducedArcCosts = PricingProblem.ReducedArcCosts;
		ReducedCostConstant = PricingProblem.ReducedCostConstant;
	};

	//Solve the shortest path problem
	//------------------------------------------------------------------------------------
	//Use local search algorithm to solve the pricing problem.
	//The number of arcs are fixed and elementarity is respected.
	//It applies in case a p-step is created which does not start at the depot.
	//All identified p-steps with nonegative reduced costs are stored in the forward list CandidatePSteps.
	//NOTE: For a pre-initialized p-step with 2 arcs, we do not attempt to improve it,
	//	    even though it might be possible to find an improvement. The function SwapDoublesCurrentPStep
	//		is available to facilitate initializing with a cyclic p-step.
	void virtual Run();

	//Local search functions
	//------------------------------------------------------------------------------------

	//Swap double customers from the current p-step.
	//For customers that are visited multiple times, the first is maintained and
	//the others are swapped.
	//The customers are swapped with the best location not in the current p-step.
	//It returns false if the current p-step could not be transformed into an elementary path.
	//In that case, the current p-step might be altered.
	bool SwapDoublesCurrentPStep();

	//Initialize OutsideCustomers
	//It puts all customers that are not in CurrentPStep in OutsideCustomers.
	void InitializeOutsideCustomers();

	//Generate an initial p-step from source to sink, inserting customers greedily until
	//MaxNumberOfArcs arcs are included.
	//It is assumed that CurrentPStep is empty.
	//The PStep is stored in CurrentPStep.
	//If no feasible PStep could be made, output false.
	bool GenerateGreedyPStep();

	//Find the best insert in CurrentPStep
	//The best location to insert from OutsideLocations will be stored in CurrentBestCustomer,
	//Location 0 is the depot and is never considered for insertion.
	//The best insert position is stored as the reference CurrentBestPosition to the next location in
	//CurrentPStep.
	//The best cost increase is stored in CurrentBestCostIncrease.
	//We aim for the lowest cost increase, ideally negative, i.e., a decrease.
	//If no feasible insert is found the function outputs false.
	bool Insert(std::vector<short int>::iterator& CurrentBestCustomer, std::list<short int>::iterator& CurrentBestPosition, double& CurrentBestCostIncrease);

	//Find the best swap between a customer in the current p-step and customers from OutsideLocations.
	//The start and end locations of the current p-step are never swapped.
	//The best customer to be removed is stored as an iterator, CurrentBestRemoveCustomer, pointing
	//to the customer in the list to be removed.
	//The best location to insert from OutsideLocations will be stored in CurrentBestInsertCustomer.
	//The best cost increase is stored in CurrentBestCostIncrease.
	//We aim for the lowest cost increase, ideally negative, i.e., a decrease.
	//If no feasible insert is found the function outputs false.
	//NOTE: It is assumed that the current p-step contains at least 3 locations.
	bool Swap(std::vector<short int>::iterator& CurrentBestInsertCustomer, std::list<short int>::iterator& CurrentBestRemoveCustomer, double& CurrentBestCostIncrease);

	//Find the best swap between two customers in the current p-step.
	//The start and end locations of the current p-step are never swapped.
	//The customers to be swapped are stored as iterators, CurrentBestFirstCustomer and
	//CurrentBestSecondCustomer, pointing to the customers in the list to be swapped.
	//The best cost increase is stored in CurrentBestCostIncrease.
	//We aim for the lowest cost increase, ideally negative, i.e., a decrease.
	//If no feasible insert is found the function outputs false.
	//NOTE: It is assumed that the current p-step contains at least 4 locations
	bool SwapIntraPStep(std::list<short int>::iterator& CurrentBestFirstCustomer, std::list<short int>::iterator& CurrentBestSecondCustomer, double& CurrentBestCostIncrease);

	//Set the cost, starting load and total load of a p-step for which the locations are already set.
	void SetCurrentPStepCostAndLoads();
};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Class used to represent an algorithm to solve a shortest path problem as encountered as a pricing problem
//when solving the CVRP using a p-step formulation.
//The shortest path problem is solved using a local search algorithm.
//It applies in case a p-step is created which starts at the depot.
//All identified p-steps with nonegative reduced costs are stored in the forward list CandidatePSteps in PricinProblem.
class PStep_LocalSearchVaryingArcs : public PStep_LocalSearchFixedArcs{
public:

	//Constructor functions
	//------------------------------------------------------------------------------------

	//Basic constructor
	PStep_LocalSearchVaryingArcs(PStep_PricingProblem& NewPricingProblem, double** (&NewDemandIncrease), double** (&NewTravelCosts), double NewTolerance, std::forward_list<PStep_PricingProblem*> &NewSolvedPricingProblems)
		: PStep_LocalSearchFixedArcs(NewPricingProblem, NewDemandIncrease, NewTravelCosts, true, NewTolerance, NewSolvedPricingProblems)
	{};

	//Solve the shortest path problem
	//------------------------------------------------------------------------------------
	//Use local search algorithm to solve the pricing problem.
	//The number of arcs can vary between 1 and a maximum number of arcs and elementarity is respected.
	//It applies in case a p-step is created which starts at the depot.
	//All identified p-steps with nonegative reduced costs are stored in the forward list CandidatePSteps.
	//NOTE:	The function RemoveDoublesCurrentPStep is available to facilitate initializing with a cyclic p-step.
	void virtual Run();

	//Local search functions
	//------------------------------------------------------------------------------------

	//Remove double customers from the current p-step.
	//For customers that are visited multiple times, the first is maintained and
	//the others are removed, unless a customer is visited as sink, in this case,
	//the sink is maintained and the others are removed.
	//It returns false if the current p-step could not be transformed into an elementary path.
	//In that case, the current p-step might be altered.
	bool RemoveDoublesCurrentPStep();

	//Find the best remove in CurrentPStep
	//The best removed customer is stored as the reference CurrentBestCustomer to CurrentPStep.Locations.
	//Location 0 is the depot and is never considered for removal, nor are the source and sink.
	//The best cost increase is stored in CurrentBestCostIncrease.
	//We aim for the lowest cost increase, ideally negative, i.e., a decrease.
	//If no feasible insert is found the function outputs false.
	//NOTE: It is assumed that the current p-step contains at least 3 locations.
	bool Remove(std::list<short int>::iterator& CurrentBestCustomer, double& CurrentBestCostIncrease);

};

#endif