Some documentation got revised.
6 Maps play a central role in LEMON. As their name suggests, they map a
7 certain 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:
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").
19 There also exists a special type of
20 ReadWrite map called \ref lemon::concept::ReferenceMap "reference map".
21 In addition that you can
22 read and write the values of a key, a reference map
23 can also give you a reference to the
24 value belonging to a key, so you have a direct access to the memory address
27 Each graph structure in LEMON provides two standard map templates called
28 \c EdgeMap and \c NodeMap. Both are reference maps and you can easily
29 assign data to the nodes and to the edges of the graph. For example if you
30 have a graph \c G defined as
34 and you want to assign a floating point value to each edge, you can do
37 ListGraph::EdgeMap<double> length(G);
39 Note that you must give the underlying graph to the constructor.
41 The value of a readable map can be obtained by <tt>operator[]</tt>.
45 where \c e is an instance of \c ListGraph::Edge.
47 that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or
48 \c ListGraph::OutEdgeIt etc.)
50 There are two ways to assign a new value to a key
52 - In case of a <em>reference map</em> <tt>operator[]</tt>
53 gives you a reference to the
54 value, thus you can use this.
58 - <em>Writable maps</em> have
59 a member function \c set(Key,const Value &)
65 The first case is more comfortable and if you store complex structures in your
66 map, it might be more efficient. However, there are writable but
67 not reference maps, so if you want to write a generic algorithm, you should
68 insist on the second way.
70 \section how-to-write-your-own-map How to Write Your Own Maps
72 \subsection read-maps Readable Maps
74 Readable maps are very frequently used as the input of an
75 algorithm. For this purpose the most straightforward way is the use of the
76 default maps provided by LEMON's graph structures.
77 Very often however, it is more
78 convenient and/or more efficient to write your own readable map.
80 You can find some examples below. In these examples \c Graph is the
81 type of the particular graph structure you use.
84 This simple map assigns \f$\pi\f$ to each edge.
90 typedef Graph::Edge Key;
91 double operator[](Key e) const { return M_PI;}
95 An alternative way to define maps is to use \c MapBase
97 \todo For this, \c MapBase seems to be a better name then \c NullMap.
100 struct MyMap : public MapBase<Graph::Edge,double>
102 Value operator[](Key e) const { return M_PI;}
106 Here is a bit more complex example.
107 It provides a length function obtained
108 from a base length function shifted by a potential difference.
111 class ReducedLengthMap : public MapBase<Graph::Edge,double>
114 const Graph::EdgeMap<double> &orig_len;
115 const Graph::NodeMap<double> &pot;
118 Value operator[](Key e) const {
119 return orig_len.get(e)-(pot.get(G.target(e))-pot.get(G.source(e)));
122 ReducedLengthMap(const Graph &_g,
123 const Graph::EdgeMap &o,
124 const Graph::NodeMap &p)
125 : G(g), orig_len(o), pot(p) {};
129 Then, you can call e.g. Dijkstra algoritm on this map like this:
132 ReducedLengthMap rm(g,len,pot);
133 Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
139 \subsection write-maps Writable Maps
143 \subsection side-effect-maps Maps with Side Effect