COIN-OR::LEMON - Graph Library

source: lemon-tutorial/maps.dox @ 57:18404ec968ca

Last change on this file since 57:18404ec968ca was 57:18404ec968ca, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Various small fixes

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 be thoroughly revised and reworked.
27
28\warning Currently, this section may contain old or faulty contents.
29
30The LEMON maps are not only just storage classes, but also
31they are %concepts of any key--value based data access.
32Beside the standard digraph maps, LEMON contains several "lightweight"
33\e map \e adaptor \e classes, which perform various operations on the
34data of the adapted maps when their access operations are called,
35but without actually copying or modifying the original storage.
36These classes also conform to the map %concepts, thus they can be used
37like standard LEMON maps.
38
39Let us suppose that we have a traffic network stored in a LEMON digraph
40structure with two arc maps \c length and \c speed, which
41denote the physical length of each arc and the maximum (or average)
42speed that can be achieved on the corresponding road-section,
43respectively. If we are interested in the best traveling times,
44the following code can be used.
45
46\code
47  dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
48\endcode
49
50
51Maps play a central role in LEMON. As their name suggests, they map a
52certain 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:
54
55\code
56  typedef Arc Key;
57  typedef double Value;
58\endcode
59
60A map can be
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").
64There also exists a special type of
65ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
66In addition that you can
67read and write the values of a key, a reference map
68can also give you a reference to the
69value belonging to a key, so you have a direct access to the memory address
70where it is stored.
71
72Each digraph structure in LEMON provides two standard map templates called
73\c ArcMap and \c NodeMap. Both are reference maps and you can easily
74assign data to the nodes and to the arcs of the digraph. For example if you
75have a digraph \c g defined as
76\code
77  ListDigraph g;
78\endcode
79and you want to assign a floating point value to each arc, you can do
80it like this.
81\code
82  ListDigraph::ArcMap<double> length(g);
83\endcode
84Note that you must give the underlying digraph to the constructor.
85
86The value of a readable map can be obtained by <tt>operator[]</tt>.
87\code
88  d=length[e];
89\endcode
90where \c e is an instance of \c ListDigraph::Arc.
91(Or anything else
92that converts to \c ListDigraph::Arc, like  \c ListDigraph::ArcIt or
93\c ListDigraph::OutArcIt etc.)
94
95There are two ways to assign a new value to a key
96
97- In case of a <em>reference map</em> <tt>operator[]</tt>
98gives you a reference to the
99value, thus you can use this.
100\code
101  length[e]=3.5;
102\endcode
103- <em>Writable maps</em> have
104a member function \c set(Key,const Value &)
105for this purpose.
106\code
107  length.set(e,3.5);
108\endcode
109
110The first case is more comfortable and if you store complex structures in your
111map, it might be more efficient. However, there are writable but
112not reference maps, so if you want to write a generic algorithm, you should
113insist on the second way.
114
115\section how-to-write-your-own-map How to Write Your Own Maps
116
117\subsection read-maps Readable Maps
118
119Readable maps are very frequently used as the input of an
120algorithm.  For this purpose the most straightforward way is the use of the
121default maps provided by LEMON's digraph structures.
122Very often however, it is more
123convenient and/or more efficient to write your own readable map.
124
125You can find some examples below. In these examples \c Digraph is the
126type of the particular digraph structure you use.
127
128
129This simple map assigns \f$\pi\f$ to each arc.
130
131\code
132struct MyMap
133{
134  typedef double Value;
135  typedef Digraph::Arc Key;
136  double operator[](Key e) const { return PI;}
137};
138\endcode
139
140An alternative way to define maps is to use \c MapBase
141
142\code
143struct MyMap : public MapBase<Digraph::Arc,double>
144{
145  Value operator[](Key e) const { return PI;}
146};
147\endcode
148
149Here is a bit more complex example.
150It provides a length function obtained
151from a base length function shifted by a potential difference.
152
153\code
154class ReducedLengthMap  : public MapBase<Digraph::Arc,double>
155{
156  const Digraph &g;
157  const Digraph::ArcMap<double> &orig_len;
158  const Digraph::NodeMap<double> &pot;
159 
160public:
161  Value operator[](Key e) const {
162    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
163  }
164 
165  ReducedLengthMap(const Digraph &_g,
166                   const Digraph::ArcMap &_o,
167                   const Digraph::NodeMap &_p)
168    : g(_g), orig_len(_o), pot(_p) {};
169};
170\endcode
171
172Then, you can call e.g. Dijkstra algoritm on this map like this:
173\code
174  ...
175  ReducedLengthMap rm(g,len,pot);
176  Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
177  dij.run(s);
178  ...
179\endcode
180
181
182In the previous section we discussed digraph topology. That is the skeleton a complex
183digraph represented data-set needs. But how to assign the data itself to that skeleton?<br>
184Here come the \b maps in.
185
186\section maps_intro Introduction to maps
187Maps play a central role in LEMON. As their name suggests, they map a certain range of <i>keys</i> to certain <i>values</i>.
188In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:
189\code
190  typedef Arc Key;
191  typedef double Value;
192\endcode
193(Except matrix maps, they have two key types.)
194
195To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes.
196<ul>
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
199</li>
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
202</li>
203<li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
204readable and writable. It is delivered from them.
205</li>
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
208providing you constant or non-constant reference to the value belonging to a key,
209so you have a direct access to the memory address where it is stored.
210</li>
211<li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
212The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap",
213\ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
214\ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
215</li>
216</ul>
217
218\section maps_graph Digraphs' maps
219Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
220satisfying the \ref DigraphMap concept.
221If you want to assign data to nodes, just declare a NodeMap with the corresponding
222type. As an example, think of a arc-weighted digraph.
223\code ListDigraph::ArcMap<int>  weight(digraph); \endcode
224You can see that the map needs the digraph whose arcs will mapped, but nothing more.
225
226If the digraph class is extendable or erasable the map will automatically follow
227the changes you make. If a new node is added a default value is mapped to it.
228You can define the default value by passing a second argument to the map's constructor.
229\code ListDigraph::ArcMap<int>  weight(digraph, 13); \endcode
230But keep in mind that \c VALUE has to have copy constructor.
231
232Of course \c VALUE can be a rather complex type.
233
234For 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
236\skip template
237\until }
238The 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
240this code. See \ref SubDigraph techniques - that's LEMON's true potential.)
241
242And the usage is simpler than the declaration suggests. The compiler deduces the
243template specialization, so the usage is like a simple function call.
244\skip std
245\until ;
246
247Most 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.
248
249If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
250(coming soon) and will use maps hardly.
251Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
252
253Here we discuss some advanced map techniques. Like writing your own maps or how to
254extend/modify a maps functionality with adaptors.
255
256\section custom_maps Writing Custom ReadMap
257\subsection custom_read_maps Readable Maps
258
259Readable maps are very frequently used as the input of an
260algorithm.  For this purpose the most straightforward way is the use of the
261default maps provided by LEMON's digraph structures.
262Very often however, it is more
263convenient and/or more efficient to write your own readable map.
264
265You can find some examples below. In these examples \c Digraph is the
266type of the particular digraph structure you use.
267
268
269This simple map assigns \f$\pi\f$ to each arc.
270
271\code
272struct MyMap
273{
274  typedef double Value;
275  typedef Digraph::Arc Key;
276  double operator[](const Key &e) const { return PI;}
277};
278\endcode
279
280An alternative way to define maps is to use MapBase
281
282\code
283struct MyMap : public MapBase<Digraph::Arc,double>
284{
285  Value operator[](const Key& e) const { return PI;}
286};
287\endcode
288
289Here is a bit more complex example.
290It provides a length function obtained
291from a base length function shifted by a potential difference.
292
293\code
294class ReducedLengthMap  : public MapBase<Digraph::Arc,double>
295{
296  const Digraph &g;
297  const Digraph::ArcMap<double> &orig_len;
298  const Digraph::NodeMap<double> &pot;
299 
300public:
301  Value operator[](Key e) const {
302    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
303  }
304 
305  ReducedLengthMap(const Digraph &_g,
306                   const Digraph::ArcMap &_o,
307                   const Digraph::NodeMap &_p)
308    : g(_g), orig_len(_o), pot(_p) {};
309};
310\endcode
311
312Then, you can call e.g. Dijkstra algoritm on this map like this:
313\code
314  ...
315  ReducedLengthMap rm(g,len,pot);
316  Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
317  dij.run(s);
318  ...
319\endcode
320
321
322[SEC]sec_map_concepts[SEC] Map Concepts
323
324...
325
326
327[SEC]sec_own_maps[SEC] Creating Own Maps
328
329...
330
331[SEC]sec_map_adaptors[SEC] Map Adaptors
332
333See \ref map_adaptors in the reference manual.
334
335
336[SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
337
338The basic functionality of the algorithms can be highly extended using
339special purpose map types for their internal data structures.
340For example, the \ref Dijkstra class stores a
341ef ProcessedMap,
342which has to be a writable node map of \ref bool value type.
343The assigned value of each node is set to \ref true when the node is
344processed, i.e., its actual distance is found.
345Applying a special map, \ref LoggerBoolMap, the processed order of
346the nodes can easily be stored in a standard container.
347
348Such specific map types can be passed to the algorithms using the technique of
349named template parameters. Similarly to the named function parameters,
350they allow specifying any subset of the parameters and in arbitrary order.
351
352\code
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);
359
360  Container container;
361  InsertIterator iterator(container);
362  ProcessedMap processed(iterator);
363
364  dijkstra.processedMap(processed).run(s);
365\endcode
366
367The function-type interfaces are considerably simpler, but they can be
368used in almost all practical cases. Surprisingly, even the above example
369can also be implemented using the \ref dijkstra() function and
370named parameters, as follows.
371Note that the function-type interface has the major advantage
372that temporary objects can be passed as parameters.
373
374\code
375  vector<ListDigraph::Node> process_order;
376  dijkstra(g, length)
377    .processedMap(loggerBoolMap(back_inserter(process_order)))
378    .run(s);
379\endcode
380
381LEMON also contains visitor based algorithm classes for
382BFS and DFS.
383
384Skeleton visitor classes are defined for both BFS and DFS, the concrete
385implementations can be inherited from them.
386\code
387  template <typename GR>
388  struct DfsVisitor {
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) {}
396  };
397\endcode
398
399In the following example, the \ref discover()} and \code{examine()
400events are processed and the DFS tree is stored in an arc map.
401The values of this map indicate whether the corresponding arc
402reaches a new node or its target node is already reached.
403\code
404  template <typename GR>
405  struct TreeVisitor : public DfsVisitor<GR> {
406    TreeVisitor(typename GR::ArcMap<bool>& tree)
407      : _tree(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;
413  };
414\endcode
415
416
417[TRAILER]
418*/
419}
Note: See TracBrowser for help on using the repository browser.