#include <WhiteheadGraph.h>
Public Member Functions | |
CutVertices (const int **G, int n) | |
Constructor. | |
~CutVertices () | |
void | compute () |
Finds articulation points. | |
void | computeBruteForce () |
Finds articulation points (Brute force algorithm. | |
int | numberOfComponents (bool ignore_single_vertices=false) |
Computes the number of connected components of the graph. | |
vector< int > | getCutVertices () const |
Get the list of articulation points. | |
Private Member Functions | |
void | init () |
void | DepthFirstSearch () |
Execute depth first search. | |
void | RecursiveDepthFirstSearch (int v) |
Execute recursive depth first search. | |
void | RDFS_Compute_Low (int v) |
Compute the low subtree recursively. | |
void | ArticulationPoints () |
Extract articulation points from the labels. | |
Private Attributes | |
int ** | theGraph |
Adjacency matrix of the graph. | |
int | N |
Number of vertices. | |
int | time |
Current time label (internal use only). | |
vector< int > | visit |
List of visited points (internal use only). | |
vector< int > | pred |
List of predecessors (internal use only). | |
vector< int > | discover |
Labels of discovered vertices (internal use only). | |
vector< int > | Low |
vector< int > | articulation_point |
List of articulation points. |
Definition at line 29 of file WhiteheadGraph.h.
|
Constructor.
|
|
|
|
Extract articulation points from the labels.
|
|
Finds articulation points.
Finds all articulation points of the graph. The result can be obtained through getCutVertices() function. This algorithm requires linear time in the size of the graph, or |
|
Finds articulation points (Brute force algorithm.
Finds all articulation points of the graph. The result can be obtained through getCutVertices() function. Complexity: |
|
Execute depth first search.
|
|
Get the list of articulation points. Return the list of articulation points obtained using one of the algorithms. compute() or computeBruteForce() must be called first.
Definition at line 72 of file WhiteheadGraph.h. References articulation_point. |
|
|
|
Computes the number of connected components of the graph. Computes the number of connected components of the graph.
|
|
Compute the low subtree recursively.
|
|
Execute recursive depth first search.
|
|
List of articulation points.
Definition at line 108 of file WhiteheadGraph.h. Referenced by getCutVertices(). |
|
Labels of discovered vertices (internal use only).
Definition at line 103 of file WhiteheadGraph.h. |
|
Definition at line 104 of file WhiteheadGraph.h. |
|
Number of vertices.
Definition at line 94 of file WhiteheadGraph.h. |
|
List of predecessors (internal use only).
Definition at line 101 of file WhiteheadGraph.h. |
|
Adjacency matrix of the graph.
Definition at line 91 of file WhiteheadGraph.h. |
|
Current time label (internal use only).
Definition at line 97 of file WhiteheadGraph.h. |
|
List of visited points (internal use only).
Definition at line 99 of file WhiteheadGraph.h. |