The CyMeAlg Software (Release 0.01)
Classes | Public Types | Public Member Functions | Protected Attributes | Friends | List of all members
cymealg::diGraph< wType > Class Template Reference

This class defines a weighted directed graph with very limited number of operations. More...

#include <digraph.h>

Classes

struct  edgeTriple
 An edge with a weight (used by the Edmonds algorithm). More...
 
class  posWeight
 A class for representing a positive number with negative values serving as the infinity (used in the Dijkstra algorithm). More...
 

Public Types

typedef wType weight_type
 The type of the weight of edges. More...
 

Public Member Functions

 diGraph ()
 The default constructor of an empty graph. More...
 
 ~diGraph ()
 The destructor. More...
 
void swap (diGraph< wType > &g)
 Swaps the data with another graph. More...
 
void addVertex (void)
 Adds a vertex. More...
 
void addEdge (int_t target)
 Adds an edge starting at the last vertex. More...
 
void addEdge (int_t target, const wType &weight)
 Adds an edge from the last vertex to the given one and sets the weight of this edge. More...
 
void setWeight (int_t vertex, int_t i, const wType &weight)
 Sets the weight of the given edge. More...
 
void setWeight (int_t edge, const wType &weight)
 Sets the weight of the given edge. More...
 
void removeVertex (void)
 Removes the last vertex and all the edges going out from it. More...
 
void removeVertex (int_t vertex, bool updateweights=false)
 Removes the given vertex and all the edges going out from it, as well as the edges going towards it. More...
 
int_t countVertices (void) const
 Returns the number of vertices. More...
 
int_t countEdges (void) const
 Returns the number of edges. More...
 
int_t countEdges (int_t vertex) const
 Counts the number of edges leaving the given vertex. More...
 
int_t getEdge (int_t vertex, int_t i) const
 Retrieves the given edge that leaves the given vertex. More...
 
const wType & getWeight (int_t vertex, int_t i) const
 Retrieves the weight of the given edge. More...
 
const wType & getWeight (int_t edge) const
 Retrieves the weight of the given edge. More...
 
template<class wType1 >
void transpose (diGraph< wType1 > &result, bool copyweights=false) const
 Creates a transposed graph. More...
 
template<class Table , class wType1 >
void subgraph (diGraph< wType1 > &result, const Table &tab, bool copyweights=false) const
 Computes a restriction of the graph to its subgraph. More...
 
template<class Table >
void DFSfinishTimeRecurrent (Table &tab, int_t vertex, int_t &counter) const
 The recurrent procedure for DFSfinishTime. More...
 
template<class Table >
void DFSfinishTimeStack (Table &tab, int_t vertex, int_t &counter) const
 A stack version of the recurrent procedure for DFSfinishTime. More...
 
template<class Table >
void DFSfinishTime (Table &tab) const
 Computes the DFS finishing time for each vertex. More...
 
template<class Table1 , class Table2 >
bool DFSforestRecurrent (Table1 &tab, Table1 &ntab, int_t vertex, int_t treeNumber, int_t countTrees, Table2 &compVertices, int_t &curVertex, diGraph *sccGraph, int_t *sccEdgeAdded) const
 The recurrent procedure for DFSforest. More...
 
template<class Table1 , class Table2 >
bool DFSforestStack (Table1 &tab, Table1 &ntab, int_t vertex, int_t treeNumber, int_t countTrees, Table2 &compVertices, int_t &curVertex, diGraph *sccGraph, int_t *sccEdgeAdded) const
 A stack version of the recurrent procedure for DFSforest. More...
 
template<class Table1 , class Table2 , class Table3 >
int_t DFSforest (const Table1 &ordered, Table2 &compVertices, Table3 &compEnds, bool nontrivial=false, diGraph< wType > *sccGraph=0) const
 Computes the DFS forest. More...
 
template<class Table , class Color >
void DFScolorRecurrent (Table &tab, const Color &color, int_t vertex=0) const
 The recurrent procedure for DFScolor. More...
 
