qkw_maxclique.java

//最大团问题的分支限界解法 //屈克文

//最大团问题的分支限界解法
//屈克文，2008.12.01   
   class MaxHeap 
   {                           //大顶堆类
     static HeapNode[] Heap;   //定义HeapNode型数组。
     static int size;          //堆的最大值。
     static int n;             //堆顶数。
    public MaxHeap(HeapNode[] h,int num,int max) 
     { //构造函数
     	Heap=h;
     	n=num;
     	size=max;
     	buildheap();
     }
    public int heapsize()
     { //返回当前堆顶点数
     	 return n;
     }
    public static boolean isLeaf(int pos)
     { //是否是叶结点
     	return(pos>=n/2)&&(pos<n);
     } 
    public static void Assert_notFalse(boolean p,String q)
     {
     	if(!p)
     		System.out.println((String)q);
     }
    public static int key( HeapNode [] q,int p)
     {  
     	return q[p].upperSize;
     }
     
    public static int leftchild(int pos)
     { //左结点位置
     	Assert_notFalse(pos<n/2,"position has no left child");
       return 2*pos+1;
     }
     
    public static int rightchild(int pos)
     { //右结点位置
     	Assert_notFalse(pos<(n-1)/2,"position has no right child");
           return 2*pos+2;
     }
    public static int parent(int pos)
     { //父结点位置
     	Assert_notFalse(pos>0,"position has no parent");
        return (pos-1)/2;
     }
    public static  void buildheap() //重构堆。
     {  
     	for(int i=n/2-1;i>=0;i--)
     		siftdown(i);
     }

    public static void swap(HeapNode[] q,int i,int j)
     {      
       HeapNode temp;
       temp=q[i];q[i]=q[j];q[j]=temp;
      }

    private static void siftdown(int pos) //put intent in itscorrent place
     {
     	Assert_notFalse((pos>=0) && (pos<n),"illegal heap position ");
      while(! isLeaf(pos))
      {
       int j=leftchild(pos);
       if((j<(n-1))&&(key(Heap,j)<key(Heap,j+1)))
         j++;  // j 是最大值的孩子位置
       if(key(Heap,pos)>=key(Heap,j))
       	 return;// Done
       swap(Heap,pos,j);
       pos=j;//Move down 
      }
     }
     
    public static void insert(HeapNode val) 
     {//堆插入函数
     Assert_notFalse(n<size,"Heap is full ");
     int curr=n++;
     Heap[curr]=val;    //从堆底开始插入。
      
     while((curr!=0)&&(key(Heap,curr)>key(Heap,parent(curr))))
       {//重建堆
         swap(Heap,curr,parent(curr));
         curr=parent(curr);
       }
    }
    public static HeapNode removemax()  //remove minimum value
      {
       Assert_notFalse(n>0,"Removing from empty heap ");
       swap(Heap,0,--n);//swap minimum with last value
       if(n!=0)     //Not on last intent
       siftdown(0); //Put new heap root val in corrent place 
       return Heap[n];
     }
  
    public static HeapNode remove(int pos)
     {   //删除指定位置的结点
      Assert_notFalse((pos>0)&&(pos<n),"illegal heap position ");
      swap(Heap,pos,--n); //swap with last value
      if(n!=0)     //Not on last intent
      siftdown(pos);//put new heap root val in corrent place
      return Heap[n];
     }
   public static void outMaxHeap()
     {
     for(int i=0;i<=n-1;i++)
     System.out.print(Heap[i].upperSize+"  ");
     System.out.println(); 
     }       

  static void heapsort()  
    {//堆排序
     System.out.println("建最大堆之后排序");
     
     for(int i=1;i<size-1;i++) 
     System.out.print(removemax().upperSize+"  ");
     System.out.println( );    
    } 
 }// class MaxHeap
 
    class BBnode  //解空间树结点类
    {
       BBnode  parent;    //父结点
       boolean leftChild; //左结点标志
    
      BBnode(BBnode par,boolean ch)
         { //构造函数
           parent=par;  
           leftChild=ch;
         }
    }
    class HeapNode implements Comparable
      {  //堆结点类
           BBnode liveNode; //活结点
           int upperSize;   
           int cliqueSize;  
           int level;       //当前层次
        HeapNode(BBnode node,int up,int size,int lev)
           {//构造函数
             liveNode=node;
             upperSize=up;
             cliqueSize=size;
             level=lev;
           }
        public int compareTo(Object x)
         {
           int xup=((HeapNode)x).upperSize;
           if(upperSize<xup)return -1;
           if(upperSize==xup)return 0;
           return 1;
         }
      } 
    class BBClique 
      {//最大团类
           static boolean [][]a;   //邻接矩阵
           static MaxHeap heap;    // 大顶堆
 
       private static void addLiveNode(int up,int size,int lev,BBnode par,boolean ch)
         {
           BBnode b=new BBnode(par,ch);
           HeapNode node=new HeapNode(b,up,size,lev);
           heap.insert(node);
         }

      public static int bbMaxClique(int [] bestx)
        {
          int n=bestx.length-1;
          HeapNode[] h=new HeapNode[n];
          MaxHeap heap=new MaxHeap(h,0,n);
          //
          BBnode enode=null;
          int i=1;  //当前层次
          int cn=0; //当前顶点数
          int bestn=0;//当前最大顶点数
          while(i!=n+1)  
           {
            // 搜索开始
            boolean ok=true;
            BBnode bnode=enode;//当前扩展结点
            for(int j=i-1;j>0;bnode=bnode.parent,j--)
              if(bnode.leftChild && !a[i][j]) //当顶点i与当前团中所有顶点之间都有边相连，若相连 
                {                             //则相应的左儿子结点是可行结点，将它加入到
                  ok=false;                   //子集树中并插入活结点优先队列，否则就不是可行结点。
                  break;
                }
              if(ok)
                {//左儿子可行
                  if(cn+1>bestn)bestn=cn+1;
                   addLiveNode(cn+n-i+1,cn+1,i+1,enode,true);//加入到子集树中并插入活结点优先队列。
                }
              if(cn+n-i>=bestn)
                //右儿子总是可行的。
              addLiveNode(cn+n-i,cn,i+1,enode,false);
              HeapNode node=(HeapNode)heap.removemax();//取当前堆中最大顶点
              enode=node.liveNode;   //做为扩展结点
              cn=node.cliqueSize;    
              i=node.level;          //向下扩展
          }
            //
          for(int j=n;j>0;j--)
            { //构造最优解。
              bestx[j]=(enode.leftChild)?1:0;
              enode=enode.parent;
            }
          return  bestn;  //当前团最大顶点数！
      } 
    }       
   
  public class qkw_MaxClique
  	{
    public static void main(String args[])
    {
     BBClique abc=new BBClique();//实例化一个最大团类，搜索最大团。
     int n1=5; //5个顶点
     int ak[]=new int[n1+1]; 
     boolean [][] aw=new boolean[n1+1][n1+1];
      aw[1][1]=false;aw[1][2]=true; aw[1][3]=false; aw[1][4]=true; aw[1][5]=true;
      aw[2][1]=true; aw[2][2]=false;aw[2][3]=true;  aw[2][4]=false;aw[2][5]=true;
      aw[3][1]=false;aw[3][2]=true; aw[3][3]=false; aw[3][4]=false;aw[3][5]=true;
      aw[4][1]=true; aw[4][2]=false;aw[4][3]=false; aw[4][4]=false;aw[4][5]=true;
      aw[5][1]=true; aw[5][2]=true; aw[5][3]=true;  aw[5][4]=true; aw[5][5]=false; 
     abc.a=aw;
     System.out.println("屈克文的最大团程序:");    
     System.out.println("最大团顶点数为 " + abc.bbMaxClique(ak));
     for(int i=1;i<=n1;i++)  //输出结果！
     System.out.print("  "+ak[i]);
     System.out.println();
        
    
  }
}