# HG changeset patch # User Alpar Juttner # Date 1220989965 -3600 # Node ID 0310c8984732b7dcf2afaa6eecdb74f936b550e8 # Parent 8d76a7bf9961cee39791b621a71b8abb914f86c5# Parent c760d691fe3c47f3f57ee31f18f5aa5ae6fcf965 Merge diff -r 8d76a7bf9961 -r 0310c8984732 lemon/bfs.h --- a/lemon/bfs.h Mon Sep 01 22:00:40 2008 +0200 +++ b/lemon/bfs.h Tue Sep 09 20:52:45 2008 +0100 @@ -1261,6 +1261,11 @@ /// class. It works with callback mechanism, the BfsVisit object calls /// the member functions of the \c Visitor class on every BFS event. /// + /// This interface of the BFS algorithm should be used in special cases + /// when extra actions have to be performed in connection with certain + /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs() + /// instead. + /// /// \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 diff -r 8d76a7bf9961 -r 0310c8984732 lemon/bits/base_extender.h --- a/lemon/bits/base_extender.h Mon Sep 01 22:00:40 2008 +0200 +++ b/lemon/bits/base_extender.h Tue Sep 09 20:52:45 2008 +0100 @@ -59,7 +59,7 @@ public: Arc() {} - /// Invalid arc constructor + // Invalid arc constructor Arc(Invalid i) : Edge(i), forward(true) {} bool operator==(const Arc &that) const { @@ -74,38 +74,41 @@ } }; + /// First node of the edge + Node u(const Edge &e) const { + return Parent::source(e); + } - - using Parent::source; - - /// Source of the given Arc. + /// Source of the given arc Node source(const Arc &e) const { return e.forward ? Parent::source(e) : Parent::target(e); } - using Parent::target; + /// Second node of the edge + Node v(const Edge &e) const { + return Parent::target(e); + } - /// Target of the given Arc. + /// Target of the given arc Node target(const Arc &e) const { return e.forward ? Parent::target(e) : Parent::source(e); } /// \brief Directed arc from an edge. /// - /// Returns a directed arc corresponding to the specified Edge. - /// If the given bool is true the given edge and the - /// returned arc have the same source node. - static Arc direct(const Edge &ue, bool d) { - return Arc(ue, d); + /// Returns a directed arc corresponding to the specified edge. + /// If the given bool is true, the first node of the given edge and + /// the source node of the returned arc are the same. + static Arc direct(const Edge &e, bool d) { + return Arc(e, d); } - /// Returns whether the given directed arc is same orientation as the - /// corresponding edge. + /// Returns whether the given directed arc has the same orientation + /// as the corresponding edge. /// /// \todo reference to the corresponding point of the undirected digraph /// concept. "What does the direction of an edge mean?" - static bool direction(const Arc &e) { return e.forward; } - + static bool direction(const Arc &a) { return a.forward; } using Parent::first; using Parent::next; @@ -229,7 +232,6 @@ return Parent::maxArcId(); } - int arcNum() const { return 2 * Parent::arcNum(); } diff -r 8d76a7bf9961 -r 0310c8984732 lemon/dfs.h --- a/lemon/dfs.h Mon Sep 01 22:00:40 2008 +0200 +++ b/lemon/dfs.h Tue Sep 09 20:52:45 2008 +0100 @@ -1208,6 +1208,11 @@ /// class. It works with callback mechanism, the DfsVisit object calls /// the member functions of the \c Visitor class on every DFS event. /// + /// This interface of the DFS algorithm should be used in special cases + /// when extra actions have to be performed in connection with certain + /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs() + /// instead. + /// /// \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 diff -r 8d76a7bf9961 -r 0310c8984732 lemon/dijkstra.h --- a/lemon/dijkstra.h Mon Sep 01 22:00:40 2008 +0200 +++ b/lemon/dijkstra.h Tue Sep 09 20:52:45 2008 +0100 @@ -1067,6 +1067,8 @@ 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. @@ -1079,7 +1081,7 @@ /// This constructor does not require parameters, therefore it initiates /// all of the attributes to default values (0, INVALID). - DijkstraWizardBase() : _g(0), _length(0), _pred(0), + DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0), _dist(0), _source(INVALID) {} /// Constructor. @@ -1093,7 +1095,7 @@ DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : _g(reinterpret_cast(const_cast(&g))), _length(reinterpret_cast(const_cast(&l))), - _pred(0), _dist(0), _source(s) {} + _processed(0), _pred(0), _dist(0), _source(s) {} }; @@ -1172,8 +1174,12 @@ Dijkstra dij(*reinterpret_cast(Base::_g), *reinterpret_cast(Base::_length)); - if(Base::_pred) dij.predMap(*reinterpret_cast(Base::_pred)); - if(Base::_dist) dij.distMap(*reinterpret_cast(Base::_dist)); + if(Base::_processed) + dij.processedMap(*reinterpret_cast(Base::_processed)); + if(Base::_pred) + dij.predMap(*reinterpret_cast(Base::_pred)); + if(Base::_dist) + dij.distMap(*reinterpret_cast(Base::_dist)); dij.run(Base::_source); } diff -r 8d76a7bf9961 -r 0310c8984732 lemon/dim2.h --- a/lemon/dim2.h Mon Sep 01 22:00:40 2008 +0200 +++ b/lemon/dim2.h Tue Sep 09 20:52:45 2008 +0100 @@ -28,8 +28,7 @@ /// The class \ref lemon::dim2::Point "dim2::Point" implements /// a two dimensional vector with the usual operations. /// -/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox" -/// can be used to determine +/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine /// the rectangular bounding box of a set of /// \ref lemon::dim2::Point "dim2::Point"'s. @@ -44,7 +43,7 @@ /// \addtogroup misc /// @{ - /// A simple two dimensional vector (plain vector) implementation + /// Two dimensional vector (plain vector) /// A simple two dimensional vector (plain vector) implementation /// with the usual vector operations. @@ -221,7 +220,7 @@ template inline std::ostream& operator<<(std::ostream &os, const Point& z) { - os << "(" << z.x << ", " << z.y << ")"; + os << "(" << z.x << "," << z.y << ")"; return os; } @@ -260,67 +259,67 @@ - /// A class to calculate or store the bounding box of plain vectors. + /// Bounding box of plain vectors (\ref Point points). - /// A class to calculate or store the bounding box of plain vectors. - /// - template - class BoundingBox { + /// A class to calculate or store the bounding box of plain vectors + /// (\ref Point points). + template + class Box { Point _bottom_left, _top_right; bool _empty; public: - ///Default constructor: creates an empty bounding box - BoundingBox() { _empty = true; } + ///Default constructor: creates an empty box + Box() { _empty = true; } - ///Construct an instance from one point - BoundingBox(Point a) { + ///Construct a box from one point + Box(Point a) { _bottom_left = _top_right = a; _empty = false; } - ///Construct an instance from two points + ///Construct a box from two points - ///Construct an instance 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. - BoundingBox(Point a,Point b) + Box(Point a,Point b) { _bottom_left = a; _top_right = b; _empty = false; } - ///Construct an instance from four numbers + ///Construct a box from four numbers - ///Construct an instance from four numbers. + ///Construct a box from four numbers. ///\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. - BoundingBox(T l,T b,T r,T t) + Box(T l,T b,T r,T t) { _bottom_left=Point(l,b); _top_right=Point(r,t); _empty = false; } - ///Return \c true if the bounding box is empty. + ///Return \c true if the box is empty. - ///Return \c true if the bounding box is empty (i.e. return \c false + ///Return \c true if the box is empty (i.e. return \c false ///if at least one point was added to the box or the coordinates of ///the box were set). /// - ///The coordinates of an empty bounding box are not defined. + ///The coordinates of an empty box are not defined. bool empty() const { return _empty; } - ///Make the BoundingBox empty + ///Make the box empty void clear() { _empty = true; } @@ -328,7 +327,7 @@ ///Give back the bottom left corner of the box ///Give back the bottom left corner of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. Point bottomLeft() const { return _bottom_left; } @@ -344,7 +343,7 @@ ///Give back the top right corner of the box ///Give back the top right corner of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. Point topRight() const { return _top_right; } @@ -360,7 +359,7 @@ ///Give back the bottom right corner of the box ///Give back the bottom right corner of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. Point bottomRight() const { return Point(_top_right.x,_bottom_left.y); } @@ -377,7 +376,7 @@ ///Give back the top left corner of the box ///Give back the top left corner of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. Point topLeft() const { return Point(_bottom_left.x,_top_right.y); } @@ -394,7 +393,7 @@ ///Give back the bottom of the box ///Give back the bottom of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. T bottom() const { return _bottom_left.y; } @@ -410,7 +409,7 @@ ///Give back the top of the box ///Give back the top of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. T top() const { return _top_right.y; } @@ -426,7 +425,7 @@ ///Give back the left side of the box ///Give back the left side of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. T left() const { return _bottom_left.x; } @@ -442,7 +441,7 @@ /// Give back the right side of the box /// Give back the right side of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. T right() const { return _top_right.x; } @@ -458,7 +457,7 @@ ///Give back the height of the box ///Give back the height of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. T height() const { return _top_right.y-_bottom_left.y; } @@ -466,12 +465,12 @@ ///Give back the width of the box ///Give back the width of the box. - ///If the bounding box is empty, then the return value is not defined. + ///If the box is empty, then the return value is not defined. T width() const { return _top_right.x-_bottom_left.x; } - ///Checks whether a point is inside a bounding box + ///Checks whether a point is inside the box bool inside(const Point& u) const { if (_empty) return false; @@ -481,11 +480,11 @@ } } - ///Increments a bounding box with a point + ///Increments the box with a point - ///Increments a bounding box with a point. + ///Increments the box with a point. /// - BoundingBox& add(const Point& u){ + Box& add(const Point& u){ if (_empty) { _bottom_left = _top_right = u; _empty = false; @@ -499,11 +498,11 @@ return *this; } - ///Increments a bounding box to contain another bounding box + ///Increments the box to contain another box - ///Increments a bounding box to contain another bounding box. + ///Increments the box to contain another box. /// - BoundingBox& add(const BoundingBox &u){ + Box& add(const Box &u){ if ( !u.empty() ){ add(u._bottom_left); add(u._top_right); @@ -511,12 +510,12 @@ return *this; } - ///Intersection of two bounding boxes + ///Intersection of two boxes - ///Intersection of two bounding boxes. + ///Intersection of two boxes. /// - BoundingBox operator&(const BoundingBox& u) const { - BoundingBox b; + Box operator&(const Box& u) const { + Box b; if (_empty || u._empty) { b._empty = true; } else { @@ -530,9 +529,50 @@ return b; } - };//class Boundingbox + };//class Box + ///Read a box from a stream + + ///Read a box from a stream. + ///\relates Box + template + inline std::istream& operator>>(std::istream &is, Box& b) { + char c; + Point p; + if (is >> c) { + 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 + inline std::ostream& operator<<(std::ostream &os, const Box& b) + { + os << "(" << b.bottomLeft() << "," << b.topRight() << ")"; + return os; + } + ///Map of x-coordinates of a \ref Point "Point"-map ///\ingroup maps diff -r 8d76a7bf9961 -r 0310c8984732 lemon/graph_to_eps.h --- a/lemon/graph_to_eps.h Mon Sep 01 22:00:40 2008 +0200 +++ b/lemon/graph_to_eps.h Tue Sep 09 20:52:45 2008 +0100 @@ -725,10 +725,10 @@ double diag_len = 1; if(!(_absoluteNodeSizes&&_absoluteArcWidths)) { - dim2::BoundingBox bb; + dim2::Box bb; for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]); if (bb.empty()) { - bb = dim2::BoundingBox(dim2::Point(0,0)); + bb = dim2::Box(dim2::Point(0,0)); } diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare()); if(diag_len bb; + dim2::Box bb; for(NodeIt n(g);n!=INVALID;++n) { double ns=_nodeSizes[n]*_nodeScale; dim2::Point p(ns,ns); @@ -758,7 +758,7 @@ } } if (bb.empty()) { - bb = dim2::BoundingBox(dim2::Point(0,0)); + bb = dim2::Box(dim2::Point(0,0)); } if(_scaleToA4) diff -r 8d76a7bf9961 -r 0310c8984732 test/dim_test.cc --- a/test/dim_test.cc Mon Sep 01 22:00:40 2008 +0200 +++ b/test/dim_test.cc Tue Sep 09 20:52:45 2008 +0100 @@ -50,38 +50,38 @@ p = b/l; check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar."); - typedef dim2::BoundingBox BB; - BB box1; - check(box1.empty(), "Wrong empty() in dim2::BoundingBox."); + typedef dim2::Box Box; + Box box1; + check(box1.empty(), "Wrong empty() in dim2::Box."); box1.add(a); - check(!box1.empty(), "Wrong empty() in dim2::BoundingBox."); + check(!box1.empty(), "Wrong empty() in dim2::Box."); box1.add(b); check(box1.left()==1 && box1.bottom()==2 && box1.right()==3 && box1.top()==4, - "Wrong addition of points to dim2::BoundingBox."); + "Wrong addition of points to dim2::Box."); - check(box1.inside(Point(2,3)), "Wrong inside() in dim2::BoundingBox."); - check(box1.inside(Point(1,3)), "Wrong inside() in dim2::BoundingBox."); - check(!box1.inside(Point(0,3)), "Wrong inside() in dim2::BoundingBox."); + check(box1.inside(Point(2,3)), "Wrong inside() in dim2::Box."); + check(box1.inside(Point(1,3)), "Wrong inside() in dim2::Box."); + check(!box1.inside(Point(0,3)), "Wrong inside() in dim2::Box."); - BB box2(Point(2,2)); - check(!box2.empty(), "Wrong empty() in dim2::BoundingBox."); - + Box box2(Point(2,2)); + check(!box2.empty(), "Wrong empty() in dim2::Box."); + box2.bottomLeft(Point(2,0)); box2.topRight(Point(5,3)); - BB box3 = box1 & box2; + Box box3 = box1 & box2; check(!box3.empty() && - box3.left()==2 && box3.bottom()==2 && + box3.left()==2 && box3.bottom()==2 && box3.right()==3 && box3.top()==3, - "Wrong intersection of two dim2::BoundingBox objects."); - + "Wrong intersection of two dim2::Box objects."); + box1.add(box2); check(!box1.empty() && box1.left()==1 && box1.bottom()==0 && box1.right()==5 && box1.top()==4, - "Wrong addition of two dim2::BoundingBox objects."); + "Wrong addition of two dim2::Box objects."); return 0; }