COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/maps.dox @ 1169:8b06fbd5712c

Last change on this file since 1169:8b06fbd5712c was 1167:ccbca6ba8b59, checked in by athos, 19 years ago

Corrected spelling errors.

File size: 3.9 KB
Line 
1namespace lemon{
2/*!
3
4\page maps-page Maps
5
6Maps play a central role in LEMON. As their name suggests, they map a
7certain 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
15A 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").
18There also exists a special type of
19ReadWrite map called \ref lemon::concept::ReferenceMap "reference map".
20In addition that you can
21read and write the values of a key, a reference map
22can also give you a reference to the
23value belonging to a key, so you have a direct access to the memory address
24where it is stored.
25
26Each graph structure in LEMON provides two standard map templates called
27\c EdgeMap and \c NodeMap. Both are reference maps and you can easily
28assign data to the nodes and to the edges of the graph. For example if you
29have a graph \c G defined as
30\code
31  ListGraph G;
32\endcode
33and you want to assign a floating point value to each edge, you can do
34it like this.
35\code
36  ListGraph::EdgeMap<double> length(G);
37\endcode
38Note that you must give the underlying graph to the constructor.
39
40The value of a readable map can be obtained by <tt>operator[]</tt>.
41\code
42  d=length[e];
43\endcode
44where \c e is an instance of \c ListGraph::Edge.
45(Or anything else
46that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
47\c ListGraph::OutEdgeIt etc.)
48
49There are two ways to assign a new value to a key
50
51- In case of a <em>reference map</em> <tt>operator[]</tt>
52gives you a reference to the
53value, thus you can use this.
54\code
55  length[e]=3.5;
56\endcode
57- <em>Writable maps</em> have
58a member function \c set(Key,const Value &)
59for this purpose.
60\code
61  length.set(e,3.5);
62\endcode
63
64The first case is more comfortable and if you store complex structures in your
65map, it might be more efficient. However, there are writable but
66not reference maps, so if you want to write a generic algorithm, you should
67insist 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
73Readable maps are very frequently used as the input of an
74algorithm.  For this purpose the most straightforward way is the use of the
75default maps provided by LEMON's graph structures.
76Very often however, it is more
77convenient and/or more efficient to write your own readable map.
78
79You can find some examples below. In these examples \c Graph is the
80type of the particular graph structure you use.
81
82
83This simple map assigns \f$\pi\f$ to each edge.
84
85\code
86struct MyMap
87{
88  typedef double Value;
89  typedef Graph::Edge Key;
90  double operator[](Key e) const { return M_PI;}
91};
92\endcode
93
94An 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
99struct MyMap : public MapBase<Graph::Edge,double>
100{
101  Value operator[](Key e) const { return M_PI;}
102};
103\endcode
104
105Here is a bit more complex example.
106It provides a length function obtained
107from a base length function shifted by a potential difference.
108
109\code
110class 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 
116public:
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
128Then, 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
140To be written...
141
142\subsection side-effect-maps Maps with Side Effect
143
144To be written...
145
146*/
147}
Note: See TracBrowser for help on using the repository browser.