Changeset 2338:359f0b71919b in lemon-0.x for lemon
- Timestamp:
- 01/11/07 22:06:47 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3130
- Location:
- lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_graph.h
r2302 r2338 99 99 100 100 101 /// Maximum node ID.102 103 /// Maximum node ID.104 ///\sa id(Node)105 101 int maxNodeId() const { return nodes.size()-1; } 106 107 /// Maximum edge ID.108 109 /// Maximum edge ID.110 ///\sa id(Edge)111 102 int maxEdgeId() const { return edges.size()-1; } 112 103 … … 165 156 static Edge edgeFromId(int id) { return Edge(id);} 166 157 167 /// Adds a new node to the graph.168 169 /// Adds a new node to the graph.170 ///171 /// \warning It adds the new node to the front of the list.172 /// (i.e. the lastly added node becomes the first.)173 158 Node addNode() { 174 159 int n; … … 736 721 ///@} 737 722 738 /**************** Undirected List Graph ****************/ 739 740 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 741 ExtendedListUGraphBase; 723 class ListUGraphBase { 724 725 protected: 726 727 struct NodeT { 728 int first_out; 729 int prev, next; 730 }; 731 732 struct EdgeT { 733 int target; 734 int prev_out, next_out; 735 }; 736 737 std::vector<NodeT> nodes; 738 739 int first_node; 740 741 int first_free_node; 742 743 std::vector<EdgeT> edges; 744 745 int first_free_edge; 746 747 public: 748 749 typedef ListUGraphBase Graph; 750 751 class Node { 752 friend class ListUGraphBase; 753 protected: 754 755 int id; 756 explicit Node(int pid) { id = pid;} 757 758 public: 759 Node() {} 760 Node (Invalid) { id = -1; } 761 bool operator==(const Node& node) const {return id == node.id;} 762 bool operator!=(const Node& node) const {return id != node.id;} 763 bool operator<(const Node& node) const {return id < node.id;} 764 }; 765 766 class UEdge { 767 friend class ListUGraphBase; 768 protected: 769 770 int id; 771 explicit UEdge(int pid) { id = pid;} 772 773 public: 774 UEdge() {} 775 UEdge (Invalid) { id = -1; } 776 bool operator==(const UEdge& edge) const {return id == edge.id;} 777 bool operator!=(const UEdge& edge) const {return id != edge.id;} 778 bool operator<(const UEdge& edge) const {return id < edge.id;} 779 }; 780 781 class Edge { 782 friend class ListUGraphBase; 783 protected: 784 785 int id; 786 explicit Edge(int pid) { id = pid;} 787 788 public: 789 operator UEdge() const { return UEdge(id / 2); } 790 791 Edge() {} 792 Edge (Invalid) { id = -1; } 793 bool operator==(const Edge& edge) const {return id == edge.id;} 794 bool operator!=(const Edge& edge) const {return id != edge.id;} 795 bool operator<(const Edge& edge) const {return id < edge.id;} 796 }; 797 798 799 800 ListUGraphBase() 801 : nodes(), first_node(-1), 802 first_free_node(-1), edges(), first_free_edge(-1) {} 803 804 805 int maxNodeId() const { return nodes.size()-1; } 806 int maxUEdgeId() const { return edges.size() / 2 - 1; } 807 int maxEdgeId() const { return edges.size()-1; } 808 809 Node source(Edge e) const { return Node(edges[e.id ^ 1].target); } 810 Node target(Edge e) const { return Node(edges[e.id].target); } 811 812 Node source(UEdge e) const { return Node(edges[2 * e.id].target); } 813 Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); } 814 815 static bool direction(Edge e) { 816 return (e.id & 1) == 1; 817 } 818 819 static Edge direct(UEdge e, bool d) { 820 return Edge(e.id * 2 + (d ? 1 : 0)); 821 } 822 823 void first(Node& node) const { 824 node.id = first_node; 825 } 826 827 void next(Node& node) const { 828 node.id = nodes[node.id].next; 829 } 830 831 void first(Edge& e) const { 832 int n = first_node; 833 while (n != -1 && nodes[n].first_out == -1) { 834 n = nodes[n].next; 835 } 836 e.id = (n == -1) ? -1 : nodes[n].first_out; 837 } 838 839 void next(Edge& e) const { 840 if (edges[e.id].next_out != -1) { 841 e.id = edges[e.id].next_out; 842 } else { 843 int n = nodes[edges[e.id ^ 1].target].next; 844 while(n != -1 && nodes[n].first_out == -1) { 845 n = nodes[n].next; 846 } 847 e.id = (n == -1) ? -1 : nodes[n].first_out; 848 } 849 } 850 851 void first(UEdge& e) const { 852 int n = first_node; 853 while (n != -1) { 854 e.id = nodes[n].first_out; 855 while ((e.id & 1) != 1) { 856 e.id = edges[e.id].next_out; 857 } 858 if (e.id != -1) { 859 e.id /= 2; 860 return; 861 } 862 n = nodes[n].next; 863 } 864 e.id = -1; 865 } 866 867 void next(UEdge& e) const { 868 int n = edges[e.id * 2].target; 869 e.id = edges[(e.id * 2) | 1].next_out; 870 while ((e.id & 1) != 1) { 871 e.id = edges[e.id].next_out; 872 } 873 if (e.id != -1) { 874 e.id /= 2; 875 return; 876 } 877 n = nodes[n].next; 878 while (n != -1) { 879 e.id = nodes[n].first_out; 880 while ((e.id & 1) != 1) { 881 e.id = edges[e.id].next_out; 882 } 883 if (e.id != -1) { 884 e.id /= 2; 885 return; 886 } 887 n = nodes[n].next; 888 } 889 e.id = -1; 890 } 891 892 void firstOut(Edge &e, const Node& v) const { 893 e.id = nodes[v.id].first_out; 894 } 895 void nextOut(Edge &e) const { 896 e.id = edges[e.id].next_out; 897 } 898 899 void firstIn(Edge &e, const Node& v) const { 900 e.id = ((nodes[v.id].first_out) ^ 1); 901 if (e.id == -2) e.id = -1; 902 } 903 void nextIn(Edge &e) const { 904 e.id = ((edges[e.id ^ 1].next_out) ^ 1); 905 if (e.id == -2) e.id = -1; 906 } 907 908 void firstInc(UEdge &e, bool& d, const Node& v) const { 909 int de = nodes[v.id].first_out; 910 e.id = de / 2; 911 d = ((de & 1) == 1); 912 } 913 void nextInc(UEdge &e, bool& d) const { 914 int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out); 915 e.id = de / 2; 916 d = ((de & 1) == 1); 917 } 918 919 static int id(Node v) { return v.id; } 920 static int id(Edge e) { return e.id; } 921 static int id(UEdge e) { return e.id; } 922 923 static Node nodeFromId(int id) { return Node(id);} 924 static Edge edgeFromId(int id) { return Edge(id);} 925 static UEdge uEdgeFromId(int id) { return UEdge(id);} 926 927 Node addNode() { 928 int n; 929 930 if(first_free_node==-1) { 931 n = nodes.size(); 932 nodes.push_back(NodeT()); 933 } else { 934 n = first_free_node; 935 first_free_node = nodes[n].next; 936 } 937 938 nodes[n].next = first_node; 939 if (first_node != -1) nodes[first_node].prev = n; 940 first_node = n; 941 nodes[n].prev = -1; 942 943 nodes[n].first_out = -1; 944 945 return Node(n); 946 } 947 948 UEdge addEdge(Node u, Node v) { 949 int n; 950 951 if (first_free_edge == -1) { 952 n = edges.size(); 953 edges.push_back(EdgeT()); 954 edges.push_back(EdgeT()); 955 } else { 956 n = first_free_edge; 957 first_free_edge = edges[n].next_out; 958 } 959 960 edges[n].target = u.id; 961 edges[n | 1].target = v.id; 962 963 edges[n].next_out = nodes[v.id].first_out; 964 edges[n | 1].next_out = nodes[u.id].first_out; 965 if (nodes[v.id].first_out != -1) { 966 edges[nodes[v.id].first_out].prev_out = n; 967 } 968 if (nodes[u.id].first_out != -1) { 969 edges[nodes[u.id].first_out].prev_out = (n | 1); 970 } 971 972 edges[n].prev_out = edges[n | 1].prev_out = -1; 973 974 nodes[v.id].first_out = n; 975 nodes[u.id].first_out = (n | 1); 976 977 return UEdge(n / 2); 978 } 979 980 void erase(const Node& node) { 981 int n = node.id; 982 983 if(nodes[n].next != -1) { 984 nodes[nodes[n].next].prev = nodes[n].prev; 985 } 986 987 if(nodes[n].prev != -1) { 988 nodes[nodes[n].prev].next = nodes[n].next; 989 } else { 990 first_node = nodes[n].next; 991 } 992 993 nodes[n].next = first_free_node; 994 first_free_node = n; 995 996 } 997 998 void erase(const UEdge& edge) { 999 int n = edge.id * 2; 1000 1001 if (edges[n].next_out != -1) { 1002 edges[edges[n].next_out].prev_out = edges[n].prev_out; 1003 } 1004 1005 if (edges[n].prev_out != -1) { 1006 edges[edges[n].prev_out].next_out = edges[n].next_out; 1007 } else { 1008 nodes[edges[n | 1].target].first_out = edges[n].next_out; 1009 } 1010 1011 if (edges[n | 1].next_out != -1) { 1012 edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out; 1013 } 1014 1015 if (edges[n | 1].prev_out != -1) { 1016 edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out; 1017 } else { 1018 nodes[edges[n].target].first_out = edges[n | 1].next_out; 1019 } 1020 1021 edges[n].next_out = first_free_edge; 1022 first_free_edge = n; 1023 1024 } 1025 1026 void clear() { 1027 edges.clear(); 1028 nodes.clear(); 1029 first_node = first_free_node = first_free_edge = -1; 1030 } 1031 1032 protected: 1033 1034 void changeTarget(UEdge e, Node n) { 1035 if(edges[2 * e.id].next_out != -1) { 1036 edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out; 1037 } 1038 if(edges[2 * e.id].prev_out != -1) { 1039 edges[edges[2 * e.id].prev_out].next_out = 1040 edges[2 * e.id].next_out; 1041 } else { 1042 nodes[edges[(2 * e.id) | 1].target].first_out = 1043 edges[2 * e.id].next_out; 1044 } 1045 1046 if (nodes[n.id].first_out != -1) { 1047 edges[nodes[n.id].first_out].prev_out = 2 * e.id; 1048 } 1049 edges[(2 * e.id) | 1].target = n.id; 1050 edges[2 * e.id].prev_out = -1; 1051 edges[2 * e.id].next_out = nodes[n.id].first_out; 1052 nodes[n.id].first_out = 2 * e.id; 1053 } 1054 1055 void changeSource(UEdge e, Node n) { 1056 if(edges[(2 * e.id) | 1].next_out != -1) { 1057 edges[edges[(2 * e.id) | 1].next_out].prev_out = 1058 edges[(2 * e.id) | 1].prev_out; 1059 } 1060 if(edges[(2 * e.id) | 1].prev_out != -1) { 1061 edges[edges[(2 * e.id) | 1].prev_out].next_out = 1062 edges[(2 * e.id) | 1].next_out; 1063 } else { 1064 nodes[edges[2 * e.id].target].first_out = 1065 edges[(2 * e.id) | 1].next_out; 1066 } 1067 1068 if (nodes[n.id].first_out != -1) { 1069 edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); 1070 } 1071 edges[2 * e.id].target = n.id; 1072 edges[(2 * e.id) | 1].prev_out = -1; 1073 edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out; 1074 nodes[n.id].first_out = ((2 * e.id) | 1); 1075 } 1076 1077 }; 1078 1079 // typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 1080 // ExtendedListUGraphBase; 1081 1082 typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase; 1083 1084 742 1085 743 1086 /// \addtogroup graphs … … 777 1120 778 1121 typedef ExtendedListUGraphBase Parent; 1122 1123 typedef Parent::OutEdgeIt IncEdgeIt; 1124 779 1125 /// \brief Add a new node to the graph. 780 1126 /// -
lemon/smart_graph.h
r2261 r2338 367 367 368 368 369 /**************** Undirected List Graph ****************/ 370 371 typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> > 372 ExtendedSmartUGraphBase; 369 class SmartUGraphBase { 370 371 protected: 372 373 struct NodeT { 374 int first_out; 375 }; 376 377 struct EdgeT { 378 int target; 379 int next_out; 380 }; 381 382 std::vector<NodeT> nodes; 383 std::vector<EdgeT> edges; 384 385 int first_free_edge; 386 387 public: 388 389 typedef SmartUGraphBase Graph; 390 391 class Node { 392 friend class SmartUGraphBase; 393 protected: 394 395 int id; 396 explicit Node(int pid) { id = pid;} 397 398 public: 399 Node() {} 400 Node (Invalid) { id = -1; } 401 bool operator==(const Node& node) const {return id == node.id;} 402 bool operator!=(const Node& node) const {return id != node.id;} 403 bool operator<(const Node& node) const {return id < node.id;} 404 }; 405 406 class UEdge { 407 friend class SmartUGraphBase; 408 protected: 409 410 int id; 411 explicit UEdge(int pid) { id = pid;} 412 413 public: 414 UEdge() {} 415 UEdge (Invalid) { id = -1; } 416 bool operator==(const UEdge& edge) const {return id == edge.id;} 417 bool operator!=(const UEdge& edge) const {return id != edge.id;} 418 bool operator<(const UEdge& edge) const {return id < edge.id;} 419 }; 420 421 class Edge { 422 friend class SmartUGraphBase; 423 protected: 424 425 int id; 426 explicit Edge(int pid) { id = pid;} 427 428 public: 429 operator UEdge() const { return UEdge(id / 2); } 430 431 Edge() {} 432 Edge (Invalid) { id = -1; } 433 bool operator==(const Edge& edge) const {return id == edge.id;} 434 bool operator!=(const Edge& edge) const {return id != edge.id;} 435 bool operator<(const Edge& edge) const {return id < edge.id;} 436 }; 437 438 439 440 SmartUGraphBase() 441 : nodes(), edges() {} 442 443 444 int maxNodeId() const { return nodes.size()-1; } 445 int maxUEdgeId() const { return edges.size() / 2 - 1; } 446 int maxEdgeId() const { return edges.size()-1; } 447 448 Node source(Edge e) const { return Node(edges[e.id ^ 1].target); } 449 Node target(Edge e) const { return Node(edges[e.id].target); } 450 451 Node source(UEdge e) const { return Node(edges[2 * e.id].target); } 452 Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); } 453 454 static bool direction(Edge e) { 455 return (e.id & 1) == 1; 456 } 457 458 static Edge direct(UEdge e, bool d) { 459 return Edge(e.id * 2 + (d ? 1 : 0)); 460 } 461 462 void first(Node& node) const { 463 node.id = nodes.size() - 1; 464 } 465 466 void next(Node& node) const { 467 --node.id; 468 } 469 470 void first(Edge& edge) const { 471 edge.id = edges.size() - 1; 472 } 473 474 void next(Edge& edge) const { 475 --edge.id; 476 } 477 478 void first(UEdge& edge) const { 479 edge.id = edges.size() / 2 - 1; 480 } 481 482 void next(UEdge& edge) const { 483 --edge.id; 484 } 485 486 void firstOut(Edge &edge, const Node& v) const { 487 edge.id = nodes[v.id].first_out; 488 } 489 void nextOut(Edge &edge) const { 490 edge.id = edges[edge.id].next_out; 491 } 492 493 void firstIn(Edge &edge, const Node& v) const { 494 edge.id = ((nodes[v.id].first_out) ^ 1); 495 if (e.id == -2) e.id = -1; 496 } 497 void nextIn(Edge &edge) const { 498 edge.id = ((edges[edge.id ^ 1].next_out) ^ 1); 499 if (e.id == -2) e.id = -1; 500 } 501 502 void firstInc(UEdge &edge, bool& d, const Node& v) const { 503 int de = nodes[v.id].first_out; 504 edge.id = de / 2; 505 d = ((de & 1) == 1); 506 } 507 void nextInc(UEdge &edge, bool& d) const { 508 int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out); 509 edge.id = de / 2; 510 d = ((de & 1) == 1); 511 } 512 513 static int id(Node v) { return v.id; } 514 static int id(Edge e) { return e.id; } 515 static int id(UEdge e) { return e.id; } 516 517 static Node nodeFromId(int id) { return Node(id);} 518 static Edge edgeFromId(int id) { return Edge(id);} 519 static UEdge uEdgeFromId(int id) { return UEdge(id);} 520 521 Node addNode() { 522 int n = nodes.size(); 523 nodes.push_back(NodeT()); 524 nodes[n].first_out = -1; 525 526 return Node(n); 527 } 528 529 UEdge addEdge(Node u, Node v) { 530 int n = edges.size(); 531 edges.push_back(EdgeT()); 532 edges.push_back(EdgeT()); 533 534 edges[n].target = u.id; 535 edges[n | 1].target = v.id; 536 537 edges[n].next_out = nodes[v.id].first_out; 538 edges[n | 1].next_out = nodes[u.id].first_out; 539 540 nodes[v.id].first_out = n; 541 nodes[u.id].first_out = (n | 1); 542 543 return UEdge(n / 2); 544 } 545 546 void clear() { 547 edges.clear(); 548 nodes.clear(); 549 } 550 551 }; 552 553 typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase; 373 554 374 555 /// \ingroup graphs … … 408 589 409 590 typedef ExtendedSmartUGraphBase Parent; 591 typedef Parent::OutEdgeIt IncEdgeIt; 410 592 411 593 /// Constructor … … 444 626 protected: 445 627 628 void saveSnapshot(Snapshot &s) 629 { 630 s.g = this; 631 s.node_num = nodes.size(); 632 s.edge_num = edges.size(); 633 } 446 634 447 635 void restoreSnapshot(const Snapshot &s) 448 636 { 449 637 while(s.edge_num<edges.size()) { 450 UEdge edge = uEdgeFromId(edges.size()-1); 638 int n=edges.size()-1; 639 UEdge edge=uEdgeFromId(n/2); 451 640 Parent::getNotifier(UEdge()).erase(edge); 452 641 std::vector<Edge> dir; 453 dir.push_back( Parent::direct(edge, true));454 dir.push_back( Parent::direct(edge, false));642 dir.push_back(edgeFromId(n)); 643 dir.push_back(edgeFromId(n-1)); 455 644 Parent::getNotifier(Edge()).erase(dir); 456 nodes[edges .back().source].first_out=edges.back().next_out;457 nodes[edges .back().target].first_in=edges.back().next_in;645 nodes[edges[n].target].first_out=edges[n].next_out; 646 nodes[edges[n-1].target].first_out=edges[n-1].next_out; 458 647 edges.pop_back(); 648 edges.pop_back(); 459 649 } 460 650 while(s.node_num<nodes.size()) { 461 Node node = nodeFromId(nodes.size()-1); 651 int n=nodes.size()-1; 652 Node node = nodeFromId(n); 462 653 Parent::getNotifier(Node()).erase(node); 463 654 nodes.pop_back(); … … 500 691 ///This constructor immediately makes a snapshot of the graph. 501 692 ///\param _g The graph we make a snapshot of. 502 Snapshot(SmartUGraph &_g) :g(&_g) { 503 node_num=g->nodes.size(); 504 edge_num=g->edges.size(); 693 Snapshot(SmartUGraph &g) { 694 g.saveSnapshot(*this); 505 695 } 506 696 … … 512 702 ///call, the previous snapshot gets lost. 513 703 ///\param _g The graph we make the snapshot of. 514 void save(SmartUGraph & _g)704 void save(SmartUGraph &g) 515 705 { 516 g=&_g; 517 node_num=g->nodes.size(); 518 edge_num=g->edges.size(); 706 g.saveSnapshot(*this); 519 707 } 520 708 … … 528 716 void restore() 529 717 { 530 718 g->restoreSnapshot(*this); 531 719 } 532 720 };
Note: See TracChangeset
for help on using the changeset viewer.