RhodeCode

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

    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;

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

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

  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

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

    }

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

    }

    return is;

  }

  ///Write a plain vector to a stream

  ///Write a plain vector to a stream.

  ///\relates Point

  ///

  template<typename T>

  inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)

  {

    return os;

  }

  ///Rotate by 90 degrees

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

  ///\relates Point

  ///

  template<typename T>

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

  {

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

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

  }

      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;

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

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

}