alpar@202: /*!
alpar@202: 
alpar@202: 
alpar@692: 
alpar@1043: \page maps-page Maps
alpar@692: 
alpar@921: Maps play 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@692: A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both
alpar@692: (ReadWrite Map). There also exists a special type of
alpar@692: ReadWrite map called <em>reference map</em>. 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@692: and you want to assign 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@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@692: \c ListGraph::OutEdgeIt)
alpar@692: 
alpar@692: There are two ways the 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@692: not reference maps, so if you want to write an generic algorithm, you should
alpar@692: insist on the second method.
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: 
alpar@289: The readable maps are very frequently used as the input of the
alpar@692: algorithms.  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@692: It provides a length function which is obtained
alpar@692: from a base length function shifted by a potential difference.
alpar@202: 
alpar@202: \code
alpar@692: class MyLengthMap  : public MapBase<Graph::Edge,double>
alpar@202: {
alpar@692:   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 {
alpar@986:     return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e));
alpar@210:   }
alpar@202:   
alpar@692:   MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p)
alpar@692:     : G(g), orig_len(o), pot(p) {};
alpar@202: };
alpar@202: \endcode
alpar@202: 
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: */