#include <chomp/struct/digraph.h>
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 target) |
Adds an edge starting at the last vertex. | |
void | addEdge (int 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 vertex, int i, const wType &weight) |
Sets the weight of the given edge. | |
void | setWeight (int 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 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 | countVertices (void) const |
Returns the number of vertices. | |
int | countEdges (void) const |
Returns the number of edges. | |
int | countEdges (int vertex) const |
Counts the number of edges leaving the given vertex. | |
int | getEdge (int vertex, int i) const |
Retrieves the given edge that leaves the given vertex. | |
const wType & | getWeight (int vertex, int i) const |
Retrieves the weight of the given edge. | |
const wType & | getWeight (int 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. | |
void | writeEdges (int(*table)[2]) 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 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 vertex=0) const |
The recurrent procedure for DFScolor. | |
template<class Table, class Color> | |
void | DFScolorStack (Table &tab, const Color &color, int 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 | DFSforest (const Table1 &ordered, Table2 &compVertices, Table3 &compEnds, bool nontrivial=false, diGraph< wType > *sccGraph=0) const |
Computes the DFS forest. | |
int | shortestPath (int source, int destination) const |
Computes the length of the shortest path from the given vertex to another one. | |
int | shortestLoop (int 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 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 source, lenTable &len) const |
Dijkstra's algorithm running on the graph's own weights. | |
template<class lenTable> | |
void | Dijkstra (int source, lenTable &len) const |
The above algorithm without rounding control. | |
template<class lenTable, class predTable, class roundType> | |
bool | BellmanFord (const roundType &rounding, int 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 source, lenTable &len, wType *infinity, predTable pred) const |
The above algorithm without rounding control. | |
template<class roundType> | |
bool | BellmanFord (const roundType &rounding, int 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 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 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 vertices and of length not exceeding the number of vertices in the graph. | |
template<class arrayType> | |
wType | minMeanPathWeight (const arrayType &starting, int 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 | nVertices |
The number of vertices. | |
multitable< int > | edgeEnds |
A table with the offsets of the one-after-the-last edge of each vertex. | |
multitable< int > | 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 vertex, int &counter) const |
The recurrent procedure for DFSfinishTime. | |
template<class Table> | |
void | DFSfinishTimeStack (Table &tab, int vertex, int &counter) const |
A stack version of the recurrent procedure for DFSfinishTime. | |
template<class Table1, class Table2> | |
bool | DFSforestRecurrent (Table1 &tab, Table1 &ntab, int vertex, int treeNumber, int countTrees, Table2 &compVertices, int &curVertex, diGraph *sccGraph, int *sccEdgeAdded) const |
The recurrent procedure for DFSforest. | |
template<class Table1, class Table2> | |
bool | DFSforestStack (Table1 &tab, Table1 &ntab, int vertex, int treeNumber, int countTrees, Table2 &compVertices, int &curVertex, diGraph *sccGraph, int *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. | |
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... |
The graph can be treated as weighted if necessary.
Definition at line 138 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 >::swap | ( | diGraph< wType > & | g | ) | [inline] |
Swaps the data with another graph.
Definition at line 599 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::my_swap(), chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
void chomp::homology::diGraph< wType >::addVertex | ( | void | ) | [inline] |
Adds a vertex.
Definition at line 609 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::collapseVertices(), chomp::homology::diGraph< wType >::DFSforest(), chomp::homology::inclusionGraph(), chomp::homology::matrix2graph(), and chomp::homology::diGraph< wType >::subgraph().
void chomp::homology::diGraph< wType >::addEdge | ( | int | target | ) | [inline] |
Adds an edge starting at the last vertex.
Note: The range of the target vertex number is not verified.
Definition at line 617 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::addRenumEdges(), chomp::homology::diGraph< wType >::DFSforestRecurrent(), chomp::homology::diGraph< wType >::DFSforestStack(), chomp::homology::inclusionGraph(), chomp::homology::matrix2graph(), and chomp::homology::diGraph< wType >::subgraph().
void chomp::homology::diGraph< wType >::addEdge | ( | int | 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 634 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
void chomp::homology::diGraph< wType >::setWeight | ( | int | vertex, | |
int | i, | |||
const wType & | weight | |||
) | [inline] |
Sets the weight of the given edge.
Definition at line 652 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::weights.
void chomp::homology::diGraph< wType >::setWeight | ( | int | edge, | |
const wType & | weight | |||
) | [inline] |
Sets the weight of the given edge.
Definition at line 663 of file digraph.h.
References chomp::homology::diGraph< wType >::weights.
void chomp::homology::diGraph< wType >::setWeights | ( | 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 670 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
void chomp::homology::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 681 of file digraph.h.
References chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::DFSforest().
void chomp::homology::diGraph< wType >::removeVertex | ( | int | 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 690 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
int chomp::homology::diGraph< wType >::countVertices | ( | void | ) | const [inline] |
Returns the number of vertices.
Definition at line 733 of file digraph.h.
References chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::collapseVertices(), chomp::homology::graph2matrix(), chomp::homology::inclusionGraph(), chomp::homology::diGraph< wType >::minPathWeight(), chomp::homology::SCC(), and chomp::homology::transitiveReduction().
int chomp::homology::diGraph< wType >::countEdges | ( | void | ) | const [inline] |
Returns the number of edges.
Definition at line 739 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::addRenumEdges(), chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), chomp::homology::graph2matrix(), chomp::homology::inclusionGraph(), and chomp::homology::diGraph< wType >::minPathWeight().
int chomp::homology::diGraph< wType >::countEdges | ( | int | vertex | ) | const [inline] |
Counts the number of edges leaving the given vertex.
Definition at line 748 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds.
int chomp::homology::diGraph< wType >::getEdge | ( | int | vertex, | |
int | i | |||
) | const [inline] |
Retrieves the given edge that leaves the given vertex.
Definition at line 757 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::addRenumEdges(), chomp::homology::graph2matrix(), and chomp::homology::inclusionGraph().
const wType & chomp::homology::diGraph< wType >::getWeight | ( | int | vertex, | |
int | i | |||
) | const [inline] |
Retrieves the weight of the given edge.
Definition at line 766 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::weights.
const wType & chomp::homology::diGraph< wType >::getWeight | ( | int | edge | ) | const [inline] |
Retrieves the weight of the given edge.
Definition at line 775 of file digraph.h.
References chomp::homology::diGraph< wType >::weights.
void chomp::homology::diGraph< wType >::getWeights | ( | Table & | tab | ) | const [inline] |
Gets the weights of all the edges at a time.
The weights are put into the table with the [] operator.
Definition at line 781 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
void chomp::homology::diGraph< wType >::writeEdges | ( | int * | table[2] | ) | const [inline] |
Fills out a table that represents all the edges of the graph.
Definition at line 792 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, and chomp::homology::diGraph< wType >::nVertices.
void chomp::homology::diGraph< wType >::transpose | ( | diGraph< wType1 > & | result, | |
bool | copyweights = false | |||
) | const [inline] |
Creates a transposed graph.
Definition at line 809 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::inclusionGraph(), and chomp::homology::SCC().
void chomp::homology::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 845 of file digraph.h.
References chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
void chomp::homology::diGraph< wType >::DFScolor | ( | Table & | tab, | |
const Color & | color, | |||
int | 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 960 of file digraph.h.
References chomp::homology::diGraph< wType >::DFScolorStack().
void chomp::homology::diGraph< wType >::DFScolorRecurrent | ( | Table & | tab, | |
const Color & | color, | |||
int | vertex = 0 | |||
) | const [inline] |
The recurrent procedure for DFScolor.
Definition at line 887 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
void chomp::homology::diGraph< wType >::DFScolorStack | ( | Table & | tab, | |
const Color & | color, | |||
int | vertex = 0 | |||
) | const [inline] |
A stack version of the recurrent procedure for DFScolor.
Definition at line 902 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFScolor().
void chomp::homology::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 1055 of file digraph.h.
References chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent(), chomp::homology::diGraph< wType >::DFSfinishTimeStack(), and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::SCC().
int 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.
Definition at line 1243 of file digraph.h.
References chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::DFSforestRecurrent(), chomp::homology::diGraph< wType >::DFSforestStack(), chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::removeVertex().
Referenced by chomp::homology::SCC().
int chomp::homology::diGraph< wType >::shortestPath | ( | int | source, | |
int | destination | |||
) | const [inline] |
Computes the length of the shortest 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, 0 or -1 if none.
Definition at line 1437 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::shortestLoop().
int chomp::homology::diGraph< wType >::shortestLoop | ( | int | 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 1525 of file digraph.h.
References chomp::homology::diGraph< wType >::shortestPath().
void chomp::homology::diGraph< wType >::Dijkstra | ( | const roundType & | rounding, | |
int | 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 1532 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::Dijkstra(), and chomp::homology::diGraph< wType >::Johnson().
void chomp::homology::diGraph< wType >::Dijkstra | ( | const roundType & | rounding, | |
int | source, | |||
lenTable & | len | |||
) | const [inline] |
Dijkstra's algorithm running on the graph's own weights.
Definition at line 1598 of file digraph.h.
References chomp::homology::diGraph< wType >::Dijkstra(), and chomp::homology::diGraph< wType >::weights.
void chomp::homology::diGraph< wType >::Dijkstra | ( | int | source, | |
lenTable & | len | |||
) | const [inline] |
The above algorithm without rounding control.
Definition at line 1607 of file digraph.h.
References chomp::homology::diGraph< wType >::Dijkstra().
bool chomp::homology::diGraph< wType >::BellmanFord | ( | const roundType & | rounding, | |
int | 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 1616 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, chomp::homology::diGraph< wType >::show(), and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::BellmanFord().
bool chomp::homology::diGraph< wType >::BellmanFord | ( | int | source, | |
lenTable & | len, | |||
wType * | infinity, | |||
predTable | pred | |||
) | const [inline] |
The above algorithm without rounding control.
Definition at line 1737 of file digraph.h.
References chomp::homology::diGraph< wType >::BellmanFord().
bool chomp::homology::diGraph< wType >::BellmanFord | ( | const roundType & | rounding, | |
int | 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 1745 of file digraph.h.
References chomp::homology::diGraph< wType >::BellmanFord(), and chomp::homology::diGraph< wType >::nVertices.
bool chomp::homology::diGraph< wType >::BellmanFord | ( | int | source | ) | const [inline] |
The above algorithm without rounding control.
Definition at line 1756 of file digraph.h.
References chomp::homology::diGraph< wType >::BellmanFord().
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.
Definition at line 1763 of file digraph.h.
References chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
wType chomp::homology::diGraph< wType >::EdmondsOld | ( | ) | const [inline] |
An old implementation of the Edmonds algorithm (less efficient).
Definition at line 1838 of file digraph.h.
References chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
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".
Definition at line 1914 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::Johnson(), and chomp::homology::diGraph< wType >::minPathWeight().
wType chomp::homology::diGraph< wType >::FloydWarshall | ( | arrayType & | arr, | |
bool | setInfinity = true , |
|||
bool | ignoreNegLoop = false | |||
) | const [inline] |
The above algorithm without rounding control.
Definition at line 2061 of file digraph.h.
References chomp::homology::diGraph< wType >::FloydWarshall().
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'.
Definition at line 2070 of file digraph.h.
References chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::nVertices, chomp::homology::diGraph< wType >::show(), and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::Johnson(), and chomp::homology::diGraph< wType >::minPathWeight().
wType chomp::homology::diGraph< wType >::Johnson | ( | arrayType & | arr, | |
bool | setInfinity = true , |
|||
bool | ignoreNegLoop = false | |||
) | const [inline] |
The above algorithm without rounding control.
Definition at line 2232 of file digraph.h.
References chomp::homology::diGraph< wType >::Johnson().
wType chomp::homology::diGraph< wType >::minPathWeight | ( | const roundType & | rounding, | |
bool | ignoreNegLoop = false , |
|||
int | sparseGraph = -1 | |||
) | const [inline] |
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 2241 of file digraph.h.
References chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::countVertices(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::Johnson(), and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::minPathWeight().
wType chomp::homology::diGraph< wType >::minPathWeight | ( | bool | ignoreNegLoop = false , |
|
int | sparseGraph = -1 | |||
) | const [inline] |
The above algorithm without rounding control.
Definition at line 2295 of file digraph.h.
References chomp::homology::diGraph< wType >::minPathWeight().
wType chomp::homology::diGraph< wType >::minMeanCycleWeight | ( | diGraph< wType > * | transposed = 0 |
) | const [inline] |
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 2375 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, chomp::homology::SCC(), and chomp::homology::diGraph< wType >::weights.
wType chomp::homology::diGraph< wType >::minMeanCycleWeight | ( | const roundType & | rounding, | |
diGraph< wType > * | transposed | |||
) | const [inline] |
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 2520 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, chomp::homology::SCC(), and chomp::homology::diGraph< wType >::weights.
wType chomp::homology::diGraph< wType >::minMeanPathWeight | ( | const roundType & | rounding, | |
const arrayType & | starting, | |||
int | n | |||
) | const [inline] |
Runs an algorithm based on Karp's idea to compute the minimum mean path weight for paths starting at any of the given 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 2688 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::minMeanPathWeight().
wType chomp::homology::diGraph< wType >::minMeanPathWeight | ( | const arrayType & | starting, | |
int | n | |||
) | const [inline] |
The above algorithm without rounding control.
Definition at line 2779 of file digraph.h.
References chomp::homology::diGraph< wType >::minMeanPathWeight().
outType & chomp::homology::diGraph< wType >::show | ( | outType & | out, | |
bool | showWeights = false | |||
) | const [inline] |
Outputs the graph to a text stream in a human-readable format.
Definition at line 2303 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::BellmanFord(), chomp::homology::diGraph< wType >::Johnson(), and chomp::homology::operator<<().
void chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent | ( | Table & | tab, | |
int | vertex, | |||
int & | counter | |||
) | const [inline, private] |
The recurrent procedure for DFSfinishTime.
Definition at line 970 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFSfinishTime().
void chomp::homology::diGraph< wType >::DFSfinishTimeStack | ( | Table & | tab, | |
int | vertex, | |||
int & | counter | |||
) | const [inline, private] |
A stack version of the recurrent procedure for DFSfinishTime.
Definition at line 991 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFSfinishTime().
bool chomp::homology::diGraph< wType >::DFSforestRecurrent | ( | Table1 & | tab, | |
Table1 & | ntab, | |||
int | vertex, | |||
int | treeNumber, | |||
int | countTrees, | |||
Table2 & | compVertices, | |||
int & | curVertex, | |||
diGraph< wType > * | sccGraph, | |||
int * | sccEdgeAdded | |||
) | const [inline, private] |
The recurrent procedure for DFSforest.
Returns true iff there is a loop within the tree found.
Definition at line 1093 of file digraph.h.
References chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFSforest().
bool chomp::homology::diGraph< wType >::DFSforestStack | ( | Table1 & | tab, | |
Table1 & | ntab, | |||
int | vertex, | |||
int | treeNumber, | |||
int | countTrees, | |||
Table2 & | compVertices, | |||
int & | curVertex, | |||
diGraph< wType > * | sccGraph, | |||
int * | sccEdgeAdded | |||
) | const [inline, private] |
A stack version of the recurrent procedure for DFSforest.
Definition at line 1145 of file digraph.h.
References chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFSforest().
int chomp::homology::diGraph< wType >::nVertices [protected] |
The number of vertices.
Definition at line 429 of file digraph.h.
Referenced by chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::BellmanFord(), chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::countVertices(), chomp::homology::diGraph< wType >::DFSfinishTime(), chomp::homology::diGraph< wType >::DFSforest(), chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::getWeights(), chomp::homology::diGraph< wType >::Johnson(), chomp::homology::diGraph< wType >::minMeanCycleWeight(), chomp::homology::diGraph< wType >::minMeanPathWeight(), chomp::homology::diGraph< wType >::minPathWeight(), chomp::homology::diGraph< wType >::removeVertex(), chomp::homology::diGraph< wType >::setWeights(), chomp::homology::diGraph< wType >::shortestPath(), chomp::homology::diGraph< wType >::show(), chomp::homology::diGraph< wType >::subgraph(), chomp::homology::diGraph< wType >::swap(), chomp::homology::diGraph< wType >::transpose(), and chomp::homology::diGraph< wType >::writeEdges().
multitable<int> chomp::homology::diGraph< wType >::edgeEnds [protected] |
A table with the offsets of the one-after-the-last edge of each vertex.
Definition at line 433 of file digraph.h.
Referenced by chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::BellmanFord(), chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::DFScolorRecurrent(), chomp::homology::diGraph< wType >::DFScolorStack(), chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent(), chomp::homology::diGraph< wType >::DFSfinishTimeStack(), chomp::homology::diGraph< wType >::DFSforestRecurrent(), chomp::homology::diGraph< wType >::DFSforestStack(), chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::getEdge(), chomp::homology::diGraph< wType >::getWeight(), chomp::homology::diGraph< wType >::getWeights(), chomp::homology::diGraph< wType >::Johnson(), chomp::homology::diGraph< wType >::minMeanCycleWeight(), chomp::homology::diGraph< wType >::minMeanPathWeight(), chomp::homology::diGraph< wType >::removeVertex(), chomp::homology::diGraph< wType >::setWeight(), chomp::homology::diGraph< wType >::setWeights(), chomp::homology::diGraph< wType >::shortestPath(), chomp::homology::diGraph< wType >::show(), chomp::homology::diGraph< wType >::subgraph(), chomp::homology::diGraph< wType >::swap(), chomp::homology::diGraph< wType >::transpose(), and chomp::homology::diGraph< wType >::writeEdges().
multitable<int> chomp::homology::diGraph< wType >::edges [protected] |
A table with edge target numbers.
Definition at line 436 of file digraph.h.
Referenced by chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::BellmanFord(), chomp::homology::diGraph< wType >::DFScolorRecurrent(), chomp::homology::diGraph< wType >::DFScolorStack(), chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent(), chomp::homology::diGraph< wType >::DFSfinishTimeStack(), chomp::homology::diGraph< wType >::DFSforestRecurrent(), chomp::homology::diGraph< wType >::DFSforestStack(), chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::getEdge(), chomp::homology::diGraph< wType >::Johnson(), chomp::homology::diGraph< wType >::minMeanCycleWeight(), chomp::homology::diGraph< wType >::minMeanPathWeight(), chomp::homology::diGraph< wType >::removeVertex(), chomp::homology::diGraph< wType >::shortestPath(), chomp::homology::diGraph< wType >::show(), chomp::homology::diGraph< wType >::subgraph(), chomp::homology::diGraph< wType >::swap(), chomp::homology::diGraph< wType >::transpose(), and chomp::homology::diGraph< wType >::writeEdges().
multitable<wType> chomp::homology::diGraph< wType >::weights [protected] |
A table with edge weights.
Definition at line 439 of file digraph.h.
Referenced by chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::BellmanFord(), chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::getWeight(), chomp::homology::diGraph< wType >::getWeights(), chomp::homology::diGraph< wType >::Johnson(), chomp::homology::diGraph< wType >::minMeanCycleWeight(), chomp::homology::diGraph< wType >::minMeanPathWeight(), chomp::homology::diGraph< wType >::removeVertex(), chomp::homology::diGraph< wType >::setWeight(), chomp::homology::diGraph< wType >::setWeights(), chomp::homology::diGraph< wType >::show(), chomp::homology::diGraph< wType >::subgraph(), chomp::homology::diGraph< wType >::swap(), and chomp::homology::diGraph< wType >::transpose().