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