doc/maps1.dox
author alpar
Thu, 03 Apr 2008 12:06:48 +0000
changeset 2599 b9905565d185
parent 2476 059dcdda37c5
permissions -rw-r--r--
Serious bugfix in Random::gamma()
Backport from hg b6bede534255
alpar@2391
     1
/* -*- C++ -*-
alpar@2391
     2
 *
alpar@2391
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@2391
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
alpar@2391
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391
     8
 *
alpar@2391
     9
 * Permission to use, modify and distribute this software is granted
alpar@2391
    10
 * provided that this copyright notice appears in all copies. For
alpar@2391
    11
 * precise terms see the accompanying LICENSE file.
alpar@2391
    12
 *
alpar@2391
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@2391
    14
 * express or implied, and with no claim as to its suitability for any
alpar@2391
    15
 * purpose.
alpar@2391
    16
 *
alpar@2391
    17
 */
alpar@2391
    18
kpeter@2476
    19
namespace lemon {
kpeter@2476
    20
alpar@2196
    21
/**
alpar@2196
    22
\page maps1 Maps I.
alpar@2196
    23
alpar@2196
    24
In the previous section we discussed graph topology. That is the skeleton a complex
alpar@2196
    25
graph represented data-set needs. But how to assign the data itself to that skeleton?<br>
alpar@2196
    26
Here come the \b maps in.
alpar@2196
    27
alpar@2196
    28
\section maps_intro Introduction to maps
alpar@2196
    29
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
    30
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
    31
\code
alpar@2196
    32
  typedef Edge Key;
alpar@2196
    33
  typedef double Value;
alpar@2196
    34
\endcode
alpar@2196
    35
(Except matrix maps, they have two key types.)
alpar@2196
    36
alpar@2196
    37
To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by graph classes.
alpar@2196
    38
<ul>
kpeter@2476
    39
<li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
alpar@2196
    40
\code value_typed_variable = map_instance[key_value]; \endcode
alpar@2196
    41
</li>
kpeter@2476
    42
<li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
alpar@2196
    43
\code map_instance.set(key_value, value_typed_expression); \endcode
alpar@2196
    44
</li>
kpeter@2476
    45
<li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
alpar@2196
    46
readable and writable. It is delivered from them.
alpar@2196
    47
</li>
kpeter@2476
    48
<li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
alpar@2196
    49
<i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to
alpar@2196
    50
providing you constant or non-constant reference to the value belonging to a key,
alpar@2196
    51
so you have a direct access to the memory address where it is stored.
alpar@2196
    52
</li>
alpar@2196
    53
<li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
kpeter@2476
    54
The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap", 
kpeter@2476
    55
\ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
kpeter@2476
    56
\ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
alpar@2196
    57
</li>
alpar@2196
    58
</ul>
alpar@2196
    59
alpar@2196
    60
\section maps_graph Graphs' maps
alpar@2196
    61
Every \ref MappableGraphComponent "mappable" graph class has two public templates: NodeMap<VALUE> and EdgeMap<VALUE>
alpar@2196
    62
satisfying the \ref GraphMap concept.
alpar@2196
    63
If you want to assign data to nodes, just declare a NodeMap with the corresponding
alpar@2196
    64
type. As an example, think of a edge-weighted directed graph.
alpar@2196
    65
\code ListGraph::EdgeMap<int>  weight(graph); \endcode
alpar@2408
    66
You can see that the map needs the graph whose edges will mapped, but nothing more.
alpar@2196
    67
alpar@2196
    68
If the graph class is extendable or erasable the map will automatically follow
alpar@2196
    69
the changes you make. If a new node is added a default value is mapped to it.
alpar@2196
    70
You can define the default value by passing a second argument to the map's constructor.
alpar@2196
    71
\code ListGraph::EdgeMap<int>  weight(graph, 13); \endcode
alpar@2196
    72
But keep in mind that \c VALUE has to have copy constructor.
alpar@2196
    73
alpar@2196
    74
Of course \c VALUE can be a rather complex type.
alpar@2196
    75
alpar@2196
    76
For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
alpar@2196
    77
\dontinclude maps_summary.cc
alpar@2196
    78
\skip template
alpar@2196
    79
\until }
alpar@2196
    80
The task is simple. We need the summary of some kind of data assigned to a graph's nodes.
alpar@2196
    81
(Whit a little trick the summary can be calculated only to a sub-graph without changing
alpar@2196
    82
this code. See \ref SubGraph techniques - that's LEMON's true potential.)
alpar@2196
    83
alpar@2196
    84
And the usage is simpler than the declaration suggests. The compiler deduces the
alpar@2196
    85
template specialization, so the usage is like a simple function call.
alpar@2196
    86
\skip std
alpar@2196
    87
\until ;
alpar@2196
    88
alpar@2196
    89
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
    90
alpar@2196
    91
If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
alpar@2196
    92
(coming soon) and will use maps hardly.
alpar@2196
    93
Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
alpar@2196
    94
*/
kpeter@2476
    95
kpeter@2476
    96
}