package csc206;
public class BranchandBound {
/**
* @param args
*/
public int[] selectedNodes = new int[5]; //nodes that have been at lease arrived at.
public int[] leftList = new int[5];
public int[] arrivedList = new int[5];
public int[] shortestPath = new int[5];
public int[][] lbResultList = {{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1}};
public int shortestDistance = 9999;
public int[] finalshortestPath = new int[5];
public static int[][] costArray = {{0,14,4,10,20},
{14,0,7,8,7},
{4,5,0,7,16},
{11,7,9,0,2} ,
{18,7,17,4,0}};
public int lowerBound = 0;
boolean allVisited = false;
int nodeCount = 0;
public static int itrCnt = 0;
public void resetDataStructures()
{
int i,j;
for(i = 0; i < 5; i++)
{
selectedNodes[i] = -1;
leftList[i] = -1;
arrivedList[i] = -1 ;
shortestPath[i] = -1 ;
}
for(i = 1; i< 5; i++)
{
for(j = 0;j < 5; j++)
{
lbResultList[i][j] = -1;
}
}
nodeCount = 0;
lowerBound = 0;
}
public void findLowerBound()
{
lowerBound = 0;
int lowLeave = 0;
boolean done = false;
int i = 0,row,col;
int emptySlot;
int leftCnt = 0, arriveCnt = 0;
while(!done)
{
emptySlot = selectedNodes[i];
if(emptySlot == -1 || selectedNodes[i] == i)
{
done = true;
}
else
{
//if(selectedNodes[i] == i)
//System.out.print(i+1+"-->");
lowerBound = lowerBound + costArray[i][selectedNodes[i]]; //calculates cost between 2 nodes
System.out.print(i+1);
System.out.print(" --> ");
i = selectedNodes[i];
}
}
System.out.print(i+1 + ":");
//finding lowest cost of leaving all the nodes
/*
* CONDITIONS TO CHECK
* 1) cannot leave for it self
* 2) cannot leave on the node that has already been arrived on
* 3) cannot leave if already left this node once.
*
*/
for(row = 0; row < 5 ; row++)
{
if(leftList[row] < 0) // checks whether we have left from the node or not
{
lowLeave = 9999;
for (col = 0; col < 5 ; col++)
{
if(costArray[row][col] != 0 && costArray[row][col] < lowLeave && arrivedList[col] == -1)
{
if(arrivedList[row] != -1) // if we have already arrived this node
{
if(leftList[col] == -1) // only leave for the node that has not been arrived before (condition 2)
{
lowLeave = costArray[row][col];
}
else
{
if(selectedNodes[row] == row && nodeCount == 4)
{
lowLeave = costArray[row][col];
}
}
}
else
{
lowLeave = costArray[row][col];
}
}
}
if(lowLeave != 9999)
leftCnt = leftCnt + lowLeave;
}
}
//finding lowest cost to arrive at all nodes
/*
* check whether we have arrived to this city once
* check the node we are arriving from is not connected to some other node.
*
*/
for(col = 0; col < 5 ; col++)
{
if(arrivedList[col] == -1) //checks whether we have arrived to this node or not.
{
lowLeave = 9999;
for (row = 0; row < 5 ; row++)
{
if(costArray[row][col] != 0 && leftList[row] == -1 && costArray[row][col] < lowLeave)
{
if(leftList[col] != -1)
{
if(arrivedList[row] == -1)
{
lowLeave = costArray[row][col];
}
else
{
if (selectedNodes[row] == row && nodeCount == 4)
{
lowLeave = costArray[row][col];
}
}
}
else
{
lowLeave = costArray[row][col];
}
}
}
if(lowLeave != 9999)
arriveCnt = arriveCnt + lowLeave;
}
}
lowerBound = lowerBound + (leftCnt + arriveCnt)/2 ;
System.out.print(" "+lowerBound + "\n");
}
public boolean checkDone()
{
boolean done = true;
int i = 0;
for(i = 0;i < 5;i++)
{
if(shortestPath[i] < 0)
{
done = false;
}
}
return done;
}
public int findLowest(int index)
{
int temp = 9999, lowestIndex = 0;
int cnt = 0;
while(cnt<5)
{
if(lbResultList[index][cnt] != -1 && lbResultList[index][cnt] < temp)
{
temp = lbResultList[index][cnt];
lowestIndex = cnt;
}
cnt++;
}
if(index == 0)
lbResultList[index][lowestIndex] = -1;
return(lowestIndex);
}
/*
* functions calculates lower bound and addes the nodes depending on the lowest bound
*
*/
public void tsp(int index)
{
int i = 0;
int newIndex = -1;
selectedNodes[index] = index;
nodeCount++;
while(!checkDone())
{
while(i<5)
{
if(selectedNodes[i] == -1)
{
selectedNodes[i] = i;
selectedNodes[index] = i;
leftList[index] = i;
arrivedList[i] = index;
findLowerBound();
lbResultList[index][i] = lowerBound;
i++;
selectedNodes[i - 1] = -1;
arrivedList[i - 1] = -1;
}
else
{
i++;
}
}
newIndex = findLowest(index);
selectedNodes[index] = newIndex ;
shortestPath[index] = newIndex;
leftList[index] = newIndex;
arrivedList[newIndex] = index;
System.out.println("\n");
if(nodeCount == 4)
{
if(newIndex != 0)
{
shortestPath[newIndex] = 0;
leftList[newIndex] = 0;
}
System.out.print("Shortest Path is : ");
int ind = 0;
System.out.print(ind + 1);
for(int a = 0; a < 5 ; a++)
{
System.out.print(" --> ");
System.out.print(shortestPath[ind] + 1);
ind = shortestPath[ind];
}
}
else
{
tsp(newIndex);
}
}// end of checkDone() while loop
}
public void getShortestPath()
{
int cnt = 1;
int newIndex = 0;
while(cnt <= 4)
{
tsp(newIndex);
resetDataStructures();
newIndex = findLowest(0);
selectedNodes[0] = newIndex;
shortestPath[0] = newIndex;
leftList[0] = newIndex;
arrivedList[newIndex] = 0;
cnt++;
System.out.println("\n----------------");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BranchandBound bb = new BranchandBound();
bb.resetDataStructures();
bb.getShortestPath();
}
}
