RhodeCode

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a \ref ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap.

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

    /// we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief %BFS algorithm class with visitor interface.

  ///

  /// This class provides an efficient implementation of the %BFS algorithm

  /// with visitor interface.

  ///

  /// The %BfsVisit class provides an alternative interface to the Bfs

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// the member functions of the \c Visitor class on every BFS event.

  ///

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  /// The default value is

  /// \ref ListDigraph. The value of _Digraph is not used directly by

  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.

  /// \tparam _Visitor The Visitor type that is used by the algorithm.

  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which

  /// does not observe the BFS events. If you want to observe the BFS

  /// events, you should implement your own visitor class.

  /// \tparam _Traits Traits class to set various data types used by the

  /// algorithm. The default traits class is

  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".

  /// See \ref BfsVisitDefaultTraits for the documentation of

  /// a BFS visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

            typename _Visitor = BfsVisitor<_Digraph>,

            typename _Traits = BfsDefaultTraits<_Digraph> >

#endif

  class BfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

  /// \brief BaseDigraph to BaseGraph extender

  template <typename Base>

  class UndirDigraphExtender : public Base {

  public:

    typedef Base Parent;

    typedef typename Parent::Arc Edge;

    typedef typename Parent::Node Node;

    typedef True UndirectedTag;

    class Arc : public Edge {

      friend class UndirDigraphExtender;

    protected:

      bool forward;

      Arc(const Edge &ue, bool _forward) :

        Edge(ue), forward(_forward) {}

    public:

      Arc() {}

      Arc(Invalid i) : Edge(i), forward(true) {}

      bool operator==(const Arc &that) const {

        return forward==that.forward && Edge(*this)==Edge(that);

      }

      bool operator!=(const Arc &that) const {

        return forward!=that.forward || Edge(*this)!=Edge(that);

      }

      bool operator<(const Arc &that) const {

        return forward<that.forward ||

          (!(that.forward<forward) && Edge(*this)<Edge(that));

      }

    };

    Node source(const Arc &e) const {

      return e.forward ? Parent::source(e) : Parent::target(e);

    }

    Node target(const Arc &e) const {

      return e.forward ? Parent::target(e) : Parent::source(e);

    }

    /// \brief Directed arc from an edge.

    ///

    }

    ///

    /// \todo reference to the corresponding point of the undirected digraph

    /// concept. "What does the direction of an edge mean?"

    using Parent::first;

    using Parent::next;

    void first(Arc &e) const {

      Parent::first(e);

      e.forward=true;

    }

    void next(Arc &e) const {

      if( e.forward ) {

        e.forward = false;

      }

      else {

        Parent::next(e);

        e.forward = true;

      }

    }

    void firstOut(Arc &e, const Node &n) const {

      Parent::firstIn(e,n);

      if( Edge(e) != INVALID ) {

        e.forward = false;

      }

    int id(const Node &n) const {

      return Parent::id(n);

    }

    int id(const Edge &e) const {

      return Parent::id(e);

    }

    int id(const Arc &e) const {

      return 2 * Parent::id(e) + int(e.forward);

    }

    int maxNodeId() const {

      return Parent::maxNodeId();

    }

    int maxArcId() const {

      return 2 * Parent::maxArcId() + 1;

    }

    int maxEdgeId() const {

      return Parent::maxArcId();

    }

    int arcNum() const {

      return 2 * Parent::arcNum();

    }

    int edgeNum() const {

      return Parent::arcNum();

    }

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

      if (p == INVALID) {

        Edge arc = Parent::findArc(s, t);

        if (arc != INVALID) return direct(arc, true);

        arc = Parent::findArc(t, s);

        if (arc != INVALID) return direct(arc, false);

      } else if (direction(p)) {

        Edge arc = Parent::findArc(s, t, p);

        if (arc != INVALID) return direct(arc, true);

        arc = Parent::findArc(t, s);

        if (arc != INVALID) return direct(arc, false);

      } else {

        Edge arc = Parent::findArc(t, s, p);

        if (arc != INVALID) return direct(arc, false);

      }

      return INVALID;

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a \ref ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap.

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

    /// we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief %DFS algorithm class with visitor interface.

  ///

  /// This class provides an efficient implementation of the %DFS algorithm

  /// with visitor interface.

  ///

  /// The %DfsVisit class provides an alternative interface to the Dfs

  /// class. It works with callback mechanism, the DfsVisit object calls

  /// the member functions of the \c Visitor class on every DFS event.

  ///

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  /// The default value is

  /// \ref ListDigraph. The value of _Digraph is not used directly by

  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.

  /// \tparam _Visitor The Visitor type that is used by the algorithm.

  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which

  /// does not observe the DFS events. If you want to observe the DFS

  /// events, you should implement your own visitor class.

  /// \tparam _Traits Traits class to set various data types used by the

  /// algorithm. The default traits class is

  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".

  /// See \ref DfsVisitDefaultTraits for the documentation of

  /// a DFS visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

            typename _Visitor = DfsVisitor<_Digraph>,

            typename _Traits = DfsDefaultTraits<_Digraph> >

#endif

  class DfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

    }

  };

  /// Default traits class used by \ref DijkstraWizard

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

  /// \todo More named parameters are required...

  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 predecessors arcs.

    void *_pred;

    //Pointer to the map of distances.

    void *_dist;

    //Pointer to the source node.

    Node _source;

  public:

    /// Constructor.

    /// This constructor does not require parameters, therefore it initiates

    /// all of the attributes to default values (0, INVALID).

                           _dist(0), _source(INVALID) {}

    /// Constructor.

    /// This constructor requires some parameters,

    /// listed in the parameters list.

    /// Others are initiated to 0.

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

    /// \param l The length map.

    /// \param s The source node.

    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :

      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),

      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),

  };

  /// Auxiliary class for the function type interface of Dijkstra algorithm.

  /// This auxiliary class is created to implement the function type

  /// interface of \ref Dijkstra algorithm. It uses the functions and features

  /// of the plain \ref Dijkstra, but it is much simpler to use it.

  /// It should only be used through the \ref dijkstra() function, which makes

  /// it easier to use the algorithm.

  ///

  /// Simplicity means that the way to change the types defined

  /// in the traits class is based on functions that returns the new class

  /// and not on templatable built-in classes.

  /// When using the plain \ref Dijkstra

  /// the new class with the modified type comes from

  /// the original class by using the ::

  /// operator. In the case of \ref DijkstraWizard only

  /// a function have to be called, and it will

  /// return the needed class.

  ///

  /// It does not have own \ref run() method. When its \ref run() method

  /// is called, it initiates a plain \ref Dijkstra object, and calls the

  /// \ref Dijkstra::run() method of it.

    DijkstraWizard() : TR() {}

    /// Constructor that requires parameters.

    /// Constructor that requires parameters.

    /// These parameters will be the default values for the traits class.

    DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :

      TR(g,l,s) {}

    ///Copy constructor

    DijkstraWizard(const TR &b) : TR(b) {}

    ~DijkstraWizard() {}

    ///Runs Dijkstra algorithm from a source node.

    ///Runs Dijkstra algorithm from a source node.

    ///The node can be given with the \ref source() function.

    void run()

    {

      if(Base::_source==INVALID) throw UninitializedParameter();

      Dijkstra<Digraph,LengthMap,TR>

        dij(*reinterpret_cast<const Digraph*>(Base::_g),

            *reinterpret_cast<const LengthMap*>(Base::_length));

      dij.run(Base::_source);

    }

    ///Runs Dijkstra algorithm from the given node.

    ///Runs Dijkstra algorithm from the given node.

    ///\param s is the given source.

    void run(Node s)

    {

      Base::_source=s;

      run();

    }

    /// Sets the source node, from which the Dijkstra algorithm runs.

    /// Sets the source node, from which the Dijkstra algorithm runs.

    /// \param s is the source node.

    DijkstraWizard<TR> &source(Node s)

    {

      Base::_source=s;

      return *this;

    }

    template<class T>

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

 *

 */

