Two Dimensional Node Arrays (node_matrix)

Definition

An instance M of the parameterized data type node_matrix<E> is a partial mapping from the set of node pairs Vx V of a graph to the set of variables of data type E, called the element type of M. The domain I of M is called the index set of M. M is said to be valid for all node pairs in I. A node matrix can also be viewed as a node array with element type node_array<E> (node_array<node_array<E> >).

Creation

node_matrix<E>	M;	creates an instance M of type node_matrix<E> and initializes the index set of M to the empty set.
node_matrix<E>	M(graph G);	creates an instance M of type node_matrix<E> and initializes the index set to be the set of all node pairs of graph G, i.e., M is made valid for all pairs in V x V where V is the set of nodes currently contained in G.
node_matrix<E>	M(graph G, E x);	creates an instance M of type node_matrix<E> and initializes the index set of M to be the set of all node pairs of graph G, i.e., M is made valid for all pairs in V x V where V is the set of nodes currently contained in G. In addition, M(v,w) is initialized with x for all nodes v,w in V.

Operations

void	M.init(graph G)	sets the index set of M to Vx V, where V is the set of all nodes of G.
void	M.init(graph G, E x)	sets the index set of M to Vx V, where V is the set of all nodes of G and initializes M(v,w) to x for all v,w in V.
node_array<E>&	M[node v]	returns the node_array M(v).
E&	M(node v, node w)	returns the variable M(v,w). Precondition: M must be valid for v and w.

Implementation

Node matrices for a graph G are implemented by vectors of node arrays and an internal numbering of the nodes of G. The access operation takes constant time, the init operation takes time O(n^2), where n is the number of nodes currently contained in G. The space requirement is O(n^2). Note that a node matrix is only valid for the nodes contained in G at the moment of the matrix declaration or initialization (init). Access operations for later added nodes are not allowed.