|
1 /** |
|
2 \page maps2 Maps II. |
|
3 |
|
4 Here we discuss some advanced map techniques. Like writing your own maps or how to |
|
5 extend/modify a maps functionality with adaptors. |
|
6 |
|
7 \section custom_maps Writing Custom ReadMap |
|
8 \subsection custom_read_maps Readable Maps |
|
9 |
|
10 Readable maps are very frequently used as the input of an |
|
11 algorithm. For this purpose the most straightforward way is the use of the |
|
12 default maps provided by LEMON's graph structures. |
|
13 Very often however, it is more |
|
14 convenient and/or more efficient to write your own readable map. |
|
15 |
|
16 You can find some examples below. In these examples \c Graph is the |
|
17 type of the particular graph structure you use. |
|
18 |
|
19 |
|
20 This simple map assigns \f$\pi\f$ to each edge. |
|
21 |
|
22 \code |
|
23 struct MyMap |
|
24 { |
|
25 typedef double Value; |
|
26 typedef Graph::Edge Key; |
|
27 double operator[](Key e) const { return M_PI;} |
|
28 }; |
|
29 \endcode |
|
30 |
|
31 An alternative way to define maps is to use MapBase |
|
32 |
|
33 \code |
|
34 struct MyMap : public MapBase<Graph::Edge,double> |
|
35 { |
|
36 Value operator[](Key e) const { return M_PI;} |
|
37 }; |
|
38 \endcode |
|
39 |
|
40 Here is a bit more complex example. |
|
41 It provides a length function obtained |
|
42 from a base length function shifted by a potential difference. |
|
43 |
|
44 \code |
|
45 class 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 |
|
51 public: |
|
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 |
|
63 Then, 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 */ |