RhodeCode

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

      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 {

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

    }

    int maxEdgeId() const {

      return Parent::maxArcId();

    }

    int arcNum() const {

      return 2 * Parent::arcNum();

    }

    int edgeNum() const {

      return Parent::arcNum();

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

    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.

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

    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.

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

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

  {

    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

        _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

        _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

        _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

        _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

        _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

        _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

        _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

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

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

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

  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;

}