alpar@2391: /* -*- C++ -*- alpar@2391: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2391: * Copyright (C) 2003-2007 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: 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?
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 keys to certain values. 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 map concepts like by graph classes. alpar@2196: alpar@2196: alpar@2196: \section maps_graph Graphs' maps alpar@2196: Every \ref MappableGraphComponent "mappable" graph class has two public templates: NodeMap and EdgeMap 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 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 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: */