Loading...
Searching...
No Matches
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 | BpGraphCopy< From, To >
| Class to copy a bipartite 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...

## Macros

#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.
#define | BPGRAPH_TYPEDEFS(BpGraph)
| Create convenience typedefs for the bipartite graph types and iterators.
#define | TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)
| Create convenience typedefs for the bipartite 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 | countRedNodes (const Graph &g)
| Function to count the red nodes in the graph.
template<typename Graph>
int | countBlueNodes (const Graph &g)
| Function to count the blue 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 GR>
bool | undirected (const GR &g)
| Check whether a graph is undirected.
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 From, typename To>
BpGraphCopy< From, To > | bpGraphCopy (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.

## Macro Definition Documentation

## DIGRAPH_TYPEDEFS

#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.

## TEMPLATE_DIGRAPH_TYPEDEFS

#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.

## GRAPH_TYPEDEFS

#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.

## TEMPLATE_GRAPH_TYPEDEFS

#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.

## BPGRAPH_TYPEDEFS

#define BPGRAPH_TYPEDEFS | ( |  | BpGraph | ) |

This `#define` creates the same convenient type definitions as defined by GRAPH_TYPEDEFS(BpGraph) and ten more, namely it creates `RedNode`, `RedNodeIt`, `BoolRedNodeMap`, `IntRedNodeMap`, `DoubleRedNodeMap`, `BlueNode`, `BlueNodeIt`, `BoolBlueNodeMap`, `IntBlueNodeMap`, `DoubleBlueNodeMap`.

Note
  If the graph type is a dependent type, ie. the graph type depend on a template parameter, then use `TEMPLATE_BPGRAPH_TYPEDEFS()` macro.

## TEMPLATE_BPGRAPH_TYPEDEFS

#define TEMPLATE_BPGRAPH_TYPEDEFS | ( |  | BpGraph | ) |

See also
  BPGRAPH_TYPEDEFS

Note
  Use this macro, if the graph type is a dependent type, ie. the graph type depend on a template parameter.

## Function Documentation

## countItems()

template<typename Graph, typename Item>

int 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.

## countNodes()

template<typename Graph>

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 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.

## countRedNodes()

template<typename Graph>

int countRedNodes | ( | const Graph & | g | ) |

inline

This function counts the red 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).

If the graph contains a redNum() member function and a NodeNumTag tag then this function calls directly the member function to query the cardinality of the node set.

## countBlueNodes()

template<typename Graph>

int countBlueNodes | ( | const Graph & | g | ) |

inline

This function counts the blue 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).

If the graph contains a blueNum() member function and a NodeNumTag tag then this function calls directly the member function to query the cardinality of the node set.

## countArcs()

template<typename Graph>

int 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.

## countEdges()

template<typename Graph>

int 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.

## countOutArcs()

template<typename Graph>

int 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`.

## countInArcs()

template<typename Graph>

int 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`.

## countIncEdges()

template<typename Graph>

int 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`.

## undirected()

template<typename GR>

bool undirected | ( | const GR & | g | ) |

This function returns `true` if the given graph is undirected.

## digraphCopy()

template<typename From, typename To>

DigraphCopy< From, To > 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();
lemon::digraphCopy
DigraphCopy< From, To > digraphCopy(const From &from, To &to)
Copy a digraph to another digraph.
Definition core.h:845

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()

template<typename From, typename To>

GraphCopy< From, To > 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();
lemon::graphCopy
GraphCopy< From, To > graphCopy(const From &from, To &to)
Copy a graph to another graph.
Definition core.h:1150

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

## bpGraphCopy()

template<typename From, typename To>

BpGraphCopy< From, To > bpGraphCopy | ( | const From & | from,
|  | To & | to )

This function copies a graph to another graph. The complete usage of it is detailed in the BpGraphCopy 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
  BpGraphCopy

## findArc()

template<typename Graph>

Graph::Arc 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)) {
...
}
lemon::findArc
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.
Definition core.h:1658
lemon::INVALID
const Invalid INVALID
Invalid iterators.
Definition base.cc:32

Note
  ConArcIt provides iterator interface for the same functionality.

See also
  ConArcIt
  ArcLookUp, AllArcLookUp, DynArcLookUp

## findEdge()

template<typename Graph>

Graph::Edge 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)) {
...
}
lemon::findEdge
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.
Definition core.h:1781

Note
  ConEdgeIt provides iterator interface for the same functionality.

See also
  ConEdgeIt