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 */