Maps

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

  typedef Edge Key;
  typedef double Value;

A map can be readable (ReadMap, for short), writable (WriteMap) or both (ReadWriteMap). There also exists a special type of ReadWrite map called reference map. In addition that you can read and write the values of a key, a reference map can also give you a reference to the value belonging to a key, so you have a direct access to the memory address where it is stored.

Each graph structure in LEMON provides two standard map templates called EdgeMap and NodeMap. Both are reference maps and you can easily assign data to the nodes and to the edges of the graph. For example if you have a graph g defined as

  ListGraph g;

and you want to assign a floating point value to each edge, you can do it like this.

  ListGraph::EdgeMap<double> length(g);

Note that you must give the underlying graph to the constructor.

The value of a readable map can be obtained by operator[].

  d=length[e];

where e is an instance of ListGraph::Edge. (Or anything else that converts to ListGraph::Edge, like ListGraph::EdgeIt or ListGraph::OutEdgeIt etc.)

There are two ways to assign a new value to a key

In case of a reference map operator[] gives you a reference to the value, thus you can use this.
```
  length[e]=3.5;
```
Writable maps have a member function set(Key,const Value &) for this purpose.
```
  length.set(e,3.5);
```

The first case is more comfortable and if you store complex structures in your map, it might be more efficient. However, there are writable but not reference maps, so if you want to write a generic algorithm, you should insist on the second way.

How to Write Your Own Maps

Readable Maps

Readable maps are very frequently used as the input of an algorithm. For this purpose the most straightforward way is the use of the default maps provided by LEMON's graph structures. Very often however, it is more convenient and/or more efficient to write your own readable map.

You can find some examples below. In these examples Graph is the type of the particular graph structure you use.

This simple map assigns $\pi$ to each edge.

struct MyMap 
{
  typedef double Value;
  typedef Graph::Edge Key;
  double operator[](Key e) const { return PI;}
};

An alternative way to define maps is to use MapBase

struct MyMap : public MapBase<Graph::Edge,double>
{
  Value operator[](Key e) const { return PI;}
};

Here is a bit more complex example. It provides a length function obtained from a base length function shifted by a potential difference.

class ReducedLengthMap  : public MapBase<Graph::Edge,double>
{
  const Graph &g;
  const Graph::EdgeMap<double> &orig_len;
  const Graph::NodeMap<double> &pot;
  
public:
  Value operator[](Key e) const {
    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
  }
  
  ReducedLengthMap(const Graph &_g,
                   const Graph::EdgeMap &_o,
                   const Graph::NodeMap &_p)
    : g(_g), orig_len(_o), pot(_p) {};
};

Then, you can call e.g. Dijkstra algoritm on this map like this:

  ...
  ReducedLengthMap rm(g,len,pot);
  Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
  dij.run(s);
  ...

Writable Maps

To be written...

Maps with Side Effect

To be written...