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