COIN-OR::LEMON - Graph Library

source: lemon-tutorial/maps.dox

Last change on this file was 58:10b6a5b7d4c0, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Improve Algorithms section (it is still under construction)

File size: 15.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
39Maps play a central role in LEMON. As their name suggests, they map a
40certain 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:
42
43\code
44  typedef Arc Key;
45  typedef double Value;
46\endcode
47
48A map can be
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").
52There also exists a special type of
53ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
54In addition that you can
55read and write the values of a key, a reference map
56can also give you a reference to the
57value belonging to a key, so you have a direct access to the memory address
58where it is stored.
59
60Each digraph structure in LEMON provides two standard map templates called
61\c ArcMap and \c NodeMap. Both are reference maps and you can easily
62assign data to the nodes and to the arcs of the digraph. For example if you
63have a digraph \c g defined as
64\code
65  ListDigraph g;
66\endcode
67and you want to assign a floating point value to each arc, you can do
68it like this.
69\code
70  ListDigraph::ArcMap<double> length(g);
71\endcode
72Note that you must give the underlying digraph to the constructor.
73
74The value of a readable map can be obtained by <tt>operator[]</tt>.
75\code
76  d=length[e];
77\endcode
78where \c e is an instance of \c ListDigraph::Arc.
79(Or anything else
80that converts to \c ListDigraph::Arc, like  \c ListDigraph::ArcIt or
81\c ListDigraph::OutArcIt etc.)
82
83There are two ways to assign a new value to a key
84
85- In case of a <em>reference map</em> <tt>operator[]</tt>
86gives you a reference to the
87value, thus you can use this.
88\code
89  length[e]=3.5;
90\endcode
91- <em>Writable maps</em> have
92a member function \c set(Key,const Value &)
93for this purpose.
94\code
95  length.set(e,3.5);
96\endcode
97
98The first case is more comfortable and if you store complex structures in your
99map, it might be more efficient. However, there are writable but
100not reference maps, so if you want to write a generic algorithm, you should
101insist on the second way.
102
103\section how-to-write-your-own-map How to Write Your Own Maps
104
105\subsection read-maps Readable Maps
106
107Readable maps are very frequently used as the input of an
108algorithm.  For this purpose the most straightforward way is the use of the
109default maps provided by LEMON's digraph structures.
110Very often however, it is more
111convenient and/or more efficient to write your own readable map.
112
113You can find some examples below. In these examples \c Digraph is the
114type of the particular digraph structure you use.
115
116
117This simple map assigns \f$\pi\f$ to each arc.
118
119\code
120struct MyMap
121{
122  typedef double Value;
123  typedef Digraph::Arc Key;
124  double operator[](Key e) const { return PI;}
125};
126\endcode
127
128An alternative way to define maps is to use \c MapBase
129
130\code
131struct MyMap : public MapBase<Digraph::Arc,double>
132{
133  Value operator[](Key e) const { return PI;}
134};
135\endcode
136
137Here is a bit more complex example.
138It provides a length function obtained
139from a base length function shifted by a potential difference.
140
141\code
142class ReducedLengthMap  : public MapBase<Digraph::Arc,double>
143{
144  const Digraph &g;
145  const Digraph::ArcMap<double> &orig_len;
146  const Digraph::NodeMap<double> &pot;
147 
148public:
149  Value operator[](Key e) const {
150    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
151  }
152 
153  ReducedLengthMap(const Digraph &_g,
154                   const Digraph::ArcMap &_o,
155                   const Digraph::NodeMap &_p)
156    : g(_g), orig_len(_o), pot(_p) {};
157};
158\endcode
159
160Then, you can call e.g. Dijkstra algoritm on this map like this:
161\code
162  ...
163  ReducedLengthMap rm(g,len,pot);
164  Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
165  dij.run(s);
166  ...
167\endcode
168
169
170In the previous section we discussed digraph topology. That is the skeleton a complex
171digraph represented data-set needs. But how to assign the data itself to that skeleton?<br>
172Here come the \b maps in.
173
174\section maps_intro Introduction to maps
175Maps play a central role in LEMON. As their name suggests, they map a certain range of <i>keys</i> to certain <i>values</i>.
176In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:
177\code
178  typedef Arc Key;
179  typedef double Value;
180\endcode
181(Except matrix maps, they have two key types.)
182
183To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes.
184<ul>
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
187</li>
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
190</li>
191<li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
192readable and writable. It is delivered from them.
193</li>
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
196providing you constant or non-constant reference to the value belonging to a key,
197so you have a direct access to the memory address where it is stored.
198</li>
199<li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
200The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap",
201\ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
202\ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
203</li>
204</ul>
205
206\section maps_graph Digraphs' maps
207Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
208satisfying the \ref DigraphMap concept.
209If you want to assign data to nodes, just declare a NodeMap with the corresponding
210type. As an example, think of a arc-weighted digraph.
211\code ListDigraph::ArcMap<int>  weight(digraph); \endcode
212You can see that the map needs the digraph whose arcs will mapped, but nothing more.
213
214If the digraph class is extendable or erasable the map will automatically follow
215the changes you make. If a new node is added a default value is mapped to it.
216You can define the default value by passing a second argument to the map's constructor.
217\code ListDigraph::ArcMap<int>  weight(digraph, 13); \endcode
218But keep in mind that \c VALUE has to have copy constructor.
219
220Of course \c VALUE can be a rather complex type.
221
222For 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
224\skip template
225\until }
226The 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
228this code. See \ref SubDigraph techniques - that's LEMON's true potential.)
229
230And the usage is simpler than the declaration suggests. The compiler deduces the
231template specialization, so the usage is like a simple function call.
232\skip std
233\until ;
234
235Most 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.
236
237If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
238(coming soon) and will use maps hardly.
239Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
240
241Here we discuss some advanced map techniques. Like writing your own maps or how to
242extend/modify a maps functionality with adaptors.
243
244\section custom_maps Writing Custom ReadMap
245\subsection custom_read_maps Readable Maps
246
247Readable maps are very frequently used as the input of an
248algorithm.  For this purpose the most straightforward way is the use of the
249default maps provided by LEMON's digraph structures.
250Very often however, it is more
251convenient and/or more efficient to write your own readable map.
252
253You can find some examples below. In these examples \c Digraph is the
254type of the particular digraph structure you use.
255
256
257This simple map assigns \f$\pi\f$ to each arc.
258
259\code
260struct MyMap
261{
262  typedef double Value;
263  typedef Digraph::Arc Key;
264  double operator[](const Key &e) const { return PI;}
265};
266\endcode
267
268An alternative way to define maps is to use MapBase
269
270\code
271struct MyMap : public MapBase<Digraph::Arc,double>
272{
273  Value operator[](const Key& e) const { return PI;}
274};
275\endcode
276
277Here is a bit more complex example.
278It provides a length function obtained
279from a base length function shifted by a potential difference.
280
281\code
282class ReducedLengthMap  : public MapBase<Digraph::Arc,double>
283{
284  const Digraph &g;
285  const Digraph::ArcMap<double> &orig_len;
286  const Digraph::NodeMap<double> &pot;
287 
288public:
289  Value operator[](Key e) const {
290    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
291  }
292 
293  ReducedLengthMap(const Digraph &_g,
294                   const Digraph::ArcMap &_o,
295                   const Digraph::NodeMap &_p)
296    : g(_g), orig_len(_o), pot(_p) {};
297};
298\endcode
299
300Then, you can call e.g. Dijkstra algoritm on this map like this:
301\code
302  ...
303  ReducedLengthMap rm(g,len,pot);
304  Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
305  dij.run(s);
306  ...
307\endcode
308
309
310[SEC]sec_map_concepts[SEC] Map Concepts
311
312...
313
314
315[SEC]sec_own_maps[SEC] Creating Own Maps
316
317...
318
319[SEC]sec_map_adaptors[SEC] Map Adaptors
320
321See \ref map_adaptors in the reference manual.
322
323
324[SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
325
326
327The basic functionality of the algorithms can be highly extended using
328special purpose map types for their internal data structures.
329For example, the \ref Dijkstra class stores a
330ef ProcessedMap,
331which has to be a writable node map of \ref bool value type.
332The assigned value of each node is set to \ref true when the node is
333processed, i.e., its actual distance is found.
334Applying a special map, \ref LoggerBoolMap, the processed order of
335the nodes can easily be stored in a standard container.
336
337Such specific map types can be passed to the algorithms using the technique of
338named template parameters. Similarly to the named function parameters,
339they allow specifying any subset of the parameters and in arbitrary order.
340
341Let us suppose that we have a traffic network stored in a LEMON digraph
342structure with two arc maps \c length and \c speed, which
343denote the physical length of each arc and the maximum (or average)
344speed that can be achieved on the corresponding road-section,
345respectively. If we are interested in the best traveling times,
346the following code can be used.
347
348\code
349  dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
350\endcode
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
381Let us see a bit more complex example to demonstrate Dfs's capabilities.
382
383We will see a program, which solves the problem of <b>topological ordering</b>.
384We need to know in which order we should put on our clothes. The program will do the following:
385<ol>
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.
389</ol>
390
391\dontinclude topological_ordering.cc
392First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
393will be done through it.
394\skip MyOrdererMap
395\until };
396The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
397we need to do is insert the key - that is the node whose processing just finished - into the beginning
398of the list.<br>
399Although we implemented this needed helper class ourselves it was not necessary.
400The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
401what we needed. To be correct it's more general - and it's all in \c LEMON. But
402we wanted to show you, how easy is to add additional functionality.
403
404First we declare the needed data structures: the digraph and a map to store the nodes' label.
405\skip ListDigraph
406\until label
407
408Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
409ordering.
410\skip belt
411\until trousers
412We label them...
413\skip label
414\until trousers
415Then add arcs which represent the precedences between those items.
416\skip trousers, belt
417\until );
418
419See how easy is to access the internal information of this algorithm trough maps.
420We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
421\skip Dfs
422\until run
423
424And now comes the third part. Write out the list in reverse order. But the list was
425composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
426\skip std
427\until endl
428
429The program is to be found in the \ref demo directory: \ref topological_ordering.cc
430
431LEMON also contains visitor based algorithm classes for
432BFS and DFS.
433
434Skeleton visitor classes are defined for both BFS and DFS, the concrete
435implementations can be inherited from them.
436\code
437  template <typename GR>
438  struct DfsVisitor {
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) {}
446  };
447\endcode
448
449In the following example, the \ref discover()} and \code{examine()
450events are processed and the DFS tree is stored in an arc map.
451The values of this map indicate whether the corresponding arc
452reaches a new node or its target node is already reached.
453\code
454  template <typename GR>
455  struct TreeVisitor : public DfsVisitor<GR> {
456    TreeVisitor(typename GR::ArcMap<bool>& tree)
457      : _tree(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;
463  };
464\endcode
465
466
467[TRAILER]
468*/
469}
Note: See TracBrowser for help on using the repository browser.