Changeset 692:098bc98f7530 in lemon-0.x for doc

Timestamp:

07/06/04 11:34:25 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@942

Message:

Extended tutorial.

File:

• doc/maps.dox (modified) (3 diffs)

doc/maps.dox

@@ -1 +1 @@
 /*!
 
-\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
+<tt>typedef</tt>'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 <em>reference map</em>. 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<double> length(G);
+\endcode
+
+The value of a readable map can be obtained by <tt>operator[]</tt>.
+\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 <em>reference map</em> <tt>operator[]</tt>
+gives you a reference to the
+value, thus you can use this.
+\code
+  length[e]=3.5;
+\endcode
+- <em>Writable maps</em> 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.
@@ -18 +84 @@
 {
   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<Edge,double>
-{
-  double operator[](Graph::Edge e) const { return M_PI;}
-};
-\endcode
-
-Or, if we had \c KeyType and \c ValueType
-
-\code
-struct MyMap : public MapBase<Edge,double>
+struct MyMap : public MapBase<Graph::Edge,double>
 {
   ValueType operator[](KeyType e) const { return M_PI;}
@@ -41 +100 @@
 \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<Graph::Edge,double>
 {
-  const Graph::EdgeMap &ol;
-  const Graph::NodeMap &pot;
+  const Graph &G;
+  const Graph::EdgeMap<double> &orig_len;
+  const Graph::NodeMap<double> &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...
+
 */