Changes in lemon/smart_graph.h [1092:dceba191c00d:1130:0759d974de81] in lemon-main
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/smart_graph.h
r1092 r1130 48 48 }; 49 49 50 std::vector<NodeT> nodes;51 std::vector<ArcT> arcs;50 std::vector<NodeT> _nodes; 51 std::vector<ArcT> _arcs; 52 52 53 53 public: … … 60 60 public: 61 61 62 SmartDigraphBase() : nodes(),arcs() { }62 SmartDigraphBase() : _nodes(), _arcs() { } 63 63 SmartDigraphBase(const SmartDigraphBase &_g) 64 : nodes(_g.nodes), arcs(_g.arcs) { }64 : _nodes(_g._nodes), _arcs(_g._arcs) { } 65 65 66 66 typedef True NodeNumTag; 67 67 typedef True ArcNumTag; 68 68 69 int nodeNum() const { return nodes.size(); }70 int arcNum() const { return arcs.size(); }71 72 int maxNodeId() const { return nodes.size()-1; }73 int maxArcId() const { return arcs.size()-1; }69 int nodeNum() const { return _nodes.size(); } 70 int arcNum() const { return _arcs.size(); } 71 72 int maxNodeId() const { return _nodes.size()-1; } 73 int maxArcId() const { return _arcs.size()-1; } 74 74 75 75 Node addNode() { 76 int n = nodes.size();77 nodes.push_back(NodeT());78 nodes[n].first_in = -1;79 nodes[n].first_out = -1;76 int n = _nodes.size(); 77 _nodes.push_back(NodeT()); 78 _nodes[n].first_in = -1; 79 _nodes[n].first_out = -1; 80 80 return Node(n); 81 81 } 82 82 83 83 Arc addArc(Node u, Node v) { 84 int n = arcs.size();85 arcs.push_back(ArcT());86 arcs[n].source = u._id;87 arcs[n].target = v._id;88 arcs[n].next_out =nodes[u._id].first_out;89 arcs[n].next_in =nodes[v._id].first_in;90 nodes[u._id].first_out =nodes[v._id].first_in = n;84 int n = _arcs.size(); 85 _arcs.push_back(ArcT()); 86 _arcs[n].source = u._id; 87 _arcs[n].target = v._id; 88 _arcs[n].next_out = _nodes[u._id].first_out; 89 _arcs[n].next_in = _nodes[v._id].first_in; 90 _nodes[u._id].first_out = _nodes[v._id].first_in = n; 91 91 92 92 return Arc(n); … … 94 94 95 95 void clear() { 96 arcs.clear();97 nodes.clear();98 } 99 100 Node source(Arc a) const { return Node( arcs[a._id].source); }101 Node target(Arc a) const { return Node( arcs[a._id].target); }96 _arcs.clear(); 97 _nodes.clear(); 98 } 99 100 Node source(Arc a) const { return Node(_arcs[a._id].source); } 101 Node target(Arc a) const { return Node(_arcs[a._id].target); } 102 102 103 103 static int id(Node v) { return v._id; } … … 108 108 109 109 bool valid(Node n) const { 110 return n._id >= 0 && n._id < static_cast<int>( nodes.size());110 return n._id >= 0 && n._id < static_cast<int>(_nodes.size()); 111 111 } 112 112 bool valid(Arc a) const { 113 return a._id >= 0 && a._id < static_cast<int>( arcs.size());113 return a._id >= 0 && a._id < static_cast<int>(_arcs.size()); 114 114 } 115 115 … … 146 146 147 147 void first(Node& node) const { 148 node._id = nodes.size() - 1;148 node._id = _nodes.size() - 1; 149 149 } 150 150 … … 154 154 155 155 void first(Arc& arc) const { 156 arc._id = arcs.size() - 1;156 arc._id = _arcs.size() - 1; 157 157 } 158 158 … … 162 162 163 163 void firstOut(Arc& arc, const Node& node) const { 164 arc._id = nodes[node._id].first_out;164 arc._id = _nodes[node._id].first_out; 165 165 } 166 166 167 167 void nextOut(Arc& arc) const { 168 arc._id = arcs[arc._id].next_out;168 arc._id = _arcs[arc._id].next_out; 169 169 } 170 170 171 171 void firstIn(Arc& arc, const Node& node) const { 172 arc._id = nodes[node._id].first_in;172 arc._id = _nodes[node._id].first_in; 173 173 } 174 174 175 175 void nextIn(Arc& arc) const { 176 arc._id = arcs[arc._id].next_in;176 arc._id = _arcs[arc._id].next_in; 177 177 } 178 178 … … 267 267 { 268 268 Node b = addNode(); 269 nodes[b._id].first_out=nodes[n._id].first_out;270 nodes[n._id].first_out=-1;271 for(int i= nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {272 arcs[i].source=b._id;269 _nodes[b._id].first_out=_nodes[n._id].first_out; 270 _nodes[n._id].first_out=-1; 271 for(int i=_nodes[b._id].first_out; i!=-1; i=_arcs[i].next_out) { 272 _arcs[i].source=b._id; 273 273 } 274 274 if(connect) addArc(n,b); … … 292 292 /// to build the digraph. 293 293 /// \sa reserveArc() 294 void reserveNode(int n) { nodes.reserve(n); };294 void reserveNode(int n) { _nodes.reserve(n); }; 295 295 296 296 /// Reserve memory for arcs. … … 302 302 /// to build the digraph. 303 303 /// \sa reserveNode() 304 void reserveArc(int m) { arcs.reserve(m); };304 void reserveArc(int m) { _arcs.reserve(m); }; 305 305 306 306 public: … … 312 312 void restoreSnapshot(const Snapshot &s) 313 313 { 314 while(s.arc_num< arcs.size()) {315 Arc arc = arcFromId( arcs.size()-1);314 while(s.arc_num<_arcs.size()) { 315 Arc arc = arcFromId(_arcs.size()-1); 316 316 Parent::notifier(Arc()).erase(arc); 317 nodes[arcs.back().source].first_out=arcs.back().next_out;318 nodes[arcs.back().target].first_in=arcs.back().next_in;319 arcs.pop_back();320 } 321 while(s.node_num< nodes.size()) {322 Node node = nodeFromId( nodes.size()-1);317 _nodes[_arcs.back().source].first_out=_arcs.back().next_out; 318 _nodes[_arcs.back().target].first_in=_arcs.back().next_in; 319 _arcs.pop_back(); 320 } 321 while(s.node_num<_nodes.size()) { 322 Node node = nodeFromId(_nodes.size()-1); 323 323 Parent::notifier(Node()).erase(node); 324 nodes.pop_back();324 _nodes.pop_back(); 325 325 } 326 326 } … … 363 363 /// 364 364 Snapshot(SmartDigraph &gr) : _graph(&gr) { 365 node_num=_graph-> nodes.size();366 arc_num=_graph-> arcs.size();365 node_num=_graph->_nodes.size(); 366 arc_num=_graph->_arcs.size(); 367 367 } 368 368 … … 374 374 void save(SmartDigraph &gr) { 375 375 _graph=&gr; 376 node_num=_graph-> nodes.size();377 arc_num=_graph-> arcs.size();376 node_num=_graph->_nodes.size(); 377 arc_num=_graph->_arcs.size(); 378 378 } 379 379 … … 403 403 }; 404 404 405 std::vector<NodeT> nodes;406 std::vector<ArcT> arcs;405 std::vector<NodeT> _nodes; 406 std::vector<ArcT> _arcs; 407 407 408 408 public: … … 466 466 467 467 SmartGraphBase() 468 : nodes(),arcs() {}468 : _nodes(), _arcs() {} 469 469 470 470 typedef True NodeNumTag; … … 472 472 typedef True ArcNumTag; 473 473 474 int nodeNum() const { return nodes.size(); }475 int edgeNum() const { return arcs.size() / 2; }476 int arcNum() const { return arcs.size(); }477 478 int maxNodeId() const { return nodes.size()-1; }479 int maxEdgeId() const { return arcs.size() / 2 - 1; }480 int maxArcId() const { return arcs.size()-1; }481 482 Node source(Arc e) const { return Node( arcs[e._id ^ 1].target); }483 Node target(Arc e) const { return Node( arcs[e._id].target); }484 485 Node u(Edge e) const { return Node( arcs[2 * e._id].target); }486 Node v(Edge e) const { return Node( arcs[2 * e._id + 1].target); }474 int nodeNum() const { return _nodes.size(); } 475 int edgeNum() const { return _arcs.size() / 2; } 476 int arcNum() const { return _arcs.size(); } 477 478 int maxNodeId() const { return _nodes.size()-1; } 479 int maxEdgeId() const { return _arcs.size() / 2 - 1; } 480 int maxArcId() const { return _arcs.size()-1; } 481 482 Node source(Arc e) const { return Node(_arcs[e._id ^ 1].target); } 483 Node target(Arc e) const { return Node(_arcs[e._id].target); } 484 485 Node u(Edge e) const { return Node(_arcs[2 * e._id].target); } 486 Node v(Edge e) const { return Node(_arcs[2 * e._id + 1].target); } 487 487 488 488 static bool direction(Arc e) { … … 495 495 496 496 void first(Node& node) const { 497 node._id = nodes.size() - 1;497 node._id = _nodes.size() - 1; 498 498 } 499 499 … … 503 503 504 504 void first(Arc& arc) const { 505 arc._id = arcs.size() - 1;505 arc._id = _arcs.size() - 1; 506 506 } 507 507 … … 511 511 512 512 void first(Edge& arc) const { 513 arc._id = arcs.size() / 2 - 1;513 arc._id = _arcs.size() / 2 - 1; 514 514 } 515 515 … … 519 519 520 520 void firstOut(Arc &arc, const Node& v) const { 521 arc._id = nodes[v._id].first_out;521 arc._id = _nodes[v._id].first_out; 522 522 } 523 523 void nextOut(Arc &arc) const { 524 arc._id = arcs[arc._id].next_out;524 arc._id = _arcs[arc._id].next_out; 525 525 } 526 526 527 527 void firstIn(Arc &arc, const Node& v) const { 528 arc._id = (( nodes[v._id].first_out) ^ 1);528 arc._id = ((_nodes[v._id].first_out) ^ 1); 529 529 if (arc._id == -2) arc._id = -1; 530 530 } 531 531 void nextIn(Arc &arc) const { 532 arc._id = (( arcs[arc._id ^ 1].next_out) ^ 1);532 arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1); 533 533 if (arc._id == -2) arc._id = -1; 534 534 } 535 535 536 536 void firstInc(Edge &arc, bool& d, const Node& v) const { 537 int de = nodes[v._id].first_out;537 int de = _nodes[v._id].first_out; 538 538 if (de != -1) { 539 539 arc._id = de / 2; … … 545 545 } 546 546 void nextInc(Edge &arc, bool& d) const { 547 int de = ( arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);547 int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); 548 548 if (de != -1) { 549 549 arc._id = de / 2; … … 564 564 565 565 bool valid(Node n) const { 566 return n._id >= 0 && n._id < static_cast<int>( nodes.size());566 return n._id >= 0 && n._id < static_cast<int>(_nodes.size()); 567 567 } 568 568 bool valid(Arc a) const { 569 return a._id >= 0 && a._id < static_cast<int>( arcs.size());569 return a._id >= 0 && a._id < static_cast<int>(_arcs.size()); 570 570 } 571 571 bool valid(Edge e) const { 572 return e._id >= 0 && 2 * e._id < static_cast<int>( arcs.size());572 return e._id >= 0 && 2 * e._id < static_cast<int>(_arcs.size()); 573 573 } 574 574 575 575 Node addNode() { 576 int n = nodes.size();577 nodes.push_back(NodeT());578 nodes[n].first_out = -1;576 int n = _nodes.size(); 577 _nodes.push_back(NodeT()); 578 _nodes[n].first_out = -1; 579 579 580 580 return Node(n); … … 582 582 583 583 Edge addEdge(Node u, Node v) { 584 int n = arcs.size();585 arcs.push_back(ArcT());586 arcs.push_back(ArcT());587 588 arcs[n].target = u._id;589 arcs[n | 1].target = v._id;590 591 arcs[n].next_out =nodes[v._id].first_out;592 nodes[v._id].first_out = n;593 594 arcs[n | 1].next_out =nodes[u._id].first_out;595 nodes[u._id].first_out = (n | 1);584 int n = _arcs.size(); 585 _arcs.push_back(ArcT()); 586 _arcs.push_back(ArcT()); 587 588 _arcs[n].target = u._id; 589 _arcs[n | 1].target = v._id; 590 591 _arcs[n].next_out = _nodes[v._id].first_out; 592 _nodes[v._id].first_out = n; 593 594 _arcs[n | 1].next_out = _nodes[u._id].first_out; 595 _nodes[u._id].first_out = (n | 1); 596 596 597 597 return Edge(n / 2); … … 599 599 600 600 void clear() { 601 arcs.clear();602 nodes.clear();601 _arcs.clear(); 602 _nodes.clear(); 603 603 } 604 604 … … 702 702 /// to build the graph. 703 703 /// \sa reserveEdge() 704 void reserveNode(int n) { nodes.reserve(n); };704 void reserveNode(int n) { _nodes.reserve(n); }; 705 705 706 706 /// Reserve memory for edges. … … 712 712 /// to build the graph. 713 713 /// \sa reserveNode() 714 void reserveEdge(int m) { arcs.reserve(2 * m); };714 void reserveEdge(int m) { _arcs.reserve(2 * m); }; 715 715 716 716 public: … … 723 723 { 724 724 s._graph = this; 725 s.node_num = nodes.size();726 s.arc_num = arcs.size();725 s.node_num = _nodes.size(); 726 s.arc_num = _arcs.size(); 727 727 } 728 728 729 729 void restoreSnapshot(const Snapshot &s) 730 730 { 731 while(s.arc_num< arcs.size()) {732 int n= arcs.size()-1;731 while(s.arc_num<_arcs.size()) { 732 int n=_arcs.size()-1; 733 733 Edge arc=edgeFromId(n/2); 734 734 Parent::notifier(Edge()).erase(arc); … … 737 737 dir.push_back(arcFromId(n-1)); 738 738 Parent::notifier(Arc()).erase(dir); 739 nodes[arcs[n-1].target].first_out=arcs[n].next_out;740 nodes[arcs[n].target].first_out=arcs[n-1].next_out;741 arcs.pop_back();742 arcs.pop_back();743 } 744 while(s.node_num< nodes.size()) {745 int n= nodes.size()-1;739 _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out; 740 _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out; 741 _arcs.pop_back(); 742 _arcs.pop_back(); 743 } 744 while(s.node_num<_nodes.size()) { 745 int n=_nodes.size()-1; 746 746 Node node = nodeFromId(n); 747 747 Parent::notifier(Node()).erase(node); 748 nodes.pop_back();748 _nodes.pop_back(); 749 749 } 750 750 } … … 826 826 }; 827 827 828 std::vector<NodeT> nodes;829 std::vector<ArcT> arcs;828 std::vector<NodeT> _nodes; 829 std::vector<ArcT> _arcs; 830 830 831 831 int first_red, first_blue; … … 916 916 917 917 SmartBpGraphBase() 918 : nodes(),arcs(), first_red(-1), first_blue(-1),918 : _nodes(), _arcs(), first_red(-1), first_blue(-1), 919 919 max_red(-1), max_blue(-1) {} 920 920 … … 923 923 typedef True ArcNumTag; 924 924 925 int nodeNum() const { return nodes.size(); }925 int nodeNum() const { return _nodes.size(); } 926 926 int redNum() const { return max_red + 1; } 927 927 int blueNum() const { return max_blue + 1; } 928 int edgeNum() const { return arcs.size() / 2; }929 int arcNum() const { return arcs.size(); }930 931 int maxNodeId() const { return nodes.size()-1; }928 int edgeNum() const { return _arcs.size() / 2; } 929 int arcNum() const { return _arcs.size(); } 930 931 int maxNodeId() const { return _nodes.size()-1; } 932 932 int maxRedId() const { return max_red; } 933 933 int maxBlueId() const { return max_blue; } 934 int maxEdgeId() const { return arcs.size() / 2 - 1; }935 int maxArcId() const { return arcs.size()-1; }936 937 bool red(Node n) const { return nodes[n._id].red; }938 bool blue(Node n) const { return ! nodes[n._id].red; }934 int maxEdgeId() const { return _arcs.size() / 2 - 1; } 935 int maxArcId() const { return _arcs.size()-1; } 936 937 bool red(Node n) const { return _nodes[n._id].red; } 938 bool blue(Node n) const { return !_nodes[n._id].red; } 939 939 940 940 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); } 941 941 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); } 942 942 943 Node source(Arc a) const { return Node( arcs[a._id ^ 1].target); }944 Node target(Arc a) const { return Node( arcs[a._id].target); }943 Node source(Arc a) const { return Node(_arcs[a._id ^ 1].target); } 944 Node target(Arc a) const { return Node(_arcs[a._id].target); } 945 945 946 946 RedNode redNode(Edge e) const { 947 return RedNode( arcs[2 * e._id].target);947 return RedNode(_arcs[2 * e._id].target); 948 948 } 949 949 BlueNode blueNode(Edge e) const { 950 return BlueNode( arcs[2 * e._id + 1].target);950 return BlueNode(_arcs[2 * e._id + 1].target); 951 951 } 952 952 … … 960 960 961 961 void first(Node& node) const { 962 node._id = nodes.size() - 1;962 node._id = _nodes.size() - 1; 963 963 } 964 964 … … 972 972 973 973 void next(RedNode& node) const { 974 node._id = nodes[node._id].partition_next;974 node._id = _nodes[node._id].partition_next; 975 975 } 976 976 … … 980 980 981 981 void next(BlueNode& node) const { 982 node._id = nodes[node._id].partition_next;982 node._id = _nodes[node._id].partition_next; 983 983 } 984 984 985 985 void first(Arc& arc) const { 986 arc._id = arcs.size() - 1;986 arc._id = _arcs.size() - 1; 987 987 } 988 988 … … 992 992 993 993 void first(Edge& arc) const { 994 arc._id = arcs.size() / 2 - 1;994 arc._id = _arcs.size() / 2 - 1; 995 995 } 996 996 … … 1000 1000 1001 1001 void firstOut(Arc &arc, const Node& v) const { 1002 arc._id = nodes[v._id].first_out;1002 arc._id = _nodes[v._id].first_out; 1003 1003 } 1004 1004 void nextOut(Arc &arc) const { 1005 arc._id = arcs[arc._id].next_out;1005 arc._id = _arcs[arc._id].next_out; 1006 1006 } 1007 1007 1008 1008 void firstIn(Arc &arc, const Node& v) const { 1009 arc._id = (( nodes[v._id].first_out) ^ 1);1009 arc._id = ((_nodes[v._id].first_out) ^ 1); 1010 1010 if (arc._id == -2) arc._id = -1; 1011 1011 } 1012 1012 void nextIn(Arc &arc) const { 1013 arc._id = (( arcs[arc._id ^ 1].next_out) ^ 1);1013 arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1); 1014 1014 if (arc._id == -2) arc._id = -1; 1015 1015 } 1016 1016 1017 1017 void firstInc(Edge &arc, bool& d, const Node& v) const { 1018 int de = nodes[v._id].first_out;1018 int de = _nodes[v._id].first_out; 1019 1019 if (de != -1) { 1020 1020 arc._id = de / 2; … … 1026 1026 } 1027 1027 void nextInc(Edge &arc, bool& d) const { 1028 int de = ( arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);1028 int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); 1029 1029 if (de != -1) { 1030 1030 arc._id = de / 2; … … 1037 1037 1038 1038 static int id(Node v) { return v._id; } 1039 int id(RedNode v) const { return nodes[v._id].partition_index; }1040 int id(BlueNode v) const { return nodes[v._id].partition_index; }1039 int id(RedNode v) const { return _nodes[v._id].partition_index; } 1040 int id(BlueNode v) const { return _nodes[v._id].partition_index; } 1041 1041 static int id(Arc e) { return e._id; } 1042 1042 static int id(Edge e) { return e._id; } … … 1047 1047 1048 1048 bool valid(Node n) const { 1049 return n._id >= 0 && n._id < static_cast<int>( nodes.size());1049 return n._id >= 0 && n._id < static_cast<int>(_nodes.size()); 1050 1050 } 1051 1051 bool valid(Arc a) const { 1052 return a._id >= 0 && a._id < static_cast<int>( arcs.size());1052 return a._id >= 0 && a._id < static_cast<int>(_arcs.size()); 1053 1053 } 1054 1054 bool valid(Edge e) const { 1055 return e._id >= 0 && 2 * e._id < static_cast<int>( arcs.size());1055 return e._id >= 0 && 2 * e._id < static_cast<int>(_arcs.size()); 1056 1056 } 1057 1057 1058 1058 RedNode addRedNode() { 1059 int n = nodes.size();1060 nodes.push_back(NodeT());1061 nodes[n].first_out = -1;1062 nodes[n].red = true;1063 nodes[n].partition_index = ++max_red;1064 nodes[n].partition_next = first_red;1059 int n = _nodes.size(); 1060 _nodes.push_back(NodeT()); 1061 _nodes[n].first_out = -1; 1062 _nodes[n].red = true; 1063 _nodes[n].partition_index = ++max_red; 1064 _nodes[n].partition_next = first_red; 1065 1065 first_red = n; 1066 1066 … … 1069 1069 1070 1070 BlueNode addBlueNode() { 1071 int n = nodes.size();1072 nodes.push_back(NodeT());1073 nodes[n].first_out = -1;1074 nodes[n].red = false;1075 nodes[n].partition_index = ++max_blue;1076 nodes[n].partition_next = first_blue;1071 int n = _nodes.size(); 1072 _nodes.push_back(NodeT()); 1073 _nodes[n].first_out = -1; 1074 _nodes[n].red = false; 1075 _nodes[n].partition_index = ++max_blue; 1076 _nodes[n].partition_next = first_blue; 1077 1077 first_blue = n; 1078 1078 … … 1081 1081 1082 1082 Edge addEdge(RedNode u, BlueNode v) { 1083 int n = arcs.size();1084 arcs.push_back(ArcT());1085 arcs.push_back(ArcT());1086 1087 arcs[n].target = u._id;1088 arcs[n | 1].target = v._id;1089 1090 arcs[n].next_out =nodes[v._id].first_out;1091 nodes[v._id].first_out = n;1092 1093 arcs[n | 1].next_out =nodes[u._id].first_out;1094 nodes[u._id].first_out = (n | 1);1083 int n = _arcs.size(); 1084 _arcs.push_back(ArcT()); 1085 _arcs.push_back(ArcT()); 1086 1087 _arcs[n].target = u._id; 1088 _arcs[n | 1].target = v._id; 1089 1090 _arcs[n].next_out = _nodes[v._id].first_out; 1091 _nodes[v._id].first_out = n; 1092 1093 _arcs[n | 1].next_out = _nodes[u._id].first_out; 1094 _nodes[u._id].first_out = (n | 1); 1095 1095 1096 1096 return Edge(n / 2); … … 1098 1098 1099 1099 void clear() { 1100 arcs.clear();1101 nodes.clear();1100 _arcs.clear(); 1101 _nodes.clear(); 1102 1102 first_red = -1; 1103 1103 first_blue = -1; … … 1214 1214 /// to build the graph. 1215 1215 /// \sa reserveEdge() 1216 void reserveNode(int n) { nodes.reserve(n); };1216 void reserveNode(int n) { _nodes.reserve(n); }; 1217 1217 1218 1218 /// Reserve memory for edges. … … 1224 1224 /// to build the graph. 1225 1225 /// \sa reserveNode() 1226 void reserveEdge(int m) { arcs.reserve(2 * m); };1226 void reserveEdge(int m) { _arcs.reserve(2 * m); }; 1227 1227 1228 1228 public: … … 1235 1235 { 1236 1236 s._graph = this; 1237 s.node_num = nodes.size();1238 s.arc_num = arcs.size();1237 s.node_num = _nodes.size(); 1238 s.arc_num = _arcs.size(); 1239 1239 } 1240 1240 1241 1241 void restoreSnapshot(const Snapshot &s) 1242 1242 { 1243 while(s.arc_num< arcs.size()) {1244 int n= arcs.size()-1;1243 while(s.arc_num<_arcs.size()) { 1244 int n=_arcs.size()-1; 1245 1245 Edge arc=edgeFromId(n/2); 1246 1246 Parent::notifier(Edge()).erase(arc); … … 1249 1249 dir.push_back(arcFromId(n-1)); 1250 1250 Parent::notifier(Arc()).erase(dir); 1251 nodes[arcs[n-1].target].first_out=arcs[n].next_out;1252 nodes[arcs[n].target].first_out=arcs[n-1].next_out;1253 arcs.pop_back();1254 arcs.pop_back();1255 } 1256 while(s.node_num< nodes.size()) {1257 int n= nodes.size()-1;1251 _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out; 1252 _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out; 1253 _arcs.pop_back(); 1254 _arcs.pop_back(); 1255 } 1256 while(s.node_num<_nodes.size()) { 1257 int n=_nodes.size()-1; 1258 1258 Node node = nodeFromId(n); 1259 1259 if (Parent::red(node)) { 1260 first_red = nodes[n].partition_next;1260 first_red = _nodes[n].partition_next; 1261 1261 if (first_red != -1) { 1262 max_red = nodes[first_red].partition_index;1262 max_red = _nodes[first_red].partition_index; 1263 1263 } else { 1264 1264 max_red = -1; … … 1266 1266 Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node)); 1267 1267 } else { 1268 first_blue = nodes[n].partition_next;1268 first_blue = _nodes[n].partition_next; 1269 1269 if (first_blue != -1) { 1270 max_blue = nodes[first_blue].partition_index;1270 max_blue = _nodes[first_blue].partition_index; 1271 1271 } else { 1272 1272 max_blue = -1; … … 1275 1275 } 1276 1276 Parent::notifier(Node()).erase(node); 1277 nodes.pop_back();1277 _nodes.pop_back(); 1278 1278 } 1279 1279 }
Note: See TracChangeset
for help on using the changeset viewer.