doc/maps.dox
author marci
Mon, 20 Sep 2004 16:20:11 +0000
changeset 889 47bb9b8f5705
parent 692 098bc98f7530
child 921 818510fa3d99
permissions -rw-r--r--
EXAMPLE_PATH is set to the demo dir.
     1 /*!
     2 
     3 
     4 
     5 \page maps Maps
     6 
     7 Maps play central role in HUGOlib. As their name suggests, they map a
     8 certain range of \e keys to certain \e values. Each map has two
     9 <tt>typedef</tt>'s to determine the types of keys and values, like this:
    10 
    11 \code
    12   typedef Edge KeyType;
    13   typedef double ValueType;
    14 \endcode
    15 
    16 A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both
    17 (ReadWrite Map). There also exists a special type of
    18 ReadWrite map called <em>reference map</em>. In addition that you can
    19 read and write the values of a key, a reference map
    20 can also give you a reference to the
    21 value belonging to a key, so you have a direct access to the memory address
    22 where it is stored.
    23 
    24 Each graph structure in HUGOlib provides two standard map templates called
    25 \c EdgeMap and \c NodeMap. Both are reference maps and you can easily
    26 assign data to the nodes and to the edges of the graph. For example if you
    27 have a graph \c G defined as
    28 \code
    29   ListGraph G;
    30 \endcode
    31 and you want to assign floating point value to each edge, you can do
    32 it like this.
    33 \code
    34   ListGraph::EdgeMap<double> length(G);
    35 \endcode
    36 
    37 The value of a readable map can be obtained by <tt>operator[]</tt>.
    38 \code
    39   d=length[e];
    40 \endcode
    41 where \c e is an instance of \c ListGraph::Edge.
    42 (Or anything else
    43 that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
    44 \c ListGraph::OutEdgeIt)
    45 
    46 There are two ways the assign a new value to a key
    47 
    48 - In case of a <em>reference map</em> <tt>operator[]</tt>
    49 gives you a reference to the
    50 value, thus you can use this.
    51 \code
    52   length[e]=3.5;
    53 \endcode
    54 - <em>Writable maps</em> have
    55 a member function \c set(KeyType,const ValueType &)
    56 for this purpose.
    57 \code
    58   length.set(e,3.5);
    59 \endcode
    60 
    61 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
    63 not reference maps, so if you want to write an generic algorithm, you should
    64 insist on the second method.
    65 
    66 \section how-to-write-your-own-map How to Write Your Own Maps
    67 
    68 \subsection read-maps Readable Maps
    69 
    70 The 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
    72 default maps provided by Hugo's graph structures.
    73 Very often however, it is more
    74 convenient and/or more efficient to write your own readable map.
    75 
    76 You can find some examples below. In these examples \c Graph is the
    77 type of the particular graph structure you use.
    78 
    79 
    80 This simple map assigns \f$\pi\f$ to each edge.
    81 
    82 \code
    83 struct MyMap 
    84 {
    85   typedef double ValueType;
    86   typedef Graph::Edge KeyType;
    87   double operator[](KeyType e) const { return M_PI;}
    88 };
    89 \endcode
    90 
    91 An alternative way to define maps is to use \c MapBase
    92 
    93 \todo For this, \c MapBase seems to be a better name then \c NullMap.
    94 
    95 \code
    96 struct MyMap : public MapBase<Graph::Edge,double>
    97 {
    98   ValueType operator[](KeyType e) const { return M_PI;}
    99 };
   100 \endcode
   101 
   102 Here is a bit more complex example.
   103 It provides a length function which is obtained
   104 from a base length function shifted by a potential difference.
   105 
   106 \code
   107 class MyLengthMap  : public MapBase<Graph::Edge,double>
   108 {
   109   const Graph &G;
   110   const Graph::EdgeMap<double> &orig_len;
   111   const Graph::NodeMap<double> &pot;
   112   
   113 public:
   114   KeyType operator[](ValueType e) const {
   115     return orig_len.get(e)-pot.get(G.head(e))-pot.get(G.tail(e));
   116   }
   117   
   118   MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p)
   119     : G(g), orig_len(o), pot(p) {};
   120 };
   121 \endcode
   122 
   123 
   124 \subsection write-maps Writable Maps
   125 
   126 To be written...
   127 
   128 \subsection side-effect-maps Maps with Side Effect
   129 
   130 To be written...
   131 
   132 */