COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/maps.dox @ 1671:3c82a0d9e0e7

Last change on this file since 1671:3c82a0d9e0e7 was 1183:8f623d1833a7, checked in by athos, 15 years ago

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

File size: 3.9 KB
Line 
1namespace lemon{
2/*!
3
4\page maps-page Maps
5
6Maps play a central role in LEMON. As their name suggests, they map a
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
11  typedef Edge Key;
12  typedef double Value;
13\endcode
14
15A map can be
16\e readable (\ref lemon::concept::ReadMap "ReadMap", for short),
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
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
27Each graph structure in LEMON provides two standard map templates called
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
34and you want to assign a floating point value to each edge, you can do
35it like this.
36\code
37  ListGraph::EdgeMap<double> length(G);
38\endcode
39Note that you must give the underlying graph to the constructor.
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
48\c ListGraph::OutEdgeIt etc.)
49
50There are two ways to assign a new value to a key
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
59a member function \c set(Key,const Value &)
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
67not reference maps, so if you want to write a generic algorithm, you should
68insist on the second way.
69
70\section how-to-write-your-own-map How to Write Your Own Maps
71
72\subsection read-maps Readable Maps
73
74Readable maps are very frequently used as the input of an
75algorithm.  For this purpose the most straightforward way is the use of the
76default maps provided by LEMON's graph structures.
77Very often however, it is more
78convenient and/or more efficient to write your own readable map.
79
80You can find some examples below. In these examples \c Graph is the
81type of the particular graph structure you use.
82
83
84This simple map assigns \f$\pi\f$ to each edge.
85
86\code
87struct MyMap
88{
89  typedef double Value;
90  typedef Graph::Edge Key;
91  double operator[](Key e) const { return M_PI;}
92};
93\endcode
94
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.
98
99\code
100struct MyMap : public MapBase<Graph::Edge,double>
101{
102  Value operator[](Key e) const { return M_PI;}
103};
104\endcode
105
106Here is a bit more complex example.
107It provides a length function obtained
108from a base length function shifted by a potential difference.
109
110\code
111class ReducedLengthMap  : public MapBase<Graph::Edge,double>
112{
113  const Graph &g;
114  const Graph::EdgeMap<double> &orig_len;
115  const Graph::NodeMap<double> &pot;
116 
117public:
118  Value operator[](Key e) const {
119    return orig_len.get(e)-(pot.get(G.target(e))-pot.get(G.source(e)));
120  }
121 
122  ReducedLengthMap(const Graph &_g,
123                   const Graph::EdgeMap &o,
124                   const Graph::NodeMap &p)
125    : G(g), orig_len(o), pot(p) {};
126};
127\endcode
128
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
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
147*/
148}
Note: See TracBrowser for help on using the repository browser.