General Graph Utilities
[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  EdgeLookUp
 Fast edge look up between given endpoints. More...
class  AllEdgeLookUp
 Fast look up of all edges between given endpoints. 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 UGRAPH_TYPEDEFS(Graph)
 Creates convenience typedefs for the undirected graph types and iterators.
#define BPUGRAPH_TYPEDEFS(Graph)
 Creates convenience typedefs for the bipartite undirected graph types and iterators.

Functions

template<typename Graph, typename Item>
int countItems (const Graph &g)
 Function to count the items in the graph.
template<typename Graph>
int countNodes (const Graph &g)
 Function to count the nodes in the graph.
template<typename Graph>
int countANodes (const Graph &g)
 Function to count the anodes in the graph.
template<typename Graph>
int countBNodes (const Graph &g)
 Function to count the bnodes in the graph.
template<typename Graph>
int countEdges (const Graph &g)
 Function to count the edges in the graph.
template<typename Graph>
int countUEdges (const Graph &g)
 Function to count the undirected edges in the graph.
template<typename Graph>
int 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 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 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 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 findUEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::UEdge p=INVALID)
 Finds an uedge between two nodes of a graph.
template<typename Target, typename Source, typename ItemIt, typename Ref>
void copyMap (Target &target, const Source &source, ItemIt it, const Ref &ref)
 Copy a map.
template<typename Target, typename Source, typename ItemIt>
void copyMap (Target &target, const Source &source, ItemIt it)
 Copy the source map to the target map.
template<typename Target, typename Source>
GraphCopy< Target, Source > copyGraph (Target &target, const Source &source)
 Copy a graph to another graph.
template<typename Target, typename Source>
UGraphCopy< Target, Source > copyUGraph (Target &target, const Source &source)
 Copy a graph to another graph.


Define Documentation

#define GRAPH_TYPEDEFS ( Graph   ) 

This #define creates convenience typedefs for the following types of Graph: Node, NodeIt, Edge, EdgeIt, InEdgeIt, OutEdgeIt

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 UGRAPH_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,

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

#define BPUGRAPH_TYPEDEFS ( Graph   ) 

Value:

UGRAPH_TYPEDEFS(Graph)                    \
    typedef Graph::ANodeIt ANodeIt;         \
    typedef Graph::BNodeIt BNodeIt;
This #define creates the same convenience typedefs as defined by UGRAPH_TYPEDEFS(Graph) and two more, namely it creates ANodeIt, BNodeIt,

Note:
If G it a template parameter, it should be used in this way.
       BPUGRAPH_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::countANodes ( const Graph g  )  [inline]

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

Todo:
refer how to specialize it

int lemon::countBNodes ( const Graph g  )  [inline]

This function counts the bnodes in the graph. The complexity of the function is O(bn) 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)) {
        ...
      }

See also:
EdgeLookUp AllEdgeLookup

ConEdgeIt

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

Finds an uedge from node u to node v in graph g. If the node u and node v is equal then each loop edge will be enumerated.

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

See also:
ConEdgeIt

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 another 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 another graph. The usage of the function:

      copyUGraph(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 Tue Oct 31 09:49:38 2006 for LEMON by  doxygen 1.5.1