RhodeCode

 * Copyright (C) 2003-2008

 * 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.

 *

 */

/// \ingroup demos

/// \file

/// \brief Demo of the graph drawing function \ref graphToEps()

///

/// This demo program shows examples how to use the function \ref

/// graphToEps(). It takes no input but simply creates seven

/// <tt>.eps</tt> files demonstrating the capability of \ref

/// graphToEps(), and showing how to draw directed graphs,

/// how to handle parallel egdes, how to change the properties (like

/// color, shape, size, title etc.) of nodes and arcs individually

///

/// \include graph_to_eps_demo.cc

#include<lemon/list_graph.h>

#include<lemon/graph_to_eps.h>

#include<lemon/math.h>

using namespace std;

using namespace lemon;

int main()

{

  Palette palette;

  Palette paletteW(true);

  // Create a small digraph

  ListDigraph g;

  typedef ListDigraph::Node Node;

  typedef ListDigraph::NodeIt NodeIt;

  typedef ListDigraph::Arc Arc;

  typedef dim2::Point<int> Point;

  Node n1=g.addNode();

  Node n2=g.addNode();

\code

 @nodes

 label  coordinates  size    title

 1      (10,20)      10      "First node"

 2      (80,80)      8       "Second node"

 3      (40,10)      10      "Third node"

\endcode

The \c \@arcs section is very similar to the \c \@nodes section,

it again starts with a header line describing the names of the maps,

but the \c "label" map is not obligatory here. The following lines

describe the arcs. The first two tokens of each line are

the source and the target node of the arc, respectively, then come the map

values. The source and target tokens must be node labels.

\code

 @arcs

         capacity

 1   2   16

 1   3   12

 2   3   18

\endcode

also store the edge set of an undirected graph. In such case there is

a conventional method for store arc maps in the file, if two columns

has the same caption with \c '+' and \c '-' prefix, then these columns

can be regarded as the values of an arc map.

The \c \@attributes section contains key-value pairs, each line

consists of two tokens, an attribute name, and then an attribute

value. The value of the attribute could be also a label value of a

node or an edge, or even an edge label prefixed with \c '+' or \c '-',

which regards to the forward or backward directed arc of the

corresponding edge.

\code

 @attributes

 source 1

 target 3

 caption "LEMON test digraph"

\endcode

The \e LGF can contain extra sections, but there is no restriction on

the format of such sections.

*/

}

  /// about each alteration in the container. The alterations have four type

  /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and

  /// \e erase() signals that only one or few items added or erased to or

  /// from the graph. If all items are erased from the graph or from an empty

  /// graph a new graph is builded then it can be signaled with the

  /// clear() and build() members. Important rule that if we erase items

  /// from graph we should first signal the alteration and after that erase

  /// them from the container, on the other way on item addition we should

  /// first extend the container and just after that signal the alteration.

  ///

  /// The alteration can be observed with a class inherited from the

  /// \e ObserverBase nested class. The signals can be handled with

  /// overriding the virtual functions defined in the base class.  The

  /// observer base can be attached to the notifier with the

  /// \e attach() member and can be detached with detach() function. The

  /// alteration handlers should not call any function which signals

  /// an other alteration in the same notifier and should not

  /// detach any observer from the notifier.

  ///

  /// Alteration observers try to be exception safe. If an \e add() or

  /// a \e clear() function throws an exception then the remaining

  /// observeres will not be notified and the fulfilled additions will

  /// be rolled back by calling the \e erase() or \e clear()

  /// functions. Thence the \e erase() and \e clear() should not throw

  /// exception which detach the observer from the notifier.

  ///

  /// There are some place when the alteration observing is not completly

  /// reliable. If we want to carry out the node degree in the graph

  /// as in the \ref InDegMap and we use the reverseEdge that cause

  /// unreliable functionality. Because the alteration observing signals

  /// only erasing and adding but not the reversing it will stores bad

  /// degrees. The sub graph adaptors cannot signal the alterations because

  /// just a setting in the filter map can modify the graph and this cannot

  /// be watched in any way.

  ///

  /// \param _Container The container which is observed.

  /// \param _Item The item type which is obserbved.

  template <typename _Container, typename _Item>

  class AlterationNotifier {

  public:

    typedef True Notifier;

    typedef _Container Container;

    typedef _Item Item;

    /// \brief Exception which can be called from \e clear() and

  // long double

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, long double> {

    typedef VectorMap<_Graph, _Item, long double> Map;

  };

  // pointer

  template <typename _Graph, typename _Item, typename _Ptr>

  struct DefaultMapSelector<_Graph, _Item, _Ptr*> {

    typedef VectorMap<_Graph, _Item, _Ptr*> Map;

  };

// #else

//   template <typename _Graph, typename _Item, typename _Value>

//   struct DefaultMapSelector {

//     typedef DebugMap<_Graph, _Item, _Value> Map;

//   };

// #endif

  template <typename _Graph, typename _Item, typename _Value>

  class DefaultMap

    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {

  public:

    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;

    typedef DefaultMap<_Graph, _Item, _Value> Map;

    typedef typename Parent::Graph Graph;

    typedef typename Parent::Value Value;

    explicit DefaultMap(const Graph& graph) : Parent(graph) {}

    DefaultMap(const Graph& graph, const Value& value)

      : Parent(graph, value) {}

    DefaultMap& operator=(const DefaultMap& cmap) {

      return operator=<DefaultMap>(cmap);

    }

    template <typename CMap>

    DefaultMap& operator=(const CMap& cmap) {

      Parent::operator=(cmap);

      return *this;

    }

  extern const Color GREEN;

  /// Blue color constant

  extern const Color BLUE;

  /// Yellow color constant

  extern const Color YELLOW;

  /// Magenta color constant

  extern const Color MAGENTA;

  /// Cyan color constant

  extern const Color CYAN;

  /// Grey color constant

  extern const Color GREY;

  /// Dark red color constant

  extern const Color DARK_RED;

  /// Dark green color constant

  extern const Color DARK_GREEN;

  /// Drak blue color constant

  extern const Color DARK_BLUE;

  /// Dark yellow color constant

  extern const Color DARK_YELLOW;

  /// Dark magenta color constant

  extern const Color DARK_MAGENTA;

  /// Dark cyan color constant

  extern const Color DARK_CYAN;

  ///This map assigns one of the predefined \ref Color "Color"s to

  ///each <tt>int</tt>. It is possible to change the colors as well as

  ///their number. The integer range is cyclically mapped to the

  ///provided set of colors.

  ///

  ///This is a true \ref concepts::ReferenceMap "reference map", so

  ///you can also change the actual colors.

  class Palette : public MapBase<int,Color>

  {

    std::vector<Color> colors;

  public:

    ///Constructor

    ///Constructor.

    ///\param have_white Indicates whether white is among the

    ///provided initial colors (\c true) or not (\c false). If it is true,

    ///white will be assigned to \c 0.

    ///\param num The number of the allocated colors. If it is \c -1,

    ///the default color configuration is set up (26 color plus optionaly the

    ///white).  If \c num is less then 26/27 then the default color

    ///list is cut. Otherwise the color list is filled repeatedly with

    ///the default color list.  (The colors can be changed later on.)

      ///

      /// Gives back the arc alteration notifier.

      EdgeNotifier& notifier(Edge) const {

        return EdgeNotifier();

      }

      template <typename _Graph>

      struct Constraints {

        void constraints() {

          checkConcept<AlterableGraphComponent<Base>, _Graph>();

          typename _Graph::EdgeNotifier& uen

            = graph.notifier(typename _Graph::Edge());

          ignore_unused_variable_warning(uen);

        }

        const _Graph& graph;

      };

    };

    /// \brief Class describing the concept of graph maps

    ///

    /// This class describes the common interface of the graph maps

    /// associate data to graph descriptors (nodes or arcs).

    template <typename _Graph, typename _Item, typename _Value>

    class GraphMap : public ReadWriteMap<_Item, _Value> {

    public:

      typedef ReadWriteMap<_Item, _Value> Parent;

      /// The graph type of the map.

      typedef _Graph Graph;

      /// The key type of the map.

      typedef _Item Key;

      /// The value type of the map.

      typedef _Value Value;

      /// \brief Construct a new map.

      ///

      /// Construct a new map for the graph.

      explicit GraphMap(const Graph&) {}

      /// \brief Construct a new map with default value.

      ///

      /// Construct a new map for the graph and initalise the values.

      GraphMap(const Graph&, const Value&) {}

    private:

    ///\param s The source node.

    ///\param t The target node.

    ///\param p The previous arc between \c s and \c t. It it is INVALID or

    ///not given, the operator finds the first appropriate arc.

    ///\return An arc from \c s to \c t after \c p or

    ///\ref INVALID if there is no more.

    ///

    ///For example, you can count the number of arcs from \c u to \c v in the

    ///following way.

    ///\code

    ///DynArcLookUp<ListDigraph> ae(g);

    ///...

    ///int n = 0;

    ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;

    ///\endcode

    ///

    ///Finding the arcs take at most <em>O</em>(log<em>d</em>)

    ///amortized time, specifically, the time complexity of the lookups

    ///is equal to the optimal search tree implementation for the

    ///current query distribution in a constant factor.

    ///

    ///\note This is a dynamic data structure, therefore the data

    ///structure is updated after each graph alteration. Thus although

    ///this data structure is theoretically faster than \ref ArcLookUp

    ///them.

    Arc operator()(Node s, Node t, Arc p = INVALID) const  {

      if (p == INVALID) {

        Arc a = _head[s];

        if (a == INVALID) return INVALID;

        Arc r = INVALID;

        while (true) {

          if (_g.target(a) < t) {

            if (_right[a] == INVALID) {

              const_cast<DynArcLookUp&>(*this).splay(a);

              return r;

            } else {

              a = _right[a];

            }

          } else {

            if (_g.target(a) == t) {

              r = a;

            }

            if (_left[a] == INVALID) {

              const_cast<DynArcLookUp&>(*this).splay(a);

              return r;

            } else {

              a = _left[a];

            }

    {

      std::vector<Arc> v;

      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);

      if(v.size()) {

        std::sort(v.begin(),v.end(),ArcLess(_g));

        _head[n]=refreshRec(v,0,v.size()-1);

      }

      else _head[n]=INVALID;

    }

    ///Refresh the full data structure.

    ///Build up the full search database. In fact, it simply calls

    ///\ref refresh(Node) "refresh(n)" for each node \c n.

    ///

    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is

    ///the number of the arcs in the digraph and <em>D</em> is the maximum

    ///out-degree of the digraph.

    void refresh()

    {

      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

    }

    ///Find an arc between two nodes.

    ///\param s The source node.

    ///\param t The target node.

    ///\return An arc from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    ///

    ///\warning If you change the digraph, refresh() must be called before using

    ///this operator. If you change the outgoing arcs of

    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.

    Arc operator()(Node s, Node t) const

    {

      Arc e;

      for(e=_head[s];

          e!=INVALID&&_g.target(e)!=t;

          e = t < _g.target(e)?_left[e]:_right[e]) ;

      return e;

    }

  };

  ///Fast look-up of all arcs between given endpoints.

  ///This class is the same as \ref ArcLookUp, with the addition

  ///that it makes it possible to find all parallel arcs between given

  ///endpoints.

    void refresh()

    {

      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);

    }

    ///Find an arc between two nodes.

    ///Find an arc between two nodes.

    ///\param s The source node.

    ///\param t The target node.

    ///\param prev The previous arc between \c s and \c t. It it is INVALID or

    ///not given, the operator finds the first appropriate arc.

    ///\return An arc from \c s to \c t after \c prev or

    ///\ref INVALID if there is no more.

    ///

    ///For example, you can count the number of arcs from \c u to \c v in the

    ///following way.

    ///\code

    ///AllArcLookUp<ListDigraph> ae(g);

    ///...

    ///int n = 0;

    ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;

    ///\endcode

    ///

    ///consecutive arcs are found in constant time.

    ///

    ///\warning If you change the digraph, refresh() must be called before using

    ///this operator. If you change the outgoing arcs of

    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.

    ///

#ifdef DOXYGEN

    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}

#else

    using ArcLookUp<G>::operator() ;

    Arc operator()(Node s, Node t, Arc prev) const

    {

      return prev==INVALID?(*this)(s,t):_next[prev];

    }

#endif

  };

  /// @}

} //namespace lemon

#endif

    }

    ///The type of the map that stores the distances of the nodes.

    ///The type of the map that stores the distances of the nodes.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a DistMap.

    ///\param g is the digraph, to which we would like to define

    ///the DistMap

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

    ///The type of the DFS paths.

    ///The type of the DFS paths.

    ///It must meet the \ref concepts::Path "Path" concept.

    typedef lemon::Path<Digraph> Path;

  };

  /// To make it easier to use Dfs algorithm

  /// we have created a wizard class.

  /// This \ref DfsWizard class needs default traits,

  /// as well as the \ref Dfs class.

  /// The \ref DfsWizardBase is a class to be the default traits of the

  /// \ref DfsWizard class.

  template<class GR>

  class DfsWizardBase : public DfsWizardDefaultTraits<GR>

  {

    typedef DfsWizardDefaultTraits<GR> Base;

  protected:

    //The type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

    //Pointer to the digraph the algorithm runs on.

    void *_g;

    //Pointer to the map of reached nodes.

    void *_reached;

    //Pointer to the map of processed nodes.

    void *_processed;

    //Pointer to the map of predecessors arcs.

    void *_pred;

      {

        return new Heap(R);

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///heap and cross reference type with automatic allocation

    ///

    ///\ref named-templ-param "Named parameter" for setting heap and cross

    ///reference type. It can allocate the heap and the cross reference

    ///object if the cross reference's constructor waits for the digraph as

    ///parameter and the heap's constructor waits for the cross reference.

    template <class H, class CR = typename Digraph::template NodeMap<int> >

    struct SetStandardHeap

      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {

      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >

      Create;

    };

    template <class T>

    struct SetOperationTraitsTraits : public Traits {

      typedef T OperationTraits;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\ref OperationTraits type.

    template <class T>

    struct SetOperationTraits

      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {

      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >

      Create;

    };

    ///@}

  protected:

    Dijkstra() {}

  public:

    ///Constructor.

    ///Constructor.

    ///\param _g The digraph the algorithm runs on.

    ///\param _length The length map used by the algorithm.

    Dijkstra(const Digraph& _g, const LengthMap& _length) :

    }

    ///The type of the map that stores the distances of the nodes.

    ///The type of the map that stores the distances of the nodes.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a DistMap.

    ///\param g is the digraph, to which we would like to define

    ///the DistMap

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

    ///The type of the shortest paths.

    ///The type of the shortest paths.

    ///It must meet the \ref concepts::Path "Path" concept.

    typedef lemon::Path<Digraph> Path;

  };

  /// To make it easier to use Dijkstra algorithm

  /// we have created a wizard class.

  /// This \ref DijkstraWizard class needs default traits,

  /// as well as the \ref Dijkstra class.

  /// The \ref DijkstraWizardBase is a class to be the default traits of the

  /// \ref DijkstraWizard class.

  template<class GR,class LM>

  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>

  {

    typedef DijkstraWizardDefaultTraits<GR,LM> Base;

  protected:

    //The type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

    //Pointer to the digraph the algorithm runs on.

    void *_g;

    //Pointer to the length map.

    void *_length;

    //Pointer to the map of processed nodes.

    void *_processed;

    //Pointer to the map of predecessors arcs.

    void *_pred;

    //Pointer to the map of distances.

  ///Rotate by 180 degrees

  ///Returns the parameter rotated by 180 degrees.

  ///\relates Point

  ///

  template<typename T>

  inline Point<T> rot180(const Point<T> &z)

  {

    return Point<T>(-z.x,-z.y);

  }

  ///Rotate by 270 degrees

  ///Returns the parameter rotated by 90 degrees in negative direction.

  ///\relates Point

  ///

  template<typename T>

  inline Point<T> rot270(const Point<T> &z)

  {

    return Point<T>(z.y,-z.x);

  }

  /// A class to calculate or store the bounding box of plain vectors

  template<typename T>

  class Box {

      Point<T> _bottom_left, _top_right;

      bool _empty;

    public:

      ///Default constructor: creates an empty box

      Box() { _empty = true; }

      ///Construct a box from one point

      Box(Point<T> a) {

        _bottom_left = _top_right = a;

        _empty = false;

      }

      ///Construct a box from two points

      ///Construct a box from two points.

      ///\param a The bottom left corner.

      ///\param b The top right corner.

      ///\warning The coordinates of the bottom left corner must be no more

      ///than those of the top right one.

      Box(Point<T> a,Point<T> b)

      {

    } else {

      is.clear();

    }

    if (!(is >> p)) return is;

    b.topRight(p);

    if (is >> c) {

      if (c != ')') is.putback(c);

    } else {

      is.clear();

    }

    return is;

  }

  ///Write a box to a stream

  ///Write a box to a stream.

  ///\relates Box

  template<typename T>

  inline std::ostream& operator<<(std::ostream &os, const Box<T>& b)

  {

    os << "(" << b.bottomLeft() << "," << b.topRight() << ")";

    return os;

  }

  ///\ingroup maps

  template<class M>

  class XMap

  {

    M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    XMap(M& map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].x;}

    void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}

  };

  ///

  ///\ingroup maps

  ///\relates XMap

  template<class M>

  inline XMap<M> xMap(M &m)

  {

    return XMap<M>(m);

  }

  template<class M>

  inline XMap<M> xMap(const M &m)

  {

    return XMap<M>(m);

  }

  ///\ingroup maps

  template<class M>

  class ConstXMap

  {

    const M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    ConstXMap(const M &map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].x;}

  };

  ///

  ///\ingroup maps

  ///\relates ConstXMap

  template<class M>

  inline ConstXMap<M> xMap(const M &m)

  {

    return ConstXMap<M>(m);

  }

  ///\ingroup maps

  template<class M>

  class YMap

  {

    M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    YMap(M& map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].y;}

    void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}

  };

  ///

  ///\ingroup maps

  ///\relates YMap

  template<class M>

  inline YMap<M> yMap(M &m)

  {

    return YMap<M>(m);

  }

  template<class M>

  inline YMap<M> yMap(const M &m)

  {

    return YMap<M>(m);

  }

  ///\ingroup maps

  template<class M>

  class ConstYMap

  {

    const M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    ConstYMap(const M &map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].y;}

  };

  ///

  ///\ingroup maps

  ///\relates ConstYMap

  template<class M>

  inline ConstYMap<M> yMap(const M &m)

  {

    return ConstYMap<M>(m);

  }

  ///

  ///Map of the \ref Point::normSquare() "normSquare()"

  ///of a \ref Point "Point"-map.

  ///\ingroup maps

  template<class M>

  class NormSquareMap

  {

    const M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    NormSquareMap(const M &map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].normSquare();}

  };

  ///

  ///\ingroup maps

  ///\relates NormSquareMap

  template<class M>

  inline NormSquareMap<M> normSquareMap(const M &m)

  {

    return NormSquareMap<M>(m);

  }

  /// @}

  } //namespce dim2

} //namespace lemon

