next up previous contents index
Next: Face Arrays ( face_array Up: Graphs and Related Data Previous: Node Arrays ( node_array   Contents   Index


Edge Arrays ( edge_array )

Definition

An instance A of the parameterized data type edge_array<E> is a partial mapping from the edge 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(e) is called the element at position e. A is said to be valid for all edges in I.

#include < LEDA/edge _array.h >

Creation

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

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

edge_array<E> A(graph G, E x) creates an instance A of type edge_array<E>, sets the index set of A to the current edge set of graph G and initializes A(v) with x for all edges v of G.

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

Operations

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

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

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

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

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

bool A.use_edge_data(graph G, E x)
    use free data slots in the edges 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

Edge 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 edges in G. The space requirement is O(n).

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


next up previous contents index
Next: Face Arrays ( face_array Up: Graphs and Related Data Previous: Node Arrays ( node_array   Contents   Index
LEDA research project
2000-02-09