kpeter@46: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@46:  *
kpeter@46:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@46:  *
kpeter@46:  * Copyright (C) 2003-2010
kpeter@46:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@46:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@46:  *
kpeter@46:  * Permission to use, modify and distribute this software is granted
kpeter@46:  * provided that this copyright notice appears in all copies. For
kpeter@46:  * precise terms see the accompanying LICENSE file.
kpeter@46:  *
kpeter@46:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@46:  * express or implied, and with no claim as to its suitability for any
kpeter@46:  * purpose.
kpeter@46:  *
kpeter@46:  */
kpeter@46: 
kpeter@46: namespace lemon {
kpeter@46: /**
kpeter@46: [PAGE]sec_maps[PAGE] Maps
kpeter@46: 
kpeter@46: \todo This page is under construction.
kpeter@46: 
kpeter@49: \todo The following contents are ported from the LEMON 0.x tutorial,
kpeter@49: thus they have to thouroughly revised, reorganized and reworked.
kpeter@49: 
kpeter@49: The LEMON maps are not only just storage classes, but also
kpeter@49: they are %concepts of any key--value based data access.
kpeter@49: Beside the standard digraph maps, LEMON contains several "lightweight"
kpeter@49: \e map \e adaptor \e classes, which perform various operations on the
kpeter@49: data of the adapted maps when their access operations are called,
kpeter@49: but without actually copying or modifying the original storage.
kpeter@49: These classes also conform to the map %concepts, thus they can be used
kpeter@49: like standard LEMON maps.
kpeter@49: 
kpeter@49: Let us suppose that we have a traffic network stored in a LEMON digraph
kpeter@49: structure with two arc maps \c length and \c speed, which
kpeter@49: denote the physical length of each arc and the maximum (or average)
kpeter@49: speed that can be achieved on the corresponding road-section,
kpeter@49: respectively. If we are interested in the best traveling times,
kpeter@49: the following code can be used.
kpeter@49: 
kpeter@49: \code
kpeter@49:   dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
kpeter@49: \endcode
kpeter@49: 
kpeter@49: 
kpeter@49: Maps play a central role in LEMON. As their name suggests, they map a
kpeter@49: certain range of \e keys to certain \e values. Each map has two
kpeter@49: <tt>typedef</tt>'s to determine the types of keys and values, like this:
kpeter@49: 
kpeter@49: \code
kpeter@49:   typedef Arc Key;
kpeter@49:   typedef double Value;
kpeter@49: \endcode
kpeter@49: 
kpeter@49: A map can be 
kpeter@49: \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
kpeter@49: \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
kpeter@49: (\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
kpeter@49: There also exists a special type of
kpeter@49: ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
kpeter@49: In addition that you can
kpeter@49: read and write the values of a key, a reference map
kpeter@49: can also give you a reference to the
kpeter@49: value belonging to a key, so you have a direct access to the memory address
kpeter@49: where it is stored.
kpeter@49: 
kpeter@49: Each digraph structure in LEMON provides two standard map templates called
kpeter@49: \c ArcMap and \c NodeMap. Both are reference maps and you can easily
kpeter@49: assign data to the nodes and to the arcs of the digraph. For example if you
kpeter@49: have a digraph \c g defined as
kpeter@49: \code
kpeter@49:   ListDigraph g;
kpeter@49: \endcode
kpeter@49: and you want to assign a floating point value to each arc, you can do
kpeter@49: it like this.
kpeter@49: \code
kpeter@49:   ListDigraph::ArcMap<double> length(g);
kpeter@49: \endcode
kpeter@49: Note that you must give the underlying digraph to the constructor.
kpeter@49: 
kpeter@49: The value of a readable map can be obtained by <tt>operator[]</tt>.
kpeter@49: \code
kpeter@49:   d=length[e];
kpeter@49: \endcode
kpeter@49: where \c e is an instance of \c ListDigraph::Arc.
kpeter@49: (Or anything else
kpeter@49: that converts to \c ListDigraph::Arc, like  \c ListDigraph::ArcIt or
kpeter@49: \c ListDigraph::OutArcIt etc.)
kpeter@49: 
kpeter@49: There are two ways to assign a new value to a key
kpeter@49: 
kpeter@49: - In case of a <em>reference map</em> <tt>operator[]</tt>
kpeter@49: gives you a reference to the
kpeter@49: value, thus you can use this.
kpeter@49: \code
kpeter@49:   length[e]=3.5;
kpeter@49: \endcode
kpeter@49: - <em>Writable maps</em> have
kpeter@49: a member function \c set(Key,const Value &)
kpeter@49: for this purpose.
kpeter@49: \code
kpeter@49:   length.set(e,3.5);
kpeter@49: \endcode
kpeter@49: 
kpeter@49: The first case is more comfortable and if you store complex structures in your
kpeter@49: map, it might be more efficient. However, there are writable but
kpeter@49: not reference maps, so if you want to write a generic algorithm, you should
kpeter@49: insist on the second way.
kpeter@49: 
kpeter@49: \section how-to-write-your-own-map How to Write Your Own Maps
kpeter@49: 
kpeter@49: \subsection read-maps Readable Maps
kpeter@49: 
kpeter@49: Readable maps are very frequently used as the input of an
kpeter@49: algorithm.  For this purpose the most straightforward way is the use of the
kpeter@49: default maps provided by LEMON's digraph structures.
kpeter@49: Very often however, it is more
kpeter@49: convenient and/or more efficient to write your own readable map.
kpeter@49: 
kpeter@49: You can find some examples below. In these examples \c Digraph is the
kpeter@49: type of the particular digraph structure you use.
kpeter@49: 
kpeter@49: 
kpeter@49: This simple map assigns \f$\pi\f$ to each arc.
kpeter@49: 
kpeter@49: \code
kpeter@49: struct MyMap 
kpeter@49: {
kpeter@49:   typedef double Value;
kpeter@49:   typedef Digraph::Arc Key;
kpeter@49:   double operator[](Key e) const { return PI;}
kpeter@49: };
kpeter@49: \endcode
kpeter@49: 
kpeter@49: An alternative way to define maps is to use \c MapBase
kpeter@49: 
kpeter@49: \code
kpeter@49: struct MyMap : public MapBase<Digraph::Arc,double>
kpeter@49: {
kpeter@49:   Value operator[](Key e) const { return PI;}
kpeter@49: };
kpeter@49: \endcode
kpeter@49: 
kpeter@49: Here is a bit more complex example.
kpeter@49: It provides a length function obtained
kpeter@49: from a base length function shifted by a potential difference.
kpeter@49: 
kpeter@49: \code
kpeter@49: class ReducedLengthMap  : public MapBase<Digraph::Arc,double>
kpeter@49: {
kpeter@49:   const Digraph &g;
kpeter@49:   const Digraph::ArcMap<double> &orig_len;
kpeter@49:   const Digraph::NodeMap<double> &pot;
kpeter@49:   
kpeter@49: public:
kpeter@49:   Value operator[](Key e) const {
kpeter@49:     return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
kpeter@49:   }
kpeter@49:   
kpeter@49:   ReducedLengthMap(const Digraph &_g,
kpeter@49:                    const Digraph::ArcMap &_o,
kpeter@49:                    const Digraph::NodeMap &_p)
kpeter@49:     : g(_g), orig_len(_o), pot(_p) {};
kpeter@49: };
kpeter@49: \endcode
kpeter@49: 
kpeter@49: Then, you can call e.g. Dijkstra algoritm on this map like this:
kpeter@49: \code
kpeter@49:   ...
kpeter@49:   ReducedLengthMap rm(g,len,pot);
kpeter@49:   Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
kpeter@49:   dij.run(s);
kpeter@49:   ...
kpeter@49: \endcode
kpeter@49: 
kpeter@49: 
kpeter@49: In the previous section we discussed digraph topology. That is the skeleton a complex
kpeter@49: digraph represented data-set needs. But how to assign the data itself to that skeleton?<br>
kpeter@49: Here come the \b maps in.
kpeter@49: 
kpeter@49: \section maps_intro Introduction to maps
kpeter@49: 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: 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: \code
kpeter@49:   typedef Arc Key;
kpeter@49:   typedef double Value;
kpeter@49: \endcode
kpeter@49: (Except matrix maps, they have two key types.)
kpeter@49: 
kpeter@49: To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes.
kpeter@49: <ul>
kpeter@49: <li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
kpeter@49: \code value_typed_variable = map_instance[key_value]; \endcode
kpeter@49: </li>
kpeter@49: <li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
kpeter@49: \code map_instance.set(key_value, value_typed_expression); \endcode
kpeter@49: </li>
kpeter@49: <li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
kpeter@49: readable and writable. It is delivered from them.
kpeter@49: </li>
kpeter@49: <li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
kpeter@49: <i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to
kpeter@49: providing you constant or non-constant reference to the value belonging to a key,
kpeter@49: so you have a direct access to the memory address where it is stored.
kpeter@49: </li>
kpeter@49: <li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
kpeter@49: The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap", 
kpeter@49: \ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
kpeter@49: \ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
kpeter@49: </li>
kpeter@49: </ul>
kpeter@49: 
kpeter@49: \section maps_graph Digraphs' maps
kpeter@49: Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
kpeter@49: satisfying the \ref DigraphMap concept.
kpeter@49: If you want to assign data to nodes, just declare a NodeMap with the corresponding
kpeter@49: type. As an example, think of a arc-weighted digraph.
kpeter@49: \code ListDigraph::ArcMap<int>  weight(digraph); \endcode
kpeter@49: You can see that the map needs the digraph whose arcs will mapped, but nothing more.
kpeter@49: 
kpeter@49: If the digraph class is extendable or erasable the map will automatically follow
kpeter@49: the changes you make. If a new node is added a default value is mapped to it.
kpeter@49: You can define the default value by passing a second argument to the map's constructor.
kpeter@49: \code ListDigraph::ArcMap<int>  weight(digraph, 13); \endcode
kpeter@49: But keep in mind that \c VALUE has to have copy constructor.
kpeter@49: 
kpeter@49: Of course \c VALUE can be a rather complex type.
kpeter@49: 
kpeter@49: For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
kpeter@49: \dontinclude maps_summary.cc
kpeter@49: \skip template
kpeter@49: \until }
kpeter@49: The task is simple. We need the summary of some kind of data assigned to a digraph's nodes.
kpeter@49: (Whit a little trick the summary can be calculated only to a sub-digraph without changing
kpeter@49: this code. See \ref SubDigraph techniques - that's LEMON's true potential.)
kpeter@49: 
kpeter@49: And the usage is simpler than the declaration suggests. The compiler deduces the
kpeter@49: template specialization, so the usage is like a simple function call.
kpeter@49: \skip std
kpeter@49: \until ;
kpeter@49: 
kpeter@49: 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: 
kpeter@49: If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
kpeter@49: (coming soon) and will use maps hardly.
kpeter@49: Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
kpeter@49: 
kpeter@49: Here we discuss some advanced map techniques. Like writing your own maps or how to
kpeter@49: extend/modify a maps functionality with adaptors.
kpeter@49: 
kpeter@49: \section custom_maps Writing Custom ReadMap
kpeter@49: \subsection custom_read_maps Readable Maps
kpeter@49: 
kpeter@49: Readable maps are very frequently used as the input of an
kpeter@49: algorithm.  For this purpose the most straightforward way is the use of the
kpeter@49: default maps provided by LEMON's digraph structures.
kpeter@49: Very often however, it is more
kpeter@49: convenient and/or more efficient to write your own readable map.
kpeter@49: 
kpeter@49: You can find some examples below. In these examples \c Digraph is the
kpeter@49: type of the particular digraph structure you use.
kpeter@49: 
kpeter@49: 
kpeter@49: This simple map assigns \f$\pi\f$ to each arc.
kpeter@49: 
kpeter@49: \code
kpeter@49: struct MyMap 
kpeter@49: {
kpeter@49:   typedef double Value;
kpeter@49:   typedef Digraph::Arc Key;
kpeter@49:   double operator[](const Key &e) const { return PI;}
kpeter@49: };
kpeter@49: \endcode
kpeter@49: 
kpeter@49: An alternative way to define maps is to use MapBase
kpeter@49: 
kpeter@49: \code
kpeter@49: struct MyMap : public MapBase<Digraph::Arc,double>
kpeter@49: {
kpeter@49:   Value operator[](const Key& e) const { return PI;}
kpeter@49: };
kpeter@49: \endcode
kpeter@49: 
kpeter@49: Here is a bit more complex example.
kpeter@49: It provides a length function obtained
kpeter@49: from a base length function shifted by a potential difference.
kpeter@49: 
kpeter@49: \code
kpeter@49: class ReducedLengthMap  : public MapBase<Digraph::Arc,double>
kpeter@49: {
kpeter@49:   const Digraph &g;
kpeter@49:   const Digraph::ArcMap<double> &orig_len;
kpeter@49:   const Digraph::NodeMap<double> &pot;
kpeter@49:   
kpeter@49: public:
kpeter@49:   Value operator[](Key e) const {
kpeter@49:     return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
kpeter@49:   }
kpeter@49:   
kpeter@49:   ReducedLengthMap(const Digraph &_g,
kpeter@49:                    const Digraph::ArcMap &_o,
kpeter@49:                    const Digraph::NodeMap &_p)
kpeter@49:     : g(_g), orig_len(_o), pot(_p) {};
kpeter@49: };
kpeter@49: \endcode
kpeter@49: 
kpeter@49: Then, you can call e.g. Dijkstra algoritm on this map like this:
kpeter@49: \code
kpeter@49:   ...
kpeter@49:   ReducedLengthMap rm(g,len,pot);
kpeter@49:   Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
kpeter@49:   dij.run(s);
kpeter@49:   ...
kpeter@49: \endcode
kpeter@49: 
kpeter@49: 
kpeter@46: [SEC]sec_map_concepts[SEC] Map Concepts
kpeter@46: 
kpeter@46: ...
kpeter@46: 
kpeter@46: 
kpeter@46: [SEC]sec_own_maps[SEC] Creating Own Maps
kpeter@46: 
kpeter@46: ...
kpeter@46: 
kpeter@46: [SEC]sec_map_adaptors[SEC] Map Adaptors
kpeter@46: 
kpeter@46: See \ref map_adaptors in the reference manual.
kpeter@46: 
kpeter@46: 
kpeter@46: [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
kpeter@46: 
kpeter@49: The basic functionality of the algorithms can be highly extended using
kpeter@49: special purpose map types for their internal data structures.
kpeter@49: For example, the \ref Dijkstra class stores a 
kpeter@49: ef ProcessedMap,
kpeter@49: which has to be a writable node map of \ref bool value type.
kpeter@49: The assigned value of each node is set to \ref true when the node is
kpeter@49: processed, i.e., its actual distance is found.
kpeter@49: Applying a special map, \ref LoggerBoolMap, the processed order of
kpeter@49: the nodes can easily be stored in a standard container.
kpeter@49: 
kpeter@49: Such specific map types can be passed to the algorithms using the technique of
kpeter@49: named template parameters. Similarly to the named function parameters,
kpeter@49: they allow specifying any subset of the parameters and in arbitrary order.
kpeter@49: 
kpeter@49: \code
kpeter@49:   typedef vector<ListDigraph::Node> Container;
kpeter@49:   typedef back_insert_iterator<Container> InsertIterator;
kpeter@49:   typedef LoggerBoolMap<InsertIterator> ProcessedMap;
kpeter@49:   Dijkstra<ListDigraph>
kpeter@49:     ::SetProcessedMap<ProcessedMap>
kpeter@49:     ::Create dijktra(g, length);
kpeter@49: 
kpeter@49:   Container container;
kpeter@49:   InsertIterator iterator(container);
kpeter@49:   ProcessedMap processed(iterator);
kpeter@49: 
kpeter@49:   dijkstra.processedMap(processed).run(s);
kpeter@49: \endcode
kpeter@49: 
kpeter@49: The function-type interfaces are considerably simpler, but they can be
kpeter@49: used in almost all practical cases. Surprisingly, even the above example
kpeter@49: can also be implemented using the \ref dijkstra() function and
kpeter@49: named parameters, as follows.
kpeter@49: Note that the function-type interface has the major advantage
kpeter@49: that temporary objects can be passed as parameters.
kpeter@49: 
kpeter@49: \code
kpeter@49:   vector<ListDigraph::Node> process_order;
kpeter@49:   dijkstra(g, length)
kpeter@49:     .processedMap(loggerBoolMap(back_inserter(process_order)))
kpeter@49:     .run(s);
kpeter@49: \endcode
kpeter@49: 
kpeter@49: LEMON also contains visitor based algorithm classes for
kpeter@49: BFS and DFS.
kpeter@49: 
kpeter@49: Skeleton visitor classes are defined for both BFS and DFS, the concrete
kpeter@49: implementations can be inherited from them.
kpeter@49: \code
kpeter@49:   template <typename GR>
kpeter@49:   struct DfsVisitor {
kpeter@49:     void start(const typename GR::Node& node) {}
kpeter@49:     void stop(const typename GR::Node& node) {}
kpeter@49:     void reach(const typename GR::Node& node) {}
kpeter@49:     void leave(const typename GR::Node& node) {}
kpeter@49:     void discover(const typename GR::Arc& arc) {}
kpeter@49:     void examine(const typename GR::Arc& arc) {}
kpeter@49:     void backtrack(const typename GR::Arc& arc) {}
kpeter@49:   };
kpeter@49: \endcode
kpeter@49: 
kpeter@49: In the following example, the \ref discover()} and \code{examine()
kpeter@49: events are processed and the DFS tree is stored in an arc map.
kpeter@49: The values of this map indicate whether the corresponding arc
kpeter@49: reaches a new node or its target node is already reached.
kpeter@49: \code
kpeter@49:   template <typename GR>
kpeter@49:   struct TreeVisitor : public DfsVisitor<GR> {
kpeter@49:     TreeVisitor(typename GR::ArcMap<bool>& tree)
kpeter@49:       : _tree(tree) {}
kpeter@49:     void discover(const typename GR::Arc& arc)
kpeter@49:       { _tree[arc] = true; }
kpeter@49:     void examine(const typename GR::Arc& arc)
kpeter@49:       { _tree[arc] = false; }
kpeter@49:     typename GR::ArcMap<bool>& _tree;
kpeter@49:   };
kpeter@49: \endcode
kpeter@49: 
kpeter@46: 
kpeter@46: [TRAILER]
kpeter@46: */
kpeter@46: }