btree.cpp

与遗传算法混合的模拟退火算法的应用

// Project: B*-trees floorplanning
// Advisor: Yao-Wen Chang  <[e-mail]>
// Authors: Jer-Ming Hsu   <[e-mail]>
// 	    Hsun-Cheng Lee <[e-mail]>
// Sponsor: Arcadia Inc.
// Date:    7/19/2000 ~

//---------------------------------------------------------------------------
#include <stack>
#include <algorithm>
#include "btree.h"
#include <iostream>
#include <time.h>
#include <stdio.h> 
#include <vector>
#include <stdlib.h> 
#include <deque>
//---------------------------------------------------------------------------
float rotate_rate = 0.3;
float swap_rate = 0.5;

//---------------------------------------------------------------------------
//   Initialization
//---------------------------------------------------------------------------

void B_Tree::clear(){
  // initial contour value
  contour_root = NIL;
  FPlan::clear();
}

void B_Tree::init(){
  // initialize contour structure
  contour.resize(modules_N);
    
  // initialize b*tree by complete binary tree
  nodes.resize(modules_N);
  nodes_root=0;
  for(int i=0; i < modules_N; i++){
    nodes[i].id = i;
    nodes[i].parent = (i+1)/2-1;
    nodes[i].left   = (2*i+1 < modules_N ? 2*i+1 : NIL);
    nodes[i].right  = (2*i+2 < modules_N ? 2*i+2 : NIL);
  }
  nodes[0].parent = NIL;
  best_sol.clear();
  last_sol.clear();
  clear();
  normalize_cost(10);
} 


string B_Tree::encode()//一个版图的编码存放在encoding 中 
{
   string encoding;      //定义一个整型向量，为两位，来存放编码   
   deque<int> s;
   int array[1000];
   for(int i=0;i<modules_N;i++)
  { 
    if(nodes[i].left==NIL&&nodes[i].right!=NIL)
            printf("%d\n",i);
          encodes.insert(encodes.begin()+i,"01");
    if(nodes[i].left!=NIL&&nodes[i].right!=NIL)
           encodes[i]="11";
    if(nodes[i].left!=NIL&&nodes[i].right==NIL)
         encodes[i]="10";
    if(nodes[i].left==NIL&&nodes[i].right==NIL)
       encodes[i]="00";
  }
   //采用层次遍历产生节点序列 所对应的01串 
    s.push_back(nodes_root);
    if(encodes[nodes_root]=="11")
     {
      array[0]=s.front();
      s.push_back(nodes[nodes_root].left);
      s.push_back(nodes[nodes_root].right);   
      }
    if(encodes[nodes_root]=="10")
      {
        array[0]=s.front();
        s.push_back(nodes[nodes_root].left); 
      }   
    if(encodes[nodes_root]=="01")
     {
      array[0]=s.front();
      s.push_back(nodes[nodes_root].right);   
      }  
   s.pop_front();
   int i=1;
   while(!s.empty())
     {
       int p=s.front();
       array[i]=p;
       if(encodes[p]=="11")
        {
          s.push_back(nodes[p].left);
          s.push_back(nodes[p].right);   
         }
       if(encodes[p]=="10")
         {
           s.push_back(nodes[p].left); 
         }   
      if(encodes[p]=="01")
       {
         s.push_back(nodes[p].right);   
        }  
      s.pop_front();  
      i++;
  }
  for(int i=0;i<modules_N;i++)
  {
    encoding=encoding+encodes[array[i]]; 
  }
   return encoding;   
  
}
void B_Tree::decode_tree(int array[],string encoding)//变量码和新的模块码一一对应，产生新的树 
{ 
   vector<string> codes(encoding.size()/2,"0");
   stack<int> s;
   deque<int> d;
   clear();
   string subencod,sub_encod,temp_code(encoding);
   int num=encoding.size(); 
   for(int i=0;i<num/2;i++)
     {
       subencod=temp_code.substr(0,2);
       sub_encod=temp_code.substr(2);
       codes[array[i]]=subencod;
       temp_code=sub_encod;
     }
    
   for(int i=codes.size()-1;i>=0;i--)  //将模块编号反序压入栈中 
   { 
      s.push(array[i]);   
   }      
    //找出根节点roots 
    int  p=s.top();
     nodes[p].parent=-1;  //此节点为根节点 
     nodes_root=p;
     s.pop();
    if(codes[p]=="11")
     { 
       nodes[p].left=s.top();
       nodes[nodes[p].left].parent=nodes_root;
       d.push_back(nodes[p].left);
       s.pop();
       nodes[p].right=s.top();
       nodes[s.top()].parent=nodes_root;
       d.push_back(nodes[p].right);
       s.pop();
      }
    if(codes[p]=="01") 
    {
      nodes[p].right=s.top();
      nodes[s.top()].parent=nodes_root;
      nodes[p].left=-1;
      d.push_back(nodes[p].right);
      s.pop();
    } 
    if(codes[p]=="10") 
     {
       nodes[p].left=s.top();
       nodes[s.top()].parent=nodes_root;
       nodes[p].right=-1;
       d.push_back(nodes[p].left);
       s.pop();
      }  

 //根据编码创建B*-Tree 
   while (!d.empty())
   { 
      p=d.front();           
      if(codes[p]=="11")
     { 
       nodes[p].left=s.top();
       nodes[s.top()].parent=p;
       d.push_back(nodes[p].left);
       s.pop();
       nodes[p].right=s.top();
       nodes[s.top()].parent=p;
       d.push_back(nodes[p].right);
       s.pop();
     }     
    if(codes[p]=="01") 
    {      
      nodes[p].right=s.top();
      nodes[s.top()].parent=p;
      nodes[p].left=-1;
      d.push_back(nodes[p].right);
      s.pop();
       } 
    if(codes[p]=="10") 
     {  
       nodes[p].left=s.top();
       nodes[nodes[p].left].parent=p;
       nodes[p].right=-1;
       d.push_back(nodes[p].left);
       s.pop();
      }  
     if(codes[p]=="00") 
     { 
       nodes[p].left=-1; 
       nodes[p].right=-1; 
      }  
      d.pop_front(); 
   }
//   show_tree();
  
}