#ifndef LEMON_DIM2_H

#define LEMON_DIM2_H

#include <iostream>

///\ingroup misc

///\file

///\brief A simple two dimensional vector and a bounding box implementation

///

/// The class \ref lemon::dim2::Point "dim2::Point" implements

/// a two dimensional vector with the usual operations.

///

/// the rectangular bounding box of a set of

/// \ref lemon::dim2::Point "dim2::Point"'s.

namespace lemon {

  ///Tools for handling two dimensional coordinates

  ///This namespace is a storage of several

  ///tools for handling two dimensional coordinates

  namespace dim2 {

  /// \addtogroup misc

  /// @{

  /// A simple two dimensional vector (plain vector) implementation

  /// with the usual vector operations.

  template<typename T>

    class Point {

    public:

      typedef T Value;

      ///First coordinate

      T x;

      ///Second coordinate

      T y;

      ///Default constructor

      Point() {}

      ///Construct an instance from coordinates

      Point(T a, T b) : x(a), y(b) { }

      ///Returns the dimension of the vector (i.e. returns 2).

      ///The dimension of the vector.

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

  }

    template<typename T>

      Point<T> _bottom_left, _top_right;

      bool _empty;

    public:

        _bottom_left = _top_right = a;

        _empty = false;

      }

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

