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

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