We have UndirGraph, so BidirGraph has been removed.
6 Maps play central role in LEMON. As their name suggests, they map a
7 certain 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:
15 A 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").
18 There also exists a special type of
19 ReadWrite map called \ref lemon::concept::ReferenceMap "reference map".
20 In addition that you can
21 read and write the values of a key, a reference map
22 can also give you a reference to the
23 value belonging to a key, so you have a direct access to the memory address
26 Each graph structure in LEMON provides two standard map templates called
27 \c EdgeMap and \c NodeMap. Both are reference maps and you can easily
28 assign data to the nodes and to the edges of the graph. For example if you
29 have a graph \c G defined as
33 and you want to assign a floating point value to each edge, you can do
36 ListGraph::EdgeMap<double> length(G);
38 Note that you must give the underlying graph to the constructor.
40 The value of a readable map can be obtained by <tt>operator[]</tt>.
44 where \c e is an instance of \c ListGraph::Edge.
46 that converts to \c ListGraph::Edge, like \c ListGraph::EdgeIt or
47 \c ListGraph::OutEdgeIt etc.)
49 There are two ways the assign a new value to a key
51 - In case of a <em>reference map</em> <tt>operator[]</tt>
52 gives you a reference to the
53 value, thus you can use this.
57 - <em>Writable maps</em> have
58 a member function \c set(Key,const Value &)
64 The first case is more comfortable and if you store complex structures in your
65 map, it might be more efficient. However, there are writable but
66 not reference maps, so if you want to write a generic algorithm, you should
67 insist on the second way.
69 \section how-to-write-your-own-map How to Write Your Own Maps
71 \subsection read-maps Readable Maps
73 Readable maps are very frequently used as the input of the
74 algorithms. For this purpose the most straightforward way is the use of the
75 default maps provided by LEMON's graph structures.
76 Very often however, it is more
77 convenient and/or more efficient to write your own readable map.
79 You can find some examples below. In these examples \c Graph is the
80 type of the particular graph structure you use.
83 This simple map assigns \f$\pi\f$ to each edge.
89 typedef Graph::Edge Key;
90 double operator[](Key e) const { return M_PI;}
94 An alternative way to define maps is to use \c MapBase
96 \todo For this, \c MapBase seems to be a better name then \c NullMap.
99 struct MyMap : public MapBase<Graph::Edge,double>
101 Value operator[](Key e) const { return M_PI;}
105 Here is a bit more complex example.
106 It provides a length function obtained
107 from a base length function shifted by a potential difference.
110 class ReducedLengthMap : public MapBase<Graph::Edge,double>
113 const Graph::EdgeMap<double> &orig_len;
114 const Graph::NodeMap<double> &pot;
117 Value operator[](Key e) const {
118 return orig_len.get(e)-pot.get(G.target(e))-pot.get(G.source(e));
121 ReducedLengthMap(const Graph &_g,
122 const Graph::EdgeMap &o,
123 const Graph::NodeMap &p)
124 : G(g), orig_len(o), pot(p) {};
128 Then, you can call e.g. Dijkstra algoritm on this map like this:
131 ReducedLengthMap rm(g,len,pot);
132 Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
138 \subsection write-maps Writable Maps
142 \subsection side-effect-maps Maps with Side Effect