sa_graph.h

用经典的局部搜索算法模拟退火算法求解一个图的最大可平面子图。

// The maximum planar subgraph project 2002-2003
// University of Tampere, Finland
// Department of Computer and Information Sciences
// Corresponding author: Timo Poranen, [e-mail]

// sa_graph.h
// header file for sa_graph class

#include <LEDA/ugraph.h>
#include <LEDA/set.h>
#include <LEDA/list.h>
#include <LEDA/partition.h>

class sa_graph
{
  public: 
  sa_graph(UGRAPH<int,int>*);
  ~sa_graph(); 

  void sa_graph::delete_ini_stuff(); //deletes some unimportant data to save space


  int sa_graph::getCurrentSolution();

  //initialization

  int sa_graph::getVertices();
  int sa_graph::getEdges();

  void sa_graph::sa2();  

  void sa_graph::initialize_empty(); //starts from empty set

  bool sa_graph::isArrayPlanar(int s);
  bool sa_graph::isSetPlanar(int s);  
  
  int * arraySizes;

  //  int sa_graph::getConTableItem(int index);
  int sa_graph::getInitialSolution();

  double getFoundTemperature()
    {return foundTemperature;}
  double getT0()
    {return t0;}
  double getT1()
    {return t1;}
  double getAlpha()
    {return alpha;}
  int getInnerLoop()
    {return inner_loop;}

  void setTraceFileName(char *);

 private:

  //SA parameters
  double t0; //start temperature
  double t1; // end temperature
  double alpha; //cooling ratio
  int inner_loop; //inner loop


  //other sa functions
  void sa_graph::initialize_sa();
  bool sa_graph::readSAParameters();


  //graph data
  int ** adjacency_matrix;
  int ** edge_delete_matrix;

  int vertices;
  int edges;
  UGRAPH<int,int> *G;  // original leda graph


  //  remaining sa material
  int partitionCounter;
  int bestResult;
  void sa_graph::setInitialSolution(int i);
  int largestPlanarSubgraph;
  int initialSolution;
  double foundTemperature;  
  int * edgesInPartitions;
  set<edge> ** edgePartitionArray;
  //for array representation
  array<edge> ** A;
  double sa_graph::evaluationFunction(int s, int * values);  

  char traceFileName[50];
  bool trace;
};