Definition
An instance A
of the parameterized data type edge_array<E>
is a partial mapping from the edge set of a graph G
to the set of
variables of type E
, called the element type of the array. The domain
I
of A
is called the index set of A
and A(e)
is called the element
at position e
. A
is said to be valid for all edges in I
.
The array access operator A[e] checks its precondition
(A
must be valid for e
). The check can be turned off by compiling
with the flag -DLEDA_CHECKING_OFF
.
#include < LEDA/graph/edge_array.h >
Creation
edge_array< E> | A | creates an instance A of type edge_array<E> with empty index set. |
edge_array< E> | A(const graph_t& G) | creates an instance A of type edge_array<E> and initializes the index set of A to be the current edge set of graph G . |
edge_array< E> | A(const graph_t& G, E x) | creates an instance A of type edge_array<E>, sets the index set of A to the current edge set of graph G and initializes A(v) with x for all edges v of G . |
edge_array< E> | A(const graph_t& G, int n, E x) | |
creates an instance A
of type edge_array<E> valid for
up to n
edges of graph G
and initializes A(e)
with x
for all edges e
of G
.
Precondition n > = | E| . A is also valid for the next n - | E| edges added to G . |
Operations
Implementation
Edge arrays for a graph G are implemented by C++vectors and an internal numbering of the nodes and edges of G . The access operation takes constant time, init takes time O(n) , where n is the number of edges in G . The space requirement is O(n) .
Remark: An edge array is only valid for a bounded number of edges of G . This number is either the number of edges of G at the moment of creation of the array or it is explicitely set by the user. Dynamic edge arrays can be realized by edge maps (cf. section Edge Maps).