problem.cc

linux下的一个分组遗传算法

//
// problem.cc - Reads in Graph Coloring Problems
//
// author: J.K.van der Hauw
// edited by: J.I.v.Hemert
// last update: 12-11-1997
//
// This file implements the class Problem. It has graph intances 
// as input, generated by a external program called generate. The
// internal representation is an adjecencylist.
//

#include "problem.h"

void ProblemC::DeleteAdjlist() {

  int i;
  Link *temp;

  for (i = 0; i < nrofnodes; i++)
    while (gradjl[i]) {
      temp = gradjl[i]->nextptr;
      delete gradjl[i];
      gradjl[i] = temp;
    }

} // ProblemC::DeleteAdjlist()


void ProblemC::PrintAdjList() {
 
  int i;
  Link *temp;

  for (i = 0; i < nrofnodes; i++) {
    cerr << "buren van node " << i << ": ";
    temp = gradjl[i];
    while (temp) {
      cerr << temp->nodenr << " ";
      temp = temp->nextptr;
    }
    cerr << endl;
  }
} // ProblemC::DeleteAdjList()


void ProblemC::CreateProblem(int n, double p, int s, char * problemdir, char * graphtype, int nrofcolors) {
 
  int i, l;
  char string[MAXSTRINGLENGTH];
  ofstream output;
  const int DECIMALS = 3;
  int intgraphtype;
  char * hostname;

  hostname = new char [22];
  if (gethostname (hostname, 20) != 0)
    strcpy (hostname, "unknown");
  strcpy (PROBLEMDIR, problemdir);
  sprintf (ProblemFilename, "%li", (long) getpid ());
  strcat(ProblemFilename, ".");
  strcat(ProblemFilename, hostname);
  strcat(ProblemFilename, ".");
  strcat(ProblemFilename, graphtype);
  l = strlen(ProblemFilename);
  ProblemFilename[l++] = 'n';
  for (i = (int) log10((double) n); i >= 0; i--)
    ProblemFilename[l++] = '0' + (n % ((int) pow(10,i+1))) / ((int) pow(10, i));
  ProblemFilename[l++] = 'p';
  if (p < 1.0)
    ProblemFilename[l++] = '0';
  else
    ProblemFilename[l++] = '1';
  ProblemFilename[l++] = '.';

  for (i = 1; i <= DECIMALS; i++)
    ProblemFilename[l++] = '0' + ((int)(pow(10, i)*p+pow(10,-DECIMALS-1))) % 10;
  ProblemFilename[l++] = 's';
  ProblemFilename[l++] = '0' + s / 10;
  ProblemFilename[l++] = '0' + s % 10;
  ProblemFilename[l++] = (char) NULL;

  strcpy(string, PROBLEMDIR);
  strcat(string, ProblemFilename);
  strcat(string,"ingen");

  intgraphtype = 0;
  if (strcmp("equi", graphtype) == 0)
	  intgraphtype = 2;
  if (strcmp("flat", graphtype) == 0)
	  intgraphtype = 6;
  if (strcmp("arbi", graphtype) == 0)
	  intgraphtype = 3;

  if (intgraphtype == 0)
  {
	  cerr << "Error: no graphtype specified (equi, flat or arbi)" <<endl;
	  exit (2);
  }

  output.open(string);
  output << 0 << endl;				// ascii code
  output << s << endl;				// seednr s
  output << intgraphtype << endl;	// equipartite
  output << n << endl;				// nr of nodes
  output << nrofcolors << endl;		// k-coloring
  if (intgraphtype == 3)
	  output <<  0 << endl;			// variability

  if((intgraphtype == 2) || (intgraphtype == 3))
	  output << 1 << endl;			// IID-edge probability

  output << p << endl;				// edge probabilty p
  if (intgraphtype == 6)
	  output << 0 << endl;			// flatness

  output << 0 << endl;				// no cheats
  output.close();

  strcpy(string, "generator ");
  strcat(string, PROBLEMDIR);
  strcat (string, ProblemFilename);
  strcat(string, " < ");
  strcat(string, PROBLEMDIR);
  strcat(string, ProblemFilename);
  strcat(string, "ingen > ");
  strcat(string, PROBLEMDIR);
  strcat(string, ProblemFilename);
  strcat(string, "NULL");
  system(string);

  free (hostname);
} // ProblemC::CreateProblem()


void ProblemC::RemoveProblem() {

  char string[MAXSTRINGLENGTH];

  strcpy(string, "rm ");
  strcat(string, PROBLEMDIR);
  strcat(string, ProblemFilename);
  system(string);
  strcpy(string, "rm ");
  strcat(string, PROBLEMDIR);
  strcat(string, ProblemFilename);
  strcat(string, "ingen");
  system(string);

  strcpy(string, "rm ");
  strcat(string, PROBLEMDIR);
  strcat(string, ProblemFilename);
  strcat(string, "NULL");
  system(string);

  DeleteAdjlist();

} // ProblemC::RemoveProblem()


int ProblemC::ReadProblem() {

  int nrofgenes = 0;
  const int MAXLEN = 250;
  ifstream input;
  int n1, n2, i;
  char kar, string[MAXLEN];
  Link  *temp;

  strcpy (string, PROBLEMDIR);
  strcat (string, ProblemFilename);
  input.open(string);

  //cerr << "# Problem \""<< string << "\" ";
  // Find line starting with p, which includes the nr of nodes
  input >> kar;
  while (kar != 'p') {
    input.getline(string, MAXLEN);
    input >> kar;
  }
 
  input >> string;
  input >> nrofnodes;
  nrofgenes = nrofnodes;
  input.getline(string, MAXLEN);

  // Initialize edges of graph at non-existent
  for (i = 0; i < nrofgenes; i++) {
    gradjl[i] = NULL;
    nrofneighbors[i] = 0;
    weight[i] = 1;
  }
 
  // Find first line starting with an 'e' to get the edges
  input >> kar;
  while (kar != 'e') {
    input.getline(string, MAXLEN);
    input >> kar;
  }
  while (!input.eof()) {
    input >> n1 >> n2;
    // cerr << "Edge (" << n1 << "," << n2 << ")" << endl;
    temp = gradjl[n1-1];
    gradjl[n1-1] = new Link;
    gradjl[n1-1]->nodenr = n2-1;
    gradjl[n1-1]->weight = 1;
    gradjl[n1-1]->nextptr = temp;
    nrofneighbors[n1-1]++;
    temp = gradjl[n2-1];
    gradjl[n2-1] = new Link;
    gradjl[n2-1]->nodenr = n1-1;
    gradjl[n2-1]->weight = 1;
    gradjl[n2-1]->nextptr = temp;
    nrofneighbors[n2-1]++;
    input >> kar;
  }

  input.close();

  //cerr << "read." << endl;
  //cerr << "# " << nrofgenes << " nodes" << endl;

  return (nrofgenes);
} // ProblemC::ReadProblem()


ProblemC problem;