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