/*Implementation of PStep_Brancher

It contains the member functions of PStep_LysgaardBrancher

*/

#include "PStep_Brancher.h"

//PStep_LysgaardBrancher:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

//Basic constructor
PStep_LysgaardBrancher::PStep_LysgaardBrancher(PStep_AlgorithmMembers& InitAlgorithmMembers)
	: PStep_Brancher(InitAlgorithmMembers), EdgeHead(NULL), EdgeTail(NULL), EdgeX(NULL)
{
	//Obtain number of locations
	short int NumberOfLocations = AlgorithmMembers.Instance.NumberOfCustomers + 1;
	//Obtain Demand
	double* Demand = AlgorithmMembers.Instance.Demand;

	//Obtain demand as required by Lysgaard
	//Lysgaard requires a 0 as first entry, and Demand[i] to correspond to customer i.
	//Also demand is required to be integer.
	LysgaardDemand = new int[NumberOfLocations];
	LysgaardDemand[0] = 0;
	for (short int i = 1; i<NumberOfLocations; i++){
		LysgaardDemand[i] = short int(Demand[i - 1]);
	}

}

//Branch on AlgorithmMembers.CurrentTreeNode. The current node is deleted
//from AlgorithmMembers.Nodes while the new node(s) are added to it.
//The Lysgaard package is used to select a single set of edges to branch on.
//A set of edges is selected of which the degree of the current selection is
//in between 2 and 4, and as close as possible to 
//AlgorithmMembers.AlgorithmSettings.LysgaardTarget.
void PStep_LysgaardBrancher::Branch(){

	//Prepare the selected edges
	SetCurrentEdges();

	//Initialize support variables
	short int NumberOfCustomers = AlgorithmMembers.Instance.NumberOfCustomers;
	short int NumberOfLocations = NumberOfCustomers + 1;
	std::vector < std::vector < PStep_Arc >> &Arcs = AlgorithmMembers.Arcs;
	//Obtain current tree node
	auto CurrentTreeNode = AlgorithmMembers.CurrentTreeNode;
	//Obtain last used node id
	int& LastUsedNodeID = AlgorithmMembers.LastUsedNodeID;
	//Obtain Nodes
	std::list<PStep_TreeNode>& Nodes = AlgorithmMembers.Nodes;

	//Initialize CnstrMgrPointer to contain the generated sets
	CnstrMgrPointer SetsCMP;
	CMGR_CreateCMgr(&SetsCMP, 1);
	
	//Generate a set to branch on
	BRNCHING_GetCandidateSets(NumberOfCustomers, LysgaardDemand, int(AlgorithmMembers.Instance.VehicleCapacity), NumberOfEdgesPlusOne - 1, EdgeTail, EdgeHead, EdgeX, AlgorithmMembers.LysgaardCuts, AlgorithmMembers.AlgorithmSettings.LysgaardTarget, 1, SetsCMP);
	
	//Obtain the set of customer to branch on:
	//----------------------------------------

	//Initialize indicators, indicating whether a location is in the set
	bool* LocationInSet = new bool[NumberOfLocations];
	for (int j = 0; j < NumberOfLocations; ++j){
		LocationInSet[j] = false;
	}

	//Obtain the set
	for (int j = 1; j <= SetsCMP->CPL[0]->IntListSize; ++j){
		//Obtain current location
		int k = SetsCMP->CPL[0]->IntList[j];
		if (k == NumberOfLocations){
			//Recode the depot
			k = 0;
		}
		//Add location the set
		LocationInSet[k] = true;
	}

	//Create list of locations that are in the set and not in the set
	std::list<short int> SelectedSet;
	std::list<short int> UnSelectedSet;
	//Go over all locations
	for (short int j = 0; j < NumberOfLocations; ++j){
		//Check whether the current location is in the Nucleus
		if (LocationInSet[j]){
			//Add the location to Set
			SelectedSet.push_back(j);
		}
		else{
			//Add the location to the Unselected list
			UnSelectedSet.push_back(j);
		}
	}

	//Transform the set of customers to branch on, into a set of edges to branch on on:
	//---------------------------------------------------------------------------------

	//Initialize list of edge indices
	std::list<short int> Indices;
	
	//Obtain edge indices of all edges between locations in and outside of the set
	//Go over all locations in the Set
	for (auto k = SelectedSet.begin(); k != SelectedSet.end(); ++k){
		//Go over all locations not in the Set
		for (auto j = UnSelectedSet.begin(); j != UnSelectedSet.end(); ++j){
			//Obtain the edge index of the corresponding edge and add it to the list
			Indices.push_back(Arcs[*k][*j].Index);
		}
	}

	//Branch on selected edges:
	//-----------------------------------------------------------------------

	//Restrict the sum of edge values to 2 in the left child, and bound them from below by 4 in the right child.

	//Create left child
	PStep_TreeNode LeftChild(*CurrentTreeNode);
	//Update left child
	++LastUsedNodeID;
	LeftChild.ID = LastUsedNodeID;
	LeftChild.Depth = CurrentTreeNode->Depth + 1;
	LeftChild.ParentID = CurrentTreeNode->ID;
	LeftChild.ParentLB = AlgorithmMembers.CurrentSolution.SolutionValue;
	//Create cut to set the sum of the edges to 2
	PStep_EdgeFlowCut LeftCut;
	LeftCut.Bound = 2;
	LeftCut.Indices=Indices;
	LeftChild.EdgeFlowCuts_ByEdges_EQ.push_back(LeftCut);

	//Create right child
	PStep_TreeNode RightChild(*CurrentTreeNode);
	//Update left child
	++LastUsedNodeID;
	RightChild.ID = LastUsedNodeID;
	RightChild.Depth = CurrentTreeNode->Depth + 1;
	RightChild.ParentID = CurrentTreeNode->ID;
	RightChild.ParentLB = AlgorithmMembers.CurrentSolution.SolutionValue;
	//Create cut to bound the sum of the edges from below by 4
	PStep_EdgeFlowCut RightCut;
	RightCut.Bound = 4;
	RightCut.Indices = Indices;
	RightChild.EdgeFlowCuts_ByEdges_LB.push_back(RightCut);

	//Delete current tree node
	Nodes.erase(CurrentTreeNode);
	//Add the children
	Nodes.push_back(LeftChild);
	Nodes.push_back(RightChild);
	//Update node counter
	++(AlgorithmMembers.CurrentNumberOfNodes);

	//Update statistics:
	//-----------------------------------------------------------------------
	++(AlgorithmMembers.CurrentBPCStatistics.NumberOfLysgaardBranching);

	//clean
	CMGR_FreeMemCMgr(&SetsCMP);
	delete[]LocationInSet;

}

//Other functions:
//------------------------------------------------------------------------------------

//Set the separation members pertaining to the used edges in the current solution,
//i.e., NumberOfEdgesPlusOne, EdgeHead, EdgeTail, EdgeX.
void PStep_LysgaardBrancher::SetCurrentEdges(){

	//Reset edge information
	NumberOfEdgesPlusOne = 1;
	delete[]EdgeHead;
	EdgeHead = NULL;
	delete[]EdgeTail;
	EdgeTail = NULL;
	delete[]EdgeX;
	EdgeX = NULL;

	//Obtain support variables
	short int NumberOfLocations = AlgorithmMembers.Instance.NumberOfCustomers + 1;
	double Tolerance = AlgorithmMembers.Tolerance;

	//Obtain current edge fraction
	double* EdgeFraction = AlgorithmMembers.CurrentSolution.EdgeFraction;

	//Identify positively selected edges:
	//-------------------------------------------------

	//Initialize vectors containing the positively selected edges
	std::vector<short int> EdgeTailVector;
	std::vector<short int> EdgeHeadVector;
	std::vector<double> EdgeXVector;
	//Go over all edges
	int Counter = 0;
	for (int j = 1; j < NumberOfLocations; ++j){
		//check whether the edge fraction from the depot (i=0) is positive
		if (EdgeFraction[Counter] > Tolerance){
			//Update number of positive edges
			++NumberOfEdgesPlusOne;
			//Store edge information
			EdgeTailVector.push_back(j);
			EdgeHeadVector.push_back(NumberOfLocations); //NumberOfCustomers+1 is used by Lysgaard to represent the depot.
			EdgeXVector.push_back(EdgeFraction[Counter]);
		}
		//Update Counter
		++Counter;
		//Go over the other locations
		for (int i = 1; i < j; ++i){
			//check whether the edge fraction is positive
			if (EdgeFraction[Counter] > Tolerance){
				//Update number of positive edges
				++NumberOfEdgesPlusOne;
				//Store edge information
				EdgeTailVector.push_back(i);
				EdgeHeadVector.push_back(j);
				EdgeXVector.push_back(EdgeFraction[Counter]);
			}
			//Update counter
			++Counter;
		}
	}
	
	//Check whether there are any positively selected edges
	if (NumberOfEdgesPlusOne > 1){

		//Construct input for the algorithm by Lysgaard:
		//-------------------------------------------------

		//Initialize arrays with edge information.
		EdgeTail = new int[NumberOfEdgesPlusOne];
		EdgeHead = new int[NumberOfEdgesPlusOne];
		EdgeX = new double[NumberOfEdgesPlusOne];
		//Lysgaard requires a bogus first edge in the array.
		EdgeTail[0] = 0;
		EdgeHead[0] = 0;
		EdgeX[0] = 0;
		//Go over all identified edges and add them to the arrays
		for (int i = 1; i < NumberOfEdgesPlusOne; ++i){
			EdgeTail[i] = EdgeTailVector[i - 1];
			EdgeHead[i] = EdgeHeadVector[i - 1];
			EdgeX[i] = EdgeXVector[i - 1];
		}
	}

}

//Destructor functions
//------------------------------------------------------------------------------------

//Default destructor
PStep_LysgaardBrancher::~PStep_LysgaardBrancher(){

	delete[]LysgaardDemand;
	delete[]EdgeHead;
	delete[]EdgeTail;
	delete[]EdgeX;

}
