sa_alg.cpp

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

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

// SA_ALG.cpp
// - simulated annealing algorithm

#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::sa2()
{      
  //open trace file if used
  if (trace==true)
    {
      ofstream tracef(traceFileName, ios::out);  
      if (!tracef) {
	cout<<"Can not open tracefile "<<traceFileName<<endl;	
	exit(0);
      }
      tracef.close();
    }
  
  cout<<"Simulated Annealing algorithm started"<<endl;
  initialize_sa();    
  foundTemperature=t0;
  cout<<"initialization";
  edge e;
  //first we insert all edges to first set!
  setInitialSolution(0);  
  int tCounter=0;
  int sSet=0;
  int sizeOfSSet=0;

  //to get data from runs of algorithm
  int godMoveCounter=0;
  int badMoveCounter=0;
  int evenMoveCounter=0;
  int unAcceptedMoves=0;
  
  int tGodMoveCounter=0;
  int tBadMoveCounter=0;
  int tEvenMoveCounter=0;
  int tUnAcceptedMoves=0;

  bool optimalSolutionFound=false;
  double t=t0;
  int counter=0;
  edge e1;
  edge e2;
  int e1o=0;
  int e2o=0;

  int sum=0; //for checking... (remove later)

  int eb=3*vertices-6;  
  //copy edges from sets to array A
  //and initialize it!
  arraySizes = new int [2];
  A = new array<edge> * [2];  

  for (int i=0;i<2;i++)
    {
      A[i]= new array<edge>(edges);
      arraySizes[i]=0;
    }

 //  cout<<"here3"<<endl;  
 //copy edges to partition!
 //copy items from edge sets to edge arrays

  forall_edges(e,*G)
    {
      A[1]->set(counter,e);
      G->assign(e,1); //assign partition number!       
      counter++;
    }
  arraySizes[1]=counter;

  counter=0; //counter is also used in the sa's main loop
  
  //to save space, delete set and other unimportant data
  //  cout<<"here4"<<endl;  
  delete_ini_stuff();

  e1o=1; //(not) planar set (could be planar for graphs with thickness 2)
  e2o=0; //planar set
  
  while (t>t1 && !optimalSolutionFound)
    {           
      if (trace==true)
	{
	  ofstream tracef(traceFileName, ios::app);  
	  if (!tracef) {
	    cout<<"Can not open tracefile "<<traceFileName<<endl;	
	    exit(0);
	  }
	  //cout<<"writing trace file: "<<t<<" "<<arraySizes[e2o]<<endl;
	  tracef<<t<<"  "<<arraySizes[e2o]<<endl;
	  tracef.close();		  
	}
      
      //      cout<<"in big loop"<<endl;
      while (counter<inner_loop && !optimalSolutionFound)
	{	  	  
	  counter++;
	  tCounter++; //for tracking whole run of algorithm
	  //cout<<"here5"<<endl;  	  
	  int e1Index=rand()%arraySizes[e1o];

	  
	  //cout<<"e1index: "<<e1Index<<" e2index: "<<e1Index<<endl;
	  
	  e1=A[e1o]->get(e1Index);

	  //cout<<"hereB"<<endl;  	  	  
	  if (arraySizes[e2o]<eb)
	    {	
	      //  cout<<" in the B"<<endl;
	      A[e2o]->set(arraySizes[e2o],e1); 
	      arraySizes[e2o]++;	
	      //cout<<" in the B1, e2o:"<<e2o<<endl;      	      

	      if (isArrayPlanar(e2o)==true) //fine!
		{	      	
		  //  cout<<"hereC"<<endl;  	  	  
		  //cout<<" good move!"<<endl;
		  godMoveCounter++;
		  edge tmp = A[e1o]->get(arraySizes[e1o]-1);		  
		  A[e1o]->set(e1Index,tmp);
		  arraySizes[e1o]--;		    		  
		}
	      else		
		{
		  //cout<<"hereD"<<endl;  	  	  
		  arraySizes[e2o]--;
		  
		  //choose edge from planar set
		  int e2Index=rand()%arraySizes[e2o];
		  e2=A[e2o]->get(e2Index);

		  A[e2o]->set(e2Index,e1);
		  A[e1o]->set(e1Index,e2);
		  
		  if (isArrayPlanar(e2o)==true) //fine!
		    {
		      //cout<<"Set "<<e2o<<" is planar after swap!!!!"<<endl;
		      evenMoveCounter++;
		    }		  
		  //swap was not possible.
		  //we try to move that edge from larger partition to smaller one!
		  else
		    {
		      //cout<<"SA test that do we move an edge to the non-planar partition!"<<endl;
		      //take again all changes back...
		      A[e2o]->set(e2Index,e2);
		      A[e1o]->set(e1Index,e1);

		      //double cDeviation=deviation2(partitionCounter,arraySizes);
		      
		      A[e1o]->set(arraySizes[e1o],e2); 
		      arraySizes[e1o]++;
		      
		      double randomNumber = rand()/double(RAND_MAX);
		      double probability = exp(-1/t);			      
		      
		      //cout<<randomNumber<<" ? <= "<<probability<<endl;			      
		      if (randomNumber<(probability))
			{		  		   
			  badMoveCounter++;				  
			  edge last=A[e2o]->get(arraySizes[e2o]-1);
			  A[e2o]->set(e2Index,last); 			      
			  arraySizes[e2o]--;			      				
			}
		      else //(randomNumber<probability)
			{		  		   
			  arraySizes[e1o]--;
			  unAcceptedMoves++;
			}
		    }
		  
		  
		}
	    }
	  else 
	    {
	      //maximum planar subgraph found! (due to euler bound)
	      //do nothing
	    }

	  int size_of_largest_set=arraySizes[0];
	  
	  if (size_of_largest_set>largestPlanarSubgraph)
	    {
	      largestPlanarSubgraph=size_of_largest_set;
	      foundTemperature = t;
	    }
	  cout<<counter<<" / "<<inner_loop<<" current: "<<size_of_largest_set<<" best: "<<largestPlanarSubgraph<<endl;      
	  if (largestPlanarSubgraph==eb)
	    {
	      optimalSolutionFound=true;	      
	    }	      
	  
	  if (badMoveCounter+godMoveCounter+evenMoveCounter+unAcceptedMoves != counter && optimalSolutionFound==false)
	   {
	     cout<<"errors when counting moves!"<<endl;	      	      
	     exit(0);
	   }	  
	  //we check total number of god, bad , even and uinaccepted moves
	  
	}
      
      cout<<"Temperature: "<<t<<endl;
      cout<<"GOD MOVES "<<godMoveCounter<<" / "<<inner_loop<<endl;
      cout<<"EVEN MOVES "<<evenMoveCounter<<" / "<<inner_loop<<endl;
      cout<<"BAD MOVES "<<badMoveCounter<<" / "<<inner_loop<<endl;
      cout<<"UNACCEPTED MOVES "<<unAcceptedMoves<<" / "<<inner_loop<<endl;

      badMoveCounter=0;
      godMoveCounter=0;
      evenMoveCounter=0;
      unAcceptedMoves=0;
      
      t=alpha*t;
      counter=0;
    }

  if (trace==true)
    {
      ofstream tracef(traceFileName, ios::app);  
      if (!tracef) {
	cout<<"Can not open tracefile "<<traceFileName<<endl;	
	exit(0);
      }
      //      cout<<"writing trace file: "<<t<<" "<<arraySizes[e2o]<<endl;
      tracef<<t<<"  "<<arraySizes[e2o]<<endl;
      //cout<<"Log file closed."<<endl;
      tracef.close();		  
    }


  for (int i=0;i<2;i++)
    {
      delete A[i];
    }
  delete [] A;
      
  cout<<"Largest found planar subgraph: "<<largestPlanarSubgraph<<endl;
  cout<<"Simulated Annealing algorithm ended"<<endl;
}