# Changeset 692:098bc98f7530 in lemon-0.x for doc/maps.dox

Ignore:
Timestamp:
07/06/04 11:34:25 (19 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@942
Message:

Extended tutorial.

File:
1 edited

### Legend:

Unmodified
 r685 /*! \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. { 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... */