This is an implementation of a chain complex over an arbitrary ring. More...

#include <chains.h>

Public Member Functions
	chaincomplex (int d, int trace_generators=0)
	The default constructor.
	~chaincomplex ()
	The destructor.
void	def_gen (int q, int n)
	Defines the number of generators in the given dimension.
void	add (int q, int m, int n, const euclidom &e)
	Adds a coefficient to the structure: D_q [m, n] += e.
euclidom	get (int q, int row, int col) const
	Returns an element from the boundary matrix for the given dimension.
const mmatrix< euclidom > &	getboundary (int i) const
	Returns a reference to the given boundary matrix.
int	getnumgen (int i) const
	Returns the number of generators at the given level.
int	dim () const
	Returns the dimension of the chain complex.
const chain< euclidom > &	gethomgen (int q, int i) const
	Returns the given homology generator at level q.
void	simple_form (int which, bool quiet)
	Reduces of the given boundary matrix in the chain complex for the purpose of homology computation.
void	simple_form (const int *level, bool quiet)
	Runs the reduction of all the boundary matrices in the chain complex.
int	simple_homology (chain< euclidom > &result, int which) const
	Computes the given level of homology of the chain complex, provided it has been transformed into the simple form previously.
int	simple_homology (chain< euclidom > &result, const int level=NULL) const
	Computes the homology of the chain complex, provided it has been transformed into the simple form previously.
void	take_homology (const chain< euclidom > *hom_chain)
	Creates a chain complex containing exactly one generator for each homology generator.
outputstream &	show_homology (outputstream &out, const chain< euclidom > hom, const int level=NULL) const
	Writes the homology module of the chain complex to an output stream.
std::ostream &	show_homology (std::ostream &out, const chain< euclidom > hom, const int level=NULL) const
	Writes the homology module of the chain complex to an output stream.
outputstream &	show_generators (outputstream &out, const chain< euclidom > &list, int q) const
	Writes the homology generators of the homology module to an output stream.
std::ostream &	show_generators (std::ostream &out, const chain< euclidom > &list, int q) const
	Writes the homology generators of the homology module to an output stream.
outputstream &	compute_and_show_homology (outputstream &out, chain< euclidom > &hom, const int level=NULL)
	Computes the homology and shows the result.
std::ostream &	compute_and_show_homology (std::ostream &out, chain< euclidom > &hom, const int level=NULL)
	Computes the homology and shows the result.
Private Member Functions
	chaincomplex (const chaincomplex< euclidom > &m)
	The copy constructor is not implemented.
chaincomplex< euclidom > &	operator= (const chaincomplex< euclidom > &s)
	The assignment operator is not implemented.
Private Attributes
int	len
	The length of the chain complex (i.e., its dimension + 1).
mmatrix< euclidom > *	boundary
	The matrices of the boundary homomorphism.
mmatrix< euclidom > *	generators
	Matrices which store actual combinations of generators.
int *	generators_initialized
	Have the generator tracing matrices been initialized to the identity (of suitable size each)?
int *	numgen
	The numbers of generators in each dimension, or -1's if not defined yet.
Friends
class	chainmap< euclidom >
	The class "chainmap" is a friend class which has access to the internal data of the chain complex class.

Detailed Description

template<class euclidom>
class chomp::homology::chaincomplex< euclidom >

This is an implementation of a chain complex over an arbitrary ring.

The dimension of the chain complex must be known apriori. If there are elements not used in boundaries, use "def_gen" to set the true number of generators at each level.

Definition at line 2445 of file chains.h.

Constructor & Destructor Documentation

template<class euclidom >

chomp::homology::chaincomplex< euclidom >::chaincomplex	(	int	d,
		int	trace_generators = `0`
	)			`[inline]`

The default constructor.

The dimension must be defined apriori and cannot be modified later. If requested, additional matrices are created to trace homology generators.

Definition at line 2590 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::add(), chomp::homology::chaincomplex< euclidom >::boundary, chomp::homology::chaincomplex< euclidom >::generators, chomp::homology::chaincomplex< euclidom >::generators_initialized, chomp::homology::chaincomplex< euclidom >::len, and chomp::homology::chaincomplex< euclidom >::numgen.

