Classes | Defines | Functions

Basic Graph Utilities

Tools and Utilities

Detailed Description

This group contains some simple basic graph utilities.

Classes

class  DigraphCopy< From, To >
 Class to copy a digraph. More...
class  GraphCopy< From, To >
 Class to copy a graph. More...
class  ConArcIt< GR >
 Iterator for iterating on parallel arcs connecting the same nodes. More...
class  ConEdgeIt< GR >
 Iterator for iterating on parallel edges connecting the same nodes. More...
class  DynArcLookUp< GR >
 Dynamic arc look-up between given endpoints. More...
class  ArcLookUp< GR >
 Fast arc look-up between given endpoints. More...
class  AllArcLookUp< GR >
 Fast look-up of all arcs between given endpoints. More...

Defines

#define DIGRAPH_TYPEDEFS(Digraph)
 Create convenience typedefs for the digraph types and iterators.
#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)
 Create convenience typedefs for the digraph types and iterators.
#define GRAPH_TYPEDEFS(Graph)
 Create convenience typedefs for the graph types and iterators.
#define TEMPLATE_GRAPH_TYPEDEFS(Graph)
 Create convenience typedefs for the graph types and iterators.

Functions

template<typename Graph , typename Item >
int countItems (const Graph &g)
 Function to count the items in a graph.
template<typename Graph >
int countNodes (const Graph &g)
 Function to count the nodes in the graph.
template<typename Graph >
int countArcs (const Graph &g)
 Function to count the arcs in the graph.
template<typename Graph >
int countEdges (const Graph &g)
 Function to count the edges in the graph.
template<typename Graph >
int countOutArcs (const Graph &g, const typename Graph::Node &n)
 Function to count the number of the out-arcs from node n.
template<typename Graph >
int countInArcs (const Graph &g, const typename Graph::Node &n)
 Function to count the number of the in-arcs 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 From , typename To >
DigraphCopy< From, To > digraphCopy (const From &from, To &to)
 Copy a digraph to another digraph.
template<typename From , typename To >
GraphCopy< From, To > graphCopy (const From &from, To &to)
 Copy a graph to another graph.
template<typename Graph >
Graph::Arc findArc (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Arc prev=INVALID)
 Find an arc between two nodes of a digraph.
template<typename Graph >
Graph::Edge findEdge (const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge p=INVALID)
 Find an edge between two nodes of a graph.

Define Documentation

#define DIGRAPH_TYPEDEFS (   Digraph)

This #define creates convenient type definitions for the following types of Digraph: Node, NodeIt, Arc, ArcIt, InArcIt, OutArcIt, BoolNodeMap, IntNodeMap, DoubleNodeMap, BoolArcMap, IntArcMap, DoubleArcMap.

Note:
If the graph type is a dependent type, ie. the graph type depend on a template parameter, then use TEMPLATE_DIGRAPH_TYPEDEFS() macro.
#define TEMPLATE_DIGRAPH_TYPEDEFS (   Digraph)
See also:
DIGRAPH_TYPEDEFS
Note:
Use this macro, if the graph type is a dependent type, ie. the graph type depend on a template parameter.
#define GRAPH_TYPEDEFS (   Graph)

This #define creates the same convenient type definitions as defined by DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates Edge, EdgeIt, IncEdgeIt, BoolEdgeMap, IntEdgeMap, DoubleEdgeMap.

Note:
If the graph type is a dependent type, ie. the graph type depend on a template parameter, then use TEMPLATE_GRAPH_TYPEDEFS() macro.
#define TEMPLATE_GRAPH_TYPEDEFS (   Graph)
See also:
GRAPH_TYPEDEFS
Note:
Use this macro, if the graph type is a dependent type, ie. the graph type depend on a template parameter.

Function Documentation

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

This function counts the items (nodes, arcs etc.) in a graph. The complexity of the function is linear 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).

Note:
If the graph contains a nodeNum() member function and a NodeNumTag tag then this function calls directly the member function to query the cardinality of the node set.
int lemon::countArcs ( const Graph &  g) [inline]

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

Note:
If the graph contains a arcNum() member function and a ArcNumTag tag then this function calls directly the member function to query the cardinality of the arc set.
int lemon::countEdges ( const Graph &  g) [inline]

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

Note:
If the graph contains a edgeNum() member function and a EdgeNumTag tag then this function calls directly the member function to query the cardinality of the edge set.
int lemon::countOutArcs ( const Graph &  g,
const typename Graph::Node &  n 
) [inline]

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

int lemon::countInArcs ( const Graph &  g,
const typename Graph::Node &  n 
) [inline]

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

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 undirected graph g.

DigraphCopy<From, To> lemon::digraphCopy ( const From &  from,
To &  to 
)

This function copies a digraph to another digraph. The complete usage of it is detailed in the DigraphCopy class, but a short example shows a basic work:

      digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();

After the copy the nr map will contain the mapping from the nodes of the from digraph to the nodes of the to digraph and acr will contain the mapping from the arcs of the to digraph to the arcs of the from digraph.

See also:
DigraphCopy
GraphCopy<From, To> lemon::graphCopy ( const From &  from,
To &  to 
)

This function copies a graph to another graph. The complete usage of it is detailed in the GraphCopy class, but a short example shows a basic work:

      graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();

After the copy the nr map will contain the mapping from the nodes of the from graph to the nodes of the to graph and ecr will contain the mapping from the edges of the to graph to the edges of the from graph.

See also:
GraphCopy
Graph::Arc lemon::findArc ( const Graph &  g,
typename Graph::Node  u,
typename Graph::Node  v,
typename Graph::Arc  prev = INVALID 
) [inline]

This function finds an arc from node u to node v in the digraph g.

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

Returns:
The found arc or INVALID if there is no such an arc.

Thus you can iterate through each arc from u to v as it follows.

      for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
        ...
      }
Note:
ConArcIt provides iterator interface for the same functionality.
See also:
ConArcIt
ArcLookUp, AllArcLookUp, DynArcLookUp
Graph::Edge lemon::findEdge ( const Graph &  g,
typename Graph::Node  u,
typename Graph::Node  v,
typename Graph::Edge  p = INVALID 
) [inline]

This function finds an edge from node u to node v in graph g. If node u and node v is equal then each loop edge will be enumerated once.

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 between u and v as it follows.

      for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
        ...
      }
Note:
ConEdgeIt provides iterator interface for the same functionality.
See also:
ConEdgeIt
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines