Changeset 1426:91eb70983697 in lemon-0.x
- Timestamp:
- 05/18/05 11:39:06 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1897
- Location:
- src/lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/concept/graph.h
r1367 r1426 37 37 38 38 39 /// \brief Modular buildedstatic graph class.39 /// \brief Modular static graph class. 40 40 /// 41 41 /// It should be the same as the \c StaticGraph class. 42 42 class _StaticGraph 43 43 : virtual public BaseGraphComponent, 44 44 public IterableGraphComponent, public MappableGraphComponent { 45 45 public: 46 46 typedef BaseGraphComponent::Node Node; … … 49 49 template <typename _Graph> 50 50 struct Constraints { 51 52 53 54 51 void constraints() { 52 checkConcept<IterableGraphComponent, _Graph>(); 53 checkConcept<MappableGraphComponent, _Graph>(); 54 } 55 55 }; 56 56 }; 57 57 58 /// \brief Modular buildedextendable graph class.58 /// \brief Modular extendable graph class. 59 59 /// 60 60 /// It should be the same as the \c ExtendableGraph class. 61 61 class _ExtendableGraph 62 62 : virtual public BaseGraphComponent, public _StaticGraph, 63 63 public ExtendableGraphComponent, public ClearableGraphComponent { 64 64 public: 65 65 typedef BaseGraphComponent::Node Node; … … 68 68 template <typename _Graph> 69 69 struct Constraints { 70 71 72 73 74 70 void constraints() { 71 checkConcept<_StaticGraph, _Graph >(); 72 checkConcept<ExtendableGraphComponent, _Graph >(); 73 checkConcept<ClearableGraphComponent, _Graph >(); 74 } 75 75 }; 76 76 }; 77 77 78 /// \brief Modular buildederasable graph class.78 /// \brief Modular erasable graph class. 79 79 /// 80 80 /// It should be the same as the \c ErasableGraph class. 81 81 class _ErasableGraph 82 82 : virtual public BaseGraphComponent, public _ExtendableGraph, 83 83 public ErasableGraphComponent { 84 84 public: 85 85 typedef BaseGraphComponent::Node Node; … … 88 88 template <typename _Graph> 89 89 struct Constraints { 90 91 92 93 90 void constraints() { 91 checkConcept<_ExtendableGraph, _Graph >(); 92 checkConcept<ErasableGraphComponent, _Graph >(); 93 } 94 94 }; 95 95 }; … … 136 136 class Node { 137 137 public: 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 138 /// Default constructor 139 140 /// @warning The default constructor sets the iterator 141 /// to an undefined value. 142 Node() { } 143 /// Copy constructor. 144 145 /// Copy constructor. 146 /// 147 Node(const Node&) { } 148 149 /// Invalid constructor \& conversion. 150 151 /// This constructor initializes the iterator to be invalid. 152 /// \sa Invalid for more details. 153 Node(Invalid) { } 154 /// Equality operator 155 156 /// Two iterators are equal if and only if they point to the 157 /// same object or both are invalid. 158 bool operator==(Node) const { return true; } 159 160 /// Inequality operator 161 162 /// \sa operator==(Node n) 163 /// 164 bool operator!=(Node) const { return true; } 165 165 166 166 }; … … 173 173 /// \code 174 174 /// int count=0; 175 /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;175 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; 176 176 /// \endcode 177 177 class NodeIt : public Node { 178 178 public: 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 179 /// Default constructor 180 181 /// @warning The default constructor sets the iterator 182 /// to an undefined value. 183 NodeIt() { } 184 /// Copy constructor. 185 186 /// Copy constructor. 187 /// 188 NodeIt(const NodeIt& n) : Node(n) { } 189 /// Invalid constructor \& conversion. 190 191 /// Initialize the iterator to be invalid. 192 /// \sa Invalid for more details. 193 NodeIt(Invalid) { } 194 /// Sets the iterator to the first node. 195 196 /// Sets the iterator to the first node of \c g. 197 /// 198 NodeIt(const StaticGraph&) { } 199 /// Node -> NodeIt conversion. 200 201 /// Sets the iterator to the node of \c g pointed by the trivial 202 /// iterator n. 203 /// This feature necessitates that each time we 204 /// iterate the edge-set, the iteration order is the same. 205 NodeIt(const StaticGraph& g, const Node& n) { } 206 /// Next node. 207 208 /// Assign the iterator to the next node. 209 /// 210 NodeIt& operator++() { return *this; } 211 211 }; 212 212 … … 218 218 class Edge { 219 219 public: 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 220 /// Default constructor 221 222 /// @warning The default constructor sets the iterator 223 /// to an undefined value. 224 Edge() { } 225 /// Copy constructor. 226 227 /// Copy constructor. 228 /// 229 Edge(const Edge&) { } 230 /// Initialize the iterator to be invalid. 231 232 /// Initialize the iterator to be invalid. 233 /// 234 Edge(Invalid) { } 235 /// Equality operator 236 237 /// Two iterators are equal if and only if they point to the 238 /// same object or both are invalid. 239 bool operator==(Edge) const { return true; } 240 /// Inequality operator 241 242 /// \sa operator==(Node n) 243 /// 244 bool operator!=(Edge) const { return true; } 245 245 }; 246 246 … … 259 259 class OutEdgeIt : public Edge { 260 260 public: 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 /// This constructor sets the iterator tofirst outgoing edge.277 278 /// This constructor setthe iterator to the first outgoing edge of279 /// node 280 281 282 283 284 285 286 287 288 289 290 291 292 293 261 /// Default constructor 262 263 /// @warning The default constructor sets the iterator 264 /// to an undefined value. 265 OutEdgeIt() { } 266 /// Copy constructor. 267 268 /// Copy constructor. 269 /// 270 OutEdgeIt(const OutEdgeIt& e) : Edge(e) { } 271 /// Initialize the iterator to be invalid. 272 273 /// Initialize the iterator to be invalid. 274 /// 275 OutEdgeIt(Invalid) { } 276 /// This constructor sets the iterator to the first outgoing edge. 277 278 /// This constructor sets the iterator to the first outgoing edge of 279 /// the node. 280 ///@param n the node 281 ///@param g the graph 282 OutEdgeIt(const StaticGraph&, const Node&) { } 283 /// Edge -> OutEdgeIt conversion 284 285 /// Sets the iterator to the value of the trivial iterator \c e. 286 /// This feature necessitates that each time we 287 /// iterate the edge-set, the iteration order is the same. 288 OutEdgeIt(const StaticGraph& g, const Edge& e) { } 289 ///Next outgoing edge 290 291 /// Assign the iterator to the next 292 /// outgoing edge of the corresponding node. 293 OutEdgeIt& operator++() { return *this; } 294 294 }; 295 295 … … 308 308 class InEdgeIt : public Edge { 309 309 public: 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 /// node 329 330 331 332 333 334 335 336 337 338 339 340 341 342 310 /// Default constructor 311 312 /// @warning The default constructor sets the iterator 313 /// to an undefined value. 314 InEdgeIt() { } 315 /// Copy constructor. 316 317 /// Copy constructor. 318 /// 319 InEdgeIt(const InEdgeIt& e) : Edge(e) { } 320 /// Initialize the iterator to be invalid. 321 322 /// Initialize the iterator to be invalid. 323 /// 324 InEdgeIt(Invalid) { } 325 /// This constructor sets the iterator to first incoming edge. 326 327 /// This constructor set the iterator to the first incoming edge of 328 /// the node. 329 ///@param n the node 330 ///@param g the graph 331 InEdgeIt(const StaticGraph&, const Node&) { } 332 /// Edge -> InEdgeIt conversion 333 334 /// Sets the iterator to the value of the trivial iterator \c e. 335 /// This feature necessitates that each time we 336 /// iterate the edge-set, the iteration order is the same. 337 InEdgeIt(const StaticGraph&, const Edge&) { } 338 /// Next incoming edge 339 340 /// Assign the iterator to the next inedge of the corresponding node. 341 /// 342 InEdgeIt& operator++() { return *this; } 343 343 }; 344 344 /// This iterator goes through each edge. … … 353 353 class EdgeIt : public Edge { 354 354 public: 355 /// Default constructor 356 357 /// @warning The default constructor sets the iterator 358 /// to an undefined value. 359 EdgeIt() { } 360 /// Copy constructor. 361 362 /// Copy constructor. 363 /// 364 EdgeIt(const EdgeIt& e) : Edge(e) { } 365 /// Initialize the iterator to be invalid. 366 367 /// Initialize the iterator to be invalid. 368 /// 369 EdgeIt(Invalid) { } 370 /// This constructor sets the iterator to first edge. 371 372 /// This constructor set the iterator to the first edge of 373 /// node 374 ///@param g the graph 375 EdgeIt(const StaticGraph&) { } 376 /// Edge -> EdgeIt conversion 377 378 /// Sets the iterator to the value of the trivial iterator \c e. 379 /// This feature necessitates that each time we 380 /// iterate the edge-set, the iteration order is the same. 381 EdgeIt(const StaticGraph&, const Edge&) { } 382 ///Next edge 383 384 /// Assign the iterator to the next 385 /// edge of the corresponding node. 386 EdgeIt& operator++() { return *this; } 355 /// Default constructor 356 357 /// @warning The default constructor sets the iterator 358 /// to an undefined value. 359 EdgeIt() { } 360 /// Copy constructor. 361 362 /// Copy constructor. 363 /// 364 EdgeIt(const EdgeIt& e) : Edge(e) { } 365 /// Initialize the iterator to be invalid. 366 367 /// Initialize the iterator to be invalid. 368 /// 369 EdgeIt(Invalid) { } 370 /// This constructor sets the iterator to the first edge. 371 372 /// This constructor sets the iterator to the first edge of \c g. 373 ///@param g the graph 374 EdgeIt(const StaticGraph&) { } 375 /// Edge -> EdgeIt conversion 376 377 /// Sets the iterator to the value of the trivial iterator \c e. 378 /// This feature necessitates that each time we 379 /// iterate the edge-set, the iteration order is the same. 380 EdgeIt(const StaticGraph&, const Edge&) { } 381 ///Next edge 382 383 /// Assign the iterator to the next edge. 384 EdgeIt& operator++() { return *this; } 387 385 }; 388 386 ///Gives back the target node of an edge. … … 408 406 public: 409 407 410 411 412 413 414 415 416 417 418 419 408 ///\e 409 NodeMap(const StaticGraph&) { } 410 ///\e 411 NodeMap(const StaticGraph&, T) { } 412 413 ///Copy constructor 414 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } 415 ///Assignment operator 416 NodeMap& operator=(const NodeMap&) { return *this; } 417 // \todo fix this concept 420 418 }; 421 419 … … 432 430 public: 433 431 434 435 436 437 438 439 440 441 442 432 ///\e 433 EdgeMap(const StaticGraph&) { } 434 ///\e 435 EdgeMap(const StaticGraph&, T) { } 436 ///Copy constructor 437 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { } 438 ///Assignment operator 439 EdgeMap& operator=(const EdgeMap&) { return *this; } 440 // \todo fix this concept 443 441 }; 444 442 … … 450 448 /// An empty non-static graph class. 451 449 452 /// This class provides everything that \ref StaticGraph 453 /// with additional functionality which enables to build a 454 /// graph from scratch. 450 /// This class provides everything that \ref StaticGraph does. 451 /// Additionally it enables building graphs from scratch. 455 452 class ExtendableGraph : public StaticGraph 456 453 { … … 487 484 /// An empty erasable graph class. 488 485 489 /// This class is an extension of \ref ExtendableGraph. It alsomakes it486 /// This class is an extension of \ref ExtendableGraph. It makes it 490 487 /// possible to erase edges or nodes. 491 488 class ErasableGraph : public ExtendableGraph -
src/lemon/xy.h
r1420 r1426 30 30 /// 31 31 /// The class \ref lemon::BoundingBox "BoundingBox" can be used to determine 32 /// the rectangular bounding box a set of \ref lemon::xy "xy"'s.32 /// the rectangular bounding box of a set of \ref lemon::xy "xy"'s. 33 33 /// 34 34 ///\author Attila Bernath … … 68 68 ///Gives back the square of the norm of the vector 69 69 T normSquare() const { 70 70 return x*x+y*y; 71 71 } 72 72 73 73 ///Increments the left hand side by u 74 74 xy<T>& operator +=(const xy<T>& u) { 75 76 77 75 x += u.x; 76 y += u.y; 77 return *this; 78 78 } 79 79 80 80 ///Decrements the left hand side by u 81 81 xy<T>& operator -=(const xy<T>& u) { 82 83 84 82 x -= u.x; 83 y -= u.y; 84 return *this; 85 85 } 86 86 87 87 ///Multiplying the left hand side with a scalar 88 88 xy<T>& operator *=(const T &u) { 89 90 91 89 x *= u; 90 y *= u; 91 return *this; 92 92 } 93 93 94 94 ///Dividing the left hand side by a scalar 95 95 xy<T>& operator /=(const T &u) { 96 97 98 96 x /= u; 97 y /= u; 98 return *this; 99 99 } 100 100 101 101 ///Returns the scalar product of two vectors 102 102 T operator *(const xy<T>& u) const { 103 103 return x*u.x+y*u.y; 104 104 } 105 105 106 106 ///Returns the sum of two vectors 107 107 xy<T> operator+(const xy<T> &u) const { 108 109 108 xy<T> b=*this; 109 return b+=u; 110 110 } 111 111 112 112 ///Returns the neg of the vectors 113 113 xy<T> operator-() const { 114 115 116 114 xy<T> b=*this; 115 b.x=-b.x; b.y=-b.y; 116 return b; 117 117 } 118 118 119 119 ///Returns the difference of two vectors 120 120 xy<T> operator-(const xy<T> &u) const { 121 122 121 xy<T> b=*this; 122 return b-=u; 123 123 } 124 124 125 125 ///Returns a vector multiplied by a scalar 126 126 xy<T> operator*(const T &u) const { 127 128 127 xy<T> b=*this; 128 return b*=u; 129 129 } 130 130 131 131 ///Returns a vector divided by a scalar 132 132 xy<T> operator/(const T &u) const { 133 134 133 xy<T> b=*this; 134 return b/=u; 135 135 } 136 136 137 137 ///Testing equality 138 138 bool operator==(const xy<T> &u) const { 139 139 return (x==u.x) && (y==u.y); 140 140 } 141 141 142 142 ///Testing inequality 143 143 bool operator!=(xy u) const { 144 144 return (x!=u.x) || (y!=u.y); 145 145 } 146 146 … … 230 230 public: 231 231 232 ///Default constructor: an empty bounding box232 ///Default constructor: creates an empty bounding box 233 233 BoundingBox() { _empty = true; } 234 234 … … 236 236 BoundingBox(xy<T> a) { bottom_left=top_right=a; _empty = false; } 237 237 238 /// Is there any point added238 ///Were any points added? 239 239 bool empty() const { 240 240 return _empty; 241 241 } 242 242 243 243 ///Makes the BoundingBox empty 244 244 void clear() { 245 245 _empty=1; 246 246 } 247 247 248 248 ///Gives back the bottom left corner (if the bounding box is empty, then the return value is not defined) 249 249 xy<T> bottomLeft() const { 250 250 return bottom_left; 251 251 } 252 252 253 253 ///Gives back the top right corner (if the bounding box is empty, then the return value is not defined) 254 254 xy<T> topRight() const { 255 255 return top_right; 256 256 } 257 257 258 258 ///Gives back the bottom right corner (if the bounding box is empty, then the return value is not defined) 259 259 xy<T> bottomRight() const { 260 260 return xy<T>(top_right.x,bottom_left.y); 261 261 } 262 262 263 263 ///Gives back the top left corner (if the bounding box is empty, then the return value is not defined) 264 264 xy<T> topLeft() const { 265 265 return xy<T>(bottom_left.x,top_right.y); 266 266 } 267 267 268 268 ///Gives back the bottom of the box (if the bounding box is empty, then the return value is not defined) 269 269 T bottom() const { 270 270 return bottom_left.y; 271 271 } 272 272 273 273 ///Gives back the top of the box (if the bounding box is empty, then the return value is not defined) 274 274 T top() const { 275 275 return top_right.y; 276 276 } 277 277 278 278 ///Gives back the left side of the box (if the bounding box is empty, then the return value is not defined) 279 279 T left() const { 280 280 return bottom_left.x; 281 281 } 282 282 283 283 ///Gives back the right side of the box (if the bounding box is empty, then the return value is not defined) 284 284 T right() const { 285 285 return top_right.x; 286 286 } 287 287 288 288 ///Gives back the height of the box (if the bounding box is empty, then the return value is not defined) 289 289 T height() const { 290 290 return top_right.y-bottom_left.y; 291 291 } 292 292 293 293 ///Gives back the width of the box (if the bounding box is empty, then the return value is not defined) 294 294 T width() const { 295 295 return top_right.x-bottom_left.x; 296 296 } 297 297 298 298 ///Checks whether a point is inside a bounding box 299 299 bool inside(const xy<T>& u){ 300 301 302 303 304 305 300 if (_empty) 301 return false; 302 else{ 303 return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 && 304 (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 ); 305 } 306 306 } 307 307 308 308 ///Increments a bounding box with a point 309 309 BoundingBox& operator +=(const xy<T>& u){ 310 311 312 313 314 315 316 317 318 319 320 310 if (_empty){ 311 bottom_left=top_right=u; 312 _empty = false; 313 } 314 else{ 315 if (bottom_left.x > u.x) bottom_left.x = u.x; 316 if (bottom_left.y > u.y) bottom_left.y = u.y; 317 if (top_right.x < u.x) top_right.x = u.x; 318 if (top_right.y < u.y) top_right.y = u.y; 319 } 320 return *this; 321 321 } 322 322 323 323 ///Sums a bounding box and a point 324 324 BoundingBox operator +(const xy<T>& u){ 325 326 325 BoundingBox b = *this; 326 return b += u; 327 327 } 328 328 329 329 ///Increments a bounding box with an other bounding box 330 330 BoundingBox& operator +=(const BoundingBox &u){ 331 332 333 334 335 331 if ( !u.empty() ){ 332 *this += u.bottomLeft(); 333 *this += u.topRight(); 334 } 335 return *this; 336 336 } 337 337 338 338 ///Sums two bounding boxes 339 339 BoundingBox operator +(const BoundingBox& u){ 340 341 340 BoundingBox b = *this; 341 return b += u; 342 342 } 343 343
Note: See TracChangeset
for help on using the changeset viewer.