Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon
- Timestamp:
- 06/30/06 14:15:45 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
- Location:
- lemon
- Files:
-
- 8 deleted
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r2115 r2116 44 44 lemon/floyd_warshall.h \ 45 45 lemon/fredman_tarjan.h \ 46 lemon/full_bpugraph.h \47 46 lemon/full_graph.h \ 48 lemon/full_ugraph.h \49 47 lemon/graph_adaptor.h \ 50 48 lemon/graph_reader.h \ … … 59 57 lemon/lemon_reader.h \ 60 58 lemon/lemon_writer.h \ 61 lemon/list_bpugraph.h \62 59 lemon/list_graph.h \ 63 lemon/list_ugraph.h \64 60 lemon/lp.h \ 65 61 lemon/lp_base.h \ … … 82 78 lemon/refptr.h \ 83 79 lemon/simann.h \ 84 lemon/smart_bpugraph.h \85 80 lemon/smart_graph.h \ 86 lemon/smart_ugraph.h \87 81 lemon/sub_graph.h \ 88 82 lemon/suurballe.h \ … … 99 93 lemon/bits/array_map.h \ 100 94 lemon/bits/base_extender.h \ 101 lemon/bits/bpugraph_extender.h \102 95 lemon/bits/default_map.h \ 103 96 lemon/bits/edge_set_extender.h \ … … 111 104 lemon/bits/mingw32_time.h \ 112 105 lemon/bits/traits.h \ 113 lemon/bits/ugraph_extender.h \114 106 lemon/bits/utility.h \ 115 107 lemon/bits/vector_map.h -
lemon/bits/graph_extender.h
r2115 r2116 21 21 22 22 #include <lemon/bits/invalid.h> 23 #include <lemon/error.h> 23 24 24 25 #include <lemon/bits/map_extender.h> 25 26 #include <lemon/bits/default_map.h> 27 28 #include <lemon/concept_check.h> 29 #include <lemon/concept/maps.h> 26 30 27 31 ///\ingroup graphbits … … 315 319 }; 316 320 321 /// \ingroup graphbits 322 /// 323 /// \brief Extender for the UGraphs 324 template <typename Base> 325 class UGraphExtender : public Base { 326 public: 327 328 typedef Base Parent; 329 typedef UGraphExtender Graph; 330 331 typedef typename Parent::Node Node; 332 typedef typename Parent::Edge Edge; 333 typedef typename Parent::UEdge UEdge; 334 335 // UGraph extension 336 337 int maxId(Node) const { 338 return Parent::maxNodeId(); 339 } 340 341 int maxId(Edge) const { 342 return Parent::maxEdgeId(); 343 } 344 345 int maxId(UEdge) const { 346 return Parent::maxUEdgeId(); 347 } 348 349 Node fromId(int id, Node) const { 350 return Parent::nodeFromId(id); 351 } 352 353 Edge fromId(int id, Edge) const { 354 return Parent::edgeFromId(id); 355 } 356 357 UEdge fromId(int id, UEdge) const { 358 return Parent::uEdgeFromId(id); 359 } 360 361 Node oppositeNode(const Node &n, const UEdge &e) const { 362 if( n == Parent::source(e)) 363 return Parent::target(e); 364 else if( n == Parent::target(e)) 365 return Parent::source(e); 366 else 367 return INVALID; 368 } 369 370 Edge oppositeEdge(const Edge &e) const { 371 return Parent::direct(e, !Parent::direction(e)); 372 } 373 374 using Parent::direct; 375 Edge direct(const UEdge &ue, const Node &s) const { 376 return Parent::direct(ue, Parent::source(ue) == s); 377 } 378 379 // Alterable extension 380 381 typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier; 382 typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier; 383 typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier; 384 385 386 protected: 387 388 mutable NodeNotifier node_notifier; 389 mutable EdgeNotifier edge_notifier; 390 mutable UEdgeNotifier uedge_notifier; 391 392 public: 393 394 NodeNotifier& getNotifier(Node) const { 395 return node_notifier; 396 } 397 398 EdgeNotifier& getNotifier(Edge) const { 399 return edge_notifier; 400 } 401 402 UEdgeNotifier& getNotifier(UEdge) const { 403 return uedge_notifier; 404 } 405 406 407 408 class NodeIt : public Node { 409 const Graph* graph; 410 public: 411 412 NodeIt() {} 413 414 NodeIt(Invalid i) : Node(i) { } 415 416 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 417 _graph.first(static_cast<Node&>(*this)); 418 } 419 420 NodeIt(const Graph& _graph, const Node& node) 421 : Node(node), graph(&_graph) {} 422 423 NodeIt& operator++() { 424 graph->next(*this); 425 return *this; 426 } 427 428 }; 429 430 431 class EdgeIt : public Edge { 432 const Graph* graph; 433 public: 434 435 EdgeIt() { } 436 437 EdgeIt(Invalid i) : Edge(i) { } 438 439 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 440 _graph.first(static_cast<Edge&>(*this)); 441 } 442 443 EdgeIt(const Graph& _graph, const Edge& e) : 444 Edge(e), graph(&_graph) { } 445 446 EdgeIt& operator++() { 447 graph->next(*this); 448 return *this; 449 } 450 451 }; 452 453 454 class OutEdgeIt : public Edge { 455 const Graph* graph; 456 public: 457 458 OutEdgeIt() { } 459 460 OutEdgeIt(Invalid i) : Edge(i) { } 461 462 OutEdgeIt(const Graph& _graph, const Node& node) 463 : graph(&_graph) { 464 _graph.firstOut(*this, node); 465 } 466 467 OutEdgeIt(const Graph& _graph, const Edge& edge) 468 : Edge(edge), graph(&_graph) {} 469 470 OutEdgeIt& operator++() { 471 graph->nextOut(*this); 472 return *this; 473 } 474 475 }; 476 477 478 class InEdgeIt : public Edge { 479 const Graph* graph; 480 public: 481 482 InEdgeIt() { } 483 484 InEdgeIt(Invalid i) : Edge(i) { } 485 486 InEdgeIt(const Graph& _graph, const Node& node) 487 : graph(&_graph) { 488 _graph.firstIn(*this, node); 489 } 490 491 InEdgeIt(const Graph& _graph, const Edge& edge) : 492 Edge(edge), graph(&_graph) {} 493 494 InEdgeIt& operator++() { 495 graph->nextIn(*this); 496 return *this; 497 } 498 499 }; 500 501 502 class UEdgeIt : public Parent::UEdge { 503 const Graph* graph; 504 public: 505 506 UEdgeIt() { } 507 508 UEdgeIt(Invalid i) : UEdge(i) { } 509 510 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 511 _graph.first(static_cast<UEdge&>(*this)); 512 } 513 514 UEdgeIt(const Graph& _graph, const UEdge& e) : 515 UEdge(e), graph(&_graph) { } 516 517 UEdgeIt& operator++() { 518 graph->next(*this); 519 return *this; 520 } 521 522 }; 523 524 class IncEdgeIt : public Parent::UEdge { 525 friend class UGraphExtender; 526 const Graph* graph; 527 bool direction; 528 public: 529 530 IncEdgeIt() { } 531 532 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } 533 534 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 535 _graph.firstInc(*this, direction, n); 536 } 537 538 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 539 : graph(&_graph), UEdge(ue) { 540 direction = (_graph.source(ue) == n); 541 } 542 543 IncEdgeIt& operator++() { 544 graph->nextInc(*this, direction); 545 return *this; 546 } 547 }; 548 549 /// \brief Base node of the iterator 550 /// 551 /// Returns the base node (ie. the source in this case) of the iterator 552 Node baseNode(const OutEdgeIt &e) const { 553 return Parent::source((Edge)e); 554 } 555 /// \brief Running node of the iterator 556 /// 557 /// Returns the running node (ie. the target in this case) of the 558 /// iterator 559 Node runningNode(const OutEdgeIt &e) const { 560 return Parent::target((Edge)e); 561 } 562 563 /// \brief Base node of the iterator 564 /// 565 /// Returns the base node (ie. the target in this case) of the iterator 566 Node baseNode(const InEdgeIt &e) const { 567 return Parent::target((Edge)e); 568 } 569 /// \brief Running node of the iterator 570 /// 571 /// Returns the running node (ie. the source in this case) of the 572 /// iterator 573 Node runningNode(const InEdgeIt &e) const { 574 return Parent::source((Edge)e); 575 } 576 577 /// Base node of the iterator 578 /// 579 /// Returns the base node of the iterator 580 Node baseNode(const IncEdgeIt &e) const { 581 return e.direction ? source(e) : target(e); 582 } 583 /// Running node of the iterator 584 /// 585 /// Returns the running node of the iterator 586 Node runningNode(const IncEdgeIt &e) const { 587 return e.direction ? target(e) : source(e); 588 } 589 590 // Mappable extension 591 592 template <typename _Value> 593 class NodeMap 594 : public MapExtender<DefaultMap<Graph, Node, _Value> > { 595 public: 596 typedef UGraphExtender Graph; 597 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; 598 599 NodeMap(const Graph& graph) 600 : Parent(graph) {} 601 NodeMap(const Graph& graph, const _Value& value) 602 : Parent(graph, value) {} 603 604 NodeMap& operator=(const NodeMap& cmap) { 605 return operator=<NodeMap>(cmap); 606 } 607 608 template <typename CMap> 609 NodeMap& operator=(const CMap& cmap) { 610 Parent::operator=(cmap); 611 return *this; 612 } 613 614 }; 615 616 template <typename _Value> 617 class EdgeMap 618 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 619 public: 620 typedef UGraphExtender Graph; 621 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 622 623 EdgeMap(const Graph& graph) 624 : Parent(graph) {} 625 EdgeMap(const Graph& graph, const _Value& value) 626 : Parent(graph, value) {} 627 628 EdgeMap& operator=(const EdgeMap& cmap) { 629 return operator=<EdgeMap>(cmap); 630 } 631 632 template <typename CMap> 633 EdgeMap& operator=(const CMap& cmap) { 634 Parent::operator=(cmap); 635 return *this; 636 } 637 }; 638 639 640 template <typename _Value> 641 class UEdgeMap 642 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { 643 public: 644 typedef UGraphExtender Graph; 645 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; 646 647 UEdgeMap(const Graph& graph) 648 : Parent(graph) {} 649 650 UEdgeMap(const Graph& graph, const _Value& value) 651 : Parent(graph, value) {} 652 653 UEdgeMap& operator=(const UEdgeMap& cmap) { 654 return operator=<UEdgeMap>(cmap); 655 } 656 657 template <typename CMap> 658 UEdgeMap& operator=(const CMap& cmap) { 659 Parent::operator=(cmap); 660 return *this; 661 } 662 663 }; 664 665 // Alteration extension 666 667 Node addNode() { 668 Node node = Parent::addNode(); 669 getNotifier(Node()).add(node); 670 return node; 671 } 672 673 UEdge addEdge(const Node& from, const Node& to) { 674 UEdge uedge = Parent::addEdge(from, to); 675 getNotifier(UEdge()).add(uedge); 676 getNotifier(Edge()).add(Parent::direct(uedge, true)); 677 getNotifier(Edge()).add(Parent::direct(uedge, false)); 678 return uedge; 679 } 680 681 void clear() { 682 getNotifier(Edge()).clear(); 683 getNotifier(UEdge()).clear(); 684 getNotifier(Node()).clear(); 685 Parent::clear(); 686 } 687 688 void erase(const Node& node) { 689 Edge edge; 690 Parent::firstOut(edge, node); 691 while (edge != INVALID ) { 692 erase(edge); 693 Parent::firstOut(edge, node); 694 } 695 696 Parent::firstIn(edge, node); 697 while (edge != INVALID ) { 698 erase(edge); 699 Parent::firstIn(edge, node); 700 } 701 702 getNotifier(Node()).erase(node); 703 Parent::erase(node); 704 } 705 706 void erase(const UEdge& uedge) { 707 getNotifier(Edge()).erase(Parent::direct(uedge, true)); 708 getNotifier(Edge()).erase(Parent::direct(uedge, false)); 709 getNotifier(UEdge()).erase(uedge); 710 Parent::erase(uedge); 711 } 712 713 UGraphExtender() { 714 node_notifier.setContainer(*this); 715 edge_notifier.setContainer(*this); 716 uedge_notifier.setContainer(*this); 717 } 718 719 ~UGraphExtender() { 720 uedge_notifier.clear(); 721 edge_notifier.clear(); 722 node_notifier.clear(); 723 } 724 725 }; 726 727 /// \ingroup graphbits 728 /// 729 /// \brief Extender for the BpUGraphs 730 template <typename Base> 731 class BpUGraphExtender : public Base { 732 public: 733 typedef Base Parent; 734 typedef BpUGraphExtender Graph; 735 736 typedef typename Parent::Node Node; 737 typedef typename Parent::UEdge UEdge; 738 739 740 using Parent::first; 741 using Parent::next; 742 743 using Parent::id; 744 745 class ANode : public Node { 746 friend class BpUGraphExtender; 747 public: 748 ANode() {} 749 ANode(const Node& node) : Node(node) { 750 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 751 typename Parent::NodeSetError()); 752 } 753 ANode(Invalid) : Node(INVALID) {} 754 }; 755 756 void first(ANode& node) const { 757 Parent::firstANode(static_cast<Node&>(node)); 758 } 759 void next(ANode& node) const { 760 Parent::nextANode(static_cast<Node&>(node)); 761 } 762 763 int id(const ANode& node) const { 764 return Parent::aNodeId(node); 765 } 766 767 class BNode : public Node { 768 friend class BpUGraphExtender; 769 public: 770 BNode() {} 771 BNode(const Node& node) : Node(node) { 772 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 773 typename Parent::NodeSetError()); 774 } 775 BNode(Invalid) : Node(INVALID) {} 776 }; 777 778 void first(BNode& node) const { 779 Parent::firstBNode(static_cast<Node&>(node)); 780 } 781 void next(BNode& node) const { 782 Parent::nextBNode(static_cast<Node&>(node)); 783 } 784 785 int id(const BNode& node) const { 786 return Parent::aNodeId(node); 787 } 788 789 Node source(const UEdge& edge) const { 790 return aNode(edge); 791 } 792 Node target(const UEdge& edge) const { 793 return bNode(edge); 794 } 795 796 void firstInc(UEdge& edge, bool& direction, const Node& node) const { 797 if (Parent::aNode(node)) { 798 Parent::firstFromANode(edge, node); 799 direction = true; 800 } else { 801 Parent::firstFromBNode(edge, node); 802 direction = static_cast<UEdge&>(edge) == INVALID; 803 } 804 } 805 void nextInc(UEdge& edge, bool& direction) const { 806 if (direction) { 807 Parent::nextFromANode(edge); 808 } else { 809 Parent::nextFromBNode(edge); 810 if (edge == INVALID) direction = true; 811 } 812 } 813 814 class Edge : public UEdge { 815 friend class BpUGraphExtender; 816 protected: 817 bool forward; 818 819 Edge(const UEdge& edge, bool _forward) 820 : UEdge(edge), forward(_forward) {} 821 822 public: 823 Edge() {} 824 Edge (Invalid) : UEdge(INVALID), forward(true) {} 825 bool operator==(const Edge& i) const { 826 return UEdge::operator==(i) && forward == i.forward; 827 } 828 bool operator!=(const Edge& i) const { 829 return UEdge::operator!=(i) || forward != i.forward; 830 } 831 bool operator<(const Edge& i) const { 832 return UEdge::operator<(i) || 833 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); 834 } 835 }; 836 837 void first(Edge& edge) const { 838 Parent::first(static_cast<UEdge&>(edge)); 839 edge.forward = true; 840 } 841 842 void next(Edge& edge) const { 843 if (!edge.forward) { 844 Parent::next(static_cast<UEdge&>(edge)); 845 } 846 edge.forward = !edge.forward; 847 } 848 849 void firstOut(Edge& edge, const Node& node) const { 850 if (Parent::aNode(node)) { 851 Parent::firstFromANode(edge, node); 852 edge.forward = true; 853 } else { 854 Parent::firstFromBNode(edge, node); 855 edge.forward = static_cast<UEdge&>(edge) == INVALID; 856 } 857 } 858 void nextOut(Edge& edge) const { 859 if (edge.forward) { 860 Parent::nextFromANode(edge); 861 } else { 862 Parent::nextFromBNode(edge); 863 edge.forward = static_cast<UEdge&>(edge) == INVALID; 864 } 865 } 866 867 void firstIn(Edge& edge, const Node& node) const { 868 if (Parent::bNode(node)) { 869 Parent::firstFromBNode(edge, node); 870 edge.forward = true; 871 } else { 872 Parent::firstFromANode(edge, node); 873 edge.forward = static_cast<UEdge&>(edge) == INVALID; 874 } 875 } 876 void nextIn(Edge& edge) const { 877 if (edge.forward) { 878 Parent::nextFromBNode(edge); 879 } else { 880 Parent::nextFromANode(edge); 881 edge.forward = static_cast<UEdge&>(edge) == INVALID; 882 } 883 } 884 885 Node source(const Edge& edge) const { 886 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); 887 } 888 Node target(const Edge& edge) const { 889 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); 890 } 891 892 int id(const Edge& edge) const { 893 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 894 (edge.forward ? 0 : 1); 895 } 896 Edge edgeFromId(int id) const { 897 return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); 898 } 899 int maxEdgeId() const { 900 return (Parent::maxUEdgeId(UEdge()) << 1) + 1; 901 } 902 903 bool direction(const Edge& edge) const { 904 return edge.forward; 905 } 906 907 Edge direct(const UEdge& edge, bool direction) const { 908 return Edge(edge, direction); 909 } 910 911 int edgeNum() const { 912 return 2 * Parent::uEdgeNum(); 913 } 914 915 int uEdgeNum() const { 916 return Parent::uEdgeNum(); 917 } 918 919 Node oppositeNode(const UEdge& edge, const Node& node) const { 920 return source(edge) == node ? 921 target(edge) : source(edge); 922 } 923 924 Edge direct(const UEdge& edge, const Node& node) const { 925 return Edge(edge, node == Parent::source(edge)); 926 } 927 928 Edge oppositeEdge(const Edge& edge) const { 929 return Parent::direct(edge, !Parent::direction(edge)); 930 } 931 932 933 int maxId(Node) const { 934 return Parent::maxNodeId(); 935 } 936 int maxId(BNode) const { 937 return Parent::maxBNodeId(); 938 } 939 int maxId(ANode) const { 940 return Parent::maxANodeId(); 941 } 942 int maxId(Edge) const { 943 return maxEdgeId(); 944 } 945 int maxId(UEdge) const { 946 return Parent::maxUEdgeId(); 947 } 948 949 950 Node fromId(int id, Node) const { 951 return Parent::nodeFromId(id); 952 } 953 ANode fromId(int id, ANode) const { 954 return Parent::fromANodeId(id); 955 } 956 BNode fromId(int id, BNode) const { 957 return Parent::fromBNodeId(id); 958 } 959 Edge fromId(int id, Edge) const { 960 return Parent::edgeFromId(id); 961 } 962 UEdge fromId(int id, UEdge) const { 963 return Parent::uEdgeFromId(id); 964 } 965 966 typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier; 967 typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier; 968 typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier; 969 typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier; 970 typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier; 971 972 protected: 973 974 mutable ANodeNotifier anode_notifier; 975 mutable BNodeNotifier bnode_notifier; 976 mutable NodeNotifier node_notifier; 977 mutable EdgeNotifier edge_notifier; 978 mutable UEdgeNotifier uedge_notifier; 979 980 public: 981 982 NodeNotifier& getNotifier(Node) const { 983 return node_notifier; 984 } 985 986 ANodeNotifier& getNotifier(ANode) const { 987 return anode_notifier; 988 } 989 990 BNodeNotifier& getNotifier(BNode) const { 991 return bnode_notifier; 992 } 993 994 EdgeNotifier& getNotifier(Edge) const { 995 return edge_notifier; 996 } 997 998 UEdgeNotifier& getNotifier(UEdge) const { 999 return uedge_notifier; 1000 } 1001 1002 class NodeIt : public Node { 1003 const Graph* graph; 1004 public: 1005 1006 NodeIt() { } 1007 1008 NodeIt(Invalid i) : Node(INVALID) { } 1009 1010 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 1011 graph->first(static_cast<Node&>(*this)); 1012 } 1013 1014 NodeIt(const Graph& _graph, const Node& node) 1015 : Node(node), graph(&_graph) { } 1016 1017 NodeIt& operator++() { 1018 graph->next(*this); 1019 return *this; 1020 } 1021 1022 }; 1023 1024 class ANodeIt : public Node { 1025 friend class BpUGraphExtender; 1026 const Graph* graph; 1027 public: 1028 1029 ANodeIt() { } 1030 1031 ANodeIt(Invalid i) : Node(INVALID) { } 1032 1033 explicit ANodeIt(const Graph& _graph) : graph(&_graph) { 1034 graph->firstANode(static_cast<Node&>(*this)); 1035 } 1036 1037 ANodeIt(const Graph& _graph, const Node& node) 1038 : Node(node), graph(&_graph) {} 1039 1040 ANodeIt& operator++() { 1041 graph->nextANode(*this); 1042 return *this; 1043 } 1044 }; 1045 1046 class BNodeIt : public Node { 1047 friend class BpUGraphExtender; 1048 const Graph* graph; 1049 public: 1050 1051 BNodeIt() { } 1052 1053 BNodeIt(Invalid i) : Node(INVALID) { } 1054 1055 explicit BNodeIt(const Graph& _graph) : graph(&_graph) { 1056 graph->firstBNode(static_cast<Node&>(*this)); 1057 } 1058 1059 BNodeIt(const Graph& _graph, const Node& node) 1060 : Node(node), graph(&_graph) {} 1061 1062 BNodeIt& operator++() { 1063 graph->nextBNode(*this); 1064 return *this; 1065 } 1066 }; 1067 1068 class EdgeIt : public Edge { 1069 friend class BpUGraphExtender; 1070 const Graph* graph; 1071 public: 1072 1073 EdgeIt() { } 1074 1075 EdgeIt(Invalid i) : Edge(INVALID) { } 1076 1077 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 1078 graph->first(static_cast<Edge&>(*this)); 1079 } 1080 1081 EdgeIt(const Graph& _graph, const Edge& edge) 1082 : Edge(edge), graph(&_graph) { } 1083 1084 EdgeIt& operator++() { 1085 graph->next(*this); 1086 return *this; 1087 } 1088 1089 }; 1090 1091 class UEdgeIt : public UEdge { 1092 friend class BpUGraphExtender; 1093 const Graph* graph; 1094 public: 1095 1096 UEdgeIt() { } 1097 1098 UEdgeIt(Invalid i) : UEdge(INVALID) { } 1099 1100 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 1101 graph->first(static_cast<UEdge&>(*this)); 1102 } 1103 1104 UEdgeIt(const Graph& _graph, const UEdge& edge) 1105 : UEdge(edge), graph(&_graph) { } 1106 1107 UEdgeIt& operator++() { 1108 graph->next(*this); 1109 return *this; 1110 } 1111 }; 1112 1113 class OutEdgeIt : public Edge { 1114 friend class BpUGraphExtender; 1115 const Graph* graph; 1116 public: 1117 1118 OutEdgeIt() { } 1119 1120 OutEdgeIt(Invalid i) : Edge(i) { } 1121 1122 OutEdgeIt(const Graph& _graph, const Node& node) 1123 : graph(&_graph) { 1124 graph->firstOut(*this, node); 1125 } 1126 1127 OutEdgeIt(const Graph& _graph, const Edge& edge) 1128 : Edge(edge), graph(&_graph) {} 1129 1130 OutEdgeIt& operator++() { 1131 graph->nextOut(*this); 1132 return *this; 1133 } 1134 1135 }; 1136 1137 1138 class InEdgeIt : public Edge { 1139 friend class BpUGraphExtender; 1140 const Graph* graph; 1141 public: 1142 1143 InEdgeIt() { } 1144 1145 InEdgeIt(Invalid i) : Edge(i) { } 1146 1147 InEdgeIt(const Graph& _graph, const Node& node) 1148 : graph(&_graph) { 1149 graph->firstIn(*this, node); 1150 } 1151 1152 InEdgeIt(const Graph& _graph, const Edge& edge) : 1153 Edge(edge), graph(&_graph) {} 1154 1155 InEdgeIt& operator++() { 1156 graph->nextIn(*this); 1157 return *this; 1158 } 1159 1160 }; 1161 1162 /// \brief Base node of the iterator 1163 /// 1164 /// Returns the base node (ie. the source in this case) of the iterator 1165 Node baseNode(const OutEdgeIt &e) const { 1166 return Parent::source((Edge&)e); 1167 } 1168 /// \brief Running node of the iterator 1169 /// 1170 /// Returns the running node (ie. the target in this case) of the 1171 /// iterator 1172 Node runningNode(const OutEdgeIt &e) const { 1173 return Parent::target((Edge&)e); 1174 } 1175 1176 /// \brief Base node of the iterator 1177 /// 1178 /// Returns the base node (ie. the target in this case) of the iterator 1179 Node baseNode(const InEdgeIt &e) const { 1180 return Parent::target((Edge&)e); 1181 } 1182 /// \brief Running node of the iterator 1183 /// 1184 /// Returns the running node (ie. the source in this case) of the 1185 /// iterator 1186 Node runningNode(const InEdgeIt &e) const { 1187 return Parent::source((Edge&)e); 1188 } 1189 1190 class IncEdgeIt : public Parent::UEdge { 1191 friend class BpUGraphExtender; 1192 const Graph* graph; 1193 bool direction; 1194 public: 1195 1196 IncEdgeIt() { } 1197 1198 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } 1199 1200 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 1201 graph->firstInc(*this, direction, n); 1202 } 1203 1204 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 1205 : graph(&_graph), UEdge(ue) { 1206 direction = (graph->source(ue) == n); 1207 } 1208 1209 IncEdgeIt& operator++() { 1210 graph->nextInc(*this, direction); 1211 return *this; 1212 } 1213 }; 1214 1215 1216 /// Base node of the iterator 1217 /// 1218 /// Returns the base node of the iterator 1219 Node baseNode(const IncEdgeIt &e) const { 1220 return e.direction ? source(e) : target(e); 1221 } 1222 1223 /// Running node of the iterator 1224 /// 1225 /// Returns the running node of the iterator 1226 Node runningNode(const IncEdgeIt &e) const { 1227 return e.direction ? target(e) : source(e); 1228 } 1229 1230 template <typename _Value> 1231 class ANodeMap 1232 : public MapExtender<DefaultMap<Graph, ANode, _Value> > { 1233 public: 1234 typedef BpUGraphExtender Graph; 1235 typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent; 1236 1237 ANodeMap(const Graph& graph) 1238 : Parent(graph) {} 1239 ANodeMap(const Graph& graph, const _Value& value) 1240 : Parent(graph, value) {} 1241 1242 ANodeMap& operator=(const ANodeMap& cmap) { 1243 return operator=<ANodeMap>(cmap); 1244 } 1245 1246 template <typename CMap> 1247 ANodeMap& operator=(const CMap& cmap) { 1248 Parent::operator=(cmap); 1249 return *this; 1250 } 1251 1252 }; 1253 1254 template <typename _Value> 1255 class BNodeMap 1256 : public MapExtender<DefaultMap<Graph, BNode, _Value> > { 1257 public: 1258 typedef BpUGraphExtender Graph; 1259 typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent; 1260 1261 BNodeMap(const Graph& graph) 1262 : Parent(graph) {} 1263 BNodeMap(const Graph& graph, const _Value& value) 1264 : Parent(graph, value) {} 1265 1266 BNodeMap& operator=(const BNodeMap& cmap) { 1267 return operator=<BNodeMap>(cmap); 1268 } 1269 1270 template <typename CMap> 1271 BNodeMap& operator=(const CMap& cmap) { 1272 Parent::operator=(cmap); 1273 return *this; 1274 } 1275 1276 }; 1277 1278 public: 1279 1280 template <typename _Value> 1281 class NodeMap { 1282 public: 1283 typedef BpUGraphExtender Graph; 1284 1285 typedef Node Key; 1286 typedef _Value Value; 1287 1288 /// The reference type of the map; 1289 typedef typename ANodeMap<_Value>::Reference Reference; 1290 /// The const reference type of the map; 1291 typedef typename ANodeMap<_Value>::ConstReference ConstReference; 1292 1293 typedef True ReferenceMapTag; 1294 1295 NodeMap(const Graph& _graph) 1296 : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {} 1297 NodeMap(const Graph& _graph, const _Value& _value) 1298 : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {} 1299 1300 NodeMap& operator=(const NodeMap& cmap) { 1301 return operator=<NodeMap>(cmap); 1302 } 1303 1304 template <typename CMap> 1305 NodeMap& operator=(const CMap& cmap) { 1306 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); 1307 const typename Parent::Notifier* notifier = Parent::getNotifier(); 1308 Edge it; 1309 for (graph.first(it); it != INVALID; graph.next(it)) { 1310 Parent::set(it, cmap[it]); 1311 } 1312 return *this; 1313 } 1314 1315 ConstReference operator[](const Key& node) const { 1316 if (Parent::aNode(node)) { 1317 return aNodeMap[node]; 1318 } else { 1319 return bNodeMap[node]; 1320 } 1321 } 1322 1323 Reference operator[](const Key& node) { 1324 if (Parent::aNode(node)) { 1325 return aNodeMap[node]; 1326 } else { 1327 return bNodeMap[node]; 1328 } 1329 } 1330 1331 void set(const Key& node, const Value& value) { 1332 if (Parent::aNode(node)) { 1333 aNodeMap.set(node, value); 1334 } else { 1335 bNodeMap.set(node, value); 1336 } 1337 } 1338 1339 class MapIt : public NodeIt { 1340 public: 1341 1342 typedef NodeIt Parent; 1343 1344 explicit MapIt(NodeMap& _map) 1345 : Parent(_map.graph), map(_map) {} 1346 1347 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { 1348 return map[*this]; 1349 } 1350 1351 typename MapTraits<NodeMap>::ReturnValue operator*() { 1352 return map[*this]; 1353 } 1354 1355 void set(const Value& value) { 1356 map.set(*this, value); 1357 } 1358 1359 private: 1360 NodeMap& map; 1361 }; 1362 1363 class ConstMapIt : public NodeIt { 1364 public: 1365 1366 typedef NodeIt Parent; 1367 1368 explicit ConstMapIt(const NodeMap& _map) 1369 : Parent(_map.graph), map(_map) {} 1370 1371 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { 1372 return map[*this]; 1373 } 1374 1375 private: 1376 const NodeMap& map; 1377 }; 1378 1379 class ItemIt : public NodeIt { 1380 public: 1381 1382 typedef NodeIt Parent; 1383 1384 explicit ItemIt(const NodeMap& _map) 1385 : Parent(_map.graph) {} 1386 1387 }; 1388 1389 private: 1390 const Graph& graph; 1391 ANodeMap<_Value> aNodeMap; 1392 BNodeMap<_Value> bNodeMap; 1393 }; 1394 1395 1396 template <typename _Value> 1397 class EdgeMap 1398 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 1399 public: 1400 typedef BpUGraphExtender Graph; 1401 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 1402 1403 EdgeMap(const Graph& graph) 1404 : Parent(graph) {} 1405 EdgeMap(const Graph& graph, const _Value& value) 1406 : Parent(graph, value) {} 1407 1408 EdgeMap& operator=(const EdgeMap& cmap) { 1409 return operator=<EdgeMap>(cmap); 1410 } 1411 1412 template <typename CMap> 1413 EdgeMap& operator=(const CMap& cmap) { 1414 Parent::operator=(cmap); 1415 return *this; 1416 } 1417 }; 1418 1419 template <typename _Value> 1420 class UEdgeMap 1421 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { 1422 public: 1423 typedef BpUGraphExtender Graph; 1424 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; 1425 1426 UEdgeMap(const Graph& graph) 1427 : Parent(graph) {} 1428 UEdgeMap(const Graph& graph, const _Value& value) 1429 : Parent(graph, value) {} 1430 1431 UEdgeMap& operator=(const UEdgeMap& cmap) { 1432 return operator=<UEdgeMap>(cmap); 1433 } 1434 1435 template <typename CMap> 1436 UEdgeMap& operator=(const CMap& cmap) { 1437 Parent::operator=(cmap); 1438 return *this; 1439 } 1440 }; 1441 1442 1443 Node addANode() { 1444 Node node = Parent::addANode(); 1445 getNotifier(ANode()).add(node); 1446 getNotifier(Node()).add(node); 1447 return node; 1448 } 1449 1450 Node addBNode() { 1451 Node node = Parent::addBNode(); 1452 getNotifier(BNode()).add(node); 1453 getNotifier(Node()).add(node); 1454 return node; 1455 } 1456 1457 UEdge addEdge(const Node& source, const Node& target) { 1458 UEdge uedge = Parent::addEdge(source, target); 1459 getNotifier(UEdge()).add(uedge); 1460 1461 std::vector<Edge> edges; 1462 edges.push_back(direct(uedge, true)); 1463 edges.push_back(direct(uedge, false)); 1464 getNotifier(Edge()).add(edges); 1465 1466 return uedge; 1467 } 1468 1469 void clear() { 1470 getNotifier(Edge()).clear(); 1471 getNotifier(UEdge()).clear(); 1472 getNotifier(Node()).clear(); 1473 getNotifier(BNode()).clear(); 1474 getNotifier(ANode()).clear(); 1475 Parent::clear(); 1476 } 1477 1478 void erase(const Node& node) { 1479 UEdge uedge; 1480 if (Parent::aNode(node)) { 1481 Parent::firstFromANode(uedge, node); 1482 while (uedge != INVALID) { 1483 erase(uedge); 1484 Parent::firstFromANode(uedge, node); 1485 } 1486 } else { 1487 Parent::firstFromBNode(uedge, node); 1488 while (uedge != INVALID) { 1489 erase(uedge); 1490 Parent::firstFromBNode(uedge, node); 1491 } 1492 } 1493 1494 getNotifier(Node()).erase(node); 1495 Parent::erase(node); 1496 } 1497 1498 void erase(const UEdge& uedge) { 1499 std::vector<Edge> edges; 1500 edges.push_back(direct(uedge, true)); 1501 edges.push_back(direct(uedge, false)); 1502 getNotifier(Edge()).erase(edges); 1503 getNotifier(UEdge()).erase(uedge); 1504 Parent::erase(uedge); 1505 } 1506 1507 1508 BpUGraphExtender() { 1509 anode_notifier.setContainer(*this); 1510 bnode_notifier.setContainer(*this); 1511 node_notifier.setContainer(*this); 1512 edge_notifier.setContainer(*this); 1513 uedge_notifier.setContainer(*this); 1514 } 1515 1516 ~BpUGraphExtender() { 1517 uedge_notifier.clear(); 1518 edge_notifier.clear(); 1519 node_notifier.clear(); 1520 anode_notifier.clear(); 1521 bnode_notifier.clear(); 1522 } 1523 1524 1525 }; 1526 317 1527 } 318 1528 -
lemon/edge_set.h
r2115 r2116 23 23 #include <lemon/bits/default_map.h> 24 24 #include <lemon/bits/edge_set_extender.h> 25 #include <lemon/bits/base_extender.h>26 25 27 26 /// \ingroup graphs -
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 -
lemon/grid_ugraph.h
r2115 r2116 25 25 26 26 #include <lemon/bits/base_extender.h> 27 #include <lemon/bits/ ugraph_extender.h>27 #include <lemon/bits/graph_extender.h> 28 28 29 29 #include <lemon/xy.h> -
lemon/list_graph.h
r2115 r2116 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief ListGraph class. 25 24 ///\brief ListGraph, ListUGraph classes. 25 26 #include <lemon/bits/base_extender.h> 26 27 #include <lemon/bits/graph_extender.h> 28 29 #include <lemon/error.h> 27 30 28 31 #include <vector> … … 307 310 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; 308 311 309 /// \ingroup graphs 312 /// \addtogroup graphs 313 /// @{ 310 314 311 315 ///A list graph class. … … 702 706 }; 703 707 708 ///@} 709 710 /**************** Undirected List Graph ****************/ 711 712 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 713 ExtendedListUGraphBase; 714 715 /// \addtogroup graphs 716 /// @{ 717 718 ///An undirected list graph class. 719 720 ///This is a simple and fast erasable undirected graph implementation. 721 /// 722 ///It conforms to the 723 ///\ref concept::UGraph "UGraph" concept. 724 /// 725 ///\sa concept::UGraph. 726 /// 727 ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract() 728 ///haven't been implemented yet. 729 /// 730 class ListUGraph : public ExtendedListUGraphBase { 731 public: 732 typedef ExtendedListUGraphBase Parent; 733 /// \brief Add a new node to the graph. 734 /// 735 /// \return the new node. 736 /// 737 Node addNode() { return Parent::addNode(); } 738 739 /// \brief Add a new edge to the graph. 740 /// 741 /// Add a new edge to the graph with source node \c s 742 /// and target node \c t. 743 /// \return the new undirected edge. 744 UEdge addEdge(const Node& s, const Node& t) { 745 return Parent::addEdge(s, t); 746 } 747 /// \brief Changes the target of \c e to \c n 748 /// 749 /// Changes the target of \c e to \c n 750 /// 751 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s 752 /// referencing the changed edge remain 753 /// valid. However <tt>InEdge</tt>'s are invalidated. 754 void changeTarget(UEdge e, Node n) { 755 Parent::changeTarget(e,n); 756 } 757 /// Changes the source of \c e to \c n 758 /// 759 /// Changes the source of \c e to \c n 760 /// 761 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s 762 ///referencing the changed edge remain 763 ///valid. However <tt>OutEdge</tt>'s are invalidated. 764 void changeSource(UEdge e, Node n) { 765 Parent::changeSource(e,n); 766 } 767 /// \brief Contract two nodes. 768 /// 769 /// This function contracts two nodes. 770 /// 771 /// Node \p b will be removed but instead of deleting 772 /// its neighboring edges, they will be joined to \p a. 773 /// The last parameter \p r controls whether to remove loops. \c true 774 /// means that loops will be removed. 775 /// 776 /// \note The <tt>Edge</tt>s 777 /// referencing a moved edge remain 778 /// valid. 779 void contract(Node a, Node b, bool r = true) { 780 for(IncEdgeIt e(*this, b); e!=INVALID;) { 781 IncEdgeIt f = e; ++f; 782 if (r && runningNode(e) == a) { 783 erase(e); 784 } else if (source(e) == b) { 785 changeSource(e, a); 786 } else { 787 changeTarget(e, a); 788 } 789 e = f; 790 } 791 erase(b); 792 } 793 }; 794 795 796 class ListBpUGraphBase { 797 public: 798 799 class NodeSetError : public LogicError { 800 virtual const char* exceptionName() const { 801 return "lemon::ListBpUGraph::NodeSetError"; 802 } 803 }; 804 805 protected: 806 807 struct NodeT { 808 int first_edge, prev, next; 809 }; 810 811 struct UEdgeT { 812 int aNode, prev_out, next_out; 813 int bNode, prev_in, next_in; 814 }; 815 816 std::vector<NodeT> aNodes; 817 std::vector<NodeT> bNodes; 818 819 std::vector<UEdgeT> edges; 820 821 int first_anode; 822 int first_free_anode; 823 824 int first_bnode; 825 int first_free_bnode; 826 827 int first_free_edge; 828 829 public: 830 831 class Node { 832 friend class ListBpUGraphBase; 833 protected: 834 int id; 835 836 explicit Node(int _id) : id(_id) {} 837 public: 838 Node() {} 839 Node(Invalid) { id = -1; } 840 bool operator==(const Node i) const {return id==i.id;} 841 bool operator!=(const Node i) const {return id!=i.id;} 842 bool operator<(const Node i) const {return id<i.id;} 843 }; 844 845 class UEdge { 846 friend class ListBpUGraphBase; 847 protected: 848 int id; 849 850 explicit UEdge(int _id) { id = _id;} 851 public: 852 UEdge() {} 853 UEdge (Invalid) { id = -1; } 854 bool operator==(const UEdge i) const {return id==i.id;} 855 bool operator!=(const UEdge i) const {return id!=i.id;} 856 bool operator<(const UEdge i) const {return id<i.id;} 857 }; 858 859 ListBpUGraphBase() 860 : first_anode(-1), first_free_anode(-1), 861 first_bnode(-1), first_free_bnode(-1), 862 first_free_edge(-1) {} 863 864 void firstANode(Node& node) const { 865 node.id = first_anode != -1 ? (first_anode << 1) : -1; 866 } 867 void nextANode(Node& node) const { 868 node.id = aNodes[node.id >> 1].next; 869 } 870 871 void firstBNode(Node& node) const { 872 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1; 873 } 874 void nextBNode(Node& node) const { 875 node.id = bNodes[node.id >> 1].next; 876 } 877 878 void first(Node& node) const { 879 if (first_anode != -1) { 880 node.id = (first_anode << 1); 881 } else if (first_bnode != -1) { 882 node.id = (first_bnode << 1) + 1; 883 } else { 884 node.id = -1; 885 } 886 } 887 void next(Node& node) const { 888 if (aNode(node)) { 889 node.id = aNodes[node.id >> 1].next; 890 if (node.id == -1) { 891 if (first_bnode != -1) { 892 node.id = (first_bnode << 1) + 1; 893 } 894 } 895 } else { 896 node.id = bNodes[node.id >> 1].next; 897 } 898 } 899 900 void first(UEdge& edge) const { 901 int aNodeId = first_anode; 902 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { 903 aNodeId = aNodes[aNodeId].next != -1 ? 904 aNodes[aNodeId].next >> 1 : -1; 905 } 906 if (aNodeId != -1) { 907 edge.id = aNodes[aNodeId].first_edge; 908 } else { 909 edge.id = -1; 910 } 911 } 912 void next(UEdge& edge) const { 913 int aNodeId = edges[edge.id].aNode >> 1; 914 edge.id = edges[edge.id].next_out; 915 if (edge.id == -1) { 916 aNodeId = aNodes[aNodeId].next != -1 ? 917 aNodes[aNodeId].next >> 1 : -1; 918 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { 919 aNodeId = aNodes[aNodeId].next != -1 ? 920 aNodes[aNodeId].next >> 1 : -1; 921 } 922 if (aNodeId != -1) { 923 edge.id = aNodes[aNodeId].first_edge; 924 } else { 925 edge.id = -1; 926 } 927 } 928 } 929 930 void firstFromANode(UEdge& edge, const Node& node) const { 931 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 932 edge.id = aNodes[node.id >> 1].first_edge; 933 } 934 void nextFromANode(UEdge& edge) const { 935 edge.id = edges[edge.id].next_out; 936 } 937 938 void firstFromBNode(UEdge& edge, const Node& node) const { 939 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 940 edge.id = bNodes[node.id >> 1].first_edge; 941 } 942 void nextFromBNode(UEdge& edge) const { 943 edge.id = edges[edge.id].next_in; 944 } 945 946 static int id(const Node& node) { 947 return node.id; 948 } 949 static Node nodeFromId(int id) { 950 return Node(id); 951 } 952 int maxNodeId() const { 953 return aNodes.size() > bNodes.size() ? 954 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; 955 } 956 957 static int id(const UEdge& edge) { 958 return edge.id; 959 } 960 static UEdge uEdgeFromId(int id) { 961 return UEdge(id); 962 } 963 int maxUEdgeId() const { 964 return edges.size(); 965 } 966 967 static int aNodeId(const Node& node) { 968 return node.id >> 1; 969 } 970 static Node fromANodeId(int id) { 971 return Node(id << 1); 972 } 973 int maxANodeId() const { 974 return aNodes.size(); 975 } 976 977 static int bNodeId(const Node& node) { 978 return node.id >> 1; 979 } 980 static Node fromBNodeId(int id) { 981 return Node((id << 1) + 1); 982 } 983 int maxBNodeId() const { 984 return bNodes.size(); 985 } 986 987 Node aNode(const UEdge& edge) const { 988 return Node(edges[edge.id].aNode); 989 } 990 Node bNode(const UEdge& edge) const { 991 return Node(edges[edge.id].bNode); 992 } 993 994 static bool aNode(const Node& node) { 995 return (node.id & 1) == 0; 996 } 997 998 static bool bNode(const Node& node) { 999 return (node.id & 1) == 1; 1000 } 1001 1002 Node addANode() { 1003 int aNodeId; 1004 if (first_free_anode == -1) { 1005 aNodeId = aNodes.size(); 1006 aNodes.push_back(NodeT()); 1007 } else { 1008 aNodeId = first_free_anode; 1009 first_free_anode = aNodes[first_free_anode].next; 1010 } 1011 if (first_anode != -1) { 1012 aNodes[aNodeId].next = first_anode << 1; 1013 aNodes[first_anode].prev = aNodeId << 1; 1014 } else { 1015 aNodes[aNodeId].next = -1; 1016 } 1017 aNodes[aNodeId].prev = -1; 1018 first_anode = aNodeId; 1019 aNodes[aNodeId].first_edge = -1; 1020 return Node(aNodeId << 1); 1021 } 1022 1023 Node addBNode() { 1024 int bNodeId; 1025 if (first_free_bnode == -1) { 1026 bNodeId = bNodes.size(); 1027 bNodes.push_back(NodeT()); 1028 } else { 1029 bNodeId = first_free_bnode; 1030 first_free_bnode = bNodes[first_free_bnode].next; 1031 } 1032 if (first_bnode != -1) { 1033 bNodes[bNodeId].next = (first_bnode << 1) + 1; 1034 bNodes[first_bnode].prev = (bNodeId << 1) + 1; 1035 } else { 1036 bNodes[bNodeId].next = -1; 1037 } 1038 first_bnode = bNodeId; 1039 bNodes[bNodeId].first_edge = -1; 1040 return Node((bNodeId << 1) + 1); 1041 } 1042 1043 UEdge addEdge(const Node& source, const Node& target) { 1044 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); 1045 int edgeId; 1046 if (first_free_edge != -1) { 1047 edgeId = first_free_edge; 1048 first_free_edge = edges[edgeId].next_out; 1049 } else { 1050 edgeId = edges.size(); 1051 edges.push_back(UEdgeT()); 1052 } 1053 if ((source.id & 1) == 0) { 1054 edges[edgeId].aNode = source.id; 1055 edges[edgeId].bNode = target.id; 1056 } else { 1057 edges[edgeId].aNode = target.id; 1058 edges[edgeId].bNode = source.id; 1059 } 1060 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge; 1061 edges[edgeId].prev_out = -1; 1062 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) { 1063 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId; 1064 } 1065 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId; 1066 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge; 1067 edges[edgeId].prev_in = -1; 1068 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) { 1069 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; 1070 } 1071 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; 1072 return UEdge(edgeId); 1073 } 1074 1075 void erase(const Node& node) { 1076 if (aNode(node)) { 1077 int aNodeId = node.id >> 1; 1078 if (aNodes[aNodeId].prev != -1) { 1079 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next; 1080 } else { 1081 first_anode = aNodes[aNodeId].next >> 1; 1082 } 1083 if (aNodes[aNodeId].next != -1) { 1084 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev; 1085 } 1086 aNodes[aNodeId].next = first_free_anode; 1087 first_free_anode = aNodeId; 1088 } else { 1089 int bNodeId = node.id >> 1; 1090 if (bNodes[bNodeId].prev != -1) { 1091 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next; 1092 } else { 1093 first_bnode = bNodes[bNodeId].next >> 1; 1094 } 1095 if (bNodes[bNodeId].next != -1) { 1096 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev; 1097 } 1098 bNodes[bNodeId].next = first_free_bnode; 1099 first_free_bnode = bNodeId; 1100 } 1101 } 1102 1103 void erase(const UEdge& edge) { 1104 1105 if (edges[edge.id].prev_out != -1) { 1106 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; 1107 } else { 1108 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out; 1109 } 1110 if (edges[edge.id].next_out != -1) { 1111 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; 1112 } 1113 1114 if (edges[edge.id].prev_in != -1) { 1115 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; 1116 } else { 1117 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in; 1118 } 1119 if (edges[edge.id].next_in != -1) { 1120 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; 1121 } 1122 1123 edges[edge.id].next_out = first_free_edge; 1124 first_free_edge = edge.id; 1125 } 1126 1127 void clear() { 1128 aNodes.clear(); 1129 bNodes.clear(); 1130 edges.clear(); 1131 first_anode = -1; 1132 first_free_anode = -1; 1133 first_bnode = -1; 1134 first_free_bnode = -1; 1135 first_free_edge = -1; 1136 } 1137 1138 }; 1139 1140 1141 typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase; 1142 1143 /// \ingroup graphs 1144 /// 1145 /// \brief A smart bipartite undirected graph class. 1146 /// 1147 /// This is a bipartite undirected graph implementation. 1148 /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" 1149 /// concept. 1150 /// \sa concept::BpUGraph. 1151 /// 1152 class ListBpUGraph : public ExtendedListBpUGraphBase {}; 1153 1154 1155 /// @} 704 1156 } //namespace lemon 705 1157 -
lemon/min_cut.h
r2115 r2116 24 24 25 25 #include <lemon/list_graph.h> 26 #include <lemon/list_ugraph.h>27 26 #include <lemon/bin_heap.h> 28 27 #include <lemon/bucket_heap.h> … … 196 195 template <typename _Graph, typename _CapacityMap, typename _Traits> 197 196 #else 198 template <typename _Graph = List Graph,197 template <typename _Graph = ListUGraph, 199 198 typename _CapacityMap = typename _Graph::template EdgeMap<int>, 200 199 typename _Traits = -
lemon/smart_graph.h
r2115 r2116 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief SmartGraph class.24 ///\brief SmartGraph and SmartUGraph classes. 25 25 26 26 #include <vector> … … 28 28 #include <lemon/bits/invalid.h> 29 29 30 #include <lemon/bits/base_extender.h> 30 31 #include <lemon/bits/graph_extender.h> 31 32 32 33 #include <lemon/bits/utility.h> 34 #include <lemon/error.h> 33 35 34 36 #include <lemon/bits/graph_extender.h> … … 355 357 356 358 359 /**************** Undirected List Graph ****************/ 360 361 typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> > 362 ExtendedSmartUGraphBase; 363 364 /// \ingroup graphs 365 /// 366 /// \brief A smart undirected graph class. 367 /// 368 /// This is a simple and fast undirected graph implementation. 369 /// It is also quite memory efficient, but at the price 370 /// that <b> it does support only limited (only stack-like) 371 /// node and edge deletions</b>. 372 /// Except from this it conforms to 373 /// the \ref concept::UGraph "UGraph" concept. 374 /// \sa concept::UGraph. 375 /// 376 /// \todo Snapshot hasn't been implemented yet. 377 /// 378 class SmartUGraph : public ExtendedSmartUGraphBase { 379 }; 380 381 382 class SmartBpUGraphBase { 383 public: 384 385 class NodeSetError : public LogicError { 386 virtual const char* exceptionName() const { 387 return "lemon::SmartBpUGraph::NodeSetError"; 388 } 389 }; 390 391 protected: 392 393 struct NodeT { 394 int first; 395 NodeT() {} 396 NodeT(int _first) : first(_first) {} 397 }; 398 399 struct UEdgeT { 400 int aNode, next_out; 401 int bNode, next_in; 402 }; 403 404 std::vector<NodeT> aNodes; 405 std::vector<NodeT> bNodes; 406 407 std::vector<UEdgeT> edges; 408 409 public: 410 411 class Node { 412 friend class SmartBpUGraphBase; 413 protected: 414 int id; 415 416 Node(int _id) : id(_id) {} 417 public: 418 Node() {} 419 Node(Invalid) { id = -1; } 420 bool operator==(const Node i) const {return id==i.id;} 421 bool operator!=(const Node i) const {return id!=i.id;} 422 bool operator<(const Node i) const {return id<i.id;} 423 }; 424 425 class UEdge { 426 friend class SmartBpUGraphBase; 427 protected: 428 int id; 429 430 UEdge(int _id) { id = _id;} 431 public: 432 UEdge() {} 433 UEdge (Invalid) { id = -1; } 434 bool operator==(const UEdge i) const {return id==i.id;} 435 bool operator!=(const UEdge i) const {return id!=i.id;} 436 bool operator<(const UEdge i) const {return id<i.id;} 437 }; 438 439 void firstANode(Node& node) const { 440 node.id = 2 * aNodes.size() - 2; 441 if (node.id < 0) node.id = -1; 442 } 443 void nextANode(Node& node) const { 444 node.id -= 2; 445 if (node.id < 0) node.id = -1; 446 } 447 448 void firstBNode(Node& node) const { 449 node.id = 2 * bNodes.size() - 1; 450 } 451 void nextBNode(Node& node) const { 452 node.id -= 2; 453 } 454 455 void first(Node& node) const { 456 if (aNodes.size() > 0) { 457 node.id = 2 * aNodes.size() - 2; 458 } else { 459 node.id = 2 * bNodes.size() - 1; 460 } 461 } 462 void next(Node& node) const { 463 node.id -= 2; 464 if (node.id == -2) { 465 node.id = 2 * bNodes.size() - 1; 466 } 467 } 468 469 void first(UEdge& edge) const { 470 edge.id = edges.size() - 1; 471 } 472 void next(UEdge& edge) const { 473 --edge.id; 474 } 475 476 void firstFromANode(UEdge& edge, const Node& node) const { 477 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 478 edge.id = aNodes[node.id >> 1].first; 479 } 480 void nextFromANode(UEdge& edge) const { 481 edge.id = edges[edge.id].next_out; 482 } 483 484 void firstFromBNode(UEdge& edge, const Node& node) const { 485 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 486 edge.id = bNodes[node.id >> 1].first; 487 } 488 void nextFromBNode(UEdge& edge) const { 489 edge.id = edges[edge.id].next_in; 490 } 491 492 static int id(const Node& node) { 493 return node.id; 494 } 495 static Node nodeFromId(int id) { 496 return Node(id); 497 } 498 int maxNodeId() const { 499 return aNodes.size() > bNodes.size() ? 500 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; 501 } 502 503 static int id(const UEdge& edge) { 504 return edge.id; 505 } 506 static UEdge uEdgeFromId(int id) { 507 return UEdge(id); 508 } 509 int maxUEdgeId() const { 510 return edges.size(); 511 } 512 513 static int aNodeId(const Node& node) { 514 return node.id >> 1; 515 } 516 static Node fromANodeId(int id) { 517 return Node(id << 1); 518 } 519 int maxANodeId() const { 520 return aNodes.size(); 521 } 522 523 static int bNodeId(const Node& node) { 524 return node.id >> 1; 525 } 526 static Node fromBNodeId(int id) { 527 return Node((id << 1) + 1); 528 } 529 int maxBNodeId() const { 530 return bNodes.size(); 531 } 532 533 Node aNode(const UEdge& edge) const { 534 return Node(edges[edge.id].aNode); 535 } 536 Node bNode(const UEdge& edge) const { 537 return Node(edges[edge.id].bNode); 538 } 539 540 static bool aNode(const Node& node) { 541 return (node.id & 1) == 0; 542 } 543 544 static bool bNode(const Node& node) { 545 return (node.id & 1) == 1; 546 } 547 548 Node addANode() { 549 NodeT nodeT; 550 nodeT.first = -1; 551 aNodes.push_back(nodeT); 552 return Node(aNodes.size() * 2 - 2); 553 } 554 555 Node addBNode() { 556 NodeT nodeT; 557 nodeT.first = -1; 558 bNodes.push_back(nodeT); 559 return Node(bNodes.size() * 2 - 1); 560 } 561 562 UEdge addEdge(const Node& source, const Node& target) { 563 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); 564 UEdgeT edgeT; 565 if ((source.id & 1) == 0) { 566 edgeT.aNode = source.id; 567 edgeT.bNode = target.id; 568 } else { 569 edgeT.aNode = target.id; 570 edgeT.bNode = source.id; 571 } 572 edgeT.next_out = aNodes[edgeT.aNode >> 1].first; 573 aNodes[edgeT.aNode >> 1].first = edges.size(); 574 edgeT.next_in = bNodes[edgeT.bNode >> 1].first; 575 bNodes[edgeT.bNode >> 1].first = edges.size(); 576 edges.push_back(edgeT); 577 return UEdge(edges.size() - 1); 578 } 579 580 void clear() { 581 aNodes.clear(); 582 bNodes.clear(); 583 edges.clear(); 584 } 585 586 typedef True NodeNumTag; 587 int nodeNum() const { return aNodes.size() + bNodes.size(); } 588 int aNodeNum() const { return aNodes.size(); } 589 int bNodeNum() const { return bNodes.size(); } 590 591 typedef True EdgeNumTag; 592 int uEdgeNum() const { return edges.size(); } 593 594 }; 595 596 597 typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase; 598 599 /// \ingroup graphs 600 /// 601 /// \brief A smart bipartite undirected graph class. 602 /// 603 /// This is a simple and fast bipartite undirected graph implementation. 604 /// It is also quite memory efficient, but at the price 605 /// that <b> it does not support node and edge deletions</b>. 606 /// Except from this it conforms to 607 /// the \ref concept::BpUGraph "BpUGraph" concept. 608 /// \sa concept::BpUGraph. 609 /// 610 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; 611 612 613 /// @} 357 614 } //namespace lemon 358 615
Note: See TracChangeset
for help on using the changeset viewer.