[202] | 1 | /*! |
---|
| 2 | |
---|
| 3 | |
---|
[692] | 4 | |
---|
| 5 | \page maps Maps |
---|
| 6 | |
---|
[921] | 7 | Maps play central role in LEMON. As their name suggests, they map a |
---|
[692] | 8 | certain range of \e keys to certain \e values. Each map has two |
---|
| 9 | <tt>typedef</tt>'s to determine the types of keys and values, like this: |
---|
| 10 | |
---|
| 11 | \code |
---|
| 12 | typedef Edge KeyType; |
---|
| 13 | typedef double ValueType; |
---|
| 14 | \endcode |
---|
| 15 | |
---|
| 16 | A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both |
---|
| 17 | (ReadWrite Map). There also exists a special type of |
---|
| 18 | ReadWrite map called <em>reference map</em>. In addition that you can |
---|
| 19 | read and write the values of a key, a reference map |
---|
| 20 | can also give you a reference to the |
---|
| 21 | value belonging to a key, so you have a direct access to the memory address |
---|
| 22 | where it is stored. |
---|
| 23 | |
---|
[921] | 24 | Each graph structure in LEMON provides two standard map templates called |
---|
[692] | 25 | \c EdgeMap and \c NodeMap. Both are reference maps and you can easily |
---|
| 26 | assign data to the nodes and to the edges of the graph. For example if you |
---|
| 27 | have a graph \c G defined as |
---|
| 28 | \code |
---|
| 29 | ListGraph G; |
---|
| 30 | \endcode |
---|
| 31 | and you want to assign floating point value to each edge, you can do |
---|
| 32 | it like this. |
---|
| 33 | \code |
---|
| 34 | ListGraph::EdgeMap<double> length(G); |
---|
| 35 | \endcode |
---|
| 36 | |
---|
| 37 | The value of a readable map can be obtained by <tt>operator[]</tt>. |
---|
| 38 | \code |
---|
| 39 | d=length[e]; |
---|
| 40 | \endcode |
---|
| 41 | where \c e is an instance of \c ListGraph::Edge. |
---|
| 42 | (Or anything else |
---|
| 43 | that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or |
---|
| 44 | \c ListGraph::OutEdgeIt) |
---|
| 45 | |
---|
| 46 | There are two ways the assign a new value to a key |
---|
| 47 | |
---|
| 48 | - In case of a <em>reference map</em> <tt>operator[]</tt> |
---|
| 49 | gives you a reference to the |
---|
| 50 | value, thus you can use this. |
---|
| 51 | \code |
---|
| 52 | length[e]=3.5; |
---|
| 53 | \endcode |
---|
| 54 | - <em>Writable maps</em> have |
---|
| 55 | a member function \c set(KeyType,const ValueType &) |
---|
| 56 | for this purpose. |
---|
| 57 | \code |
---|
| 58 | length.set(e,3.5); |
---|
| 59 | \endcode |
---|
| 60 | |
---|
| 61 | The first case is more comfortable and if you store complex structures in your |
---|
| 62 | map, it might be more efficient. However, there are writable but |
---|
| 63 | not reference maps, so if you want to write an generic algorithm, you should |
---|
| 64 | insist on the second method. |
---|
| 65 | |
---|
[697] | 66 | \section how-to-write-your-own-map How to Write Your Own Maps |
---|
[692] | 67 | |
---|
| 68 | \subsection read-maps Readable Maps |
---|
[202] | 69 | |
---|
[289] | 70 | The readable maps are very frequently used as the input of the |
---|
[692] | 71 | algorithms. For this purpose the most straightforward way is the use of the |
---|
[921] | 72 | default maps provided by LEMON's graph structures. |
---|
[692] | 73 | Very often however, it is more |
---|
[289] | 74 | convenient and/or more efficient to write your own readable map. |
---|
[202] | 75 | |
---|
[692] | 76 | You can find some examples below. In these examples \c Graph is the |
---|
| 77 | type of the particular graph structure you use. |
---|
| 78 | |
---|
[202] | 79 | |
---|
[204] | 80 | This simple map assigns \f$\pi\f$ to each edge. |
---|
| 81 | |
---|
[202] | 82 | \code |
---|
[273] | 83 | struct MyMap |
---|
[202] | 84 | { |
---|
[273] | 85 | typedef double ValueType; |
---|
[692] | 86 | typedef Graph::Edge KeyType; |
---|
| 87 | double operator[](KeyType e) const { return M_PI;} |
---|
[204] | 88 | }; |
---|
| 89 | \endcode |
---|
| 90 | |
---|
[692] | 91 | An alternative way to define maps is to use \c MapBase |
---|
| 92 | |
---|
| 93 | \todo For this, \c MapBase seems to be a better name then \c NullMap. |
---|
[289] | 94 | |
---|
| 95 | \code |
---|
[692] | 96 | struct MyMap : public MapBase<Graph::Edge,double> |
---|
[289] | 97 | { |
---|
| 98 | ValueType operator[](KeyType e) const { return M_PI;} |
---|
| 99 | }; |
---|
| 100 | \endcode |
---|
| 101 | |
---|
[692] | 102 | Here is a bit more complex example. |
---|
| 103 | It provides a length function which is obtained |
---|
| 104 | from a base length function shifted by a potential difference. |
---|
[202] | 105 | |
---|
| 106 | \code |
---|
[692] | 107 | class MyLengthMap : public MapBase<Graph::Edge,double> |
---|
[202] | 108 | { |
---|
[692] | 109 | const Graph &G; |
---|
| 110 | const Graph::EdgeMap<double> &orig_len; |
---|
| 111 | const Graph::NodeMap<double> &pot; |
---|
[202] | 112 | |
---|
[273] | 113 | public: |
---|
[927] | 114 | ValueType operator[](KeyType e) const { |
---|
[986] | 115 | return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e)); |
---|
[210] | 116 | } |
---|
[202] | 117 | |
---|
[692] | 118 | MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p) |
---|
| 119 | : G(g), orig_len(o), pot(p) {}; |
---|
[202] | 120 | }; |
---|
| 121 | \endcode |
---|
| 122 | |
---|
[692] | 123 | |
---|
| 124 | \subsection write-maps Writable Maps |
---|
| 125 | |
---|
| 126 | To be written... |
---|
| 127 | |
---|
| 128 | \subsection side-effect-maps Maps with Side Effect |
---|
| 129 | |
---|
| 130 | To be written... |
---|
| 131 | |
---|
[202] | 132 | */ |
---|