COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/maps.dox @ 781:d4d182ab75bd

Last change on this file since 781:d4d182ab75bd was 697:89d97db9c927, checked in by Alpar Juttner, 20 years ago

Capitalized section title.

File size: 3.5 KB
RevLine 
[202]1/*!
2
3
[692]4
5\page maps Maps
6
7Maps play central role in HUGOlib. As their name suggests, they map a
8certain 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
16A map can \e readable (ReadMap, for short), \e writable (WriteMap) or both
17(ReadWrite Map). There also exists a special type of
18ReadWrite map called <em>reference map</em>. In addition that you can
19read and write the values of a key, a reference map
20can also give you a reference to the
21value belonging to a key, so you have a direct access to the memory address
22where it is stored.
23
24Each graph structure in HUGOlib provides two standard map templates called
25\c EdgeMap and \c NodeMap. Both are reference maps and you can easily
26assign data to the nodes and to the edges of the graph. For example if you
27have a graph \c G defined as
28\code
29  ListGraph G;
30\endcode
31and you want to assign floating point value to each edge, you can do
32it like this.
33\code
34  ListGraph::EdgeMap<double> length(G);
35\endcode
36
37The value of a readable map can be obtained by <tt>operator[]</tt>.
38\code
39  d=length[e];
40\endcode
41where \c e is an instance of \c ListGraph::Edge.
42(Or anything else
43that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
44\c ListGraph::OutEdgeIt)
45
46There are two ways the assign a new value to a key
47
48- In case of a <em>reference map</em> <tt>operator[]</tt>
49gives you a reference to the
50value, thus you can use this.
51\code
52  length[e]=3.5;
53\endcode
54- <em>Writable maps</em> have
55a member function \c set(KeyType,const ValueType &)
56for this purpose.
57\code
58  length.set(e,3.5);
59\endcode
60
61The first case is more comfortable and if you store complex structures in your
62map, it might be more efficient. However, there are writable but
63not reference maps, so if you want to write an generic algorithm, you should
64insist on the second method.
65
[697]66\section how-to-write-your-own-map How to Write Your Own Maps
[692]67
68\subsection read-maps Readable Maps
[202]69
[289]70The readable maps are very frequently used as the input of the
[692]71algorithms.  For this purpose the most straightforward way is the use of the
72default maps provided by Hugo's graph structures.
73Very often however, it is more
[289]74convenient and/or more efficient to write your own readable map.
[202]75
[692]76You can find some examples below. In these examples \c Graph is the
77type of the particular graph structure you use.
78
[202]79
[204]80This simple map assigns \f$\pi\f$ to each edge.
81
[202]82\code
[273]83struct MyMap
[202]84{
[273]85  typedef double ValueType;
[692]86  typedef Graph::Edge KeyType;
87  double operator[](KeyType e) const { return M_PI;}
[204]88};
89\endcode
90
[692]91An 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.
[289]94
95\code
[692]96struct MyMap : public MapBase<Graph::Edge,double>
[289]97{
98  ValueType operator[](KeyType e) const { return M_PI;}
99};
100\endcode
101
[692]102Here is a bit more complex example.
103It provides a length function which is obtained
104from a base length function shifted by a potential difference.
[202]105
106\code
[692]107class MyLengthMap  : public MapBase<Graph::Edge,double>
[202]108{
[692]109  const Graph &G;
110  const Graph::EdgeMap<double> &orig_len;
111  const Graph::NodeMap<double> &pot;
[202]112 
[273]113public:
[692]114  KeyType operator[](ValueType e) const {
115    return orig_len.get(e)-pot.get(G.head(e))-pot.get(G.tail(e));
[210]116  }
[202]117 
[692]118  MyLengthMap(const Graph &g, const Graph::EdgeMap &o,const Graph::NodeMap &p)
119    : G(g), orig_len(o), pot(p) {};
[202]120};
121\endcode
122
[692]123
124\subsection write-maps Writable Maps
125
126To be written...
127
128\subsection side-effect-maps Maps with Side Effect
129
130To be written...
131
[202]132*/
Note: See TracBrowser for help on using the repository browser.