source: lemon-tutorial/maps.dox @ 53:0f695eac7e07

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

namespace lemon {
/**
[PAGE]sec_maps[PAGE] Maps

\todo This page is under construction.

\todo The following contents are ported from the LEMON 0.x tutorial,
thus they have to thouroughly revised, reorganized and reworked.

The LEMON maps are not only just storage classes, but also
they are %concepts of any key--value based data access.
Beside the standard digraph maps, LEMON contains several "lightweight"
\e map \e adaptor \e classes, which perform various operations on the
data of the adapted maps when their access operations are called,
but without actually copying or modifying the original storage.
These classes also conform to the map %concepts, thus they can be used
like standard LEMON maps.

Let us suppose that we have a traffic network stored in a LEMON digraph
structure with two arc maps \c length and \c speed, which
denote the physical length of each arc and the maximum (or average)
speed that can be achieved on the corresponding road-section,
respectively. If we are interested in the best traveling times,
the following code can be used.

\code
  dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
\endcode


Maps play a central role in LEMON. As their name suggests, they map a
certain range of \e keys to certain \e values. Each map has two
<tt>typedef</tt>'s to determine the types of keys and values, like this:

\code
  typedef Arc Key;
  typedef double Value;
\endcode

A map can be 
\e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
\e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
(\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
There also exists a special type of
ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
In addition that you can
read and write the values of a key, a reference map
can also give you a reference to the
value belonging to a key, so you have a direct access to the memory address
where it is stored.

Each digraph structure in LEMON provides two standard map templates called
\c ArcMap and \c NodeMap. Both are reference maps and you can easily
assign data to the nodes and to the arcs of the digraph. For example if you
have a digraph \c g defined as
\code
  ListDigraph g;
\endcode
and you want to assign a floating point value to each arc, you can do
it like this.
\code
  ListDigraph::ArcMap<double> length(g);
\endcode
Note that you must give the underlying digraph to the constructor.

The value of a readable map can be obtained by <tt>operator[]</tt>.
\code
  d=length[e];
\endcode
where \c e is an instance of \c ListDigraph::Arc.
(Or anything else
that converts to \c ListDigraph::Arc, like  \c ListDigraph::ArcIt or
\c ListDigraph::OutArcIt etc.)

There are two ways to assign a new value to a key

- In case of a <em>reference map</em> <tt>operator[]</tt>
gives you a reference to the
value, thus you can use this.
\code
  length[e]=3.5;
\endcode
- <em>Writable maps</em> have
a member function \c set(Key,const Value &)
for this purpose.
\code
  length.set(e,3.5);
\endcode

The first case is more comfortable and if you store complex structures in your
map, it might be more efficient. However, there are writable but
not reference maps, so if you want to write a generic algorithm, you should
insist on the second way.

\section how-to-write-your-own-map How to Write Your Own Maps

\subsection read-maps Readable Maps

Readable maps are very frequently used as the input of an
algorithm.  For this purpose the most straightforward way is the use of the
default maps provided by LEMON's digraph structures.
Very often however, it is more
convenient and/or more efficient to write your own readable map.

You can find some examples below. In these examples \c Digraph is the
type of the particular digraph structure you use.


This simple map assigns \f$\pi\f$ to each arc.

\code
struct MyMap 
{
  typedef double Value;
  typedef Digraph::Arc Key;
  double operator[](Key e) const { return PI;}
};
\endcode

An alternative way to define maps is to use \c MapBase

\code
struct MyMap : public MapBase<Digraph::Arc,double>
{
  Value operator[](Key e) const { return PI;}
};
\endcode

Here is a bit more complex example.
It provides a length function obtained
from a base length function shifted by a potential difference.

\code
class ReducedLengthMap  : public MapBase<Digraph::Arc,double>
{
  const Digraph &g;
  const Digraph::ArcMap<double> &orig_len;
  const Digraph::NodeMap<double> &pot;
  
public:
  Value operator[](Key e) const {
    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
  }
  
  ReducedLengthMap(const Digraph &_g,
                   const Digraph::ArcMap &_o,
                   const Digraph::NodeMap &_p)
    : g(_g), orig_len(_o), pot(_p) {};
};
\endcode

Then, you can call e.g. Dijkstra algoritm on this map like this:
\code
  ...
  ReducedLengthMap rm(g,len,pot);
  Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
  dij.run(s);
  ...
\endcode


In the previous section we discussed digraph topology. That is the skeleton a complex
digraph represented data-set needs. But how to assign the data itself to that skeleton?<br>
Here come the \b maps in.

\section maps_intro Introduction to maps
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>.
In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:
\code
  typedef Arc Key;
  typedef double Value;
\endcode
(Except matrix maps, they have two key types.)

To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes.
<ul>
<li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
\code value_typed_variable = map_instance[key_value]; \endcode
</li>
<li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
\code map_instance.set(key_value, value_typed_expression); \endcode
</li>
<li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
readable and writable. It is delivered from them.
</li>
<li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
<i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to
providing you constant or non-constant reference to the value belonging to a key,
so you have a direct access to the memory address where it is stored.
</li>
<li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap", 
\ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
\ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
</li>
</ul>

\section maps_graph Digraphs' maps
Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
satisfying the \ref DigraphMap concept.
If you want to assign data to nodes, just declare a NodeMap with the corresponding
type. As an example, think of a arc-weighted digraph.
\code ListDigraph::ArcMap<int>  weight(digraph); \endcode
You can see that the map needs the digraph whose arcs will mapped, but nothing more.

If the digraph class is extendable or erasable the map will automatically follow
the changes you make. If a new node is added a default value is mapped to it.
You can define the default value by passing a second argument to the map's constructor.
\code ListDigraph::ArcMap<int>  weight(digraph, 13); \endcode
But keep in mind that \c VALUE has to have copy constructor.

Of course \c VALUE can be a rather complex type.

For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
\dontinclude maps_summary.cc
\skip template
\until }
The task is simple. We need the summary of some kind of data assigned to a digraph's nodes.
(Whit a little trick the summary can be calculated only to a sub-digraph without changing
this code. See \ref SubDigraph techniques - that's LEMON's true potential.)

And the usage is simpler than the declaration suggests. The compiler deduces the
template specialization, so the usage is like a simple function call.
\skip std
\until ;

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.

If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
(coming soon) and will use maps hardly.
Or if you want to know more about maps read these \ref maps2 "advanced map techniques".

Here we discuss some advanced map techniques. Like writing your own maps or how to
extend/modify a maps functionality with adaptors.

\section custom_maps Writing Custom ReadMap
\subsection custom_read_maps Readable Maps

Readable maps are very frequently used as the input of an
algorithm.  For this purpose the most straightforward way is the use of the
default maps provided by LEMON's digraph structures.
Very often however, it is more
convenient and/or more efficient to write your own readable map.

You can find some examples below. In these examples \c Digraph is the
type of the particular digraph structure you use.


This simple map assigns \f$\pi\f$ to each arc.

\code
struct MyMap 
{
  typedef double Value;
  typedef Digraph::Arc Key;
  double operator[](const Key &e) const { return PI;}
};
\endcode

An alternative way to define maps is to use MapBase

\code
struct MyMap : public MapBase<Digraph::Arc,double>
{
  Value operator[](const Key& e) const { return PI;}
};
\endcode

Here is a bit more complex example.
It provides a length function obtained
from a base length function shifted by a potential difference.

\code
class ReducedLengthMap  : public MapBase<Digraph::Arc,double>
{
  const Digraph &g;
  const Digraph::ArcMap<double> &orig_len;
  const Digraph::NodeMap<double> &pot;
  
public:
  Value operator[](Key e) const {
    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
  }
  
  ReducedLengthMap(const Digraph &_g,
                   const Digraph::ArcMap &_o,
                   const Digraph::NodeMap &_p)
    : g(_g), orig_len(_o), pot(_p) {};
};
\endcode

Then, you can call e.g. Dijkstra algoritm on this map like this:
\code
  ...
  ReducedLengthMap rm(g,len,pot);
  Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
  dij.run(s);
  ...
\endcode


[SEC]sec_map_concepts[SEC] Map Concepts

...


[SEC]sec_own_maps[SEC] Creating Own Maps

...

[SEC]sec_map_adaptors[SEC] Map Adaptors

See \ref map_adaptors in the reference manual.


[SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps

The basic functionality of the algorithms can be highly extended using
special purpose map types for their internal data structures.
For example, the \ref Dijkstra class stores a 
ef ProcessedMap,
which has to be a writable node map of \ref bool value type.
The assigned value of each node is set to \ref true when the node is
processed, i.e., its actual distance is found.
Applying a special map, \ref LoggerBoolMap, the processed order of
the nodes can easily be stored in a standard container.

Such specific map types can be passed to the algorithms using the technique of
named template parameters. Similarly to the named function parameters,
they allow specifying any subset of the parameters and in arbitrary order.

\code
  typedef vector<ListDigraph::Node> Container;
  typedef back_insert_iterator<Container> InsertIterator;
  typedef LoggerBoolMap<InsertIterator> ProcessedMap;
  Dijkstra<ListDigraph>
    ::SetProcessedMap<ProcessedMap>
    ::Create dijktra(g, length);

  Container container;
  InsertIterator iterator(container);
  ProcessedMap processed(iterator);

  dijkstra.processedMap(processed).run(s);
\endcode

The function-type interfaces are considerably simpler, but they can be
used in almost all practical cases. Surprisingly, even the above example
can also be implemented using the \ref dijkstra() function and
named parameters, as follows.
Note that the function-type interface has the major advantage
that temporary objects can be passed as parameters.

\code
  vector<ListDigraph::Node> process_order;
  dijkstra(g, length)
    .processedMap(loggerBoolMap(back_inserter(process_order)))
    .run(s);
\endcode

LEMON also contains visitor based algorithm classes for
BFS and DFS.

Skeleton visitor classes are defined for both BFS and DFS, the concrete
implementations can be inherited from them.
\code
  template <typename GR>
  struct DfsVisitor {
    void start(const typename GR::Node& node) {}
    void stop(const typename GR::Node& node) {}
    void reach(const typename GR::Node& node) {}
    void leave(const typename GR::Node& node) {}
    void discover(const typename GR::Arc& arc) {}
    void examine(const typename GR::Arc& arc) {}
    void backtrack(const typename GR::Arc& arc) {}
  };
\endcode

In the following example, the \ref discover()} and \code{examine()
events are processed and the DFS tree is stored in an arc map.
The values of this map indicate whether the corresponding arc
reaches a new node or its target node is already reached.
\code
  template <typename GR>
  struct TreeVisitor : public DfsVisitor<GR> {
    TreeVisitor(typename GR::ArcMap<bool>& tree)
      : _tree(tree) {}
    void discover(const typename GR::Arc& arc)
      { _tree[arc] = true; }
    void examine(const typename GR::Arc& arc)
      { _tree[arc] = false; }
    typename GR::ArcMap<bool>& _tree;
  };
\endcode


[TRAILER]
*/
}