doc/maps.dox
changeset 1131 425731cb66de
parent 1043 52a2201a88e9
child 1167 ccbca6ba8b59
equal deleted inserted replaced
14:411e39a20cd3 15:e8ab703836eb
       
     1 namespace lemon{
     1 /*!
     2 /*!
     2 
       
     3 
       
     4 
     3 
     5 \page maps-page Maps
     4 \page maps-page Maps
     6 
     5 
     7 Maps play central role in LEMON. As their name suggests, they map a
     6 Maps play central role in LEMON. As their name suggests, they map a
     8 certain range of \e keys to certain \e values. Each map has two
     7 certain range of \e keys to certain \e values. Each map has two
    11 \code
    10 \code
    12   typedef Edge Key;
    11   typedef Edge Key;
    13   typedef double Value;
    12   typedef double Value;
    14 \endcode
    13 \endcode
    15 
    14 
    16 A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both
    15 A map can \e readable (\ref lemon::concept::ReadMap "ReadMap", for short),
    17 (ReadWrite Map). There also exists a special type of
    16 \e writable (\ref lemon::concept::WriteMap "WriteMap") or both
    18 ReadWrite map called <em>reference map</em>. In addition that you can
    17 (\ref lemon::concept::ReadWriteMap "ReadWriteMap").
       
    18 There also exists a special type of
       
    19 ReadWrite map called \ref lemon::concept::ReferenceMap "reference map".
       
    20 In addition that you can
    19 read and write the values of a key, a reference map
    21 read and write the values of a key, a reference map
    20 can also give you a reference to the
    22 can also give you a reference to the
    21 value belonging to a key, so you have a direct access to the memory address
    23 value belonging to a key, so you have a direct access to the memory address
    22 where it is stored.
    24 where it is stored.
    23 
    25 
    26 assign data to the nodes and to the edges of the graph. For example if you
    28 assign data to the nodes and to the edges of the graph. For example if you
    27 have a graph \c G defined as
    29 have a graph \c G defined as
    28 \code
    30 \code
    29   ListGraph G;
    31   ListGraph G;
    30 \endcode
    32 \endcode
    31 and you want to assign floating point value to each edge, you can do
    33 and you want to assign a floating point value to each edge, you can do
    32 it like this.
    34 it like this.
    33 \code
    35 \code
    34   ListGraph::EdgeMap<double> length(G);
    36   ListGraph::EdgeMap<double> length(G);
    35 \endcode
    37 \endcode
       
    38 Note that you must give the underlying graph to the constructor.
    36 
    39 
    37 The value of a readable map can be obtained by <tt>operator[]</tt>.
    40 The value of a readable map can be obtained by <tt>operator[]</tt>.
    38 \code
    41 \code
    39   d=length[e];
    42   d=length[e];
    40 \endcode
    43 \endcode
    41 where \c e is an instance of \c ListGraph::Edge.
    44 where \c e is an instance of \c ListGraph::Edge.
    42 (Or anything else
    45 (Or anything else
    43 that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
    46 that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
    44 \c ListGraph::OutEdgeIt)
    47 \c ListGraph::OutEdgeIt etc.)
    45 
    48 
    46 There are two ways the assign a new value to a key
    49 There are two ways the assign a new value to a key
    47 
    50 
    48 - In case of a <em>reference map</em> <tt>operator[]</tt>
    51 - In case of a <em>reference map</em> <tt>operator[]</tt>
    49 gives you a reference to the
    52 gives you a reference to the
    58   length.set(e,3.5);
    61   length.set(e,3.5);
    59 \endcode
    62 \endcode
    60 
    63 
    61 The first case is more comfortable and if you store complex structures in your
    64 The first case is more comfortable and if you store complex structures in your
    62 map, it might be more efficient. However, there are writable but
    65 map, it might be more efficient. However, there are writable but
    63 not reference maps, so if you want to write an generic algorithm, you should
    66 not reference maps, so if you want to write a generic algorithm, you should
    64 insist on the second method.
    67 insist on the second way.
    65 
    68 
    66 \section how-to-write-your-own-map How to Write Your Own Maps
    69 \section how-to-write-your-own-map How to Write Your Own Maps
    67 
    70 
    68 \subsection read-maps Readable Maps
    71 \subsection read-maps Readable Maps
    69 
    72 
    70 The readable maps are very frequently used as the input of the
    73 Readable maps are very frequently used as the input of the
    71 algorithms.  For this purpose the most straightforward way is the use of the
    74 algorithms.  For this purpose the most straightforward way is the use of the
    72 default maps provided by LEMON's graph structures.
    75 default maps provided by LEMON's graph structures.
    73 Very often however, it is more
    76 Very often however, it is more
    74 convenient and/or more efficient to write your own readable map.
    77 convenient and/or more efficient to write your own readable map.
    75 
    78 
    98   Value operator[](Key e) const { return M_PI;}
   101   Value operator[](Key e) const { return M_PI;}
    99 };
   102 };
   100 \endcode
   103 \endcode
   101 
   104 
   102 Here is a bit more complex example.
   105 Here is a bit more complex example.
   103 It provides a length function which is obtained
   106 It provides a length function obtained
   104 from a base length function shifted by a potential difference.
   107 from a base length function shifted by a potential difference.
   105 
   108 
   106 \code
   109 \code
   107 class MyLengthMap  : public MapBase<Graph::Edge,double>
   110 class ReducedLengthMap  : public MapBase<Graph::Edge,double>
   108 {
   111 {
   109   const Graph &G;
   112   const Graph &g;
   110   const Graph::EdgeMap<double> &orig_len;
   113   const Graph::EdgeMap<double> &orig_len;
   111   const Graph::NodeMap<double> &pot;
   114   const Graph::NodeMap<double> &pot;
   112   
   115   
   113 public:
   116 public:
   114   Value operator[](Key e) const {
   117   Value operator[](Key e) const {
   115     return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e));
   118     return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e));
   116   }
   119   }
   117   
   120   
   118   MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p)
   121   ReducedLengthMap(const Graph &_g,
       
   122                    const Graph::EdgeMap &o,
       
   123                    const Graph::NodeMap &p)
   119     : G(g), orig_len(o), pot(p) {};
   124     : G(g), orig_len(o), pot(p) {};
   120 };
   125 };
       
   126 \endcode
       
   127 
       
   128 Then, you can call e.g. Dijkstra algoritm on this map like this:
       
   129 \code
       
   130   ...
       
   131   ReducedLengthMap rm(g,len,pot);
       
   132   Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
       
   133   dij.run(s);
       
   134   ...
   121 \endcode
   135 \endcode
   122 
   136 
   123 
   137 
   124 \subsection write-maps Writable Maps
   138 \subsection write-maps Writable Maps
   125 
   139 
   128 \subsection side-effect-maps Maps with Side Effect
   142 \subsection side-effect-maps Maps with Side Effect
   129 
   143 
   130 To be written...
   144 To be written...
   131 
   145 
   132 */
   146 */
       
   147 }