//---------------------------------------------------------------------------
//   Testing, Debuging tools
//---------------------------------------------------------------------------

bool B_Tree::legal(){
  int num=0;
  return legal_tree(NIL,nodes_root,num);
}

bool B_Tree::legal_tree(int p,int n,int &num){
  num++;
  if(nodes[n].parent!=p) return false;
  if(nodes[n].left != NIL)
    if(legal_tree(n,nodes[n].left,num) != true) return false;

  if(nodes[n].right != NIL)
    if(legal_tree(n,nodes[n].right,num) != true) return false;

  if(p==NIL) // root
    return (num==modules_N);
  return true;
}

void B_Tree::testing(){
  int p,n;
  Solution E;

  do{
    n = rand()%modules_N;
    p = rand()%modules_N;

    while(n==nodes_root)		// n is not root
      n = rand()%modules_N;

    while(n==p||nodes[n].parent==p||nodes[p].parent==n)	// n != p & n.parent != p
      p = rand()%modules_N;
   
    Node &node = nodes[n];
    Node &parent = nodes[p];
    get_solution(E);
    swap_node(parent,node);
  }while(legal());

  cout << "p=" << p << ", n=" << n << endl;
  recover(E);
  show_tree();
  cout << "\n  p=" << p << ", n=" << n << endl;
  swap_node(nodes[p],nodes[n]);
  show_tree();
}

void B_Tree::show_tree(){
  cout << "root: " << nodes_root << endl;
  for(int i=0; i < modules_N; i++){
    cout << nodes[i].id << ": ";
    cout << nodes[i].left << " ";
    cout << nodes[i].parent << " ";
    cout << nodes[i].right << endl;
  }
}

//---------------------------------------------------------------------------
//   Placement modules
//---------------------------------------------------------------------------

void B_Tree::packing(){
  stack<int> S;

  clear();
  int p = nodes_root;

  place_module(p,NIL);
  Node &n = nodes[p];
  if(n.right != NIL)      S.push(n.right);
  if(n.left  != NIL)      S.push(n.left);

  // inorder traverse
  while(!S.empty()){
    p = S.top();
    S.pop();
    Node &n = nodes[p];

    assert(n.parent != NIL);
    bool is_left = (nodes[n.parent].left == n.id);
    place_module(p,n.parent,is_left);

    if(n.right != NIL)      S.push(n.right);
    if(n.left  != NIL)      S.push(n.left);
  }

  // compute Width, Height
  double max_x=-1,max_y=-1;
  for(int p= contour_root; p != NIL; p=contour[p].front){
    max_x = max(max_x,double(modules_info[p].rx));  
    max_y = max(max_y,double(modules_info[p].ry));
  }

  Width  = max_x;
  Height = max_y;
  Area   = Height*Width;

  FPlan::packing(); 	// for wirelength  
}

// is_left: default is true
void B_Tree::place_module(int mod,int abut,bool is_left){
  Module_Info &mod_mf = modules_info[mod];
  mod_mf.rotate       = nodes[mod].rotate;
  mod_mf.flip         = nodes[mod].flip;

  int w =  modules[mod].width;
  int h =  modules[mod].height;
  if(nodes[mod].rotate)
    swap(w,h);
  
  if(abut==NIL){	// root node
    contour_root = mod;
    contour[mod].back = NIL;
    contour[mod].front = NIL;
    mod_mf.x  = mod_mf.y = 0;
    mod_mf.rx = w, mod_mf.ry = h;
    return;
  }
  
  int p;   // trace contour from p

  if(is_left){	// left
    int abut_width = (nodes[abut].rotate ? modules[abut].height : 
                                           modules[abut].width);
    mod_mf.x  = modules_info[abut].x + abut_width;
    mod_mf.rx = mod_mf.x + w;
    p = contour[abut].front;

    contour[abut].front = mod;
    contour[mod].back = abut;

    if(p==NIL){  // no obstacle in X axis
      mod_mf.y = 0;
      mod_mf.ry = h;
      contour[mod].front = NIL;
      return;
    }
  }else{	// upper
    mod_mf.x = modules_info[abut].x;
    mod_mf.rx = mod_mf.x + w;
    p = abut;
     
    int n=contour[abut].back;