COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/maps2.dox @ 2390:8450951a8e2d

Last change on this file since 2390:8450951a8e2d was 2196:09af6d2b683b, checked in by Alpar Juttner, 13 years ago

Add missing Tutorial dox files

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