chomp::homology Namespace Reference
[Unifexp]

This is the main namespace that contains most of the CHomP library classes and functions, some of which are used in the Uniform Expansion project. More...


Classes

class  BitField
 This class defines a bit field that is part of some larger array or that uses an allocated piece of memory. More...
class  SetOfBitFields
 This class defines a set of bit fields of the same length which are to be stored in a contiguous piece of memory to avoid multiple memory allocation/deallocation. More...
class  BitSets
 This class uses bit representation to store many small sets. More...
class  dummyRounding
 A dummy class for rounding operations which does not actually do any rounding. More...
class  dummyArray
 A dummy array of integers that ignores all the assigned values. More...
class  diGraph
 This class defines a directed graph with very limited number of operations, and a few specific algorithms implemented on it, like DFS. More...
class  FibonacciHeap
 This template contains the definition of a Fibonacci heap that can be used as an efficient priority queue, for example, in the Dijxtra graph algorithm. More...
class  flatMatrix
 This class defines a simple data structure for a flat 2-dim square matrix whose entries are stored in a single array. More...
class  multitable
 A container for elements placed in a table (like a vector) that is actually built of many smaller tables. More...

Typedefs

typedef BitField bitfield
 A lower-case version of the name of a bit field [deprecated].
typedef SetOfBitFields bitfieldset
 A lower-case version of the name of a bit field set [deprecated].

Functions

