alpar@1083: namespace lemon{ alpar@202: /*! alpar@202: alpar@1043: \page maps-page Maps alpar@692: athos@1167: Maps play a 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@1083: A map can \e readable (\ref lemon::concept::ReadMap "ReadMap", for short), alpar@1083: \e writable (\ref lemon::concept::WriteMap "WriteMap") or both alpar@1083: (\ref lemon::concept::ReadWriteMap "ReadWriteMap"). alpar@1083: There also exists a special type of alpar@1083: ReadWrite map called \ref lemon::concept::ReferenceMap "reference map". alpar@1083: 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@1083: and you want to assign a 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@1083: Note that you must give the underlying graph to the constructor. 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@1083: \c ListGraph::OutEdgeIt etc.) alpar@692: athos@1167: There are two ways to 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@1083: not reference maps, so if you want to write a generic algorithm, you should alpar@1083: insist on the second way. 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: athos@1167: Readable maps are very frequently used as the input of an athos@1167: algorithm. 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@1083: It provides a length function obtained alpar@692: from a base length function shifted by a potential difference. alpar@202: alpar@202: \code alpar@1083: class ReducedLengthMap : public MapBase alpar@202: { alpar@1083: 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 { athos@1167: return orig_len.get(e)-(pot.get(G.target(e))-pot.get(G.source(e))); alpar@210: } alpar@202: alpar@1083: ReducedLengthMap(const Graph &_g, alpar@1083: const Graph::EdgeMap &o, alpar@1083: const Graph::NodeMap &p) alpar@692: : G(g), orig_len(o), pot(p) {}; alpar@202: }; alpar@202: \endcode alpar@202: alpar@1083: Then, you can call e.g. Dijkstra algoritm on this map like this: alpar@1083: \code alpar@1083: ... alpar@1083: ReducedLengthMap rm(g,len,pot); alpar@1083: Dijkstra dij(g,rm); alpar@1083: dij.run(s); alpar@1083: ... alpar@1083: \endcode alpar@1083: 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: */ alpar@1083: }