btree.h

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

// 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 ~

//---------------------------------------------------------------------------
#ifndef btreeH
#define btreeH
//---------------------------------------------------------------------------
#include <vector>
#include <cassert>
#include "fplan.h"
//---------------------------------------------------------------------------
const int NIL = -1;
typedef bool DIR;
const bool LEFT=0, RIGHT=1;

struct Node{
  int id,parent,left,right;
  bool rotate,flip;
  bool isleaf(){ return (left==NIL && right==NIL); }
};
 
struct Contour{
  int front,back;
};

class B_Tree : public FPlan{
  public:
    B_Tree(float calpha=1) :FPlan(calpha) {}  //构造函数 
    virtual void init();                        //初始化 
    virtual void packing();
    virtual void perturb();
    virtual void keep_sol();
    virtual void keep_best();    
    virtual void recover();
    virtual void recover_best();
    virtual void show_tree();                         //输出B-TREE   
    virtual void decode_tree(int array[],string encoding); 
    virtual string encode();
    // debuging
    void testing();                           //测试 
    
  protected:
    
 
    void place_module(int mod,int abut,bool is_left=true);
    bool legal();                            //测试是否合法 
    void clear();                            //清除 
    
    // Auxilary function
    void wire_nodes(int parent,int child,DIR edge);
    int child(int node,DIR d);
    bool legal_tree(int p,int n,int &num);
    void add_changed_nodes(int n);
  
    // SA permutating operation
    void swap_node(Node &n1, Node &n2);
    void insert_node(Node &parent,Node &node);
    void delete_node(Node &node);
    
    bool delete_node2(Node &node,DIR pull);
    void insert_node2(Node &parent,Node &node,
                     DIR edge,DIR push,bool fold=false);

    int contour_root;
    vector<Contour> contour;    
    int nodes_root;
    vector<Node> nodes;   
    vector<string> encodes;
 
  private:        
    struct Solution{
      int nodes_root;
      vector<Node> nodes;
      double cost;
      Solution() { cost = 1; }
      void clear() { cost = 1, nodes.clear(); }
    };
  
    void get_solution(Solution &sol);
    void recover(Solution &sol);
    void recover_partial();

    Solution best_sol, last_sol;
    // for partial recover
    vector<Node> changed_nodes;
    int changed_root;    
    int array[1000];
};

//---------------------------------------------------------------------------
#endif