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: Node Maps ( node_map Up: Graphs and Related Data Previous: Edge Arrays ( edge_array Contents Index

LEDA research project
2000-02-09

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.

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.