      {

        _bottom_left = a;

        _top_right = b;

        _empty = false;

      }

      ///\param l The left side of the box.

      ///\param b The bottom of the box.

      ///\param r The right side of the box.

      ///\param t The top of the box.

      ///\warning The left side must be no more than the right side and

      ///bottom must be no more than the top.

      {

        _bottom_left=Point<T>(l,b);

        _top_right=Point<T>(r,t);

        _empty = false;

      }

      ///if at least one point was added to the box or the coordinates of

      ///the box were set).

      ///

      bool empty() const {

        return _empty;

      }

      void clear() {

        _empty = true;

      }

      ///Give back the bottom left corner of the box

      ///Give back the bottom left corner of the box.

      Point<T> bottomLeft() const {

        return _bottom_left;

      }

      ///Set the bottom left corner of the box

      ///Set the bottom left corner of the box.

      ///\pre The box must not be empty.

      void bottomLeft(Point<T> p) {

        _bottom_left = p;

      }

      ///Give back the top right corner of the box

      ///Give back the top right corner of the box.

      Point<T> topRight() const {

        return _top_right;

      }

      ///Set the top right corner of the box

      ///Set the top right corner of the box.

      ///\pre The box must not be empty.

      void topRight(Point<T> p) {

        _top_right = p;

      }

      ///Give back the bottom right corner of the box

      ///Give back the bottom right corner of the box.

      Point<T> bottomRight() const {

        return Point<T>(_top_right.x,_bottom_left.y);

      }

      ///Set the bottom right corner of the box

      ///Set the bottom right corner of the box.

      ///\pre The box must not be empty.

      void bottomRight(Point<T> p) {

        _top_right.x = p.x;

        _bottom_left.y = p.y;

      }

      ///Give back the top left corner of the box

      ///Give back the top left corner of the box.

      Point<T> topLeft() const {

        return Point<T>(_bottom_left.x,_top_right.y);

      }

      ///Set the top left corner of the box

      ///Set the top left corner of the box.

      ///\pre The box must not be empty.

      void topLeft(Point<T> p) {

        _top_right.y = p.y;

        _bottom_left.x = p.x;

      }

      ///Give back the bottom of the box

      ///Give back the bottom of the box.

      T bottom() const {

        return _bottom_left.y;

      }

      ///Set the bottom of the box

      ///Set the bottom of the box.

      ///\pre The box must not be empty.

      void bottom(T t) {

        _bottom_left.y = t;

      }

      ///Give back the top of the box

      ///Give back the top of the box.

      T top() const {

        return _top_right.y;

      }

      ///Set the top of the box

      ///Set the top of the box.

      ///\pre The box must not be empty.

      void top(T t) {

        _top_right.y = t;

      }

      ///Give back the left side of the box

      ///Give back the left side of the box.

      T left() const {

        return _bottom_left.x;

      }

      ///Set the left side of the box

      ///Set the left side of the box.

      ///\pre The box must not be empty.

      void left(T t) {

        _bottom_left.x = t;

      }

      /// Give back the right side of the box

      /// Give back the right side of the box.

      T right() const {

        return _top_right.x;

      }

      ///Set the right side of the box

      ///Set the right side of the box.

      ///\pre The box must not be empty.

      void right(T t) {

        _top_right.x = t;

      }

      ///Give back the height of the box

      ///Give back the height of the box.

      T height() const {

        return _top_right.y-_bottom_left.y;

      }

      ///Give back the width of the box

      ///Give back the width of the box.

      T width() const {

        return _top_right.x-_bottom_left.x;

      }

      bool inside(const Point<T>& u) const {

        if (_empty)

          return false;

        else {

          return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&

                   (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );

        }

      }

      ///

        if (_empty) {

          _bottom_left = _top_right = u;

          _empty = false;

        }

        else {

          if (_bottom_left.x > u.x) _bottom_left.x = u.x;

          if (_bottom_left.y > u.y) _bottom_left.y = u.y;

          if (_top_right.x < u.x) _top_right.x = u.x;

          if (_top_right.y < u.y) _top_right.y = u.y;

        }

