Maps II.

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

Writing Custom ReadMap

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 graph 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 Graph is the type of the particular graph structure you use.

This simple map assigns to each edge.

struct MyMap 
{
  typedef double Value;
  typedef Graph::Edge Key;
  double operator[](const Key &e) const { return PI;}
};

An alternative way to define maps is to use MapBase

struct MyMap : public MapBase<Graph::Edge,double>
{
  Value operator[](const Key& e) const { return PI;}
};

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

class ReducedLengthMap  : public MapBase<Graph::Edge,double>
{
  const Graph &g;
  const Graph::EdgeMap<double> &orig_len;
  const Graph::NodeMap<double> &pot;
  
public:
  Value operator[](Key e) const {
    return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
  }
  
  ReducedLengthMap(const Graph &_g,
                   const Graph::EdgeMap &_o,
                   const Graph::NodeMap &_p)
    : g(_g), orig_len(_o), pot(_p) {};
};

Then, you can call e.g. Dijkstra algoritm on this map like this:

  ...
  ReducedLengthMap rm(g,len,pot);
  Dijkstra<Graph,ReducedLengthMap> dij(g,rm);
  dij.run(s);
  ...