doc/maps.dox
author alpar
Thu, 03 Apr 2008 12:06:48 +0000
changeset 2599 b9905565d185
parent 2553 bfced05fa852
permissions -rw-r--r--
Serious bugfix in Random::gamma()
Backport from hg b6bede534255
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 namespace lemon{
    20 /*!
    21 
    22 \page maps-page Maps
    23 
    24 Maps play a central role in LEMON. As their name suggests, they map a
    25 certain range of \e keys to certain \e values. Each map has two
    26 <tt>typedef</tt>'s to determine the types of keys and values, like this:
    27 
    28 \code
    29   typedef Edge Key;
    30   typedef double Value;
    31 \endcode
    32 
    33 A map can be 
    34 \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
    35 \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
    36 (\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
    37 There also exists a special type of
    38 ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
    39 In addition that you can
    40 read and write the values of a key, a reference map
    41 can also give you a reference to the
    42 value belonging to a key, so you have a direct access to the memory address
    43 where it is stored.
    44 
    45 Each graph structure in LEMON provides two standard map templates called
    46 \c EdgeMap and \c NodeMap. Both are reference maps and you can easily
    47 assign data to the nodes and to the edges of the graph. For example if you
    48 have a graph \c g defined as
    49 \code
    50   ListGraph g;
    51 \endcode
    52 and you want to assign a floating point value to each edge, you can do
    53 it like this.
    54 \code
    55   ListGraph::EdgeMap<double> length(g);
    56 \endcode
    57 Note that you must give the underlying graph to the constructor.
    58 
    59 The value of a readable map can be obtained by <tt>operator[]</tt>.
    60 \code
    61   d=length[e];
    62 \endcode
    63 where \c e is an instance of \c ListGraph::Edge.
    64 (Or anything else
    65 that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
    66 \c ListGraph::OutEdgeIt etc.)
    67 
    68 There are two ways to assign a new value to a key
    69 
    70 - In case of a <em>reference map</em> <tt>operator[]</tt>
    71 gives you a reference to the
    72 value, thus you can use this.
    73 \code
    74   length[e]=3.5;
    75 \endcode
    76 - <em>Writable maps</em> have
    77 a member function \c set(Key,const Value &)
    78 for this purpose.
    79 \code
    80   length.set(e,3.5);
    81 \endcode
    82 
    83 The first case is more comfortable and if you store complex structures in your
    84 map, it might be more efficient. However, there are writable but
    85 not reference maps, so if you want to write a generic algorithm, you should
    86 insist on the second way.
    87 
    88 \section how-to-write-your-own-map How to Write Your Own Maps
    89 
    90 \subsection read-maps Readable Maps
    91 
    92 Readable maps are very frequently used as the input of an
    93 algorithm.  For this purpose the most straightforward way is the use of the
    94 default maps provided by LEMON's graph structures.
    95 Very often however, it is more
    96 convenient and/or more efficient to write your own readable map.
    97 
    98 You can find some examples below. In these examples \c Graph is the
    99 type of the particular graph structure you use.
   100 
   101 
   102 This simple map assigns \f$\pi\f$ to each edge.
   103 
   104 \code
   105 struct MyMap 
   106 {
   107   typedef double Value;
   108   typedef Graph::Edge Key;
   109   double operator[](Key e) const { return PI;}
   110 };
   111 \endcode
   112 
   113 An alternative way to define maps is to use \c MapBase
   114 
   115 \code
   116 struct MyMap : public MapBase<Graph::Edge,double>
   117 {
   118   Value operator[](Key e) const { return PI;}
   119 };
   120 \endcode
   121 
   122 Here is a bit more complex example.
   123 It provides a length function obtained
   124 from a base length function shifted by a potential difference.
   125 
   126 \code
   127 class ReducedLengthMap  : public MapBase<Graph::Edge,double>
   128 {
   129   const Graph &g;
   130   const Graph::EdgeMap<double> &orig_len;
   131   const Graph::NodeMap<double> &pot;
   132   
   133 public:
   134   Value operator[](Key e) const {
   135     return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
   136   }
   137   
   138   ReducedLengthMap(const Graph &_g,
   139                    const Graph::EdgeMap &_o,
   140                    const Graph::NodeMap &_p)
   141     : g(_g), orig_len(_o), pot(_p) {};
   142 };
   143 \endcode
   144 
   145 Then, you can call e.g. Dijkstra algoritm on this map like this:
   146 \code
   147   ...
   148   ReducedLengthMap rm(g,len,pot);
   149   Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
   150   dij.run(s);
   151   ...
   152 \endcode
   153 
   154 
   155 \subsection write-maps Writable Maps
   156 
   157 To be written...
   158 
   159 \subsection side-effect-maps Maps with Side Effect
   160 
   161 To be written...
   162 
   163 */
   164 }