{
        // set the number of tables to be sufficient for 0 to d inclusive
        len = (d >= 0) ? (d + 1) : 0;

        // create a table of empty matrices
        boundary = len ? new mmatrix<euclidom> [len] : NULL;

        // create a table of matrices for tracing generators of homology
        generators = (trace_generators && len) ?
                new mmatrix<euclidom> [len] : NULL;
        if (generators)
                generators_initialized = new int [len];
        else
                generators_initialized = NULL;

        // create a table of generator numbers
        numgen = len ? new int [len] : NULL;

        // link the boundary matrices to each other and to the generators
        for (int i = 0; i < len; ++ i)
        {
                numgen [i] = -1;
                if (i < len - 1)
                        boundary [i]. dom_img. add (boundary [i + 1]);
                if (i > 0)
                        boundary [i]. img_dom. add (boundary [i - 1]);
                if (generators)
                {
                        boundary [i]. dom_dom. add (generators [i]);
                        if (i > 0)
                                boundary [i]. img_dom. add
                                        (generators [i - 1]);
                        generators_initialized [i] = 0;
                }
        }

        return;
} /* chaincomplex<euclidom>::chaincomplex */

template<class euclidom >

chomp::homology::chaincomplex< euclidom >::~chaincomplex ( ) [inline]

The destructor.

Definition at line 2631 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::boundary, chomp::homology::chaincomplex< euclidom >::generators, chomp::homology::chaincomplex< euclidom >::generators_initialized, and chomp::homology::chaincomplex< euclidom >::numgen.

{
        if (boundary)
                delete [] boundary;
        if (generators)
                delete [] generators;
        if (numgen)
                delete [] numgen;
        if (generators_initialized)
                delete [] generators_initialized;
        return;
} /* chaincomplex<euclidom>::~chaincomplex */

template<class euclidom>

chomp::homology::chaincomplex< euclidom >::chaincomplex ( const chaincomplex< euclidom > & m ) [inline, private]

The copy constructor is not implemented.

Definition at line 2556 of file chains.h.

                {throw "Copying constructor not implemented "
                "for a chain complex.";}

Member Function Documentation

template<class euclidom >

void chomp::homology::chaincomplex< euclidom >::add	(	int	q,
		int	m,
		int	n,
		const euclidom &	e
	)			`[inline]`

Adds a coefficient to the structure: D_q [m, n] += e.

In other words, boundary of element n += e * element m.

Definition at line 2664 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::boundary, chomp::homology::chaincomplex< euclidom >::len, and chomp::homology::chaincomplex< euclidom >::numgen.

Referenced by chomp::homology::chaincomplex< euclidom >::chaincomplex(), and chomp::homology::chaincomplex< euclidom >::simple_homology().

{
        if ((q <= 0) || (q >= len))
                throw "Trying to add a boundary for dimension out of range";

        if (numgen [q] <= n)
                numgen [q] = n + 1;
        if (numgen [q - 1] <= m)
                numgen [q - 1] = m + 1;

        boundary [q]. add (m, n, e);
        return;
} /* chaincomplex<euclidom>::add */

template<class euclidom >

outputstream & chomp::homology::chaincomplex< euclidom >::compute_and_show_homology	(	outputstream &	out,
		chain< euclidom > *&	hom,
		const int *	level = `NULL`
	)			`[inline]`

Computes the homology and shows the result.

Definition at line 2898 of file chains.h.

References chomp::homology::show_homology().

{
        simple_form (level, false);
        simple_homology (hom, level);
        show_homology (out, hom, level);
        return out;
} /* chaincomplex<euclidom>::compute_and_show_homology */

template<class euclidom >

std::ostream & chomp::homology::chaincomplex< euclidom >::compute_and_show_homology	(	std::ostream &	out,
		chain< euclidom > *&	hom,
		const int *	level = `NULL`
	)			`[inline]`

Computes the homology and shows the result.

Definition at line 2908 of file chains.h.

