# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# 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<void*>(const_cast<GR*>(&g))),
_length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
- _pred(0), _dist(0), _source(s) {}
+ _processed(0), _pred(0), _dist(0), _source(s) {}
};
@@ -1172,8 +1174,12 @@
Dijkstra<Digraph,LengthMap,TR>
dij(*reinterpret_cast<const Digraph*>(Base::_g),
*reinterpret_cast<const LengthMap*>(Base::_length));
- if(Base::_pred) dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
- if(Base::_dist) dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
+ if(Base::_processed)
+ dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
+ if(Base::_pred)
+ dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
+ if(Base::_dist)
+ dij.distMap(*reinterpret_cast<DistMap*>(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<typename T>
inline std::ostream& operator<<(std::ostream &os, const Point<T>& 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<typename T>
- class BoundingBox {
+ /// A class to calculate or store the bounding box of plain vectors
+ /// (\ref Point points).
+ template<typename T>
+ class Box {
Point<T> _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<T> a) {
+ ///Construct a box from one point
+ Box(Point<T> 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<T> a,Point<T> b)
+ Box(Point<T> a,Point<T> 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<T>(l,b);
_top_right=Point<T>(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<T> 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<T> 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<T> bottomRight() const {
return Point<T>(_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<T> topLeft() const {
return Point<T>(_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<T>& 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<T>& u){
+ Box& add(const Point<T>& 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<typename T>
+ inline std::istream& operator>>(std::istream &is, Box<T>& b) {
+ char c;
+ Point<T> 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<typename T>
+ inline std::ostream& operator<<(std::ostream &os, const Box<T>& 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<double> bb;
+ dim2::Box<double> bb;
for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);
if (bb.empty()) {
- bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
+ bb = dim2::Box<double>(dim2::Point<double>(0,0));
}
diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());
if(diag_len<EPSILON) diag_len = 1;
@@ -736,7 +736,7 @@
if(!_absoluteArcWidths) _arcWidthScale*=diag_len;
}
- dim2::BoundingBox<double> bb;
+ dim2::Box<double> bb;
for(NodeIt n(g);n!=INVALID;++n) {
double ns=_nodeSizes[n]*_nodeScale;
dim2::Point<double> p(ns,ns);
@@ -758,7 +758,7 @@
}
}
if (bb.empty()) {
- bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
+ bb = dim2::Box<double>(dim2::Point<double>(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<int> BB;
- BB box1;
- check(box1.empty(), "Wrong empty() in dim2::BoundingBox.");
+ typedef dim2::Box<int> 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;
}