11 \code |
10 \code |
12 typedef Edge Key; |
11 typedef Edge Key; |
13 typedef double Value; |
12 typedef double Value; |
14 \endcode |
13 \endcode |
15 |
14 |
16 A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both |
15 A map can \e readable (\ref lemon::concept::ReadMap "ReadMap", for short), |
17 (ReadWrite Map). There also exists a special type of |
16 \e writable (\ref lemon::concept::WriteMap "WriteMap") or both |
18 ReadWrite map called <em>reference map</em>. In addition that you can |
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 |
19 read and write the values of a key, a reference map |
21 read and write the values of a key, a reference map |
20 can also give you a reference to the |
22 can also give you a reference to the |
21 value belonging to a key, so you have a direct access to the memory address |
23 value belonging to a key, so you have a direct access to the memory address |
22 where it is stored. |
24 where it is stored. |
23 |
25 |
26 assign data to the nodes and to the edges of the graph. For example if you |
28 assign data to the nodes and to the edges of the graph. For example if you |
27 have a graph \c G defined as |
29 have a graph \c G defined as |
28 \code |
30 \code |
29 ListGraph G; |
31 ListGraph G; |
30 \endcode |
32 \endcode |
31 and you want to assign floating point value to each edge, you can do |
33 and you want to assign a floating point value to each edge, you can do |
32 it like this. |
34 it like this. |
33 \code |
35 \code |
34 ListGraph::EdgeMap<double> length(G); |
36 ListGraph::EdgeMap<double> length(G); |
35 \endcode |
37 \endcode |
|
38 Note that you must give the underlying graph to the constructor. |
36 |
39 |
37 The value of a readable map can be obtained by <tt>operator[]</tt>. |
40 The value of a readable map can be obtained by <tt>operator[]</tt>. |
38 \code |
41 \code |
39 d=length[e]; |
42 d=length[e]; |
40 \endcode |
43 \endcode |
41 where \c e is an instance of \c ListGraph::Edge. |
44 where \c e is an instance of \c ListGraph::Edge. |
42 (Or anything else |
45 (Or anything else |
43 that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or |
46 that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or |
44 \c ListGraph::OutEdgeIt) |
47 \c ListGraph::OutEdgeIt etc.) |
45 |
48 |
46 There are two ways the assign a new value to a key |
49 There are two ways the assign a new value to a key |
47 |
50 |
48 - In case of a <em>reference map</em> <tt>operator[]</tt> |
51 - In case of a <em>reference map</em> <tt>operator[]</tt> |
49 gives you a reference to the |
52 gives you a reference to the |
58 length.set(e,3.5); |
61 length.set(e,3.5); |
59 \endcode |
62 \endcode |
60 |
63 |
61 The first case is more comfortable and if you store complex structures in your |
64 The first case is more comfortable and if you store complex structures in your |
62 map, it might be more efficient. However, there are writable but |
65 map, it might be more efficient. However, there are writable but |
63 not reference maps, so if you want to write an generic algorithm, you should |
66 not reference maps, so if you want to write a generic algorithm, you should |
64 insist on the second method. |
67 insist on the second way. |
65 |
68 |
66 \section how-to-write-your-own-map How to Write Your Own Maps |
69 \section how-to-write-your-own-map How to Write Your Own Maps |
67 |
70 |
68 \subsection read-maps Readable Maps |
71 \subsection read-maps Readable Maps |
69 |
72 |
70 The readable maps are very frequently used as the input of the |
73 Readable maps are very frequently used as the input of the |
71 algorithms. For this purpose the most straightforward way is the use of the |
74 algorithms. For this purpose the most straightforward way is the use of the |
72 default maps provided by LEMON's graph structures. |
75 default maps provided by LEMON's graph structures. |
73 Very often however, it is more |
76 Very often however, it is more |
74 convenient and/or more efficient to write your own readable map. |
77 convenient and/or more efficient to write your own readable map. |
75 |
78 |
98 Value operator[](Key e) const { return M_PI;} |
101 Value operator[](Key e) const { return M_PI;} |
99 }; |
102 }; |
100 \endcode |
103 \endcode |
101 |
104 |
102 Here is a bit more complex example. |
105 Here is a bit more complex example. |
103 It provides a length function which is obtained |
106 It provides a length function obtained |
104 from a base length function shifted by a potential difference. |
107 from a base length function shifted by a potential difference. |
105 |
108 |
106 \code |
109 \code |
107 class MyLengthMap : public MapBase<Graph::Edge,double> |
110 class ReducedLengthMap : public MapBase<Graph::Edge,double> |
108 { |
111 { |
109 const Graph &G; |
112 const Graph &g; |
110 const Graph::EdgeMap<double> &orig_len; |
113 const Graph::EdgeMap<double> &orig_len; |
111 const Graph::NodeMap<double> &pot; |
114 const Graph::NodeMap<double> &pot; |
112 |
115 |
113 public: |
116 public: |
114 Value operator[](Key e) const { |
117 Value operator[](Key e) const { |
115 return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e)); |
118 return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e)); |
116 } |
119 } |
117 |
120 |
118 MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p) |
121 ReducedLengthMap(const Graph &_g, |
|
122 const Graph::EdgeMap &o, |
|
123 const Graph::NodeMap &p) |
119 : G(g), orig_len(o), pot(p) {}; |
124 : G(g), orig_len(o), pot(p) {}; |
120 }; |
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 ... |
121 \endcode |
135 \endcode |
122 |
136 |
123 |
137 |
124 \subsection write-maps Writable Maps |
138 \subsection write-maps Writable Maps |
125 |
139 |