COIN-OR::LEMON - Graph Library

Changeset 692:098bc98f7530 in lemon-0.x


Ignore:
Timestamp:
07/06/04 11:34:25 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@942
Message:

Extended tutorial.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/maps.dox

    r685 r692  
    11/*!
    22
    3 \page maps How to write your own maps
    43
    5 \section read-maps Readable Maps
     4
     5\page maps Maps
     6
     7Maps play central role in HUGOlib. As their name suggests, they map a
     8certain range of \e keys to certain \e values. Each map has two
     9<tt>typedef</tt>'s to determine the types of keys and values, like this:
     10
     11\code
     12  typedef Edge KeyType;
     13  typedef double ValueType;
     14\endcode
     15
     16A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both
     17(ReadWrite Map). There also exists a special type of
     18ReadWrite map called <em>reference map</em>. In addition that you can
     19read and write the values of a key, a reference map
     20can also give you a reference to the
     21value belonging to a key, so you have a direct access to the memory address
     22where it is stored.
     23
     24Each graph structure in HUGOlib provides two standard map templates called
     25\c EdgeMap and \c NodeMap. Both are reference maps and you can easily
     26assign data to the nodes and to the edges of the graph. For example if you
     27have a graph \c G defined as
     28\code
     29  ListGraph G;
     30\endcode
     31and you want to assign floating point value to each edge, you can do
     32it like this.
     33\code
     34  ListGraph::EdgeMap<double> length(G);
     35\endcode
     36
     37The value of a readable map can be obtained by <tt>operator[]</tt>.
     38\code
     39  d=length[e];
     40\endcode
     41where \c e is an instance of \c ListGraph::Edge.
     42(Or anything else
     43that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
     44\c ListGraph::OutEdgeIt)
     45
     46There are two ways the assign a new value to a key
     47
     48- In case of a <em>reference map</em> <tt>operator[]</tt>
     49gives you a reference to the
     50value, thus you can use this.
     51\code
     52  length[e]=3.5;
     53\endcode
     54- <em>Writable maps</em> have
     55a member function \c set(KeyType,const ValueType &)
     56for this purpose.
     57\code
     58  length.set(e,3.5);
     59\endcode
     60
     61The first case is more comfortable and if you store complex structures in your
     62map, it might be more efficient. However, there are writable but
     63not reference maps, so if you want to write an generic algorithm, you should
     64insist on the second method.
     65
     66\section how-to-write-your-own-map How To write your own maps
     67
     68\subsection read-maps Readable Maps
    669
    770The readable maps are very frequently used as the input of the
    8 algorithms.  For this purpose the most straightforward is to use the
    9 maps provided by Hugo's graph structres. Very often however, it is more
     71algorithms.  For this purpose the most straightforward way is the use of the
     72default maps provided by Hugo's graph structures.
     73Very often however, it is more
    1074convenient and/or more efficient to write your own readable map.
    1175
    12 You can find some examples below.
     76You can find some examples below. In these examples \c Graph is the
     77type of the particular graph structure you use.
     78
    1379
    1480This simple map assigns \f$\pi\f$ to each edge.
     
    1884{
    1985  typedef double ValueType;
    20   double operator[](Graph::Edge e) const { return M_PI;}
     86  typedef Graph::Edge KeyType;
     87  double operator[](KeyType e) const { return M_PI;}
    2188};
    2289\endcode
    2390
    24 An alternative way to define maps. For this, \c MapBase seems to
    25 be a better name then \c NullMap
     91An alternative way to define maps is to use \c MapBase
     92
     93\todo For this, \c MapBase seems to be a better name then \c NullMap.
    2694
    2795\code
    28 struct MyMap : public MapBase<Edge,double>
    29 {
    30   double operator[](Graph::Edge e) const { return M_PI;}
    31 };
    32 \endcode
    33 
    34 Or, if we had \c KeyType and \c ValueType
    35 
    36 \code
    37 struct MyMap : public MapBase<Edge,double>
     96struct MyMap : public MapBase<Graph::Edge,double>
    3897{
    3998  ValueType operator[](KeyType e) const { return M_PI;}
     
    41100\endcode
    42101
    43 
    44 Here is a more complex example. It provides a length function which is obtained
    45 from a base length function modified by a potential difference.
     102Here is a bit more complex example.
     103It provides a length function which is obtained
     104from a base length function shifted by a potential difference.
    46105
    47106\code
    48 class MyLengthMap
     107class MyLengthMap  : public MapBase<Graph::Edge,double>
    49108{
    50   const Graph::EdgeMap &ol;
    51   const Graph::NodeMap &pot;
     109  const Graph &G;
     110  const Graph::EdgeMap<double> &orig_len;
     111  const Graph::NodeMap<double> &pot;
    52112 
    53113public:
    54   typedef double ValueType;
    55 
    56   double operator[](Graph::Edge e) const {
    57     return ol.get(e)-pot.get(v)-pot.get(u);
     114  KeyType operator[](ValueType e) const {
     115    return orig_len.get(e)-pot.get(G.head(e))-pot.get(G.tail(e));
    58116  }
    59117 
    60   MyComplexMap(const Graph::EdgeMap &o,const Graph::NodeMap &p) :
    61     ol(o), pot(p);
     118  MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p)
     119    : G(g), orig_len(o), pot(p) {};
    62120};
    63121\endcode
    64122
    65 \todo Please improve on the english.
    66 \todo Don't we need \e to \e require a 'typedef xxx KeyType' tag, as well?
     123
     124\subsection write-maps Writable Maps
     125
     126To be written...
     127
     128\subsection side-effect-maps Maps with Side Effect
     129
     130To be written...
     131
    67132*/
Note: See TracChangeset for help on using the changeset viewer.