Public Member Functions | Private Member Functions | Private Attributes | Friends

chomp::homology::chaincomplex< euclidom > Class Template Reference

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

#include <chains.h>

List of all members.

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.
outputstreamshow_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.
outputstreamshow_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.
outputstreamcompute_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]
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 */


Friends And Related Function Documentation

template<class euclidom>
friend class chainmap< euclidom > [friend]

The class "chainmap" is a friend class which has access to the internal data of the chain complex class.

Definition at line 2552 of file chains.h.


Member Data Documentation

template<class euclidom>
mmatrix<euclidom>* chomp::homology::chaincomplex< euclidom >::boundary [private]
template<class euclidom>
mmatrix<euclidom>* chomp::homology::chaincomplex< euclidom >::generators [private]

Matrices which store actual combinations of generators.

Used for the extraction of generators of homology.

Definition at line 2575 of file chains.h.

Referenced by chomp::homology::chaincomplex< euclidom >::chaincomplex(), chomp::homology::chaincomplex< euclidom >::gethomgen(), chomp::homology::chaincomplex< euclidom >::simple_form(), and chomp::homology::chaincomplex< euclidom >::~chaincomplex().

template<class euclidom>
int* chomp::homology::chaincomplex< euclidom >::generators_initialized [private]
template<class euclidom>
int chomp::homology::chaincomplex< euclidom >::len [private]
template<class euclidom>
int* chomp::homology::chaincomplex< euclidom >::numgen [private]

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