COIN-OR::LEMON - Graph Library

source: lemon-tutorial/maps.dox @ 55:edb7d5759e0d

Last change on this file since 55:edb7d5759e0d was 49:c8c5a2a4ec71, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Port the remaining 0.x tutorial contents from SVN -r 3524

File size: 13.9 KB
Line 
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
19namespace 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,
26thus they have to thouroughly revised, reorganized and reworked.
27
28The LEMON maps are not only just storage classes, but also
29they are %concepts of any key--value based data access.
30Beside the standard digraph maps, LEMON contains several "lightweight"
31\e map \e adaptor \e classes, which perform various operations on the
32data of the adapted maps when their access operations are called,
33but without actually copying or modifying the original storage.
34These classes also conform to the map %concepts, thus they can be used
35like standard LEMON maps.
36
37Let us suppose that we have a traffic network stored in a LEMON digraph
38structure with two arc maps \c length and \c speed, which
39denote the physical length of each arc and the maximum (or average)
40speed that can be achieved on the corresponding road-section,
41respectively. If we are interested in the best traveling times,
42the following code can be used.
43
44\code
45  dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
46\endcode
47
48
49Maps play a central role in LEMON. As their name suggests, they map a
50certain 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
58A 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").
62There also exists a special type of
63ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
64In addition that you can
65read and write the values of a key, a reference map
66can also give you a reference to the
67value belonging to a key, so you have a direct access to the memory address
68where it is stored.
69
70Each digraph structure in LEMON provides two standard map templates called
71\c ArcMap and \c NodeMap. Both are reference maps and you can easily
72assign data to the nodes and to the arcs of the digraph. For example if you
73have a digraph \c g defined as
74\code
75  ListDigraph g;
76\endcode
77and you want to assign a floating point value to each arc, you can do
78it like this.
79\code
80  ListDigraph::ArcMap<double> length(g);
81\endcode
82Note that you must give the underlying digraph to the constructor.
83
84The value of a readable map can be obtained by <tt>operator[]</tt>.
85\code
86  d=length[e];
87\endcode
88where \c e is an instance of \c ListDigraph::Arc.
89(Or anything else
90that converts to \c ListDigraph::Arc, like  \c ListDigraph::ArcIt or
91\c ListDigraph::OutArcIt etc.)
92
93There are two ways to assign a new value to a key
94
95- In case of a <em>reference map</em> <tt>operator[]</tt>
96gives you a reference to the
97value, thus you can use this.
98\code
99  length[e]=3.5;
100\endcode
101- <em>Writable maps</em> have
102a member function \c set(Key,const Value &)
103for this purpose.
104\code
105  length.set(e,3.5);
106\endcode
107
108The first case is more comfortable and if you store complex structures in your
109map, it might be more efficient. However, there are writable but
110not reference maps, so if you want to write a generic algorithm, you should
111insist 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
117Readable maps are very frequently used as the input of an
118algorithm.  For this purpose the most straightforward way is the use of the
119default maps provided by LEMON's digraph structures.
120Very often however, it is more
121convenient and/or more efficient to write your own readable map.
122
123You can find some examples below. In these examples \c Digraph is the
124type of the particular digraph structure you use.
125
126
127This simple map assigns \f$\pi\f$ to each arc.
128
129\code
130struct MyMap
131{
132  typedef double Value;
133  typedef Digraph::Arc Key;
134  double operator[](Key e) const { return PI;}
135};
136\endcode
137
138An alternative way to define maps is to use \c MapBase
139
140\code
141struct MyMap : public MapBase<Digraph::Arc,double>
142{
143  Value operator[](Key e) const { return PI;}
144};
145\endcode
146
147Here is a bit more complex example.
148It provides a length function obtained
149from a base length function shifted by a potential difference.
150
151\code
152class 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 
158public:
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
170Then, 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
180In the previous section we discussed digraph topology. That is the skeleton a complex
181digraph represented data-set needs. But how to assign the data itself to that skeleton?<br>
182Here come the \b maps in.
183
184\section maps_intro Introduction to maps
185Maps play a central role in LEMON. As their name suggests, they map a certain range of <i>keys</i> to certain <i>values</i>.
186In 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
193To 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
202readable 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
206providing you constant or non-constant reference to the value belonging to a key,
207so 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.
210The 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
217Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
218satisfying the \ref DigraphMap concept.
219If you want to assign data to nodes, just declare a NodeMap with the corresponding
220type. As an example, think of a arc-weighted digraph.
221\code ListDigraph::ArcMap<int>  weight(digraph); \endcode
222You can see that the map needs the digraph whose arcs will mapped, but nothing more.
223
224If the digraph class is extendable or erasable the map will automatically follow
225the changes you make. If a new node is added a default value is mapped to it.
226You can define the default value by passing a second argument to the map's constructor.
227\code ListDigraph::ArcMap<int>  weight(digraph, 13); \endcode
228But keep in mind that \c VALUE has to have copy constructor.
229
230Of course \c VALUE can be a rather complex type.
231
232For 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 }
236The 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
238this code. See \ref SubDigraph techniques - that's LEMON's true potential.)
239
240And the usage is simpler than the declaration suggests. The compiler deduces the
241template specialization, so the usage is like a simple function call.
242\skip std
243\until ;
244
245Most 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
247If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
248(coming soon) and will use maps hardly.
249Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
250
251Here we discuss some advanced map techniques. Like writing your own maps or how to
252extend/modify a maps functionality with adaptors.
253
254\section custom_maps Writing Custom ReadMap
255\subsection custom_read_maps Readable Maps
256
257Readable maps are very frequently used as the input of an
258algorithm.  For this purpose the most straightforward way is the use of the
259default maps provided by LEMON's digraph structures.
260Very often however, it is more
261convenient and/or more efficient to write your own readable map.
262
263You can find some examples below. In these examples \c Digraph is the
264type of the particular digraph structure you use.
265
266
267This simple map assigns \f$\pi\f$ to each arc.
268
269\code
270struct MyMap
271{
272  typedef double Value;
273  typedef Digraph::Arc Key;
274  double operator[](const Key &e) const { return PI;}
275};
276\endcode
277
278An alternative way to define maps is to use MapBase
279
280\code
281struct MyMap : public MapBase<Digraph::Arc,double>
282{
283  Value operator[](const Key& e) const { return PI;}
284};
285\endcode
286
287Here is a bit more complex example.
288It provides a length function obtained
289from a base length function shifted by a potential difference.
290
291\code
292class 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 
298public:
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
310Then, 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
331See \ref map_adaptors in the reference manual.
332
333
334[SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
335
336The basic functionality of the algorithms can be highly extended using
337special purpose map types for their internal data structures.
338For example, the \ref Dijkstra class stores a
339ef ProcessedMap,
340which has to be a writable node map of \ref bool value type.
341The assigned value of each node is set to \ref true when the node is
342processed, i.e., its actual distance is found.
343Applying a special map, \ref LoggerBoolMap, the processed order of
344the nodes can easily be stored in a standard container.
345
346Such specific map types can be passed to the algorithms using the technique of
347named template parameters. Similarly to the named function parameters,
348they 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
365The function-type interfaces are considerably simpler, but they can be
366used in almost all practical cases. Surprisingly, even the above example
367can also be implemented using the \ref dijkstra() function and
368named parameters, as follows.
369Note that the function-type interface has the major advantage
370that 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
379LEMON also contains visitor based algorithm classes for
380BFS and DFS.
381
382Skeleton visitor classes are defined for both BFS and DFS, the concrete
383implementations 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
397In the following example, the \ref discover()} and \code{examine()
398events are processed and the DFS tree is stored in an arc map.
399The values of this map indicate whether the corresponding arc
400reaches 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}
Note: See TracBrowser for help on using the repository browser.