Generator.cpp

Go to the documentation of this file.

// MIT License
//
// Copyright (c) 2019 Ian Parberry
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

#include "Generator.h"
#include "Random.h"
#include "Defines.h"
#include "Timer.h"
#include "Board.h"
#include "DivideAndConquer.h"
#include "ConcentricBraid.h"
#include "FourCover.h"


CGenerator::CGenerator(){ 
} //constructor


CGenerator::CGenerator(int w, int h):
  m_nWidth(w), m_nHeight(h), m_nSize(w*h){ 
} //constructor


CGenerator::CGenerator(int n): CGenerator(n, n){ 
} //constructor

// Code for Task::Generate

#pragma region Task::Generate


void CGenerator::Generate(const CTourneyDesc& t, int nThreads){ 
  const GeneratorType gentype = t.m_eGenerator;
  const CycleType cycletype = t.m_eCycle;

   //deterministic generators 

  if(gentype == GeneratorType::DivideAndConquer){ 
    CBoard b(m_nWidth, m_nHeight); //board for the tour
    CDivideAndConquer().Generate(b, cycletype); //generate it
    if(t.m_bObfuscate)b.Obfuscate(); //obfuscate if necessary

    std::string s = MakeFileNameBase(t, b.GetWidth()); //file name

    b.Save(s); //save to text file
    b.SaveToSVG(s); //save to SVG file
  } //if

  else if(gentype == GeneratorType::ConcentricBraid){ 
    CBoard b(m_nWidth, m_nHeight); //board for the tour
    CConcentricBraid().Generate(b); //generate it
    if(cycletype == CycleType::TourFromTourney)b.JoinUntilTour(); //make tour
    if(t.m_bObfuscate)b.Obfuscate(); //obfuscate if necessary

    std::string s = MakeFileNameBase(t, b.GetWidth()); //save file name
    b.Save(s); //save to text file
    b.SaveToSVG(s); //save to SVG file
  } //if

  else if(gentype == GeneratorType::FourCover){
    CBoard b(m_nWidth, m_nHeight); //board for the tour
    CFourCover().Generate(b); //generate it
    if(cycletype == CycleType::TourFromTourney)b.JoinUntilTour(); //make tour
    if(t.m_bObfuscate)b.Obfuscate(); //obfuscate if necessary

    std::string s = MakeFileNameBase(t, b.GetWidth()); //save file name
    b.Save(s); //save to text file
    b.SaveToSVG(s); //save to SVG file
  } //if

  //probabilistic generators

  else{ 
    for(int i=0; i<nThreads; i++) //queue up search requests
      m_cSearchRequest.push(CSearchRequest(t, m_nWidth, m_nHeight, ::rand()));  
  
    for(int i=0; i<nThreads; i++) //launch the search threads
      m_vecThreadList.push_back(std::thread((CSearchThread())));

    //start timing CPU and elapsed time

    CTimer Timer;
    Timer.Start();
    printf("Starting %d theads at: %s", nThreads, Timer.GetCurrentDateAndTime());

    //wait for all search threads to terminate
  
    std::for_each(m_vecThreadList.begin(), m_vecThreadList.end(), 
      std::mem_fn(&std::thread::join));

    Timer.Finish(); //stop the timer
    m_vecThreadList.clear(); //clear the thread list for next use

    //process results of search

    CSearchResult result; //current search result

    const int nResults = (int)m_cSearchResult.size();

    if(nResults == 0)
      printf("\n**** Error: Search failed, nothing to print.\n");

    if(m_cSearchResult.pop(result)){ //get current search result
      CBoard& b = *(result.m_pBoard);
      std::string s = MakeFileNameBase(result.m_cTourneyDesc, b.GetWidth());

      b.Save(s); //save tour to text file
      b.SaveToSVG(s); //save to SVG file

      delete result.m_pBoard;
    } //if
  } //else
} //Generate

#pragma endregion generation task

// Code for Task::Measure

#pragma region Task::Measure


