COIN-OR::LEMON - Graph Library

Ignore:
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r257 r258  
    12621262  /// the member functions of the \c Visitor class on every BFS event.
    12631263  ///
     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  ///
    12641269  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    12651270  /// The default value is
  • lemon/bits/base_extender.h

    r220 r256  
    6060      Arc() {}
    6161
    62       /// Invalid arc constructor
     62      // Invalid arc constructor
    6363      Arc(Invalid i) : Edge(i), forward(true) {}
    6464
     
    7575    };
    7676
    77 
    78 
    79     using Parent::source;
    80 
    81     /// Source of the given Arc.
     77    /// First node of the edge
     78    Node u(const Edge &e) const {
     79      return Parent::source(e);
     80    }
     81
     82    /// Source of the given arc
    8283    Node source(const Arc &e) const {
    8384      return e.forward ? Parent::source(e) : Parent::target(e);
    8485    }
    8586
    86     using Parent::target;
    87 
    88     /// Target of the given Arc.
     87    /// Second node of the edge
     88    Node v(const Edge &e) const {
     89      return Parent::target(e);
     90    }
     91
     92    /// Target of the given arc
    8993    Node target(const Arc &e) const {
    9094      return e.forward ? Parent::target(e) : Parent::source(e);
     
    9397    /// \brief Directed arc from an edge.
    9498    ///
    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);
    100     }
    101 
    102     /// Returns whether the given directed arc is same orientation as the
    103     /// corresponding edge.
     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);
     104    }
     105
     106    /// Returns whether the given directed arc has the same orientation
     107    /// as the corresponding edge.
    104108    ///
    105109    /// \todo reference to the corresponding point of the undirected digraph
    106110    /// 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; }
    109112
    110113    using Parent::first;
     
    229232      return Parent::maxArcId();
    230233    }
    231 
    232234
    233235    int arcNum() const {
  • lemon/dfs.h

    r257 r258  
    12091209  /// the member functions of the \c Visitor class on every DFS event.
    12101210  ///
     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  ///
    12111216  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    12121217  /// The default value is
  • lemon/dijkstra.h

    r257 r258  
    10681068    //Pointer to the length map
    10691069    void *_length;
     1070    //Pointer to the map of processed nodes.
     1071    void *_processed;
    10701072    //Pointer to the map of predecessors arcs.
    10711073    void *_pred;
     
    10801082    /// This constructor does not require parameters, therefore it initiates
    10811083    /// 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),
    10831085                           _dist(0), _source(INVALID) {}
    10841086
     
    10941096      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    10951097      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
    1096       _pred(0), _dist(0), _source(s) {}
     1098      _processed(0), _pred(0), _dist(0), _source(s) {}
    10971099
    10981100  };
     
    11731175        dij(*reinterpret_cast<const Digraph*>(Base::_g),
    11741176            *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));
    11771183      dij.run(Base::_source);
    11781184    }
  • lemon/dim2.h

    r241 r253  
    2929/// a two dimensional vector with the usual operations.
    3030///
    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
    3332/// the rectangular bounding box of a set of
    3433/// \ref lemon::dim2::Point "dim2::Point"'s.
     
    4544  /// @{
    4645
    47   /// A simple two dimensional vector (plain vector) implementation
     46  /// Two dimensional vector (plain vector)
    4847
    4948  /// A simple two dimensional vector (plain vector) implementation
     
    222221  inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
    223222  {
    224     os << "(" << z.x << ", " << z.y << ")";
     223    os << "(" << z.x << "," << z.y << ")";
    225224    return os;
    226225  }
     
    261260
    262261
    263     /// A class to calculate or store the bounding box of plain vectors.
    264 
    265     /// A class to calculate or store the bounding box of plain vectors.
    266     ///
    267     template<typename T>
    268     class BoundingBox {
     262  /// Bounding box of plain vectors (\ref Point points).
     263
     264  /// A class to calculate or store the bounding box of plain vectors
     265  /// (\ref Point points).
     266  template<typename T>
     267  class Box {
    269268      Point<T> _bottom_left, _top_right;
    270269      bool _empty;
    271270    public:
    272271
    273       ///Default constructor: creates an empty bounding box
    274       BoundingBox() { _empty = true; }
    275 
    276       ///Construct an instance from one point
    277       BoundingBox(Point<T> a) {
     272      ///Default constructor: creates an empty box
     273      Box() { _empty = true; }
     274
     275      ///Construct a box from one point
     276      Box(Point<T> a) {
    278277        _bottom_left = _top_right = a;
    279278        _empty = false;
    280279      }
    281280
    282       ///Construct an instance from two points
    283 
    284       ///Construct an instance from two points.
     281      ///Construct a box from two points
     282
     283      ///Construct a box from two points.
    285284      ///\param a The bottom left corner.
    286285      ///\param b The top right corner.
    287286      ///\warning The coordinates of the bottom left corner must be no more
    288287      ///than those of the top right one.
    289       BoundingBox(Point<T> a,Point<T> b)
     288      Box(Point<T> a,Point<T> b)
    290289      {
    291290        _bottom_left = a;
     
    294293      }
    295294
    296       ///Construct an instance from four numbers
    297 
    298       ///Construct an instance from four numbers.
     295      ///Construct a box from four numbers
     296
     297      ///Construct a box from four numbers.
    299298      ///\param l The left side of the box.
    300299      ///\param b The bottom of the box.
     
    303302      ///\warning The left side must be no more than the right side and
    304303      ///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)
    306305      {
    307306        _bottom_left=Point<T>(l,b);
     
    310309      }
    311310
    312       ///Return \c true if the bounding box is empty.
    313 
    314       ///Return \c true if the bounding box is empty (i.e. return \c false
     311      ///Return \c true if the box is empty.
     312
     313      ///Return \c true if the box is empty (i.e. return \c false
    315314      ///if at least one point was added to the box or the coordinates of
    316315      ///the box were set).
    317316      ///
    318       ///The coordinates of an empty bounding box are not defined.
     317      ///The coordinates of an empty box are not defined.
    319318      bool empty() const {
    320319        return _empty;
    321320      }
    322321
    323       ///Make the BoundingBox empty
     322      ///Make the box empty
    324323      void clear() {
    325324        _empty = true;
     
    329328
    330329      ///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.
    332331      Point<T> bottomLeft() const {
    333332        return _bottom_left;
     
    345344
    346345      ///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.
    348347      Point<T> topRight() const {
    349348        return _top_right;
     
    361360
    362361      ///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.
    364363      Point<T> bottomRight() const {
    365364        return Point<T>(_top_right.x,_bottom_left.y);
     
    378377
    379378      ///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.
    381380      Point<T> topLeft() const {
    382381        return Point<T>(_bottom_left.x,_top_right.y);
     
    395394
    396395      ///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.
    398397      T bottom() const {
    399398        return _bottom_left.y;
     
    411410
    412411      ///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.
    414413      T top() const {
    415414        return _top_right.y;
     
    427426
    428427      ///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.
    430429      T left() const {
    431430        return _bottom_left.x;
     
    443442
    444443      /// 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.
    446445      T right() const {
    447446        return _top_right.x;
     
    459458
    460459      ///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.
    462461      T height() const {
    463462        return _top_right.y-_bottom_left.y;
     
    467466
    468467      ///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.
    470469      T width() const {
    471470        return _top_right.x-_bottom_left.x;
    472471      }
    473472
    474       ///Checks whether a point is inside a bounding box
     473      ///Checks whether a point is inside the box
    475474      bool inside(const Point<T>& u) const {
    476475        if (_empty)
     
    482481      }
    483482
    484       ///Increments a bounding box with a point
    485 
    486       ///Increments a bounding box with a point.
     483      ///Increments the box with a point
     484
     485      ///Increments the box with a point.
    487486      ///
    488       BoundingBox& add(const Point<T>& u){
     487      Box& add(const Point<T>& u){
    489488        if (_empty) {
    490489          _bottom_left = _top_right = u;
     
    500499      }
    501500
    502       ///Increments a bounding box to contain another bounding box
    503 
    504       ///Increments a bounding box to contain another bounding box.
     501      ///Increments the box to contain another box
     502
     503      ///Increments the box to contain another box.
    505504      ///
    506       BoundingBox& add(const BoundingBox &u){
     505      Box& add(const Box &u){
    507506        if ( !u.empty() ){
    508507          add(u._bottom_left);
     
    512511      }
    513512
    514       ///Intersection of two bounding boxes
    515 
    516       ///Intersection of two bounding boxes.
     513      ///Intersection of two boxes
     514
     515      ///Intersection of two boxes.
    517516      ///
    518       BoundingBox operator&(const BoundingBox& u) const {
    519         BoundingBox b;
     517      Box operator&(const Box& u) const {
     518        Box b;
    520519        if (_empty || u._empty) {
    521520          b._empty = true;
     
    531530      }
    532531
    533     };//class Boundingbox
    534 
     532  };//class Box
     533
     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  }
    535575
    536576  ///Map of x-coordinates of a \ref Point "Point"-map
  • lemon/graph_to_eps.h

    r220 r253  
    726726    double diag_len = 1;
    727727    if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {
    728       dim2::BoundingBox<double> bb;
     728      dim2::Box<double> bb;
    729729      for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);
    730730      if (bb.empty()) {
    731         bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
     731        bb = dim2::Box<double>(dim2::Point<double>(0,0));
    732732      }
    733733      diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());
     
    737737    }
    738738
    739     dim2::BoundingBox<double> bb;
     739    dim2::Box<double> bb;
    740740    for(NodeIt n(g);n!=INVALID;++n) {
    741741      double ns=_nodeSizes[n]*_nodeScale;
     
    759759    }
    760760    if (bb.empty()) {
    761       bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
     761      bb = dim2::Box<double>(dim2::Point<double>(0,0));
    762762    }
    763763
  • test/dim_test.cc

    r242 r253  
    5151  check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar.");
    5252
    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.");
    5656
    5757  box1.add(a);
    58   check(!box1.empty(), "Wrong empty() in dim2::BoundingBox.");
     58  check(!box1.empty(), "Wrong empty() in dim2::Box.");
    5959  box1.add(b);
    6060
    6161  check(box1.left()==1 && box1.bottom()==2 &&
    6262        box1.right()==3 && box1.top()==4,
    63         "Wrong addition of points to dim2::BoundingBox.");
     63        "Wrong addition of points to dim2::Box.");
    6464
    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.");
    6868
    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
    7272  box2.bottomLeft(Point(2,0));
    7373  box2.topRight(Point(5,3));
    74   BB box3 = box1 & box2;
     74  Box box3 = box1 & box2;
    7575  check(!box3.empty() &&
    76         box3.left()==2 && box3.bottom()==2 && 
     76        box3.left()==2 && box3.bottom()==2 &&
    7777        box3.right()==3 && box3.top()==3,
    78         "Wrong intersection of two dim2::BoundingBox objects.");
    79  
     78        "Wrong intersection of two dim2::Box objects.");
     79
    8080  box1.add(box2);
    8181  check(!box1.empty() &&
    8282        box1.left()==1 && box1.bottom()==0 &&
    8383        box1.right()==5 && box1.top()==4,
    84         "Wrong addition of two dim2::BoundingBox objects.");
     84        "Wrong addition of two dim2::Box objects.");
    8585
    8686  return 0;
Note: See TracChangeset for help on using the changeset viewer.