template<class Table , class Color >
void DFScolorStack (Table &tab, const Color &color, int_t vertex=0) const
 A stack version of the recurrent procedure for DFScolor. More...
 
template<class Table , class Color >
void DFScolor (Table &tab, const Color &color, int_t vertex=0) const
 Marks each vertex visited by DFS with the given color, starting with the given vertex. More...
 
int_t shortestPath (int_t source, int_t destination) const
 Computes the length of the shortest nontrivial path from the given vertex to another one. More...
 
int_t shortestLoop (int_t origin) const
 Computes the length of the shortest loop from the given vertex to itself. More...
 
template<class lenTable , class weightsType , class roundType >
void Dijkstra (const roundType &rounding, int_t source, lenTable &len, weightsType &edgeWeights) const
 Dijkstra's algorithm for solving the single-source shortest paths problem if all the edge weights are nonnegative. More...
 
template<class lenTable , class roundType >
void Dijkstra (const roundType &rounding, int_t source, lenTable &len) const
 Dijkstra's algorithm running on the graph's own weights. More...
 
template<class lenTable >
void Dijkstra (int_t source, lenTable &len) const
 The above algorithm without rounding control. More...
 
template<class lenTable , class predTable , class roundType >
bool BellmanFord (const roundType &rounding, int_t source, lenTable &len, wType *infinity, predTable pred) const
 Runs the Bellman-Ford algorithm which computes the single-source shortest paths in a weighted directed graph, where some edge weights may be negative. More...
 
template<class lenTable , class predTable >
bool BellmanFord (int_t source, lenTable &len, wType *infinity, predTable pred) const
 The above algorithm without rounding control. More...
 
template<class roundType >
bool BellmanFord (const roundType &rounding, int_t source) const
 Runs the Bellman-Ford algorithm (see above) without storing the distances, only returns the information about the existence of a negative-weight cycle. More...
 
bool BellmanFord (int_t source) const
 The above algorithm without rounding control. More...
 
wType Edmonds () const
 Runs the Edmonds algorithm to compute the shortest path that runs through all the vertices of the graph. More...
 
wType EdmondsOld () const
 An old implementation of the Edmonds algorithm (less efficient). More...
 