{
        outputstream tout (out);
        compute_and_show_homology (tout, hom, level);
        return out;
} /* chaincomplex<euclidom>::compute_and_show_homology */

template<class euclidom >

void chomp::homology::chaincomplex< euclidom >::def_gen	(	int	q,
		int	n
	)			`[inline]`

Defines the number of generators in the given dimension.

This number is automatically increased while boundary formulas are added. However, it must be used if some generators do not appear in the boundaries or have zero boundaries.

Definition at line 2645 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::boundary, chomp::homology::chaincomplex< euclidom >::dim(), chomp::homology::chaincomplex< euclidom >::len, and chomp::homology::chaincomplex< euclidom >::numgen.

{
        if ((q < 0) || (q >= len))
                return;

        if (numgen [q] < n)
                numgen [q] = n;

        if (q == 0)
                boundary [0]. define (0, numgen [q]);
        if ((q > 0) && (numgen [q - 1] >= 0))
                boundary [q]. define (numgen [q - 1], numgen [q]);
        if ((q < dim ()) && (numgen [q + 1] >= 0))
                boundary [q + 1]. define (numgen [q], numgen [q + 1]);

        return;
} /* chaincomplex<euclidom>::def_gen */

template<class euclidom >

int chomp::homology::chaincomplex< euclidom >::dim ( ) const [inline]

Returns the dimension of the chain complex.

Definition at line 2712 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::len.

Referenced by chomp::homology::chaincomplex< euclidom >::def_gen(), and chomp::homology::chaincomplex< euclidom >::simple_homology().

{
        return len - 1;
} /* chaincomplex<euclidom>::dim */

template<class euclidom >

euclidom chomp::homology::chaincomplex< euclidom >::get	(	int	q,
		int	row,
		int	col
	)			const `[inline]`

Returns an element from the boundary matrix for the given dimension.

Definition at line 2680 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::boundary, and chomp::homology::chaincomplex< euclidom >::len.

{
        if ((q <= 0) || (q >= len))
                throw "Boundary coefficient out of range from chain cplx.";

        return boundary [q]. get (row, col);
} /* chaincomplex<euclidom>::get */

template<class euclidom >

const mmatrix< euclidom > & chomp::homology::chaincomplex< euclidom >::getboundary ( int i ) const [inline]

Returns a reference to the given boundary matrix.

Definition at line 2689 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::boundary, and chomp::homology::chaincomplex< euclidom >::len.

{
        if ((i <= 0) || (i >= len))
                throw "Boundary matrix out of range from chain complex.";

        return boundary [i];
} /* chaincomplex<euclidom>::getboundary */

template<class euclidom >

const chain< euclidom > & chomp::homology::chaincomplex< euclidom >::gethomgen	(	int	q,
		int	i
	)			const `[inline]`

Returns the given homology generator at level q.

Note: 'i' must be the number of chain generator.

Definition at line 2718 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::generators, chomp::homology::chaincomplex< euclidom >::generators_initialized, and chomp::homology::chaincomplex< euclidom >::len.

{
        if ((q < 0) || (q >= len))
                throw "Level for homology generators out of range.";
        if (!generators_initialized [q])
                throw "Trying to get non-existent homology generators.";
        return generators [q]. getcol (i);
} /* chaincomplex<euclidom>::getgen */

template<class euclidom >

int chomp::homology::chaincomplex< euclidom >::getnumgen ( int i ) const [inline]

Returns the number of generators at the given level.

Definition at line 2699 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::len, and chomp::homology::chaincomplex< euclidom >::numgen.

{
        if ((i < 0) || (i >= len))
        //      throw "Level for the number of generators out of range.";
                return 0;

        if (numgen [i] < 0)
                return 0;
        else
                return numgen [i];
} /* chaincomplex<euclidom>::getnumgen */

template<class euclidom>

chaincomplex<euclidom>& chomp::homology::chaincomplex< euclidom >::operator= ( const chaincomplex< euclidom > & s ) [inline, private]

The assignment operator is not implemented.

