COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/maps.dox @ 1639:aec340db8fc2

Last change on this file since 1639:aec340db8fc2 was 1183:8f623d1833a7, checked in by athos, 19 years ago

Some more documentation (sorry, I forgot to check the doxygen.log and now I am under windows)

File size: 3.9 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
30have a graph \c G defined as
31\code
32  ListGraph G;
33\endcode
[1083]34and you want to assign a floating point value to each edge, you can do
[692]35it like this.
36\code
37  ListGraph::EdgeMap<double> length(G);
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
97\todo For this, \c MapBase seems to be a better name then \c NullMap.
[289]98
99\code
[692]100struct MyMap : public MapBase<Graph::Edge,double>
[289]101{
[987]102  Value operator[](Key e) const { return M_PI;}
[289]103};
104\endcode
105
[692]106Here is a bit more complex example.
[1083]107It provides a length function obtained
[692]108from a base length function shifted by a potential difference.
[202]109
110\code
[1083]111class ReducedLengthMap  : public MapBase<Graph::Edge,double>
[202]112{
[1083]113  const Graph &g;
[692]114  const Graph::EdgeMap<double> &orig_len;
115  const Graph::NodeMap<double> &pot;
[202]116 
[273]117public:
[987]118  Value operator[](Key e) const {
[1167]119    return orig_len.get(e)-(pot.get(G.target(e))-pot.get(G.source(e)));
[210]120  }
[202]121 
[1083]122  ReducedLengthMap(const Graph &_g,
123                   const Graph::EdgeMap &o,
124                   const Graph::NodeMap &p)
[692]125    : G(g), orig_len(o), pot(p) {};
[202]126};
127\endcode
128
[1083]129Then, you can call e.g. Dijkstra algoritm on this map like this:
130\code
131  ...
132  ReducedLengthMap rm(g,len,pot);
133  Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
134  dij.run(s);
135  ...
136\endcode
137
[692]138
139\subsection write-maps Writable Maps
140
141To be written...
142
143\subsection side-effect-maps Maps with Side Effect
144
145To be written...
146
[202]147*/
[1183]148}
Note: See TracBrowser for help on using the repository browser.