Index   Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  
Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes

GoStaticSafetySolver Class Reference

Common algorithm for static safety. More...

#include <GoStaticSafetySolver.h>

Inheritance diagram for GoStaticSafetySolver:
Inheritance graph
[legend]

List of all members.

Public Member Functions

 GoStaticSafetySolver (const GoBoard &board, GoRegionBoard *regions=0)
 Constructor.
virtual ~GoStaticSafetySolver ()
 Destructor, deallocates if there are own regions.
Accessors

const GoBoardBoard () const
 our board
Forwarding accessors for GoRegionBoard

virtual bool UpToDate () const
 See GoRegionBoard::UpToDate.
const GoRegionBoardRegions () const
 our regions

Protected Member Functions

GoRegionBoardRegions ()
 our regions
virtual void FindTestSets (SgVectorOf< SgVectorOf< GoBlock > > *sets, SgBlackWhite color) const
 Main step of Benson's algorithm.
virtual void FindClosure (SgVectorOf< GoBlock > *blocks) const
 Compute closure of blocks set for Benson's algorithm.
virtual void GenBlocksRegions ()
 Compute all GoBlock's and GoRegion's on board.
virtual bool RegionHealthyForBlock (const GoRegion &r, const GoBlock &b) const
 Is r healthy for b? Implements Benson, override for better tests Benson's classic healthyness test: all empty points of region must be liberties of the block.
virtual void FindSafePoints (SgBWSet *safe)
 Main function, compute all safe points on board.
virtual void FindHealthy ()
 Find healthy regions for block, calls RegionHealthyForBlock.
void TestAlive (SgVectorOf< GoBlock > *blocks, SgBWSet *safe, SgBlackWhite color)
 Test if list of Benson blocks forms a living group.
void TestAdjacent (SgVectorOf< GoRegion > *regions, const SgVectorOf< GoBlock > &blocks) const
 Reduce regions: keep only if completely surrounded by blocks.

Private Member Functions

 GoStaticSafetySolver (const GoStaticSafetySolver &)
 not implemented
GoStaticSafetySolveroperator= (const GoStaticSafetySolver &)
 not implemented

Private Attributes

const GoBoardm_board
 The board we are computing on.
GoRegionBoardm_regions
 Contains the GoRegion's and GoBlock's we are using.
bool m_allocRegion
 Did we allocate the GoRegionBoard or did the user supply it?

Detailed Description

Common algorithm for static safety.

The algorithm is used to implement both Benson's algorithm for unconditional safety and a solver using the extended 1-vitality and 2-vitality definitions from Martin Mueller's thesis [Mueller 95, p. 62-63] and from [Mueller 97b].

Definition at line 20 of file GoStaticSafetySolver.h.


Constructor & Destructor Documentation

GoStaticSafetySolver::GoStaticSafetySolver ( const GoBoard board,
GoRegionBoard regions = 0 
)

Constructor.

If regions = 0, allocates own.

Definition at line 18 of file GoStaticSafetySolver.cpp.

References m_regions.

GoStaticSafetySolver::~GoStaticSafetySolver (  )  [virtual]

Destructor, deallocates if there are own regions.

Definition at line 29 of file GoStaticSafetySolver.cpp.

References m_allocRegion, and m_regions.

GoStaticSafetySolver::GoStaticSafetySolver ( const GoStaticSafetySolver  )  [private]

not implemented


Member Function Documentation

const GoBoard & GoStaticSafetySolver::Board (  )  const
void GoStaticSafetySolver::FindClosure ( SgVectorOf< GoBlock > *  blocks  )  const [protected, virtual]

Compute closure of blocks set for Benson's algorithm.

Expand set of blocks until all blocks adjacent to all adjacent regions are in set. see [Benson] for explanation.

Reimplemented in GoSafetySolver.

Definition at line 161 of file GoStaticSafetySolver.cpp.

References SgVectorOf< T >::Back(), GoRegion::Blocks(), SgVectorOf< T >::Contains(), GoBlock::Healthy(), SgVectorOf< T >::NonEmpty(), SgVectorOf< T >::PopBack(), and SgVectorOf< T >::PushBack().

Referenced by FindTestSets().

void GoStaticSafetySolver::FindHealthy (  )  [protected, virtual]

Find healthy regions for block, calls RegionHealthyForBlock.

Reimplemented in GoSafetySolver.

Definition at line 58 of file GoStaticSafetySolver.cpp.

References GoRegion::Blocks(), RegionHealthyForBlock(), Regions(), and GoRegionBoard::SetComputedHealthy().

