[2196] | 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 | */ |
---|