Definition at line 2562 of file chains.h.

                {throw "Operator = not implemented "
                "for a chain complex."; return *this;}

template<class euclidom >

std::ostream & chomp::homology::chaincomplex< euclidom >::show_generators	(	std::ostream &	out,
		const chain< euclidom > &	list,
		int	q
	)			const `[inline]`

Writes the homology generators of the homology module to an output stream.

Each generator as a combination of the original ones is shown on a separate line.

Definition at line 2888 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::show_generators().

{
        outputstream tout (out);
        show_generators (tout, list, q);
        return out;
} /* chaincomplex<euclidom>::show_generators */

template<class euclidom >

outputstream & chomp::homology::chaincomplex< euclidom >::show_generators	(	outputstream &	out,
		const chain< euclidom > &	list,
		int	q
	)			const `[inline]`

Writes the homology generators of the homology module to an output stream.

Each generator as a combination of the original ones is shown on a separate line.

Definition at line 2878 of file chains.h.

Referenced by chomp::homology::chaincomplex< euclidom >::show_generators().

{
        if (!generators || (q < 0) || (q >= len))
                return out;
        for (int i = 0; i < list. size (); ++ i)
                out << gethomgen (q, list. num (i)) << '\n';
        return out;
} /* chaincomplex<euclidom>::show_generators */

template<class euclidom >

std::ostream & chomp::homology::chaincomplex< euclidom >::show_homology	(	std::ostream &	out,
		const chain< euclidom > *	hom,
		const int *	level = `NULL`
	)			const `[inline]`

Writes the homology module of the chain complex to an output stream.

If a table of levels is given, shows only these levels for which the table's entry is nonzero.

Definition at line 2868 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::show_homology().

{
        outputstream tout (out);
        show_homology (tout, hom, level);
        return out;
} /* chaincomplex<euclidom>::show_homology */

template<class euclidom >

outputstream & chomp::homology::chaincomplex< euclidom >::show_homology	(	outputstream &	out,
		const chain< euclidom > *	hom,
		const int *	level = `NULL`
	)			const `[inline]`

Writes the homology module of the chain complex to an output stream.

If a table of levels is given, shows only these levels for which the table's entry is nonzero.

Definition at line 2848 of file chains.h.

References chomp::homology::show_homology().

Referenced by chomp::homology::chaincomplex< euclidom >::show_homology().

{
        int max_level = len - 1;
        while ((max_level >= 0) && !hom [max_level]. size ())
                -- max_level;
        ++ max_level;
        for (int q = 0; q < max_level; ++ q)
        {
                if (!level || level [q])
                {
                        out << "H_" << q << " = ";
                        chomp::homology::show_homology (out, hom [q]);
                        out << '\n';
                }
        }
        return out;
} /* chaincomplex<euclidom>::show_homology */

template<class euclidom >

void chomp::homology::chaincomplex< euclidom >::simple_form	(	const int *	level,
		bool	quiet
	)			`[inline]`

Runs the reduction of all the boundary matrices in the chain complex.

If the array of levels is given, computes only simple forms necessary for homology levels for which the entries in the array are nonzero.

Definition at line 2775 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::len, and chomp::homology::chaincomplex< euclidom >::simple_form().

{
        for (int i = len - 1; i >= 0; -- i)
        {
                if (!level || level [i] || (i && level [i - 1]))
                        simple_form (i, quiet);
        }
        return;
} /* chaincomplex<euclidom>::simple_form */

template<class euclidom >

void chomp::homology::chaincomplex< euclidom >::simple_form	(	int	which,
		bool	quiet
	)			`[inline]`

Reduces of the given boundary matrix in the chain complex for the purpose of homology computation.

Definition at line 2729 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::boundary, chomp::homology::chaincomplex< euclidom >::generators, chomp::homology::chaincomplex< euclidom >::generators_initialized, chomp::homology::chaincomplex< euclidom >::len, chomp::homology::chaincomplex< euclidom >::numgen, and chomp::homology::sout.

Referenced by chomp::homology::chaincomplex< euclidom >::simple_form().

