doc/maps.dox
author klao
Sat, 19 Feb 2005 21:11:20 +0000
changeset 1157 3996d2098090
parent 1043 52a2201a88e9
child 1167 ccbca6ba8b59
permissions -rw-r--r--
lemon/error.h: boost::shared_ptr helyett std::auto_ptr
(Sokkal kenylemetlenebb, es nem teljesen biztos, hogy helyes megoldas)
alpar@1083
     1
namespace lemon{
alpar@202
     2
/*!
alpar@202
     3
alpar@1043
     4
\page maps-page Maps
alpar@692
     5
alpar@921
     6
Maps play central role in LEMON. As their name suggests, they map a
alpar@692
     7
certain range of \e keys to certain \e values. Each map has two
alpar@692
     8
<tt>typedef</tt>'s to determine the types of keys and values, like this:
alpar@692
     9
alpar@692
    10
\code
alpar@987
    11
  typedef Edge Key;
alpar@987
    12
  typedef double Value;
alpar@692
    13
\endcode
alpar@692
    14
alpar@1083
    15
A map can \e readable (\ref lemon::concept::ReadMap "ReadMap", for short),
alpar@1083
    16
\e writable (\ref lemon::concept::WriteMap "WriteMap") or both
alpar@1083
    17
(\ref lemon::concept::ReadWriteMap "ReadWriteMap").
alpar@1083
    18
There also exists a special type of
alpar@1083
    19
ReadWrite map called \ref lemon::concept::ReferenceMap "reference map".
alpar@1083
    20
In addition that you can
alpar@692
    21
read and write the values of a key, a reference map
alpar@692
    22
can also give you a reference to the
alpar@692
    23
value belonging to a key, so you have a direct access to the memory address
alpar@692
    24
where it is stored.
alpar@692
    25
alpar@921
    26
Each graph structure in LEMON provides two standard map templates called
alpar@692
    27
\c EdgeMap and \c NodeMap. Both are reference maps and you can easily
alpar@692
    28
assign data to the nodes and to the edges of the graph. For example if you
alpar@692
    29
have a graph \c G defined as
alpar@692
    30
\code
alpar@692
    31
  ListGraph G;
alpar@692
    32
\endcode
alpar@1083
    33
and you want to assign a floating point value to each edge, you can do
alpar@692
    34
it like this.
alpar@692
    35
\code
alpar@692
    36
  ListGraph::EdgeMap<double> length(G);
alpar@692
    37
\endcode
alpar@1083
    38
Note that you must give the underlying graph to the constructor.
alpar@692
    39
alpar@692
    40
The value of a readable map can be obtained by <tt>operator[]</tt>.
alpar@692
    41
\code
alpar@692
    42
  d=length[e];
alpar@692
    43
\endcode
alpar@692
    44
where \c e is an instance of \c ListGraph::Edge.
alpar@692
    45
(Or anything else
alpar@692
    46
that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
alpar@1083
    47
\c ListGraph::OutEdgeIt etc.)
alpar@692
    48
alpar@692
    49
There are two ways the assign a new value to a key
alpar@692
    50
alpar@692
    51
- In case of a <em>reference map</em> <tt>operator[]</tt>
alpar@692
    52
gives you a reference to the
alpar@692
    53
value, thus you can use this.
alpar@692
    54
\code
alpar@692
    55
  length[e]=3.5;
alpar@692
    56
\endcode
alpar@692
    57
- <em>Writable maps</em> have
alpar@987
    58
a member function \c set(Key,const Value &)
alpar@692
    59
for this purpose.
alpar@692
    60
\code
alpar@692
    61
  length.set(e,3.5);
alpar@692
    62
\endcode
alpar@692
    63
alpar@692
    64
The first case is more comfortable and if you store complex structures in your
alpar@692
    65
map, it might be more efficient. However, there are writable but
alpar@1083
    66
not reference maps, so if you want to write a generic algorithm, you should
alpar@1083
    67
insist on the second way.
alpar@692
    68
alpar@697
    69
\section how-to-write-your-own-map How to Write Your Own Maps
alpar@692
    70
alpar@692
    71
\subsection read-maps Readable Maps
alpar@202
    72
alpar@1083
    73
Readable maps are very frequently used as the input of the
alpar@692
    74
algorithms.  For this purpose the most straightforward way is the use of the
alpar@921
    75
default maps provided by LEMON's graph structures.
alpar@692
    76
Very often however, it is more
alpar@289
    77
convenient and/or more efficient to write your own readable map.
alpar@202
    78
alpar@692
    79
You can find some examples below. In these examples \c Graph is the
alpar@692
    80
type of the particular graph structure you use.
alpar@692
    81
alpar@202
    82
alpar@204
    83
This simple map assigns \f$\pi\f$ to each edge.
alpar@204
    84
alpar@202
    85
\code
alpar@273
    86
struct MyMap 
alpar@202
    87
{
alpar@987
    88
  typedef double Value;
alpar@987
    89
  typedef Graph::Edge Key;
alpar@987
    90
  double operator[](Key e) const { return M_PI;}
alpar@204
    91
};
alpar@204
    92
\endcode
alpar@204
    93
alpar@692
    94
An alternative way to define maps is to use \c MapBase
alpar@692
    95
alpar@692
    96
\todo For this, \c MapBase seems to be a better name then \c NullMap.
alpar@289
    97
alpar@289
    98
\code
alpar@692
    99
struct MyMap : public MapBase<Graph::Edge,double>
alpar@289
   100
{
alpar@987
   101
  Value operator[](Key e) const { return M_PI;}
alpar@289
   102
};
alpar@289
   103
\endcode
alpar@289
   104
alpar@692
   105
Here is a bit more complex example.
alpar@1083
   106
It provides a length function obtained
alpar@692
   107
from a base length function shifted by a potential difference.
alpar@202
   108
alpar@202
   109
\code
alpar@1083
   110
class ReducedLengthMap  : public MapBase<Graph::Edge,double>
alpar@202
   111
{
alpar@1083
   112
  const Graph &g;
alpar@692
   113
  const Graph::EdgeMap<double> &orig_len;
alpar@692
   114
  const Graph::NodeMap<double> &pot;
alpar@202
   115
  
alpar@273
   116
public:
alpar@987
   117
  Value operator[](Key e) const {
alpar@986
   118
    return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e));
alpar@210
   119
  }
alpar@202
   120
  
alpar@1083
   121
  ReducedLengthMap(const Graph &_g,
alpar@1083
   122
                   const Graph::EdgeMap &o,
alpar@1083
   123
                   const Graph::NodeMap &p)
alpar@692
   124
    : G(g), orig_len(o), pot(p) {};
alpar@202
   125
};
alpar@202
   126
\endcode
alpar@202
   127
alpar@1083
   128
Then, you can call e.g. Dijkstra algoritm on this map like this:
alpar@1083
   129
\code
alpar@1083
   130
  ...
alpar@1083
   131
  ReducedLengthMap rm(g,len,pot);
alpar@1083
   132
  Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
alpar@1083
   133
  dij.run(s);
alpar@1083
   134
  ...
alpar@1083
   135
\endcode
alpar@1083
   136
alpar@692
   137
alpar@692
   138
\subsection write-maps Writable Maps
alpar@692
   139
alpar@692
   140
To be written...
alpar@692
   141
alpar@692
   142
\subsection side-effect-maps Maps with Side Effect
alpar@692
   143
alpar@692
   144
To be written...
alpar@692
   145
alpar@202
   146
*/
alpar@1083
   147
}