HomologyEngines

Files
file	algstruct.h
	This file defines an algebraic data structure which is used to store the information about computed homology groups.
file	cubfiles.h
	This file defines various types of cubical sets whose homology can be computed by homology engines.
file	cubiset.h
	This file defines a very simple interface to manipulating a full cubical set represented as a bitmap for the purpose of homology computation.
file	engines.h
	This file defines several engines for the homology computation of cubical sets.
file	homology.h
	This file defines a top-level interface to a homology computation procedure of full cubical sets represented in terms of a bitmap.

Namespaces
namespace	chomp
	This namespace contains the entire CHomP library interface.

Classes
class	CubicalSet
	This class stores a full cubical set and implements some basic operations on such a set, like adding or removing cubes with given coordinates. More...

Functions
void	ComputeBettiNumbers (const CubicalSet &s, int *result, const char *engine=0, bool quiet=false)
	Computes the Betti numbers of a full cubical set represented by an object of the class "CubicalSet". More...
void	ComputeBettiNumbers (const void *buffer, int *sizes, int dim, int *result, const char *engine=0, const int *wrapping=0, bool quiet=false)
	Computes the Betti numbers of the given set of full cubes encoded in a binary bitmap. More...
	CubicalSet::CubicalSet (const int *left_coords, const int *right_coords, int dim=EMBEDDING_DIM, const int *space_wrapping=0)
	The only constructor allowed: Creates an empty cubical bitmap of the given size. More...
	CubicalSet::~CubicalSet ()
	The destructor. More...
	CubicalSet::CubicalSet (const CubicalSet &c)
	The copy constructor. More...
CubicalSet &	CubicalSet::operator= (const CubicalSet &c)
	The assignment operator. More...
int	CubicalSet::ByteOffset (const int *coords) const
	Computes the right word offset in the buffer. More...
int	CubicalSet::BitMask (const int *coords) const
	Computes the mask for the bit in the right word. More...
bool	CubicalSet::Inside (const int *coords)
	Verifies whether the cube is within the bounding box. More...
int	CubicalSet::Add (const int *coords)
	Adds a cube to the set unless the cube is outside the box. More...
int	CubicalSet::Delete (const int *coords)
	Deletes a cube from the set. More...
bool	CubicalSet::Contains (const int *coords) const
	Verifies whether the given cube is contained in the cubical set. More...
void	CubicalSet::Clear ()
	Clears the bitmap and makes the cubical set empty. More...
void	CubicalSet::ComputeBettiNumbers (int *result, const char *engine=0, bool quiet=false) const
	Computes the Betti numbers of the cubical set. More...

Variables
ofstreamcout	fcout
	An output stream defined by M. Mrozek in the CAPD library. More...

Detailed Description

Function Documentation

Add()

int CubicalSet::Add ( const int *  coords )

inline

Adds a cube to the set unless the cube is outside the box.

Returns 0 if the cube is within the box or -1 otherwise.

Definition at line 235 of file cubiset.h.

{
        if (!Inside (coords))
                return -1;
        buffer [ByteOffset (coords)] |= BitMask (coords);
        return 0;
} /* CubicalSet::Add */

References CubicalSet::BitMask(), CubicalSet::buffer, CubicalSet::ByteOffset(), and CubicalSet::Inside().

BitMask()

int CubicalSet::BitMask ( const int *  coords ) const

inlineprivate

Computes the mask for the bit in the right word.

Definition at line 218 of file cubiset.h.

{
        return 1 << ((coords [0] - minimal [0]) & 0x07);
} /* CubicalSet::BitMask */

References CubicalSet::minimal.

Referenced by CubicalSet::Add(), CubicalSet::Contains(), and CubicalSet::Delete().

ByteOffset()

int CubicalSet::ByteOffset ( const int *  coords ) const

inlineprivate

Computes the right word offset in the buffer.

Definition at line 206 of file cubiset.h.

{
        int offset = (coords [0] - minimal [0]) >> 3;
        int multiply = ((sizes [0] + 31) >> 5) << 2;
        for (int i = 1; i < dim; ++ i)
        {
                offset += multiply * (coords [i] - minimal [i]);
                multiply *= sizes [i];
        }
        return offset;
} /* CubicalSet::ByteOffset */

References CubicalSet::dim, CubicalSet::minimal, and CubicalSet::sizes.

Referenced by CubicalSet::Add(), CubicalSet::Contains(), and CubicalSet::Delete().

Clear()

void CubicalSet::Clear ( )

inline

Clears the bitmap and makes the cubical set empty.

Definition at line 256 of file cubiset.h.

{
        std::memset (buffer, 0, bufsize);
        return;
} /* CubicalSet::Clear */

References CubicalSet::buffer, and CubicalSet::bufsize.

