Maps I.

In the previous section we discussed graph topology. That is the skeleton a complex graph represented data-set needs. But how to assign the data itself to that skeleton?
Here come the maps in.

Introduction to maps

Maps play a central role in LEMON. As their name suggests, they map a certain range of keys to certain values. In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:

  typedef Edge Key;
  typedef double Value;

(Except matrix maps, they have two key types.)

To make easy to use them - especially as template parameters - there are map concepts like by graph classes.

• ReadMap - values can be read out with the operator[].

   value_typed_variable = map_instance[key_value]; 
  

• WriteMap - values can be set with the set() member function.

   map_instance.set(key_value, value_typed_expression); 
  

• ReadWriteMap - it's just a shortcut to indicate that the map is both readable and writable. It is delivered from them.
• ReferenceMap - a subclass of ReadWriteMap. It has two additional typedefs Reference and ConstReference and two overloads of operator[] to providing you constant or non-constant reference to the value belonging to a key, so you have a direct access to the memory address where it is stored.
• And there are the Matrix version of these maps, where the values are assigned to a pair of keys. The keys can be different types. (ReadMatrixMap, WriteMatrixMap, ReadWriteMatrixMap, ReferenceMatrixMap)

Graphs' maps

Every mappable graph class has two public templates: NodeMap<VALUE> and EdgeMap<VALUE> satisfying the GraphMap concept. If you want to assign data to nodes, just declare a NodeMap with the corresponding type. As an example, think of a edge-weighted directed graph.

 ListGraph::EdgeMap<int>  weight(graph); 

You can see that the map needs the graph whose edges will mapped, but nothing more.

If the graph class is extendable or erasable the map will automatically follow the changes you make. If a new node is added a default value is mapped to it. You can define the default value by passing a second argument to the map's constructor.

 ListGraph::EdgeMap<int>  weight(graph, 13); 

But keep in mind that VALUE has to have copy constructor.

Of course VALUE can be a rather complex type.

For practice let's see the following template function (from maps-summary.cc in the demo directory)!

template < typename GRAPH, typename MAP >
typename MAP::Value  summary( GRAPH& gr, MAP& m )
{
  typename MAP::Value  summ = typename MAP::Value();
  
  for( typename GRAPH::NodeIt  n(gr); n != lemon::INVALID; ++n )
    summ += m[n];

  return summ;
}

The task is simple. We need the summary of some kind of data assigned to a graph's nodes. (Whit a little trick the summary can be calculated only to a sub-graph without changing this code. See SubGraph techniques - that's LEMON's true potential.)

And the usage is simpler than the declaration suggests. The compiler deduces the template specialization, so the usage is like a simple function call.

  std::cout << "The summary of assigned values is " << summary(gr,value) << std::endl;

Most of the time you will probably use graph maps, but keep in mind, that in LEMON maps are more general and can be used widely.

If you want some 'real-life' examples see the next page, where we discuss Algorithms (coming soon) and will use maps hardly. Or if you want to know more about maps read these advanced map techniques.