doc/maps.dox
author deba
Tue, 31 Oct 2006 14:27:58 +0000
changeset 2282 9d7b12f83daa
parent 1788 614ce2dd3cba
child 2391 14a343be7a5a
permissions -rw-r--r--
Bug fixes
     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::concepts::ReadMap "ReadMap", for short),
    17 \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
    18 (\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
    19 There also exists a special type of
    20 ReadWrite map called \ref lemon::concepts::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 \code
    98 struct MyMap : public MapBase<Graph::Edge,double>
    99 {
   100   Value operator[](Key e) const { return M_PI;}
   101 };
   102 \endcode
   103 
   104 Here is a bit more complex example.
   105 It provides a length function obtained
   106 from a base length function shifted by a potential difference.
   107 
   108 \code
   109 class ReducedLengthMap  : public MapBase<Graph::Edge,double>
   110 {
   111   const Graph &g;
   112   const Graph::EdgeMap<double> &orig_len;
   113   const Graph::NodeMap<double> &pot;
   114   
   115 public:
   116   Value operator[](Key e) const {
   117     return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
   118   }
   119   
   120   ReducedLengthMap(const Graph &_g,
   121                    const Graph::EdgeMap &_o,
   122                    const Graph::NodeMap &_p)
   123     : g(_g), orig_len(_o), pot(_p) {};
   124 };
   125 \endcode
   126 
   127 Then, you can call e.g. Dijkstra algoritm on this map like this:
   128 \code
   129   ...
   130   ReducedLengthMap rm(g,len,pot);
   131   Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
   132   dij.run(s);
   133   ...
   134 \endcode
   135 
   136 
   137 \subsection write-maps Writable Maps
   138 
   139 To be written...
   140 
   141 \subsection side-effect-maps Maps with Side Effect
   142 
   143 To be written...
   144 
   145 */
   146 }