doc/maps.dox
author zsuzska
Fri, 01 Apr 2005 08:16:35 +0000
changeset 1285 bf1840562c67
parent 1167 ccbca6ba8b59
child 1788 614ce2dd3cba
permissions -rw-r--r--
corrections in docs
     1 namespace lemon{
     2 /*!
     3 
     4 \page maps-page Maps
     5 
     6 Maps play a central role in LEMON. As their name suggests, they map a
     7 certain range of \e keys to certain \e values. Each map has two
     8 <tt>typedef</tt>'s to determine the types of keys and values, like this:
     9 
    10 \code
    11   typedef Edge Key;
    12   typedef double Value;
    13 \endcode
    14 
    15 A map can be 
    16 \e readable (\ref lemon::concept::ReadMap "ReadMap", for short),
    17 \e writable (\ref lemon::concept::WriteMap "WriteMap") or both
    18 (\ref lemon::concept::ReadWriteMap "ReadWriteMap").
    19 There also exists a special type of
    20 ReadWrite map called \ref lemon::concept::ReferenceMap "reference map".
    21 In addition that you can
    22 read and write the values of a key, a reference map
    23 can also give you a reference to the
    24 value belonging to a key, so you have a direct access to the memory address
    25 where it is stored.
    26 
    27 Each graph structure in LEMON provides two standard map templates called
    28 \c EdgeMap and \c NodeMap. Both are reference maps and you can easily
    29 assign data to the nodes and to the edges of the graph. For example if you
    30 have a graph \c G defined as
    31 \code
    32   ListGraph G;
    33 \endcode
    34 and you want to assign a floating point value to each edge, you can do
    35 it like this.
    36 \code
    37   ListGraph::EdgeMap<double> length(G);
    38 \endcode
    39 Note that you must give the underlying graph to the constructor.
    40 
    41 The value of a readable map can be obtained by <tt>operator[]</tt>.
    42 \code
    43   d=length[e];
    44 \endcode
    45 where \c e is an instance of \c ListGraph::Edge.
    46 (Or anything else
    47 that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
    48 \c ListGraph::OutEdgeIt etc.)
    49 
    50 There are two ways to assign a new value to a key
    51 
    52 - In case of a <em>reference map</em> <tt>operator[]</tt>
    53 gives you a reference to the
    54 value, thus you can use this.
    55 \code
    56   length[e]=3.5;
    57 \endcode
    58 - <em>Writable maps</em> have
    59 a member function \c set(Key,const Value &)
    60 for this purpose.
    61 \code
    62   length.set(e,3.5);
    63 \endcode
    64 
    65 The first case is more comfortable and if you store complex structures in your
    66 map, it might be more efficient. However, there are writable but
    67 not reference maps, so if you want to write a generic algorithm, you should
    68 insist on the second way.
    69 
    70 \section how-to-write-your-own-map How to Write Your Own Maps
    71 
    72 \subsection read-maps Readable Maps
    73 
    74 Readable maps are very frequently used as the input of an
    75 algorithm.  For this purpose the most straightforward way is the use of the
    76 default maps provided by LEMON's graph structures.
    77 Very often however, it is more
    78 convenient and/or more efficient to write your own readable map.
    79 
    80 You can find some examples below. In these examples \c Graph is the
    81 type of the particular graph structure you use.
    82 
    83 
    84 This simple map assigns \f$\pi\f$ to each edge.
    85 
    86 \code
    87 struct MyMap 
    88 {
    89   typedef double Value;
    90   typedef Graph::Edge Key;
    91   double operator[](Key e) const { return M_PI;}
    92 };
    93 \endcode
    94 
    95 An alternative way to define maps is to use \c MapBase
    96 
    97 \todo For this, \c MapBase seems to be a better name then \c NullMap.
    98 
    99 \code
   100 struct MyMap : public MapBase<Graph::Edge,double>
   101 {
   102   Value operator[](Key e) const { return M_PI;}
   103 };
   104 \endcode
   105 
   106 Here is a bit more complex example.
   107 It provides a length function obtained
   108 from a base length function shifted by a potential difference.
   109 
   110 \code
   111 class ReducedLengthMap  : public MapBase<Graph::Edge,double>
   112 {
   113   const Graph &g;
   114   const Graph::EdgeMap<double> &orig_len;
   115   const Graph::NodeMap<double> &pot;
   116   
   117 public:
   118   Value operator[](Key e) const {
   119     return orig_len.get(e)-(pot.get(G.target(e))-pot.get(G.source(e)));
   120   }
   121   
   122   ReducedLengthMap(const Graph &_g,
   123                    const Graph::EdgeMap &o,
   124                    const Graph::NodeMap &p)
   125     : G(g), orig_len(o), pot(p) {};
   126 };
   127 \endcode
   128 
   129 Then, you can call e.g. Dijkstra algoritm on this map like this:
   130 \code
   131   ...
   132   ReducedLengthMap rm(g,len,pot);
   133   Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
   134   dij.run(s);
   135   ...
   136 \endcode
   137 
   138 
   139 \subsection write-maps Writable Maps
   140 
   141 To be written...
   142 
   143 \subsection side-effect-maps Maps with Side Effect
   144 
   145 To be written...
   146 
   147 */
   148 }