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@2196: /** alpar@2196: \page maps2 Maps II. alpar@2196: alpar@2196: Here we discuss some advanced map techniques. Like writing your own maps or how to alpar@2196: extend/modify a maps functionality with adaptors. alpar@2196: alpar@2196: \section custom_maps Writing Custom ReadMap alpar@2196: \subsection custom_read_maps Readable Maps alpar@2196: alpar@2196: Readable maps are very frequently used as the input of an alpar@2196: algorithm. For this purpose the most straightforward way is the use of the alpar@2196: default maps provided by LEMON's graph structures. alpar@2196: Very often however, it is more alpar@2196: convenient and/or more efficient to write your own readable map. alpar@2196: alpar@2196: You can find some examples below. In these examples \c Graph is the alpar@2196: type of the particular graph structure you use. alpar@2196: alpar@2196: alpar@2196: This simple map assigns \f$\pi\f$ to each edge. alpar@2196: alpar@2196: \code alpar@2196: struct MyMap alpar@2196: { alpar@2196: typedef double Value; alpar@2196: typedef Graph::Edge Key; alpar@2568: double operator[](const Key &e) const { return PI;} alpar@2196: }; alpar@2196: \endcode alpar@2196: alpar@2196: An alternative way to define maps is to use MapBase alpar@2196: alpar@2196: \code alpar@2196: struct MyMap : public MapBase alpar@2196: { alpar@2568: Value operator[](const Key& e) const { return PI;} alpar@2196: }; alpar@2196: \endcode alpar@2196: alpar@2196: Here is a bit more complex example. alpar@2196: It provides a length function obtained alpar@2196: from a base length function shifted by a potential difference. alpar@2196: alpar@2196: \code alpar@2196: class ReducedLengthMap : public MapBase alpar@2196: { alpar@2196: const Graph &g; alpar@2196: const Graph::EdgeMap &orig_len; alpar@2196: const Graph::NodeMap &pot; alpar@2196: alpar@2196: public: alpar@2196: Value operator[](Key e) const { alpar@2196: return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]); alpar@2196: } alpar@2196: alpar@2196: ReducedLengthMap(const Graph &_g, alpar@2196: const Graph::EdgeMap &_o, alpar@2196: const Graph::NodeMap &_p) alpar@2196: : g(_g), orig_len(_o), pot(_p) {}; alpar@2196: }; alpar@2196: \endcode alpar@2196: alpar@2196: Then, you can call e.g. Dijkstra algoritm on this map like this: alpar@2196: \code alpar@2196: ... alpar@2196: ReducedLengthMap rm(g,len,pot); alpar@2196: Dijkstra dij(g,rm); alpar@2196: dij.run(s); alpar@2196: ... alpar@2196: \endcode alpar@2196: alpar@2196: */