alpar@202: /*! alpar@202: alpar@202: alpar@692: alpar@1043: \page maps-page Maps alpar@692: alpar@921: Maps play central role in LEMON. As their name suggests, they map a alpar@692: certain range of \e keys to certain \e values. Each map has two alpar@692: typedef's to determine the types of keys and values, like this: alpar@692: alpar@692: \code alpar@987: typedef Edge Key; alpar@987: typedef double Value; alpar@692: \endcode alpar@692: alpar@692: A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both alpar@692: (ReadWrite Map). There also exists a special type of alpar@692: ReadWrite map called reference map. In addition that you can alpar@692: read and write the values of a key, a reference map alpar@692: can also give you a reference to the alpar@692: value belonging to a key, so you have a direct access to the memory address alpar@692: where it is stored. alpar@692: alpar@921: Each graph structure in LEMON provides two standard map templates called alpar@692: \c EdgeMap and \c NodeMap. Both are reference maps and you can easily alpar@692: assign data to the nodes and to the edges of the graph. For example if you alpar@692: have a graph \c G defined as alpar@692: \code alpar@692: ListGraph G; alpar@692: \endcode alpar@692: and you want to assign floating point value to each edge, you can do alpar@692: it like this. alpar@692: \code alpar@692: ListGraph::EdgeMap length(G); alpar@692: \endcode alpar@692: alpar@692: The value of a readable map can be obtained by operator[]. alpar@692: \code alpar@692: d=length[e]; alpar@692: \endcode alpar@692: where \c e is an instance of \c ListGraph::Edge. alpar@692: (Or anything else alpar@692: that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or alpar@692: \c ListGraph::OutEdgeIt) alpar@692: alpar@692: There are two ways the assign a new value to a key alpar@692: alpar@692: - In case of a reference map operator[] alpar@692: gives you a reference to the alpar@692: value, thus you can use this. alpar@692: \code alpar@692: length[e]=3.5; alpar@692: \endcode alpar@692: - Writable maps have alpar@987: a member function \c set(Key,const Value &) alpar@692: for this purpose. alpar@692: \code alpar@692: length.set(e,3.5); alpar@692: \endcode alpar@692: alpar@692: The first case is more comfortable and if you store complex structures in your alpar@692: map, it might be more efficient. However, there are writable but alpar@692: not reference maps, so if you want to write an generic algorithm, you should alpar@692: insist on the second method. alpar@692: alpar@697: \section how-to-write-your-own-map How to Write Your Own Maps alpar@692: alpar@692: \subsection read-maps Readable Maps alpar@202: alpar@289: The readable maps are very frequently used as the input of the alpar@692: algorithms. For this purpose the most straightforward way is the use of the alpar@921: default maps provided by LEMON's graph structures. alpar@692: Very often however, it is more alpar@289: convenient and/or more efficient to write your own readable map. alpar@202: alpar@692: You can find some examples below. In these examples \c Graph is the alpar@692: type of the particular graph structure you use. alpar@692: alpar@202: alpar@204: This simple map assigns \f$\pi\f$ to each edge. alpar@204: alpar@202: \code alpar@273: struct MyMap alpar@202: { alpar@987: typedef double Value; alpar@987: typedef Graph::Edge Key; alpar@987: double operator[](Key e) const { return M_PI;} alpar@204: }; alpar@204: \endcode alpar@204: alpar@692: An alternative way to define maps is to use \c MapBase alpar@692: alpar@692: \todo For this, \c MapBase seems to be a better name then \c NullMap. alpar@289: alpar@289: \code alpar@692: struct MyMap : public MapBase alpar@289: { alpar@987: Value operator[](Key e) const { return M_PI;} alpar@289: }; alpar@289: \endcode alpar@289: alpar@692: Here is a bit more complex example. alpar@692: It provides a length function which is obtained alpar@692: from a base length function shifted by a potential difference. alpar@202: alpar@202: \code alpar@692: class MyLengthMap : public MapBase alpar@202: { alpar@692: const Graph &G; alpar@692: const Graph::EdgeMap &orig_len; alpar@692: const Graph::NodeMap &pot; alpar@202: alpar@273: public: alpar@987: Value operator[](Key e) const { alpar@986: return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e)); alpar@210: } alpar@202: alpar@692: MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p) alpar@692: : G(g), orig_len(o), pot(p) {}; alpar@202: }; alpar@202: \endcode alpar@202: alpar@692: alpar@692: \subsection write-maps Writable Maps alpar@692: alpar@692: To be written... alpar@692: alpar@692: \subsection side-effect-maps Maps with Side Effect alpar@692: alpar@692: To be written... alpar@692: alpar@202: */