sa_graph.cpp

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

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

//SA_GRAPH.CPP
// - constructors
// - destructors
// - initialization 

#include <LEDA/ugraph.h>
#include <LEDA/set.h>
#include <LEDA/list.h>
#include <LEDA/node_list.h>
#include <LEDA/graph_misc.h> 
#include <LEDA/graph_alg.h>

#include <LEDA/array.h>

#include <iostream.h>
#include <stdlib.h>
#include "sa_graph.h"


void sa_graph::setTraceFileName(char * file)
{
  //cout<<"tracefile set"<<endl;
  trace=true;
  strcpy(traceFileName,file);
}

void sa_graph::setInitialSolution(int i)
{
  initialSolution=i;
  largestPlanarSubgraph=i;
}

sa_graph::sa_graph(UGRAPH<int,int> *Gr)
{
  
  G = Gr;
  vertices=G->number_of_nodes();
  edges=G->number_of_edges();

  largestPlanarSubgraph=0;
  
  edgePartitionArray = new set<edge> * [vertices];
  
  for (int i=0;i<2;i++)
    {
      edgePartitionArray[i]= new set<edge>;
    }

  bestResult=-1;
  trace=false;
}

void sa_graph::delete_ini_stuff()
{

  //delete [] tmpSarmat;
  
  for (int i=0;i<2;i++)
    {
      delete edgePartitionArray[i];
    }
  delete [] edgePartitionArray;
}


sa_graph::~sa_graph()
{
  //  delete [] conTable;
  //cout<<"in the destructor!"<<endl;
} 

//PLANARITY CHECK FOR edge sets and edge arrays

//checks that is array (0..partitionCounter-1) planar
//we hide all other edges and then test planarity
//finally we restore all edges!
bool sa_graph::isArrayPlanar(int s)
{
  //cout<<"in the planarity test"<<endl;
  edge e;   
  forall_edges(e,*G)
    {
      G->hide_edge(e);
    }
  
  for (int i=0;i<arraySizes[s];i++)
    {
      e = A[s]->get(i);
      G->restore_edge(e);
    }
  
  bool planarFlag=false;
  
  if (Is_Planar(*G))    
    {
      planarFlag=true;	  
    }
  
  G->restore_all_edges();  

  //  cout<<"planarity test end"<<endl;  
  return planarFlag;
}


int sa_graph::getVertices()
{
  return vertices;
}
int sa_graph::getEdges()
{
  return edges;
}

bool sa_graph::readSAParameters()
{
  
  cout<<"reading parameter file!"<<endl;
  ifstream parameterFile("sa_parameters.txt");

  if (!parameterFile)
    {
      cout<<"Can't open parameterfile sa_parameters.txt"<<endl;      
      exit(0);
    }

  char txt[20];
  double value;
  parameterFile >> txt;
  parameterFile >> value;
  t0=value;
  parameterFile >> txt;
  parameterFile >> value;
  t1=value;
  parameterFile >> txt;
  parameterFile >> value;
  alpha=value;
  int loop;
  parameterFile >> txt;
  parameterFile >> loop;
  inner_loop=loop;  
  return true;
}

int sa_graph::getCurrentSolution()
{
  return largestPlanarSubgraph;
}

//places randomly only one edge to the first planar set
//We call this initialization method "empty", since
//it starts from an empty set and place one edge to the first set.
//Now we can use sa-algorithms main loop 
void sa_graph::initialize_empty()
{
  cout<<"initialization";
  partitionCounter=2;
  edge e;
  
  //first we insert all edges to first set!
  forall_edges(e,*G)
    {
      edgePartitionArray[1]->insert(e);
      G->assign(e,1); //assign partition number!       
    }
  
  e=edgePartitionArray[1]->choose();

  edgePartitionArray[0]->insert(e);
  if (isSetPlanar(0)==true)
    {
      edgePartitionArray[1]->del(e);	      
      G->assign(e,0); //assign part. number!  
      cout<<"one edge inserted to set 1"<<endl;
      edgesInPartitions[0]++;
    }
  else
    {
      cout<<"an error, since one edge induces always planar graph!"<<endl;
      exit(0);    
    }
  
  setInitialSolution(edgesInPartitions[0]);  
}



void sa_graph::initialize_sa()
{
  cout<<"Simulated annealing started!"<<endl;
  if (!readSAParameters())
    {
      cout<<"can't read parameters from sa_parameters.txt"<<endl;
      exit(0);
    }

  if  (t0<0 || t0>15)
    {
      cout<<"error 't0' in sa's paremeters"<<endl;
      exit(0);
    }

  if  (t1<0 || t1>15)
    {
      cout<<"error 't1' in sa's paremeters"<<endl;
      exit(0);
    }

  if  (alpha<0 || alpha>15)
    {
      cout<<"error 'alpha' in sa's paremeters"<<endl;
      exit(0);
    }

  if  (inner_loop<0 || inner_loop>7)
    {
      cout<<"error 'inner_loop' in sa's paremeters"<<endl;
      exit(0);
    }

  //set correct value for global variable inner_loop
  if (inner_loop==0)
    inner_loop=vertices;
  else if (inner_loop==1)
    inner_loop=2*vertices;
  else if (inner_loop==2)
    inner_loop=vertices*vertices;
  else if (inner_loop==3)
    inner_loop=vertices*vertices/2;
  else if (inner_loop==4)
    inner_loop=edges/2;
  else if (inner_loop==5)
    inner_loop=edges;
  else if (inner_loop==6)
    inner_loop=2*edges;

  else
    {
      cout<<"error 'inner_loop' in sa's paremeters"<<endl;
      exit(0);
    }

  cout<<"initialization done"<<endl;
}


//checks that is set s (0..partitionCounter-1) planar
bool sa_graph::isSetPlanar(int s)
{
  edge e;

  set<edge> hidden;
  forall_edges(e,*G) {
    if (edgePartitionArray[s]->member(e))
      {
        //do nothing
      }
    else
      {
        G->hide_edge(e);
        hidden.insert(e);
      }
  }

  bool planarFlag=false;
  if (Is_Planar(*G))
    planarFlag=true;

  forall(e,hidden)
    {
      G->restore_edge(e);
    }
  return planarFlag;
}