alpar@2391: /* -*- C++ -*- alpar@2391: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2553: * Copyright (C) 2003-2008 alpar@2391: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2391: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2391: * alpar@2391: * Permission to use, modify and distribute this software is granted alpar@2391: * provided that this copyright notice appears in all copies. For alpar@2391: * precise terms see the accompanying LICENSE file. alpar@2391: * alpar@2391: * This software is provided "AS IS" with no warranty of any kind, alpar@2391: * express or implied, and with no claim as to its suitability for any alpar@2391: * purpose. alpar@2391: * alpar@2391: */ alpar@2391: 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: athos@1183: A map can be alpar@2260: \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short), alpar@2260: \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both alpar@2260: (\ref lemon::concepts::ReadWriteMap "ReadWriteMap"). alpar@1083: There also exists a special type of alpar@2260: ReadWrite map called \ref lemon::concepts::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 deba@1788: have a graph \c g defined as alpar@692: \code deba@1788: 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 deba@1788: 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@2568: double operator[](Key e) const { return PI;} alpar@204: }; alpar@204: \endcode alpar@204: alpar@692: An alternative way to define maps is to use \c MapBase alpar@692: alpar@289: \code alpar@692: struct MyMap : public MapBase alpar@289: { alpar@2568: Value operator[](Key e) const { return 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 { deba@1788: return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]); alpar@210: } alpar@202: alpar@1083: ReducedLengthMap(const Graph &_g, deba@1788: const Graph::EdgeMap &_o, deba@1788: const Graph::NodeMap &_p) deba@1788: : 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: */ athos@1183: }