template<class arrayType , class roundType >
wType FloydWarshall (const roundType &rounding, arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const
 Runs the Floyd-Warshall algorithm to compute the shortest paths between all pairs of vertices in the graph. More...
 
template<class arrayType >
wType FloydWarshall (arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const
 The above algorithm without rounding control. More...
 
template<class arrayType , class roundType >
wType Johnson (const roundType &rounding, arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const
 Runs Johnson's algorithm to compute the minimum path weight between any vertices in the graph. More...
 
template<class arrayType >
wType Johnson (arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const
 The above algorithm without rounding control. More...
 
template<class roundType >
wType minPathWeight (const roundType &rounding, bool ignoreNegLoop=false, int sparseGraph=-1) const
 Uses the Floyd-Warshall algorithm or Johnson's algorithm, depending on the number of edges, to compute the minimum path weight between any vertices in the graph. More...
 
wType minPathWeight (bool ignoreNegLoop=false, int sparseGraph=-1) const
 The above algorithm without rounding control. More...
 

Protected Attributes

int_t nVertices
 The number of vertices. More...
 
chomp::homology::multitable< int_t > edgeEnds
 A table with the offsets of the one-after-the-last edge of each vertex. More...
 
chomp::homology::multitable< int_t > edges
 A table with edge target numbers. More...
 
chomp::homology::multitable< wType > weights
 A table with edge weights. More...
 

Friends

template<class wType1 , class wType2 >
bool operator== (const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
 Operator == for comparing digraphs. More...
 

Detailed Description

template<class wType = int>
class cymealg::diGraph< wType >

This class defines a weighted directed graph with very limited number of operations.

The graph can be treated as non-weighted if necessary.

Definition at line 75 of file digraph.h.

Member Typedef Documentation

◆ weight_type

template<class wType = int>
typedef wType cymealg::diGraph< wType >::weight_type

The type of the weight of edges.

Definition at line 79 of file digraph.h.

Constructor & Destructor Documentation

◆ diGraph()

template<class wType >
cymealg::diGraph< wType >::diGraph ( )
inline

The default constructor of an empty graph.

Note: The default copy constructor and assignment operator generated by the compiler are good for copying graphs.

Definition at line 455 of file digraph.h.

◆ ~diGraph()

template<class wType >
cymealg::diGraph< wType >::~diGraph ( )
inline

The destructor.

Definition at line 462 of file digraph.h.

Member Function Documentation

◆ addEdge() [1/2]

template<class wType >
void cymealg::diGraph< wType >::addEdge ( int_t  target)
inline

Adds an edge starting at the last vertex.

Note: The range of the target vertex number is not verified.

Definition at line 520 of file digraph.h.

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

Referenced by cymealg::diGraph< wType >::DFSforestRecurrent(), cymealg::diGraph< wType >::DFSforestStack(), and cymealg::diGraph< wType >::subgraph().

◆ addEdge() [2/2]

template<class wType >
void cymealg::diGraph< wType >::addEdge ( int_t  target,
const wType &  weight 
)
inline

Adds an edge from the last vertex to the given one and sets the weight of this edge.

Definition at line 537 of file digraph.h.

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

◆ addVertex()

template<class wType >
void cymealg::diGraph< wType >::addVertex ( void  )
inline

◆ BellmanFord() [1/4]

template<class wType >
template<class lenTable , class predTable , class roundType >
bool cymealg::diGraph< wType >::BellmanFord ( const roundType &  rounding,
int_t  source,
lenTable &  len,
wType *  infinity,
predTable  pred 
) const
inline

Runs the Bellman-Ford algorithm which computes the single-source shortest paths in a weighted directed graph, where some edge weights may be negative.

Runs in O(V*E). The table 'len' is used to store the path lengths during the computations and contains the final result. The number for infinity is set to indicate unreachable vertices. The table with predecessors allows to retrieve shortest paths; this must be a pointer to an array-like structure, e.g., int **. To ignore this data, use an object of the 'dummyArray' class. Returns true if successful, false if a negative cycle is found.

Definition at line 1498 of file digraph.h.

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

Referenced by cymealg::diGraph< wType >::BellmanFord().

◆ BellmanFord() [2/4]

template<class wType >
template<class lenTable , class predTable >
bool cymealg::diGraph< wType >::BellmanFord ( int_t  source,
lenTable &  len,
wType *  infinity,
predTable  pred 
) const
inline

The above algorithm without rounding control.

Definition at line 1619 of file digraph.h.

References cymealg::diGraph< wType >::BellmanFord().

◆ BellmanFord() [3/4]

template<class wType >
template<class roundType >
bool cymealg::diGraph< wType >::BellmanFord ( const roundType &  rounding,
int_t  source 
) const
inline

Runs the Bellman-Ford algorithm (see above) without storing the distances, only returns the information about the existence of a negative-weight cycle.

Definition at line 1627 of file digraph.h.

References cymealg::diGraph< wType >::BellmanFord(), and cymealg::diGraph< wType >::nVertices.

◆ BellmanFord() [4/4]

template<class wType >
bool cymealg::diGraph< wType >::BellmanFord ( int_t  source) const
inline

The above algorithm without rounding control.

Definition at line 1638 of file digraph.h.

References cymealg::diGraph< wType >::BellmanFord().

◆ countEdges() [1/2]

template<class wType >
int_t cymealg::diGraph< wType >::countEdges ( void  ) const
inline

◆ countEdges() [2/2]

template<class wType >
int_t cymealg::diGraph< wType >::countEdges ( int_t  vertex) const
inline

Counts the number of edges leaving the given vertex.

Definition at line 640 of file digraph.h.

References cymealg::diGraph< wType >::edgeEnds.

◆ countVertices()

template<class wType >
int_t cymealg::diGraph< wType >::countVertices ( void  ) const
inline

Returns the number of vertices.

Definition at line 625 of file digraph.h.

References cymealg::diGraph< wType >::nVertices.

Referenced by cymealg::diGraph< wType >::minPathWeight().

◆ DFScolor()

template<class wType >
template<class Table , class Color >
void cymealg::diGraph< wType >::DFScolor ( Table &  tab,
const Color &  color,
int_t  vertex = 0 
) const
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 834 of file digraph.h.

References cymealg::diGraph< wType >::DFScolorStack().

◆ DFScolorRecurrent()

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

The recurrent procedure for DFScolor.

Definition at line 758 of file digraph.h.

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

◆ DFScolorStack()

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

A stack version of the recurrent procedure for DFScolor.

Definition at line 774 of file digraph.h.

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

Referenced by cymealg::diGraph< wType >::DFScolor().

◆ DFSfinishTime()

template<class wType >
template<class Table >
void cymealg::diGraph< wType >::DFSfinishTime ( Table &  tab) const
inline

Computes the DFS finishing time for each vertex.

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

Definition at line 932 of file digraph.h.

References cymealg::diGraph< wType >::DFSfinishTimeRecurrent(), cymealg::diGraph< wType >::DFSfinishTimeStack(), and cymealg::diGraph< wType >::nVertices.

◆ DFSfinishTimeRecurrent()

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

The recurrent procedure for DFSfinishTime.

Definition at line 844 of file digraph.h.

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

Referenced by cymealg::diGraph< wType >::DFSfinishTime().

◆ DFSfinishTimeStack()

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

A stack version of the recurrent procedure for DFSfinishTime.

Definition at line 866 of file digraph.h.

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

Referenced by cymealg::diGraph< wType >::DFSfinishTime().

◆ DFSforest()

template<class wType >
template<class Table1 , class Table2 , class Table3 >
int_t cymealg::diGraph< wType >::DFSforest ( const Table1 &  ordered,
Table2 &  compVertices,
Table3 &  compEnds,
bool  nontrivial = false,
diGraph< wType > *  sccGraph = 0 
) const
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 1128 of file digraph.h.

References cymealg::diGraph< wType >::addVertex(), cymealg::diGraph< wType >::DFSforestRecurrent(), cymealg::diGraph< wType >::DFSforestStack(), cymealg::diGraph< wType >::nVertices, and cymealg::diGraph< wType >::removeVertex().

◆ DFSforestRecurrent()

template<class wType >
template<class Table1 , class Table2 >
bool cymealg::diGraph< wType >::DFSforestRecurrent ( Table1 &  tab,
Table1 &  ntab,
int_t  vertex,
int_t  treeNumber,
int_t  countTrees,
Table2 &  compVertices,
int_t &  curVertex,
diGraph< wType > *  sccGraph,
int_t *  sccEdgeAdded 
) const
inline

The recurrent procedure for DFSforest.

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

Definition at line 975 of file digraph.h.

References cymealg::diGraph< wType >::addEdge(), cymealg::diGraph< wType >::edgeEnds, and cymealg::diGraph< wType >::edges.

Referenced by cymealg::diGraph< wType >::DFSforest().

◆ DFSforestStack()

template<class wType >
template<class Table1 , class Table2 >
bool cymealg::diGraph< wType >::DFSforestStack ( Table1 &  tab,
Table1 &  ntab,
int_t  vertex,
int_t  treeNumber,
int_t  countTrees,
Table2 &  compVertices,
int_t &  curVertex,
diGraph< wType > *  sccGraph,
int_t *  sccEdgeAdded 
) const
inline

A stack version of the recurrent procedure for DFSforest.

Definition at line 1028 of file digraph.h.

References cymealg::diGraph< wType >::addEdge(), cymealg::diGraph< wType >::edgeEnds, and cymealg::diGraph< wType >::edges.

Referenced by cymealg::diGraph< wType >::DFSforest().

◆ Dijkstra() [1/3]

template<class wType >
template<class lenTable , class weightsType , class roundType >
void cymealg::diGraph< wType >::Dijkstra ( const roundType &  rounding,
int_t  source,
lenTable &  len,
weightsType &  edgeWeights 
) const
inline

Dijkstra's algorithm for solving the single-source shortest paths problem if all the edge weights are nonnegative.

The table 'len' is used to store the path lengths during the computations and contains the final result. A negative value stands for the infinity (no path to the given vertex). This is a special version that uses the given edge weights instead of the weights contained in the definition of the graph.

Definition at line 1413 of file digraph.h.

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

Referenced by cymealg::diGraph< wType >::Dijkstra(), and cymealg::diGraph< wType >::Johnson().

◆ Dijkstra() [2/3]

template<class wType >
template<class lenTable , class roundType >
void cymealg::diGraph< wType >::Dijkstra ( const roundType &  rounding,
int_t  source,
lenTable &  len 
) const
inline

Dijkstra's algorithm running on the graph's own weights.

Definition at line 1480 of file digraph.h.

References cymealg::diGraph< wType >::Dijkstra(), and cymealg::diGraph< wType >::weights.

◆ Dijkstra() [3/3]

template<class wType >
template<class lenTable >
void cymealg::diGraph< wType >::Dijkstra ( int_t  source,
lenTable &  len 
) const
inline

The above algorithm without rounding control.

Definition at line 1489 of file digraph.h.

References cymealg::diGraph< wType >::Dijkstra().

◆ Edmonds()

template<class wType >
wType cymealg::diGraph< wType >::Edmonds ( ) const
inline

Runs the Edmonds algorithm to compute the shortest path that runs through all the vertices of the graph.

Computation time: O (n log n). The length of the path is measured as the sum of the weights of the edges. The path does not contain any loops. The graph should be strongly connected.

Definition at line 1645 of file digraph.h.

References cymealg::diGraph< wType >::countEdges(), cymealg::diGraph< wType >::edgeEnds, cymealg::diGraph< wType >::edges, cymealg::diGraph< wType >::nVertices, and cymealg::diGraph< wType >::weights.

◆ EdmondsOld()

template<class wType >
wType cymealg::diGraph< wType >::EdmondsOld ( ) const
inline

◆ FloydWarshall() [1/2]

template<class wType >
template<class arrayType , class roundType >
wType cymealg::diGraph< wType >::FloydWarshall ( const roundType &  rounding,
arrayType &  arr,
bool  setInfinity = true,
bool  ignoreNegLoop = false 
) const
inline

Runs the Floyd-Warshall algorithm to compute the shortest paths between all pairs of vertices in the graph.

The position [i] [j] of the array contains the length of the shortest path from vertex i to vertex j. Provides a rigorous lower bound in interval arithmetic, provided that intervals are compared with "<" and "<=" by comparing their lower ends only. If "setInfinity" is "true", then computes a value that serves as the infinity, fills in the corresponding entries in "arr", and returns this value. Otherwise, returns the length of the shortest path. In this case, arr [i] [j] is undefined if there is no path i -> j. Throws an error message if a negative loop is found, unless "ignoreNegLoop" is set to "true".

Definition at line 1799 of file digraph.h.

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

Referenced by cymealg::diGraph< wType >::FloydWarshall(), cymealg::diGraph< wType >::Johnson(), and cymealg::diGraph< wType >::minPathWeight().

◆ FloydWarshall() [2/2]

template<class wType >
template<class arrayType >
wType cymealg::diGraph< wType >::FloydWarshall ( arrayType &  arr,
bool  setInfinity = true,
bool  ignoreNegLoop = false 
) const
inline

The above algorithm without rounding control.

Definition at line 1947 of file digraph.h.

References cymealg::diGraph< wType >::FloydWarshall().

◆ getEdge()

template<class wType >
int_t cymealg::diGraph< wType >::getEdge ( int_t  vertex,
int_t  i 
) const
inline

Retrieves the given edge that leaves the given vertex.

Definition at line 649 of file digraph.h.

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

◆ getWeight() [1/2]

template<class wType >
const wType & cymealg::diGraph< wType >::getWeight ( int_t  vertex,
int_t  i 
) const
inline

Retrieves the weight of the given edge.

Definition at line 658 of file digraph.h.

References cymealg::diGraph< wType >::edgeEnds, and cymealg::diGraph< wType >::weights.

◆ getWeight() [2/2]

template<class wType >
const wType & cymealg::diGraph< wType >::getWeight ( int_t  edge) const
inline

Retrieves the weight of the given edge.

Definition at line 667 of file digraph.h.

References cymealg::diGraph< wType >::weights.

◆ Johnson() [1/2]

template<class wType >
template<class arrayType , class roundType >
wType cymealg::diGraph< wType >::Johnson ( const roundType &  rounding,
arrayType &  arr,
bool  setInfinity = true,
bool  ignoreNegLoop = false 
) const
inline

Runs Johnson's algorithm to compute the minimum path weight between any vertices in the graph.

The time complexity of this algorithm is essentially O (V^2 log V + VE log V), which is better than the complexity of the Warshall-Floyd algorithm for sparse graphs, that is, graphs in which the number of edges E is of order smaller than V^2. The meaning of the arguments and the returned value is the same as in 'FloydWarshall'.

Definition at line 1956 of file digraph.h.

References cymealg::diGraph< wType >::Dijkstra(), cymealg::diGraph< wType >::edgeEnds, cymealg::diGraph< wType >::edges, cymealg::diGraph< wType >::FloydWarshall(), cymealg::diGraph< wType >::nVertices, and cymealg::diGraph< wType >::weights.

Referenced by cymealg::diGraph< wType >::Johnson(), and cymealg::diGraph< wType >::minPathWeight().

◆ Johnson() [2/2]

template<class wType >
template<class arrayType >
wType cymealg::diGraph< wType >::Johnson ( arrayType &  arr,
bool  setInfinity = true,
bool  ignoreNegLoop = false 
) const
inline

The above algorithm without rounding control.

Definition at line 2119 of file digraph.h.

References cymealg::diGraph< wType >::Johnson().

◆ minPathWeight() [1/2]

template<class wType >
template<class roundType >
wType cymealg::diGraph< wType >::minPathWeight ( const roundType &  rounding,
bool  ignoreNegLoop = false,
int  sparseGraph = -1 
) const

Uses the Floyd-Warshall algorithm or Johnson's algorithm, depending on the number of edges, to compute the minimum path weight between any vertices in the graph.

Throws an error message if a negative loop exists in the graph, unless "ignoreNegLoop" is set to "true". To force the use of Johnson's algorithm, set "sparseGraph" to 1, to force the use of Warshall-Floyd, set "sparseGraph" to 0, otherwise it will be determined heuristically which algorithm should be used.

Definition at line 2128 of file digraph.h.

References cymealg::diGraph< wType >::countEdges(), cymealg::diGraph< wType >::countVertices(), cymealg::diGraph< wType >::FloydWarshall(), cymealg::diGraph< wType >::Johnson(), and cymealg::diGraph< wType >::nVertices.

Referenced by cymealg::diGraph< wType >::minPathWeight().

◆ minPathWeight() [2/2]

template<class wType >
wType cymealg::diGraph< wType >::minPathWeight ( bool  ignoreNegLoop = false,
int  sparseGraph = -1 
) const

The above algorithm without rounding control.

Definition at line 2182 of file digraph.h.

References cymealg::diGraph< wType >::minPathWeight().

◆ removeVertex() [1/2]

template<class wType >
void cymealg::diGraph< wType >::removeVertex ( void  )
inline

Removes the last vertex and all the edges going out from it.

This is done in the time O(1).

Definition at line 573 of file digraph.h.

References cymealg::diGraph< wType >::nVertices.

Referenced by cymealg::diGraph< wType >::DFSforest().

◆ removeVertex() [2/2]

template<class wType >
void cymealg::diGraph< wType >::removeVertex ( int_t  vertex,
bool  updateweights = false 
)
inline

Removes the given vertex and all the edges going out from it, as well as the edges going towards it.

If requested, the weights in the graph are also updated. This function might be slow - it is done in the time O(V+E).

Definition at line 582 of file digraph.h.

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

◆ setWeight() [1/2]

template<class wType >
void cymealg::diGraph< wType >::setWeight ( int_t  vertex,
int_t  i,
const wType &  weight 
)
inline

Sets the weight of the given edge.

Definition at line 555 of file digraph.h.

References cymealg::diGraph< wType >::edgeEnds, and cymealg::diGraph< wType >::weights.

◆ setWeight() [2/2]

template<class wType >
void cymealg::diGraph< wType >::setWeight ( int_t  edge,
const wType &  weight 
)
inline

Sets the weight of the given edge.

Definition at line 566 of file digraph.h.

References cymealg::diGraph< wType >::weights.

◆ shortestLoop()

template<class wType >
int_t cymealg::diGraph< wType >::shortestLoop ( int_t  origin) const
inline

Computes the length of the shortest loop from the given vertex to itself.

The length is measured by counting edges on the way. Uses a stack version of the BFS algorithm. Returns the length of the loop or 0 if none.

Definition at line 1406 of file digraph.h.

References cymealg::diGraph< wType >::shortestPath().

◆ shortestPath()

template<class wType >
int_t cymealg::diGraph< wType >::shortestPath ( int_t  source,
int_t  destination 
) const
inline

Computes the length of the shortest nontrivial path from the given vertex to another one.

The length is measured by counting edges. Uses a stack version of the BFS algorithm. Returns the length of the path or 0 if none.

Definition at line 1326 of file digraph.h.

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

Referenced by cymealg::diGraph< wType >::shortestLoop().

◆ subgraph()

template<class wType >
template<class Table , class wType1 >
void cymealg::diGraph< wType >::subgraph ( diGraph< wType1 > &  result,
const Table &  tab,
bool  copyweights = false 
) const
inline

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 713 of file digraph.h.

References cymealg::diGraph< wType >::addEdge(), cymealg::diGraph< wType >::addVertex(), cymealg::diGraph< wType >::edgeEnds, cymealg::diGraph< wType >::edges, cymealg::diGraph< wType >::nVertices, and cymealg::diGraph< wType >::weights.

◆ swap()

template<class wType >
void cymealg::diGraph< wType >::swap ( diGraph< wType > &  g)
inline

◆ transpose()

template<class wType >
template<class wType1 >
void cymealg::diGraph< wType >::transpose ( diGraph< wType1 > &  result,
bool  copyweights = false 
) const
inline

Friends And Related Function Documentation

◆ operator==

template<class wType = int>
template<class wType1 , class wType2 >
bool operator== ( const diGraph< wType1 > &  g1,
const diGraph< wType2 > &  g2 
)
friend

Operator == for comparing digraphs.

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

Definition at line 470 of file digraph.h.

Member Data Documentation

◆ edgeEnds

template<class wType = int>
chomp::homology::multitable<int_t> cymealg::diGraph< wType >::edgeEnds
protected

◆ edges

template<class wType = int>
chomp::homology::multitable<int_t> cymealg::diGraph< wType >::edges
protected

◆ nVertices

template<class wType = int>
int_t cymealg::diGraph< wType >::nVertices
protected

◆ weights

template<class wType = int>
chomp::homology::multitable<wType> cymealg::diGraph< wType >::weights
protected

The documentation for this class was generated from the following file: