1.1 --- a/lemon/bfs.h Mon Sep 01 22:00:40 2008 +0200
1.2 +++ b/lemon/bfs.h Tue Sep 09 20:52:45 2008 +0100
1.3 @@ -1261,6 +1261,11 @@
1.4 /// class. It works with callback mechanism, the BfsVisit object calls
1.5 /// the member functions of the \c Visitor class on every BFS event.
1.6 ///
1.7 + /// This interface of the BFS algorithm should be used in special cases
1.8 + /// when extra actions have to be performed in connection with certain
1.9 + /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1.10 + /// instead.
1.11 + ///
1.12 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.13 /// The default value is
1.14 /// \ref ListDigraph. The value of _Digraph is not used directly by
2.1 --- a/lemon/bits/base_extender.h Mon Sep 01 22:00:40 2008 +0200
2.2 +++ b/lemon/bits/base_extender.h Tue Sep 09 20:52:45 2008 +0100
2.3 @@ -59,7 +59,7 @@
2.4 public:
2.5 Arc() {}
2.6
2.7 - /// Invalid arc constructor
2.8 + // Invalid arc constructor
2.9 Arc(Invalid i) : Edge(i), forward(true) {}
2.10
2.11 bool operator==(const Arc &that) const {
2.12 @@ -74,38 +74,41 @@
2.13 }
2.14 };
2.15
2.16 + /// First node of the edge
2.17 + Node u(const Edge &e) const {
2.18 + return Parent::source(e);
2.19 + }
2.20
2.21 -
2.22 - using Parent::source;
2.23 -
2.24 - /// Source of the given Arc.
2.25 + /// Source of the given arc
2.26 Node source(const Arc &e) const {
2.27 return e.forward ? Parent::source(e) : Parent::target(e);
2.28 }
2.29
2.30 - using Parent::target;
2.31 + /// Second node of the edge
2.32 + Node v(const Edge &e) const {
2.33 + return Parent::target(e);
2.34 + }
2.35
2.36 - /// Target of the given Arc.
2.37 + /// Target of the given arc
2.38 Node target(const Arc &e) const {
2.39 return e.forward ? Parent::target(e) : Parent::source(e);
2.40 }
2.41
2.42 /// \brief Directed arc from an edge.
2.43 ///
2.44 - /// Returns a directed arc corresponding to the specified Edge.
2.45 - /// If the given bool is true the given edge and the
2.46 - /// returned arc have the same source node.
2.47 - static Arc direct(const Edge &ue, bool d) {
2.48 - return Arc(ue, d);
2.49 + /// Returns a directed arc corresponding to the specified edge.
2.50 + /// If the given bool is true, the first node of the given edge and
2.51 + /// the source node of the returned arc are the same.
2.52 + static Arc direct(const Edge &e, bool d) {
2.53 + return Arc(e, d);
2.54 }
2.55
2.56 - /// Returns whether the given directed arc is same orientation as the
2.57 - /// corresponding edge.
2.58 + /// Returns whether the given directed arc has the same orientation
2.59 + /// as the corresponding edge.
2.60 ///
2.61 /// \todo reference to the corresponding point of the undirected digraph
2.62 /// concept. "What does the direction of an edge mean?"
2.63 - static bool direction(const Arc &e) { return e.forward; }
2.64 -
2.65 + static bool direction(const Arc &a) { return a.forward; }
2.66
2.67 using Parent::first;
2.68 using Parent::next;
2.69 @@ -229,7 +232,6 @@
2.70 return Parent::maxArcId();
2.71 }
2.72
2.73 -
2.74 int arcNum() const {
2.75 return 2 * Parent::arcNum();
2.76 }
3.1 --- a/lemon/dfs.h Mon Sep 01 22:00:40 2008 +0200
3.2 +++ b/lemon/dfs.h Tue Sep 09 20:52:45 2008 +0100
3.3 @@ -1208,6 +1208,11 @@
3.4 /// class. It works with callback mechanism, the DfsVisit object calls
3.5 /// the member functions of the \c Visitor class on every DFS event.
3.6 ///
3.7 + /// This interface of the DFS algorithm should be used in special cases
3.8 + /// when extra actions have to be performed in connection with certain
3.9 + /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
3.10 + /// instead.
3.11 + ///
3.12 /// \tparam _Digraph The type of the digraph the algorithm runs on.
3.13 /// The default value is
3.14 /// \ref ListDigraph. The value of _Digraph is not used directly by
4.1 --- a/lemon/dijkstra.h Mon Sep 01 22:00:40 2008 +0200
4.2 +++ b/lemon/dijkstra.h Tue Sep 09 20:52:45 2008 +0100
4.3 @@ -1067,6 +1067,8 @@
4.4 void *_g;
4.5 //Pointer to the length map
4.6 void *_length;
4.7 + //Pointer to the map of processed nodes.
4.8 + void *_processed;
4.9 //Pointer to the map of predecessors arcs.
4.10 void *_pred;
4.11 //Pointer to the map of distances.
4.12 @@ -1079,7 +1081,7 @@
4.13
4.14 /// This constructor does not require parameters, therefore it initiates
4.15 /// all of the attributes to default values (0, INVALID).
4.16 - DijkstraWizardBase() : _g(0), _length(0), _pred(0),
4.17 + DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
4.18 _dist(0), _source(INVALID) {}
4.19
4.20 /// Constructor.
4.21 @@ -1093,7 +1095,7 @@
4.22 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
4.23 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
4.24 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
4.25 - _pred(0), _dist(0), _source(s) {}
4.26 + _processed(0), _pred(0), _dist(0), _source(s) {}
4.27
4.28 };
4.29
4.30 @@ -1172,8 +1174,12 @@
4.31 Dijkstra<Digraph,LengthMap,TR>
4.32 dij(*reinterpret_cast<const Digraph*>(Base::_g),
4.33 *reinterpret_cast<const LengthMap*>(Base::_length));
4.34 - if(Base::_pred) dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
4.35 - if(Base::_dist) dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
4.36 + if(Base::_processed)
4.37 + dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
4.38 + if(Base::_pred)
4.39 + dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
4.40 + if(Base::_dist)
4.41 + dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
4.42 dij.run(Base::_source);
4.43 }
4.44
5.1 --- a/lemon/dim2.h Mon Sep 01 22:00:40 2008 +0200
5.2 +++ b/lemon/dim2.h Tue Sep 09 20:52:45 2008 +0100
5.3 @@ -28,8 +28,7 @@
5.4 /// The class \ref lemon::dim2::Point "dim2::Point" implements
5.5 /// a two dimensional vector with the usual operations.
5.6 ///
5.7 -/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
5.8 -/// can be used to determine
5.9 +/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
5.10 /// the rectangular bounding box of a set of
5.11 /// \ref lemon::dim2::Point "dim2::Point"'s.
5.12
5.13 @@ -44,7 +43,7 @@
5.14 /// \addtogroup misc
5.15 /// @{
5.16
5.17 - /// A simple two dimensional vector (plain vector) implementation
5.18 + /// Two dimensional vector (plain vector)
5.19
5.20 /// A simple two dimensional vector (plain vector) implementation
5.21 /// with the usual vector operations.
5.22 @@ -221,7 +220,7 @@
5.23 template<typename T>
5.24 inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
5.25 {
5.26 - os << "(" << z.x << ", " << z.y << ")";
5.27 + os << "(" << z.x << "," << z.y << ")";
5.28 return os;
5.29 }
5.30
5.31 @@ -260,67 +259,67 @@
5.32
5.33
5.34
5.35 - /// A class to calculate or store the bounding box of plain vectors.
5.36 + /// Bounding box of plain vectors (\ref Point points).
5.37
5.38 - /// A class to calculate or store the bounding box of plain vectors.
5.39 - ///
5.40 - template<typename T>
5.41 - class BoundingBox {
5.42 + /// A class to calculate or store the bounding box of plain vectors
5.43 + /// (\ref Point points).
5.44 + template<typename T>
5.45 + class Box {
5.46 Point<T> _bottom_left, _top_right;
5.47 bool _empty;
5.48 public:
5.49
5.50 - ///Default constructor: creates an empty bounding box
5.51 - BoundingBox() { _empty = true; }
5.52 + ///Default constructor: creates an empty box
5.53 + Box() { _empty = true; }
5.54
5.55 - ///Construct an instance from one point
5.56 - BoundingBox(Point<T> a) {
5.57 + ///Construct a box from one point
5.58 + Box(Point<T> a) {
5.59 _bottom_left = _top_right = a;
5.60 _empty = false;
5.61 }
5.62
5.63 - ///Construct an instance from two points
5.64 + ///Construct a box from two points
5.65
5.66 - ///Construct an instance from two points.
5.67 + ///Construct a box from two points.
5.68 ///\param a The bottom left corner.
5.69 ///\param b The top right corner.
5.70 ///\warning The coordinates of the bottom left corner must be no more
5.71 ///than those of the top right one.
5.72 - BoundingBox(Point<T> a,Point<T> b)
5.73 + Box(Point<T> a,Point<T> b)
5.74 {
5.75 _bottom_left = a;
5.76 _top_right = b;
5.77 _empty = false;
5.78 }
5.79
5.80 - ///Construct an instance from four numbers
5.81 + ///Construct a box from four numbers
5.82
5.83 - ///Construct an instance from four numbers.
5.84 + ///Construct a box from four numbers.
5.85 ///\param l The left side of the box.
5.86 ///\param b The bottom of the box.
5.87 ///\param r The right side of the box.
5.88 ///\param t The top of the box.
5.89 ///\warning The left side must be no more than the right side and
5.90 ///bottom must be no more than the top.
5.91 - BoundingBox(T l,T b,T r,T t)
5.92 + Box(T l,T b,T r,T t)
5.93 {
5.94 _bottom_left=Point<T>(l,b);
5.95 _top_right=Point<T>(r,t);
5.96 _empty = false;
5.97 }
5.98
5.99 - ///Return \c true if the bounding box is empty.
5.100 + ///Return \c true if the box is empty.
5.101
5.102 - ///Return \c true if the bounding box is empty (i.e. return \c false
5.103 + ///Return \c true if the box is empty (i.e. return \c false
5.104 ///if at least one point was added to the box or the coordinates of
5.105 ///the box were set).
5.106 ///
5.107 - ///The coordinates of an empty bounding box are not defined.
5.108 + ///The coordinates of an empty box are not defined.
5.109 bool empty() const {
5.110 return _empty;
5.111 }
5.112
5.113 - ///Make the BoundingBox empty
5.114 + ///Make the box empty
5.115 void clear() {
5.116 _empty = true;
5.117 }
5.118 @@ -328,7 +327,7 @@
5.119 ///Give back the bottom left corner of the box
5.120
5.121 ///Give back the bottom left corner of the box.
5.122 - ///If the bounding box is empty, then the return value is not defined.
5.123 + ///If the box is empty, then the return value is not defined.
5.124 Point<T> bottomLeft() const {
5.125 return _bottom_left;
5.126 }
5.127 @@ -344,7 +343,7 @@
5.128 ///Give back the top right corner of the box
5.129
5.130 ///Give back the top right corner of the box.
5.131 - ///If the bounding box is empty, then the return value is not defined.
5.132 + ///If the box is empty, then the return value is not defined.
5.133 Point<T> topRight() const {
5.134 return _top_right;
5.135 }
5.136 @@ -360,7 +359,7 @@
5.137 ///Give back the bottom right corner of the box
5.138
5.139 ///Give back the bottom right corner of the box.
5.140 - ///If the bounding box is empty, then the return value is not defined.
5.141 + ///If the box is empty, then the return value is not defined.
5.142 Point<T> bottomRight() const {
5.143 return Point<T>(_top_right.x,_bottom_left.y);
5.144 }
5.145 @@ -377,7 +376,7 @@
5.146 ///Give back the top left corner of the box
5.147
5.148 ///Give back the top left corner of the box.
5.149 - ///If the bounding box is empty, then the return value is not defined.
5.150 + ///If the box is empty, then the return value is not defined.
5.151 Point<T> topLeft() const {
5.152 return Point<T>(_bottom_left.x,_top_right.y);
5.153 }
5.154 @@ -394,7 +393,7 @@
5.155 ///Give back the bottom of the box
5.156
5.157 ///Give back the bottom of the box.
5.158 - ///If the bounding box is empty, then the return value is not defined.
5.159 + ///If the box is empty, then the return value is not defined.
5.160 T bottom() const {
5.161 return _bottom_left.y;
5.162 }
5.163 @@ -410,7 +409,7 @@
5.164 ///Give back the top of the box
5.165
5.166 ///Give back the top of the box.
5.167 - ///If the bounding box is empty, then the return value is not defined.
5.168 + ///If the box is empty, then the return value is not defined.
5.169 T top() const {
5.170 return _top_right.y;
5.171 }
5.172 @@ -426,7 +425,7 @@
5.173 ///Give back the left side of the box
5.174
5.175 ///Give back the left side of the box.
5.176 - ///If the bounding box is empty, then the return value is not defined.
5.177 + ///If the box is empty, then the return value is not defined.
5.178 T left() const {
5.179 return _bottom_left.x;
5.180 }
5.181 @@ -442,7 +441,7 @@
5.182 /// Give back the right side of the box
5.183
5.184 /// Give back the right side of the box.
5.185 - ///If the bounding box is empty, then the return value is not defined.
5.186 + ///If the box is empty, then the return value is not defined.
5.187 T right() const {
5.188 return _top_right.x;
5.189 }
5.190 @@ -458,7 +457,7 @@
5.191 ///Give back the height of the box
5.192
5.193 ///Give back the height of the box.
5.194 - ///If the bounding box is empty, then the return value is not defined.
5.195 + ///If the box is empty, then the return value is not defined.
5.196 T height() const {
5.197 return _top_right.y-_bottom_left.y;
5.198 }
5.199 @@ -466,12 +465,12 @@
5.200 ///Give back the width of the box
5.201
5.202 ///Give back the width of the box.
5.203 - ///If the bounding box is empty, then the return value is not defined.
5.204 + ///If the box is empty, then the return value is not defined.
5.205 T width() const {
5.206 return _top_right.x-_bottom_left.x;
5.207 }
5.208
5.209 - ///Checks whether a point is inside a bounding box
5.210 + ///Checks whether a point is inside the box
5.211 bool inside(const Point<T>& u) const {
5.212 if (_empty)
5.213 return false;
5.214 @@ -481,11 +480,11 @@
5.215 }
5.216 }
5.217
5.218 - ///Increments a bounding box with a point
5.219 + ///Increments the box with a point
5.220
5.221 - ///Increments a bounding box with a point.
5.222 + ///Increments the box with a point.
5.223 ///
5.224 - BoundingBox& add(const Point<T>& u){
5.225 + Box& add(const Point<T>& u){
5.226 if (_empty) {
5.227 _bottom_left = _top_right = u;
5.228 _empty = false;
5.229 @@ -499,11 +498,11 @@
5.230 return *this;
5.231 }
5.232
5.233 - ///Increments a bounding box to contain another bounding box
5.234 + ///Increments the box to contain another box
5.235
5.236 - ///Increments a bounding box to contain another bounding box.
5.237 + ///Increments the box to contain another box.
5.238 ///
5.239 - BoundingBox& add(const BoundingBox &u){
5.240 + Box& add(const Box &u){
5.241 if ( !u.empty() ){
5.242 add(u._bottom_left);
5.243 add(u._top_right);
5.244 @@ -511,12 +510,12 @@
5.245 return *this;
5.246 }
5.247
5.248 - ///Intersection of two bounding boxes
5.249 + ///Intersection of two boxes
5.250
5.251 - ///Intersection of two bounding boxes.
5.252 + ///Intersection of two boxes.
5.253 ///
5.254 - BoundingBox operator&(const BoundingBox& u) const {
5.255 - BoundingBox b;
5.256 + Box operator&(const Box& u) const {
5.257 + Box b;
5.258 if (_empty || u._empty) {
5.259 b._empty = true;
5.260 } else {
5.261 @@ -530,9 +529,50 @@
5.262 return b;
5.263 }
5.264
5.265 - };//class Boundingbox
5.266 + };//class Box
5.267
5.268
5.269 + ///Read a box from a stream
5.270 +
5.271 + ///Read a box from a stream.
5.272 + ///\relates Box
5.273 + template<typename T>
5.274 + inline std::istream& operator>>(std::istream &is, Box<T>& b) {
5.275 + char c;
5.276 + Point<T> p;
5.277 + if (is >> c) {
5.278 + if (c != '(') is.putback(c);
5.279 + } else {
5.280 + is.clear();
5.281 + }
5.282 + if (!(is >> p)) return is;
5.283 + b.bottomLeft(p);
5.284 + if (is >> c) {
5.285 + if (c != ',') is.putback(c);
5.286 + } else {
5.287 + is.clear();
5.288 + }
5.289 + if (!(is >> p)) return is;
5.290 + b.topRight(p);
5.291 + if (is >> c) {
5.292 + if (c != ')') is.putback(c);
5.293 + } else {
5.294 + is.clear();
5.295 + }
5.296 + return is;
5.297 + }
5.298 +
5.299 + ///Write a box to a stream
5.300 +
5.301 + ///Write a box to a stream.
5.302 + ///\relates Box
5.303 + template<typename T>
5.304 + inline std::ostream& operator<<(std::ostream &os, const Box<T>& b)
5.305 + {
5.306 + os << "(" << b.bottomLeft() << "," << b.topRight() << ")";
5.307 + return os;
5.308 + }
5.309 +
5.310 ///Map of x-coordinates of a \ref Point "Point"-map
5.311
5.312 ///\ingroup maps
6.1 --- a/lemon/graph_to_eps.h Mon Sep 01 22:00:40 2008 +0200
6.2 +++ b/lemon/graph_to_eps.h Tue Sep 09 20:52:45 2008 +0100
6.3 @@ -725,10 +725,10 @@
6.4
6.5 double diag_len = 1;
6.6 if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {
6.7 - dim2::BoundingBox<double> bb;
6.8 + dim2::Box<double> bb;
6.9 for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);
6.10 if (bb.empty()) {
6.11 - bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
6.12 + bb = dim2::Box<double>(dim2::Point<double>(0,0));
6.13 }
6.14 diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());
6.15 if(diag_len<EPSILON) diag_len = 1;
6.16 @@ -736,7 +736,7 @@
6.17 if(!_absoluteArcWidths) _arcWidthScale*=diag_len;
6.18 }
6.19
6.20 - dim2::BoundingBox<double> bb;
6.21 + dim2::Box<double> bb;
6.22 for(NodeIt n(g);n!=INVALID;++n) {
6.23 double ns=_nodeSizes[n]*_nodeScale;
6.24 dim2::Point<double> p(ns,ns);
6.25 @@ -758,7 +758,7 @@
6.26 }
6.27 }
6.28 if (bb.empty()) {
6.29 - bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
6.30 + bb = dim2::Box<double>(dim2::Point<double>(0,0));
6.31 }
6.32
6.33 if(_scaleToA4)
7.1 --- a/test/dim_test.cc Mon Sep 01 22:00:40 2008 +0200
7.2 +++ b/test/dim_test.cc Tue Sep 09 20:52:45 2008 +0100
7.3 @@ -50,38 +50,38 @@
7.4 p = b/l;
7.5 check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar.");
7.6
7.7 - typedef dim2::BoundingBox<int> BB;
7.8 - BB box1;
7.9 - check(box1.empty(), "Wrong empty() in dim2::BoundingBox.");
7.10 + typedef dim2::Box<int> Box;
7.11 + Box box1;
7.12 + check(box1.empty(), "Wrong empty() in dim2::Box.");
7.13
7.14 box1.add(a);
7.15 - check(!box1.empty(), "Wrong empty() in dim2::BoundingBox.");
7.16 + check(!box1.empty(), "Wrong empty() in dim2::Box.");
7.17 box1.add(b);
7.18
7.19 check(box1.left()==1 && box1.bottom()==2 &&
7.20 box1.right()==3 && box1.top()==4,
7.21 - "Wrong addition of points to dim2::BoundingBox.");
7.22 + "Wrong addition of points to dim2::Box.");
7.23
7.24 - check(box1.inside(Point(2,3)), "Wrong inside() in dim2::BoundingBox.");
7.25 - check(box1.inside(Point(1,3)), "Wrong inside() in dim2::BoundingBox.");
7.26 - check(!box1.inside(Point(0,3)), "Wrong inside() in dim2::BoundingBox.");
7.27 + check(box1.inside(Point(2,3)), "Wrong inside() in dim2::Box.");
7.28 + check(box1.inside(Point(1,3)), "Wrong inside() in dim2::Box.");
7.29 + check(!box1.inside(Point(0,3)), "Wrong inside() in dim2::Box.");
7.30
7.31 - BB box2(Point(2,2));
7.32 - check(!box2.empty(), "Wrong empty() in dim2::BoundingBox.");
7.33 -
7.34 + Box box2(Point(2,2));
7.35 + check(!box2.empty(), "Wrong empty() in dim2::Box.");
7.36 +
7.37 box2.bottomLeft(Point(2,0));
7.38 box2.topRight(Point(5,3));
7.39 - BB box3 = box1 & box2;
7.40 + Box box3 = box1 & box2;
7.41 check(!box3.empty() &&
7.42 - box3.left()==2 && box3.bottom()==2 &&
7.43 + box3.left()==2 && box3.bottom()==2 &&
7.44 box3.right()==3 && box3.top()==3,
7.45 - "Wrong intersection of two dim2::BoundingBox objects.");
7.46 -
7.47 + "Wrong intersection of two dim2::Box objects.");
7.48 +
7.49 box1.add(box2);
7.50 check(!box1.empty() &&
7.51 box1.left()==1 && box1.bottom()==0 &&
7.52 box1.right()==5 && box1.top()==4,
7.53 - "Wrong addition of two dim2::BoundingBox objects.");
7.54 + "Wrong addition of two dim2::Box objects.");
7.55
7.56 return 0;
7.57 }