Node Maps (node_map)

Definition

An instance of the data type node_map<E> is a map for the nodes of a graph G, i.e., equivalent to map<node,E> (cf. Maps). It can be used as a dynamic variant of the data type node_array (cf. Node Arrays).

Creation

node_map<E>	M;	introduces a variable M of type node_map<E> and initializes it to the map with empty domain.
node_map<E>	M(graph G);	introduces a variable M of type node_map<E> and initializes it with a mapping m from the set of all nodes of G into the set of variables of type E. The variables in the range of m are initialized by a call of the default constructor of type E.
node_map<E>	M(graph G, E x);	introduces a variable M of type node_map<E> and initializes it with a mapping m from the set of all nodes of G into the set of variables of type E. The variables in the range of m are initialized with a copy of x.

Operations

graph	M.get_graph()	returns a reference to the graph of M.
void	M.init()	makes M a node map with empty domain.
void	M.init(graph G)	makes M a mapping m from the set of all nodes of G into the set of variables of type E. The variables in the range of m are initialized by a call of the default constructor of type E.
void	M.init(graph G, E x)	makes M a mapping m from the set of all nodes of G into the set of variables of type E. The variables in the range of m are initialized with a copy of x.
E&	M[node v]	returns the variable M(v).

Implementation

Node maps are implemented by an efficient hashing method based on the internal numbering of the nodes. An access operation takes expected time O(1).