The CyMeAlg Software (Release 0.01)
|
Classes | |
class | diGraph |
This class defines a weighted directed graph with very limited number of operations. More... | |
class | dummyArray |
A dummy array of integers that ignores all the assigned values. More... | |
class | dummyRounding |
A dummy class for rounding operations which does not actually do any rounding. More... | |
class | tBoostRounding |
A class for rounding operations which uses the BOOST library. More... | |
Functions | |
template<class wType > | |
wType | minMeanCycleWeight (const diGraph< wType > &g, diGraph< wType > *transposed=0) |
Runs the Karp algorithm for each strongly connected component of the graph and returns the minimum mean cycle weight, which can be negative. More... | |
template<class wType , class roundType > | |
wType | minMeanCycleWeight (const diGraph< wType > &g, const roundType &rounding, diGraph< wType > *transposed) |
A version of Karp algorithm modified for the purpose of interval arithmetic to provide the correct lower bound for the minimum mean cycle weight in a graph. More... | |
template<class wType , class roundType > | |
wType | minMeanCycleWeightMem (const diGraph< wType > &g, const roundType &rounding, diGraph< wType > *transposed) |
A rigorous numerics version of Karp algorithm modified in such a way that the memory usage is minimized, at the cost of slower execution (up to twice slower). More... | |
template<class Graph , class Table > | |
void | DFSfinishTimeRecurrent (const Graph &g, Table &tab, int_t vertex, int_t &counter) |
The recurrent procedure for DFSfinishTime. More... | |
template<class Graph , class Table > | |
void | DFSfinishTimeStack (const Graph &g, Table &tab, int_t vertex, int_t &counter) |
A stack version of the recurrent procedure for DFSfinishTime. More... | |
template<class Graph , class Table > | |
void | DFSfinishTime (const Graph &g, Table &tab) |
Computes the DFS finishing time for each vertex. More... | |
template<class Graph , class Table1 , class Table2 > | |
bool | DFSforestRecurrent (const Graph &g, Table1 &tab, Table1 &ntab, int_t vertex, int_t treeNumber, int_t countTrees, Table2 &compVertices, int_t &curVertex, Graph *sccGraph, int_t *sccEdgeAdded) |
The recurrent procedure for DFSforest. More... | |
template<class Graph , class Table1 , class Table2 > | |
bool | DFSforestStack (const Graph &g, Table1 &tab, Table1 &ntab, int_t vertex, int_t treeNumber, int_t countTrees, Table2 &compVertices, int_t &curVertex, Graph *sccGraph, int_t *sccEdgeAdded) |
A stack version of the recurrent procedure for DFSforest. More... | |
template<class Graph , class Table1 , class Table2 , class Table3 > | |
int_t | DFSforest (const Graph &g, const Table1 &ordered, Table2 &compVertices, Table3 &compEnds, bool nontrivial=false, Graph *sccGraph=0) |
Computes the DFS forest. More... | |
template<class Graph , class Table , class Color > | |
void | DFScolorRecurrent (const Graph &g, Table &tab, const Color &color, int_t vertex=0) |
The recurrent procedure for DFScolor. More... | |
template<class Graph , class Table , class Color > | |
void | DFScolorStack (const Graph &g, Table &tab, const Color &color, int_t vertex=0) |
A stack version of the recurrent procedure for DFScolor. More... | |
template<class Graph , class Table , class Color > | |
void | DFScolor (const Graph &g, Table &tab, const Color &color, int_t vertex=0) |
Marks each vertex visited by DFS with the given color, starting with the given vertex. More... | |
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 Graph , class Table > | |
void | setWeights (Graph &g, const Table &tab) |
Sets the weights of all the edges at a time. More... | |
template<class Graph , class Table > | |
void | getWeights (const Graph &g, Table &tab) |
Gets the weights of all the edges at a time. More... | |
template<class Graph , class Table > | |
void | writeEdges (const Graph &g, Table &tab) |
Fills out a table that represents all the edges of the graph. More... | |
template<class wType , class arrayType , class roundType > | |
wType | minMeanPathWeight (const diGraph< wType > &g, const roundType &rounding, const arrayType &starting, int_t n) |
Runs an algorithm based on Karp's idea to compute the minimum mean path weight for paths starting at any of the given n vertices and of length not exceeding the number of vertices in the graph. More... | |
template<class wType , class arrayType > | |
wType | minMeanPathWeight (const diGraph< wType > &g, const arrayType &starting, int_t n) |
The above algorithm without rounding control. More... | |
template<class inType , class Graph > | |
inType & | read (inType &in, Graph &g) |
Reads a graph in the text mode from an input stream. More... | |
template<class wType > | |
std::istream & | operator>> (std::istream &in, diGraph< wType > &g) |
Reads a graph in the text mode from an input stream. More... | |
template<class outType , class Graph > | |
outType & | write (outType &out, const Graph &g, bool writeWeights) |
Outputs the graph to a text stream in a human-readable format. More... | |
template<class wType > | |
std::ostream & | operator<< (std::ostream &out, const diGraph< wType > &g) |
Writes a graph in the text mode to an output stream. More... | |
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 path components of the graph 'g'. More... | |
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). More... | |
template<class Graph1 , class Graph2 , class Table > | |
void | subgraph (const Graph1 &g, Graph2 &result, const Table &tab, bool copyweights=false) |
Computes a restriction of the graph to its subgraph. More... | |
template<class Graph1 , class Graph2 > | |
void | transpose (const Graph1 &g, Graph2 &result, bool copyweights=false) |
Creates a transposed graph. More... | |
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". More... | |
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. More... | |
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". More... | |
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. More... | |
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. More... | |
template<class GraphType > | |
int_t | computePeriod (const GraphType &g) |
Computes the period of a strongly connected graph. More... | |
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. More... | |
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. More... | |
template<class wType , class matrix > | |
void | graph2matrix (const diGraph< wType > &g, matrix &m) |
Creates the adjacency matrix of the given graph. More... | |
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. More... | |
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. More... | |
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. More... | |
template<class wType > | |
void | transitiveReduction (const diGraph< wType > &g, diGraph< wType > &gRed) |
Computes the transitive reduction of an arbitrary acyclic graph. More... | |
|
inline |
A helper function for "collapseVertices".
Definition at line 44 of file various.h.
Referenced by collapseVertices().
|
inline |
A helper function for "collapseVertices2".
Definition at line 159 of file various.h.
Referenced by collapseVertices2().
|
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 76 of file various.h.
References addRenumEdges().
|
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 202 of file various.h.
References addRenumEdges2().
|
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).
|
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.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Computes the DFS forest.
Considers the vertices in the given order. Saves the numbers of vertices of each tree in 'compVertices', and keeps the one-beyond-the-end offsets of the trees in the table 'compEnds'. Records the connections between the trees in 'scc' (which must be empty when this function is called). If requested, only those single-vertex trees are counted which have an edge that loops back to themselves. Returns the number of trees in the computed forest.
Definition at line 104 of file dfs.h.
Referenced by SCC().
|
inline |
|
inline |
|
inline |
Gets the weights of all the edges at a time.
The weights are put into the table with the [] operator.
Definition at line 56 of file digraphtab.h.
|
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 865 of file various.h.
Referenced by transitiveReduction().
|
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.
|
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 643 of file various.h.
References transpose().
|
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 885 of file various.h.
Referenced by transitiveReduction().
wType cymealg::minMeanCycleWeight | ( | const diGraph< wType > & | g, |
diGraph< wType > * | transposed = 0 |
||
) |
Runs the Karp algorithm for each strongly connected component of the graph and returns the minimum mean cycle weight, which can be negative.
As a byproduct, saves the transposed graph, if requested to.
Definition at line 48 of file cyclemean.h.
References SCC().
Referenced by cymealgTest().
wType cymealg::minMeanCycleWeight | ( | const diGraph< wType > & | g, |
const roundType & | rounding, | ||
diGraph< wType > * | transposed | ||
) |
A version of Karp algorithm modified for the purpose of interval arithmetic to provide the correct lower bound for the minimum mean cycle weight in a graph.
This specialization is necessary, because of the subtraction operation used in Karp's algorithm. Therefore, upper and lower bounds for the minimum path progression weights must be computed independently. The intervals are compared by comparing their lower bounds only.
Definition at line 231 of file cyclemean.h.
References SCC().
wType cymealg::minMeanCycleWeightMem | ( | const diGraph< wType > & | g, |
const roundType & | rounding, | ||
diGraph< wType > * | transposed | ||
) |
A rigorous numerics version of Karp algorithm modified in such a way that the memory usage is minimized, at the cost of slower execution (up to twice slower).
Note that a memory conservative version of the algorithm that uses non-rigorous numerics is not programmed yet.
Definition at line 433 of file cyclemean.h.
References SCC().
Referenced by cymealgTest().
wType cymealg::minMeanPathWeight | ( | const diGraph< wType > & | g, |
const roundType & | rounding, | ||
const arrayType & | starting, | ||
int_t | n | ||
) |
Runs an algorithm based on Karp's idea to compute the minimum mean path weight for paths starting at any of the given n vertices and of length not exceeding the number of vertices in the graph.
Returns 0 if no path starts at any of the vertices.
Definition at line 52 of file pathmean.h.
Referenced by minMeanPathWeight().
wType cymealg::minMeanPathWeight | ( | const diGraph< wType > & | g, |
const arrayType & | starting, | ||
int_t | n | ||
) |
The above algorithm without rounding control.
Definition at line 148 of file pathmean.h.
References minMeanPathWeight().
|
inline |
Writes a graph in the text mode to an output stream.
Definition at line 165 of file readwrite.h.
References write().
|
inline |
No isomorphism check, just comparing with the same order of vertices. Ignores weights.
Definition at line 470 of file digraph.h.
References cymealg::diGraph< wType >::edgeEnds, cymealg::diGraph< wType >::edges, and cymealg::diGraph< wType >::nVertices.
|
inline |
Reads a graph in the text mode from an input stream.
Definition at line 131 of file readwrite.h.
References read().
|
inline |
Reads a graph in the text mode from an input stream.
The graph must be initially empty, or otherwise the graph read from the input stream is appended to the existing graph.
Definition at line 47 of file readwrite.h.
Referenced by cymealgTest(), and operator>>().
|
inline |
Computes strongly connected path 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 59 of file scc.h.
References DFSfinishTime(), DFSforest(), and transpose().
Referenced by minMeanCycleWeight(), and minMeanCycleWeightMem().
|
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.
|
inline |
Sets the weights of all the edges at a time.
The weights are pulled from the table with the [] operator.
Definition at line 45 of file digraphtab.h.
void cymealg::subgraph | ( | const Graph1 & | g, |
Graph2 & | result, | ||
const Table & | tab, | ||
bool | copyweights = false |
||
) |
Computes a restriction of the graph to its subgraph.
The subgraph vertices are defined by nonzero entries in the supplied table. The result must be initially empty.
Definition at line 46 of file subgraph.h.
|
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 903 of file various.h.
Referenced by transitiveReduction().
|
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 927 of file various.h.
Referenced by transitiveReduction().
|
inline |
Computes the transitive reduction of an arbitrary acyclic graph.
The output graph must be initially empty.
Definition at line 946 of file various.h.
References graph2matrix(), matrix2graph(), transitiveClosure(), and transitiveReduction().
|
inline |
Creates a transposed graph.
Definition at line 43 of file transpose.h.
Referenced by inclusionGraph(), and SCC().
|
inline |
Outputs the graph to a text stream in a human-readable format.
Definition at line 140 of file readwrite.h.
Referenced by operator<<().
|
inline |
Fills out a table that represents all the edges of the graph.
The indices of a starting and ending vertex of the n-th edge are written to "tab [n] [0]" and "tab [n] [1]", respectively. The weights are ignored; use "getWeights" to store them separately.
Definition at line 69 of file digraphtab.h.