alpar@1083: namespace lemon{
alpar@202: /*!
alpar@202: 
alpar@1043: \page maps-page Maps
alpar@692: 
athos@1167: Maps play a central role in LEMON. As their name suggests, they map a
alpar@692: certain range of \e keys to certain \e values. Each map has two
alpar@692: <tt>typedef</tt>'s to determine the types of keys and values, like this:
alpar@692: 
alpar@692: \code
alpar@987:   typedef Edge Key;
alpar@987:   typedef double Value;
alpar@692: \endcode
alpar@692: 
alpar@1083: A map can \e readable (\ref lemon::concept::ReadMap "ReadMap", for short),
alpar@1083: \e writable (\ref lemon::concept::WriteMap "WriteMap") or both
alpar@1083: (\ref lemon::concept::ReadWriteMap "ReadWriteMap").
alpar@1083: There also exists a special type of
alpar@1083: ReadWrite map called \ref lemon::concept::ReferenceMap "reference map".
alpar@1083: In addition that you can
alpar@692: read and write the values of a key, a reference map
alpar@692: can also give you a reference to the
alpar@692: value belonging to a key, so you have a direct access to the memory address
alpar@692: where it is stored.
alpar@692: 
alpar@921: Each graph structure in LEMON provides two standard map templates called
alpar@692: \c EdgeMap and \c NodeMap. Both are reference maps and you can easily
alpar@692: assign data to the nodes and to the edges of the graph. For example if you
alpar@692: have a graph \c G defined as
alpar@692: \code
alpar@692:   ListGraph G;
alpar@692: \endcode
alpar@1083: and you want to assign a floating point value to each edge, you can do
alpar@692: it like this.
alpar@692: \code
alpar@692:   ListGraph::EdgeMap<double> length(G);
alpar@692: \endcode
alpar@1083: Note that you must give the underlying graph to the constructor.
alpar@692: 
alpar@692: The value of a readable map can be obtained by <tt>operator[]</tt>.
alpar@692: \code
alpar@692:   d=length[e];
alpar@692: \endcode
alpar@692: where \c e is an instance of \c ListGraph::Edge.
alpar@692: (Or anything else
alpar@692: that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
alpar@1083: \c ListGraph::OutEdgeIt etc.)
alpar@692: 
athos@1167: There are two ways to assign a new value to a key
alpar@692: 
alpar@692: - In case of a <em>reference map</em> <tt>operator[]</tt>
alpar@692: gives you a reference to the
alpar@692: value, thus you can use this.
alpar@692: \code
alpar@692:   length[e]=3.5;
alpar@692: \endcode
alpar@692: - <em>Writable maps</em> have
alpar@987: a member function \c set(Key,const Value &)
alpar@692: for this purpose.
alpar@692: \code
alpar@692:   length.set(e,3.5);
alpar@692: \endcode
alpar@692: 
alpar@692: The first case is more comfortable and if you store complex structures in your
alpar@692: map, it might be more efficient. However, there are writable but
alpar@1083: not reference maps, so if you want to write a generic algorithm, you should
alpar@1083: insist on the second way.
alpar@692: 
alpar@697: \section how-to-write-your-own-map How to Write Your Own Maps
alpar@692: 
alpar@692: \subsection read-maps Readable Maps
alpar@202: 
athos@1167: Readable maps are very frequently used as the input of an
athos@1167: algorithm.  For this purpose the most straightforward way is the use of the
alpar@921: default maps provided by LEMON's graph structures.
alpar@692: Very often however, it is more
alpar@289: convenient and/or more efficient to write your own readable map.
alpar@202: 
alpar@692: You can find some examples below. In these examples \c Graph is the
alpar@692: type of the particular graph structure you use.
alpar@692: 
alpar@202: 
alpar@204: This simple map assigns \f$\pi\f$ to each edge.
alpar@204: 
alpar@202: \code
alpar@273: struct MyMap 
alpar@202: {
alpar@987:   typedef double Value;
alpar@987:   typedef Graph::Edge Key;
alpar@987:   double operator[](Key e) const { return M_PI;}
alpar@204: };
alpar@204: \endcode
alpar@204: 
alpar@692: An alternative way to define maps is to use \c MapBase
alpar@692: 
alpar@692: \todo For this, \c MapBase seems to be a better name then \c NullMap.
alpar@289: 
alpar@289: \code
alpar@692: struct MyMap : public MapBase<Graph::Edge,double>
alpar@289: {
alpar@987:   Value operator[](Key e) const { return M_PI;}
alpar@289: };
alpar@289: \endcode
alpar@289: 
alpar@692: Here is a bit more complex example.
alpar@1083: It provides a length function obtained
alpar@692: from a base length function shifted by a potential difference.
alpar@202: 
alpar@202: \code
alpar@1083: class ReducedLengthMap  : public MapBase<Graph::Edge,double>
alpar@202: {
alpar@1083:   const Graph &g;
alpar@692:   const Graph::EdgeMap<double> &orig_len;
alpar@692:   const Graph::NodeMap<double> &pot;
alpar@202:   
alpar@273: public:
alpar@987:   Value operator[](Key e) const {
athos@1167:     return orig_len.get(e)-(pot.get(G.target(e))-pot.get(G.source(e)));
alpar@210:   }
alpar@202:   
alpar@1083:   ReducedLengthMap(const Graph &_g,
alpar@1083:                    const Graph::EdgeMap &o,
alpar@1083:                    const Graph::NodeMap &p)
alpar@692:     : G(g), orig_len(o), pot(p) {};
alpar@202: };
alpar@202: \endcode
alpar@202: 
alpar@1083: Then, you can call e.g. Dijkstra algoritm on this map like this:
alpar@1083: \code
alpar@1083:   ...
alpar@1083:   ReducedLengthMap rm(g,len,pot);
alpar@1083:   Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
alpar@1083:   dij.run(s);
alpar@1083:   ...
alpar@1083: \endcode
alpar@1083: 
alpar@692: 
alpar@692: \subsection write-maps Writable Maps
alpar@692: 
alpar@692: To be written...
alpar@692: 
alpar@692: \subsection side-effect-maps Maps with Side Effect
alpar@692: 
alpar@692: To be written...
alpar@692: 
alpar@202: */
alpar@1083: }