#endif //LEMON_DIM2_H

#include<lemon/color.h>

#include<lemon/bits/bezier.h>

#include<lemon/error.h>

///\ingroup eps_io

///\file

///\brief A well configurable tool for visualizing graphs

namespace lemon {

  namespace _graph_to_eps_bits {

    template<class MT>

    class _NegY {

    public:

      typedef typename MT::Key Key;

      typedef typename MT::Value Value;

      const MT ↦

      int yscale;

      _NegY(const MT &m,bool b) : map(m), yscale(1-b*2) {}

      Value operator[](Key n) { return Value(map[n].x,map[n].y*yscale);}

    };

  }

///Default traits class of \ref GraphToEps.

///

///\c G is the type of the underlying graph.

template<class G>

struct DefaultGraphToEpsTraits

{

  typedef G Graph;

  typedef typename Graph::Node Node;

  typedef typename Graph::NodeIt NodeIt;

  typedef typename Graph::Arc Arc;

  typedef typename Graph::ArcIt ArcIt;

  typedef typename Graph::InArcIt InArcIt;

  typedef typename Graph::OutArcIt OutArcIt;

  const Graph &g;

  std::ostream& os;

  typedef ConstMap<typename Graph::Node,dim2::Point<double> > CoordsMapType;

  CoordsMapType _coords;

