The Finite Resolution Dynamics Software
|
A directed graph class with some algorithms built-in. More...
#include <graph.h>
Public Member Functions | |
void | addVertex (void) |
Adds a vertex. More... | |
void | addEdge (int target) |
Adds an edge starting at the last vertex. More... | |
int | countVertices (void) const |
Returns the number of vertices. More... | |
int | countEdges (void) const |
Returns the number of edges. More... | |
int | countEdges (int vertex) const |
Counts the number of edges leaving the given vertex. More... | |
int | getEdge (int vertex, int i) const |
Retrieves the given edge that leaves the given vertex. More... | |
bool | checkStronglyConnected () const |
Verifies if the graph is strongly connected. More... | |
bool | checkAperiodic () const |
Verifies if the graph is aperiodic. More... | |
Private Attributes | |
chomp::homology::diGraph | g |
The underlying graph object. More... | |
A directed graph class with some algorithms built-in.
This class defines a directed graph which is optimized for the particular application in this project. It supports a very limited number of operations, but these operations are very fast. This class also implements a few algorithms necessary in this project. This particular implementation is a wrapper for the class "diGraph" available in the CHomP software package. Note: The default constructor, destructor and assignment operator are good for this class, so none are defined.
|
inline |
|
inline |
|
inline |
|
inline |
Verifies if the graph is strongly connected.
This function uses Tarjan's algorithm (as described in the Wikipedia) for the computation of strongly connected components in order to determine whether the given graph is strongly connected.
Tha advantage of this approach over the one described in Cormen's textbook is that the transposed graph need not be computed.
Definition at line 138 of file graph.h.
References countVertices(), and g.
|
inline |
Returns the number of edges.
Definition at line 116 of file graph.h.
References g.
Referenced by countEdges().
|
inline |
Counts the number of edges leaving the given vertex.
Definition at line 121 of file graph.h.
References countEdges(), and g.
|
inline |
Returns the number of vertices.
Definition at line 111 of file graph.h.
References g.
Referenced by checkStronglyConnected().
|
inline |
|
private |
The underlying graph object.
Definition at line 93 of file graph.h.
Referenced by addEdge(), addVertex(), checkAperiodic(), checkStronglyConnected(), countEdges(), countVertices(), and getEdge().