1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 [PAGE]sec_maps[PAGE] Maps
23 \todo This page is under construction.
25 \todo The following contents are ported from the LEMON 0.x tutorial,
26 thus they have to thouroughly revised, reorganized and reworked.
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.
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.
45 dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
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:
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
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
77 and you want to assign a floating point value to each arc, you can do
80 ListDigraph::ArcMap<double> length(g);
82 Note that you must give the underlying digraph to the constructor.
84 The value of a readable map can be obtained by <tt>operator[]</tt>.
88 where \c e is an instance of \c ListDigraph::Arc.
90 that converts to \c ListDigraph::Arc, like \c ListDigraph::ArcIt or
91 \c ListDigraph::OutArcIt etc.)
93 There are two ways to assign a new value to a key
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.
101 - <em>Writable maps</em> have
102 a member function \c set(Key,const Value &)
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.
113 \section how-to-write-your-own-map How to Write Your Own Maps
115 \subsection read-maps Readable Maps
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.
123 You can find some examples below. In these examples \c Digraph is the
124 type of the particular digraph structure you use.
127 This simple map assigns \f$\pi\f$ to each arc.
132 typedef double Value;
133 typedef Digraph::Arc Key;
134 double operator[](Key e) const { return PI;}
138 An alternative way to define maps is to use \c MapBase
141 struct MyMap : public MapBase<Digraph::Arc,double>
143 Value operator[](Key e) const { return PI;}
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.
152 class ReducedLengthMap : public MapBase<Digraph::Arc,double>
155 const Digraph::ArcMap<double> &orig_len;
156 const Digraph::NodeMap<double> &pot;
159 Value operator[](Key e) const {
160 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
163 ReducedLengthMap(const Digraph &_g,
164 const Digraph::ArcMap &_o,
165 const Digraph::NodeMap &_p)
166 : g(_g), orig_len(_o), pot(_p) {};
170 Then, you can call e.g. Dijkstra algoritm on this map like this:
173 ReducedLengthMap rm(g,len,pot);
174 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
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.
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:
189 typedef double Value;
191 (Except matrix maps, they have two key types.)
193 To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes.
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
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
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.
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.
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")
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.
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.
230 Of course \c VALUE can be a rather complex type.
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
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.)
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.
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.
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".
251 Here we discuss some advanced map techniques. Like writing your own maps or how to
252 extend/modify a maps functionality with adaptors.
254 \section custom_maps Writing Custom ReadMap
255 \subsection custom_read_maps Readable Maps
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.
263 You can find some examples below. In these examples \c Digraph is the
264 type of the particular digraph structure you use.
267 This simple map assigns \f$\pi\f$ to each arc.
272 typedef double Value;
273 typedef Digraph::Arc Key;
274 double operator[](const Key &e) const { return PI;}
278 An alternative way to define maps is to use MapBase
281 struct MyMap : public MapBase<Digraph::Arc,double>
283 Value operator[](const Key& e) const { return PI;}
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.
292 class ReducedLengthMap : public MapBase<Digraph::Arc,double>
295 const Digraph::ArcMap<double> &orig_len;
296 const Digraph::NodeMap<double> &pot;
299 Value operator[](Key e) const {
300 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
303 ReducedLengthMap(const Digraph &_g,
304 const Digraph::ArcMap &_o,
305 const Digraph::NodeMap &_p)
306 : g(_g), orig_len(_o), pot(_p) {};
310 Then, you can call e.g. Dijkstra algoritm on this map like this:
313 ReducedLengthMap rm(g,len,pot);
314 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
320 [SEC]sec_map_concepts[SEC] Map Concepts
325 [SEC]sec_own_maps[SEC] Creating Own Maps
329 [SEC]sec_map_adaptors[SEC] Map Adaptors
331 See \ref map_adaptors in the reference manual.
334 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
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
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.
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.
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);
359 InsertIterator iterator(container);
360 ProcessedMap processed(iterator);
362 dijkstra.processedMap(processed).run(s);
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.
373 vector<ListDigraph::Node> process_order;
375 .processedMap(loggerBoolMap(back_inserter(process_order)))
379 LEMON also contains visitor based algorithm classes for
382 Skeleton visitor classes are defined for both BFS and DFS, the concrete
383 implementations can be inherited from them.
385 template <typename GR>
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) {}
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.
402 template <typename GR>
403 struct TreeVisitor : public DfsVisitor<GR> {
404 TreeVisitor(typename GR::ArcMap<bool>& 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;