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 | */ |
---|