Generated on Tue Dec 16 12:50:03 2008 for BIU-2.2.0 by doxygen 1.5.1

biu::Graph_UD Class Reference

#include <Graph_UD.hh>


Detailed Description

An undirected graph implementation. Nodes are labeled using integers starting from 0. The numbering has to be succesively.
Author:
Martin Mann

Definition at line 18 of file Graph_UD.hh.

Public Types

typedef std::set< size_t
>::const_iterator 
AdjacencyIterator
typedef std::pair< AdjacencyIterator,
AdjacencyIterator
AdjItPair
typedef std::vector< size_t > CompLabel

Public Member Functions

void addEdge (const size_t n1, const size_t n2)
AdjItPair adjNodes (const size_t n) const
size_t connectedComponents (CompLabel &compID) const
size_t degree (const size_t n) const
size_t edges () const
 Graph_UD (size_t nodeNumber=0)
bool isEdge (const size_t n1, const size_t n2)
size_t nodes () const
void printDOT (std::ostream &out) const
void remEdge (const size_t n1, const size_t n2)
void setNodeNumber (const size_t n)
virtual ~Graph_UD ()

Protected Member Functions

void labelAdjacentNodes (const size_t curNode, CompLabel &compID, const size_t label) const

Protected Attributes

std::vector< std::set< size_t > > adjList


Member Typedef Documentation

typedef std::set<size_t>::const_iterator biu::Graph_UD::AdjacencyIterator

iterator on the adjacency list of a node

Definition at line 33 of file Graph_UD.hh.

pair of begin/end adjacency iterator

Definition at line 35 of file Graph_UD.hh.

typedef std::vector<size_t> biu::Graph_UD::CompLabel

Definition at line 30 of file Graph_UD.hh.


Constructor & Destructor Documentation

biu::Graph_UD::Graph_UD ( size_t  nodeNumber = 0  ) 

constructs an undirected graph and initializes the node list with nodeNumber nodes.

Definition at line 11 of file Graph_UD.cc.

biu::Graph_UD::~Graph_UD (  )  [virtual]

destruction

Definition at line 16 of file Graph_UD.cc.


Member Function Documentation

void biu::Graph_UD::addEdge ( const size_t  n1,
const size_t  n2 
)

Adds an edge between node n1 and n2.

Definition at line 21 of file Graph_UD.cc.

Graph_UD::AdjItPair biu::Graph_UD::adjNodes ( const size_t  n  )  const

Gives the begin/end iterator of the adjacency list of the specified node.

Parameters:
n node index
Returns:
the begin and end iterator of the adjacency list of node indices

Definition at line 166 of file Graph_UD.cc.

size_t biu::Graph_UD::connectedComponents ( CompLabel compID  )  const

calculates the number of connected components and writes the nodeID componentID labeling into the given label vector.

Returns:
the number of independent connected components

Definition at line 60 of file Graph_UD.cc.

size_t biu::Graph_UD::degree ( const size_t  n  )  const

Returns the node degree in the graph.

Parameters:
n node index
Returns:
node degree of the node

Definition at line 55 of file Graph_UD.cc.

size_t biu::Graph_UD::edges (  )  const

Returns the number of edges in the graph.

Returns:
number of edges

Definition at line 46 of file Graph_UD.cc.

bool biu::Graph_UD::isEdge ( const size_t  n1,
const size_t  n2 
)

Tests whether or not an edge in the graph between node n1 and n2.

Returns:
true if the edge exists, false otherwise

Definition at line 35 of file Graph_UD.cc.

void biu::Graph_UD::labelAdjacentNodes ( const size_t  curNode,
CompLabel compID,
const size_t  label 
) const [protected]

Labels all uncolored direct or indirect to curNode adjacent nodes and therefore the corresponding conntected component. The compID of uncolored nodes is UINT_MAX. The method is internally called by method 'connectedComponents(..)'.

Parameters:
curNode the initial node to explore the connected component
compID the labels set so far
label the label of this connected component to set

Definition at line 89 of file Graph_UD.cc.

size_t biu::Graph_UD::nodes (  )  const

Returns the number of nodes in the graph.

Returns:
number of nodes

Definition at line 41 of file Graph_UD.cc.

void biu::Graph_UD::printDOT ( std::ostream &  out  )  const

prints the graph in DOT-format to the given output stream.

Definition at line 138 of file Graph_UD.cc.

void biu::Graph_UD::remEdge ( const size_t  n1,
const size_t  n2 
)

Removes an edge from the graph between node n1 and n2.

Definition at line 28 of file Graph_UD.cc.

void biu::Graph_UD::setNodeNumber ( const size_t  n  ) 

updates the node list to indices 0..(n-1) and removes all edges previously connected to nodes with index >= n

Parameters:
n the number of nodes after the changes

Definition at line 156 of file Graph_UD.cc.


Field Documentation

std::vector< std::set<size_t> > biu::Graph_UD::adjList [protected]

the internal adjacency list representation

Definition at line 24 of file Graph_UD.hh.


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