/*Implementation of PStep_Brancher

It contains the member functions of PStep_MostFractionalEdgeBrancher

*/

#include "PStep_Brancher.h"

//PStep_MostFractionalEdgeBrancher:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Branching functions
//------------------------------------------------------------------------------------

//Branch on AlgorithmMembers.CurrentTreeNode. The current node is deleted
//from AlgorithmMembers.Nodes while the new node(s) are added to it.
//Branch on the most fractional edge.
//Only edges not connected to the depot are considered.
void PStep_MostFractionalEdgeBrancher::Branch(){

	BranchOnMostFractionalEdge();

}


//Branch on the most fractional edge.
//Only edges not connected to the depot are considered.
void PStep_MostFractionalEdgeBrancher::BranchOnMostFractionalEdge(){

	//Obtain number of locations
	short int NumberOfLocations = AlgorithmMembers.Instance.NumberOfCustomers + 1;
	//Obtain pointer to current edge fraction
	double* EdgeFraction = AlgorithmMembers.CurrentSolution.EdgeFraction;
	//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;

	//Select the most fractional edge among edged not connected to the depot:
	//-----------------------------------------------------------------------
	
	//Initialize most fractional edge index and distance as corresponding to
	//edge 1-2, the first edge not connected to the depot.
	short int MostFractionalEdgeIndex = 2;
	double MostFractionalEdgeDistance = std::abs(EdgeFraction[2] - 0.5);

	//Go over all edges
	//Initialize EdgeCounter, we skip i=0, j=1 because this is an edge connected to the depot.
	short int EdgeCounter = 3;
	//Go over all ending locations
	for (short int j = 3; j < NumberOfLocations; ++j){
		//Update the counter for skipping the depot.
		++EdgeCounter;
		//Go over all starting except the depot
		for (short int i = 1; i < j; ++i){
			
			//Compute current distance to 0.5
			double CurrentDistance = std::abs(EdgeFraction[EdgeCounter] - 0.5);

			//Check whether the current edge is more fractional than the current most
			if (CurrentDistance < MostFractionalEdgeDistance){
				//The current edgevalue is more fractional, update
				MostFractionalEdgeIndex = EdgeCounter;
				MostFractionalEdgeDistance = CurrentDistance;
			}

			//Update counter
			++EdgeCounter;
		}
	}

	//Branch on selected edge:
	//-----------------------------------------------------------------------

	//Set the edge to 1 in the left child, and 0 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 edge to 1
	PStep_EdgeFlowCut Cut;
	Cut.Bound = 1;
	Cut.Indices.push_back(MostFractionalEdgeIndex);
	LeftChild.EdgeFlowCuts_ByEdges_EQ.push_back(Cut);

	//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;
	//Disable the use of the edge
	RightChild.EdgeInUse[MostFractionalEdgeIndex] = false;

	//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.NumberOfMostFractionalEdgeBranching);

}