Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

General Graph Utilities
[Graph Algorithms]

Collaboration diagram for General Graph Utilities:


Detailed Description

This group describes some simple general graph utilities.


Files

file  graph_utils.h
 Graph utilities.

Functions

template<typename Graph, typename ItemIt>
int lemon::countItems (const Graph &g)
 Function to count the items in the graph.
template<typename Graph>
int lemon::countNodes (const Graph &g)
 Function to count the nodes in the graph.
template<typename Graph>
int lemon::countEdges (const Graph &g)
 Function to count the edges in the graph.
template<typename Graph>
int lemon::countUndirEdges (const Graph &g)
 Function to count the edges in the graph.
template<typename Graph>
Graph::Edge lemon::findEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge prev=INVALID)
 Finds an edge between two nodes of a graph.
template<typename Graph>
int lemon::countOutEdges (const Graph &_g, const typename Graph::Node &_n)
 
template<typename Graph>
int lemon::countInEdges (const Graph &_g, const typename Graph::Node &_n)
 


Function Documentation

int countItems const Graph &  g  )  [inline]
 

This function counts the items in the graph. The complexity of the function is O(n) because it iterates on all of the items.

Definition at line 46 of file graph_utils.h.

int countNodes const Graph &  g  )  [inline]
 

This function counts the nodes in the graph. The complexity of the function is O(n) but for some graph structure it is specialized to run in O(1).

Todo:
refer how to specialize it

Definition at line 77 of file graph_utils.h.

int countEdges const Graph &  g  )  [inline]
 

This function counts the edges in the graph. The complexity of the function is O(e) but for some graph structure it is specialized to run in O(1).

Definition at line 102 of file graph_utils.h.

int countUndirEdges const Graph &  g  )  [inline]
 

This function counts the edges in the graph. The complexity of the function is O(e) but for some graph structure it is specialized to run in O(1).

Definition at line 127 of file graph_utils.h.

Graph::Edge findEdge const Graph &  g,
typename Graph::Node  u,
typename Graph::Node  v,
typename Graph::Edge  prev = INVALID
 

Finds an edge from node u to node v in graph g.

If prev is INVALID (this is the default value), then it finds the first edge from u to v. Otherwise it looks for the next edge from u to v after prev.

Returns:
The found edge or INVALID if there is no such an edge.
Thus you can iterate through each edge from u to v as it follows.
      for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
        ...
      }

Todo:
We may want to use the GraphBase interface here...
Bug:
Untested ...

Definition at line 161 of file graph_utils.h.

int countOutEdges const Graph &  _g,
const typename Graph::Node &  _n
[inline]
 

Todo:
Please document.

Definition at line 178 of file graph_utils.h.

int countInEdges const Graph &  _g,
const typename Graph::Node &  _n
[inline]
 

Todo:
Please document.

Definition at line 187 of file graph_utils.h.


Generated on Mon Feb 21 15:02:28 2005 for LEMON by  doxygen 1.4.1