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 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
.
TEMPLATE_DIGRAPH_TYPEDEFS()
macro. #define TEMPLATE_DIGRAPH_TYPEDEFS | ( | Digraph | ) |
#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
.
TEMPLATE_GRAPH_TYPEDEFS()
macro. #define TEMPLATE_GRAPH_TYPEDEFS | ( | Graph | ) |
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).
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).
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).
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.
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.
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
.
Thus you can iterate through each arc from u
to v
as it follows.
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
.
Thus you can iterate through each edge between u
and v
as it follows.