doc/maps2.dox
author deba
Fri, 03 Nov 2006 16:29:32 +0000
changeset 2293 1ee6e8788cc7
child 2391 14a343be7a5a
permissions -rw-r--r--
First implementation of the static graph class
It could be improved to get better running times on benchmarks
alpar@2196
     1
/**
alpar@2196
     2
\page maps2 Maps II.
alpar@2196
     3
alpar@2196
     4
Here we discuss some advanced map techniques. Like writing your own maps or how to
alpar@2196
     5
extend/modify a maps functionality with adaptors.
alpar@2196
     6
alpar@2196
     7
\section custom_maps Writing Custom ReadMap
alpar@2196
     8
\subsection custom_read_maps Readable Maps
alpar@2196
     9
alpar@2196
    10
Readable maps are very frequently used as the input of an
alpar@2196
    11
algorithm.  For this purpose the most straightforward way is the use of the
alpar@2196
    12
default maps provided by LEMON's graph structures.
alpar@2196
    13
Very often however, it is more
alpar@2196
    14
convenient and/or more efficient to write your own readable map.
alpar@2196
    15
alpar@2196
    16
You can find some examples below. In these examples \c Graph is the
alpar@2196
    17
type of the particular graph structure you use.
alpar@2196
    18
alpar@2196
    19
alpar@2196
    20
This simple map assigns \f$\pi\f$ to each edge.
alpar@2196
    21
alpar@2196
    22
\code
alpar@2196
    23
struct MyMap 
alpar@2196
    24
{
alpar@2196
    25
  typedef double Value;
alpar@2196
    26
  typedef Graph::Edge Key;
alpar@2196
    27
  double operator[](Key e) const { return M_PI;}
alpar@2196
    28
};
alpar@2196
    29
\endcode
alpar@2196
    30
alpar@2196
    31
An alternative way to define maps is to use MapBase
alpar@2196
    32
alpar@2196
    33
\code
alpar@2196
    34
struct MyMap : public MapBase<Graph::Edge,double>
alpar@2196
    35
{
alpar@2196
    36
  Value operator[](Key e) const { return M_PI;}
alpar@2196
    37
};
alpar@2196
    38
\endcode
alpar@2196
    39
alpar@2196
    40
Here is a bit more complex example.
alpar@2196
    41
It provides a length function obtained
alpar@2196
    42
from a base length function shifted by a potential difference.
alpar@2196
    43
alpar@2196
    44
\code
alpar@2196
    45
class ReducedLengthMap  : public MapBase<Graph::Edge,double>
alpar@2196
    46
{
alpar@2196
    47
  const Graph &g;
alpar@2196
    48
  const Graph::EdgeMap<double> &orig_len;
alpar@2196
    49
  const Graph::NodeMap<double> &pot;
alpar@2196
    50
  
alpar@2196
    51
public:
alpar@2196
    52
  Value operator[](Key e) const {
alpar@2196
    53
    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
alpar@2196
    54
  }
alpar@2196
    55
  
alpar@2196
    56
  ReducedLengthMap(const Graph &_g,
alpar@2196
    57
                   const Graph::EdgeMap &_o,
alpar@2196
    58
                   const Graph::NodeMap &_p)
alpar@2196
    59
    : g(_g), orig_len(_o), pot(_p) {};
alpar@2196
    60
};
alpar@2196
    61
\endcode
alpar@2196
    62
alpar@2196
    63
Then, you can call e.g. Dijkstra algoritm on this map like this:
alpar@2196
    64
\code
alpar@2196
    65
  ...
alpar@2196
    66
  ReducedLengthMap rm(g,len,pot);
alpar@2196
    67
  Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
alpar@2196
    68
  dij.run(s);
alpar@2196
    69
  ...
alpar@2196
    70
\endcode
alpar@2196
    71
alpar@2196
    72
*/