int bitcountbyte (char n)
int bitcount (int number)
void int2bits (int bits, int length, BitField &field)
int bits2int (const BitField &field, int length)
template<class wType1, class wType2>
bool operator== (const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
template<class wType1, class wType2>
bool operator!= (const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
template<class wType>
std::ostream & operator<< (std::ostream &out, const diGraph< wType > &g)
 Writes a graph in the text mode to an output stream.
template<class wType, class Table1, class Table2>
int SCC (const diGraph< wType > &g, Table1 &compVertices, Table2 &compEnds, diGraph< wType > *scc=0, diGraph< wType > *transposed=0, bool copyweights=false)
 Computes strongly connected components of the graph 'g'.
template<class wType>
int addRenumEdges (const diGraph< wType > &g, int vertex, const int *newNum, int cur, int *srcVert, diGraph< wType > &result)
template<class wType, class Table1, class Table2>
int collapseVertices (const diGraph< wType > &g, int compNum, Table1 &compVertices, Table2 &compEnds, diGraph< wType > &result, int *newNumbers=0)
 Collapses sets of vertices to single vertices and creates a corresponding graph in which the first vertices come from the collapsed ones.
template<class wType>
int inclusionGraph (const diGraph< wType > &g, int nVert, diGraph< wType > &result)
 Computes the graph that represents flow-induced relations on Morse sets.
template<class wType, class TConn>
int inclusionGraph (const diGraph< wType > &g, int nVert, diGraph< wType > &result, TConn &connections)
 A more complicated version of the 'inclusionGraph' function.
template<class wType, class matrix>
void graph2matrix (const diGraph< wType > &g, matrix &m)
 Creates the adjacency matrix of the given graph.
template<class wType, class matrix>
void matrix2graph (const matrix &m, int n, diGraph< wType > &g)
 Creates a graph based on the given adjacency matrix.
template<class matrix>
void transitiveClosure (matrix &m, int n)
 Computes the transitive closure of an acyclic graph defined by its adjacency matrix, using the Warshall's algorithm: S.
template<class matrix>
void transitiveReduction (matrix &m, int n)
 Computes the transitive reduction of a CLOSED acyclic graph defined by its adjacency matrix, using the algorithm by D.
template<class wType>
void transitiveReduction (const diGraph< wType > &g, diGraph< wType > &gRed)
 Computes the transitive reduction of an arbitrary acyclic graph.
template<typename T>
void my_swap (T &x, T &y)

Variables

unsigned char bitcounttable []


Detailed Description

This is the main namespace that contains most of the CHomP library classes and functions, some of which are used in the Uniform Expansion project.

Typedef Documentation

typedef BitField chomp::homology::bitfield

A lower-case version of the name of a bit field [deprecated].

Definition at line 56 of file bitfield.h.

typedef SetOfBitFields chomp::homology::bitfieldset

A lower-case version of the name of a bit field set [deprecated].

Definition at line 62 of file bitfield.h.


Function Documentation

template<class wType>
int chomp::homology::addRenumEdges ( const diGraph< wType > &  g,
int  vertex,
const int *  newNum,
int  cur,
int *  srcVert,
diGraph< wType > &  result 
) [inline]

Definition at line 2793 of file digraph.h.

References chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::countEdges(), and chomp::homology::diGraph< wType >::getEdge().

Referenced by collapseVertices().

int chomp::homology::bitcount ( int  number  )  [inline]

Definition at line 49 of file bitcount.h.

References bitcountbyte().

int chomp::homology::bitcountbyte ( char  n  )  [inline]

Definition at line 44 of file bitcount.h.

References bitcounttable.

Referenced by bitcount().

int chomp::homology::bits2int ( const BitField &  field,
int  length 
) [inline]

The length must not exceed the size of the integer.

Definition at line 214 of file bitfield.h.

References chomp::homology::BitField::table.

template<class wType, class Table1, class Table2>
int chomp::homology::collapseVertices ( const diGraph< wType > &  g,
int  compNum,
Table1 &  compVertices,
Table2 &  compEnds,
diGraph< wType > &  result,
int *  newNumbers = 0 
) [inline]

Collapses sets of vertices to single vertices and creates a corresponding graph in which the first vertices come from the collapsed ones.

The result graph must be initially empty. Saves translation table from old to new vertex numbers. The table must have sufficient length.

Definition at line 2824 of file digraph.h.

References addRenumEdges(), chomp::homology::diGraph< wType >::addVertex(), and chomp::homology::diGraph< wType >::countVertices().

template<class wType, class matrix>
void chomp::homology::graph2matrix ( const diGraph< wType > &  g,
matrix &  m 
) [inline]

Creates the adjacency matrix of the given graph.

m [i] [j] is set to 1 if the graph g contains the edge i -> j, using the assignment operator.

Definition at line 3250 of file digraph.h.

References chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::countVertices(), and chomp::homology::diGraph< wType >::getEdge().

Referenced by transitiveReduction().

template<class wType, class TConn>
int chomp::homology::inclusionGraph ( const diGraph< wType > &  g,
int  nVert,
diGraph< wType > &  result,
TConn &  connections 
) [inline]

A more complicated version of the 'inclusionGraph' function.

Computes the graph that represents flow-induced relations on Morse sets. The vertices of the result graph are the first "nVert" vertices from the source graph. An edge is added to the new graph iff there exists a path from one vertex to another. Edges that come from the transitive closure are not added. Records vertices along connecting orbits using operator () with the following arguments: source, target, vertex.

Definition at line 3028 of file digraph.h.

References chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::countVertices(), chomp::homology::diGraph< wType >::getEdge(), and chomp::homology::diGraph< wType >::transpose().

template<class wType>
int chomp::homology::inclusionGraph ( const diGraph< wType > &  g,
int  nVert,
diGraph< wType > &  result 
) [inline]

Computes the graph that represents flow-induced relations on Morse sets.

The vertices of the result graph are the first "nVert" vertices from the source graph. An edge is added to the new graph iff there exists a path from one vertex to another. Edges that come from the transitive closure are not added.

Definition at line 2908 of file digraph.h.

References chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::countVertices(), and chomp::homology::diGraph< wType >::getEdge().

void chomp::homology::int2bits ( int  bits,
int  length,
BitField &  field 
) [inline]

The length must not exceed the size of the integer.

Definition at line 200 of file bitfield.h.

References chomp::homology::BitField::table.

template<class wType, class matrix>
void chomp::homology::matrix2graph ( const matrix &  m,
int  n,
diGraph< wType > &  g 
) [inline]

Creates a graph based on the given adjacency matrix.

If m [i] [j] is nonzero, then the edge i -> j is added to the graph. It is assumed that the graph g is initially empty. The size of the matrix (the number of vertices), n, must be given.

Definition at line 3270 of file digraph.h.

References chomp::homology::diGraph< wType >::addEdge(), and chomp::homology::diGraph< wType >::addVertex().

Referenced by transitiveReduction().

template<typename T>
void chomp::homology::my_swap ( T &  x,
T &  y 
) [inline]

Definition at line 56 of file multitab.h.

Referenced by chomp::homology::multitable< element >::swap(), and chomp::homology::diGraph< wType >::swap().

template<class wType1, class wType2>
bool chomp::homology::operator!= ( const diGraph< wType1 > &  g1,
const diGraph< wType2 > &  g2 
) [inline]

Definition at line 590 of file digraph.h.

template<class wType>
std::ostream& chomp::homology::operator<< ( std::ostream &  out,
const diGraph< wType > &  g 
) [inline]

Writes a graph in the text mode to an output stream.

Definition at line 2327 of file digraph.h.

References chomp::homology::diGraph< wType >::show().

template<class wType1, class wType2>
bool chomp::homology::operator== ( const diGraph< wType1 > &  g1,
const diGraph< wType2 > &  g2 
) [inline]

No isomorphism check, just comparing with the same order of vertices. Ignores weights.

Definition at line 572 of file digraph.h.

template<class wType, class Table1, class Table2>
int chomp::homology::SCC ( const diGraph< wType > &  g,
Table1 &  compVertices,
Table2 &  compEnds,
diGraph< wType > *  scc = 0,
diGraph< wType > *  transposed = 0,
bool  copyweights = false 
) [inline]

Computes strongly connected components of the graph 'g'.

Creates the graph 'scc' in which each vertex corresponds to one component. The graph 'scc' given as an argument must be initially empty. The table 'compVertices' is filled out with the numbers of vertices in 'g' which form the components, and the indices that end each component listing are stored in the table 'compEnds'. Returns the number of strongly connected components found.

Definition at line 2342 of file digraph.h.

References chomp::homology::diGraph< wType >::countVertices(), chomp::homology::diGraph< wType >::DFSfinishTime(), chomp::homology::diGraph< wType >::DFSforest(), and chomp::homology::diGraph< wType >::transpose().

Referenced by chomp::homology::diGraph< wType >::minMeanCycleWeight().

template<class matrix>
void chomp::homology::transitiveClosure ( matrix &  m,
int  n 
) [inline]

Computes the transitive closure of an acyclic graph defined by its adjacency matrix, using the Warshall's algorithm: S.

Warshall, A theorem on Boolean matrices, J. ACM 9 (1962) 11-12.

Definition at line 3288 of file digraph.h.

Referenced by transitiveReduction().

template<class wType>
void chomp::homology::transitiveReduction ( const diGraph< wType > &  g,
diGraph< wType > &  gRed 
) [inline]

Computes the transitive reduction of an arbitrary acyclic graph.

The output graph must be initially empty.

Definition at line 3331 of file digraph.h.

References chomp::homology::diGraph< wType >::countVertices(), graph2matrix(), matrix2graph(), transitiveClosure(), and transitiveReduction().

template<class matrix>
void chomp::homology::transitiveReduction ( matrix &  m,
int  n 
) [inline]

Computes the transitive reduction of a CLOSED acyclic graph defined by its adjacency matrix, using the algorithm by D.

Gries, A.J. Martin, J.L.A. van de Snepscheut and J.T. Udding, An algorithm for transitive reduction of an acyclic graph, Science of Computer Programming 12 (1989), 151-155. WARNING: The input graph MUST BE CLOSED, use the "transitiveClosure" algorithm first if this is not the case.

Definition at line 3312 of file digraph.h.

Referenced by transitiveReduction().


Variable Documentation

unsigned char chomp::homology::bitcounttable[]

Referenced by bitcountbyte().


Generated on Wed Nov 21 11:08:42 2007 for The Uniform Expansion Software by  doxygen 1.5.3