doc/maps.dox
author deba
Tue, 28 Aug 2007 14:00:42 +0000
changeset 2467 2025a571895e
parent 2260 4274224f8a7d
child 2553 bfced05fa852
permissions -rw-r--r--
PathNodeIt

PathWriter/Reader structures
Distinict MapSet readers and writers
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@2391
     5
 * Copyright (C) 2003-2007
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@1083
    19
namespace lemon{
alpar@202
    20
/*!
alpar@202
    21
alpar@1043
    22
\page maps-page Maps
alpar@692
    23
athos@1167
    24
Maps play a central role in LEMON. As their name suggests, they map a
alpar@692
    25
certain range of \e keys to certain \e values. Each map has two
alpar@692
    26
<tt>typedef</tt>'s to determine the types of keys and values, like this:
alpar@692
    27
alpar@692
    28
\code
alpar@987
    29
  typedef Edge Key;
alpar@987
    30
  typedef double Value;
alpar@692
    31
\endcode
alpar@692
    32
athos@1183
    33
A map can be 
alpar@2260
    34
\e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
alpar@2260
    35
\e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
alpar@2260
    36
(\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
alpar@1083
    37
There also exists a special type of
alpar@2260
    38
ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
alpar@1083
    39
In addition that you can
alpar@692
    40
read and write the values of a key, a reference map
alpar@692
    41
can also give you a reference to the
alpar@692
    42
value belonging to a key, so you have a direct access to the memory address
alpar@692
    43
where it is stored.
alpar@692
    44
alpar@921
    45
Each graph structure in LEMON provides two standard map templates called
alpar@692
    46
\c EdgeMap and \c NodeMap. Both are reference maps and you can easily
alpar@692
    47
assign data to the nodes and to the edges of the graph. For example if you
deba@1788
    48
have a graph \c g defined as
alpar@692
    49
\code
deba@1788
    50
  ListGraph g;
alpar@692
    51
\endcode
alpar@1083
    52
and you want to assign a floating point value to each edge, you can do
alpar@692
    53
it like this.
alpar@692
    54
\code
deba@1788
    55
  ListGraph::EdgeMap<double> length(g);
alpar@692
    56
\endcode
alpar@1083
    57
Note that you must give the underlying graph to the constructor.
alpar@692
    58
alpar@692
    59
The value of a readable map can be obtained by <tt>operator[]</tt>.
alpar@692
    60
\code
alpar@692
    61
  d=length[e];
alpar@692
    62
\endcode
alpar@692
    63
where \c e is an instance of \c ListGraph::Edge.
alpar@692
    64
(Or anything else
alpar@692
    65
that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
alpar@1083
    66
\c ListGraph::OutEdgeIt etc.)
alpar@692
    67
athos@1167
    68
There are two ways to assign a new value to a key
alpar@692
    69
alpar@692
    70
- In case of a <em>reference map</em> <tt>operator[]</tt>
alpar@692
    71
gives you a reference to the
alpar@692
    72
value, thus you can use this.
alpar@692
    73
\code
alpar@692
    74
  length[e]=3.5;
alpar@692
    75
\endcode
alpar@692
    76
- <em>Writable maps</em> have
alpar@987
    77
a member function \c set(Key,const Value &)
alpar@692
    78
for this purpose.
alpar@692
    79
\code
alpar@692
    80
  length.set(e,3.5);
alpar@692
    81
\endcode
alpar@692
    82
alpar@692
    83
The first case is more comfortable and if you store complex structures in your
alpar@692
    84
map, it might be more efficient. However, there are writable but
alpar@1083
    85
not reference maps, so if you want to write a generic algorithm, you should
alpar@1083
    86
insist on the second way.
alpar@692
    87
alpar@697
    88
\section how-to-write-your-own-map How to Write Your Own Maps
alpar@692
    89
alpar@692
    90
\subsection read-maps Readable Maps
alpar@202
    91
athos@1167
    92
Readable maps are very frequently used as the input of an
athos@1167
    93
algorithm.  For this purpose the most straightforward way is the use of the
alpar@921
    94
default maps provided by LEMON's graph structures.
alpar@692
    95
Very often however, it is more
alpar@289
    96
convenient and/or more efficient to write your own readable map.
alpar@202
    97
alpar@692
    98
You can find some examples below. In these examples \c Graph is the
alpar@692
    99
type of the particular graph structure you use.
alpar@692
   100
alpar@202
   101
alpar@204
   102
This simple map assigns \f$\pi\f$ to each edge.
alpar@204
   103
alpar@202
   104
\code
alpar@273
   105
struct MyMap 
alpar@202
   106
{
alpar@987
   107
  typedef double Value;
alpar@987
   108
  typedef Graph::Edge Key;
alpar@987
   109
  double operator[](Key e) const { return M_PI;}
alpar@204
   110
};
alpar@204
   111
\endcode
alpar@204
   112
alpar@692
   113
An alternative way to define maps is to use \c MapBase
alpar@692
   114
alpar@289
   115
\code
alpar@692
   116
struct MyMap : public MapBase<Graph::Edge,double>
alpar@289
   117
{
alpar@987
   118
  Value operator[](Key e) const { return M_PI;}
alpar@289
   119
};
alpar@289
   120
\endcode
alpar@289
   121
alpar@692
   122
Here is a bit more complex example.
alpar@1083
   123
It provides a length function obtained
alpar@692
   124
from a base length function shifted by a potential difference.
alpar@202
   125
alpar@202
   126
\code
alpar@1083
   127
class ReducedLengthMap  : public MapBase<Graph::Edge,double>
alpar@202
   128
{
alpar@1083
   129
  const Graph &g;
alpar@692
   130
  const Graph::EdgeMap<double> &orig_len;
alpar@692
   131
  const Graph::NodeMap<double> &pot;
alpar@202
   132
  
alpar@273
   133
public:
alpar@987
   134
  Value operator[](Key e) const {
deba@1788
   135
    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
alpar@210
   136
  }
alpar@202
   137
  
alpar@1083
   138
  ReducedLengthMap(const Graph &_g,
deba@1788
   139
                   const Graph::EdgeMap &_o,
deba@1788
   140
                   const Graph::NodeMap &_p)
deba@1788
   141
    : g(_g), orig_len(_o), pot(_p) {};
alpar@202
   142
};
alpar@202
   143
\endcode
alpar@202
   144
alpar@1083
   145
Then, you can call e.g. Dijkstra algoritm on this map like this:
alpar@1083
   146
\code
alpar@1083
   147
  ...
alpar@1083
   148
  ReducedLengthMap rm(g,len,pot);
alpar@1083
   149
  Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
alpar@1083
   150
  dij.run(s);
alpar@1083
   151
  ...
alpar@1083
   152
\endcode
alpar@1083
   153
alpar@692
   154
alpar@692
   155
\subsection write-maps Writable Maps
alpar@692
   156
alpar@692
   157
To be written...
alpar@692
   158
alpar@692
   159
\subsection side-effect-maps Maps with Side Effect
alpar@692
   160
alpar@692
   161
To be written...
alpar@692
   162
alpar@202
   163
*/
athos@1183
   164
}