CutVertices Class Reference

Implements an algorithm to find all articulation points of a graph//. More...

#include <WhiteheadGraph.h>

List of all members.

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.

Detailed Description

Implements an algorithm to find all articulation points of a graph//.

Definition at line 29 of file WhiteheadGraph.h.


Constructor & Destructor Documentation

CutVertices::CutVertices ( const int **  G,
int  n 
)

Constructor.

Parameters:
G - the adjacency matrix of a graph ( there is an edge from i to j in the graph iff G[i][j] $\neq$ 0 ).
n - the number of vertices.
CutVertices::~CutVertices (  ) 

Member Function Documentation

void CutVertices::ArticulationPoints (  )  [private]

Extract articulation points from the labels.

void CutVertices::compute (  ) 

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 $O(n^2)$.

void CutVertices::computeBruteForce (  ) 

Finds articulation points (Brute force algorithm.

Finds all articulation points of the graph. The result can be obtained through getCutVertices() function. Complexity: $O(n^2)$.

void CutVertices::DepthFirstSearch (  )  [private]

Execute depth first search.

vector<int> CutVertices::getCutVertices (  )  const [inline]

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.

Returns:
The list of articulation vertices.

Definition at line 72 of file WhiteheadGraph.h.

References articulation_point.

void CutVertices::init (  )  [private]
int CutVertices::numberOfComponents ( bool  ignore_single_vertices = false  ) 

Computes the number of connected components of the graph.

Computes the number of connected components of the graph.

Parameters:
ignore_single_vertices - if set to true, then components containing only one vertex are ignored. Default value is false.
Returns:
The number of connected components
void CutVertices::RDFS_Compute_Low ( int  v  )  [private]

Compute the low subtree recursively.

void CutVertices::RecursiveDepthFirstSearch ( int  v  )  [private]

Execute recursive depth first search.


Member Data Documentation

vector<int> CutVertices::articulation_point [private]

List of articulation points.

Definition at line 108 of file WhiteheadGraph.h.

Referenced by getCutVertices().

vector<int> CutVertices::discover [private]

Labels of discovered vertices (internal use only).

Definition at line 103 of file WhiteheadGraph.h.

vector<int> CutVertices::Low [private]

Definition at line 104 of file WhiteheadGraph.h.

int CutVertices::N [private]

Number of vertices.

Definition at line 94 of file WhiteheadGraph.h.

vector<int> CutVertices::pred [private]

List of predecessors (internal use only).

Definition at line 101 of file WhiteheadGraph.h.

int** CutVertices::theGraph [private]

Adjacency matrix of the graph.

Definition at line 91 of file WhiteheadGraph.h.

int CutVertices::time [private]

Current time label (internal use only).

Definition at line 97 of file WhiteheadGraph.h.

vector<int> CutVertices::visit [private]

List of visited points (internal use only).

Definition at line 99 of file WhiteheadGraph.h.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on Mon Sep 26 18:43:46 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1