Changeset 692:098bc98f7530 in lemon-0.x
- Timestamp:
- 07/06/04 11:34:25 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@942
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/maps.dox
r685 r692 1 1 /*! 2 2 3 \page maps How to write your own maps4 3 5 \section read-maps Readable Maps 4 5 \page maps Maps 6 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: 10 11 \code 12 typedef Edge KeyType; 13 typedef double ValueType; 14 \endcode 15 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 22 where it is stored. 23 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 28 \code 29 ListGraph G; 30 \endcode 31 and you want to assign floating point value to each edge, you can do 32 it like this. 33 \code 34 ListGraph::EdgeMap<double> length(G); 35 \endcode 36 37 The value of a readable map can be obtained by <tt>operator[]</tt>. 38 \code 39 d=length[e]; 40 \endcode 41 where \c e is an instance of \c ListGraph::Edge. 42 (Or anything else 43 that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or 44 \c ListGraph::OutEdgeIt) 45 46 There are two ways the assign a new value to a key 47 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. 51 \code 52 length[e]=3.5; 53 \endcode 54 - <em>Writable maps</em> have 55 a member function \c set(KeyType,const ValueType &) 56 for this purpose. 57 \code 58 length.set(e,3.5); 59 \endcode 60 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. 65 66 \section how-to-write-your-own-map How To write your own maps 67 68 \subsection read-maps Readable Maps 6 69 7 70 The readable maps are very frequently used as the input of the 8 algorithms. For this purpose the most straightforward is to use the 9 maps provided by Hugo's graph structres. Very often however, it is more 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 10 74 convenient and/or more efficient to write your own readable map. 11 75 12 You can find some examples below. 76 You can find some examples below. In these examples \c Graph is the 77 type of the particular graph structure you use. 78 13 79 14 80 This simple map assigns \f$\pi\f$ to each edge. … … 18 84 { 19 85 typedef double ValueType; 20 double operator[](Graph::Edge e) const { return M_PI;} 86 typedef Graph::Edge KeyType; 87 double operator[](KeyType e) const { return M_PI;} 21 88 }; 22 89 \endcode 23 90 24 An alternative way to define maps. For this, \c MapBase seems to 25 be a better name then \c NullMap 91 An alternative way to define maps is to use \c MapBase 92 93 \todo For this, \c MapBase seems to be a better name then \c NullMap. 26 94 27 95 \code 28 struct MyMap : public MapBase<Edge,double> 29 { 30 double operator[](Graph::Edge e) const { return M_PI;} 31 }; 32 \endcode 33 34 Or, if we had \c KeyType and \c ValueType 35 36 \code 37 struct MyMap : public MapBase<Edge,double> 96 struct MyMap : public MapBase<Graph::Edge,double> 38 97 { 39 98 ValueType operator[](KeyType e) const { return M_PI;} … … 41 100 \endcode 42 101 43 44 Here is a more complex example.It provides a length function which is obtained45 from a base length function modified by a potential difference.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. 46 105 47 106 \code 48 class MyLengthMap 107 class MyLengthMap : public MapBase<Graph::Edge,double> 49 108 { 50 const Graph::EdgeMap &ol; 51 const Graph::NodeMap &pot; 109 const Graph &G; 110 const Graph::EdgeMap<double> &orig_len; 111 const Graph::NodeMap<double> &pot; 52 112 53 113 public: 54 typedef double ValueType; 55 56 double operator[](Graph::Edge e) const { 57 return ol.get(e)-pot.get(v)-pot.get(u); 114 KeyType operator[](ValueType e) const { 115 return orig_len.get(e)-pot.get(G.head(e))-pot.get(G.tail(e)); 58 116 } 59 117 60 My ComplexMap(const Graph::EdgeMap &o,const Graph::NodeMap &p) :61 ol(o), pot(p);118 MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p) 119 : G(g), orig_len(o), pot(p) {}; 62 120 }; 63 121 \endcode 64 122 65 \todo Please improve on the english. 66 \todo Don't we need \e to \e require a 'typedef xxx KeyType' tag, as well? 123 124 \subsection write-maps Writable Maps 125 126 To be written... 127 128 \subsection side-effect-maps Maps with Side Effect 129 130 To be written... 131 67 132 */
Note: See TracChangeset
for help on using the changeset viewer.