ComputeBettiNumbers() [1/3]

void ComputeBettiNumbers ( const CubicalSet &  s, int *  result, const char *  engine = 0, bool  quiet = false  )

inline

Computes the Betti numbers of a full cubical set represented by an object of the class "CubicalSet".

Definition at line 272 of file cubiset.h.

{
        s. ComputeBettiNumbers (result, engine, quiet);
        return;
} /* ComputeBettiNumbers */

References ComputeBettiNumbers().

Referenced by ComputeBettiNumbers().

ComputeBettiNumbers() [2/3]

void ComputeBettiNumbers ( const void *  buffer, int *  sizes, int  dim, int *  result, const char *  engine = 0, const int *  wrapping = 0, bool  quiet = false  )

inline

Computes the Betti numbers of the given set of full cubes encoded in a binary bitmap.

Parameters

buffer	- a buffer that contains the bitmap which defines the cubes; each byte stores 8 subsequent positions, with lower bits corresponding to cubes placed to the left from the higher bits; the width of each line must be a multiple of 4 bytes (if the number of cubes is less than that, then the lines must be padded with zeros) - this is required by the MM* engines; the first line corresponds to pixels with the coordinates (0,0,0,...,0), (1,0,0,...,0), ..., (n,0,0,...,0); the next line in the bitmap corresponds to the pixels (0,1,0,...,0), ..., (n,1,0,...,0), etc.
sizes	- a table of the sizes of the bitmap in each direction,
dim	- the space dimension,
result	- a table into which the result is written; its size must be at least (dim + 1),
engine	- the name of a homology engine to choose; the engine is automatically selected if this is zero
wrapping	- space wrapping in each direction (0 = no wrapping)
quiet	- true = the function should display no messages to the standard output stream; false = show a lot of messages

Definition at line 63 of file homology.h.

{
        using namespace chomp::homology;
        // turn off screen output if requested to
        bool soutput = sout. show;
        bool coutput = scon. show;
        if (quiet)
        {
                sout. show = false;
                scon. show = false;
                fcout. turnOff ();
        }
        else
                fcout. turnOn ();
 
        // create a corresponding set of cubes
        chomp::homengin::cubitmap X (reinterpret_cast<const char *> (buffer),
                sizes, dim);
 
        // set the space wrapping
        if (wrapping)
                X. setwrapping (wrapping, dim);
 
        // find the best engine to use for the homology computation
        const chomp::homengin::engine *e;
        if (!engine)
                e = chomp::homengin::engine::find (&X);
 
        // another possibility: find the engine with the given name
        else
                e = chomp::homengin::engine::find (engine);
 
        // compute the homology of the set of cubes
        chomp::homengin::algstruct<chomp::homology::integer> hom;
        e -> homology (X, hom);
        sout << "The computed homology is " << hom << ".\n";
 
        // fill in the resulting table of Betti numbers
        int levels = hom. countLevels ();
        for (int i = 0; i <= dim; ++ i)
                result [i] = (i < levels) ? hom. getBetti (i) : 0;
 
        // restore the message settings
        chomp::homology::sout. show = soutput;
        chomp::homology::scon. show = coutput;
        return;
} /* ComputeBettiNumbers */

References fcout, chomp::homengin::engine::find(), chomp::homology::scon, and chomp::homology::sout.

ComputeBettiNumbers() [3/3]

void CubicalSet::ComputeBettiNumbers ( int *  result, const char *  engine = 0, bool  quiet = false  ) const

inline

Computes the Betti numbers of the cubical set.

Note: The size of the result table must be at least dim+1.

Definition at line 262 of file cubiset.h.

{
        ::ComputeBettiNumbers (buffer, sizes, dim, result, engine,
                wrapping, quiet);
        return;
} /* CubicalSet::ComputeBettiNumbers */

References CubicalSet::buffer, CubicalSet::ComputeBettiNumbers(), CubicalSet::dim, CubicalSet::sizes, and CubicalSet::wrapping.

Referenced by CubicalSet::ComputeBettiNumbers().

Contains()

bool CubicalSet::Contains ( const int *  coords ) const

inline

Verifies whether the given cube is contained in the cubical set.

Returns 'true' if yes, 'false' if not.

Definition at line 251 of file cubiset.h.

{
        return buffer [ByteOffset (coords)] & BitMask (coords);
} /* CubicalSet::Contains */

References CubicalSet::BitMask(), CubicalSet::buffer, and CubicalSet::ByteOffset().

CubicalSet() [1/2]

CubicalSet::CubicalSet ( const CubicalSet &  c )

inline

The copy constructor.

Definition at line 168 of file cubiset.h.

