doc/maps2.dox
author deba
Tue, 17 Oct 2006 10:50:57 +0000
changeset 2247 269a0dcee70b
child 2391 14a343be7a5a
permissions -rw-r--r--
Update the Path concept
Concept check for paths

DirPath renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed
// I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation
     1 /**
     2 \page maps2 Maps II.
     3 
     4 Here we discuss some advanced map techniques. Like writing your own maps or how to
     5 extend/modify a maps functionality with adaptors.
     6 
     7 \section custom_maps Writing Custom ReadMap
     8 \subsection custom_read_maps Readable Maps
     9 
    10 Readable maps are very frequently used as the input of an
    11 algorithm.  For this purpose the most straightforward way is the use of the
    12 default maps provided by LEMON's graph structures.
    13 Very often however, it is more
    14 convenient and/or more efficient to write your own readable map.
    15 
    16 You can find some examples below. In these examples \c Graph is the
    17 type of the particular graph structure you use.
    18 
    19 
    20 This simple map assigns \f$\pi\f$ to each edge.
    21 
    22 \code
    23 struct MyMap 
    24 {
    25   typedef double Value;
    26   typedef Graph::Edge Key;
    27   double operator[](Key e) const { return M_PI;}
    28 };
    29 \endcode
    30 
    31 An alternative way to define maps is to use MapBase
    32 
    33 \code
    34 struct MyMap : public MapBase<Graph::Edge,double>
    35 {
    36   Value operator[](Key e) const { return M_PI;}
    37 };
    38 \endcode
    39 
    40 Here is a bit more complex example.
    41 It provides a length function obtained
    42 from a base length function shifted by a potential difference.
    43 
    44 \code
    45 class ReducedLengthMap  : public MapBase<Graph::Edge,double>
    46 {
    47   const Graph &g;
    48   const Graph::EdgeMap<double> &orig_len;
    49   const Graph::NodeMap<double> &pot;
    50   
    51 public:
    52   Value operator[](Key e) const {
    53     return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
    54   }
    55   
    56   ReducedLengthMap(const Graph &_g,
    57                    const Graph::EdgeMap &_o,
    58                    const Graph::NodeMap &_p)
    59     : g(_g), orig_len(_o), pot(_p) {};
    60 };
    61 \endcode
    62 
    63 Then, you can call e.g. Dijkstra algoritm on this map like this:
    64 \code
    65   ...
    66   ReducedLengthMap rm(g,len,pot);
    67   Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
    68   dij.run(s);
    69   ...
    70 \endcode
    71 
    72 */