alpar@2196: /**
alpar@2196: \page maps2 Maps II.
alpar@2196: 
alpar@2196: Here we discuss some advanced map techniques. Like writing your own maps or how to
alpar@2196: extend/modify a maps functionality with adaptors.
alpar@2196: 
alpar@2196: \section custom_maps Writing Custom ReadMap
alpar@2196: \subsection custom_read_maps Readable Maps
alpar@2196: 
alpar@2196: Readable maps are very frequently used as the input of an
alpar@2196: algorithm.  For this purpose the most straightforward way is the use of the
alpar@2196: default maps provided by LEMON's graph structures.
alpar@2196: Very often however, it is more
alpar@2196: convenient and/or more efficient to write your own readable map.
alpar@2196: 
alpar@2196: You can find some examples below. In these examples \c Graph is the
alpar@2196: type of the particular graph structure you use.
alpar@2196: 
alpar@2196: 
alpar@2196: This simple map assigns \f$\pi\f$ to each edge.
alpar@2196: 
alpar@2196: \code
alpar@2196: struct MyMap 
alpar@2196: {
alpar@2196:   typedef double Value;
alpar@2196:   typedef Graph::Edge Key;
alpar@2196:   double operator[](Key e) const { return M_PI;}
alpar@2196: };
alpar@2196: \endcode
alpar@2196: 
alpar@2196: An alternative way to define maps is to use MapBase
alpar@2196: 
alpar@2196: \code
alpar@2196: struct MyMap : public MapBase<Graph::Edge,double>
alpar@2196: {
alpar@2196:   Value operator[](Key e) const { return M_PI;}
alpar@2196: };
alpar@2196: \endcode
alpar@2196: 
alpar@2196: Here is a bit more complex example.
alpar@2196: It provides a length function obtained
alpar@2196: from a base length function shifted by a potential difference.
alpar@2196: 
alpar@2196: \code
alpar@2196: class ReducedLengthMap  : public MapBase<Graph::Edge,double>
alpar@2196: {
alpar@2196:   const Graph &g;
alpar@2196:   const Graph::EdgeMap<double> &orig_len;
alpar@2196:   const Graph::NodeMap<double> &pot;
alpar@2196:   
alpar@2196: public:
alpar@2196:   Value operator[](Key e) const {
alpar@2196:     return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
alpar@2196:   }
alpar@2196:   
alpar@2196:   ReducedLengthMap(const Graph &_g,
alpar@2196:                    const Graph::EdgeMap &_o,
alpar@2196:                    const Graph::NodeMap &_p)
alpar@2196:     : g(_g), orig_len(_o), pot(_p) {};
alpar@2196: };
alpar@2196: \endcode
alpar@2196: 
alpar@2196: Then, you can call e.g. Dijkstra algoritm on this map like this:
alpar@2196: \code
alpar@2196:   ...
alpar@2196:   ReducedLengthMap rm(g,len,pot);
alpar@2196:   Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
alpar@2196:   dij.run(s);
alpar@2196:   ...
alpar@2196: \endcode
alpar@2196: 
alpar@2196: */