1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2010 |
---|
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 | |
---|
19 | namespace lemon { |
---|
20 | /** |
---|
21 | [PAGE]sec_maps[PAGE] Maps |
---|
22 | |
---|
23 | \todo This page is under construction. |
---|
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 | |
---|
320 | [SEC]sec_map_concepts[SEC] Map Concepts |
---|
321 | |
---|
322 | ... |
---|
323 | |
---|
324 | |
---|
325 | [SEC]sec_own_maps[SEC] Creating Own Maps |
---|
326 | |
---|
327 | ... |
---|
328 | |
---|
329 | [SEC]sec_map_adaptors[SEC] Map Adaptors |
---|
330 | |
---|
331 | See \ref map_adaptors in the reference manual. |
---|
332 | |
---|
333 | |
---|
334 | [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps |
---|
335 | |
---|
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 | |
---|
414 | |
---|
415 | [TRAILER] |
---|
416 | */ |
---|
417 | } |
---|