The CyMeAlg Software (Release 0.01)
|
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... | |
This class defines a weighted directed graph with very limited number of operations.
The graph can be treated as non-weighted if necessary.
typedef wType cymealg::diGraph< wType >::weight_type |
|
inline |
|
inline |
|
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().
|
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.
|
inline |
Adds a vertex.
Definition at line 511 of file digraph.h.
References cymealg::diGraph< wType >::edgeEnds, and cymealg::diGraph< wType >::nVertices.
Referenced by cymealg::diGraph< wType >::DFSforest(), and cymealg::diGraph< wType >::subgraph().
|
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().
|
inline |
The above algorithm without rounding control.
Definition at line 1619 of file digraph.h.
References cymealg::diGraph< wType >::BellmanFord().
|
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.
|
inline |
The above algorithm without rounding control.
Definition at line 1638 of file digraph.h.
References cymealg::diGraph< wType >::BellmanFord().
|
inline |
Returns the number of edges.
Definition at line 631 of file digraph.h.
References cymealg::diGraph< wType >::edgeEnds, and cymealg::diGraph< wType >::nVertices.
Referenced by cymealg::diGraph< wType >::Edmonds(), cymealg::diGraph< wType >::EdmondsOld(), and cymealg::diGraph< wType >::minPathWeight().
|
inline |
Counts the number of edges leaving the given vertex.
Definition at line 640 of file digraph.h.
References cymealg::diGraph< wType >::edgeEnds.
|
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().
|
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().
|
inline |
The recurrent procedure for DFScolor.
Definition at line 758 of file digraph.h.
References cymealg::diGraph< wType >::edgeEnds, and cymealg::diGraph< wType >::edges.
|
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().
|
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.
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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.
|
inline |
The above algorithm without rounding control.
Definition at line 1489 of file digraph.h.
References cymealg::diGraph< wType >::Dijkstra().
|
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.
|
inline |
An old implementation of the Edmonds algorithm (less efficient).
Definition at line 1720 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.
|
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().
|
inline |
The above algorithm without rounding control.
Definition at line 1947 of file digraph.h.
References cymealg::diGraph< wType >::FloydWarshall().
|
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.
|
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.
|
inline |
Retrieves the weight of the given edge.
Definition at line 667 of file digraph.h.
References cymealg::diGraph< wType >::weights.
|
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().
|
inline |
The above algorithm without rounding control.
Definition at line 2119 of file digraph.h.
References cymealg::diGraph< wType >::Johnson().
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().
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().
|
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().
|
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.
|
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.
|
inline |
Sets the weight of the given edge.
Definition at line 566 of file digraph.h.
References cymealg::diGraph< wType >::weights.
|
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().
|
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().
|
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.
|
inline |
Swaps the data with another graph.
Definition at line 501 of file digraph.h.
References cymealg::diGraph< wType >::edgeEnds, cymealg::diGraph< wType >::edges, cymealg::diGraph< wType >::nVertices, and cymealg::diGraph< wType >::weights.
|
inline |
Creates a transposed graph.
Definition at line 675 of file digraph.h.
References cymealg::diGraph< wType >::edgeEnds, cymealg::diGraph< wType >::edges, cymealg::diGraph< wType >::nVertices, and cymealg::diGraph< wType >::weights.
|
protected |
A table with the offsets of the one-after-the-last edge of each vertex.
Definition at line 355 of file digraph.h.
Referenced by cymealg::diGraph< wType >::addEdge(), cymealg::diGraph< wType >::addVertex(), cymealg::diGraph< wType >::BellmanFord(), cymealg::diGraph< wType >::countEdges(), cymealg::diGraph< wType >::DFScolorRecurrent(), cymealg::diGraph< wType >::DFScolorStack(), cymealg::diGraph< wType >::DFSfinishTimeRecurrent(), cymealg::diGraph< wType >::DFSfinishTimeStack(), cymealg::diGraph< wType >::DFSforestRecurrent(), cymealg::diGraph< wType >::DFSforestStack(), cymealg::diGraph< wType >::Dijkstra(), cymealg::diGraph< wType >::Edmonds(), cymealg::diGraph< wType >::EdmondsOld(), cymealg::diGraph< wType >::FloydWarshall(), cymealg::diGraph< wType >::getEdge(), cymealg::diGraph< wType >::getWeight(), cymealg::diGraph< wType >::Johnson(), cymealg::operator==(), cymealg::diGraph< wType >::removeVertex(), cymealg::diGraph< wType >::setWeight(), cymealg::diGraph< wType >::shortestPath(), cymealg::diGraph< wType >::subgraph(), cymealg::diGraph< wType >::swap(), and cymealg::diGraph< wType >::transpose().
|
protected |
A table with edge target numbers.
Definition at line 358 of file digraph.h.
Referenced by cymealg::diGraph< wType >::addEdge(), cymealg::diGraph< wType >::BellmanFord(), cymealg::diGraph< wType >::DFScolorRecurrent(), cymealg::diGraph< wType >::DFScolorStack(), cymealg::diGraph< wType >::DFSfinishTimeRecurrent(), cymealg::diGraph< wType >::DFSfinishTimeStack(), cymealg::diGraph< wType >::DFSforestRecurrent(), cymealg::diGraph< wType >::DFSforestStack(), cymealg::diGraph< wType >::Dijkstra(), cymealg::diGraph< wType >::Edmonds(), cymealg::diGraph< wType >::EdmondsOld(), cymealg::diGraph< wType >::FloydWarshall(), cymealg::diGraph< wType >::getEdge(), cymealg::diGraph< wType >::Johnson(), cymealg::operator==(), cymealg::diGraph< wType >::removeVertex(), cymealg::diGraph< wType >::shortestPath(), cymealg::diGraph< wType >::subgraph(), cymealg::diGraph< wType >::swap(), and cymealg::diGraph< wType >::transpose().
|
protected |
The number of vertices.
Definition at line 351 of file digraph.h.
Referenced by cymealg::diGraph< wType >::addEdge(), cymealg::diGraph< wType >::addVertex(), cymealg::diGraph< wType >::BellmanFord(), cymealg::diGraph< wType >::countEdges(), cymealg::diGraph< wType >::countVertices(), cymealg::diGraph< wType >::DFSfinishTime(), cymealg::diGraph< wType >::DFSforest(), cymealg::diGraph< wType >::Dijkstra(), cymealg::diGraph< wType >::Edmonds(), cymealg::diGraph< wType >::EdmondsOld(), cymealg::diGraph< wType >::FloydWarshall(), cymealg::diGraph< wType >::Johnson(), cymealg::diGraph< wType >::minPathWeight(), cymealg::operator==(), cymealg::diGraph< wType >::removeVertex(), cymealg::diGraph< wType >::shortestPath(), cymealg::diGraph< wType >::subgraph(), cymealg::diGraph< wType >::swap(), and cymealg::diGraph< wType >::transpose().
|
protected |
A table with edge weights.
Definition at line 361 of file digraph.h.
Referenced by cymealg::diGraph< wType >::addEdge(), cymealg::diGraph< wType >::BellmanFord(), cymealg::diGraph< wType >::Dijkstra(), cymealg::diGraph< wType >::Edmonds(), cymealg::diGraph< wType >::EdmondsOld(), cymealg::diGraph< wType >::FloydWarshall(), cymealg::diGraph< wType >::getWeight(), cymealg::diGraph< wType >::Johnson(), cymealg::diGraph< wType >::removeVertex(), cymealg::diGraph< wType >::setWeight(), cymealg::diGraph< wType >::subgraph(), cymealg::diGraph< wType >::swap(), and cymealg::diGraph< wType >::transpose().