- graph:
G = (V, E)
V
= vertices, nodesE
= edges, i.e., pairs(n, m)
of nodes; [directed] links between nodes
- node
n
is adjacent to nodem
if there is an edge(n, m)
or(m, n)
- generally there are multiple nodes adjacent to a node
n
- for a node it is possible to get iterators for the adjacent nodes
- generally there are multiple nodes adjacent to a node
- edge
e = (n, m)
is incident to nodesn
andm
- source node
n
and target nodem
can be access directly - for a node it is possible get iterator for the incident edges
- source node
- nodes and edges may have properties:
- nodes may, e.g., have a _position, a supply, a demand, a color, etc.
- edges may, e.g., have a weight, a capacity, a length, a flow, a color, etc.
Not all of the functions need to modelled for all algorithms
Expression | Type | Semantics |
---|---|---|
g |
G |
G is a type modelling the Graph concept and g is an instance thereof |
vit |
using VI = typename G::vertex_iterator |
an iterator over all vertices and instances there of |
v = *vit |
using V = typename G::vertex_descriptor |
a handle to access a specific node |
eit |
using EI = typename G::edge_iterator |
an iterator over all edges and instances thereof |
e = *eit |
using E = typename G::edge_descriptor |
a handle to access a specific edge |
ait |
using AI = typename G::adjacency_iterator |
an iterator over adjacent nodes |
v = *ait |
typename G::vertex_descriptor |
access to the adjacent node |
oit |
using II = typename G::out_edge_iterator |
an iterator over incident edges (in edge direction) |
e = *oit |
typename G::edge_descriptor |
access to the incident edge |
iit |
using II = typename G::in_edge_iterator |
an iterator over incident edges (against edge direction) |
e = *oit |
typename G::edge_descriptor |
access to the incident edge |
s = source(e, g) |
V |
source node incident to e |
t = target(e, g) |
V |
target node incident to e |
vertices(g) |
pair<VI, VI> |
begin/end iterator for the range of nodes |
edges(g) |
pair<EI, EI> |
begin/end iterator for the range of edges |
adjacent_vertices(v, g) |
pair<AI, AI> |
access to iterators for the nodes adjacent to v |
out_edges(v, g) |
pair<OI, OI> |
begin/end iterator for the range of edges incident to v leading from v |
in_edges(v, g) |
pair<II, II> |
begin/end iterator for the range of edges incident to v leading to v |
Access to a property associated with a node or an edge. The key is a vertex descriptor to access a node property or an edge descriptor to access an edge property
Expression | Type | Semantics |
---|---|---|
pm |
PM |
a class modelling a property map and an instance thereof |
p = get(pm, key) |
typename PM::type |
read the value of the property for the object key |
put(pm, key, p) |
set the value of the property for th object key to p |
|
pm[key] |
typename PM::reference |
lvalue access to the property type |