[2391] | 1 | /* -*- C++ -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
| 4 | * |
---|
[2553] | 5 | * Copyright (C) 2003-2008 |
---|
[2391] | 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
[1083] | 19 | namespace lemon{ |
---|
[202] | 20 | /*! |
---|
| 21 | |
---|
[1043] | 22 | \page maps-page Maps |
---|
[692] | 23 | |
---|
[1167] | 24 | Maps play a central role in LEMON. As their name suggests, they map a |
---|
[692] | 25 | certain range of \e keys to certain \e values. Each map has two |
---|
| 26 | <tt>typedef</tt>'s to determine the types of keys and values, like this: |
---|
| 27 | |
---|
| 28 | \code |
---|
[987] | 29 | typedef Edge Key; |
---|
| 30 | typedef double Value; |
---|
[692] | 31 | \endcode |
---|
| 32 | |
---|
[1183] | 33 | A map can be |
---|
[2260] | 34 | \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short), |
---|
| 35 | \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both |
---|
| 36 | (\ref lemon::concepts::ReadWriteMap "ReadWriteMap"). |
---|
[1083] | 37 | There also exists a special type of |
---|
[2260] | 38 | ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map". |
---|
[1083] | 39 | In addition that you can |
---|
[692] | 40 | read and write the values of a key, a reference map |
---|
| 41 | can also give you a reference to the |
---|
| 42 | value belonging to a key, so you have a direct access to the memory address |
---|
| 43 | where it is stored. |
---|
| 44 | |
---|
[921] | 45 | Each graph structure in LEMON provides two standard map templates called |
---|
[692] | 46 | \c EdgeMap and \c NodeMap. Both are reference maps and you can easily |
---|
| 47 | assign data to the nodes and to the edges of the graph. For example if you |
---|
[1788] | 48 | have a graph \c g defined as |
---|
[692] | 49 | \code |
---|
[1788] | 50 | ListGraph g; |
---|
[692] | 51 | \endcode |
---|
[1083] | 52 | and you want to assign a floating point value to each edge, you can do |
---|
[692] | 53 | it like this. |
---|
| 54 | \code |
---|
[1788] | 55 | ListGraph::EdgeMap<double> length(g); |
---|
[692] | 56 | \endcode |
---|
[1083] | 57 | Note that you must give the underlying graph to the constructor. |
---|
[692] | 58 | |
---|
| 59 | The value of a readable map can be obtained by <tt>operator[]</tt>. |
---|
| 60 | \code |
---|
| 61 | d=length[e]; |
---|
| 62 | \endcode |
---|
| 63 | where \c e is an instance of \c ListGraph::Edge. |
---|
| 64 | (Or anything else |
---|
| 65 | that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or |
---|
[1083] | 66 | \c ListGraph::OutEdgeIt etc.) |
---|
[692] | 67 | |
---|
[1167] | 68 | There are two ways to assign a new value to a key |
---|
[692] | 69 | |
---|
| 70 | - In case of a <em>reference map</em> <tt>operator[]</tt> |
---|
| 71 | gives you a reference to the |
---|
| 72 | value, thus you can use this. |
---|
| 73 | \code |
---|
| 74 | length[e]=3.5; |
---|
| 75 | \endcode |
---|
| 76 | - <em>Writable maps</em> have |
---|
[987] | 77 | a member function \c set(Key,const Value &) |
---|
[692] | 78 | for this purpose. |
---|
| 79 | \code |
---|
| 80 | length.set(e,3.5); |
---|
| 81 | \endcode |
---|
| 82 | |
---|
| 83 | The first case is more comfortable and if you store complex structures in your |
---|
| 84 | map, it might be more efficient. However, there are writable but |
---|
[1083] | 85 | not reference maps, so if you want to write a generic algorithm, you should |
---|
| 86 | insist on the second way. |
---|
[692] | 87 | |
---|
[697] | 88 | \section how-to-write-your-own-map How to Write Your Own Maps |
---|
[692] | 89 | |
---|
| 90 | \subsection read-maps Readable Maps |
---|
[202] | 91 | |
---|
[1167] | 92 | Readable maps are very frequently used as the input of an |
---|
| 93 | algorithm. For this purpose the most straightforward way is the use of the |
---|
[921] | 94 | default maps provided by LEMON's graph structures. |
---|
[692] | 95 | Very often however, it is more |
---|
[289] | 96 | convenient and/or more efficient to write your own readable map. |
---|
[202] | 97 | |
---|
[692] | 98 | You can find some examples below. In these examples \c Graph is the |
---|
| 99 | type of the particular graph structure you use. |
---|
| 100 | |
---|
[202] | 101 | |
---|
[204] | 102 | This simple map assigns \f$\pi\f$ to each edge. |
---|
| 103 | |
---|
[202] | 104 | \code |
---|
[273] | 105 | struct MyMap |
---|
[202] | 106 | { |
---|
[987] | 107 | typedef double Value; |
---|
| 108 | typedef Graph::Edge Key; |
---|
[2568] | 109 | double operator[](Key e) const { return PI;} |
---|
[204] | 110 | }; |
---|
| 111 | \endcode |
---|
| 112 | |
---|
[692] | 113 | An alternative way to define maps is to use \c MapBase |
---|
| 114 | |
---|
[289] | 115 | \code |
---|
[692] | 116 | struct MyMap : public MapBase<Graph::Edge,double> |
---|
[289] | 117 | { |
---|
[2568] | 118 | Value operator[](Key e) const { return PI;} |
---|
[289] | 119 | }; |
---|
| 120 | \endcode |
---|
| 121 | |
---|
[692] | 122 | Here is a bit more complex example. |
---|
[1083] | 123 | It provides a length function obtained |
---|
[692] | 124 | from a base length function shifted by a potential difference. |
---|
[202] | 125 | |
---|
| 126 | \code |
---|
[1083] | 127 | class ReducedLengthMap : public MapBase<Graph::Edge,double> |
---|
[202] | 128 | { |
---|
[1083] | 129 | const Graph &g; |
---|
[692] | 130 | const Graph::EdgeMap<double> &orig_len; |
---|
| 131 | const Graph::NodeMap<double> &pot; |
---|
[202] | 132 | |
---|
[273] | 133 | public: |
---|
[987] | 134 | Value operator[](Key e) const { |
---|
[1788] | 135 | return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]); |
---|
[210] | 136 | } |
---|
[202] | 137 | |
---|
[1083] | 138 | ReducedLengthMap(const Graph &_g, |
---|
[1788] | 139 | const Graph::EdgeMap &_o, |
---|
| 140 | const Graph::NodeMap &_p) |
---|
| 141 | : g(_g), orig_len(_o), pot(_p) {}; |
---|
[202] | 142 | }; |
---|
| 143 | \endcode |
---|
| 144 | |
---|
[1083] | 145 | Then, you can call e.g. Dijkstra algoritm on this map like this: |
---|
| 146 | \code |
---|
| 147 | ... |
---|
| 148 | ReducedLengthMap rm(g,len,pot); |
---|
| 149 | Dijkstra<Graph,ReducedLengthMap> dij(g,rm); |
---|
| 150 | dij.run(s); |
---|
| 151 | ... |
---|
| 152 | \endcode |
---|
| 153 | |
---|
[692] | 154 | |
---|
| 155 | \subsection write-maps Writable Maps |
---|
| 156 | |
---|
| 157 | To be written... |
---|
| 158 | |
---|
| 159 | \subsection side-effect-maps Maps with Side Effect |
---|
| 160 | |
---|
| 161 | To be written... |
---|
| 162 | |
---|
[202] | 163 | */ |
---|
[1183] | 164 | } |
---|