This class defines a directed graph with very limited number of operations, and a few specific algorithms implemented on it, like DFS. More...
#include <chomp/struct/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. | |
Public Member Functions | |
| diGraph () | |
| The default constructor of an empty graph. | |
| ~diGraph () | |
| The destructor. | |
| void | swap (diGraph< wType > &g) |
| Swaps the data with another graph. | |
| void | addVertex (void) |
| Adds a vertex. | |
| void | addEdge (int_t target) |
| Adds an edge starting at the last vertex. | |
| 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. | |
| void | setWeight (int_t vertex, int_t i, const wType &weight) |
| Sets the weight of the given edge. | |
| void | setWeight (int_t edge, const wType &weight) |
| Sets the weight of the given edge. | |
| template<class Table > | |
| void | setWeights (const Table &tab) |
| Sets the weights of all the edges at a time. | |
| void | removeVertex (void) |
| Removes the last vertex and all the edges going out from it. | |
| 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. | |
| int_t | countVertices (void) const |
| Returns the number of vertices. | |
| int_t | countEdges (void) const |
| Returns the number of edges. | |
| int_t | countEdges (int_t vertex) const |
| Counts the number of edges leaving the given vertex. | |
| int_t | getEdge (int_t vertex, int_t i) const |
| Retrieves the given edge that leaves the given vertex. | |
| const wType & | getWeight (int_t vertex, int_t i) const |
| Retrieves the weight of the given edge. | |
| const wType & | getWeight (int_t edge) const |
| Retrieves the weight of the given edge. | |
| template<class Table > | |
| void | getWeights (Table &tab) const |
| Gets the weights of all the edges at a time. | |
| template<class Table > | |
| void | writeEdges (Table &tab) const |
| Fills out a table that represents all the edges of the graph. | |
| template<class wType1 > | |
| void | transpose (diGraph< wType1 > &result, bool copyweights=false) const |
| Creates a transposed graph. | |
| 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. | |
| 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. | |
| template<class Table , class Color > | |
| void | DFScolorRecurrent (Table &tab, const Color &color, int_t vertex=0) const |
| The recurrent procedure for DFScolor. | |
| 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. | |
| template<class Table > | |
| void | DFSfinishTime (Table &tab) const |
| Computes the DFS finishing time for each vertex. | |
| 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. | |
| 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. | |
| int_t | shortestLoop (int_t origin) const |
| Computes the length of the shortest loop from the given vertex to itself. | |
| 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. | |
| 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. | |
| template<class lenTable > | |
| void | Dijkstra (int_t source, lenTable &len) const |
| The above algorithm without rounding control. | |
| 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. | |
| template<class lenTable , class predTable > | |
| bool | BellmanFord (int_t source, lenTable &len, wType *infinity, predTable pred) const |
| The above algorithm without rounding control. | |
| 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. | |
| bool | BellmanFord (int_t source) const |
| The above algorithm without rounding control. | |
| wType | Edmonds () const |
| Runs the Edmonds algorithm to compute the shortest path that runs through all the vertices of the graph. | |
| wType | EdmondsOld () const |
| An old implementation of the Edmonds algorithm (less efficient). | |
| 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. | |
| template<class arrayType > | |
| wType | FloydWarshall (arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const |
| The above algorithm without rounding control. | |
| 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. | |
| template<class arrayType > | |
| wType | Johnson (arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const |
| The above algorithm without rounding control. | |
| 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. | |
| wType | minPathWeight (bool ignoreNegLoop=false, int sparseGraph=-1) const |
| The above algorithm without rounding control. | |
| wType | minMeanCycleWeight (diGraph< wType > *transposed=0) const |
| Runs the Karp algorithm for each strongly connected component of the graph and returns the minimum mean cycle weight, which can be negative. | |
| template<class roundType > | |
| wType | minMeanCycleWeight (const roundType &rounding, diGraph< wType > *transposed) const |
| A version of the above function modified for the purpose of interval arithmetic to provide the correct lower bound for the minimum mean cycle weight in a graph. | |
| template<class arrayType , class roundType > | |
| wType | minMeanPathWeight (const roundType &rounding, const arrayType &starting, int_t n) const |
| 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. | |
| template<class arrayType > | |
| wType | minMeanPathWeight (const arrayType &starting, int_t n) const |
| The above algorithm without rounding control. | |
| template<class outType > | |
| outType & | show (outType &out, bool showWeights=false) const |
| Outputs the graph to a text stream in a human-readable format. | |
Protected Attributes | |
| int_t | nVertices |
| The number of vertices. | |
| multitable< int_t > | edgeEnds |
| A table with the offsets of the one-after-the-last edge of each vertex. | |
| multitable< int_t > | edges |
| A table with edge target numbers. | |
| multitable< wType > | weights |
| A table with edge weights. | |
Private Member Functions | |
| template<class Table > | |
| void | DFSfinishTimeRecurrent (Table &tab, int_t vertex, int_t &counter) const |
| The recurrent procedure for DFSfinishTime. | |
| template<class Table > | |
| void | DFSfinishTimeStack (Table &tab, int_t vertex, int_t &counter) const |
| A stack version of the recurrent procedure for DFSfinishTime. | |
| 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. | |
| 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. | |
Friends | |
| template<class wType1 , class wType2 > | |
| bool | operator== (const diGraph< wType1 > &g1, const diGraph< wType2 > &g2) |
| Operator == for comparing digraphs. | |
This class defines a directed graph with very limited number of operations, and a few specific algorithms implemented on it, like DFS.
The graph can be treated as weighted if necessary.
Definition at line 143 of file digraph.h.
| typedef wType chomp::homology::diGraph< wType >::weight_type |
| chomp::homology::diGraph< wType >::diGraph | ( | ) | [inline] |
| chomp::homology::diGraph< wType >::~diGraph | ( | ) | [inline] |
| void chomp::homology::diGraph< wType >::addEdge | ( | int_t | target ) | [inline] |
| void chomp::homology::diGraph< wType >::addEdge | ( | int_t | target, |
| const wType & | weight | ||
| ) | [inline] |
| void chomp::homology::diGraph< wType >::addVertex | ( | void | ) | [inline] |
| bool chomp::homology::diGraph< wType >::BellmanFord | ( | const roundType & | rounding, |
| int_t | source | ||
| ) | const [inline] |
| bool chomp::homology::diGraph< wType >::BellmanFord | ( | int_t | source ) | const [inline] |
| bool chomp::homology::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.
| bool chomp::homology::diGraph< wType >::BellmanFord | ( | int_t | source, |
| lenTable & | len, | ||
| wType * | infinity, | ||
| predTable | pred | ||
| ) | const [inline] |
| int_t chomp::homology::diGraph< wType >::countEdges | ( | void | ) | const [inline] |
| int_t chomp::homology::diGraph< wType >::countEdges | ( | int_t | vertex ) | const [inline] |
| int_t chomp::homology::diGraph< wType >::countVertices | ( | void | ) | const [inline] |
| void chomp::homology::diGraph< wType >::DFScolor | ( | Table & | tab, |
| const Color & | color, | ||
| int_t | vertex = 0 |
||
| ) | const [inline] |
| void chomp::homology::diGraph< wType >::DFScolorRecurrent | ( | Table & | tab, |
| const Color & | color, | ||
| int_t | vertex = 0 |
||
| ) | const [inline] |
| void chomp::homology::diGraph< wType >::DFScolorStack | ( | Table & | tab, |
| const Color & | color, | ||
| int_t | vertex = 0 |
||
| ) | const [inline] |
| void chomp::homology::diGraph< wType >::DFSfinishTime | ( | Table & | tab ) | const [inline] |
| void chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent | ( | Table & | tab, |
| int_t | vertex, | ||
| int_t & | counter | ||
| ) | const [inline, private] |
| void chomp::homology::diGraph< wType >::DFSfinishTimeStack | ( | Table & | tab, |
| int_t | vertex, | ||
| int_t & | counter | ||
| ) | const [inline, private] |
| int_t chomp::homology::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.
| bool chomp::homology::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, private] |
| bool chomp::homology::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, private] |
| void chomp::homology::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.
| void chomp::homology::diGraph< wType >::Dijkstra | ( | int_t | source, |
| lenTable & | len | ||
| ) | const [inline] |
| void chomp::homology::diGraph< wType >::Dijkstra | ( | const roundType & | rounding, |
| int_t | source, | ||
| lenTable & | len | ||
| ) | const [inline] |
| wType chomp::homology::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.
| wType chomp::homology::diGraph< wType >::EdmondsOld | ( | ) | const [inline] |
| wType chomp::homology::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".
| wType chomp::homology::diGraph< wType >::FloydWarshall | ( | arrayType & | arr, |
| bool | setInfinity = true, |
||
| bool | ignoreNegLoop = false |
||
| ) | const [inline] |
| int_t chomp::homology::diGraph< wType >::getEdge | ( | int_t | vertex, |
| int_t | i | ||
| ) | const [inline] |
| const wType & chomp::homology::diGraph< wType >::getWeight | ( | int_t | vertex, |
| int_t | i | ||
| ) | const [inline] |
| const wType & chomp::homology::diGraph< wType >::getWeight | ( | int_t | edge ) | const [inline] |
| void chomp::homology::diGraph< wType >::getWeights | ( | Table & | tab ) | const [inline] |
| wType chomp::homology::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'.
| wType chomp::homology::diGraph< wType >::Johnson | ( | arrayType & | arr, |
| bool | setInfinity = true, |
||
| bool | ignoreNegLoop = false |
||
| ) | const [inline] |
| wType chomp::homology::diGraph< wType >::minMeanCycleWeight | ( | diGraph< wType > * | transposed = 0 ) |
const |
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 2593 of file digraph.h.
References chomp::homology::SCC().
| wType chomp::homology::diGraph< wType >::minMeanCycleWeight | ( | const roundType & | rounding, |
| diGraph< wType > * | transposed | ||
| ) | const |
A version of the above function 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 2740 of file digraph.h.
References chomp::homology::SCC().
| wType chomp::homology::diGraph< wType >::minMeanPathWeight | ( | const roundType & | rounding, |
| const arrayType & | starting, | ||
| int_t | n | ||
| ) | const |
| wType chomp::homology::diGraph< wType >::minMeanPathWeight | ( | const arrayType & | starting, |
| int_t | n | ||
| ) | const |
| wType chomp::homology::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.
| wType chomp::homology::diGraph< wType >::minPathWeight | ( | bool | ignoreNegLoop = false, |
| int | sparseGraph = -1 |
||
| ) | const |
| void chomp::homology::diGraph< wType >::removeVertex | ( | int_t | vertex, |
| bool | updateweights = false |
||
| ) | [inline] |
| void chomp::homology::diGraph< wType >::removeVertex | ( | void | ) | [inline] |
| void chomp::homology::diGraph< wType >::setWeight | ( | int_t | vertex, |
| int_t | i, | ||
| const wType & | weight | ||
| ) | [inline] |
| void chomp::homology::diGraph< wType >::setWeight | ( | int_t | edge, |
| const wType & | weight | ||
| ) | [inline] |
| void chomp::homology::diGraph< wType >::setWeights | ( | const Table & | tab ) | [inline] |
| int_t chomp::homology::diGraph< wType >::shortestLoop | ( | int_t | origin ) | const [inline] |
| int_t chomp::homology::diGraph< wType >::shortestPath | ( | int_t | source, |
| int_t | destination | ||
| ) | const [inline] |
| outType & chomp::homology::diGraph< wType >::show | ( | outType & | out, |
| bool | showWeights = false |
||
| ) | const [inline] |
| void chomp::homology::diGraph< wType >::subgraph | ( | diGraph< wType1 > & | result, |
| const Table & | tab, | ||
| bool | copyweights = false |
||
| ) | const [inline] |
| void chomp::homology::diGraph< wType >::swap | ( | diGraph< wType > & | g ) | [inline] |
| void chomp::homology::diGraph< wType >::transpose | ( | diGraph< wType1 > & | result, |
| bool | copyweights = false |
||
| ) | const [inline] |
| void chomp::homology::diGraph< wType >::writeEdges | ( | Table & | tab ) | const [inline] |
multitable<int_t> chomp::homology::diGraph< wType >::edgeEnds [protected] |
multitable<int_t> chomp::homology::diGraph< wType >::edges [protected] |
int_t chomp::homology::diGraph< wType >::nVertices [protected] |
multitable<wType> chomp::homology::diGraph< wType >::weights [protected] |
1.7.2