Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon/full_graph.h
- Timestamp:
- 06/30/06 14:15:45 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/full_graph.h
r2115 r2116 22 22 #include <cmath> 23 23 24 #include <lemon/bits/base_extender.h> 24 25 #include <lemon/bits/graph_extender.h> 25 26 … … 30 31 ///\ingroup graphs 31 32 ///\file 32 ///\brief FullGraph class.33 ///\brief FullGraph and FullUGraph classes. 33 34 34 35 … … 247 248 }; 248 249 250 251 /// \brief Base of the FullUGrpah. 252 /// 253 /// Base of the FullUGrpah. 254 class FullUGraphBase { 255 int _nodeNum; 256 int _edgeNum; 257 public: 258 259 typedef FullUGraphBase Graph; 260 261 class Node; 262 class Edge; 263 264 public: 265 266 FullUGraphBase() {} 267 268 269 ///Creates a full graph with \c n nodes. 270 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } 271 272 /// \brief Returns the node with the given index. 273 /// 274 /// Returns the node with the given index. Because it is a 275 /// static size graph the node's of the graph can be indiced 276 /// by the range from 0 to \e nodeNum()-1 and the index of 277 /// the node can accessed by the \e index() member. 278 Node operator()(int index) const { return Node(index); } 279 280 /// \brief Returns the index of the node. 281 /// 282 /// Returns the index of the node. Because it is a 283 /// static size graph the node's of the graph can be indiced 284 /// by the range from 0 to \e nodeNum()-1 and the index of 285 /// the node can accessed by the \e index() member. 286 int index(const Node& node) const { return node.id; } 287 288 typedef True NodeNumTag; 289 typedef True EdgeNumTag; 290 291 ///Number of nodes. 292 int nodeNum() const { return _nodeNum; } 293 ///Number of edges. 294 int edgeNum() const { return _edgeNum; } 295 296 /// Maximum node ID. 297 298 /// Maximum node ID. 299 ///\sa id(Node) 300 int maxNodeId() const { return _nodeNum-1; } 301 /// Maximum edge ID. 302 303 /// Maximum edge ID. 304 ///\sa id(Edge) 305 int maxEdgeId() const { return _edgeNum-1; } 306 307 /// \brief Returns the node from its \c id. 308 /// 309 /// Returns the node from its \c id. If there is not node 310 /// with the given id the effect of the function is undefinied. 311 static Node nodeFromId(int id) { return Node(id);} 312 313 /// \brief Returns the edge from its \c id. 314 /// 315 /// Returns the edge from its \c id. If there is not edge 316 /// with the given id the effect of the function is undefinied. 317 static Edge edgeFromId(int id) { return Edge(id);} 318 319 Node source(Edge e) const { 320 /// \todo we may do it faster 321 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2); 322 } 323 324 Node target(Edge e) const { 325 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; 326 return Node(e.id - (source) * (source - 1) / 2); 327 } 328 329 330 /// \brief Node ID. 331 /// 332 /// The ID of a valid Node is a nonnegative integer not greater than 333 /// \ref maxNodeId(). The range of the ID's is not surely continuous 334 /// and the greatest node ID can be actually less then \ref maxNodeId(). 335 /// 336 /// The ID of the \ref INVALID node is -1. 337 /// \return The ID of the node \c v. 338 339 static int id(Node v) { return v.id; } 340 341 /// \brief Edge ID. 342 /// 343 /// The ID of a valid Edge is a nonnegative integer not greater than 344 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 345 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 346 /// 347 /// The ID of the \ref INVALID edge is -1. 348 ///\return The ID of the edge \c e. 349 static int id(Edge e) { return e.id; } 350 351 /// \brief Finds an edge between two nodes. 352 /// 353 /// Finds an edge from node \c u to node \c v. 354 /// 355 /// If \c prev is \ref INVALID (this is the default value), then 356 /// It finds the first edge from \c u to \c v. Otherwise it looks for 357 /// the next edge from \c u to \c v after \c prev. 358 /// \return The found edge or INVALID if there is no such an edge. 359 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { 360 if (prev.id != -1 || u.id <= v.id) return Edge(-1); 361 return Edge(u.id * (u.id - 1) / 2 + v.id); 362 } 363 364 typedef True FindEdgeTag; 365 366 367 class Node { 368 friend class FullUGraphBase; 369 370 protected: 371 int id; 372 Node(int _id) { id = _id;} 373 public: 374 Node() {} 375 Node (Invalid) { id = -1; } 376 bool operator==(const Node node) const {return id == node.id;} 377 bool operator!=(const Node node) const {return id != node.id;} 378 bool operator<(const Node node) const {return id < node.id;} 379 }; 380 381 382 383 class Edge { 384 friend class FullUGraphBase; 385 386 protected: 387 int id; // _nodeNum * target + source; 388 389 Edge(int _id) : id(_id) {} 390 391 public: 392 Edge() { } 393 Edge (Invalid) { id = -1; } 394 bool operator==(const Edge edge) const {return id == edge.id;} 395 bool operator!=(const Edge edge) const {return id != edge.id;} 396 bool operator<(const Edge edge) const {return id < edge.id;} 397 }; 398 399 void first(Node& node) const { 400 node.id = _nodeNum - 1; 401 } 402 403 static void next(Node& node) { 404 --node.id; 405 } 406 407 void first(Edge& edge) const { 408 edge.id = _edgeNum - 1; 409 } 410 411 static void next(Edge& edge) { 412 --edge.id; 413 } 414 415 void firstOut(Edge& edge, const Node& node) const { 416 int src = node.id; 417 int trg = 0; 418 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); 419 } 420 421 /// \todo with specialized iterators we can make faster iterating 422 void nextOut(Edge& edge) const { 423 int src = source(edge).id; 424 int trg = target(edge).id; 425 ++trg; 426 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); 427 } 428 429 void firstIn(Edge& edge, const Node& node) const { 430 int src = node.id + 1; 431 int trg = node.id; 432 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); 433 } 434 435 void nextIn(Edge& edge) const { 436 int src = source(edge).id; 437 int trg = target(edge).id; 438 ++src; 439 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); 440 } 441 442 }; 443 444 typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> > 445 ExtendedFullUGraphBase; 446 447 /// \ingroup graphs 448 /// 449 /// \brief An undirected full graph class. 450 /// 451 /// This is a simple and fast undirected full graph implementation. 452 /// It is completely static, so you can neither add nor delete either 453 /// edges or nodes. 454 /// 455 /// The main difference beetween the \e FullGraph and \e FullUGraph class 456 /// is that this class conforms to the undirected graph concept and 457 /// it does not contain the loop edges. 458 /// 459 /// \sa FullUGraphBase 460 /// \sa FullGraph 461 /// 462 /// \author Balazs Dezso 463 class FullUGraph : public ExtendedFullUGraphBase { 464 public: 465 466 typedef ExtendedFullUGraphBase Parent; 467 468 /// \brief Constructor 469 FullUGraph() { construct(0); } 470 471 /// \brief Constructor 472 FullUGraph(int n) { construct(n); } 473 474 /// \brief Resize the graph 475 /// 476 /// Resize the graph. The function will fully destroy and build the graph. 477 /// This cause that the maps of the graph will reallocated 478 /// automatically and the previous values will be lost. 479 void resize(int n) { 480 Parent::getNotifier(Edge()).clear(); 481 Parent::getNotifier(UEdge()).clear(); 482 Parent::getNotifier(Node()).clear(); 483 construct(n); 484 Parent::getNotifier(Node()).build(); 485 Parent::getNotifier(UEdge()).build(); 486 Parent::getNotifier(Edge()).build(); 487 } 488 }; 489 490 491 class FullBpUGraphBase { 492 protected: 493 494 int _aNodeNum; 495 int _bNodeNum; 496 497 int _edgeNum; 498 499 public: 500 501 class NodeSetError : public LogicError { 502 virtual const char* exceptionName() const { 503 return "lemon::FullBpUGraph::NodeSetError"; 504 } 505 }; 506 507 class Node { 508 friend class FullBpUGraphBase; 509 protected: 510 int id; 511 512 Node(int _id) : id(_id) {} 513 public: 514 Node() {} 515 Node(Invalid) { id = -1; } 516 bool operator==(const Node i) const {return id==i.id;} 517 bool operator!=(const Node i) const {return id!=i.id;} 518 bool operator<(const Node i) const {return id<i.id;} 519 }; 520 521 class UEdge { 522 friend class FullBpUGraphBase; 523 protected: 524 int id; 525 526 UEdge(int _id) { id = _id;} 527 public: 528 UEdge() {} 529 UEdge (Invalid) { id = -1; } 530 bool operator==(const UEdge i) const {return id==i.id;} 531 bool operator!=(const UEdge i) const {return id!=i.id;} 532 bool operator<(const UEdge i) const {return id<i.id;} 533 }; 534 535 void construct(int aNodeNum, int bNodeNum) { 536 _aNodeNum = aNodeNum; 537 _bNodeNum = bNodeNum; 538 _edgeNum = aNodeNum * bNodeNum; 539 } 540 541 void firstANode(Node& node) const { 542 node.id = 2 * _aNodeNum - 2; 543 if (node.id < 0) node.id = -1; 544 } 545 void nextANode(Node& node) const { 546 node.id -= 2; 547 if (node.id < 0) node.id = -1; 548 } 549 550 void firstBNode(Node& node) const { 551 node.id = 2 * _bNodeNum - 1; 552 } 553 void nextBNode(Node& node) const { 554 node.id -= 2; 555 } 556 557 void first(Node& node) const { 558 if (_aNodeNum > 0) { 559 node.id = 2 * _aNodeNum - 2; 560 } else { 561 node.id = 2 * _bNodeNum - 1; 562 } 563 } 564 void next(Node& node) const { 565 node.id -= 2; 566 if (node.id == -2) { 567 node.id = 2 * _bNodeNum - 1; 568 } 569 } 570 571 void first(UEdge& edge) const { 572 edge.id = _edgeNum - 1; 573 } 574 void next(UEdge& edge) const { 575 --edge.id; 576 } 577 578 void firstFromANode(UEdge& edge, const Node& node) const { 579 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 580 edge.id = (node.id >> 1) * _bNodeNum; 581 } 582 void nextFromANode(UEdge& edge) const { 583 ++(edge.id); 584 if (edge.id % _bNodeNum == 0) edge.id = -1; 585 } 586 587 void firstFromBNode(UEdge& edge, const Node& node) const { 588 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 589 edge.id = (node.id >> 1); 590 } 591 void nextFromBNode(UEdge& edge) const { 592 edge.id += _bNodeNum; 593 if (edge.id >= _edgeNum) edge.id = -1; 594 } 595 596 static int id(const Node& node) { 597 return node.id; 598 } 599 static Node nodeFromId(int id) { 600 return Node(id); 601 } 602 int maxNodeId() const { 603 return _aNodeNum > _bNodeNum ? 604 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1; 605 } 606 607 static int id(const UEdge& edge) { 608 return edge.id; 609 } 610 static UEdge uEdgeFromId(int id) { 611 return UEdge(id); 612 } 613 int maxUEdgeId() const { 614 return _edgeNum - 1; 615 } 616 617 static int aNodeId(const Node& node) { 618 return node.id >> 1; 619 } 620 static Node fromANodeId(int id) { 621 return Node(id << 1); 622 } 623 int maxANodeId() const { 624 return _aNodeNum; 625 } 626 627 static int bNodeId(const Node& node) { 628 return node.id >> 1; 629 } 630 static Node fromBNodeId(int id) { 631 return Node((id << 1) + 1); 632 } 633 int maxBNodeId() const { 634 return _bNodeNum; 635 } 636 637 Node aNode(const UEdge& edge) const { 638 return Node((edge.id / _bNodeNum) << 1); 639 } 640 Node bNode(const UEdge& edge) const { 641 return Node(((edge.id % _bNodeNum) << 1) + 1); 642 } 643 644 static bool aNode(const Node& node) { 645 return (node.id & 1) == 0; 646 } 647 648 static bool bNode(const Node& node) { 649 return (node.id & 1) == 1; 650 } 651 652 static Node aNode(int index) { 653 return Node(index << 1); 654 } 655 656 static Node bNode(int index) { 657 return Node((index << 1) + 1); 658 } 659 660 typedef True NodeNumTag; 661 int nodeNum() const { return _aNodeNum + _bNodeNum; } 662 int aNodeNum() const { return _aNodeNum; } 663 int bNodeNum() const { return _bNodeNum; } 664 665 typedef True EdgeNumTag; 666 int uEdgeNum() const { return _edgeNum; } 667 668 }; 669 670 671 typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase; 672 673 674 /// \ingroup graphs 675 /// 676 /// \brief An undirected full bipartite graph class. 677 /// 678 /// This is a simple and fast bipartite undirected full graph implementation. 679 /// It is completely static, so you can neither add nor delete either 680 /// edges or nodes. 681 /// 682 /// \sa FullUGraphBase 683 /// \sa FullGraph 684 /// 685 /// \author Balazs Dezso 686 class FullBpUGraph : 687 public ExtendedFullBpUGraphBase { 688 public: 689 690 typedef ExtendedFullBpUGraphBase Parent; 691 692 FullBpUGraph() { 693 Parent::construct(0, 0); 694 } 695 696 FullBpUGraph(int aNodeNum, int bNodeNum) { 697 Parent::construct(aNodeNum, bNodeNum); 698 } 699 700 /// \brief Resize the graph 701 /// 702 void resize(int n, int m) { 703 Parent::getNotifier(Edge()).clear(); 704 Parent::getNotifier(UEdge()).clear(); 705 Parent::getNotifier(Node()).clear(); 706 Parent::getNotifier(ANode()).clear(); 707 Parent::getNotifier(BNode()).clear(); 708 construct(n, m); 709 Parent::getNotifier(ANode()).build(); 710 Parent::getNotifier(BNode()).build(); 711 Parent::getNotifier(Node()).build(); 712 Parent::getNotifier(UEdge()).build(); 713 Parent::getNotifier(Edge()).build(); 714 } 715 }; 716 249 717 } //namespace lemon 250 718
Note: See TracChangeset
for help on using the changeset viewer.