Next: Edge Arrays ( edge_array Up: Graphs and Related Data Previous: Parameterized Planar Maps (   Contents   Index

# Node Arrays ( node_array )

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 with empty index set. node_array< E> A(const graph_t& G) creates an instance A of type node_array 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, 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 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

 const graph_t& A.get_graph() returns a reference to the graph of A . E& A[node v] returns the variable A(v) . Precondition A must be valid for v . void A.init(const graph_t& G) sets the index set I of A to the node set of G , i.e., makes A valid for all nodes of G . void A.init(const graph_t& G, E x) makes A valid for all nodes of G and sets A(v) = x for all nodes v of G . void A.init(const graph_t& G, int n, E x) makes A valid for at most n nodes of G and sets A(v) = x for all nodes v of G . Precondition n > = | V| . A is also valid for the next n - | V| nodes added to G . bool A.use_node_data(const graph_t& G) use free data slots in the nodes of G (if available) for storing the entries of A . If no free data slot is available in G , an ordinary node_arrayis created. The number of additional data slots in the nodes and edges of a graph can be specified in the graph::graph(int n_slots, int e_slots) constructor. The result is true if a free slot is available and false otherwise. bool A.use_node_data(const graph_t& G, E x) use free data slots in the nodes of G (if available) for storing the entries of A and initializes A(v) = x for all nodes v of G . If no free data slot is available in G , an ordinary node_array is created. The number of additional data slots in the nodes and edges of a graph can be specified in the graph::graph(int n_slots, int e_slots) constructor. The result is true if a free slot is available and false otherwise.

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).

Next: Edge Arrays ( edge_array Up: Graphs and Related Data Previous: Parameterized Planar Maps (   Contents   Index
Christian Uhrig 2017-04-07