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<Graph::Edge,double>
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<Graph::Edge,double>
alpar@2196: {
alpar@2196:   const Graph &g;
alpar@2196:   const Graph::EdgeMap<double> &orig_len;
alpar@2196:   const Graph::NodeMap<double> &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<Graph,ReducedLengthMap> dij(g,rm);
alpar@2196:   dij.run(s);
alpar@2196:   ...
alpar@2196: \endcode
alpar@2196: 
alpar@2196: */