chomp::homology::diGraph< wType > Class Template Reference

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>

List of all members.

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


Detailed Description

template<class wType = int>
class chomp::homology::diGraph< wType >

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


Member Typedef Documentation

template<class wType = int>
typedef wType chomp::homology::diGraph< wType >::weight_type

The type of the weight of edges.

Definition at line 142 of file digraph.h.


Constructor & Destructor Documentation

template<class wType>
chomp::homology::diGraph< wType >::diGraph (  )  [inline]

The default constructor of an empty graph.

Definition at line 557 of file digraph.h.

template<class wType>
chomp::homology::diGraph< wType >::~diGraph (  )  [inline]

The destructor.

Definition at line 564 of file digraph.h.


Member Function Documentation

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

template<class wType>
template<class Table, class wType1>
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.

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

template<class wType>
template<class Table, class Color>
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.

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

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

template<class wType>
template<class Table1, class Table2, class Table3>
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().

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Friends And Related Function Documentation

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


Member Data Documentation

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

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

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

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


The documentation for this class was generated from the following file:
Generated on Wed Nov 21 11:08:42 2007 for The Uniform Expansion Software by  doxygen 1.5.3