COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/maps.dox @ 2058:0b1fc1566fdb

Last change on this file since 2058:0b1fc1566fdb was 1788:614ce2dd3cba, checked in by Balazs Dezso, 18 years ago

Some documentation modifications

File size: 3.8 KB
RevLine 
[1083]1namespace lemon{
[202]2/*!
3
[1043]4\page maps-page Maps
[692]5
[1167]6Maps play a central role in LEMON. As their name suggests, they map a
[692]7certain range of \e keys to certain \e values. Each map has two
8<tt>typedef</tt>'s to determine the types of keys and values, like this:
9
10\code
[987]11  typedef Edge Key;
12  typedef double Value;
[692]13\endcode
14
[1183]15A map can be
16\e readable (\ref lemon::concept::ReadMap "ReadMap", for short),
[1083]17\e writable (\ref lemon::concept::WriteMap "WriteMap") or both
18(\ref lemon::concept::ReadWriteMap "ReadWriteMap").
19There also exists a special type of
20ReadWrite map called \ref lemon::concept::ReferenceMap "reference map".
21In addition that you can
[692]22read and write the values of a key, a reference map
23can also give you a reference to the
24value belonging to a key, so you have a direct access to the memory address
25where it is stored.
26
[921]27Each graph structure in LEMON provides two standard map templates called
[692]28\c EdgeMap and \c NodeMap. Both are reference maps and you can easily
29assign data to the nodes and to the edges of the graph. For example if you
[1788]30have a graph \c g defined as
[692]31\code
[1788]32  ListGraph g;
[692]33\endcode
[1083]34and you want to assign a floating point value to each edge, you can do
[692]35it like this.
36\code
[1788]37  ListGraph::EdgeMap<double> length(g);
[692]38\endcode
[1083]39Note that you must give the underlying graph to the constructor.
[692]40
41The value of a readable map can be obtained by <tt>operator[]</tt>.
42\code
43  d=length[e];
44\endcode
45where \c e is an instance of \c ListGraph::Edge.
46(Or anything else
47that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
[1083]48\c ListGraph::OutEdgeIt etc.)
[692]49
[1167]50There are two ways to assign a new value to a key
[692]51
52- In case of a <em>reference map</em> <tt>operator[]</tt>
53gives you a reference to the
54value, thus you can use this.
55\code
56  length[e]=3.5;
57\endcode
58- <em>Writable maps</em> have
[987]59a member function \c set(Key,const Value &)
[692]60for this purpose.
61\code
62  length.set(e,3.5);
63\endcode
64
65The first case is more comfortable and if you store complex structures in your
66map, it might be more efficient. However, there are writable but
[1083]67not reference maps, so if you want to write a generic algorithm, you should
68insist on the second way.
[692]69
[697]70\section how-to-write-your-own-map How to Write Your Own Maps
[692]71
72\subsection read-maps Readable Maps
[202]73
[1167]74Readable maps are very frequently used as the input of an
75algorithm.  For this purpose the most straightforward way is the use of the
[921]76default maps provided by LEMON's graph structures.
[692]77Very often however, it is more
[289]78convenient and/or more efficient to write your own readable map.
[202]79
[692]80You can find some examples below. In these examples \c Graph is the
81type of the particular graph structure you use.
82
[202]83
[204]84This simple map assigns \f$\pi\f$ to each edge.
85
[202]86\code
[273]87struct MyMap
[202]88{
[987]89  typedef double Value;
90  typedef Graph::Edge Key;
91  double operator[](Key e) const { return M_PI;}
[204]92};
93\endcode
94
[692]95An alternative way to define maps is to use \c MapBase
96
[289]97\code
[692]98struct MyMap : public MapBase<Graph::Edge,double>
[289]99{
[987]100  Value operator[](Key e) const { return M_PI;}
[289]101};
102\endcode
103
[692]104Here is a bit more complex example.
[1083]105It provides a length function obtained
[692]106from a base length function shifted by a potential difference.
[202]107
108\code
[1083]109class ReducedLengthMap  : public MapBase<Graph::Edge,double>
[202]110{
[1083]111  const Graph &g;
[692]112  const Graph::EdgeMap<double> &orig_len;
113  const Graph::NodeMap<double> &pot;
[202]114 
[273]115public:
[987]116  Value operator[](Key e) const {
[1788]117    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
[210]118  }
[202]119 
[1083]120  ReducedLengthMap(const Graph &_g,
[1788]121                   const Graph::EdgeMap &_o,
122                   const Graph::NodeMap &_p)
123    : g(_g), orig_len(_o), pot(_p) {};
[202]124};
125\endcode
126
[1083]127Then, you can call e.g. Dijkstra algoritm on this map like this:
128\code
129  ...
130  ReducedLengthMap rm(g,len,pot);
131  Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
132  dij.run(s);
133  ...
134\endcode
135
[692]136
137\subsection write-maps Writable Maps
138
139To be written...
140
141\subsection side-effect-maps Maps with Side Effect
142
143To be written...
144
[202]145*/
[1183]146}
Note: See TracBrowser for help on using the repository browser.