1.1 --- a/maps.dox Mon Feb 22 02:00:51 2010 +0100
1.2 +++ b/maps.dox Mon Feb 22 02:03:25 2010 +0100
1.3 @@ -22,6 +22,301 @@
1.4
1.5 \todo This page is under construction.
1.6
1.7 +\todo The following contents are ported from the LEMON 0.x tutorial,
1.8 +thus they have to thouroughly revised, reorganized and reworked.
1.9 +
1.10 +The LEMON maps are not only just storage classes, but also
1.11 +they are %concepts of any key--value based data access.
1.12 +Beside the standard digraph maps, LEMON contains several "lightweight"
1.13 +\e map \e adaptor \e classes, which perform various operations on the
1.14 +data of the adapted maps when their access operations are called,
1.15 +but without actually copying or modifying the original storage.
1.16 +These classes also conform to the map %concepts, thus they can be used
1.17 +like standard LEMON maps.
1.18 +
1.19 +Let us suppose that we have a traffic network stored in a LEMON digraph
1.20 +structure with two arc maps \c length and \c speed, which
1.21 +denote the physical length of each arc and the maximum (or average)
1.22 +speed that can be achieved on the corresponding road-section,
1.23 +respectively. If we are interested in the best traveling times,
1.24 +the following code can be used.
1.25 +
1.26 +\code
1.27 + dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
1.28 +\endcode
1.29 +
1.30 +
1.31 +Maps play a central role in LEMON. As their name suggests, they map a
1.32 +certain range of \e keys to certain \e values. Each map has two
1.33 +<tt>typedef</tt>'s to determine the types of keys and values, like this:
1.34 +
1.35 +\code
1.36 + typedef Arc Key;
1.37 + typedef double Value;
1.38 +\endcode
1.39 +
1.40 +A map can be
1.41 +\e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
1.42 +\e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
1.43 +(\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
1.44 +There also exists a special type of
1.45 +ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
1.46 +In addition that you can
1.47 +read and write the values of a key, a reference map
1.48 +can also give you a reference to the
1.49 +value belonging to a key, so you have a direct access to the memory address
1.50 +where it is stored.
1.51 +
1.52 +Each digraph structure in LEMON provides two standard map templates called
1.53 +\c ArcMap and \c NodeMap. Both are reference maps and you can easily
1.54 +assign data to the nodes and to the arcs of the digraph. For example if you
1.55 +have a digraph \c g defined as
1.56 +\code
1.57 + ListDigraph g;
1.58 +\endcode
1.59 +and you want to assign a floating point value to each arc, you can do
1.60 +it like this.
1.61 +\code
1.62 + ListDigraph::ArcMap<double> length(g);
1.63 +\endcode
1.64 +Note that you must give the underlying digraph to the constructor.
1.65 +
1.66 +The value of a readable map can be obtained by <tt>operator[]</tt>.
1.67 +\code
1.68 + d=length[e];
1.69 +\endcode
1.70 +where \c e is an instance of \c ListDigraph::Arc.
1.71 +(Or anything else
1.72 +that converts to \c ListDigraph::Arc, like \c ListDigraph::ArcIt or
1.73 +\c ListDigraph::OutArcIt etc.)
1.74 +
1.75 +There are two ways to assign a new value to a key
1.76 +
1.77 +- In case of a <em>reference map</em> <tt>operator[]</tt>
1.78 +gives you a reference to the
1.79 +value, thus you can use this.
1.80 +\code
1.81 + length[e]=3.5;
1.82 +\endcode
1.83 +- <em>Writable maps</em> have
1.84 +a member function \c set(Key,const Value &)
1.85 +for this purpose.
1.86 +\code
1.87 + length.set(e,3.5);
1.88 +\endcode
1.89 +
1.90 +The first case is more comfortable and if you store complex structures in your
1.91 +map, it might be more efficient. However, there are writable but
1.92 +not reference maps, so if you want to write a generic algorithm, you should
1.93 +insist on the second way.
1.94 +
1.95 +\section how-to-write-your-own-map How to Write Your Own Maps
1.96 +
1.97 +\subsection read-maps Readable Maps
1.98 +
1.99 +Readable maps are very frequently used as the input of an
1.100 +algorithm. For this purpose the most straightforward way is the use of the
1.101 +default maps provided by LEMON's digraph structures.
1.102 +Very often however, it is more
1.103 +convenient and/or more efficient to write your own readable map.
1.104 +
1.105 +You can find some examples below. In these examples \c Digraph is the
1.106 +type of the particular digraph structure you use.
1.107 +
1.108 +
1.109 +This simple map assigns \f$\pi\f$ to each arc.
1.110 +
1.111 +\code
1.112 +struct MyMap
1.113 +{
1.114 + typedef double Value;
1.115 + typedef Digraph::Arc Key;
1.116 + double operator[](Key e) const { return PI;}
1.117 +};
1.118 +\endcode
1.119 +
1.120 +An alternative way to define maps is to use \c MapBase
1.121 +
1.122 +\code
1.123 +struct MyMap : public MapBase<Digraph::Arc,double>
1.124 +{
1.125 + Value operator[](Key e) const { return PI;}
1.126 +};
1.127 +\endcode
1.128 +
1.129 +Here is a bit more complex example.
1.130 +It provides a length function obtained
1.131 +from a base length function shifted by a potential difference.
1.132 +
1.133 +\code
1.134 +class ReducedLengthMap : public MapBase<Digraph::Arc,double>
1.135 +{
1.136 + const Digraph &g;
1.137 + const Digraph::ArcMap<double> &orig_len;
1.138 + const Digraph::NodeMap<double> &pot;
1.139 +
1.140 +public:
1.141 + Value operator[](Key e) const {
1.142 + return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
1.143 + }
1.144 +
1.145 + ReducedLengthMap(const Digraph &_g,
1.146 + const Digraph::ArcMap &_o,
1.147 + const Digraph::NodeMap &_p)
1.148 + : g(_g), orig_len(_o), pot(_p) {};
1.149 +};
1.150 +\endcode
1.151 +
1.152 +Then, you can call e.g. Dijkstra algoritm on this map like this:
1.153 +\code
1.154 + ...
1.155 + ReducedLengthMap rm(g,len,pot);
1.156 + Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
1.157 + dij.run(s);
1.158 + ...
1.159 +\endcode
1.160 +
1.161 +
1.162 +In the previous section we discussed digraph topology. That is the skeleton a complex
1.163 +digraph represented data-set needs. But how to assign the data itself to that skeleton?<br>
1.164 +Here come the \b maps in.
1.165 +
1.166 +\section maps_intro Introduction to maps
1.167 +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>.
1.168 +In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:
1.169 +\code
1.170 + typedef Arc Key;
1.171 + typedef double Value;
1.172 +\endcode
1.173 +(Except matrix maps, they have two key types.)
1.174 +
1.175 +To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes.
1.176 +<ul>
1.177 +<li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
1.178 +\code value_typed_variable = map_instance[key_value]; \endcode
1.179 +</li>
1.180 +<li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
1.181 +\code map_instance.set(key_value, value_typed_expression); \endcode
1.182 +</li>
1.183 +<li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
1.184 +readable and writable. It is delivered from them.
1.185 +</li>
1.186 +<li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
1.187 +<i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to
1.188 +providing you constant or non-constant reference to the value belonging to a key,
1.189 +so you have a direct access to the memory address where it is stored.
1.190 +</li>
1.191 +<li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
1.192 +The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap",
1.193 +\ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
1.194 +\ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
1.195 +</li>
1.196 +</ul>
1.197 +
1.198 +\section maps_graph Digraphs' maps
1.199 +Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
1.200 +satisfying the \ref DigraphMap concept.
1.201 +If you want to assign data to nodes, just declare a NodeMap with the corresponding
1.202 +type. As an example, think of a arc-weighted digraph.
1.203 +\code ListDigraph::ArcMap<int> weight(digraph); \endcode
1.204 +You can see that the map needs the digraph whose arcs will mapped, but nothing more.
1.205 +
1.206 +If the digraph class is extendable or erasable the map will automatically follow
1.207 +the changes you make. If a new node is added a default value is mapped to it.
1.208 +You can define the default value by passing a second argument to the map's constructor.
1.209 +\code ListDigraph::ArcMap<int> weight(digraph, 13); \endcode
1.210 +But keep in mind that \c VALUE has to have copy constructor.
1.211 +
1.212 +Of course \c VALUE can be a rather complex type.
1.213 +
1.214 +For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
1.215 +\dontinclude maps_summary.cc
1.216 +\skip template
1.217 +\until }
1.218 +The task is simple. We need the summary of some kind of data assigned to a digraph's nodes.
1.219 +(Whit a little trick the summary can be calculated only to a sub-digraph without changing
1.220 +this code. See \ref SubDigraph techniques - that's LEMON's true potential.)
1.221 +
1.222 +And the usage is simpler than the declaration suggests. The compiler deduces the
1.223 +template specialization, so the usage is like a simple function call.
1.224 +\skip std
1.225 +\until ;
1.226 +
1.227 +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.
1.228 +
1.229 +If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
1.230 +(coming soon) and will use maps hardly.
1.231 +Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
1.232 +
1.233 +Here we discuss some advanced map techniques. Like writing your own maps or how to
1.234 +extend/modify a maps functionality with adaptors.
1.235 +
1.236 +\section custom_maps Writing Custom ReadMap
1.237 +\subsection custom_read_maps Readable Maps
1.238 +
1.239 +Readable maps are very frequently used as the input of an
1.240 +algorithm. For this purpose the most straightforward way is the use of the
1.241 +default maps provided by LEMON's digraph structures.
1.242 +Very often however, it is more
1.243 +convenient and/or more efficient to write your own readable map.
1.244 +
1.245 +You can find some examples below. In these examples \c Digraph is the
1.246 +type of the particular digraph structure you use.
1.247 +
1.248 +
1.249 +This simple map assigns \f$\pi\f$ to each arc.
1.250 +
1.251 +\code
1.252 +struct MyMap
1.253 +{
1.254 + typedef double Value;
1.255 + typedef Digraph::Arc Key;
1.256 + double operator[](const Key &e) const { return PI;}
1.257 +};
1.258 +\endcode
1.259 +
1.260 +An alternative way to define maps is to use MapBase
1.261 +
1.262 +\code
1.263 +struct MyMap : public MapBase<Digraph::Arc,double>
1.264 +{
1.265 + Value operator[](const Key& e) const { return PI;}
1.266 +};
1.267 +\endcode
1.268 +
1.269 +Here is a bit more complex example.
1.270 +It provides a length function obtained
1.271 +from a base length function shifted by a potential difference.
1.272 +
1.273 +\code
1.274 +class ReducedLengthMap : public MapBase<Digraph::Arc,double>
1.275 +{
1.276 + const Digraph &g;
1.277 + const Digraph::ArcMap<double> &orig_len;
1.278 + const Digraph::NodeMap<double> &pot;
1.279 +
1.280 +public:
1.281 + Value operator[](Key e) const {
1.282 + return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
1.283 + }
1.284 +
1.285 + ReducedLengthMap(const Digraph &_g,
1.286 + const Digraph::ArcMap &_o,
1.287 + const Digraph::NodeMap &_p)
1.288 + : g(_g), orig_len(_o), pot(_p) {};
1.289 +};
1.290 +\endcode
1.291 +
1.292 +Then, you can call e.g. Dijkstra algoritm on this map like this:
1.293 +\code
1.294 + ...
1.295 + ReducedLengthMap rm(g,len,pot);
1.296 + Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
1.297 + dij.run(s);
1.298 + ...
1.299 +\endcode
1.300 +
1.301 +
1.302 [SEC]sec_map_concepts[SEC] Map Concepts
1.303
1.304 ...
1.305 @@ -38,7 +333,84 @@
1.306
1.307 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
1.308
1.309 -...
1.310 +The basic functionality of the algorithms can be highly extended using
1.311 +special purpose map types for their internal data structures.
1.312 +For example, the \ref Dijkstra class stores a
1.313 +ef ProcessedMap,
1.314 +which has to be a writable node map of \ref bool value type.
1.315 +The assigned value of each node is set to \ref true when the node is
1.316 +processed, i.e., its actual distance is found.
1.317 +Applying a special map, \ref LoggerBoolMap, the processed order of
1.318 +the nodes can easily be stored in a standard container.
1.319 +
1.320 +Such specific map types can be passed to the algorithms using the technique of
1.321 +named template parameters. Similarly to the named function parameters,
1.322 +they allow specifying any subset of the parameters and in arbitrary order.
1.323 +
1.324 +\code
1.325 + typedef vector<ListDigraph::Node> Container;
1.326 + typedef back_insert_iterator<Container> InsertIterator;
1.327 + typedef LoggerBoolMap<InsertIterator> ProcessedMap;
1.328 + Dijkstra<ListDigraph>
1.329 + ::SetProcessedMap<ProcessedMap>
1.330 + ::Create dijktra(g, length);
1.331 +
1.332 + Container container;
1.333 + InsertIterator iterator(container);
1.334 + ProcessedMap processed(iterator);
1.335 +
1.336 + dijkstra.processedMap(processed).run(s);
1.337 +\endcode
1.338 +
1.339 +The function-type interfaces are considerably simpler, but they can be
1.340 +used in almost all practical cases. Surprisingly, even the above example
1.341 +can also be implemented using the \ref dijkstra() function and
1.342 +named parameters, as follows.
1.343 +Note that the function-type interface has the major advantage
1.344 +that temporary objects can be passed as parameters.
1.345 +
1.346 +\code
1.347 + vector<ListDigraph::Node> process_order;
1.348 + dijkstra(g, length)
1.349 + .processedMap(loggerBoolMap(back_inserter(process_order)))
1.350 + .run(s);
1.351 +\endcode
1.352 +
1.353 +LEMON also contains visitor based algorithm classes for
1.354 +BFS and DFS.
1.355 +
1.356 +Skeleton visitor classes are defined for both BFS and DFS, the concrete
1.357 +implementations can be inherited from them.
1.358 +\code
1.359 + template <typename GR>
1.360 + struct DfsVisitor {
1.361 + void start(const typename GR::Node& node) {}
1.362 + void stop(const typename GR::Node& node) {}
1.363 + void reach(const typename GR::Node& node) {}
1.364 + void leave(const typename GR::Node& node) {}
1.365 + void discover(const typename GR::Arc& arc) {}
1.366 + void examine(const typename GR::Arc& arc) {}
1.367 + void backtrack(const typename GR::Arc& arc) {}
1.368 + };
1.369 +\endcode
1.370 +
1.371 +In the following example, the \ref discover()} and \code{examine()
1.372 +events are processed and the DFS tree is stored in an arc map.
1.373 +The values of this map indicate whether the corresponding arc
1.374 +reaches a new node or its target node is already reached.
1.375 +\code
1.376 + template <typename GR>
1.377 + struct TreeVisitor : public DfsVisitor<GR> {
1.378 + TreeVisitor(typename GR::ArcMap<bool>& tree)
1.379 + : _tree(tree) {}
1.380 + void discover(const typename GR::Arc& arc)
1.381 + { _tree[arc] = true; }
1.382 + void examine(const typename GR::Arc& arc)
1.383 + { _tree[arc] = false; }
1.384 + typename GR::ArcMap<bool>& _tree;
1.385 + };
1.386 +\endcode
1.387 +
1.388
1.389 [TRAILER]
1.390 */