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 be thoroughly revised and reworked.
28 \warning Currently, this section may contain old or faulty contents.
30 The LEMON maps are not only just storage classes, but also
31 they are %concepts of any key--value based data access.
32 Beside the standard digraph maps, LEMON contains several "lightweight"
33 \e map \e adaptor \e classes, which perform various operations on the
34 data of the adapted maps when their access operations are called,
35 but without actually copying or modifying the original storage.
36 These classes also conform to the map %concepts, thus they can be used
37 like standard LEMON maps.
39 Let us suppose that we have a traffic network stored in a LEMON digraph
40 structure with two arc maps \c length and \c speed, which
41 denote the physical length of each arc and the maximum (or average)
42 speed that can be achieved on the corresponding road-section,
43 respectively. If we are interested in the best traveling times,
44 the following code can be used.
47 dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
51 Maps play a central role in LEMON. As their name suggests, they map a
52 certain range of \e keys to certain \e values. Each map has two
53 <tt>typedef</tt>'s to determine the types of keys and values, like this:
61 \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
62 \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
63 (\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
64 There also exists a special type of
65 ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
66 In addition that you can
67 read and write the values of a key, a reference map
68 can also give you a reference to the
69 value belonging to a key, so you have a direct access to the memory address
72 Each digraph structure in LEMON provides two standard map templates called
73 \c ArcMap and \c NodeMap. Both are reference maps and you can easily
74 assign data to the nodes and to the arcs of the digraph. For example if you
75 have a digraph \c g defined as
79 and you want to assign a floating point value to each arc, you can do
82 ListDigraph::ArcMap<double> length(g);
84 Note that you must give the underlying digraph to the constructor.
86 The value of a readable map can be obtained by <tt>operator[]</tt>.
90 where \c e is an instance of \c ListDigraph::Arc.
92 that converts to \c ListDigraph::Arc, like \c ListDigraph::ArcIt or
93 \c ListDigraph::OutArcIt etc.)
95 There are two ways to assign a new value to a key
97 - In case of a <em>reference map</em> <tt>operator[]</tt>
98 gives you a reference to the
99 value, thus you can use this.
103 - <em>Writable maps</em> have
104 a member function \c set(Key,const Value &)
110 The first case is more comfortable and if you store complex structures in your
111 map, it might be more efficient. However, there are writable but
112 not reference maps, so if you want to write a generic algorithm, you should
113 insist on the second way.
115 \section how-to-write-your-own-map How to Write Your Own Maps
117 \subsection read-maps Readable Maps
119 Readable maps are very frequently used as the input of an
120 algorithm. For this purpose the most straightforward way is the use of the
121 default maps provided by LEMON's digraph structures.
122 Very often however, it is more
123 convenient and/or more efficient to write your own readable map.
125 You can find some examples below. In these examples \c Digraph is the
126 type of the particular digraph structure you use.
129 This simple map assigns \f$\pi\f$ to each arc.
134 typedef double Value;
135 typedef Digraph::Arc Key;
136 double operator[](Key e) const { return PI;}
140 An alternative way to define maps is to use \c MapBase
143 struct MyMap : public MapBase<Digraph::Arc,double>
145 Value operator[](Key e) const { return PI;}
149 Here is a bit more complex example.
150 It provides a length function obtained
151 from a base length function shifted by a potential difference.
154 class ReducedLengthMap : public MapBase<Digraph::Arc,double>
157 const Digraph::ArcMap<double> &orig_len;
158 const Digraph::NodeMap<double> &pot;
161 Value operator[](Key e) const {
162 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
165 ReducedLengthMap(const Digraph &_g,
166 const Digraph::ArcMap &_o,
167 const Digraph::NodeMap &_p)
168 : g(_g), orig_len(_o), pot(_p) {};
172 Then, you can call e.g. Dijkstra algoritm on this map like this:
175 ReducedLengthMap rm(g,len,pot);
176 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
182 In the previous section we discussed digraph topology. That is the skeleton a complex
183 digraph represented data-set needs. But how to assign the data itself to that skeleton?<br>
184 Here come the \b maps in.
186 \section maps_intro Introduction to maps
187 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>.
188 In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:
191 typedef double Value;
193 (Except matrix maps, they have two key types.)
195 To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes.
197 <li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
198 \code value_typed_variable = map_instance[key_value]; \endcode
200 <li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
201 \code map_instance.set(key_value, value_typed_expression); \endcode
203 <li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
204 readable and writable. It is delivered from them.
206 <li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
207 <i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to
208 providing you constant or non-constant reference to the value belonging to a key,
209 so you have a direct access to the memory address where it is stored.
211 <li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
212 The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap",
213 \ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
214 \ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
218 \section maps_graph Digraphs' maps
219 Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
220 satisfying the \ref DigraphMap concept.
221 If you want to assign data to nodes, just declare a NodeMap with the corresponding
222 type. As an example, think of a arc-weighted digraph.
223 \code ListDigraph::ArcMap<int> weight(digraph); \endcode
224 You can see that the map needs the digraph whose arcs will mapped, but nothing more.
226 If the digraph class is extendable or erasable the map will automatically follow
227 the changes you make. If a new node is added a default value is mapped to it.
228 You can define the default value by passing a second argument to the map's constructor.
229 \code ListDigraph::ArcMap<int> weight(digraph, 13); \endcode
230 But keep in mind that \c VALUE has to have copy constructor.
232 Of course \c VALUE can be a rather complex type.
234 For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
235 \dontinclude maps_summary.cc
238 The task is simple. We need the summary of some kind of data assigned to a digraph's nodes.
239 (Whit a little trick the summary can be calculated only to a sub-digraph without changing
240 this code. See \ref SubDigraph techniques - that's LEMON's true potential.)
242 And the usage is simpler than the declaration suggests. The compiler deduces the
243 template specialization, so the usage is like a simple function call.
247 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.
249 If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
250 (coming soon) and will use maps hardly.
251 Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
253 Here we discuss some advanced map techniques. Like writing your own maps or how to
254 extend/modify a maps functionality with adaptors.
256 \section custom_maps Writing Custom ReadMap
257 \subsection custom_read_maps Readable Maps
259 Readable maps are very frequently used as the input of an
260 algorithm. For this purpose the most straightforward way is the use of the
261 default maps provided by LEMON's digraph structures.
262 Very often however, it is more
263 convenient and/or more efficient to write your own readable map.
265 You can find some examples below. In these examples \c Digraph is the
266 type of the particular digraph structure you use.
269 This simple map assigns \f$\pi\f$ to each arc.
274 typedef double Value;
275 typedef Digraph::Arc Key;
276 double operator[](const Key &e) const { return PI;}
280 An alternative way to define maps is to use MapBase
283 struct MyMap : public MapBase<Digraph::Arc,double>
285 Value operator[](const Key& e) const { return PI;}
289 Here is a bit more complex example.
290 It provides a length function obtained
291 from a base length function shifted by a potential difference.
294 class ReducedLengthMap : public MapBase<Digraph::Arc,double>
297 const Digraph::ArcMap<double> &orig_len;
298 const Digraph::NodeMap<double> &pot;
301 Value operator[](Key e) const {
302 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
305 ReducedLengthMap(const Digraph &_g,
306 const Digraph::ArcMap &_o,
307 const Digraph::NodeMap &_p)
308 : g(_g), orig_len(_o), pot(_p) {};
312 Then, you can call e.g. Dijkstra algoritm on this map like this:
315 ReducedLengthMap rm(g,len,pot);
316 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
322 [SEC]sec_map_concepts[SEC] Map Concepts
327 [SEC]sec_own_maps[SEC] Creating Own Maps
331 [SEC]sec_map_adaptors[SEC] Map Adaptors
333 See \ref map_adaptors in the reference manual.
336 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
338 The basic functionality of the algorithms can be highly extended using
339 special purpose map types for their internal data structures.
340 For example, the \ref Dijkstra class stores a
342 which has to be a writable node map of \ref bool value type.
343 The assigned value of each node is set to \ref true when the node is
344 processed, i.e., its actual distance is found.
345 Applying a special map, \ref LoggerBoolMap, the processed order of
346 the nodes can easily be stored in a standard container.
348 Such specific map types can be passed to the algorithms using the technique of
349 named template parameters. Similarly to the named function parameters,
350 they allow specifying any subset of the parameters and in arbitrary order.
353 typedef vector<ListDigraph::Node> Container;
354 typedef back_insert_iterator<Container> InsertIterator;
355 typedef LoggerBoolMap<InsertIterator> ProcessedMap;
356 Dijkstra<ListDigraph>
357 ::SetProcessedMap<ProcessedMap>
358 ::Create dijktra(g, length);
361 InsertIterator iterator(container);
362 ProcessedMap processed(iterator);
364 dijkstra.processedMap(processed).run(s);
367 The function-type interfaces are considerably simpler, but they can be
368 used in almost all practical cases. Surprisingly, even the above example
369 can also be implemented using the \ref dijkstra() function and
370 named parameters, as follows.
371 Note that the function-type interface has the major advantage
372 that temporary objects can be passed as parameters.
375 vector<ListDigraph::Node> process_order;
377 .processedMap(loggerBoolMap(back_inserter(process_order)))
381 LEMON also contains visitor based algorithm classes for
384 Skeleton visitor classes are defined for both BFS and DFS, the concrete
385 implementations can be inherited from them.
387 template <typename GR>
389 void start(const typename GR::Node& node) {}
390 void stop(const typename GR::Node& node) {}
391 void reach(const typename GR::Node& node) {}
392 void leave(const typename GR::Node& node) {}
393 void discover(const typename GR::Arc& arc) {}
394 void examine(const typename GR::Arc& arc) {}
395 void backtrack(const typename GR::Arc& arc) {}
399 In the following example, the \ref discover()} and \code{examine()
400 events are processed and the DFS tree is stored in an arc map.
401 The values of this map indicate whether the corresponding arc
402 reaches a new node or its target node is already reached.
404 template <typename GR>
405 struct TreeVisitor : public DfsVisitor<GR> {
406 TreeVisitor(typename GR::ArcMap<bool>& tree)
408 void discover(const typename GR::Arc& arc)
409 { _tree[arc] = true; }
410 void examine(const typename GR::Arc& arc)
411 { _tree[arc] = false; }
412 typename GR::ArcMap<bool>& _tree;