kpeter@46: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@46: *
kpeter@46: * This file is a part of LEMON, a generic C++ optimization library.
kpeter@46: *
kpeter@46: * Copyright (C) 2003-2010
kpeter@46: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@46: * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@46: *
kpeter@46: * Permission to use, modify and distribute this software is granted
kpeter@46: * provided that this copyright notice appears in all copies. For
kpeter@46: * precise terms see the accompanying LICENSE file.
kpeter@46: *
kpeter@46: * This software is provided "AS IS" with no warranty of any kind,
kpeter@46: * express or implied, and with no claim as to its suitability for any
kpeter@46: * purpose.
kpeter@46: *
kpeter@46: */
kpeter@46:
kpeter@46: namespace lemon {
kpeter@46: /**
kpeter@46: [PAGE]sec_maps[PAGE] Maps
kpeter@46:
kpeter@46: \todo This page is under construction.
kpeter@46:
kpeter@49: \todo The following contents are ported from the LEMON 0.x tutorial,
kpeter@57: thus they have to be thoroughly revised and reworked.
kpeter@57:
kpeter@57: \warning Currently, this section may contain old or faulty contents.
kpeter@49:
kpeter@49: The LEMON maps are not only just storage classes, but also
kpeter@49: they are %concepts of any key--value based data access.
kpeter@49: Beside the standard digraph maps, LEMON contains several "lightweight"
kpeter@49: \e map \e adaptor \e classes, which perform various operations on the
kpeter@49: data of the adapted maps when their access operations are called,
kpeter@49: but without actually copying or modifying the original storage.
kpeter@49: These classes also conform to the map %concepts, thus they can be used
kpeter@49: like standard LEMON maps.
kpeter@49:
kpeter@49: Let us suppose that we have a traffic network stored in a LEMON digraph
kpeter@49: structure with two arc maps \c length and \c speed, which
kpeter@49: denote the physical length of each arc and the maximum (or average)
kpeter@49: speed that can be achieved on the corresponding road-section,
kpeter@49: respectively. If we are interested in the best traveling times,
kpeter@49: the following code can be used.
kpeter@49:
kpeter@49: \code
kpeter@49: dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
kpeter@49: \endcode
kpeter@49:
kpeter@49:
kpeter@49: Maps play a central role in LEMON. As their name suggests, they map a
kpeter@49: certain range of \e keys to certain \e values. Each map has two
kpeter@49: typedef's to determine the types of keys and values, like this:
kpeter@49:
kpeter@49: \code
kpeter@49: typedef Arc Key;
kpeter@49: typedef double Value;
kpeter@49: \endcode
kpeter@49:
kpeter@49: A map can be
kpeter@49: \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
kpeter@49: \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
kpeter@49: (\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
kpeter@49: There also exists a special type of
kpeter@49: ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
kpeter@49: In addition that you can
kpeter@49: read and write the values of a key, a reference map
kpeter@49: can also give you a reference to the
kpeter@49: value belonging to a key, so you have a direct access to the memory address
kpeter@49: where it is stored.
kpeter@49:
kpeter@49: Each digraph structure in LEMON provides two standard map templates called
kpeter@49: \c ArcMap and \c NodeMap. Both are reference maps and you can easily
kpeter@49: assign data to the nodes and to the arcs of the digraph. For example if you
kpeter@49: have a digraph \c g defined as
kpeter@49: \code
kpeter@49: ListDigraph g;
kpeter@49: \endcode
kpeter@49: and you want to assign a floating point value to each arc, you can do
kpeter@49: it like this.
kpeter@49: \code
kpeter@49: ListDigraph::ArcMap length(g);
kpeter@49: \endcode
kpeter@49: Note that you must give the underlying digraph to the constructor.
kpeter@49:
kpeter@49: The value of a readable map can be obtained by operator[].
kpeter@49: \code
kpeter@49: d=length[e];
kpeter@49: \endcode
kpeter@49: where \c e is an instance of \c ListDigraph::Arc.
kpeter@49: (Or anything else
kpeter@49: that converts to \c ListDigraph::Arc, like \c ListDigraph::ArcIt or
kpeter@49: \c ListDigraph::OutArcIt etc.)
kpeter@49:
kpeter@49: There are two ways to assign a new value to a key
kpeter@49:
kpeter@49: - In case of a reference map operator[]
kpeter@49: gives you a reference to the
kpeter@49: value, thus you can use this.
kpeter@49: \code
kpeter@49: length[e]=3.5;
kpeter@49: \endcode
kpeter@49: - Writable maps have
kpeter@49: a member function \c set(Key,const Value &)
kpeter@49: for this purpose.
kpeter@49: \code
kpeter@49: length.set(e,3.5);
kpeter@49: \endcode
kpeter@49:
kpeter@49: The first case is more comfortable and if you store complex structures in your
kpeter@49: map, it might be more efficient. However, there are writable but
kpeter@49: not reference maps, so if you want to write a generic algorithm, you should
kpeter@49: insist on the second way.
kpeter@49:
kpeter@49: \section how-to-write-your-own-map How to Write Your Own Maps
kpeter@49:
kpeter@49: \subsection read-maps Readable Maps
kpeter@49:
kpeter@49: Readable maps are very frequently used as the input of an
kpeter@49: algorithm. For this purpose the most straightforward way is the use of the
kpeter@49: default maps provided by LEMON's digraph structures.
kpeter@49: Very often however, it is more
kpeter@49: convenient and/or more efficient to write your own readable map.
kpeter@49:
kpeter@49: You can find some examples below. In these examples \c Digraph is the
kpeter@49: type of the particular digraph structure you use.
kpeter@49:
kpeter@49:
kpeter@49: This simple map assigns \f$\pi\f$ to each arc.
kpeter@49:
kpeter@49: \code
kpeter@49: struct MyMap
kpeter@49: {
kpeter@49: typedef double Value;
kpeter@49: typedef Digraph::Arc Key;
kpeter@49: double operator[](Key e) const { return PI;}
kpeter@49: };
kpeter@49: \endcode
kpeter@49:
kpeter@49: An alternative way to define maps is to use \c MapBase
kpeter@49:
kpeter@49: \code
kpeter@49: struct MyMap : public MapBase
kpeter@49: {
kpeter@49: Value operator[](Key e) const { return PI;}
kpeter@49: };
kpeter@49: \endcode
kpeter@49:
kpeter@49: Here is a bit more complex example.
kpeter@49: It provides a length function obtained
kpeter@49: from a base length function shifted by a potential difference.
kpeter@49:
kpeter@49: \code
kpeter@49: class ReducedLengthMap : public MapBase
kpeter@49: {
kpeter@49: const Digraph &g;
kpeter@49: const Digraph::ArcMap &orig_len;
kpeter@49: const Digraph::NodeMap &pot;
kpeter@49:
kpeter@49: public:
kpeter@49: Value operator[](Key e) const {
kpeter@49: return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
kpeter@49: }
kpeter@49:
kpeter@49: ReducedLengthMap(const Digraph &_g,
kpeter@49: const Digraph::ArcMap &_o,
kpeter@49: const Digraph::NodeMap &_p)
kpeter@49: : g(_g), orig_len(_o), pot(_p) {};
kpeter@49: };
kpeter@49: \endcode
kpeter@49:
kpeter@49: Then, you can call e.g. Dijkstra algoritm on this map like this:
kpeter@49: \code
kpeter@49: ...
kpeter@49: ReducedLengthMap rm(g,len,pot);
kpeter@49: Dijkstra dij(g,rm);
kpeter@49: dij.run(s);
kpeter@49: ...
kpeter@49: \endcode
kpeter@49:
kpeter@49:
kpeter@49: In the previous section we discussed digraph topology. That is the skeleton a complex
kpeter@49: digraph represented data-set needs. But how to assign the data itself to that skeleton?
kpeter@49: Here come the \b maps in.
kpeter@49:
kpeter@49: \section maps_intro Introduction to maps
kpeter@49: Maps play a central role in LEMON. As their name suggests, they map a certain range of keys to certain values.
kpeter@49: In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:
kpeter@49: \code
kpeter@49: typedef Arc Key;
kpeter@49: typedef double Value;
kpeter@49: \endcode
kpeter@49: (Except matrix maps, they have two key types.)
kpeter@49:
kpeter@49: To make easy to use them - especially as template parameters - there are map concepts like by digraph classes.
kpeter@49:
kpeter@49: - \ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
kpeter@49: \code value_typed_variable = map_instance[key_value]; \endcode
kpeter@49:
kpeter@49: - \ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
kpeter@49: \code map_instance.set(key_value, value_typed_expression); \endcode
kpeter@49:
kpeter@49: - \ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
kpeter@49: readable and writable. It is delivered from them.
kpeter@49:
kpeter@49: - \ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
kpeter@49: Reference and ConstReference and two overloads of \c operator[] to
kpeter@49: providing you constant or non-constant reference to the value belonging to a key,
kpeter@49: so you have a direct access to the memory address where it is stored.
kpeter@49:
kpeter@49: - And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
kpeter@49: The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap",
kpeter@49: \ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
kpeter@49: \ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
kpeter@49:
kpeter@49:
kpeter@49:
kpeter@49: \section maps_graph Digraphs' maps
kpeter@49: Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap and ArcMap
kpeter@49: satisfying the \ref DigraphMap concept.
kpeter@49: If you want to assign data to nodes, just declare a NodeMap with the corresponding
kpeter@49: type. As an example, think of a arc-weighted digraph.
kpeter@49: \code ListDigraph::ArcMap weight(digraph); \endcode
kpeter@49: You can see that the map needs the digraph whose arcs will mapped, but nothing more.
kpeter@49:
kpeter@49: If the digraph class is extendable or erasable the map will automatically follow
kpeter@49: the changes you make. If a new node is added a default value is mapped to it.
kpeter@49: You can define the default value by passing a second argument to the map's constructor.
kpeter@49: \code ListDigraph::ArcMap weight(digraph, 13); \endcode
kpeter@49: But keep in mind that \c VALUE has to have copy constructor.
kpeter@49:
kpeter@49: Of course \c VALUE can be a rather complex type.
kpeter@49:
kpeter@49: For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
kpeter@49: \dontinclude maps_summary.cc
kpeter@49: \skip template
kpeter@49: \until }
kpeter@49: The task is simple. We need the summary of some kind of data assigned to a digraph's nodes.
kpeter@49: (Whit a little trick the summary can be calculated only to a sub-digraph without changing
kpeter@49: this code. See \ref SubDigraph techniques - that's LEMON's true potential.)
kpeter@49:
kpeter@49: And the usage is simpler than the declaration suggests. The compiler deduces the
kpeter@49: template specialization, so the usage is like a simple function call.
kpeter@49: \skip std
kpeter@49: \until ;
kpeter@49:
kpeter@49: Most of the time you will probably use digraph maps, but keep in mind, that in LEMON maps are more general and can be used widely.
kpeter@49:
kpeter@49: If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
kpeter@49: (coming soon) and will use maps hardly.
kpeter@49: Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
kpeter@49:
kpeter@49: Here we discuss some advanced map techniques. Like writing your own maps or how to
kpeter@49: extend/modify a maps functionality with adaptors.
kpeter@49:
kpeter@49: \section custom_maps Writing Custom ReadMap
kpeter@49: \subsection custom_read_maps Readable Maps
kpeter@49:
kpeter@49: Readable maps are very frequently used as the input of an
kpeter@49: algorithm. For this purpose the most straightforward way is the use of the
kpeter@49: default maps provided by LEMON's digraph structures.
kpeter@49: Very often however, it is more
kpeter@49: convenient and/or more efficient to write your own readable map.
kpeter@49:
kpeter@49: You can find some examples below. In these examples \c Digraph is the
kpeter@49: type of the particular digraph structure you use.
kpeter@49:
kpeter@49:
kpeter@49: This simple map assigns \f$\pi\f$ to each arc.
kpeter@49:
kpeter@49: \code
kpeter@49: struct MyMap
kpeter@49: {
kpeter@49: typedef double Value;
kpeter@49: typedef Digraph::Arc Key;
kpeter@49: double operator[](const Key &e) const { return PI;}
kpeter@49: };
kpeter@49: \endcode
kpeter@49:
kpeter@49: An alternative way to define maps is to use MapBase
kpeter@49:
kpeter@49: \code
kpeter@49: struct MyMap : public MapBase
kpeter@49: {
kpeter@49: Value operator[](const Key& e) const { return PI;}
kpeter@49: };
kpeter@49: \endcode
kpeter@49:
kpeter@49: Here is a bit more complex example.
kpeter@49: It provides a length function obtained
kpeter@49: from a base length function shifted by a potential difference.
kpeter@49:
kpeter@49: \code
kpeter@49: class ReducedLengthMap : public MapBase
kpeter@49: {
kpeter@49: const Digraph &g;
kpeter@49: const Digraph::ArcMap &orig_len;
kpeter@49: const Digraph::NodeMap &pot;
kpeter@49:
kpeter@49: public:
kpeter@49: Value operator[](Key e) const {
kpeter@49: return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
kpeter@49: }
kpeter@49:
kpeter@49: ReducedLengthMap(const Digraph &_g,
kpeter@49: const Digraph::ArcMap &_o,
kpeter@49: const Digraph::NodeMap &_p)
kpeter@49: : g(_g), orig_len(_o), pot(_p) {};
kpeter@49: };
kpeter@49: \endcode
kpeter@49:
kpeter@49: Then, you can call e.g. Dijkstra algoritm on this map like this:
kpeter@49: \code
kpeter@49: ...
kpeter@49: ReducedLengthMap rm(g,len,pot);
kpeter@49: Dijkstra dij(g,rm);
kpeter@49: dij.run(s);
kpeter@49: ...
kpeter@49: \endcode
kpeter@49:
kpeter@49:
kpeter@46: [SEC]sec_map_concepts[SEC] Map Concepts
kpeter@46:
kpeter@46: ...
kpeter@46:
kpeter@46:
kpeter@46: [SEC]sec_own_maps[SEC] Creating Own Maps
kpeter@46:
kpeter@46: ...
kpeter@46:
kpeter@46: [SEC]sec_map_adaptors[SEC] Map Adaptors
kpeter@46:
kpeter@46: See \ref map_adaptors in the reference manual.
kpeter@46:
kpeter@46:
kpeter@46: [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
kpeter@46:
kpeter@49: The basic functionality of the algorithms can be highly extended using
kpeter@49: special purpose map types for their internal data structures.
kpeter@49: For example, the \ref Dijkstra class stores a
kpeter@49: ef ProcessedMap,
kpeter@49: which has to be a writable node map of \ref bool value type.
kpeter@49: The assigned value of each node is set to \ref true when the node is
kpeter@49: processed, i.e., its actual distance is found.
kpeter@49: Applying a special map, \ref LoggerBoolMap, the processed order of
kpeter@49: the nodes can easily be stored in a standard container.
kpeter@49:
kpeter@49: Such specific map types can be passed to the algorithms using the technique of
kpeter@49: named template parameters. Similarly to the named function parameters,
kpeter@49: they allow specifying any subset of the parameters and in arbitrary order.
kpeter@49:
kpeter@49: \code
kpeter@49: typedef vector Container;
kpeter@49: typedef back_insert_iterator InsertIterator;
kpeter@49: typedef LoggerBoolMap ProcessedMap;
kpeter@49: Dijkstra
kpeter@49: ::SetProcessedMap
kpeter@49: ::Create dijktra(g, length);
kpeter@49:
kpeter@49: Container container;
kpeter@49: InsertIterator iterator(container);
kpeter@49: ProcessedMap processed(iterator);
kpeter@49:
kpeter@49: dijkstra.processedMap(processed).run(s);
kpeter@49: \endcode
kpeter@49:
kpeter@49: The function-type interfaces are considerably simpler, but they can be
kpeter@49: used in almost all practical cases. Surprisingly, even the above example
kpeter@49: can also be implemented using the \ref dijkstra() function and
kpeter@49: named parameters, as follows.
kpeter@49: Note that the function-type interface has the major advantage
kpeter@49: that temporary objects can be passed as parameters.
kpeter@49:
kpeter@49: \code
kpeter@49: vector process_order;
kpeter@49: dijkstra(g, length)
kpeter@49: .processedMap(loggerBoolMap(back_inserter(process_order)))
kpeter@49: .run(s);
kpeter@49: \endcode
kpeter@49:
kpeter@49: LEMON also contains visitor based algorithm classes for
kpeter@49: BFS and DFS.
kpeter@49:
kpeter@49: Skeleton visitor classes are defined for both BFS and DFS, the concrete
kpeter@49: implementations can be inherited from them.
kpeter@49: \code
kpeter@49: template
kpeter@49: struct DfsVisitor {
kpeter@49: void start(const typename GR::Node& node) {}
kpeter@49: void stop(const typename GR::Node& node) {}
kpeter@49: void reach(const typename GR::Node& node) {}
kpeter@49: void leave(const typename GR::Node& node) {}
kpeter@49: void discover(const typename GR::Arc& arc) {}
kpeter@49: void examine(const typename GR::Arc& arc) {}
kpeter@49: void backtrack(const typename GR::Arc& arc) {}
kpeter@49: };
kpeter@49: \endcode
kpeter@49:
kpeter@49: In the following example, the \ref discover()} and \code{examine()
kpeter@49: events are processed and the DFS tree is stored in an arc map.
kpeter@49: The values of this map indicate whether the corresponding arc
kpeter@49: reaches a new node or its target node is already reached.
kpeter@49: \code
kpeter@49: template
kpeter@49: struct TreeVisitor : public DfsVisitor {
kpeter@49: TreeVisitor(typename GR::ArcMap& tree)
kpeter@49: : _tree(tree) {}
kpeter@49: void discover(const typename GR::Arc& arc)
kpeter@49: { _tree[arc] = true; }
kpeter@49: void examine(const typename GR::Arc& arc)
kpeter@49: { _tree[arc] = false; }
kpeter@49: typename GR::ArcMap& _tree;
kpeter@49: };
kpeter@49: \endcode
kpeter@49:
kpeter@46:
kpeter@46: [TRAILER]
kpeter@46: */
kpeter@46: }