# HG changeset patch
# User alpar
# Date 1089106465 0
# Node ID 098bc98f7530837d1b4aa16ecd1dc27eaebbd32d
# Parent 014c2e4eb07b895f6cdef6c48e277312d5ca0ac4
Extended tutorial.
diff -r 014c2e4eb07b -r 098bc98f7530 doc/maps.dox
--- a/doc/maps.dox Mon Jul 05 16:44:18 2004 +0000
+++ b/doc/maps.dox Tue Jul 06 09:34:25 2004 +0000
@@ -1,15 +1,81 @@
/*!
-\page maps How to write your own maps
-\section read-maps Readable Maps
+
+\page maps Maps
+
+Maps play central role in HUGOlib. As their name suggests, they map a
+certain range of \e keys to certain \e values. Each map has two
+typedef's to determine the types of keys and values, like this:
+
+\code
+ typedef Edge KeyType;
+ typedef double ValueType;
+\endcode
+
+A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both
+(ReadWrite Map). There also exists a special type of
+ReadWrite map called reference map. In addition that you can
+read and write the values of a key, a reference map
+can also give you a reference to the
+value belonging to a key, so you have a direct access to the memory address
+where it is stored.
+
+Each graph structure in HUGOlib provides two standard map templates called
+\c EdgeMap and \c NodeMap. Both are reference maps and you can easily
+assign data to the nodes and to the edges of the graph. For example if you
+have a graph \c G defined as
+\code
+ ListGraph G;
+\endcode
+and you want to assign floating point value to each edge, you can do
+it like this.
+\code
+ ListGraph::EdgeMap length(G);
+\endcode
+
+The value of a readable map can be obtained by operator[].
+\code
+ d=length[e];
+\endcode
+where \c e is an instance of \c ListGraph::Edge.
+(Or anything else
+that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or
+\c ListGraph::OutEdgeIt)
+
+There are two ways the assign a new value to a key
+
+- In case of a reference map operator[]
+gives you a reference to the
+value, thus you can use this.
+\code
+ length[e]=3.5;
+\endcode
+- Writable maps have
+a member function \c set(KeyType,const ValueType &)
+for this purpose.
+\code
+ length.set(e,3.5);
+\endcode
+
+The first case is more comfortable and if you store complex structures in your
+map, it might be more efficient. However, there are writable but
+not reference maps, so if you want to write an generic algorithm, you should
+insist on the second method.
+
+\section how-to-write-your-own-map How To write your own maps
+
+\subsection read-maps Readable Maps
The readable maps are very frequently used as the input of the
-algorithms. For this purpose the most straightforward is to use the
-maps provided by Hugo's graph structres. Very often however, it is more
+algorithms. For this purpose the most straightforward way is the use of the
+default maps provided by Hugo's graph structures.
+Very often however, it is more
convenient and/or more efficient to write your own readable map.
-You can find some examples below.
+You can find some examples below. In these examples \c Graph is the
+type of the particular graph structure you use.
+
This simple map assigns \f$\pi\f$ to each edge.
@@ -17,51 +83,50 @@
struct MyMap
{
typedef double ValueType;
- double operator[](Graph::Edge e) const { return M_PI;}
+ typedef Graph::Edge KeyType;
+ double operator[](KeyType e) const { return M_PI;}
};
\endcode
-An alternative way to define maps. For this, \c MapBase seems to
-be a better name then \c NullMap
+An alternative way to define maps is to use \c MapBase
+
+\todo For this, \c MapBase seems to be a better name then \c NullMap.
\code
-struct MyMap : public MapBase
-{
- double operator[](Graph::Edge e) const { return M_PI;}
-};
-\endcode
-
-Or, if we had \c KeyType and \c ValueType
-
-\code
-struct MyMap : public MapBase
+struct MyMap : public MapBase
{
ValueType operator[](KeyType e) const { return M_PI;}
};
\endcode
-
-Here is a more complex example. It provides a length function which is obtained
-from a base length function modified by a potential difference.
+Here is a bit more complex example.
+It provides a length function which is obtained
+from a base length function shifted by a potential difference.
\code
-class MyLengthMap
+class MyLengthMap : public MapBase
{
- const Graph::EdgeMap &ol;
- const Graph::NodeMap &pot;
+ const Graph &G;
+ const Graph::EdgeMap &orig_len;
+ const Graph::NodeMap &pot;
public:
- typedef double ValueType;
-
- double operator[](Graph::Edge e) const {
- return ol.get(e)-pot.get(v)-pot.get(u);
+ KeyType operator[](ValueType e) const {
+ return orig_len.get(e)-pot.get(G.head(e))-pot.get(G.tail(e));
}
- MyComplexMap(const Graph::EdgeMap &o,const Graph::NodeMap &p) :
- ol(o), pot(p);
+ MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p)
+ : G(g), orig_len(o), pot(p) {};
};
\endcode
-\todo Please improve on the english.
-\todo Don't we need \e to \e require a 'typedef xxx KeyType' tag, as well?
+
+\subsection write-maps Writable Maps
+
+To be written...
+
+\subsection side-effect-maps Maps with Side Effect
+
+To be written...
+
*/