gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 7 0
merge default
3 files changed with 144 insertions and 86 deletions:
↑ Collapse diff ↑
Ignore white space 6 line context
... ...
@@ -1263,2 +1263,7 @@
1263 1263
  ///
1264
  /// This interface of the BFS algorithm should be used in special cases
1265
  /// when extra actions have to be performed in connection with certain
1266
  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1267
  /// instead.
1268
  ///
1264 1269
  /// \tparam _Digraph The type of the digraph the algorithm runs on.
Ignore white space 6 line context
... ...
@@ -61,3 +61,3 @@
61 61

	
62
      /// Invalid arc constructor
62
      // Invalid arc constructor
63 63
      Arc(Invalid i) : Edge(i), forward(true) {}
... ...
@@ -76,7 +76,8 @@
76 76

	
77
    /// First node of the edge
78
    Node u(const Edge &e) const {
79
      return Parent::source(e);
80
    }
77 81

	
78

	
79
    using Parent::source;
80

	
81
    /// Source of the given Arc.
82
    /// Source of the given arc
82 83
    Node source(const Arc &e) const {
... ...
@@ -85,5 +86,8 @@
85 86

	
86
    using Parent::target;
87
    /// Second node of the edge
88
    Node v(const Edge &e) const {
89
      return Parent::target(e);
90
    }
87 91

	
88
    /// Target of the given Arc.
92
    /// Target of the given arc
89 93
    Node target(const Arc &e) const {
... ...
@@ -94,11 +98,11 @@
94 98
    ///
95
    /// Returns a directed arc corresponding to the specified Edge.
96
    /// If the given bool is true the given edge and the
97
    /// returned arc have the same source node.
98
    static Arc direct(const Edge &ue, bool d) {
99
      return Arc(ue, d);
99
    /// Returns a directed arc corresponding to the specified edge.
100
    /// If the given bool is true, the first node of the given edge and
101
    /// the source node of the returned arc are the same.
102
    static Arc direct(const Edge &e, bool d) {
103
      return Arc(e, d);
100 104
    }
101 105

	
102
    /// Returns whether the given directed arc is same orientation as the
103
    /// corresponding edge.
106
    /// Returns whether the given directed arc has the same orientation
107
    /// as the corresponding edge.
104 108
    ///
... ...
@@ -106,4 +110,3 @@
106 110
    /// concept. "What does the direction of an edge mean?"
107
    static bool direction(const Arc &e) { return e.forward; }
108

	
111
    static bool direction(const Arc &a) { return a.forward; }
109 112

	
... ...
@@ -231,3 +234,2 @@
231 234

	
232

	
233 235
    int arcNum() const {
Ignore white space 6 line context
... ...
@@ -1210,2 +1210,7 @@
1210 1210
  ///
1211
  /// This interface of the DFS algorithm should be used in special cases
1212
  /// when extra actions have to be performed in connection with certain
1213
  /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
1214
  /// instead.
1215
  ///
1211 1216
  /// \tparam _Digraph The type of the digraph the algorithm runs on.
Show white space 6 line context
... ...
@@ -1069,2 +1069,4 @@
1069 1069
    void *_length;
1070
    //Pointer to the map of processed nodes.
1071
    void *_processed;
1070 1072
    //Pointer to the map of predecessors arcs.
... ...
@@ -1081,3 +1083,3 @@
1081 1083
    /// all of the attributes to default values (0, INVALID).
1082
    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
1084
    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
1083 1085
                           _dist(0), _source(INVALID) {}
... ...
@@ -1095,3 +1097,3 @@
1095 1097
      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1096
      _pred(0), _dist(0), _source(s) {}
1098
      _processed(0), _pred(0), _dist(0), _source(s) {}
1097 1099

	
... ...
@@ -1174,4 +1176,8 @@
1174 1176
            *reinterpret_cast<const LengthMap*>(Base::_length));
1175
      if(Base::_pred) dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1176
      if(Base::_dist) dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1177
      if(Base::_processed)
1178
        dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1179
      if(Base::_pred)
1180
        dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1181
      if(Base::_dist)
1182
        dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1177 1183
      dij.run(Base::_source);
Ignore white space 6 line context
... ...
@@ -30,4 +30,3 @@
30 30
///
31
/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
32
/// can be used to determine
31
/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
33 32
/// the rectangular bounding box of a set of
... ...
@@ -46,3 +45,3 @@
46 45

	
47
  /// A simple two dimensional vector (plain vector) implementation
46
  /// Two dimensional vector (plain vector)
48 47

	
... ...
@@ -223,3 +222,3 @@
223 222
  {
224
    os << "(" << z.x << ", " << z.y << ")";
223
    os << "(" << z.x << "," << z.y << ")";
225 224
    return os;
... ...
@@ -262,8 +261,8 @@
262 261

	
263
    /// A class to calculate or store the bounding box of plain vectors.
262
  /// Bounding box of plain vectors (\ref Point points).
264 263

	
265
    /// A class to calculate or store the bounding box of plain vectors.
266
    ///
267
    template<typename T>
268
    class BoundingBox {
264
  /// A class to calculate or store the bounding box of plain vectors
265
  /// (\ref Point points).
266
  template<typename T>
267
  class Box {
269 268
      Point<T> _bottom_left, _top_right;
... ...
@@ -272,7 +271,7 @@
272 271

	
273
      ///Default constructor: creates an empty bounding box
274
      BoundingBox() { _empty = true; }
272
      ///Default constructor: creates an empty box
273
      Box() { _empty = true; }
275 274

	
276
      ///Construct an instance from one point
277
      BoundingBox(Point<T> a) {
275
      ///Construct a box from one point
276
      Box(Point<T> a) {
278 277
        _bottom_left = _top_right = a;
... ...
@@ -281,5 +280,5 @@
281 280

	
282
      ///Construct an instance from two points
281
      ///Construct a box from two points
283 282

	
284
      ///Construct an instance from two points.
283
      ///Construct a box from two points.
285 284
      ///\param a The bottom left corner.
... ...
@@ -288,3 +287,3 @@
288 287
      ///than those of the top right one.
289
      BoundingBox(Point<T> a,Point<T> b)
288
      Box(Point<T> a,Point<T> b)
290 289
      {
... ...
@@ -295,5 +294,5 @@
295 294

	
296
      ///Construct an instance from four numbers
295
      ///Construct a box from four numbers
297 296

	
298
      ///Construct an instance from four numbers.
297
      ///Construct a box from four numbers.
299 298
      ///\param l The left side of the box.
... ...
@@ -304,3 +303,3 @@
304 303
      ///bottom must be no more than the top.
305
      BoundingBox(T l,T b,T r,T t)
304
      Box(T l,T b,T r,T t)
306 305
      {
... ...
@@ -311,5 +310,5 @@
311 310

	
312
      ///Return \c true if the bounding box is empty.
311
      ///Return \c true if the box is empty.
313 312

	
314
      ///Return \c true if the bounding box is empty (i.e. return \c false
313
      ///Return \c true if the box is empty (i.e. return \c false
315 314
      ///if at least one point was added to the box or the coordinates of
... ...
@@ -317,3 +316,3 @@
317 316
      ///
318
      ///The coordinates of an empty bounding box are not defined.
317
      ///The coordinates of an empty box are not defined.
319 318
      bool empty() const {
... ...
@@ -322,3 +321,3 @@
322 321

	
323
      ///Make the BoundingBox empty
322
      ///Make the box empty
324 323
      void clear() {
... ...
@@ -330,3 +329,3 @@
330 329
      ///Give back the bottom left corner of the box.
331
      ///If the bounding box is empty, then the return value is not defined.
330
      ///If the box is empty, then the return value is not defined.
332 331
      Point<T> bottomLeft() const {
... ...
@@ -346,3 +345,3 @@
346 345
      ///Give back the top right corner of the box.
347
      ///If the bounding box is empty, then the return value is not defined.
346
      ///If the box is empty, then the return value is not defined.
348 347
      Point<T> topRight() const {
... ...
@@ -362,3 +361,3 @@
362 361
      ///Give back the bottom right corner of the box.
363
      ///If the bounding box is empty, then the return value is not defined.
362
      ///If the box is empty, then the return value is not defined.
364 363
      Point<T> bottomRight() const {
... ...
@@ -379,3 +378,3 @@
379 378
      ///Give back the top left corner of the box.
380
      ///If the bounding box is empty, then the return value is not defined.
379
      ///If the box is empty, then the return value is not defined.
381 380
      Point<T> topLeft() const {
... ...
@@ -396,3 +395,3 @@
396 395
      ///Give back the bottom of the box.
397
      ///If the bounding box is empty, then the return value is not defined.
396
      ///If the box is empty, then the return value is not defined.
398 397
      T bottom() const {
... ...
@@ -412,3 +411,3 @@
412 411
      ///Give back the top of the box.
413
      ///If the bounding box is empty, then the return value is not defined.
412
      ///If the box is empty, then the return value is not defined.
414 413
      T top() const {
... ...
@@ -428,3 +427,3 @@
428 427
      ///Give back the left side of the box.
429
      ///If the bounding box is empty, then the return value is not defined.
428
      ///If the box is empty, then the return value is not defined.
430 429
      T left() const {
... ...
@@ -444,3 +443,3 @@
444 443
      /// Give back the right side of the box.
445
      ///If the bounding box is empty, then the return value is not defined.
444
      ///If the box is empty, then the return value is not defined.
446 445
      T right() const {
... ...
@@ -460,3 +459,3 @@
460 459
      ///Give back the height of the box.
461
      ///If the bounding box is empty, then the return value is not defined.
460
      ///If the box is empty, then the return value is not defined.
462 461
      T height() const {
... ...
@@ -468,3 +467,3 @@
468 467
      ///Give back the width of the box.
469
      ///If the bounding box is empty, then the return value is not defined.
468
      ///If the box is empty, then the return value is not defined.
470 469
      T width() const {
... ...
@@ -473,3 +472,3 @@
473 472

	
474
      ///Checks whether a point is inside a bounding box
473
      ///Checks whether a point is inside the box
475 474
      bool inside(const Point<T>& u) const {
... ...
@@ -483,7 +482,7 @@
483 482

	
484
      ///Increments a bounding box with a point
483
      ///Increments the box with a point
485 484

	
486
      ///Increments a bounding box with a point.
485
      ///Increments the box with a point.
487 486
      ///
488
      BoundingBox& add(const Point<T>& u){
487
      Box& add(const Point<T>& u){
489 488
        if (_empty) {
... ...
@@ -501,7 +500,7 @@
501 500

	
502
      ///Increments a bounding box to contain another bounding box
501
      ///Increments the box to contain another box
503 502

	
504
      ///Increments a bounding box to contain another bounding box.
503
      ///Increments the box to contain another box.
505 504
      ///
506
      BoundingBox& add(const BoundingBox &u){
505
      Box& add(const Box &u){
507 506
        if ( !u.empty() ){
... ...
@@ -513,8 +512,8 @@
513 512

	
514
      ///Intersection of two bounding boxes
513
      ///Intersection of two boxes
515 514

	
516
      ///Intersection of two bounding boxes.
515
      ///Intersection of two boxes.
517 516
      ///
518
      BoundingBox operator&(const BoundingBox& u) const {
519
        BoundingBox b;
517
      Box operator&(const Box& u) const {
518
        Box b;
520 519
        if (_empty || u._empty) {
... ...
@@ -532,5 +531,46 @@
532 531

	
533
    };//class Boundingbox
532
  };//class Box
534 533

	
535 534

	
535
  ///Read a box from a stream
536

	
537
  ///Read a box from a stream.
538
  ///\relates Box
539
  template<typename T>
540
  inline std::istream& operator>>(std::istream &is, Box<T>& b) {
541
    char c;
542
    Point<T> p;
543
    if (is >> c) {
544
      if (c != '(') is.putback(c);
545
    } else {
546
      is.clear();
547
    }
548
    if (!(is >> p)) return is;
549
    b.bottomLeft(p);
550
    if (is >> c) {
551
      if (c != ',') is.putback(c);
552
    } else {
553
      is.clear();
554
    }
555
    if (!(is >> p)) return is;
556
    b.topRight(p);
557
    if (is >> c) {
558
      if (c != ')') is.putback(c);
559
    } else {
560
      is.clear();
561
    }
562
    return is;
563
  }
564

	
565
  ///Write a box to a stream
566

	
567
  ///Write a box to a stream.
568
  ///\relates Box
569
  template<typename T>
570
  inline std::ostream& operator<<(std::ostream &os, const Box<T>& b)
571
  {
572
    os << "(" << b.bottomLeft() << "," << b.topRight() << ")";
573
    return os;
574
  }
575

	
536 576
  ///Map of x-coordinates of a \ref Point "Point"-map
Ignore white space 6 line context
... ...
@@ -727,6 +727,6 @@
727 727
    if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {
728
      dim2::BoundingBox<double> bb;
728
      dim2::Box<double> bb;
729 729
      for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);
730 730
      if (bb.empty()) {
731
        bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
731
        bb = dim2::Box<double>(dim2::Point<double>(0,0));
732 732
      }
... ...
@@ -738,3 +738,3 @@
738 738

	
739
    dim2::BoundingBox<double> bb;
739
    dim2::Box<double> bb;
740 740
    for(NodeIt n(g);n!=INVALID;++n) {
... ...
@@ -760,3 +760,3 @@
760 760
    if (bb.empty()) {
761
      bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
761
      bb = dim2::Box<double>(dim2::Point<double>(0,0));
762 762
    }
Ignore white space 6 line context
... ...
@@ -52,8 +52,8 @@
52 52

	
53
  typedef dim2::BoundingBox<int> BB;
54
  BB box1;
55
  check(box1.empty(), "Wrong empty() in dim2::BoundingBox.");
53
  typedef dim2::Box<int> Box;
54
  Box box1;
55
  check(box1.empty(), "Wrong empty() in dim2::Box.");
56 56

	
57 57
  box1.add(a);
58
  check(!box1.empty(), "Wrong empty() in dim2::BoundingBox.");
58
  check(!box1.empty(), "Wrong empty() in dim2::Box.");
59 59
  box1.add(b);
... ...
@@ -62,19 +62,19 @@
62 62
        box1.right()==3 && box1.top()==4,
63
        "Wrong addition of points to dim2::BoundingBox.");
63
        "Wrong addition of points to dim2::Box.");
64 64

	
65
  check(box1.inside(Point(2,3)), "Wrong inside() in dim2::BoundingBox.");
66
  check(box1.inside(Point(1,3)), "Wrong inside() in dim2::BoundingBox.");
67
  check(!box1.inside(Point(0,3)), "Wrong inside() in dim2::BoundingBox.");
65
  check(box1.inside(Point(2,3)), "Wrong inside() in dim2::Box.");
66
  check(box1.inside(Point(1,3)), "Wrong inside() in dim2::Box.");
67
  check(!box1.inside(Point(0,3)), "Wrong inside() in dim2::Box.");
68 68

	
69
  BB box2(Point(2,2));
70
  check(!box2.empty(), "Wrong empty() in dim2::BoundingBox.");
71
  
69
  Box box2(Point(2,2));
70
  check(!box2.empty(), "Wrong empty() in dim2::Box.");
71

	
72 72
  box2.bottomLeft(Point(2,0));
73 73
  box2.topRight(Point(5,3));
74
  BB box3 = box1 & box2;
74
  Box box3 = box1 & box2;
75 75
  check(!box3.empty() &&
76
        box3.left()==2 && box3.bottom()==2 && 
76
        box3.left()==2 && box3.bottom()==2 &&
77 77
        box3.right()==3 && box3.top()==3,
78
        "Wrong intersection of two dim2::BoundingBox objects.");
79
  
78
        "Wrong intersection of two dim2::Box objects.");
79

	
80 80
  box1.add(box2);
... ...
@@ -83,3 +83,3 @@
83 83
        box1.right()==5 && box1.top()==4,
84
        "Wrong addition of two dim2::BoundingBox objects.");
84
        "Wrong addition of two dim2::Box objects.");
85 85

	
0 comments (0 inline)