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