doc/maps2.dox
author deba
Tue, 06 Mar 2007 17:03:37 +0000
changeset 2394 8b9b44a9c754
parent 2196 09af6d2b683b
child 2408 467ca6d16556
permissions -rw-r--r--
Bug fix missing include
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 /**
    20 \page maps2 Maps II.
    21 
    22 Here we discuss some advanced map techniques. Like writing your own maps or how to
    23 extend/modify a maps functionality with adaptors.
    24 
    25 \section custom_maps Writing Custom ReadMap
    26 \subsection custom_read_maps Readable Maps
    27 
    28 Readable maps are very frequently used as the input of an
    29 algorithm.  For this purpose the most straightforward way is the use of the
    30 default maps provided by LEMON's graph structures.
    31 Very often however, it is more
    32 convenient and/or more efficient to write your own readable map.
    33 
    34 You can find some examples below. In these examples \c Graph is the
    35 type of the particular graph structure you use.
    36 
    37 
    38 This simple map assigns \f$\pi\f$ to each edge.
    39 
    40 \code
    41 struct MyMap 
    42 {
    43   typedef double Value;
    44   typedef Graph::Edge Key;
    45   double operator[](Key e) const { return M_PI;}
    46 };
    47 \endcode
    48 
    49 An alternative way to define maps is to use MapBase
    50 
    51 \code
    52 struct MyMap : public MapBase<Graph::Edge,double>
    53 {
    54   Value operator[](Key e) const { return M_PI;}
    55 };
    56 \endcode
    57 
    58 Here is a bit more complex example.
    59 It provides a length function obtained
    60 from a base length function shifted by a potential difference.
    61 
    62 \code
    63 class ReducedLengthMap  : public MapBase<Graph::Edge,double>
    64 {
    65   const Graph &g;
    66   const Graph::EdgeMap<double> &orig_len;
    67   const Graph::NodeMap<double> &pot;
    68   
    69 public:
    70   Value operator[](Key e) const {
    71     return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
    72   }
    73   
    74   ReducedLengthMap(const Graph &_g,
    75                    const Graph::EdgeMap &_o,
    76                    const Graph::NodeMap &_p)
    77     : g(_g), orig_len(_o), pot(_p) {};
    78 };
    79 \endcode
    80 
    81 Then, you can call e.g. Dijkstra algoritm on this map like this:
    82 \code
    83   ...
    84   ReducedLengthMap rm(g,len,pot);
    85   Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
    86   dij.run(s);
    87   ...
    88 \endcode
    89 
    90 */