Definition
An instance A of the parameterized data type node_array<E>
is a partial mapping from the node 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(v) is called the element
at position v. A is said to be valid for all nodes in I.
The array access operator A[v] checks its precondition
(A must be valid for v). The check can be turned off by compiling
with the flag -DLEDA_CHECKING_OFF
.
#include < LEDA/graph/node_array.h >
Creation
node_array<E> | A | creates an instance A of type node_array<E> with empty index set. |
node_array<E> | A(const graph_t& G) | creates an instance A of type node_array<E> and initializes the index set of A to the current node set of graph G. |
node_array<E> | A(const graph_t& G, E x) | creates an instance A of type node_array<E>, sets the index set of A to the current node set of graph G and initializes A(v) with x for all nodes v of G. |
node_array<E> | A(const graph_t& G, int n, E x) | |
creates an instance A of type node_array<E> valid for
up to n nodes of graph G and initializes A(v) with x
for all nodes v of G.
Precondition n > = | V|. A is also valid for the next n - | V| nodes added to G. |
Operations
Implementation
Node 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 nodes in G. The space requirement is O(n).
Remark: A node array is only valid for a bounded number of nodes of G. This number is either the number of nodes of G at the moment of creation of the array or it is explicitely set by the user. Dynamic node arrays can be realized by node maps (cf. section Node Maps).