WhiteheadSimpleGraph Class Reference

Implements Whitehead Simple graph (i.e. no multiple edges or loops allowed). More...

#include <WhiteheadGraph.h>

Inheritance diagram for WhiteheadSimpleGraph:


Public Member Functions
	WhiteheadSimpleGraph (const Word &w, int num_of_gens)
	Constructor.
	~WhiteheadSimpleGraph ()
int	getCount (int i, int j) const
	Get the label of the edge (i,j).
int	getSize () const
	Get the number of vertices of the graph.
vector< double >	getWeightVector () const
	Get a vector containing weights of the edges of the graph.
vector< Word >	getWeightNames () const
	Get a vector of words, corresponding to edges of the graph.
bool	isUndirected () const
	Check if undirected graph.
void	makeUndirected ()
	Convert to undirected Whitehead graph.
int	numberOfComponents () const
	Get the number of connected components.
int	numberOfCutVertices () const
	Get the number of cut vertices (articulation points).
vector< int >	cutVertices () const
	Get the list of cut vertices (articulation points).
int	numberOfCutVerticesBruteForce () const
vector< int >	cutVerticesBruteForce () const
Private Member Functions
void	printOn (ostream &out) const
	Outputs the graph into a stream.
int	genToIndex (const Generator &g) const
	Transfers a letter into a graph vertex.
Generator	indToGenerator (int i) const
	Transfers a vertex into the corresponding letter.
int	nOfComponents () const
	computes the number of connected components
Private Attributes
int	theSize
	The number of vertices.
int **	theAdjMatrix
	The adjacensy matrix of the graph.
bool	undirected
	True if undirected.
Friends
ostream &	operator<< (ostream &out, const WhiteheadSimpleGraph &g)
	Output operator.

Detailed Description

Implements Whitehead Simple graph (i.e. no multiple edges or loops allowed).

Definition at line 155 of file WhiteheadGraph.h.

Constructor & Destructor Documentation

WhiteheadSimpleGraph::WhiteheadSimpleGraph ( const Word & w,

int num_of_gens

)

Constructor.

Parameters:

w - input word.

num_of_gen - the number of generators in the corresponding group

WhiteheadSimpleGraph::~WhiteheadSimpleGraph ( )

Member Function Documentation

vector<int> WhiteheadSimpleGraph::cutVertices ( ) const

Get the list of cut vertices (articulation points).

Returns:
The list of cut vertices.

vector<int> WhiteheadSimpleGraph::cutVerticesBruteForce ( ) const

int WhiteheadSimpleGraph::genToIndex ( const Generator & g ) const [inline, private]

Transfers a letter into a graph vertex.

Definition at line 246 of file WhiteheadGraph.h.
References WhiteheadGraph::nOfGenerators.

int WhiteheadSimpleGraph::getCount ( int i,

int j

) const [inline]

Get the label of the edge (i,j).
The label is the number of times (counts) the subword $i j^{-1}$ occurred in w.
Parameters:

i - first vertex (letter)

j - second vertex (letter)

Returns:
Label of the edge (i,j)

Definition at line 180 of file WhiteheadGraph.h.
References msgs::error(), theAdjMatrix, and theSize.

int WhiteheadSimpleGraph::getSize ( ) const [inline]

Get the number of vertices of the graph.

Returns:
The number of vertices

Definition at line 190 of file WhiteheadGraph.h.
References theSize.

vector<Word> WhiteheadSimpleGraph::getWeightNames ( ) const

Get a vector of words, corresponding to edges of the graph.

Returns:
The vector of words, corresponding to the edges of the Whitehead graph.

vector<double> WhiteheadSimpleGraph::getWeightVector ( ) const

Get a vector containing weights of the edges of the graph.

Returns:
Vector of the weights of the edges of the graph. NOTE: the graph is treated as undirected Whitehead graph when weights are computed. See makeUndirected() for more information.

Generator WhiteheadSimpleGraph::indToGenerator ( int i ) const [inline, private]

Transfers a vertex into the corresponding letter.

Definition at line 255 of file WhiteheadGraph.h.
References WhiteheadGraph::nOfGenerators.

bool WhiteheadSimpleGraph::isUndirected ( ) const [inline]

Check if undirected graph.
By default the graph is undirected Whitehead graph. Run makeUndirected() to convert to undirected graph.
Returns:
true if the graph is undirected Whitehead graph, false otherwise.

Definition at line 210 of file WhiteheadGraph.h.
References undirected.

void WhiteheadSimpleGraph::makeUndirected ( )

Convert to undirected Whitehead graph.
Initially a Directed Whitehead graph is constructed. Use this function to convert to undirected Whitehead graph.
Edges are added, and the new edge weights $\omega^*(i,j) = \omega^*(j,i) = \omega(i,j) + \omega(j,i)$ , where $\omega(m,n)$ are the weights in the directed graph.

int WhiteheadSimpleGraph::nOfComponents ( ) const [private]

computes the number of connected components

int WhiteheadSimpleGraph::numberOfComponents ( ) const

Get the number of connected components.

Returns:
The number of connected components.

int WhiteheadSimpleGraph::numberOfCutVertices ( ) const

Get the number of cut vertices (articulation points).

Returns:
The number of cut vertices.

int WhiteheadSimpleGraph::numberOfCutVerticesBruteForce ( ) const

void WhiteheadSimpleGraph::printOn ( ostream & out ) const [private]

Outputs the graph into a stream.

Friends And Related Function Documentation

ostream& operator<< ( ostream & out,

const WhiteheadSimpleGraph & g

) [friend]

Output operator.

Definition at line 167 of file WhiteheadGraph.h.

Member Data Documentation

int** WhiteheadSimpleGraph::theAdjMatrix [private]

The adjacensy matrix of the graph.

Definition at line 272 of file WhiteheadGraph.h.
Referenced by getCount().

int WhiteheadSimpleGraph::theSize [private]

The number of vertices.

Definition at line 269 of file WhiteheadGraph.h.
Referenced by getCount(), and getSize().

bool WhiteheadSimpleGraph::undirected [private]

True if undirected.

Definition at line 275 of file WhiteheadGraph.h.
Referenced by isUndirected().

The documentation for this class was generated from the following file:

FreeGroup/include/WhiteheadGraph.h

Generated on Sun Dec 3 10:59:06 2006 for CRyptography And Groups (CRAG) by

1.4.6

WhiteheadSimpleGraph Class Reference

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation