alpar@2391: /* -*- C++ -*-
alpar@2391:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@2391:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391:  *
alpar@2391:  * Permission to use, modify and distribute this software is granted
alpar@2391:  * provided that this copyright notice appears in all copies. For
alpar@2391:  * precise terms see the accompanying LICENSE file.
alpar@2391:  *
alpar@2391:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2391:  * express or implied, and with no claim as to its suitability for any
alpar@2391:  * purpose.
alpar@2391:  *
alpar@2391:  */
alpar@2391: 
kpeter@2476: namespace lemon {
kpeter@2476: 
alpar@2196: /**
alpar@2196: \page maps1 Maps I.
alpar@2196: 
alpar@2196: In the previous section we discussed graph topology. That is the skeleton a complex
alpar@2196: graph represented data-set needs. But how to assign the data itself to that skeleton?<br>
alpar@2196: Here come the \b maps in.
alpar@2196: 
alpar@2196: \section maps_intro Introduction to maps
alpar@2196: 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: 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: \code
alpar@2196:   typedef Edge Key;
alpar@2196:   typedef double Value;
alpar@2196: \endcode
alpar@2196: (Except matrix maps, they have two key types.)
alpar@2196: 
alpar@2196: To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by graph classes.
alpar@2196: <ul>
kpeter@2476: <li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
alpar@2196: \code value_typed_variable = map_instance[key_value]; \endcode
alpar@2196: </li>
kpeter@2476: <li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
alpar@2196: \code map_instance.set(key_value, value_typed_expression); \endcode
alpar@2196: </li>
kpeter@2476: <li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
alpar@2196: readable and writable. It is delivered from them.
alpar@2196: </li>
kpeter@2476: <li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
alpar@2196: <i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to
alpar@2196: providing you constant or non-constant reference to the value belonging to a key,
alpar@2196: so you have a direct access to the memory address where it is stored.
alpar@2196: </li>
alpar@2196: <li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
kpeter@2476: The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap", 
kpeter@2476: \ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
kpeter@2476: \ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
alpar@2196: </li>
alpar@2196: </ul>
alpar@2196: 
alpar@2196: \section maps_graph Graphs' maps
alpar@2196: Every \ref MappableGraphComponent "mappable" graph class has two public templates: NodeMap<VALUE> and EdgeMap<VALUE>
alpar@2196: satisfying the \ref GraphMap concept.
alpar@2196: If you want to assign data to nodes, just declare a NodeMap with the corresponding
alpar@2196: type. As an example, think of a edge-weighted directed graph.
alpar@2196: \code ListGraph::EdgeMap<int>  weight(graph); \endcode
alpar@2408: You can see that the map needs the graph whose edges will mapped, but nothing more.
alpar@2196: 
alpar@2196: If the graph class is extendable or erasable the map will automatically follow
alpar@2196: the changes you make. If a new node is added a default value is mapped to it.
alpar@2196: You can define the default value by passing a second argument to the map's constructor.
alpar@2196: \code ListGraph::EdgeMap<int>  weight(graph, 13); \endcode
alpar@2196: But keep in mind that \c VALUE has to have copy constructor.
alpar@2196: 
alpar@2196: Of course \c VALUE can be a rather complex type.
alpar@2196: 
alpar@2196: For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
alpar@2196: \dontinclude maps_summary.cc
alpar@2196: \skip template
alpar@2196: \until }
alpar@2196: The task is simple. We need the summary of some kind of data assigned to a graph's nodes.
alpar@2196: (Whit a little trick the summary can be calculated only to a sub-graph without changing
alpar@2196: this code. See \ref SubGraph techniques - that's LEMON's true potential.)
alpar@2196: 
alpar@2196: And the usage is simpler than the declaration suggests. The compiler deduces the
alpar@2196: template specialization, so the usage is like a simple function call.
alpar@2196: \skip std
alpar@2196: \until ;
alpar@2196: 
alpar@2196: 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: 
alpar@2196: If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
alpar@2196: (coming soon) and will use maps hardly.
alpar@2196: Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
alpar@2196: */
kpeter@2476: 
kpeter@2476: }