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