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 GRAPH_TYPEDEFS | ( | Graph | ) |
This #define
creates convenience typedefs for the following types of Graph:
Node
, NodeIt
, Edge
, EdgeIt
, InEdgeIt
, OutEdgeIt
G
it a template parameter, it should be used in this way. GRAPH_TYPEDEFS(typename G)
#define UGRAPH_TYPEDEFS | ( | Graph | ) |
Value:
GRAPH_TYPEDEFS(Graph) \ typedef Graph:: UEdge UEdge; \ typedef Graph:: UEdgeIt UEdgeIt; \ typedef Graph:: IncEdgeIt IncEdgeIt;
#define
creates the same convenience typedefs as defined by GRAPH_TYPEDEFS(Graph) and three more, namely it creates UEdge
, UEdgeIt
, IncEdgeIt
,
G
it a template parameter, it should be used in this way. UGRAPH_TYPEDEFS(typename G)
#define BPUGRAPH_TYPEDEFS | ( | Graph | ) |
Value:
UGRAPH_TYPEDEFS(Graph) \ typedef Graph::ANodeIt ANodeIt; \ typedef Graph::BNodeIt BNodeIt;
#define
creates the same convenience typedefs as defined by UGRAPH_TYPEDEFS(Graph) and two more, namely it creates ANodeIt
, BNodeIt
,
G
it a template parameter, it should be used in this way. BPUGRAPH_TYPEDEFS(typename G)
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).
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).
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).
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
.
u
to v
as it follows.
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
.
u
to v
as it follows.
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.