Extended tutorial.
authoralpar
Tue, 06 Jul 2004 09:34:25 +0000
changeset 692098bc98f7530
parent 691 014c2e4eb07b
child 693 80164e89dcbc
Extended tutorial.
doc/maps.dox
     1.1 --- a/doc/maps.dox	Mon Jul 05 16:44:18 2004 +0000
     1.2 +++ b/doc/maps.dox	Tue Jul 06 09:34:25 2004 +0000
     1.3 @@ -1,15 +1,81 @@
     1.4  /*!
     1.5  
     1.6 -\page maps How to write your own maps
     1.7  
     1.8 -\section read-maps Readable Maps
     1.9 +
    1.10 +\page maps Maps
    1.11 +
    1.12 +Maps play central role in HUGOlib. As their name suggests, they map a
    1.13 +certain range of \e keys to certain \e values. Each map has two
    1.14 +<tt>typedef</tt>'s to determine the types of keys and values, like this:
    1.15 +
    1.16 +\code
    1.17 +  typedef Edge KeyType;
    1.18 +  typedef double ValueType;
    1.19 +\endcode
    1.20 +
    1.21 +A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both
    1.22 +(ReadWrite Map). There also exists a special type of
    1.23 +ReadWrite map called <em>reference map</em>. In addition that you can
    1.24 +read and write the values of a key, a reference map
    1.25 +can also give you a reference to the
    1.26 +value belonging to a key, so you have a direct access to the memory address
    1.27 +where it is stored.
    1.28 +
    1.29 +Each graph structure in HUGOlib provides two standard map templates called
    1.30 +\c EdgeMap and \c NodeMap. Both are reference maps and you can easily
    1.31 +assign data to the nodes and to the edges of the graph. For example if you
    1.32 +have a graph \c G defined as
    1.33 +\code
    1.34 +  ListGraph G;
    1.35 +\endcode
    1.36 +and you want to assign floating point value to each edge, you can do
    1.37 +it like this.
    1.38 +\code
    1.39 +  ListGraph::EdgeMap<double> length(G);
    1.40 +\endcode
    1.41 +
    1.42 +The value of a readable map can be obtained by <tt>operator[]</tt>.
    1.43 +\code
    1.44 +  d=length[e];
    1.45 +\endcode
    1.46 +where \c e is an instance of \c ListGraph::Edge.
    1.47 +(Or anything else
    1.48 +that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
    1.49 +\c ListGraph::OutEdgeIt)
    1.50 +
    1.51 +There are two ways the assign a new value to a key
    1.52 +
    1.53 +- In case of a <em>reference map</em> <tt>operator[]</tt>
    1.54 +gives you a reference to the
    1.55 +value, thus you can use this.
    1.56 +\code
    1.57 +  length[e]=3.5;
    1.58 +\endcode
    1.59 +- <em>Writable maps</em> have
    1.60 +a member function \c set(KeyType,const ValueType &)
    1.61 +for this purpose.
    1.62 +\code
    1.63 +  length.set(e,3.5);
    1.64 +\endcode
    1.65 +
    1.66 +The first case is more comfortable and if you store complex structures in your
    1.67 +map, it might be more efficient. However, there are writable but
    1.68 +not reference maps, so if you want to write an generic algorithm, you should
    1.69 +insist on the second method.
    1.70 +
    1.71 +\section how-to-write-your-own-map How To write your own maps
    1.72 +
    1.73 +\subsection read-maps Readable Maps
    1.74  
    1.75  The readable maps are very frequently used as the input of the
    1.76 -algorithms.  For this purpose the most straightforward is to use the
    1.77 -maps provided by Hugo's graph structres. Very often however, it is more
    1.78 +algorithms.  For this purpose the most straightforward way is the use of the
    1.79 +default maps provided by Hugo's graph structures.
    1.80 +Very often however, it is more
    1.81  convenient and/or more efficient to write your own readable map.
    1.82  
    1.83 -You can find some examples below.
    1.84 +You can find some examples below. In these examples \c Graph is the
    1.85 +type of the particular graph structure you use.
    1.86 +
    1.87  
    1.88  This simple map assigns \f$\pi\f$ to each edge.
    1.89  
    1.90 @@ -17,51 +83,50 @@
    1.91  struct MyMap 
    1.92  {
    1.93    typedef double ValueType;
    1.94 -  double operator[](Graph::Edge e) const { return M_PI;}
    1.95 +  typedef Graph::Edge KeyType;
    1.96 +  double operator[](KeyType e) const { return M_PI;}
    1.97  };
    1.98  \endcode
    1.99  
   1.100 -An alternative way to define maps. For this, \c MapBase seems to
   1.101 -be a better name then \c NullMap
   1.102 +An alternative way to define maps is to use \c MapBase
   1.103 +
   1.104 +\todo For this, \c MapBase seems to be a better name then \c NullMap.
   1.105  
   1.106  \code
   1.107 -struct MyMap : public MapBase<Edge,double>
   1.108 -{
   1.109 -  double operator[](Graph::Edge e) const { return M_PI;}
   1.110 -};
   1.111 -\endcode
   1.112 -
   1.113 -Or, if we had \c KeyType and \c ValueType
   1.114 -
   1.115 -\code
   1.116 -struct MyMap : public MapBase<Edge,double>
   1.117 +struct MyMap : public MapBase<Graph::Edge,double>
   1.118  {
   1.119    ValueType operator[](KeyType e) const { return M_PI;}
   1.120  };
   1.121  \endcode
   1.122  
   1.123 -
   1.124 -Here is a more complex example. It provides a length function which is obtained
   1.125 -from a base length function modified by a potential difference.
   1.126 +Here is a bit more complex example.
   1.127 +It provides a length function which is obtained
   1.128 +from a base length function shifted by a potential difference.
   1.129  
   1.130  \code
   1.131 -class MyLengthMap 
   1.132 +class MyLengthMap  : public MapBase<Graph::Edge,double>
   1.133  {
   1.134 -  const Graph::EdgeMap &ol;
   1.135 -  const Graph::NodeMap &pot;
   1.136 +  const Graph &G;
   1.137 +  const Graph::EdgeMap<double> &orig_len;
   1.138 +  const Graph::NodeMap<double> &pot;
   1.139    
   1.140  public:
   1.141 -  typedef double ValueType;
   1.142 -
   1.143 -  double operator[](Graph::Edge e) const {
   1.144 -    return ol.get(e)-pot.get(v)-pot.get(u);
   1.145 +  KeyType operator[](ValueType e) const {
   1.146 +    return orig_len.get(e)-pot.get(G.head(e))-pot.get(G.tail(e));
   1.147    }
   1.148    
   1.149 -  MyComplexMap(const Graph::EdgeMap &o,const Graph::NodeMap &p) :
   1.150 -    ol(o), pot(p);
   1.151 +  MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p)
   1.152 +    : G(g), orig_len(o), pot(p) {};
   1.153  };
   1.154  \endcode
   1.155  
   1.156 -\todo Please improve on the english. 
   1.157 -\todo Don't we need \e to \e require a 'typedef xxx KeyType' tag, as well?
   1.158 +
   1.159 +\subsection write-maps Writable Maps
   1.160 +
   1.161 +To be written...
   1.162 +
   1.163 +\subsection side-effect-maps Maps with Side Effect
   1.164 +
   1.165 +To be written...
   1.166 +
   1.167  */