Small bugs in the documentation.
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::concepts::ReadMap "ReadMap", for short),
17 \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
18 (\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
19 There also exists a special type of
20 ReadWrite map called \ref lemon::concepts::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
98 struct MyMap : public MapBase<Graph::Edge,double>
100 Value operator[](Key e) const { return M_PI;}
104 Here is a bit more complex example.
105 It provides a length function obtained
106 from a base length function shifted by a potential difference.
109 class ReducedLengthMap : public MapBase<Graph::Edge,double>
112 const Graph::EdgeMap<double> &orig_len;
113 const Graph::NodeMap<double> &pot;
116 Value operator[](Key e) const {
117 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
120 ReducedLengthMap(const Graph &_g,
121 const Graph::EdgeMap &_o,
122 const Graph::NodeMap &_p)
123 : g(_g), orig_len(_o), pot(_p) {};
127 Then, you can call e.g. Dijkstra algoritm on this map like this:
130 ReducedLengthMap rm(g,len,pot);
131 Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
137 \subsection write-maps Writable Maps
141 \subsection side-effect-maps Maps with Side Effect