General Graph Utilities
[Graph Algorithms]


Detailed Description

This group describes some simple general graph utilities.


Files

file  graph_utils.h
 Graph utilities.
file  map_iterator.h
 Iterators on the maps.

Classes

class  ConEdgeIt
 Iterator for iterating on edges connected the same nodes. More...
class  ConUEdgeIt
 Iterator for iterating on uedges connected the same nodes. More...
class  GraphCopy
 Class to copy a graph. More...
class  UGraphCopy
 Class to copy an undirected graph. More...
class  MapIt
 Iterator for maps with possibility of changing values. More...
class  ConstMapIt
 Iterator for maps with possibility of getting values. More...
class  FilterMapIt
 Iterator for maps which filters items by the values. More...

Defines

#define GRAPH_TYPEDEFS(Graph)
 Creates convenience typedefs for the graph types and iterators.
#define UNDIRGRAPH_TYPEDEFS(Graph)
 Creates convenience typedefs for the undirected graph types and iterators.

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::countUEdges (const Graph &g)
 Function to count the undirected edges in the graph.
template<typename Graph>
int lemon::countOutEdges (const Graph &_g, const typename Graph::Node &_n)
 Function to count the number of the out-edges from node n.
template<typename Graph>
int lemon::countInEdges (const Graph &_g, const typename Graph::Node &_n)
 Function to count the number of the in-edges to node n.
template<typename Graph>
int lemon::countIncEdges (const Graph &_g, const typename Graph::Node &_n)
 Function to count the number of the inc-edges to node n.
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>
Graph::UEdge lemon::findUEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::UEdge prev=INVALID)
 Finds an uedge between two nodes of a graph.
template<typename Target, typename Source, typename ItemIt, typename Ref>
void lemon::copyMap (Target &target, const Source &source, ItemIt it, const Ref &ref)
 Copy a map.
template<typename Target, typename Source, typename ItemIt>
void lemon::copyMap (Target &target, const Source &source, ItemIt it)
 Copy the source map to the target map.
template<typename Target, typename Source>
GraphCopy< Target, Source > lemon::copyGraph (Target &target, const Source &source)
 Copy a graph to an other graph.
template<typename Target, typename Source>
UGraphCopy< Target, Source > lemon::copyUGraph (Target &target, const Source &source)
 Copy a graph to an other graph.


Define Documentation

#define GRAPH_TYPEDEFS Graph   ) 
 

This #define creates convenience typedefs for the following types of Graph: Node, NodeIt, Edge, EdgeIt, InEdgeIt, OutEdgeIt, BoolNodeMap, IntNodeMap, DoubleNodeMap, BoolEdgeMap, IntEdgeMap, DoubleEdgeMap.

Note:
If G it a template parameter, it should be used in this way.
       GRAPH_TYPEDEFS(typename G)
Warning:
There are no typedefs for the graph maps because of the lack of template typedefs in C++.

#define UNDIRGRAPH_TYPEDEFS Graph   ) 
 

Value:

GRAPH_TYPEDEFS(Graph)                                           \
    typedef Graph:: UEdge   UEdge;                      \
    typedef Graph:: UEdgeIt UEdgeIt;                    \
    typedef Graph:: IncEdgeIt   IncEdgeIt;
This #define creates the same convenience typedefs as defined by GRAPH_TYPEDEFS(Graph) and three more, namely it creates UEdge, UEdgeIt, IncEdgeIt, BoolUEdgeMap, IntUEdgeMap, DoubleUEdgeMap.

Note:
If G it a template parameter, it should be used in this way.
       UNDIRGRAPH_TYPEDEFS(typename G)
Warning:
There are no typedefs for the graph maps because of the lack of template typedefs in C++.


Function Documentation

int lemon::countItems const Graph g  )  [inline]
 

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

int lemon::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 structures it is specialized to run in O(1).

Todo:
refer how to specialize it

int lemon::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 structures it is specialized to run in O(1).

int lemon::countUEdges const Graph g  )  [inline]
 

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

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

This function counts the number of the out-edges from node n in the graph.

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

This function counts the number of the in-edges to node n in the graph.

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

This function counts the number of the inc-edges to node n in the graph.

Graph::Edge lemon::findEdge const Graph g,
typename Graph::Node  u,
typename Graph::Node  v,
typename Graph::Edge  prev = INVALID
[inline]
 

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)) {
        ...
      }

Graph::UEdge lemon::findUEdge const Graph g,
typename Graph::Node  u,
typename Graph::Node  v,
typename Graph::UEdge  prev = INVALID
[inline]
 

Finds an uedge 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(UEdge e = findUEdge(g,u,v); e != INVALID; 
          e = findUEdge(g,u,v,e)) {
        ...
      }

void lemon::copyMap Target &  target,
const Source &  source,
ItemIt  it,
const Ref &  ref
 

This function copies the source map to the target map. It uses the given iterator to iterate on the data structure and it uses the ref mapping to convert the source's keys to the target's keys.

void lemon::copyMap Target &  target,
const Source &  source,
ItemIt  it
 

Copy the source map to the target map. It uses the given iterator to iterate on the data structure.

GraphCopy<Target, Source> lemon::copyGraph Target &  target,
const Source &  source
 

Copy a graph to an other graph. The usage of the function:

      copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);

After the copy the nr map will contain the mapping from the source graph's nodes to the target graph's nodes and the ecr will contain the mapping from the target graph's edges to the source's edges.

UGraphCopy<Target, Source> lemon::copyUGraph Target &  target,
const Source &  source
 

Copy a graph to an other graph. The usage of the function:

      copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);

After the copy the nr map will contain the mapping from the source graph's nodes to the target graph's nodes and the ecr will contain the mapping from the target graph's edges to the source's edges.


Generated on Fri Feb 3 18:40:01 2006 for LEMON by  doxygen 1.4.6