20 /** |
20 /** |
21 [PAGE]sec_maps[PAGE] Maps |
21 [PAGE]sec_maps[PAGE] Maps |
22 |
22 |
23 \todo This page is under construction. |
23 \todo This page is under construction. |
24 |
24 |
|
25 \todo The following contents are ported from the LEMON 0.x tutorial, |
|
26 thus they have to thouroughly revised, reorganized and reworked. |
|
27 |
|
28 The LEMON maps are not only just storage classes, but also |
|
29 they are %concepts of any key--value based data access. |
|
30 Beside the standard digraph maps, LEMON contains several "lightweight" |
|
31 \e map \e adaptor \e classes, which perform various operations on the |
|
32 data of the adapted maps when their access operations are called, |
|
33 but without actually copying or modifying the original storage. |
|
34 These classes also conform to the map %concepts, thus they can be used |
|
35 like standard LEMON maps. |
|
36 |
|
37 Let us suppose that we have a traffic network stored in a LEMON digraph |
|
38 structure with two arc maps \c length and \c speed, which |
|
39 denote the physical length of each arc and the maximum (or average) |
|
40 speed that can be achieved on the corresponding road-section, |
|
41 respectively. If we are interested in the best traveling times, |
|
42 the following code can be used. |
|
43 |
|
44 \code |
|
45 dijkstra(g, divMap(length, speed)).distMap(dist).run(s); |
|
46 \endcode |
|
47 |
|
48 |
|
49 Maps play a central role in LEMON. As their name suggests, they map a |
|
50 certain range of \e keys to certain \e values. Each map has two |
|
51 <tt>typedef</tt>'s to determine the types of keys and values, like this: |
|
52 |
|
53 \code |
|
54 typedef Arc Key; |
|
55 typedef double Value; |
|
56 \endcode |
|
57 |
|
58 A map can be |
|
59 \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short), |
|
60 \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both |
|
61 (\ref lemon::concepts::ReadWriteMap "ReadWriteMap"). |
|
62 There also exists a special type of |
|
63 ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map". |
|
64 In addition that you can |
|
65 read and write the values of a key, a reference map |
|
66 can also give you a reference to the |
|
67 value belonging to a key, so you have a direct access to the memory address |
|
68 where it is stored. |
|
69 |
|
70 Each digraph structure in LEMON provides two standard map templates called |
|
71 \c ArcMap and \c NodeMap. Both are reference maps and you can easily |
|
72 assign data to the nodes and to the arcs of the digraph. For example if you |
|
73 have a digraph \c g defined as |
|
74 \code |
|
75 ListDigraph g; |
|
76 \endcode |
|
77 and you want to assign a floating point value to each arc, you can do |
|
78 it like this. |
|
79 \code |
|
80 ListDigraph::ArcMap<double> length(g); |
|
81 \endcode |
|
82 Note that you must give the underlying digraph to the constructor. |
|
83 |
|
84 The value of a readable map can be obtained by <tt>operator[]</tt>. |
|
85 \code |
|
86 d=length[e]; |
|
87 \endcode |
|
88 where \c e is an instance of \c ListDigraph::Arc. |
|
89 (Or anything else |
|
90 that converts to \c ListDigraph::Arc, like \c ListDigraph::ArcIt or |
|
91 \c ListDigraph::OutArcIt etc.) |
|
92 |
|
93 There are two ways to assign a new value to a key |
|
94 |
|
95 - In case of a <em>reference map</em> <tt>operator[]</tt> |
|
96 gives you a reference to the |
|
97 value, thus you can use this. |
|
98 \code |
|
99 length[e]=3.5; |
|
100 \endcode |
|
101 - <em>Writable maps</em> have |
|
102 a member function \c set(Key,const Value &) |
|
103 for this purpose. |
|
104 \code |
|
105 length.set(e,3.5); |
|
106 \endcode |
|
107 |
|
108 The first case is more comfortable and if you store complex structures in your |
|
109 map, it might be more efficient. However, there are writable but |
|
110 not reference maps, so if you want to write a generic algorithm, you should |
|
111 insist on the second way. |
|
112 |
|
113 \section how-to-write-your-own-map How to Write Your Own Maps |
|
114 |
|
115 \subsection read-maps Readable Maps |
|
116 |
|
117 Readable maps are very frequently used as the input of an |
|
118 algorithm. For this purpose the most straightforward way is the use of the |
|
119 default maps provided by LEMON's digraph structures. |
|
120 Very often however, it is more |
|
121 convenient and/or more efficient to write your own readable map. |
|
122 |
|
123 You can find some examples below. In these examples \c Digraph is the |
|
124 type of the particular digraph structure you use. |
|
125 |
|
126 |
|
127 This simple map assigns \f$\pi\f$ to each arc. |
|
128 |
|
129 \code |
|
130 struct MyMap |
|
131 { |
|
132 typedef double Value; |
|
133 typedef Digraph::Arc Key; |
|
134 double operator[](Key e) const { return PI;} |
|
135 }; |
|
136 \endcode |
|
137 |
|
138 An alternative way to define maps is to use \c MapBase |
|
139 |
|
140 \code |
|
141 struct MyMap : public MapBase<Digraph::Arc,double> |
|
142 { |
|
143 Value operator[](Key e) const { return PI;} |
|
144 }; |
|
145 \endcode |
|
146 |
|
147 Here is a bit more complex example. |
|
148 It provides a length function obtained |
|
149 from a base length function shifted by a potential difference. |
|
150 |
|
151 \code |
|
152 class ReducedLengthMap : public MapBase<Digraph::Arc,double> |
|
153 { |
|
154 const Digraph &g; |
|
155 const Digraph::ArcMap<double> &orig_len; |
|
156 const Digraph::NodeMap<double> &pot; |
|
157 |
|
158 public: |
|
159 Value operator[](Key e) const { |
|
160 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]); |
|
161 } |
|
162 |
|
163 ReducedLengthMap(const Digraph &_g, |
|
164 const Digraph::ArcMap &_o, |
|
165 const Digraph::NodeMap &_p) |
|
166 : g(_g), orig_len(_o), pot(_p) {}; |
|
167 }; |
|
168 \endcode |
|
169 |
|
170 Then, you can call e.g. Dijkstra algoritm on this map like this: |
|
171 \code |
|
172 ... |
|
173 ReducedLengthMap rm(g,len,pot); |
|
174 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm); |
|
175 dij.run(s); |
|
176 ... |
|
177 \endcode |
|
178 |
|
179 |
|
180 In the previous section we discussed digraph topology. That is the skeleton a complex |
|
181 digraph represented data-set needs. But how to assign the data itself to that skeleton?<br> |
|
182 Here come the \b maps in. |
|
183 |
|
184 \section maps_intro Introduction to maps |
|
185 Maps play a central role in LEMON. As their name suggests, they map a certain range of <i>keys</i> to certain <i>values</i>. |
|
186 In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this: |
|
187 \code |
|
188 typedef Arc Key; |
|
189 typedef double Value; |
|
190 \endcode |
|
191 (Except matrix maps, they have two key types.) |
|
192 |
|
193 To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes. |
|
194 <ul> |
|
195 <li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[]. |
|
196 \code value_typed_variable = map_instance[key_value]; \endcode |
|
197 </li> |
|
198 <li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function. |
|
199 \code map_instance.set(key_value, value_typed_expression); \endcode |
|
200 </li> |
|
201 <li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both |
|
202 readable and writable. It is delivered from them. |
|
203 </li> |
|
204 <li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs |
|
205 <i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to |
|
206 providing you constant or non-constant reference to the value belonging to a key, |
|
207 so you have a direct access to the memory address where it is stored. |
|
208 </li> |
|
209 <li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys. |
|
210 The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap", |
|
211 \ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap", |
|
212 \ref concepts::ReferenceMatrixMap "ReferenceMatrixMap") |
|
213 </li> |
|
214 </ul> |
|
215 |
|
216 \section maps_graph Digraphs' maps |
|
217 Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE> |
|
218 satisfying the \ref DigraphMap concept. |
|
219 If you want to assign data to nodes, just declare a NodeMap with the corresponding |
|
220 type. As an example, think of a arc-weighted digraph. |
|
221 \code ListDigraph::ArcMap<int> weight(digraph); \endcode |
|
222 You can see that the map needs the digraph whose arcs will mapped, but nothing more. |
|
223 |
|
224 If the digraph class is extendable or erasable the map will automatically follow |
|
225 the changes you make. If a new node is added a default value is mapped to it. |
|
226 You can define the default value by passing a second argument to the map's constructor. |
|
227 \code ListDigraph::ArcMap<int> weight(digraph, 13); \endcode |
|
228 But keep in mind that \c VALUE has to have copy constructor. |
|
229 |
|
230 Of course \c VALUE can be a rather complex type. |
|
231 |
|
232 For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)! |
|
233 \dontinclude maps_summary.cc |
|
234 \skip template |
|
235 \until } |
|
236 The task is simple. We need the summary of some kind of data assigned to a digraph's nodes. |
|
237 (Whit a little trick the summary can be calculated only to a sub-digraph without changing |
|
238 this code. See \ref SubDigraph techniques - that's LEMON's true potential.) |
|
239 |
|
240 And the usage is simpler than the declaration suggests. The compiler deduces the |
|
241 template specialization, so the usage is like a simple function call. |
|
242 \skip std |
|
243 \until ; |
|
244 |
|
245 Most of the time you will probably use digraph maps, but keep in mind, that in LEMON maps are more general and can be used widely. |
|
246 |
|
247 If you want some 'real-life' examples see the next page, where we discuss \ref algorithms |
|
248 (coming soon) and will use maps hardly. |
|
249 Or if you want to know more about maps read these \ref maps2 "advanced map techniques". |
|
250 |
|
251 Here we discuss some advanced map techniques. Like writing your own maps or how to |
|
252 extend/modify a maps functionality with adaptors. |
|
253 |
|
254 \section custom_maps Writing Custom ReadMap |
|
255 \subsection custom_read_maps Readable Maps |
|
256 |
|
257 Readable maps are very frequently used as the input of an |
|
258 algorithm. For this purpose the most straightforward way is the use of the |
|
259 default maps provided by LEMON's digraph structures. |
|
260 Very often however, it is more |
|
261 convenient and/or more efficient to write your own readable map. |
|
262 |
|
263 You can find some examples below. In these examples \c Digraph is the |
|
264 type of the particular digraph structure you use. |
|
265 |
|
266 |
|
267 This simple map assigns \f$\pi\f$ to each arc. |
|
268 |
|
269 \code |
|
270 struct MyMap |
|
271 { |
|
272 typedef double Value; |
|
273 typedef Digraph::Arc Key; |
|
274 double operator[](const Key &e) const { return PI;} |
|
275 }; |
|
276 \endcode |
|
277 |
|
278 An alternative way to define maps is to use MapBase |
|
279 |
|
280 \code |
|
281 struct MyMap : public MapBase<Digraph::Arc,double> |
|
282 { |
|
283 Value operator[](const Key& e) const { return PI;} |
|
284 }; |
|
285 \endcode |
|
286 |
|
287 Here is a bit more complex example. |
|
288 It provides a length function obtained |
|
289 from a base length function shifted by a potential difference. |
|
290 |
|
291 \code |
|
292 class ReducedLengthMap : public MapBase<Digraph::Arc,double> |
|
293 { |
|
294 const Digraph &g; |
|
295 const Digraph::ArcMap<double> &orig_len; |
|
296 const Digraph::NodeMap<double> &pot; |
|
297 |
|
298 public: |
|
299 Value operator[](Key e) const { |
|
300 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]); |
|
301 } |
|
302 |
|
303 ReducedLengthMap(const Digraph &_g, |
|
304 const Digraph::ArcMap &_o, |
|
305 const Digraph::NodeMap &_p) |
|
306 : g(_g), orig_len(_o), pot(_p) {}; |
|
307 }; |
|
308 \endcode |
|
309 |
|
310 Then, you can call e.g. Dijkstra algoritm on this map like this: |
|
311 \code |
|
312 ... |
|
313 ReducedLengthMap rm(g,len,pot); |
|
314 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm); |
|
315 dij.run(s); |
|
316 ... |
|
317 \endcode |
|
318 |
|
319 |
25 [SEC]sec_map_concepts[SEC] Map Concepts |
320 [SEC]sec_map_concepts[SEC] Map Concepts |
26 |
321 |
27 ... |
322 ... |
28 |
323 |
29 |
324 |
36 See \ref map_adaptors in the reference manual. |
331 See \ref map_adaptors in the reference manual. |
37 |
332 |
38 |
333 |
39 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps |
334 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps |
40 |
335 |
41 ... |
336 The basic functionality of the algorithms can be highly extended using |
|
337 special purpose map types for their internal data structures. |
|
338 For example, the \ref Dijkstra class stores a |
|
339 ef ProcessedMap, |
|
340 which has to be a writable node map of \ref bool value type. |
|
341 The assigned value of each node is set to \ref true when the node is |
|
342 processed, i.e., its actual distance is found. |
|
343 Applying a special map, \ref LoggerBoolMap, the processed order of |
|
344 the nodes can easily be stored in a standard container. |
|
345 |
|
346 Such specific map types can be passed to the algorithms using the technique of |
|
347 named template parameters. Similarly to the named function parameters, |
|
348 they allow specifying any subset of the parameters and in arbitrary order. |
|
349 |
|
350 \code |
|
351 typedef vector<ListDigraph::Node> Container; |
|
352 typedef back_insert_iterator<Container> InsertIterator; |
|
353 typedef LoggerBoolMap<InsertIterator> ProcessedMap; |
|
354 Dijkstra<ListDigraph> |
|
355 ::SetProcessedMap<ProcessedMap> |
|
356 ::Create dijktra(g, length); |
|
357 |
|
358 Container container; |
|
359 InsertIterator iterator(container); |
|
360 ProcessedMap processed(iterator); |
|
361 |
|
362 dijkstra.processedMap(processed).run(s); |
|
363 \endcode |
|
364 |
|
365 The function-type interfaces are considerably simpler, but they can be |
|
366 used in almost all practical cases. Surprisingly, even the above example |
|
367 can also be implemented using the \ref dijkstra() function and |
|
368 named parameters, as follows. |
|
369 Note that the function-type interface has the major advantage |
|
370 that temporary objects can be passed as parameters. |
|
371 |
|
372 \code |
|
373 vector<ListDigraph::Node> process_order; |
|
374 dijkstra(g, length) |
|
375 .processedMap(loggerBoolMap(back_inserter(process_order))) |
|
376 .run(s); |
|
377 \endcode |
|
378 |
|
379 LEMON also contains visitor based algorithm classes for |
|
380 BFS and DFS. |
|
381 |
|
382 Skeleton visitor classes are defined for both BFS and DFS, the concrete |
|
383 implementations can be inherited from them. |
|
384 \code |
|
385 template <typename GR> |
|
386 struct DfsVisitor { |
|
387 void start(const typename GR::Node& node) {} |
|
388 void stop(const typename GR::Node& node) {} |
|
389 void reach(const typename GR::Node& node) {} |
|
390 void leave(const typename GR::Node& node) {} |
|
391 void discover(const typename GR::Arc& arc) {} |
|
392 void examine(const typename GR::Arc& arc) {} |
|
393 void backtrack(const typename GR::Arc& arc) {} |
|
394 }; |
|
395 \endcode |
|
396 |
|
397 In the following example, the \ref discover()} and \code{examine() |
|
398 events are processed and the DFS tree is stored in an arc map. |
|
399 The values of this map indicate whether the corresponding arc |
|
400 reaches a new node or its target node is already reached. |
|
401 \code |
|
402 template <typename GR> |
|
403 struct TreeVisitor : public DfsVisitor<GR> { |
|
404 TreeVisitor(typename GR::ArcMap<bool>& tree) |
|
405 : _tree(tree) {} |
|
406 void discover(const typename GR::Arc& arc) |
|
407 { _tree[arc] = true; } |
|
408 void examine(const typename GR::Arc& arc) |
|
409 { _tree[arc] = false; } |
|
410 typename GR::ArcMap<bool>& _tree; |
|
411 }; |
|
412 \endcode |
|
413 |
42 |
414 |
43 [TRAILER] |
415 [TRAILER] |
44 */ |
416 */ |
45 } |
417 } |