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 | auto_array |
| An auto_array template that mimics selected behaviors of the std::auto_ptr template, but releases the memory with delete[], and thus should be applied to arrays. More... | |
| 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 | local_var |
| Local variable guardian. More... | |
| class | multitable |
| A container for elements placed in a table (like a vector) that is actually built of many smaller tables. More... | |
| class | setunion |
| A union of two hashed sets. 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_t length, BitField &field) |
| int | bits2int (const BitField &field, int_t 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_t | 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 , class Table1 , class Table2 > | |
| int_t | SCC_Tarjan (const diGraph< wType > &g, Table1 &compVertices, Table2 &compEnds) |
| Computes strongly connected components of the graph 'g' using Tarjan's algorithm (as described in the Wikipedia). | |
| template<class wType > | |
| int_t | addRenumEdges (const diGraph< wType > &g, int_t vertex, const int_t *newNum, int_t cur, int_t *srcVert, diGraph< wType > &result) |
| A helper function for "collapseVertices". | |
| template<class wType , class Table1 , class Table2 > | |
| int_t | collapseVertices (const diGraph< wType > &g, int_t compNum, Table1 &compVertices, Table2 &compEnds, diGraph< wType > &result, int_t *newNumbers=0) |
| Collapses disjoint subsets of vertices to single vertices and creates a corresponding graph in which the first vertices come from the collapsed ones. | |
| template<class wType , class TabSets > | |
| int_t | addRenumEdges2 (const diGraph< wType > &g, int_t vertex, const int_t *newNum, TabSets &numSets, int_t cur, int_t *srcVert, diGraph< wType > &result) |
| A helper function for "collapseVertices2". | |
| template<class wType , class Table1 , class Table2 > | |
| int_t | collapseVertices2 (const diGraph< wType > &g, int_t compNum, Table1 &compVertices, Table2 &compEnds, diGraph< wType > &result) |
| Collapses (possibly non-disjoint) subsets of vertices to single vertices and creates a corresponding graph in which the first vertices come from the collapsed ones. | |
| template<class wType > | |
| int_t | connectionGraph (const diGraph< wType > &g, int_t nVert, diGraph< wType > &result) |
| Computes the graph that represents connections between a number of the first vertices in the given graph. | |
| template<class GraphType > | |
| int_t | computePeriod (const GraphType &g) |
| Computes the period of a strongly connected graph. | |
| template<class wType > | |
| int_t | inclusionGraph (const diGraph< wType > &g, int_t nVert, diGraph< wType > &result) |
| Computes the graph that represents flow-induced relations on Morse sets. | |
| template<class wType , class TConn > | |
| int_t | inclusionGraph (const diGraph< wType > &g, int_t 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_t n, diGraph< wType > &g) |
| Creates a graph based on the given adjacency matrix. | |
| template<class matrix > | |
| void | transitiveClosure (matrix &m, int_t 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_t 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<class set1type , class set2type > | |
| setunion< set1type, set2type > | makesetunion (const set1type &set1, const set2type &set2) |
| Creates an object which represents the union of two sets. | |
Variables | |
| unsigned char | bitcounttable [] |
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 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_t chomp::homology::addRenumEdges | ( | const diGraph< wType > & | g, |
| int_t | vertex, | ||
| const int_t * | newNum, | ||
| int_t | cur, | ||
| int_t * | srcVert, | ||
| diGraph< wType > & | result | ||
| ) | [inline] |
A helper function for "collapseVertices".
Definition at line 3016 of file digraph.h.
Referenced by collapseVertices().
| int_t chomp::homology::addRenumEdges2 | ( | const diGraph< wType > & | g, |
| int_t | vertex, | ||
| const int_t * | newNum, | ||
| TabSets & | numSets, | ||
| int_t | cur, | ||
| int_t * | srcVert, | ||
| diGraph< wType > & | result | ||
| ) | [inline] |
A helper function for "collapseVertices2".
Definition at line 3131 of file digraph.h.
Referenced by collapseVertices2().
| int chomp::homology::bitcount | ( | int | number ) | [inline] |
Definition at line 49 of file bitcount.h.
References bitcountbyte().
| int chomp::homology::bitcountbyte | ( | char | n ) | [inline] |
| int chomp::homology::bits2int | ( | const BitField & | field, |
| int_t | length | ||
| ) | [inline] |
The length must not exceed the size of the integer.
Definition at line 214 of file bitfield.h.
| int_t chomp::homology::collapseVertices | ( | const diGraph< wType > & | g, |
| int_t | compNum, | ||
| Table1 & | compVertices, | ||
| Table2 & | compEnds, | ||
| diGraph< wType > & | result, | ||
| int_t * | newNumbers = 0 |
||
| ) | [inline] |
Collapses disjoint subsets 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 3048 of file digraph.h.
References addRenumEdges().
| int_t chomp::homology::collapseVertices2 | ( | const diGraph< wType > & | g, |
| int_t | compNum, | ||
| Table1 & | compVertices, | ||
| Table2 & | compEnds, | ||
| diGraph< wType > & | result | ||
| ) | [inline] |
Collapses (possibly non-disjoint) subsets 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.
Definition at line 3174 of file digraph.h.
References addRenumEdges2().
| int_t chomp::homology::computePeriod | ( | const GraphType & | g ) | [inline] |
Computes the period of a strongly connected graph.
The period of a graph is defined as the greatest common divisor of the lengths of all the cycles in the graph. Period 1 means that the graph is aperiodic. The complexity of this operation is linear (one DFS).
| int_t chomp::homology::connectionGraph | ( | const diGraph< wType > & | g, |
| int_t | nVert, | ||
| diGraph< wType > & | result | ||
| ) | [inline] |
Computes the graph that represents connections between a number of the first vertices in the given graph.
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, without going through any other vertex in that set. Runs DFS starting from each of the first "nVert" vertices, and thus may be a little inefficient in some cases.
| 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 3836 of file digraph.h.
Referenced by transitiveReduction().
| int_t chomp::homology::inclusionGraph | ( | const diGraph< wType > & | g, |
| int_t | 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.
| int_t chomp::homology::inclusionGraph | ( | const diGraph< wType > & | g, |
| int_t | 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.
| void chomp::homology::int2bits | ( | int | bits, |
| int_t | length, | ||
| BitField & | field | ||
| ) | [inline] |
The length must not exceed the size of the integer.
Definition at line 200 of file bitfield.h.
| setunion<set1type,set2type> chomp::homology::makesetunion | ( | const set1type & | set1, |
| const set2type & | set2 | ||
| ) | [inline] |
Creates an object which represents the union of two sets.
Definition at line 226 of file setunion.h.
| void chomp::homology::matrix2graph | ( | const matrix & | m, |
| int_t | 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 3856 of file digraph.h.
Referenced by transitiveReduction().
| 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] |
| bool chomp::homology::operator== | ( | const diGraph< wType1 > & | g1, |
| const diGraph< wType2 > & | g2 | ||
| ) | [inline] |
| int_t 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 with the numbers of vertices in 'g' which form the components, and the indices that end the listing for each component are stored in the table 'compEnds'. Returns the number of strongly connected components found.
Definition at line 2377 of file digraph.h.
Referenced by chomp::homology::diGraph< wType >::minMeanCycleWeight().
| int_t chomp::homology::SCC_Tarjan | ( | const diGraph< wType > & | g, |
| Table1 & | compVertices, | ||
| Table2 & | compEnds | ||
| ) | [inline] |
Computes strongly connected components of the graph 'g' using Tarjan's algorithm (as described in the Wikipedia).
Tha advantage of this approach over the one described in Cormen's textbook is that the transposed graph need not be computed. However, this algorithm might be slightly slower than the other one. The table 'compVertices' is filled with the numbers of vertices in 'g' which form the components, and the indices that end the listing for each component are stored in the table 'compEnds'. Returns the number of strongly connected components found.
| void chomp::homology::transitiveClosure | ( | matrix & | m, |
| int_t | 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 3874 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 3917 of file digraph.h.
References graph2matrix(), matrix2graph(), transitiveClosure(), and transitiveReduction().
| void chomp::homology::transitiveReduction | ( | matrix & | m, |
| int_t | 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 3898 of file digraph.h.
Referenced by transitiveReduction().
| unsigned char chomp::homology::bitcounttable[] |
Referenced by bitcountbyte().
1.7.2