doc/maps1.dox
author kpeter
Mon, 18 Feb 2008 03:34:16 +0000
changeset 2577 2c6204d4b0f6
parent 2476 059dcdda37c5
permissions -rw-r--r--
Add a cost scaling min cost flow algorithm.

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