COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/maps2.dox @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 2.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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
25\section custom_maps Writing Custom ReadMap
26\subsection custom_read_maps Readable Maps
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
32convenient and/or more efficient to write your own readable map.
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 M_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 M_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.