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

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

 void CutVertices::DepthFirstSearch ( ) ` [private]`

Execute depth first search.

 vector 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 CutVertices::articulation_point` [private]`

List of articulation points.

Definition at line 108 of file WhiteheadGraph.h.

Referenced by getCutVertices().

 vector CutVertices::discover` [private]`

Labels of discovered vertices (internal use only).

Definition at line 103 of file WhiteheadGraph.h.

 vector 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 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 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:

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