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 [] |
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.
A lower-case version of the name of a bit field set [deprecated].
Definition at line 62 of file bitfield.h.
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] |
int chomp::homology::bitcountbyte | ( | char | n | ) | [inline] |
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.
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().
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().
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().
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.
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().
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().
bool chomp::homology::operator!= | ( | const diGraph< wType1 > & | g1, | |
const diGraph< wType2 > & | g2 | |||
) | [inline] |
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().
bool chomp::homology::operator== | ( | const diGraph< wType1 > & | g1, | |
const diGraph< wType2 > & | g2 | |||
) | [inline] |
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().
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().
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().
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().
unsigned char chomp::homology::bitcounttable[] |
Referenced by bitcountbyte().