COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/maps.dox

Last change on this file was 2568:046c055217f6, checked in by Alpar Juttner, 12 years ago

Math constants + configure bugfix backported
from hg a315a588a20d and 761622e5ed4c

File size: 4.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19namespace lemon{
20/*!
21
22\page maps-page Maps
23
24Maps play a central role in LEMON. As their name suggests, they map a
25certain range of \e keys to certain \e values. Each map has two
26<tt>typedef</tt>'s to determine the types of keys and values, like this:
27
28\code
29  typedef Edge Key;
30  typedef double Value;
31\endcode
32
33A map can be
34\e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
35\e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
36(\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
37There also exists a special type of
38ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
39In addition that you can
40read and write the values of a key, a reference map
41can also give you a reference to the
42value belonging to a key, so you have a direct access to the memory address
43where it is stored.
44
45Each graph structure in LEMON provides two standard map templates called
46\c EdgeMap and \c NodeMap. Both are reference maps and you can easily
47assign data to the nodes and to the edges of the graph. For example if you
48have a graph \c g defined as
49\code
50  ListGraph g;
51\endcode
52and you want to assign a floating point value to each edge, you can do
53it like this.
54\code
55  ListGraph::EdgeMap<double> length(g);
56\endcode
57Note that you must give the underlying graph to the constructor.
58
59The value of a readable map can be obtained by <tt>operator[]</tt>.
60\code
61  d=length[e];
62\endcode
63where \c e is an instance of \c ListGraph::Edge.
64(Or anything else
65that converts to \c ListGraph::Edge, like  \c ListGraph::EdgeIt or
66\c ListGraph::OutEdgeIt etc.)
67
68There are two ways to assign a new value to a key
69
70- In case of a <em>reference map</em> <tt>operator[]</tt>
71gives you a reference to the
72value, thus you can use this.
73\code
74  length[e]=3.5;
75\endcode
76- <em>Writable maps</em> have
77a member function \c set(Key,const Value &)
78for this purpose.
79\code
80  length.set(e,3.5);
81\endcode
82
83The first case is more comfortable and if you store complex structures in your
84map, it might be more efficient. However, there are writable but
85not reference maps, so if you want to write a generic algorithm, you should
86insist on the second way.
87
88\section how-to-write-your-own-map How to Write Your Own Maps
89
90\subsection read-maps Readable Maps
91
92Readable maps are very frequently used as the input of an
93algorithm.  For this purpose the most straightforward way is the use of the
94default maps provided by LEMON's graph structures.
95Very often however, it is more
96convenient and/or more efficient to write your own readable map.
97
98You can find some examples below. In these examples \c Graph is the
99type of the particular graph structure you use.
100
101
102This simple map assigns \f$\pi\f$ to each edge.
103
104\code
105struct MyMap
106{
107  typedef double Value;
108  typedef Graph::Edge Key;
109  double operator[](Key e) const { return PI;}
110};
111\endcode
112
113An alternative way to define maps is to use \c MapBase
114
115\code
116struct MyMap : public MapBase<Graph::Edge,double>
117{
118  Value operator[](Key e) const { return PI;}
119};
120\endcode
121
122Here is a bit more complex example.
123It provides a length function obtained
124from a base length function shifted by a potential difference.
125
126\code
127class ReducedLengthMap  : public MapBase<Graph::Edge,double>
128{
129  const Graph &g;
130  const Graph::EdgeMap<double> &orig_len;
131  const Graph::NodeMap<double> &pot;
132 
133public:
134  Value operator[](Key e) const {
135    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
136  }
137 
138  ReducedLengthMap(const Graph &_g,
139                   const Graph::EdgeMap &_o,
140                   const Graph::NodeMap &_p)
141    : g(_g), orig_len(_o), pot(_p) {};
142};
143\endcode
144
145Then, you can call e.g. Dijkstra algoritm on this map like this:
146\code
147  ...
148  ReducedLengthMap rm(g,len,pot);
149  Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
150  dij.run(s);
151  ...
152\endcode
153
154
155\subsection write-maps Writable Maps
156
157To be written...
158
159\subsection side-effect-maps Maps with Side Effect
160
161To be written...
162
163*/
164}
Note: See TracBrowser for help on using the repository browser.