Legal stuff, version 0.2.
7 Maps play central role in HUGOlib. As their name suggests, they map a
8 certain range of \e keys to certain \e values. Each map has two
9 <tt>typedef</tt>'s to determine the types of keys and values, like this:
13 typedef double ValueType;
16 A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both
17 (ReadWrite Map). There also exists a special type of
18 ReadWrite map called <em>reference map</em>. In addition that you can
19 read and write the values of a key, a reference map
20 can also give you a reference to the
21 value belonging to a key, so you have a direct access to the memory address
24 Each graph structure in HUGOlib provides two standard map templates called
25 \c EdgeMap and \c NodeMap. Both are reference maps and you can easily
26 assign data to the nodes and to the edges of the graph. For example if you
27 have a graph \c G defined as
31 and you want to assign floating point value to each edge, you can do
34 ListGraph::EdgeMap<double> length(G);
37 The value of a readable map can be obtained by <tt>operator[]</tt>.
41 where \c e is an instance of \c ListGraph::Edge.
43 that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or
44 \c ListGraph::OutEdgeIt)
46 There are two ways the assign a new value to a key
48 - In case of a <em>reference map</em> <tt>operator[]</tt>
49 gives you a reference to the
50 value, thus you can use this.
54 - <em>Writable maps</em> have
55 a member function \c set(KeyType,const ValueType &)
61 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
63 not reference maps, so if you want to write an generic algorithm, you should
64 insist on the second method.
66 \section how-to-write-your-own-map How to Write Your Own Maps
68 \subsection read-maps Readable Maps
70 The 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
72 default maps provided by Hugo's graph structures.
73 Very often however, it is more
74 convenient and/or more efficient to write your own readable map.
76 You can find some examples below. In these examples \c Graph is the
77 type of the particular graph structure you use.
80 This simple map assigns \f$\pi\f$ to each edge.
85 typedef double ValueType;
86 typedef Graph::Edge KeyType;
87 double operator[](KeyType e) const { return M_PI;}
91 An alternative way to define maps is to use \c MapBase
93 \todo For this, \c MapBase seems to be a better name then \c NullMap.
96 struct MyMap : public MapBase<Graph::Edge,double>
98 ValueType operator[](KeyType e) const { return M_PI;}
102 Here is a bit more complex example.
103 It provides a length function which is obtained
104 from a base length function shifted by a potential difference.
107 class MyLengthMap : public MapBase<Graph::Edge,double>
110 const Graph::EdgeMap<double> &orig_len;
111 const Graph::NodeMap<double> &pot;
114 KeyType operator[](ValueType e) const {
115 return orig_len.get(e)-pot.get(G.head(e))-pot.get(G.tail(e));
118 MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p)
119 : G(g), orig_len(o), pot(p) {};
124 \subsection write-maps Writable Maps
128 \subsection side-effect-maps Maps with Side Effect