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 Maps play a central role in LEMON. As their name suggests, they map a
40 certain range of \e keys to certain \e values. Each map has two
41 <tt>typedef</tt>'s to determine the types of keys and values, like this:
49 \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
50 \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
51 (\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
52 There also exists a special type of
53 ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
54 In addition that you can
55 read and write the values of a key, a reference map
56 can also give you a reference to the
57 value belonging to a key, so you have a direct access to the memory address
60 Each digraph structure in LEMON provides two standard map templates called
61 \c ArcMap and \c NodeMap. Both are reference maps and you can easily
62 assign data to the nodes and to the arcs of the digraph. For example if you
63 have a digraph \c g defined as
67 and you want to assign a floating point value to each arc, you can do
70 ListDigraph::ArcMap<double> length(g);
72 Note that you must give the underlying digraph to the constructor.
74 The value of a readable map can be obtained by <tt>operator[]</tt>.
78 where \c e is an instance of \c ListDigraph::Arc.
80 that converts to \c ListDigraph::Arc, like \c ListDigraph::ArcIt or
81 \c ListDigraph::OutArcIt etc.)
83 There are two ways to assign a new value to a key
85 - In case of a <em>reference map</em> <tt>operator[]</tt>
86 gives you a reference to the
87 value, thus you can use this.
91 - <em>Writable maps</em> have
92 a member function \c set(Key,const Value &)
98 The first case is more comfortable and if you store complex structures in your
99 map, it might be more efficient. However, there are writable but
100 not reference maps, so if you want to write a generic algorithm, you should
101 insist on the second way.
103 \section how-to-write-your-own-map How to Write Your Own Maps
105 \subsection read-maps Readable Maps
107 Readable maps are very frequently used as the input of an
108 algorithm. For this purpose the most straightforward way is the use of the
109 default maps provided by LEMON's digraph structures.
110 Very often however, it is more
111 convenient and/or more efficient to write your own readable map.
113 You can find some examples below. In these examples \c Digraph is the
114 type of the particular digraph structure you use.
117 This simple map assigns \f$\pi\f$ to each arc.
122 typedef double Value;
123 typedef Digraph::Arc Key;
124 double operator[](Key e) const { return PI;}
128 An alternative way to define maps is to use \c MapBase
131 struct MyMap : public MapBase<Digraph::Arc,double>
133 Value operator[](Key e) const { return PI;}
137 Here is a bit more complex example.
138 It provides a length function obtained
139 from a base length function shifted by a potential difference.
142 class ReducedLengthMap : public MapBase<Digraph::Arc,double>
145 const Digraph::ArcMap<double> &orig_len;
146 const Digraph::NodeMap<double> &pot;
149 Value operator[](Key e) const {
150 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
153 ReducedLengthMap(const Digraph &_g,
154 const Digraph::ArcMap &_o,
155 const Digraph::NodeMap &_p)
156 : g(_g), orig_len(_o), pot(_p) {};
160 Then, you can call e.g. Dijkstra algoritm on this map like this:
163 ReducedLengthMap rm(g,len,pot);
164 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
170 In the previous section we discussed digraph topology. That is the skeleton a complex
171 digraph represented data-set needs. But how to assign the data itself to that skeleton?<br>
172 Here come the \b maps in.
174 \section maps_intro Introduction to maps
175 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>.
176 In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:
179 typedef double Value;
181 (Except matrix maps, they have two key types.)
183 To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes.
185 <li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
186 \code value_typed_variable = map_instance[key_value]; \endcode
188 <li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
189 \code map_instance.set(key_value, value_typed_expression); \endcode
191 <li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
192 readable and writable. It is delivered from them.
194 <li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
195 <i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to
196 providing you constant or non-constant reference to the value belonging to a key,
197 so you have a direct access to the memory address where it is stored.
199 <li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
200 The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap",
201 \ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
202 \ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
206 \section maps_graph Digraphs' maps
207 Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
208 satisfying the \ref DigraphMap concept.
209 If you want to assign data to nodes, just declare a NodeMap with the corresponding
210 type. As an example, think of a arc-weighted digraph.
211 \code ListDigraph::ArcMap<int> weight(digraph); \endcode
212 You can see that the map needs the digraph whose arcs will mapped, but nothing more.
214 If the digraph class is extendable or erasable the map will automatically follow
215 the changes you make. If a new node is added a default value is mapped to it.
216 You can define the default value by passing a second argument to the map's constructor.
217 \code ListDigraph::ArcMap<int> weight(digraph, 13); \endcode
218 But keep in mind that \c VALUE has to have copy constructor.
220 Of course \c VALUE can be a rather complex type.
222 For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
223 \dontinclude maps_summary.cc
226 The task is simple. We need the summary of some kind of data assigned to a digraph's nodes.
227 (Whit a little trick the summary can be calculated only to a sub-digraph without changing
228 this code. See \ref SubDigraph techniques - that's LEMON's true potential.)
230 And the usage is simpler than the declaration suggests. The compiler deduces the
231 template specialization, so the usage is like a simple function call.
235 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.
237 If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
238 (coming soon) and will use maps hardly.
239 Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
241 Here we discuss some advanced map techniques. Like writing your own maps or how to
242 extend/modify a maps functionality with adaptors.
244 \section custom_maps Writing Custom ReadMap
245 \subsection custom_read_maps Readable Maps
247 Readable maps are very frequently used as the input of an
248 algorithm. For this purpose the most straightforward way is the use of the
249 default maps provided by LEMON's digraph structures.
250 Very often however, it is more
251 convenient and/or more efficient to write your own readable map.
253 You can find some examples below. In these examples \c Digraph is the
254 type of the particular digraph structure you use.
257 This simple map assigns \f$\pi\f$ to each arc.
262 typedef double Value;
263 typedef Digraph::Arc Key;
264 double operator[](const Key &e) const { return PI;}
268 An alternative way to define maps is to use MapBase
271 struct MyMap : public MapBase<Digraph::Arc,double>
273 Value operator[](const Key& e) const { return PI;}
277 Here is a bit more complex example.
278 It provides a length function obtained
279 from a base length function shifted by a potential difference.
282 class ReducedLengthMap : public MapBase<Digraph::Arc,double>
285 const Digraph::ArcMap<double> &orig_len;
286 const Digraph::NodeMap<double> &pot;
289 Value operator[](Key e) const {
290 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
293 ReducedLengthMap(const Digraph &_g,
294 const Digraph::ArcMap &_o,
295 const Digraph::NodeMap &_p)
296 : g(_g), orig_len(_o), pot(_p) {};
300 Then, you can call e.g. Dijkstra algoritm on this map like this:
303 ReducedLengthMap rm(g,len,pot);
304 Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
310 [SEC]sec_map_concepts[SEC] Map Concepts
315 [SEC]sec_own_maps[SEC] Creating Own Maps
319 [SEC]sec_map_adaptors[SEC] Map Adaptors
321 See \ref map_adaptors in the reference manual.
324 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
327 The basic functionality of the algorithms can be highly extended using
328 special purpose map types for their internal data structures.
329 For example, the \ref Dijkstra class stores a
331 which has to be a writable node map of \ref bool value type.
332 The assigned value of each node is set to \ref true when the node is
333 processed, i.e., its actual distance is found.
334 Applying a special map, \ref LoggerBoolMap, the processed order of
335 the nodes can easily be stored in a standard container.
337 Such specific map types can be passed to the algorithms using the technique of
338 named template parameters. Similarly to the named function parameters,
339 they allow specifying any subset of the parameters and in arbitrary order.
341 Let us suppose that we have a traffic network stored in a LEMON digraph
342 structure with two arc maps \c length and \c speed, which
343 denote the physical length of each arc and the maximum (or average)
344 speed that can be achieved on the corresponding road-section,
345 respectively. If we are interested in the best traveling times,
346 the following code can be used.
349 dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
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 Let us see a bit more complex example to demonstrate Dfs's capabilities.
383 We will see a program, which solves the problem of <b>topological ordering</b>.
384 We need to know in which order we should put on our clothes. The program will do the following:
386 <li>We run the dfs algorithm to all nodes.
387 <li>Put every node into a list when processed completely.
388 <li>Write out the list in reverse order.
391 \dontinclude topological_ordering.cc
392 First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
393 will be done through it.
396 The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
397 we need to do is insert the key - that is the node whose processing just finished - into the beginning
399 Although we implemented this needed helper class ourselves it was not necessary.
400 The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
401 what we needed. To be correct it's more general - and it's all in \c LEMON. But
402 we wanted to show you, how easy is to add additional functionality.
404 First we declare the needed data structures: the digraph and a map to store the nodes' label.
408 Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
415 Then add arcs which represent the precedences between those items.
419 See how easy is to access the internal information of this algorithm trough maps.
420 We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
424 And now comes the third part. Write out the list in reverse order. But the list was
425 composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
429 The program is to be found in the \ref demo directory: \ref topological_ordering.cc
431 LEMON also contains visitor based algorithm classes for
434 Skeleton visitor classes are defined for both BFS and DFS, the concrete
435 implementations can be inherited from them.
437 template <typename GR>
439 void start(const typename GR::Node& node) {}
440 void stop(const typename GR::Node& node) {}
441 void reach(const typename GR::Node& node) {}
442 void leave(const typename GR::Node& node) {}
443 void discover(const typename GR::Arc& arc) {}
444 void examine(const typename GR::Arc& arc) {}
445 void backtrack(const typename GR::Arc& arc) {}
449 In the following example, the \ref discover()} and \code{examine()
450 events are processed and the DFS tree is stored in an arc map.
451 The values of this map indicate whether the corresponding arc
452 reaches a new node or its target node is already reached.
454 template <typename GR>
455 struct TreeVisitor : public DfsVisitor<GR> {
456 TreeVisitor(typename GR::ArcMap<bool>& tree)
458 void discover(const typename GR::Arc& arc)
459 { _tree[arc] = true; }
460 void examine(const typename GR::Arc& arc)
461 { _tree[arc] = false; }
462 typename GR::ArcMap<bool>& _tree;