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

• FreeGroup/include/WhiteheadGraph.h