{
//      if ((which < 0) || (which >= len))
//              throw "Trying to find the simple form of a wrong matrix.";

        // if the generator tracing matrices are not initialized, do it now
        if (generators)
        {
                if (!generators_initialized [which])
                        generators [which]. identity (numgen [which]);
                generators_initialized [which] = 1;
                if ((which > 0) && (!generators_initialized [which - 1]))
                {
                        generators [which - 1]. identity
                                (numgen [which - 1]);
                        generators_initialized [which - 1] = 1;
                }
        }

        // verify that the adjacent matrices have sufficient size
        if (which > 0)
        {
                int n = boundary [which]. getnrows ();
                mmatrix<euclidom> &other = boundary [which - 1];
                if (other. getncols () < n)
                        other. define (other. getnrows (), n);
        }
        if (which < len - 1)
        {
                int n = boundary [which]. getncols ();
                mmatrix<euclidom> &other = boundary [which + 1];
                if (other. getnrows () < n)
                        other. define (n, other. getncols ());
        }

        // compute simple form of the desired boundary matrix
        if (!quiet && which)
                sout << "Reducing D_" << which << ": ";
        boundary [which]. simple_form (quiet);
        if (!quiet && which)
                sout << '\n';

        return;
} /* chaincomplex<euclidom>::simple_form */

template<class euclidom >

int chomp::homology::chaincomplex< euclidom >::simple_homology	(	chain< euclidom > *&	result,
		const int *	level = `NULL`
	)			const `[inline]`

Computes the homology of the chain complex, provided it has been transformed into the simple form previously.

Encodes the homology as a table of chains (one chain for each dimension) which are combinations of generator numberss together with their torsion coefficients (or with 1's if none). Returns the dimension of the chain complex. If a table of levels is given, computes only these levels of homology for which the table's entry is nonzero.

Definition at line 2812 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::dim(), chomp::homology::chaincomplex< euclidom >::len, and chomp::homology::chaincomplex< euclidom >::simple_homology().

{
        // if the chain complex is empty, then just set the result to NULL
        if (!len)
        {
                result = NULL;
                return dim ();
        }

        result = new chain<euclidom> [len];
        if (!result)
                throw "Not enough memory to create homology chains.";

        for (int q = 0; q < len; ++ q)
        {
                if (!level || level [q])
                        simple_homology (result [q], q);
        }

        return dim ();
} /* chaincomplex<euclidom>::simple_homology */

template<class euclidom >

int chomp::homology::chaincomplex< euclidom >::simple_homology	(	chain< euclidom > &	result,
		int	which
	)			const `[inline]`

Computes the given level of homology of the chain complex, provided it has been transformed into the simple form previously.

Encodes this homology group as a chain which is a combination generator numbers together with their torsion coefficients (or with 1's if none).

Definition at line 2787 of file chains.h.

References chomp::homology::chaincomplex< euclidom >::add(), chomp::homology::chaincomplex< euclidom >::boundary, and chomp::homology::chaincomplex< euclidom >::dim().

Referenced by chomp::homology::chaincomplex< euclidom >::simple_homology().

{
        int g = boundary [which]. findcol (-1, 0);
        while (g >= 0)
        {
                euclidom e;
                if (which == dim ())
                        e = 0;
                else
                        e = boundary [which + 1]. get (g, -1);
                if (e == 0)
                {
                        e = 1;
                        result. add (g, e);
                }
                else if (e. delta () > 1)
                        result. add (g, e. normalized ());
                g = boundary [which]. findcol (-1, g + 1);
        }

        return which;
} /* chaincomplex<euclidom>::simple_homology */

template<class euclidom >

void chomp::homology::chaincomplex< euclidom >::take_homology ( const chain< euclidom > * hom_chain ) [inline]

Creates a chain complex containing exactly one generator for each homology generator.

This function is used for extracting the map induced in homology by a chain map.

Definition at line 2837 of file chains.h.

{
        if (!hom_chain)
                return;
        for (int q = 0; q < len; ++ q)
                def_gen (q, hom_chain [q]. size ());
        return;
} /* chaincomplex<euclidom>::take_homology */