next up previous contents index
Next: Node Maps ( node_map Up: Graphs and Related Data Previous: Edge Arrays ( edge_array   Contents   Index


Face Arrays ( face_array )

Definition

An instance A of the parameterized data type face_array<E> is a partial mapping from the face 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 f. A is said to be valid for all faces in I.

#include < LEDA/face _array.h >

Creation

face_array<E> A creates an instance A of type face_array<E> with empty index set.

face_array<E> A(graph G) creates an instance A of type face_array<E> and initializes the index set of A to the current face set of graph G.

face_array<E> A(graph G, E x) creates an instance A of type face_array<E>, sets the index set of A to the current face set of graph G and initializes A(f ) with x for all faces f of G.

face_array<E> A(graph G, int n, E x) creates an instance A of type face_array<E> valid for up to n faces of graph G and initializes A(f ) with x for all faces f of G.
Precondition n > = | V|.
A is also valid for the next n - | V| faces added to G.

Operations

graph A.get_graph() returns a reference to the graph of A.

E& A[face f] returns the variable A(f ).
Precondition A must be valid for f.

void A.init(graph G) sets the index set I of A to the face set of G, i.e., makes A valid for all faces of G.

void A.init(graph G, E x) makes A valid for all faces of G and sets A(f )= x for all faces f of G.

void A.init(graph G, int n, E x)
    makes A valid for at most n faces of G and sets A(f )= x for all faces f of G.
Precondition n > = | V|.
A is also valid for the next n - | V| faces added to G.

bool A.use_face_data(graph G, E x)
    use free data slots in the faces 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 faces and edges of G. The access operation takes constant time, init takes time O(n), where n is the number of faces in G. The space requirement is O(n).

Remark: A face array is only valid for a bounded number of faces of G. This number is either the number of faces of G at the moment of creation of the array or it is explicitely set by the user. Dynamic face arrays can be realized by face maps (cf. section Node Maps).


next up previous contents index
Next: Node Maps ( node_map Up: Graphs and Related Data Previous: Edge Arrays ( edge_array   Contents   Index
LEDA research project
2000-02-09