The CyMeAlg Software (Release 0.01)
Classes | Functions
cymealg Namespace Reference

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...
 

Function Documentation

◆ addRenumEdges()

template<class wType >
int_t cymealg::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 44 of file various.h.

Referenced by collapseVertices().

◆ addRenumEdges2()

template<class wType , class TabSets >
int_t cymealg::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 159 of file various.h.

Referenced by collapseVertices2().

◆ collapseVertices()

template<class wType , class Table1 , class Table2 >
int_t cymealg::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 76 of file various.h.

References addRenumEdges().

◆ collapseVertices2()

template<class wType , class Table1 , class Table2 >
int_t cymealg::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 202 of file various.h.

References addRenumEdges2().

◆ computePeriod()

template<class GraphType >
int_t cymealg::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).

Definition at line 426 of file various.h.

◆ connectionGraph()

template<class wType >
int_t cymealg::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.

Definition at line 316 of file various.h.

◆ DFScolor()

template<class Graph , class Table , class Color >
void cymealg::DFScolor ( const Graph &  g,
Table &  tab,
const Color &  color,
int_t  vertex = 0 
)
inline

Marks each vertex visited by DFS with the given color, starting with the given vertex.

Runs for one component only. The initial color in 'tab' must be different than the given one.

Definition at line 134 of file dfs.h.

◆ DFScolorRecurrent()

template<class Graph , class Table , class Color >
void cymealg::DFScolorRecurrent ( const Graph &  g,
Table &  tab,
const Color &  color,
int_t  vertex = 0 
)
inline

The recurrent procedure for DFScolor.

Definition at line 114 of file dfs.h.

◆ DFScolorStack()

template<class Graph , class Table , class Color >
void cymealg::DFScolorStack ( const Graph &  g,
Table &  tab,
const Color &  color,
int_t  vertex = 0 
)
inline

A stack version of the recurrent procedure for DFScolor.

Definition at line 123 of file dfs.h.

◆ DFSfinishTime()

template<class Graph , class Table >
void cymealg::DFSfinishTime ( const Graph &  g,
Table &  tab 
)
inline

Computes the DFS finishing time for each vertex.

Note: The time begins with 1, not with 0.

Definition at line 63 of file dfs.h.

Referenced by SCC().

◆ DFSfinishTimeRecurrent()

template<class Graph , class Table >
void cymealg::DFSfinishTimeRecurrent ( const Graph &  g,
Table &  tab,
int_t  vertex,
int_t &  counter 
)
inline

The recurrent procedure for DFSfinishTime.

Definition at line 44 of file dfs.h.

◆ DFSfinishTimeStack()

template<class Graph , class Table >
void cymealg::DFSfinishTimeStack ( const Graph &  g,
Table &  tab,
int_t  vertex,
int_t &  counter 
)
inline

A stack version of the recurrent procedure for DFSfinishTime.

Definition at line 53 of file dfs.h.

◆ DFSforest()

template<class Graph , class Table1 , class Table2 , class Table3 >
int_t cymealg::DFSforest ( const Graph &  g,
const Table1 &  ordered,
Table2 &  compVertices,
Table3 &  compEnds,
bool  nontrivial = false,
Graph *  sccGraph = 0 
)
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().

◆ DFSforestRecurrent()

template<class Graph , class Table1 , class Table2 >
bool cymealg::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 
)
inline

The recurrent procedure for DFSforest.

Returns true iff there is a loop within the tree found.

Definition at line 72 of file dfs.h.

◆ DFSforestStack()

template<class Graph , class Table1 , class Table2 >
bool cymealg::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 
)
inline

A stack version of the recurrent procedure for DFSforest.

Definition at line 84 of file dfs.h.

◆ getWeights()

template<class Graph , class Table >
void cymealg::getWeights ( const Graph &  g,
Table &  tab 
)
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.

◆ graph2matrix()

template<class wType , class matrix >
void cymealg::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 865 of file various.h.

Referenced by transitiveReduction().

◆ inclusionGraph() [1/2]

template<class wType >
int_t cymealg::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.

Definition at line 523 of file various.h.

◆ inclusionGraph() [2/2]

template<class wType , class TConn >
int_t cymealg::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.

Definition at line 643 of file various.h.

References transpose().

◆ matrix2graph()

template<class wType , class matrix >
void cymealg::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 885 of file various.h.

Referenced by transitiveReduction().

◆ minMeanCycleWeight() [1/2]

template<class wType >
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().

◆ minMeanCycleWeight() [2/2]

template<class wType , class roundType >
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().

◆ minMeanCycleWeightMem()

template<class wType , class roundType >
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().

◆ minMeanPathWeight() [1/2]

template<class wType , class arrayType , class roundType >
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().

◆ minMeanPathWeight() [2/2]

template<class wType , class arrayType >
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().

◆ operator!=()

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

Definition at line 492 of file digraph.h.

◆ operator<<()

template<class wType >
std::ostream& cymealg::operator<< ( std::ostream &  out,
const diGraph< wType > &  g 
)
inline

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

Definition at line 165 of file readwrite.h.

References write().

◆ operator==()

template<class wType1 , class wType2 >
bool cymealg::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 470 of file digraph.h.

References cymealg::diGraph< wType >::edgeEnds, cymealg::diGraph< wType >::edges, and cymealg::diGraph< wType >::nVertices.

◆ operator>>()

template<class wType >
std::istream& cymealg::operator>> ( std::istream &  in,
diGraph< wType > &  g 
)
inline

Reads a graph in the text mode from an input stream.

Definition at line 131 of file readwrite.h.

References read().

◆ read()

template<class inType , class Graph >
inType& cymealg::read ( inType &  in,
Graph &  g 
)
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>>().

◆ SCC()

template<class wType , class Table1 , class Table2 >
int_t cymealg::SCC ( const diGraph< wType > &  g,
Table1 &  compVertices,
Table2 &  compEnds,
diGraph< wType > *  scc = 0,
diGraph< wType > *  transposed = 0,
bool  copyweights = false 
)
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().

◆ SCC_Tarjan()

template<class wType , class Table1 , class Table2 >
int_t cymealg::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.

Definition at line 101 of file scc.h.

◆ setWeights()

template<class Graph , class Table >
void cymealg::setWeights ( Graph &  g,
const Table &  tab 
)
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.

◆ subgraph()

template<class Graph1 , class Graph2 , class Table >
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.

◆ transitiveClosure()

template<class matrix >
void cymealg::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 903 of file various.h.

Referenced by transitiveReduction().

◆ transitiveReduction() [1/2]

template<class matrix >
void cymealg::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 927 of file various.h.

Referenced by transitiveReduction().

◆ transitiveReduction() [2/2]

template<class wType >
void cymealg::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 946 of file various.h.

References graph2matrix(), matrix2graph(), transitiveClosure(), and transitiveReduction().

◆ transpose()

template<class Graph1 , class Graph2 >
void cymealg::transpose ( const Graph1 &  g,
Graph2 &  result,
bool  copyweights = false 
)
inline

Creates a transposed graph.

Definition at line 43 of file transpose.h.

Referenced by inclusionGraph(), and SCC().

◆ write()

template<class outType , class Graph >
outType& cymealg::write ( outType &  out,
const Graph &  g,
bool  writeWeights 
)
inline

Outputs the graph to a text stream in a human-readable format.

Definition at line 140 of file readwrite.h.

Referenced by operator<<().

◆ writeEdges()

template<class Graph , class Table >
void cymealg::writeEdges ( const Graph &  g,
Table &  tab 
)
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.