  ConstMap<typename Graph::Node,double > _nodeSizes;

  ConstMap<typename Graph::Node,int > _nodeShapes;

    ///

    /// \warning An Arc pointing to a removed item

    /// could become valid again later if new nodes are

    /// added to the graph.

    bool valid(Arc a) const { return Parent::valid(a); }

    /// Change the target of \c a to \c n

    /// Change the target of \c a to \c n

    ///

    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing

    ///the changed arc remain valid. However <tt>InArcIt</tt>s are

    ///invalidated.

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void changeTarget(Arc a, Node n) {

      Parent::changeTarget(a,n);

    }

    /// Change the source of \c a to \c n

    /// Change the source of \c a to \c n

    ///

    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain

    ///invalidated.

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void changeSource(Arc a, Node n) {

      Parent::changeSource(a,n);

    }

    /// Invert the direction of an arc.

    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain

    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are

    ///invalidated.

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void reverseArc(Arc e) {

      Node t=target(e);

      changeTarget(e,source(e));

      changeSource(e,t);

    }

    /// Reserve memory for nodes.

#include <iterator>

#include <functional>

#include <vector>

#include <lemon/core.h>

///\file

///\ingroup maps

///\brief Miscellaneous property maps

#include <map>

namespace lemon {

  /// \addtogroup maps

  /// @{

  /// Base class of maps.

  /// Base class of maps. It provides the necessary type definitions

  /// required by the map %concepts.

  template<typename K, typename V>

  class MapBase {

  public:

    typedef K Key;

    /// \brief The value type of the map.

    /// (The type of objects associated with the keys).

    typedef V Value;

  };

  /// Null map. (a.k.a. DoNothingMap)

  /// This map can be used if you have to provide a map only for

  /// its type definitions, or if you have to provide a writable map,

  /// but data written to it is not required (i.e. it will be sent to

  /// <tt>/dev/null</tt>).

  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

  ///

  /// \sa ConstMap

  template<typename K, typename V>

  class NullMap : public MapBase<K, V> {

  public:

    typedef MapBase<K, V> Parent;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    /// Gives back a default constructed element.

    };

    /// \brief Gives back the inverse of the map.

    ///

    /// Gives back the inverse of the map.

    const InverseMap inverse() const {

      return InverseMap(*this);

    }

  };

  /// \brief Returns the source of the given arc.

  ///