Referenced by FindSafePoints().

void GoStaticSafetySolver::FindSafePoints ( SgBWSet safe  )  [protected, virtual]

Main function, compute all safe points on board.

Reimplemented in GoBensonSolver, and GoSafetySolver.

Definition at line 206 of file GoStaticSafetySolver.cpp.

References FindHealthy(), FindTestSets(), GenBlocksRegions(), GO_REGION_SAFE, Regions(), GoRegionBoard::SetComputedFlagForAll(), and TestAlive().

void GoStaticSafetySolver::FindTestSets ( SgVectorOf< SgVectorOf< GoBlock > > *  sets,
SgBlackWhite  color 
) const [protected, virtual]

Main step of Benson's algorithm.

Reimplemented in GoSafetySolver.

Definition at line 184 of file GoStaticSafetySolver.cpp.

References FindClosure(), SgVectorOf< T >::PushBack(), Regions(), and SG_ASSERT.

Referenced by FindSafePoints().

void GoStaticSafetySolver::GenBlocksRegions (  )  [protected, virtual]

Compute all GoBlock's and GoRegion's on board.

Reimplemented in GoSafetySolver.

Definition at line 47 of file GoStaticSafetySolver.cpp.

References GoRegionBoard::GenBlocksRegions(), Regions(), GoRegionBoard::ReInitializeBlocksRegions(), and UpToDate().

Referenced by FindSafePoints().

GoStaticSafetySolver& GoStaticSafetySolver::operator= ( const GoStaticSafetySolver  )  [private]

not implemented

bool GoStaticSafetySolver::RegionHealthyForBlock ( const GoRegion r,
const GoBlock b 
) const [protected, virtual]

Is r healthy for b? Implements Benson, override for better tests Benson's classic healthyness test: all empty points of region must be liberties of the block.

Reimplemented in GoSafetySolver.

Definition at line 36 of file GoStaticSafetySolver.cpp.

References GoBlock::AllEmptyAreLiberties(), and GoRegion::Points().

Referenced by FindHealthy().

GoRegionBoard * GoStaticSafetySolver::Regions (  )  [protected]

our regions

Definition at line 114 of file GoStaticSafetySolver.h.

References m_regions, and SG_ASSERT.

const GoRegionBoard * GoStaticSafetySolver::Regions (  )  const
void GoStaticSafetySolver::TestAdjacent ( SgVectorOf< GoRegion > *  regions,
const SgVectorOf< GoBlock > &  blocks 
) const [protected]

Reduce regions: keep only if completely surrounded by blocks.

Definition at line 81 of file GoStaticSafetySolver.cpp.

References SgVectorOf< T >::PushBack().

Referenced by TestAlive().

void GoStaticSafetySolver::TestAlive ( SgVectorOf< GoBlock > *  blocks,
SgBWSet safe,
SgBlackWhite  color 
) [protected]

Test if list of Benson blocks forms a living group.

Each block must have a sure liberty count of at least 2. A region provides one sure liberty if it is healthy and its boundary consists only of blocks in the list.

Definition at line 91 of file GoStaticSafetySolver.cpp.

References GoSafetyUtil::AddToSafe(), SgVectorOf< T >::Clear(), GoBlock::Color(), SgVectorOf< T >::Contains(), SgVectorOf< T >::Exclude(), SgVectorOf< T >::Front(), m_board, SgVectorOf< T >::MinLength(), SgVectorOf< T >::NonEmpty(), SgVectorOf< T >::PushBack(), Regions(), SG_ASSERT, SG_DEBUG_ONLY, and TestAdjacent().

Referenced by FindSafePoints().

bool GoStaticSafetySolver::UpToDate (  )  const [virtual]

See GoRegionBoard::UpToDate.

Reimplemented in GoSafetySolver.

Definition at line 42 of file GoStaticSafetySolver.cpp.

References Regions(), and GoRegionBoard::UpToDate().

Referenced by GenBlocksRegions().


Member Data Documentation

Did we allocate the GoRegionBoard or did the user supply it?

Definition at line 99 of file GoStaticSafetySolver.h.

Referenced by ~GoStaticSafetySolver().

The board we are computing on.

Definition at line 93 of file GoStaticSafetySolver.h.

Referenced by Board(), and TestAlive().

Contains the GoRegion's and GoBlock's we are using.

Definition at line 96 of file GoStaticSafetySolver.h.

Referenced by GoStaticSafetySolver(), Regions(), and ~GoStaticSafetySolver().


The documentation for this class was generated from the following files:


Sun Mar 13 2011 Doxygen 1.7.1