        return *this;

      }

      ///

        if ( !u.empty() ){

          add(u._bottom_left);

          add(u._top_right);

        }

        return *this;

      }

      ///

        if (_empty || u._empty) {

          b._empty = true;

        } else {

          b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);

          b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);

          b._top_right.x = std::min(_top_right.x, u._top_right.x);

          b._top_right.y = std::min(_top_right.y, u._top_right.y);

          b._empty = b._bottom_left.x > b._top_right.x ||

                     b._bottom_left.y > b._top_right.y;

        }

        return b;

      }

  ///Map of x-coordinates of a \ref Point "Point"-map

  ///\ingroup maps

  ///Map of x-coordinates of a \ref Point "Point"-map.

  ///

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

  };

  ///Returns an \ref XMap class

  ///This function just returns an \ref XMap class.

  ///

  ///\ingroup maps

    }

    if (_autoArcWidthScale) {

      double max_w=0;

      for(ArcIt e(g);e!=INVALID;++e)

        max_w=std::max(double(_arcWidths[e]),max_w);

      //\todo better 'epsilon' would be nice here.

      if(max_w>EPSILON) {

        _arcWidthScale/=max_w;

      }

    }

    if (_autoNodeScale) {

      double max_s=0;

      for(NodeIt n(g);n!=INVALID;++n)

        max_s=std::max(double(_nodeSizes[n]),max_s);

      //\todo better 'epsilon' would be nice here.

      if(max_s>EPSILON) {

        _nodeScale/=max_s;

      }

    }

    double diag_len = 1;

    if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {

      for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);

      if (bb.empty()) {

      }

      diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());

      if(diag_len<EPSILON) diag_len = 1;

      if(!_absoluteNodeSizes) _nodeScale*=diag_len;

      if(!_absoluteArcWidths) _arcWidthScale*=diag_len;

    }

    for(NodeIt n(g);n!=INVALID;++n) {

      double ns=_nodeSizes[n]*_nodeScale;

      dim2::Point<double> p(ns,ns);

      switch(_nodeShapes[n]) {

      case CIRCLE:

      case SQUARE:

      case DIAMOND:

        bb.add(p+mycoords[n]);

        bb.add(-p+mycoords[n]);

        break;

      case MALE:

        bb.add(-p+mycoords[n]);

        bb.add(dim2::Point<double>(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]);

        break;

      case FEMALE:

        bb.add(p+mycoords[n]);

        bb.add(dim2::Point<double>(-ns,-3.01*ns)+mycoords[n]);

        break;

      }

    }

    if (bb.empty()) {

    }

    if(_scaleToA4)

      os <<"%%BoundingBox: 0 0 596 842\n%%DocumentPaperSizes: a4\n";

    else {

      if(_preScale) {

        //Rescale so that BoundingBox won't be neither to big nor too small.

        while(bb.height()*_scale>1000||bb.width()*_scale>1000) _scale/=10;

        while(bb.height()*_scale<100||bb.width()*_scale<100) _scale*=10;

      }

      os << "%%BoundingBox: "

         << int(floor(bb.left()   * _scale - _xBorder)) << ' '

         << int(floor(bb.bottom() * _scale - _yBorder)) << ' '

         << int(ceil(bb.right()  * _scale + _xBorder)) << ' '

         << int(ceil(bb.top()    * _scale + _yBorder)) << '\n';

    }

    os << "%%EndComments\n";

    //x1 y1 x2 y2 x3 y3 cr cg cb w

    os << "/lb { setlinewidth setrgbcolor newpath moveto\n"

       << "      4 2 roll 1 index 1 index curveto stroke } bind def\n";

    os << "/l { setlinewidth setrgbcolor newpath moveto lineto stroke }"

  Point p;

  check(p.size()==2, "Wrong dim2::Point initialization.");

  Point a(1,2);

  Point b(3,4);

  check(a[0]==1 && a[1]==2, "Wrong dim2::Point initialization.");

  p = a+b;

  check(p.x==4 && p.y==6, "Wrong dim2::Point addition.");

  p = a-b;

  check(p.x==-2 && p.y==-2, "Wrong dim2::Point subtraction.");

  check(a.normSquare()==5,"Wrong dim2::Point norm calculation.");

  check(a*b==11, "Wrong dim2::Point scalar product.");

  int l=2;

  p = a*l;

  check(p.x==2 && p.y==4, "Wrong dim2::Point multiplication by a scalar.");

  p = b/l;

  check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar.");

  box1.add(a);

  box1.add(b);

  check(box1.left()==1 && box1.bottom()==2 &&

        box1.right()==3 && box1.top()==4,

  box2.bottomLeft(Point(2,0));

  box2.topRight(Point(5,3));

  check(!box3.empty() &&

        box3.left()==2 && box3.bottom()==2 && 

        box3.right()==3 && box3.top()==3,

  box1.add(box2);

  check(!box1.empty() &&

        box1.left()==1 && box1.bottom()==0 &&

        box1.right()==5 && box1.top()==4,

  return 0;

}