//
// bifurcating search selecting: parameters selection and heuristic
// 
// 00: <reject,accept> min degree
// 01: <reject,accept> max degree
// 10: <accept,reject> min degree
// 11: <accept,reject> max degree
//
import java.util.*;

class MCBif extends MCU {

    int heuristic;

    MCBif (int n,int[][]A,int[] degree,int style,int selection,int heuristic) {
	super(n,A,degree,style,selection);
	this.heuristic = heuristic;
    }

    void search(){
	cpuTime                               = System.currentTimeMillis();
	nodes                                 = 0;
	ArrayList<Integer> C                  = new ArrayList<Integer>(n);
	ArrayList<Integer> ColOrd             = new ArrayList<Integer>(n);
	orderVertices(ColOrd);
	expand(C,ColOrd);
    }

    void expand(ArrayList<Integer> C,ArrayList<Integer> ColOrd){
	if (timeLimit > 0 && System.currentTimeMillis() - cpuTime >= timeLimit) return;
	nodes++;	
	nodesAtDepth[C.size()]++;
	ArrayList<ArrayList<Integer>> colourClasses = colourSort(ColOrd);
	if (colourClasses.size() + C.size() > maxSize){
	    int v = -1;
	    if (heuristic == 0) v = selectMin(ColOrd);
	    if (heuristic == 1) v = selectMax(ColOrd);
	    if (heuristic == 2) v = selectLastVertex(colourClasses);
	    if (heuristic == 3) v = selectFirstVertex(colourClasses);
	    if (selection == 0){
		reject(C,ColOrd,v);
		accept(C,ColOrd,v);
	    }
	    if (selection == 1){
		accept(C,ColOrd,v);
		reject(C,ColOrd,v);
	    }
	}
    }

    void accept(ArrayList<Integer> C,ArrayList<Integer> ColOrd, int v){
	C.add(v);
	ArrayList<Integer> newColOrd = new ArrayList<Integer>();
	for (int w : ColOrd) if (adjacent(v,w)) newColOrd.add(w);
	if (C.size() > maxSize) saveSolution(C);
	if (!newColOrd.isEmpty()) expand(C,newColOrd);
	C.remove((Integer) v);
    }

     void reject(ArrayList<Integer> C,ArrayList<Integer> ColOrd, int v){
	ArrayList<Integer> newColOrd = new ArrayList<Integer>();
	for (int w : ColOrd) if (v!=w) newColOrd.add(w);
	if (!newColOrd.isEmpty()) expand(C,newColOrd);
    }


    int selectLastVertex(ArrayList<ArrayList<Integer>> colourClasses){
	int n = colourClasses.size();
	ArrayList<Integer> colourClass = colourClasses.get(n-1);
	int m = colourClass.size();
	return colourClass.get(m-1);
    }

    int selectFirstVertex(ArrayList<ArrayList<Integer>> colourClasses){
	ArrayList<Integer> colourClass = colourClasses.get(0);
	return colourClass.get(0);
    }

    int selectMin(ArrayList<Integer> P){
	int n = P.size();
	int[] deg = getDegree(P);
	int minDeg = n;
	int vertex = -1;
	for (int i=0;i<n;i++) 
	    if (deg[i] < minDeg){minDeg = deg[i];vertex = i;}
	return P.get(vertex);
    }

    int selectMax(ArrayList<Integer> P){
	int n = P.size();
	int[] deg = getDegree(P);
	int maxDeg = -1;
	int vertex = -1;
	for (int i=0;i<n;i++) 
	    if (deg[i] > maxDeg){maxDeg = deg[i];vertex = i;}
	return P.get(vertex);
    }

    int[] getDegree(ArrayList<Integer> P){
	int n = P.size();
	int[] deg = new int[n];
	for (int i=0;i<n-1;i++){
	    int v = P.get(i);
	    for (int j=i+1;j<n;j++){
		int w = P.get(j);
		deg[i] = deg[i] + A[v][w];
		deg[j] = deg[j] + A[w][v];
	    }
	}
	return deg;
    }
}