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). New: Since node_map<E> is derived from node_array<E> node maps can be passed (by reference) to functions with node array parameters. In particular, all LEDA graph algorithms expecting a node_array<E>& argument can be passed a node_map<E> instead.

#include < LEDA/graph/node_map.h >

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(const graph_t& 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(const graph_t& 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

const graph_t&	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(const graph_t& 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(const graph_t& 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.
bool	M.use_node_data(const graph_t& G, E x)
		use free data slots in the nodes 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.
E&	M[node v]	returns the variable M(v).

Implementation

Node maps either use free node_slots or they are implemented by an efficient hashing method based on the internal numbering of the nodes or they use. In each case an access operation takes expected time O(1).