Bug fix in CapacityScaling.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
24 Maps play a central role in LEMON. As their name suggests, they map a
25 certain 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:
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").
37 There also exists a special type of
38 ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
39 In addition that you can
40 read and write the values of a key, a reference map
41 can also give you a reference to the
42 value belonging to a key, so you have a direct access to the memory address
45 Each graph structure in LEMON provides two standard map templates called
46 \c EdgeMap and \c NodeMap. Both are reference maps and you can easily
47 assign data to the nodes and to the edges of the graph. For example if you
48 have a graph \c g defined as
52 and you want to assign a floating point value to each edge, you can do
55 ListGraph::EdgeMap<double> length(g);
57 Note that you must give the underlying graph to the constructor.
59 The value of a readable map can be obtained by <tt>operator[]</tt>.
63 where \c e is an instance of \c ListGraph::Edge.
65 that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or
66 \c ListGraph::OutEdgeIt etc.)
68 There are two ways to assign a new value to a key
70 - In case of a <em>reference map</em> <tt>operator[]</tt>
71 gives you a reference to the
72 value, thus you can use this.
76 - <em>Writable maps</em> have
77 a member function \c set(Key,const Value &)
83 The first case is more comfortable and if you store complex structures in your
84 map, it might be more efficient. However, there are writable but
85 not reference maps, so if you want to write a generic algorithm, you should
86 insist on the second way.
88 \section how-to-write-your-own-map How to Write Your Own Maps
90 \subsection read-maps Readable Maps
92 Readable maps are very frequently used as the input of an
93 algorithm. For this purpose the most straightforward way is the use of the
94 default maps provided by LEMON's graph structures.
95 Very often however, it is more
96 convenient and/or more efficient to write your own readable map.
98 You can find some examples below. In these examples \c Graph is the
99 type of the particular graph structure you use.
102 This simple map assigns \f$\pi\f$ to each edge.
107 typedef double Value;
108 typedef Graph::Edge Key;
109 double operator[](Key e) const { return PI;}
113 An alternative way to define maps is to use \c MapBase
116 struct MyMap : public MapBase<Graph::Edge,double>
118 Value operator[](Key e) const { return PI;}
122 Here is a bit more complex example.
123 It provides a length function obtained
124 from a base length function shifted by a potential difference.
127 class ReducedLengthMap : public MapBase<Graph::Edge,double>
130 const Graph::EdgeMap<double> &orig_len;
131 const Graph::NodeMap<double> &pot;
134 Value operator[](Key e) const {
135 return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
138 ReducedLengthMap(const Graph &_g,
139 const Graph::EdgeMap &_o,
140 const Graph::NodeMap &_p)
141 : g(_g), orig_len(_o), pot(_p) {};
145 Then, you can call e.g. Dijkstra algoritm on this map like this:
148 ReducedLengthMap rm(g,len,pot);
149 Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
155 \subsection write-maps Writable Maps
159 \subsection side-effect-maps Maps with Side Effect