# source:lemon-0.x/doc/maps2.dox@2568:046c055217f6

Last change on this file since 2568:046c055217f6 was 2568:046c055217f6, checked in by Alpar Juttner, 16 years ago

Math constants + configure bugfix backported
from hg a315a588a20d and 761622e5ed4c

File size: 2.3 KB
Line
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
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
22Here we discuss some advanced map techniques. Like writing your own maps or how to
23extend/modify a maps functionality with adaptors.
24
27
28Readable maps are very frequently used as the input of an
29algorithm.  For this purpose the most straightforward way is the use of the
30default maps provided by LEMON's graph structures.
31Very often however, it is more
33
34You can find some examples below. In these examples \c Graph is the
35type of the particular graph structure you use.
36
37
38This simple map assigns \f$\pi\f$ to each edge.
39
40\code
41struct MyMap
42{
43  typedef double Value;
44  typedef Graph::Edge Key;
45  double operator[](const Key &e) const { return PI;}
46};
47\endcode
48
49An alternative way to define maps is to use MapBase
50
51\code
52struct MyMap : public MapBase<Graph::Edge,double>
53{
54  Value operator[](const Key& e) const { return PI;}
55};
56\endcode
57
58Here is a bit more complex example.
59It provides a length function obtained
60from a base length function shifted by a potential difference.
61
62\code
63class 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
69public:
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
81Then, 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*/
Note: See TracBrowser for help on using the repository browser.