RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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();

  Node n3=g.addNode();

  Node n4=g.addNode();

  Node n5=g.addNode();

  ListDigraph::NodeMap<Point> coords(g);

  ListDigraph::NodeMap<double> sizes(g);

  ListDigraph::NodeMap<int> colors(g);

  ListDigraph::NodeMap<int> shapes(g);

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

non-empty lines until the next section describes nodes of the

graph. Each line contains the values of the node maps

associated to the current node.

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

*/

}

//  LocalWords:  whitespace whitespaces

  /// alteration of the graph.

  ///

  /// This class provides an interface to the container. The \e first() and \e

  /// next() member functions make possible to iterate on the keys of the

  /// container. The \e id() function returns an integer id for each key.

  /// The \e maxId() function gives back an upper bound of the ids.

  ///

  /// For the proper functonality of this class, we should notify it

  /// 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

    /// \e erase().

    ///

    /// From the \e clear() and \e erase() function only this

    /// exception is allowed to throw. The exception immediatly

    /// detaches the current observer from the notifier. Because the

    /// \e clear() and \e erase() should not throw other exceptions

    /// it can be used to invalidate the observer.

    struct ImmediateDetach {};

  };

  // double

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, double> {

    typedef VectorMap<_Graph, _Item,  double> Map;

  };

  // 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;

    }

  };

}

#endif

  /// White color constant

  extern const Color WHITE;

  /// Black color constant

  extern const Color BLACK;

  /// Red color constant

  extern const Color RED;

  /// Green color constant

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

    Palette(bool have_white=false,int num=-1)

    {

      if (num==0) return;

      do {

        if(have_white) colors.push_back(Color(1,1,1));

        colors.push_back(Color(0,0,0));

        colors.push_back(Color(1,0,0));

      typedef typename Base::Edge Edge;

      /// The arc observer registry.

      typedef AlterationNotifier<AlterableGraphComponent, Edge>

      EdgeNotifier;

      /// \brief Gives back the arc alteration notifier.

      ///

      /// 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:

      /// \brief Copy constructor.

      ///

      /// Copy Constructor.

      GraphMap(const GraphMap&) : Parent() {}

      /// \brief Assign operator.

      ///

      /// Assign operator. It does not mofify the underlying graph,

    }

  public:

    ///Find an arc between two nodes.

    ///Find an arc between two nodes.

    ///\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];

            }

          }

        }

      } else {

        Arc a = p;

        if (_right[a] != INVALID) {

          a = _right[a];

          while (_left[a] != INVALID) {

            a = _left[a];

  public:

    ///Refresh the search data structure at a node.

    ///Build up the search database of node \c n.

    ///

    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>

    ///is the number of the outgoing arcs of \c n.

    void refresh(Node n)

    {

      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.

  ///

  ///\warning This class is static, so you should call refresh() (or at

  ///least refresh(Node)) to refresh this data structure whenever the

  ///digraph changes. This is a time consuming (superlinearly proportional

  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).

  ///

  ///\tparam G The type of the underlying digraph.

  ///

    ///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(_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

    ///Instantiates a ReachedMap.

    ///This function instantiates a ReachedMap.

    ///\param g is the digraph, to which

    ///we would like to define the ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &g)

    {

      return new ReachedMap(g);

    }

    ///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;

    //Pointer to the map of distances.

    void *_dist;

    //Pointer to the DFS path to the target node.

    void *_path;

    //Pointer to the distance of the target node.

    int *_di;

    public:

    template <class H, class CR>

    struct SetStandardHeapTraits : public Traits {

      typedef CR HeapCrossRef;

      typedef H Heap;

      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {

        return new HeapCrossRef(G);

      }

      static Heap *createHeap(HeapCrossRef &R)

      {

        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) :

      G(&_g), length(&_length),

      _pred(NULL), local_pred(false),

      _dist(NULL), local_dist(false),

      _processed(NULL), local_processed(false),

      _heap_cross_ref(NULL), local_heap_cross_ref(false),

      _heap(NULL), local_heap(false)

    { }

    ///we would like to define the ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

      return new ProcessedMap();

    }

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

    void *_dist;

    //Pointer to the shortest path to the target node.

    void *_path;

    //Pointer to the distance of the target node.

    void *_di;

  public:

    /// Constructor.

  ///\relates Point

  ///

  template<typename T>

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

  {

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

  }

  ///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)

      {

        _bottom_left = a;

        _top_right = b;

        _empty = false;

      }

      ///Construct a box from four numbers

      ///Construct a box from four numbers.

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

    } else {

      is.clear();

    }

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

    b.bottomLeft(p);

    if (is >> c) {

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

    } 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();}

  };