cn94.hpp

Go to the documentation of this file.

#ifndef _CN94_H
#define _CN94_H

#include <iostream>
#include <iomanip>
#include "properties.hpp"
#include "geometry.hpp"
#include "coloring.hpp"
#include "arak.hpp"
#include "coloring_mcmc.hpp"

namespace Arak {

  using namespace Geometry;

  class CN94Proposal : public ColoringProposal {

  protected:

    enum MoveType {
      INT_TRIANGLE_BIRTH = 0,     
      INT_TRIANGLE_DEATH,         
      RECOLOR,                    
      MOVE_INT_VERTEX,            
      MOVE_BD_VERTEX_ALONG_BD,    
      MOVE_BD_VERTEX_PAST_CORNER, 
      INT_VERTEX_BIRTH,           
      INT_VERTEX_DEATH,           
      BD_TRIANGLE_BIRTH,          
      BD_TRIANGLE_DEATH,          
      CORNER_CUT_BIRTH,           
      CORNER_CUT_DEATH,           
      INVALID_MOVE,               
      UNSPECIFIED_MOVE            
    };

    static const int numMoveTypes = 13;

    static const char* moveNames[numMoveTypes];
      
    unsigned long int numProposed[numMoveTypes];

    unsigned long int numAccepted[numMoveTypes];

    class InteriorTriangleBirth : public ColoringMove {

      friend class CN94Proposal;
    
    protected:

      Point u, v, w;

      Coloring::VertexHandle vh;

    public:

      InteriorTriangleBirth() {}

      void reset(const Point& u, const Point& v, const Point& w);

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    InteriorTriangleBirth itb;

    class InteriorTriangleDeath : public ColoringMove {

      friend class CN94Proposal;
    
    protected:

      const CN94Proposal& proposal;

      Coloring::VertexHandle vh;

      Point u, v, w;

      bool isShort;

    public:

      InteriorTriangleDeath(const CN94Proposal& proposal) 
  : proposal(proposal) {}

      void reset(Coloring::VertexHandle vertex, bool isShort);

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    InteriorTriangleDeath itd;

    class Recolor : public ColoringMove {

      friend class CN94Proposal;
      friend class ModifiedCN94Proposal;
    
    protected:

      Coloring::IntEdgeHandle edge1;

      Coloring::IntEdgeHandle edge2;

      bool joinSourceToSource;

      bool convex;

    public:

      Recolor() {}

      void reset(Coloring::IntEdgeHandle edge1, 
     Coloring::IntEdgeHandle edge2,
     bool joinSourceToSource,
     bool convex);

      bool isConvex() { return convex; }

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    Recolor rec;

    class MoveInteriorVertex : public ColoringMove {

      friend class CN94Proposal;
    
    protected:

      Coloring::VertexHandle vertex;

      Point oldLoc;

      Point newLoc;

    public:

      MoveInteriorVertex() {}

      void reset(Coloring::VertexHandle vertex, const Point& point);

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    MoveInteriorVertex miv;

    class MoveVertexAlongBdEdge : public ColoringMove {
    
      friend class CN94Proposal;
    
    protected:
    
      Coloring::VertexHandle vertex;
    
      Point oldLoc;

      Point newLoc;

    public:
    
      MoveVertexAlongBdEdge() { }
      
      void reset(Coloring::VertexHandle vertex, const Point& point);

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    MoveVertexAlongBdEdge mbb;

    class MoveBdVertexPastCorner : public ColoringMove {

      friend class CN94Proposal;
    
    protected:

      Coloring::BdEdgeHandle edge;

      Point oldLoc;

      Point newLoc;

    public:

      MoveBdVertexPastCorner() {}

      void reset(Coloring::BdEdgeHandle edge, const Point& point);

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    MoveBdVertexPastCorner mbc;

    class InteriorVertexBirth : public ColoringMove {

      friend class CN94Proposal;
    
    protected:
    
      Coloring::VertexHandle prevVertex;
    
      Coloring::VertexHandle nextVertex;

      Point point;

    public:

      void reset(Coloring::IntEdgeHandle edge, const Point& point);

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    InteriorVertexBirth ivb;

    class InteriorVertexDeath : public ColoringMove {

      friend class CN94Proposal;

    protected:

      const CN94Proposal& proposal;

      Coloring::VertexHandle prevVertex;

      Point point;

      double newEdgeLength;

    public:

      InteriorVertexDeath(const CN94Proposal& proposal) 
  : proposal(proposal) {}

      void reset(Coloring::VertexHandle vertex);

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    InteriorVertexDeath ivd;

    class BoundaryTriangleBirth : public ColoringMove {

      friend class CN94Proposal;
      friend class ModifiedCN94Proposal;
    
    protected:


      Coloring::BdEdgeHandle edge;

      Point u, v;

      Point w;

      Coloring::VertexHandle vh;


    public:

      BoundaryTriangleBirth() {}

      void reset(Coloring::BdEdgeHandle e,
     const Point& u, 
     const Point& v, 
     const Point& w);
 
      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    BoundaryTriangleBirth btb;

    class BoundaryTriangleDeath : public ColoringMove {

      friend class CN94Proposal;
      friend class ModifiedCN94Proposal;
    
    protected:

      Coloring::VertexHandle vh;

      Point up, vp;

      Point wp;

      Coloring::VertexHandle prevBoundaryVertex;

      Coloring::VertexHandle nextBoundaryVertex;

    public:

      BoundaryTriangleDeath() {}

      void reset(Coloring::VertexHandle vertex);

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    BoundaryTriangleDeath btd;

    class CornerCutBirth : public ColoringMove {

      friend class CN94Proposal;
    
    protected:

      Coloring::VertexHandle corner;

      Point u;

      Point v;

      Coloring::VertexHandle vh;

    public:

      CornerCutBirth() {}

      void reset(Coloring::VertexHandle corner, 
     const Point& u, const Point& v);
 
      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    CornerCutBirth ccb;

    class CornerCutDeath : public ColoringMove {

      friend class CN94Proposal;
    
    protected:

      Coloring::VertexHandle corner;

      Point u;

      Point v;

      Coloring::VertexHandle vh;

    public:

      CornerCutDeath() {}

      void reset(Coloring::VertexHandle vertex);

      virtual void execute(Coloring& c);

      virtual void undo(Coloring& c);

    };

    CornerCutDeath ccd;

    virtual void sampleInteriorTriangleBirth(const Coloring& state, 
               Arak::Util::Random& random);

    virtual void sampleInteriorDeath(const Coloring& state, 
             Arak::Util::Random& random,
             bool reversible = true);

    virtual void proposeBdTriangleDeath(const Coloring& state,
          Coloring::VertexHandle prevVertex,
          Coloring::VertexHandle vertex,
          Coloring::VertexHandle nextVertex,
          bool reversible = true);

    virtual void proposeIntVertexDeath(const Coloring& state,
               Coloring::VertexHandle prevVertex,
               Coloring::VertexHandle vertex,
               Coloring::VertexHandle nextVertex,
               bool reversible = true);

    virtual void proposeIntTriangleDeath(const Coloring& state,
           Coloring::VertexHandle prevVertex,
           Coloring::VertexHandle vertex,
           Coloring::VertexHandle nextVertex,
           bool reversible = true);

    virtual void sampleRecolor(const Coloring& state, 
             Arak::Util::Random& random);

    virtual void sampleMoveBdVertexPastCorner(const Coloring& state, 
                Arak::Util::Random& random);

    virtual void sampleInteriorVertexBirth(const Coloring& state, 
             Arak::Util::Random& random);

    virtual void sampleMoveInteriorVertex(const Coloring& state, 
            Arak::Util::Random& random);

    virtual void sampleMoveVertexAlongBd(const Coloring& state, 
           Arak::Util::Random& random);

    virtual void sampleBoundaryTriangleBirth(const Coloring& state, 
               Arak::Util::Random& random);

    virtual void sampleBoundaryTriangleDeath(const Coloring& state, 
               Arak::Util::Random& random,
               bool reversible = true);