{
        dim = c. dim;
        bufsize = c. bufsize;
        sizes = new int [dim];
        minimal = new int [dim];
        for (int i = 0; i < dim; ++ i)
        {
                minimal [i] = c. minimal [i];
                sizes [i] = c. sizes [i];
        }
        buffer = new unsigned char [bufsize];
        std::memcpy (buffer, c. buffer, bufsize);
        return;
} /* CubicalSet::CubicalSet */

References CubicalSet::buffer, CubicalSet::bufsize, CubicalSet::dim, CubicalSet::minimal, and CubicalSet::sizes.

CubicalSet() [2/2]

CubicalSet::CubicalSet ( const int *  left_coords, const int *  right_coords, int  dim = EMBEDDING_DIM, const int *  space_wrapping = 0  )

inline

The only constructor allowed: Creates an empty cubical bitmap of the given size.

Definition at line 118 of file cubiset.h.

{
        if (dim <= 0)
                throw "Non-positive dimension of a cubical complex.";
        this -> dim = dim;
        this -> sizes = new int [dim];
        this -> minimal = new int [dim];
        this -> wrapping = space_wrapping ? new int [dim] : 0;
        this -> bufsize = 0;
        for (int i = 0; i < dim; ++ i)
        {
                minimal [i] = left_coords [i];
                sizes [i] = right_coords [i] - left_coords [i];
                if (sizes [i] <= 0)
                        throw "Non-positive size of a cubical complex.";
                if (!i)
                {
                        sizes [0] = (sizes [0] + 63) & ~63;
                        bufsize = sizes [0] >> 3;
                }
                else
                        bufsize *= sizes [i];
        }
        if (space_wrapping)
        {
                for (int i = 0; i < dim; ++ i)
                {
                        wrapping [i] = space_wrapping [i];
                        if (wrapping [i] < 0)
                                wrapping [i] = -space_wrapping [i];
                }
        }
        if (bufsize <= 0)
                throw "Wrong buffer size in a cubical complex.";
        buffer = new unsigned char [bufsize];
        std::memset (buffer, 0, bufsize);
        return;
} /* CubicalSet::CubicalSet */

References CubicalSet::buffer, CubicalSet::bufsize, CubicalSet::dim, CubicalSet::minimal, CubicalSet::sizes, and CubicalSet::wrapping.

Delete()

int CubicalSet::Delete ( const int *  coords )

inline

Deletes a cube from the set.

Returns 0 if deleted or -1 if the cube is outside the box.

Definition at line 243 of file cubiset.h.

{
        if (!Inside (coords))
                return -1;
        buffer [ByteOffset (coords)] &= ~(BitMask (coords));
        return 0;
} /* CubicalSet::Delete */

References CubicalSet::BitMask(), CubicalSet::buffer, CubicalSet::ByteOffset(), and CubicalSet::Inside().

Inside()

bool CubicalSet::Inside ( const int *  coords )

inlineprivate

Verifies whether the cube is within the bounding box.

Definition at line 223 of file cubiset.h.

{
        for (int i = 0; i < dim; ++ i)
        {
                if (coords [i] < minimal [i])
                        return false;
                if (coords [i] >= minimal [i] + sizes [i])
                        return false;
        }
        return true;
} /* CubicalSet::Inside */

References CubicalSet::dim, CubicalSet::minimal, and CubicalSet::sizes.

Referenced by CubicalSet::Add(), and CubicalSet::Delete().

operator=()

CubicalSet & CubicalSet::operator= ( const CubicalSet &  c )

inline

The assignment operator.

Definition at line 184 of file cubiset.h.

{
        delete [] sizes;
        delete [] minimal;
        delete [] buffer;
 
        dim = c. dim;
        bufsize = c. bufsize;
        sizes = new int [dim];
        minimal = new int [dim];
        for (int i = 0; i < dim; ++ i)
        {
                minimal [i] = c. minimal [i];
                sizes [i] = c. sizes [i];
                if (i > 0)
                        bufsize *= sizes [i];
        }
        buffer = new unsigned char [bufsize];
        std::memcpy (buffer, c. buffer, bufsize);
        return *this;
} /* CubicalSet::operator = */

References CubicalSet::buffer, CubicalSet::bufsize, CubicalSet::dim, CubicalSet::minimal, and CubicalSet::sizes.

~CubicalSet()

CubicalSet::~CubicalSet ( )

inline

The destructor.

Definition at line 158 of file cubiset.h.

{
        delete [] sizes;
        delete [] minimal;
        delete [] buffer;
        if (wrapping)
                delete [] wrapping;
        return;
} /* CubicalSet::~CubicalSet */

References CubicalSet::buffer, CubicalSet::minimal, CubicalSet::sizes, and CubicalSet::wrapping.

Variable Documentation

fcout

ofstreamcout fcout

extern

An output stream defined by M. Mrozek in the CAPD library.

Referenced by ComputeBettiNumbers().