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.
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 |
typedef std::pair<AdjacencyIterator,AdjacencyIterator> biu::Graph_UD::AdjItPair |
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] |
Member Function Documentation
void biu::Graph_UD::addEdge | ( | const size_t | n1, | |
const size_t | n2 | |||
) |
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 | |||
) |
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 documentation for this class was generated from the following files:
- src/biu/Graph_UD.hh
- src/biu/Graph_UD.cc