void CGenerator::Measure(const CTourneyDesc& t, int nThreads, int n){ 
  //queue up search requests

  for(int i=0; i<n; i++){
    CSearchRequest request(t, m_nWidth, m_nHeight, ::rand());
    request.m_bDiscard = true; //we're measuring stats, so throw them away
    m_cSearchRequest.push(request); //submit request
  } //for

  //start timing CPU and elapsed time

  CTimer Timer;
  Timer.Start();

  printf("Starting %d theads at: %s", nThreads, Timer.GetCurrentDateAndTime());

  //launch the search threads
  
  for(int i=0; i<nThreads; i++)
    m_vecThreadList.push_back(std::thread((CSearchThread())));

  //wait for all search threads to terminate
  
  std::for_each(m_vecThreadList.begin(), m_vecThreadList.end(), 
    std::mem_fn(&std::thread::join));

  Timer.Finish();
  m_vecThreadList.clear(); //clear the thread list for next use

  //process the measurements that were made by the threads

  //you can't iterate through std::queue, so transfer results to an std::vector

  std::vector<CSearchResult> results; //result list

  CSearchResult r; //current search result

  while(m_cSearchResult.pop(r)) //get current search result
    results.push_back(r);

  //now process the results

  double fSingleMove[8] = {0}; //single move count
  double fRelativeMove[8] = {0}; //relative move count
  
  double fSingleMean[8] = {0}; //single move observed mean
  double fRelativeMean[8] = {0}; //relative move observed mean 
    
  double fSingleStdev[8] = {0}; //single move standard deviation
  double fRelativeStdev[8] = {0}; //relative move standard deviation


    for(CSearchResult r: results)
    for(int i=0; i<8; i++){
      fSingleMove[i] += (double)r.m_nSingleMove[i];
      fRelativeMove[i] += (double)r.m_nRelativeMove[i];
    } //for

  for(int i=0; i<8; i++){
    fSingleMove[i] /= (double)m_nSize;
    fRelativeMove[i] /= (double)m_nSize;
  } //for

  //compute observed mean
  
  for(int i=0; i<8; i++){
    fSingleMean[i] = fSingleMove[i]/(double)n;
    fRelativeMean[i] = fRelativeMove[i]/(double)n;
  } //for

  //compute observed standard deviation

  const double denom = (double)m_nSize; //denominator
  
  for(CSearchResult r: results){
    for(int i=0; i<8; i++){
      fSingleStdev[i] += sqr((double)r.m_nSingleMove[i]/denom - fSingleMean[i]);
      fRelativeStdev[i] += sqr((double)r.m_nRelativeMove[i]/denom - fRelativeMean[i]);
    } //for
  } //for
  
  if(n > 1){
    const double denom = (double)n - 1; //denominator for standard deviation

    for(int i=0; i<8; i++){
      fSingleStdev[i] = sqrt(fSingleStdev[i]/denom);
      fRelativeStdev[i] = sqrt(fRelativeStdev[i]/denom);
    } //for
  } //if

  //write mean and standard deviation to a file
  
  std::string strFileName = "Stats" + MakeFileNameBase(t, m_nWidth) //file name
    + "-" + std::to_string(n) + ".txt";

  FILE* output = fopen(strFileName.c_str(), "wt"); //open file

  if(output != nullptr){ //success
    fprintf(output, "Single\n");
    fprintf(output, "Mean\t");  OutputStat(output, fSingleMean);
    fprintf(output, "Stdev\t"); OutputStat(output, fSingleStdev);
    fprintf(output, "\n");
    
    fprintf(output, "Relative\n");    
    fprintf(output, "Mean\t");  OutputStat(output, fRelativeMean);    
    fprintf(output, "Stdev\t"); OutputStat(output, fRelativeStdev);

    fclose(output); //close file
  } //if
} //Measure


void CGenerator::OutputStat(FILE* output, double a[8]){
  assert(output != 0); //safety
  fprintf(output, "%0.4f", a[0]);
  for(int i=1; i<8; i++)
    fprintf(output, "\t%0.4f", a[i]);
  fprintf(output, "\n");
} //OutputStat

#pragma endregion Task::Measure

// Code for Task::Time

#pragma region Task::Time


void CGenerator::Time(const CTourneyDesc& t, int nThreads, int n){
  //queue up search requests

  for(int i=0; i<n; i++){
    CSearchRequest request(t, m_nWidth, m_nHeight, ::rand());
    request.m_bDiscard = true;
    m_cSearchRequest.push(request);
  } //for

  //start timing CPU and elapsed time

  CTimer Timer;
  Timer.Start();

  //launch the search threads
  
  for(int i=0; i<nThreads; i++)
    m_vecThreadList.push_back(std::thread((CSearchThread())));

  //wait for all search threads to terminate
  
  std::for_each(m_vecThreadList.begin(), m_vecThreadList.end(), 
    std::mem_fn(&std::thread::join));
  
  m_vecThreadList.clear(); //clear the thread list for next use
  
  //append cpu and elapsed time to a file

  std::string strFileName = "Time" + MakeFileNameBase(t);
  strFileName += "-" + std::to_string(n) + ".txt";

  FILE* output = fopen(strFileName.c_str(), "at");

  if(output != nullptr){
    OutputTimes(output, Timer.GetCPUTime(), Timer.GetElapsedTime());
    fclose(output);
  } //if
} //Time


void CGenerator::OutputTimes(FILE* output, float fCpu, float fElapsed){
  assert(output != 0); //safety

  if(output != nullptr)
    fprintf(output, "%d\t%0.2f\t%0.2f\n", m_nWidth, fCpu, fElapsed);
} //OutputTimes

#pragma endregion Task::Time