/*!

\page maps Maps

Maps play central role in LEMON. As their name suggests, they map a

certain range of \e keys to certain \e values. Each map has two

<tt>typedef</tt>'s to determine the types of keys and values, like this:

\code

  typedef Edge KeyType;

  typedef double ValueType;

\endcode

A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both

(ReadWrite Map). There also exists a special type of

ReadWrite map called <em>reference map</em>. 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

\c EdgeMap and \c 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 \c G defined as

\code

  ListGraph G;

\endcode

and you want to assign floating point value to each edge, you can do

it like this.

\code

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

\endcode

The value of a readable map can be obtained by <tt>operator[]</tt>.

\code

  d=length[e];

\endcode

where \c e is an instance of \c ListGraph::Edge.

(Or anything else

that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or

\c ListGraph::OutEdgeIt)

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

- In case of a <em>reference map</em> <tt>operator[]</tt>

gives you a reference to the

value, thus you can use this.

\code

  length[e]=3.5;

\endcode

- <em>Writable maps</em> have

a member function \c set(KeyType,const ValueType &)

for this purpose.

\code

  length.set(e,3.5);

\endcode

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 an generic algorithm, you should

insist on the second method.

\section how-to-write-your-own-map How to Write Your Own Maps

\subsection read-maps Readable Maps

The readable maps are very frequently used as the input of the

algorithms.  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 \c Graph is the

type of the particular graph structure you use.

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

\code

struct MyMap 

{

  typedef double ValueType;

  typedef Graph::Edge KeyType;

  double operator[](KeyType e) const { return M_PI;}

};

\endcode

An alternative way to define maps is to use \c MapBase

\todo For this, \c MapBase seems to be a better name then \c NullMap.

\code

struct MyMap : public MapBase<Graph::Edge,double>

{

  ValueType operator[](KeyType e) const { return M_PI;}

};

\endcode

Here is a bit more complex example.

It provides a length function which is obtained

from a base length function shifted by a potential difference.

\code

class MyLengthMap  : public MapBase<Graph::Edge,double>

{

  const Graph &G;

  const Graph::EdgeMap<double> &orig_len;

  const Graph::NodeMap<double> &pot;

public:

  ValueType operator[](KeyType e) const {

    return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e));

  }

  MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p)

    : G(g), orig_len(o), pot(p) {};

};

\endcode

\subsection write-maps Writable Maps

To be written...

\subsection side-effect-maps Maps with Side Effect

To be written...

*/