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