    virtual void sampleCornerCutBirth(const Coloring& state, 
              Arak::Util::Random& random);

    virtual void sampleCornerCutDeath(const Coloring& state, 
              Arak::Util::Random& random);

    double ZETA_BD_NOT_MR;

    double ZETA_MOVE_NOT_RECOLOR;

    double ZETA_BIRTH_NOT_DEATH;

    double ZETA_INT_NOT_BOUNDARY;

    double ZETA_BOUND_NOT_CORNER;

    double ZETA_IB_VERTEX_NOT_TRIANGLE;

    MoveType curMoveType;

    double castingBoxRadius;

    Point sampleInCastingBox(const Point& p,
           Arak::Util::Random& random) const;

    bool inCastingBox(const Point& p, const Point& q) const;

    double castingArea() const { 
      return 4.0 * castingBoxRadius * castingBoxRadius; 
    }

  public:
  
    CN94Proposal(const Arak::Util::PropertyMap& props);

    virtual ~CN94Proposal();

    virtual void sample(const Coloring& state, 
      Arak::Util::Random& random,
      bool reversible = true);

    virtual ColoringMove& move();

    virtual double ll(const Coloring& c);
  
    virtual double rll(const Coloring& c);

    virtual void result(bool accepted) {
      if (accepted) numAccepted[int(curMoveType)]++;
    }

    template<typename charT, typename traits>
    void writeStatistics(std::basic_ostream<charT,traits>& out) const {
      double numProposals = 0.0;
      for (int i = 0; i < numMoveTypes; i++)
  numProposals += double(numProposed[i]);
      out << "Clifford & Nicholls (1994) proposal statistics:" << std::endl;
      out << std::setw(28) << "move type" 
    << std::setw(12) << "% proposed" 
    << std::setw(12) << "% accepted" 
    << std::endl;
      out << std::setw(28) << "----------------------------" 
    << std::setw(12) << "-----------" 
    << std::setw(12) << "-----------" 
    << std::endl;
      out.precision(3);
      for (int i = 0; i < numMoveTypes; i++) {
  out << std::setw(28) << moveNames[i]
      << std::setw(12) 
      << 100.0 * (double(numProposed[i]) / numProposals) 
      << std::setw(12) 
      << 100.0 * (double(numAccepted[i]) / double(numProposed[i])) 
      << std::endl;
      }
    }

  }; // End of class: Arak::CN94Proposal

  class ModifiedCN94Proposal : public CN94Proposal {

  protected:

    double ZETA_LOCAL_NOT_GLOBAL_RECOLOR;

    virtual void sampleRecolor(const Coloring& state, 
             Arak::Util::Random& random);

    double ZETA_LOCAL_NOT_GLOBAL_BD_TRI_BIRTH;

    virtual void sampleBoundaryTriangleBirth(const Coloring& state, 
               Arak::Util::Random& random);

    class SlideInteriorVertex : public CN94Proposal::MoveInteriorVertex {

      friend class ModifiedCN94Proposal;
    
    protected:

      bool next;

    public:

      SlideInteriorVertex() {}

      void reset(Coloring::VertexHandle vertex, bool next, 
     const Point& point) {
  CN94Proposal::MoveInteriorVertex::reset(vertex, point);
  this->next = next;
      }

    };

    SlideInteriorVertex siv;

    double ZETA_SLIDE_NOT_MOVE_INT_VERTEX;

    bool slide_not_move;

    virtual void sampleSlideInteriorVertex(const Coloring& state, 
             Arak::Util::Random& random);

    virtual void sampleMoveInteriorVertex(const Coloring& state, 
            Arak::Util::Random& random);

  public:

    ModifiedCN94Proposal(const Arak::Util::PropertyMap& props);

    virtual ~ModifiedCN94Proposal() { }

    virtual ColoringMove& move() {
      if ((curMoveType == MOVE_INT_VERTEX) && slide_not_move)
  return siv;
      else return CN94Proposal::move();
    }

    virtual double ll(const Coloring& c);
  
    virtual double rll(const Coloring& c);
  };

} // End of namespace: Arak

#endif

---