max_planar.cpp

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

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

// max_planar.cpp
// Main loop for max_planar_{SA} algorithm

#include <LEDA/array.h>
#include <LEDA/graph.h>
#include <LEDA/plane_graph_alg.h>

#include<iostream.h>
#include<string.h>
#include<time.h>

#include"sa_graph.h"

void printUsage()
{
  cout<<endl;
  cout<<"A simulated annealing algorithm for determining maximum planar subgraphs"<<endl;
  cout<<"University of Tampere, Department of Computer and Information Sciences, 2003"<<endl;
  cout<<endl; 
  cout<<"Usage: a.out REPEATS RESULT_FILE -e -sa GRAPH_SOURCE_TYPE [PARAMETERS]"<<endl;
  cout<<"       REPEATS         number of repeats of the algorithm"<<endl;
  cout<<"       RESULT_FILE     file where results are written"<<endl; 
  cout<<"       -e              empty set initialization"<<endl;
  cout<<"       -sa             simulated annealing algorithm"<<endl;
  cout<<"       -f FILENAME     graph is read from file. File in edge-list format"<<endl;
  cout<<"       -fgml FILENAME  graph is read from file. File in gml format"<<endl;
  cout<<"       -r V E [TARGET] random graph with V vertices and E edges"<<endl;
  cout<<"                       graph is saved to filename TARGET in gml-format"<<endl;  
  cout<<"       -t trace.txt    a trace file trace.txt is written"<<endl;
  cout<<endl; 
  cout<<"Examples: ./a.out 20 results/res.txt -e -sa -f graphs/data/g5.dat "<<endl;
  cout<<"          ./a.out 1 res.txt -e -sa -fgml graphs/random1.gml"<<endl;
  cout<<"          ./a.out 1 res.txt -e -sa -r 80 350 graphs/random1.gml"<<endl;
  cout<<"          ./a.out 1 results/res.txt -e -sa -f graphs/data/g19.dat -t results/trace.txt"<<endl;
  cout<<endl;
  cout<<"Notice that the order of parameters matters! See also README.txt to get more information."<<endl;
  cout<<endl;
  exit(0);
}


int main (int argc, char *argv[]) 
{      
  srand(time(0));  
  bool randomGraph=false;  
  double iniSolAverage=0;
  double solutionAverage=0;  
  int bestSolution=0;  
  if (argc<7)
    {
      printUsage();
    }      
  int rounds=atoi(argv[1]);
  ofstream outfile(argv[2], ios::out);  
  if (!outfile) {
    cout<<"Can not open file "<<argv[2]<<" for results"<<endl;
    exit(0);
  }  
  UGRAPH<int,int> G;     
  
  for (int runs=0;runs<rounds;runs++)
    {            
      //we print information on graph just once            
      //check that if we are handling random graphs!
      
      if (randomGraph==false)
	{
	  UGRAPH<int,int> G;     
	}

      //initialization from file  
      if (strcmp(argv[5], "-fgml")==0)
	{      
	  cout<<"Reading graph from file "<<argv[6]<<endl;	  
	  bool flag=false;
	  if (runs==0)
	    {
	      outfile<<"Graph "<<argv[6]<<" read from file "<<endl;	  
	    }	  
	  flag=G.read_gml(argv[6]);	  
	  if (flag==true)
	    {
	      //why LEDA function read_gml() does not return false if
	      //file doesn't exists??
	      if (runs==0)
		{
		  outfile<<"Vertices: "<<G.number_of_nodes()<<" Edges: "<<G.number_of_edges()<<endl;	  
		}
	      if (G.number_of_nodes()==0 || G.number_of_edges()==0)
		{		  
		  cout<<"graph is not valid or it does not exists"<<endl;
		  outfile<<"graph is not valid or it does not exists"<<endl;		  
		  exit(0);
		}
	    }
	  else
	    {	      	      
	      cout<<"Something wrong with the gml-file "<<argv[6]<<endl;
	      outfile<<"graph is not valid or it does not exists"<<endl;
	      exit(0);
	    }	  
	}
      //reads non-gml file, graph saved in edge-list format
      else if (strcmp(argv[5], "-f")==0)
	{      
	  int v,e;
	  cout<<"Reading graph from file "<<argv[6]<<endl;	  
	  bool flag=false;	  
	  if (runs==0)
	    {
	      outfile<<"Graph "<<argv[6]<<" read from file "<<endl;	  
	    }

	  ifstream infile(argv[6]);	  
	  if (!infile)
	    {
	      cout<<"graph is not valid or it does not exists"<<endl;
	      outfile<<"graph is not valid or it does not exists"<<endl;		  
	      exit(0);
	    }
	  infile >> v;
	  infile >> e;	  
	  cout<<"vertice: "<<v<<" edges: "<<e<<endl;	  
	  G.del_all_edges();
	  G.del_all_nodes();	  	      
	  int total=0;	      
	  if (runs==0)
	    {
	      outfile<<"Vertices: "<<v<<" Edges: "<<e<<endl;
	      
	    }
	  //create nodes
	  set<node> ** nodePartitionArray = new set<node> * [v];
	  for (int i=0;i<v;i++)
	    {
	      nodePartitionArray[i]= new set<node>;
	    }
	  for (int i=0;i<v;i++)
	    {
	      node d;
	      d=G.new_node();
	      nodePartitionArray[i]->insert(d);	      	      
	    }	  

	  //read edges and add them to the graph!
	  int s,t;
	  for (int i=0;i<e;i++)
	    {
	      infile >> s;
	      infile >> t;
	      if (s <=0 || t<=0 || s>v || t > v || s==t)
		{
		  cout<<"graph file is not valid"<<endl;
		  outfile<<"graph file is not valid"<<endl;
		  
		  exit(0);
		}
	      node snode = nodePartitionArray[s-1]->choose();
	      node tnode = nodePartitionArray[t-1]->choose();
	      G.new_edge(snode,tnode);
	    }
	  delete [] nodePartitionArray;            
	}
      
      //random graph
      else if (strcmp(argv[5], "-r")==0 )      
	{
	  if (argc<8)
	    {
	      printUsage();
	    }
	  //we create random graph only once!
	  if (runs==0)
	    {
	      int n=atoi(argv[6]);
	      int m=atoi(argv[7]);
	      //complete_graph(G,n);
	      random_graph(G,n,m,true,true,true);
	      randomGraph=true;
	      cout<<"Random graph with "<<n<<" vertices and "<<m<<" edges created"<<endl;
	      outfile<<"Random graph with "<<n<<" vertices and "<<m<<" edges created"<<endl;
	      outfile<<"Vertices: "<<G.number_of_nodes()<<" Edges: "<<G.number_of_edges()<<endl;	  
	    }
	} 
      else 
	{      
	  cout<<"The source of input graph is not valid!"<<endl;
	  cout<<"Use -r, -f or -fgml for the third parameter!"<<endl;	        
	  printUsage();
	}      
      sa_graph *gg = new sa_graph(&G);      
      if (PLANAR(G,0))
	{
	  cout<<"Input graph is planar graph"<<endl;
	}      
      else
	{
	  cout<<"Input graph is NOT planar graph"<<endl;      
	  cout<<"Vertices: "<<gg->getVertices()<<" Edges: "<<gg->getEdges()<<endl;

	  if (strcmp(argv[3], "-e")==0)
	    {
	      if (runs==0)
		{
		  outfile<<"Empty set initialization"<<endl;
		}

	      cout<<"Empty set  initialization"<<endl;	
	    }
	  else
	    {
	      cout<<"Unknown initialization type!"<<endl;
	      cout<<"Use -e for the initialization parameter!"<<endl;	  
	      printUsage();
	    }

	  //write parameters to result file
	  if (strcmp(argv[4], "-sa")==0)
	    {
	      if (runs==0)
		{
		  outfile<<"Simulated annealing algorithm"<<endl;
		  //cout<<"writing parameter file"<<endl;
		  outfile<<"PARAMETERS: ";
		  outfile<<" t0: ";		 		  
		  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;
		  outfile<<value<<" t1:";
		  
		  parameterFile >> txt;
		  parameterFile >> value;
		  outfile<<value<<" alpha:";
		  
		  parameterFile >> txt;
		  parameterFile >> value;
		  outfile<<value<<" i_l:";
	      
		  int loop;
		  parameterFile >> txt;
		  parameterFile >> loop;
		  outfile<<loop<<endl;		  
		  parameterFile.close();
		}

	      if (strcmp(argv[3], "-e")==0)
		{
		  outfile<<"INI_SOL: "<<gg->getCurrentSolution();
		  iniSolAverage=iniSolAverage+gg->getCurrentSolution();
		  if (argc==9 && strcmp(argv[7], "-t")==0)
		    {
		      cout<<"setting trage file..."<<endl;
		      outfile<<"Trace file: "<<argv[8];
		      gg->setTraceFileName(argv[8]);
		    }
		  gg->sa2();      
		  outfile<<" RES: "<<gg->getCurrentSolution();
		  solutionAverage=solutionAverage+gg->getCurrentSolution();		  
		  outfile<<"    foundTemperature: "<<gg->getFoundTemperature()<<endl;
		  
		  //gg->printSolution();
		  
		  if (gg->getCurrentSolution() > bestSolution)
		    bestSolution=gg->getCurrentSolution();		  
		}
	      else
		{
		  cout<<"Unknown algorithm type!"<<endl;
		  cout<<"Use -sa or -no for the fourth parameter!"<<endl;
		  printUsage();
		}
	    }
	}
      
      //don't save it more than once!
      if (randomGraph==true && runs==0)
	{
	  //it is good to save it to file (if target file is given!)
	  if (argc>8)
	    {
	      cout<<"graph file saved in file "<<argv[8]<<endl;
	      G.write_gml(argv[8]);             
	    }
	  else
	    cout<<"graph file not saved"<<endl;
	}  
      //if we use random graphs, 
      //we don't want to delete it between distinct runs!
      if (randomGraph!=true)
	{
	  delete gg;	  
	}
    }
  //now we are ready to save average results.  
  iniSolAverage=iniSolAverage/rounds;

  outfile<<"INI_SOL_AVE: "<<iniSolAverage;

  //cout<<"sol_total: "<<solutionAverage<<endl;
  
  if (strcmp(argv[4], "-no")!=0)
    {
      solutionAverage=solutionAverage/rounds;  
      outfile<<"  SOL_AVE: "<<solutionAverage<<endl;
    }

  outfile<<"BEST SOLUTION: "<<bestSolution<<endl;  

  return 0;
}