COIN-OR::LEMON - Graph Library

Changes in / [21:40d6f625e549:22:45f8b617339e] in lemon


Ignore:
Files:
3 added
7 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r3 r9  
    66*.o
    77.#.*
     8*.log
     9*.lo
     10*.tar.*
    811Makefile.in
    912aclocal.m4
     
    2023lemon/stamp-h2
    2124doc/Doxyfile
    22 lemon/.dirstamp
    23 lemon/.libs/*
     25.dirstamp
     26.libs/*
     27.deps/*
    2428
    2529syntax: regexp
    26 html/.*
    27 autom4te.cache/.*
    28 build-aux/.*
    29 objs.*/.*
     30^doc/html/.*
     31^autom4te.cache/.*
     32^build-aux/.*
     33^objs.*/.*
     34^test/[a-z_]*$
  • lemon/Makefile.am

    r8 r10  
    88
    99lemon_libemon_la_SOURCES = \
    10         lemon/base.cc
     10        lemon/base.cc \
     11        lemon/random.cc
     12
    1113
    1214lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     
    1517lemon_HEADERS += \
    1618        lemon/dim2.h \
     19        lemon/random.h \
    1720        lemon/list_graph.h \
    1821        lemon/tolerance.h
  • lemon/bits/invalid.h

    r7 r13  
    2525namespace lemon {
    2626
    27   /// \brief Dummy type to make it easier to make invalid iterators.
     27  /// \brief Dummy type to make it easier to create invalid iterators.
    2828  ///
    2929  /// See \ref INVALID for the usage.
     
    3535  };
    3636 
    37   /// Invalid iterators.
    38  
     37  /// \brief Invalid iterators.
     38  ///
    3939  /// \ref Invalid is a global type that converts to each iterator
    4040  /// in such a way that the value of the target iterator will be invalid.
  • lemon/dim2.h

    r8 r15  
    3535/// the rectangular bounding box of a set of
    3636/// \ref lemon::dim2::Point "dim2::Point"'s.
    37 ///
    38 ///\author Attila Bernath
    39 
    4037
    4138namespace lemon {
     
    6360      typedef T Value;
    6461
    65       ///First co-ordinate
     62      ///First coordinate
    6663      T x;
    67       ///Second co-ordinate
     64      ///Second coordinate
    6865      T y;     
    6966     
     
    7673      ///The dimension of the vector.
    7774
    78       ///This class give back always 2.
    79       ///
     75      ///The dimension of the vector.
     76      ///This function always returns 2.
    8077      int size() const { return 2; }
    8178
     
    139136      }
    140137
    141       ///Return the neg of the vectors
     138      ///Return the negative of the vector
    142139      Point<T> operator-() const {
    143140        Point<T> b=*this;
     
    176173    };
    177174
    178   ///Return an Point
    179 
    180   ///Return an Point
     175  ///Return a Point
     176
     177  ///Return a Point.
    181178  ///\relates Point
    182179  template <typename T>
     
    187184  ///Return a vector multiplied by a scalar
    188185
    189   ///Return a vector multiplied by a scalar
     186  ///Return a vector multiplied by a scalar.
    190187  ///\relates Point
    191188  template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
     
    195192  ///Read a plainvector from a stream
    196193
    197   ///Read a plainvector from a stream
     194  ///Read a plainvector from a stream.
    198195  ///\relates Point
    199196  ///
     
    223220  ///Write a plainvector to a stream
    224221
    225   ///Write a plainvector to a stream
     222  ///Write a plainvector to a stream.
    226223  ///\relates Point
    227224  ///
     
    235232  ///Rotate by 90 degrees
    236233
    237   ///Returns its parameter rotated by 90 degrees in positive direction.
     234  ///Returns the parameter rotated by 90 degrees in positive direction.
    238235  ///\relates Point
    239236  ///
     
    246243  ///Rotate by 180 degrees
    247244
    248   ///Returns its parameter rotated by 180 degrees.
     245  ///Returns the parameter rotated by 180 degrees.
    249246  ///\relates Point
    250247  ///
     
    257254  ///Rotate by 270 degrees
    258255
    259   ///Returns its parameter rotated by 90 degrees in negative direction.
     256  ///Returns the parameter rotated by 90 degrees in negative direction.
    260257  ///\relates Point
    261258  ///
     
    272269  /// A class to calculate or store the bounding box of plainvectors.
    273270  ///
    274   ///\author Attila Bernath
    275271    template<typename T>
    276272    class BoundingBox {
     
    287283      ///Construct an instance from two points
    288284     
    289       ///Construct an instance from two points
    290       ///\warning The coordinates of the bottom-left corner must be no more
    291       ///than those of the top-right one
     285      ///Construct an instance from two points.
     286      ///\param a The bottom left corner.
     287      ///\param b The top right corner.
     288      ///\warning The coordinates of the bottom left corner must be no more
     289      ///than those of the top right one.
    292290      BoundingBox(Point<T> a,Point<T> b)
    293291      {
     
    299297      ///Construct an instance from four numbers
    300298
    301       ///Construct an instance from four numbers
    302       ///\warning The coordinates of the bottom-left corner must be no more
    303       ///than those of the top-right one
     299      ///Construct an instance from four numbers.
     300      ///\param l The left side of the box.
     301      ///\param b The bottom of the box.
     302      ///\param r The right side of the box.
     303      ///\param t The top of the box.
     304      ///\warning The left side must be no more than the right side and
     305      ///bottom must be no more than the top.
    304306      BoundingBox(T l,T b,T r,T t)
    305307      {
     
    309311      }
    310312     
    311       ///Were any points added?
     313      ///Return \c true if the bounding box is empty.
     314     
     315      ///Return \c true if the bounding box is empty (i.e. return \c false
     316      ///if at least one point was added to the box or the coordinates of
     317      ///the box were set).
     318      ///The coordinates of an empty bounding box are not defined.
    312319      bool empty() const {
    313320        return _empty;
     
    330337
    331338      ///Set the bottom left corner.
    332       ///It should only bee used for non-empty box.
     339      ///It should only be used for non-empty box.
    333340      void bottomLeft(Point<T> p) {
    334341        bottom_left = p;
     
    346353
    347354      ///Set the top right corner.
    348       ///It should only bee used for non-empty box.
     355      ///It should only be used for non-empty box.
    349356      void topRight(Point<T> p) {
    350357        top_right = p;
     
    362369
    363370      ///Set the bottom right corner.
    364       ///It should only bee used for non-empty box.
     371      ///It should only be used for non-empty box.
    365372      void bottomRight(Point<T> p) {
    366373        top_right.x = p.x;
     
    379386
    380387      ///Set the top left corner.
    381       ///It should only bee used for non-empty box.
     388      ///It should only be used for non-empty box.
    382389      void topLeft(Point<T> p) {
    383390        top_right.y = p.y;
     
    396403
    397404      ///Set the bottom of the box.
    398       ///It should only bee used for non-empty box.
     405      ///It should only be used for non-empty box.
    399406      void bottom(T t) {
    400407        bottom_left.y = t;
     
    412419
    413420      ///Set the top of the box.
    414       ///It should only bee used for non-empty box.
     421      ///It should only be used for non-empty box.
    415422      void top(T t) {
    416423        top_right.y = t;
     
    428435
    429436      ///Set the left side of the box.
    430       ///It should only bee used for non-empty box
     437      ///It should only be used for non-empty box.
    431438      void left(T t) {
    432439        bottom_left.x = t;
     
    444451
    445452      ///Set the right side of the box.
    446       ///It should only bee used for non-empty box
     453      ///It should only be used for non-empty box.
    447454      void right(T t) {
    448455        top_right.x = t;
     
    466473
    467474      ///Checks whether a point is inside a bounding box
    468       bool inside(const Point<T>& u){
     475      bool inside(const Point<T>& u) const {
    469476        if (_empty)
    470477          return false;
     
    476483 
    477484      ///Increments a bounding box with a point
     485
     486      ///Increments a bounding box with a point.
     487      ///
    478488      BoundingBox& add(const Point<T>& u){
    479489        if (_empty){
     
    490500      }
    491501   
    492       ///Increments a bounding to contain another bounding box
     502      ///Increments a bounding box to contain another bounding box
     503     
     504      ///Increments a bounding box to contain another bounding box.
     505      ///
    493506      BoundingBox& add(const BoundingBox &u){
    494507        if ( !u.empty() ){
     
    500513 
    501514      ///Intersection of two bounding boxes
    502       BoundingBox operator &(const BoundingBox& u){
     515
     516      ///Intersection of two bounding boxes.
     517      ///
     518      BoundingBox operator&(const BoundingBox& u) const {
    503519        BoundingBox b;
    504         b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x);
    505         b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y);
    506         b.top_right.x=std::min(this->top_right.x,u.top_right.x);
    507         b.top_right.y=std::min(this->top_right.y,u.top_right.y);
    508         b._empty = this->_empty || u._empty ||
    509           b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y;
     520        if (this->_empty || u._empty) {
     521          b._empty = true;
     522        } else {
     523          b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);
     524          b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);
     525          b.top_right.x = std::min(this->top_right.x,u.top_right.x);
     526          b.top_right.y = std::min(this->top_right.y,u.top_right.y);
     527          b._empty = b.bottom_left.x > b.top_right.x ||
     528                     b.bottom_left.y > b.top_right.y;
     529        }
    510530        return b;
    511531      }
     
    514534
    515535
    516   ///Map of x-coordinates of a dim2::Point<>-map
    517 
    518   ///\ingroup maps
    519   ///Map of x-coordinates of a dim2::Point<>-map
     536  ///Map of x-coordinates of a \ref Point "Point"-map
     537
     538  ///\ingroup maps
     539  ///Map of x-coordinates of a \ref Point "Point"-map.
    520540  ///
    521541  template<class M>
     
    571591  ///Returns a \ref ConstXMap class
    572592
    573   ///This function just returns an \ref ConstXMap class.
     593  ///This function just returns a \ref ConstXMap class.
    574594  ///
    575595  ///\ingroup maps
     
    581601  }
    582602
    583   ///Map of y-coordinates of a dim2::Point<>-map
     603  ///Map of y-coordinates of a \ref Point "Point"-map
    584604   
    585605  ///\ingroup maps
    586   ///Map of y-coordinates of a dim2::Point<>-map
     606  ///Map of y-coordinates of a \ref Point "Point"-map.
    587607  ///
    588608  template<class M>
     
    600620  };
    601621
    602   ///Returns an \ref YMap class
    603 
    604   ///This function just returns an \ref YMap class.
     622  ///Returns a \ref YMap class
     623
     624  ///This function just returns a \ref YMap class.
    605625  ///
    606626  ///\ingroup maps
     
    638658  ///Returns a \ref ConstYMap class
    639659
    640   ///This function just returns an \ref ConstYMap class.
     660  ///This function just returns a \ref ConstYMap class.
    641661  ///
    642662  ///\ingroup maps
     
    650670
    651671    ///\brief Map of the \ref Point::normSquare() "normSquare()"
    652     ///of an \ref Point "Point"-map
     672    ///of a \ref Point "Point"-map
    653673    ///
    654674    ///Map of the \ref Point::normSquare() "normSquare()"
    655     ///of an \ref Point "Point"-map
     675    ///of a \ref Point "Point"-map.
    656676    ///\ingroup maps
    657677    ///
     
    671691  ///Returns a \ref NormSquareMap class
    672692
    673   ///This function just returns an \ref NormSquareMap class.
     693  ///This function just returns a \ref NormSquareMap class.
    674694  ///
    675695  ///\ingroup maps
  • lemon/tolerance.h

    r7 r16  
    4949  ///\sa Tolerance<long double>
    5050  ///\sa Tolerance<int>
     51#if defined __GNUC__ && !defined __STRICT_ANSI__ 
    5152  ///\sa Tolerance<long long int>
     53#endif
    5254  ///\sa Tolerance<unsigned int>
     55#if defined __GNUC__ && !defined __STRICT_ANSI__ 
    5356  ///\sa Tolerance<unsigned long long int>
     57#endif
    5458
    5559  template<class T>
     
    131135    bool negative(Value a) const { return -_epsilon>a; }
    132136    ///Returns \c true if \c a is \e surely non-zero
    133     bool nonZero(Value a) const { return positive(a)||negative(a); };
     137    bool nonZero(Value a) const { return positive(a)||negative(a); }
    134138
    135139    ///@}
     
    182186    bool negative(Value a) const { return -_epsilon>a; }
    183187    ///Returns \c true if \c a is \e surely non-zero
    184     bool nonZero(Value a) const { return positive(a)||negative(a); };
     188    bool nonZero(Value a) const { return positive(a)||negative(a); }
    185189
    186190    ///@}
     
    233237    bool negative(Value a) const { return -_epsilon>a; }
    234238    ///Returns \c true if \c a is \e surely non-zero
    235     bool nonZero(Value a) const { return positive(a)||negative(a); };
     239    bool nonZero(Value a) const { return positive(a)||negative(a); }
    236240
    237241    ///@}
     
    266270    static bool negative(Value a) { return 0>a; }
    267271    ///Returns \c true if \c a is \e surely non-zero
    268     static bool nonZero(Value a) { return a!=0; };
     272    static bool nonZero(Value a) { return a!=0; }
    269273
    270274    ///@}
     
    299303    static bool negative(Value) { return false; }
    300304    ///Returns \c true if \c a is \e surely non-zero
    301     static bool nonZero(Value a) { return a!=0; };
     305    static bool nonZero(Value a) { return a!=0; }
    302306
    303307    ///@}
     
    333337    static bool negative(Value a) { return 0>a; }
    334338    ///Returns \c true if \c a is \e surely non-zero
    335     static bool nonZero(Value a) { return a!=0;};
     339    static bool nonZero(Value a) { return a!=0;}
    336340
    337341    ///@}
     
    366370    static bool negative(Value) { return false; }
    367371    ///Returns \c true if \c a is \e surely non-zero
    368     static bool nonZero(Value a) { return a!=0;};
     372    static bool nonZero(Value a) { return a!=0;}
    369373
    370374    ///@}
     
    403407    static bool negative(Value a) { return 0>a; }
    404408    ///Returns \c true if \c a is \e surely non-zero
    405     static bool nonZero(Value a) { return a!=0;};
     409    static bool nonZero(Value a) { return a!=0;}
    406410
    407411    ///@}
     
    438442    static bool negative(Value) { return false; }
    439443    ///Returns \c true if \c a is \e surely non-zero
    440     static bool nonZero(Value a) { return a!=0;};
     444    static bool nonZero(Value a) { return a!=0;}
    441445
    442446    ///@}
  • test/Makefile.am

    r8 r10  
    44noinst_HEADERS += \
    55        test/test_tools.h
    6  
     6
    77check_PROGRAMS += \
    88        test/dim_test \
     9        test/random_test \
    910        test/test_tools_fail \
    1011        test/test_tools_pass
    11  
     12
    1213TESTS += $(check_PROGRAMS)
    1314XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    1415
    1516test_dim_test_SOURCES = test/dim_test.cc
     17test_random_test_SOURCES = test/random_test.cc
    1618test_test_tools_fail_SOURCES = test/test_tools_fail.cc
    1719test_test_tools_pass_SOURCES = test/test_tools_pass.cc
  • test/dim_test.cc

    r8 r14  
    2323using namespace std;
    2424using namespace lemon;
     25
    2526int main()
    2627{
    27 
    28   cout << "Testing classes `dim2::Point' and `dim2::BoundingBox'." << endl;
     28  cout << "Testing classes 'dim2::Point' and 'dim2::BoundingBox'." << endl;
    2929
    3030  typedef dim2::Point<int> Point;
    31        
    32   Point seged;
    33   check(seged.size()==2, "Wrong vector addition");
     31
     32  Point p;
     33  check(p.size()==2, "Wrong vector initialization.");
    3434
    3535  Point a(1,2);
    3636  Point b(3,4);
     37  check(a[0]==1 && a[1]==2, "Wrong vector initialization.");
    3738
    38   check(a[0]==1 && a[1]==2, "Wrong vector addition");
     39  p = a+b;
     40  check(p.x==4 && p.y==6, "Wrong vector addition.");
    3941
    40   seged = a+b;
    41   check(seged.x==4 && seged.y==6, "Wrong vector addition");
     42  p = a-b;
     43  check(p.x==-2 && p.y==-2, "Wrong vector subtraction.");
    4244
    43   seged = a-b;
    44   check(seged.x==-2 && seged.y==-2, "a-b");
    45 
    46   check(a.normSquare()==5,"Wrong norm calculation");
    47   check(a*b==11, "a*b");
     45  check(a.normSquare()==5,"Wrong vector norm calculation.");
     46  check(a*b==11, "Wrong vector scalar product.");
    4847
    4948  int l=2;
    50   seged = a*l;
    51   check(seged.x==2 && seged.y==4, "a*l");
     49  p = a*l;
     50  check(p.x==2 && p.y==4, "Wrong vector multiplication by a scalar.");
    5251
    53   seged = b/l;
    54   check(seged.x==1 && seged.y==2, "b/l");
     52  p = b/l;
     53  check(p.x==1 && p.y==2, "Wrong vector division by a scalar.");
    5554
    5655  typedef dim2::BoundingBox<int> BB;
    57   BB doboz1;
    58   check(doboz1.empty(), "It should be empty.");
    59        
    60   doboz1.add(a);
    61   check(!doboz1.empty(), "It should not be empty.");
    62   doboz1.add(b);
     56  BB box1;
     57  check(box1.empty(), "It should be empty.");
    6358
    64   check(doboz1.bottomLeft().x==1 &&
    65         doboz1.bottomLeft().y==2 &&
    66         doboz1.topRight().x==3 &&
    67         doboz1.topRight().y==4, 
    68         "added points to box");
     59  box1.add(a);
     60  check(!box1.empty(), "It should not be empty.");
     61  box1.add(b);
    6962
    70   seged.x=2;seged.y=3;
    71   check(doboz1.inside(seged),"It should be inside.");
     63  check(box1.bottomLeft().x==1 &&
     64        box1.bottomLeft().y==2 &&
     65        box1.topRight().x==3 &&
     66        box1.topRight().y==4,
     67        "Wrong addition of points to box.");
    7268
    73   seged.x=1;seged.y=3;
    74   check(doboz1.inside(seged),"It should be inside.");
     69  p.x=2; p.y=3;
     70  check(box1.inside(p), "It should be inside.");
    7571
    76   seged.x=0;seged.y=3;
    77   check(!doboz1.inside(seged),"It should not be inside.");
     72  p.x=1; p.y=3;
     73  check(box1.inside(p), "It should be inside.");
    7874
    79   BB doboz2(seged);
    80   check(!doboz2.empty(),
     75  p.x=0; p.y=3;
     76  check(!box1.inside(p), "It should not be inside.");
     77
     78  BB box2(p);
     79  check(!box2.empty(),
    8180        "It should not be empty. Constructed from 1 point.");
    8281
    83   doboz2.add(doboz1);
    84   check(doboz2.inside(seged),
     82  box2.add(box1);
     83  check(box2.inside(p),
    8584        "It should be inside. Incremented a box with another one.");
     85
     86  return 0;
    8687}
Note: See TracChangeset for help on using the changeset viewer.