1 | /* -*- C++ -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2007 |
---|
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 | |
---|
19 | /** |
---|
20 | \page maps1 Maps I. |
---|
21 | |
---|
22 | In the previous section we discussed graph topology. That is the skeleton a complex |
---|
23 | graph represented data-set needs. But how to assign the data itself to that skeleton?<br> |
---|
24 | Here come the \b maps in. |
---|
25 | |
---|
26 | \section maps_intro Introduction to maps |
---|
27 | Maps play a central role in LEMON. As their name suggests, they map a certain range of <i>keys</i> to certain <i>values</i>. |
---|
28 | In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this: |
---|
29 | \code |
---|
30 | typedef Edge Key; |
---|
31 | typedef double Value; |
---|
32 | \endcode |
---|
33 | (Except matrix maps, they have two key types.) |
---|
34 | |
---|
35 | To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by graph classes. |
---|
36 | <ul> |
---|
37 | <li>\ref ReadMap - values can be red out with the \c operator[]. |
---|
38 | \code value_typed_variable = map_instance[key_value]; \endcode |
---|
39 | </li> |
---|
40 | <li>\ref WriteMap - values can be set with the \c set() member function. |
---|
41 | \code map_instance.set(key_value, value_typed_expression); \endcode |
---|
42 | </li> |
---|
43 | <li>\ref ReadWriteMap - it's just a shortcut to indicate that the map is both |
---|
44 | readable and writable. It is delivered from them. |
---|
45 | </li> |
---|
46 | <li>\ref ReferenceMap - a subclass of ReadWriteMap. It has two additional typedefs |
---|
47 | <i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to |
---|
48 | providing you constant or non-constant reference to the value belonging to a key, |
---|
49 | so you have a direct access to the memory address where it is stored. |
---|
50 | </li> |
---|
51 | <li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys. |
---|
52 | The keys can be different types. (\ref ReadMatrixMap, \ref WriteMatrixMap, \ref ReadWriteMatrixMap, \ref ReferenceMatrixMap) |
---|
53 | </li> |
---|
54 | </ul> |
---|
55 | |
---|
56 | \section maps_graph Graphs' maps |
---|
57 | Every \ref MappableGraphComponent "mappable" graph class has two public templates: NodeMap<VALUE> and EdgeMap<VALUE> |
---|
58 | satisfying the \ref GraphMap concept. |
---|
59 | If you want to assign data to nodes, just declare a NodeMap with the corresponding |
---|
60 | type. As an example, think of a edge-weighted directed graph. |
---|
61 | \code ListGraph::EdgeMap<int> weight(graph); \endcode |
---|
62 | You can see that the map needs the graph hows edges will mapped, but nothing more. |
---|
63 | |
---|
64 | If the graph class is extendable or erasable the map will automatically follow |
---|
65 | the changes you make. If a new node is added a default value is mapped to it. |
---|
66 | You can define the default value by passing a second argument to the map's constructor. |
---|
67 | \code ListGraph::EdgeMap<int> weight(graph, 13); \endcode |
---|
68 | But keep in mind that \c VALUE has to have copy constructor. |
---|
69 | |
---|
70 | Of course \c VALUE can be a rather complex type. |
---|
71 | |
---|
72 | For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)! |
---|
73 | \dontinclude maps_summary.cc |
---|
74 | \skip template |
---|
75 | \until } |
---|
76 | The task is simple. We need the summary of some kind of data assigned to a graph's nodes. |
---|
77 | (Whit a little trick the summary can be calculated only to a sub-graph without changing |
---|
78 | this code. See \ref SubGraph techniques - that's LEMON's true potential.) |
---|
79 | |
---|
80 | And the usage is simpler than the declaration suggests. The compiler deduces the |
---|
81 | template specialization, so the usage is like a simple function call. |
---|
82 | \skip std |
---|
83 | \until ; |
---|
84 | |
---|
85 | Most of the time you will probably use graph maps, but keep in mind, that in LEMON maps are more general and can be used widely. |
---|
86 | |
---|
87 | If you want some 'real-life' examples see the next page, where we discuss \ref algorithms |
---|
88 | (coming soon) and will use maps hardly. |
---|
89 | Or if you want to know more about maps read these \ref maps2 "advanced map techniques". |
---|
90 | */ |
---|