/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2007

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 namespace lemon{

 /*!

 \page maps-page Maps

 Maps play a 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 Key;

   typedef double Value;

 \endcode

 A map can be 

 \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),

 \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both

 (\ref lemon::concepts::ReadWriteMap "ReadWriteMap").

 There also exists a special type of

 ReadWrite map called \ref lemon::concepts::ReferenceMap "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

 \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 a floating point value to each edge, you can do

 it like this.

 \code

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

 \endcode

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

 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 etc.)

 There are two ways to 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(Key,const Value &)

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

 insist on the second way.

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

 \subsection read-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 \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 Value;

   typedef Graph::Edge Key;

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

 };

 \endcode

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

 \code

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

 {

   Value operator[](Key e) const { return M_PI;}

 };

 \endcode

 Here is a bit more complex example.

 It provides a length function obtained

 from a base length function shifted by a potential difference.

 \code

 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) {};

 };

 \endcode

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

 \code

   ...

   ReducedLengthMap rm(g,len,pot);

   Dijkstra<Graph,ReducedLengthMap> dij(g,rm);

   dij.run(s);

   ...

 \endcode

 \subsection write-maps Writable Maps

 To be written...

 \subsection side-effect-maps Maps with Side Effect

 To be written...

 */

 }