WhiteheadSimpleGraph Class Reference

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

#include <WhiteheadGraph.h>

Inheritance diagram for WhiteheadSimpleGraph:
WhiteheadGraph

List of all members.

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< WordgetWeightNames () 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

The adjacensy matrix of the graph.

Definition at line 272 of file WhiteheadGraph.h.

Referenced by getCount().

The number of vertices.

Definition at line 269 of file WhiteheadGraph.h.

Referenced by getCount(), and getSize().

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:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

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