next up previous contents index
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.

#include < LEDA/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(graph 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(graph 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(graph 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

graph 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(graph 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(graph 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(graph 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(graph G, E x)
    use free data slots in the nodes of G (if available) for storing the entries of A. 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 up previous contents index
Next: Edge Arrays ( edge_array Up: Graphs and Related Data Previous: Parameterized Planar Maps (   Contents   Index
LEDA research project
2000-02-09