Changeset 209:765619b7cbb2 in lemon1.2 for lemon/list_graph.h
 Timestamp:
 07/13/08 20:51:02 (16 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/list_graph.h
r184 r209 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 38 38 int prev, next; 39 39 }; 40 40 41 41 struct ArcT { 42 42 int target, source; … … 54 54 55 55 int first_free_arc; 56 56 57 57 public: 58 58 59 59 typedef ListDigraphBase Digraph; 60 60 61 61 class Node { 62 62 friend class ListDigraphBase; … … 93 93 ListDigraphBase() 94 94 : nodes(), first_node(1), 95 96 97 98 int maxNodeId() const { return nodes.size()1; } 95 first_free_node(1), arcs(), first_free_arc(1) {} 96 97 98 int maxNodeId() const { return nodes.size()1; } 99 99 int maxArcId() const { return arcs.size()1; } 100 100 … … 103 103 104 104 105 void first(Node& node) const { 105 void first(Node& node) const { 106 106 node.id = first_node; 107 107 } … … 112 112 113 113 114 void first(Arc& arc) const { 114 void first(Arc& arc) const { 115 115 int n; 116 for(n = first_node; 117 n!=1 && nodes[n].first_in == 1; 118 116 for(n = first_node; 117 n!=1 && nodes[n].first_in == 1; 118 n = nodes[n].next) {} 119 119 arc.id = (n == 1) ? 1 : nodes[n].first_in; 120 120 } … … 122 122 void next(Arc& arc) const { 123 123 if (arcs[arc.id].next_in != 1) { 124 125 } else { 126 127 128 n!=1 && nodes[n].first_in == 1; 129 130 131 } 124 arc.id = arcs[arc.id].next_in; 125 } else { 126 int n; 127 for(n = nodes[arcs[arc.id].target].next; 128 n!=1 && nodes[n].first_in == 1; 129 n = nodes[n].next) {} 130 arc.id = (n == 1) ? 1 : nodes[n].first_in; 131 } 132 132 } 133 133 … … 146 146 } 147 147 148 148 149 149 static int id(Node v) { return v.id; } 150 150 static int id(Arc e) { return e.id; } … … 153 153 static Arc arcFromId(int id) { return Arc(id);} 154 154 155 bool valid(Node n) const { 156 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 157 158 } 159 160 bool valid(Arc a) const { 161 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 162 163 } 164 165 Node addNode() { 155 bool valid(Node n) const { 156 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 157 nodes[n.id].prev != 2; 158 } 159 160 bool valid(Arc a) const { 161 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 162 arcs[a.id].prev_in != 2; 163 } 164 165 Node addNode() { 166 166 int n; 167 167 168 168 if(first_free_node==1) { 169 170 171 } else { 172 173 174 } 175 169 n = nodes.size(); 170 nodes.push_back(NodeT()); 171 } else { 172 n = first_free_node; 173 first_free_node = nodes[n].next; 174 } 175 176 176 nodes[n].next = first_node; 177 177 if(first_node != 1) nodes[first_node].prev = n; 178 178 first_node = n; 179 179 nodes[n].prev = 1; 180 180 181 181 nodes[n].first_in = nodes[n].first_out = 1; 182 182 183 183 return Node(n); 184 184 } 185 185 186 186 Arc addArc(Node u, Node v) { 187 int n; 187 int n; 188 188 189 189 if (first_free_arc == 1) { 190 191 192 } else { 193 194 195 } 196 197 arcs[n].source = u.id; 190 n = arcs.size(); 191 arcs.push_back(ArcT()); 192 } else { 193 n = first_free_arc; 194 first_free_arc = arcs[n].next_in; 195 } 196 197 arcs[n].source = u.id; 198 198 arcs[n].target = v.id; 199 199 200 200 arcs[n].next_out = nodes[u.id].first_out; 201 201 if(nodes[u.id].first_out != 1) { 202 203 } 204 202 arcs[nodes[u.id].first_out].prev_out = n; 203 } 204 205 205 arcs[n].next_in = nodes[v.id].first_in; 206 206 if(nodes[v.id].first_in != 1) { 207 208 } 209 207 arcs[nodes[v.id].first_in].prev_in = n; 208 } 209 210 210 arcs[n].prev_in = arcs[n].prev_out = 1; 211 211 212 212 nodes[u.id].first_out = nodes[v.id].first_in = n; 213 213 214 214 return Arc(n); 215 215 } 216 216 217 217 void erase(const Node& node) { 218 218 int n = node.id; 219 219 220 220 if(nodes[n].next != 1) { 221 222 } 223 221 nodes[nodes[n].next].prev = nodes[n].prev; 222 } 223 224 224 if(nodes[n].prev != 1) { 225 226 } else { 227 228 } 229 225 nodes[nodes[n].prev].next = nodes[n].next; 226 } else { 227 first_node = nodes[n].next; 228 } 229 230 230 nodes[n].next = first_free_node; 231 231 first_free_node = n; … … 233 233 234 234 } 235 235 236 236 void erase(const Arc& arc) { 237 237 int n = arc.id; 238 238 239 239 if(arcs[n].next_in!=1) { 240 240 arcs[arcs[n].next_in].prev_in = arcs[n].prev_in; 241 241 } 242 242 243 243 if(arcs[n].prev_in!=1) { 244 245 } else { 246 247 } 248 249 244 arcs[arcs[n].prev_in].next_in = arcs[n].next_in; 245 } else { 246 nodes[arcs[n].target].first_in = arcs[n].next_in; 247 } 248 249 250 250 if(arcs[n].next_out!=1) { 251 252 } 251 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; 252 } 253 253 254 254 if(arcs[n].prev_out!=1) { 255 256 } else { 257 258 } 259 255 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; 256 } else { 257 nodes[arcs[n].source].first_out = arcs[n].next_out; 258 } 259 260 260 arcs[n].next_in = first_free_arc; 261 261 first_free_arc = n; … … 270 270 271 271 protected: 272 void changeTarget(Arc e, Node n) 272 void changeTarget(Arc e, Node n) 273 273 { 274 274 if(arcs[e.id].next_in != 1) 275 275 arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in; 276 276 if(arcs[e.id].prev_in != 1) 277 277 arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in; 278 278 else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in; 279 279 if (nodes[n.id].first_in != 1) { 280 280 arcs[nodes[n.id].first_in].prev_in = e.id; 281 281 } 282 282 arcs[e.id].target = n.id; … … 285 285 nodes[n.id].first_in = e.id; 286 286 } 287 void changeSource(Arc e, Node n) 287 void changeSource(Arc e, Node n) 288 288 { 289 289 if(arcs[e.id].next_out != 1) 290 290 arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out; 291 291 if(arcs[e.id].prev_out != 1) 292 292 arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out; 293 293 else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out; 294 294 if (nodes[n.id].first_out != 1) { 295 295 arcs[nodes[n.id].first_out].prev_out = e.id; 296 296 } 297 297 arcs[e.id].source = n.id; … … 308 308 /// @{ 309 309 310 ///A general directed graph structure. 311 312 ///\ref ListDigraph is a simple and fast <em>directed graph</em> 313 ///implementation based on static linked lists that are stored in 314 ///\c std::vector structures. 310 ///A general directed graph structure. 311 312 ///\ref ListDigraph is a simple and fast <em>directed graph</em> 313 ///implementation based on static linked lists that are stored in 314 ///\c std::vector structures. 315 315 /// 316 316 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it … … 327 327 private: 328 328 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 329 329 330 330 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 331 331 /// … … 342 342 343 343 /// Constructor 344 344 345 345 /// Constructor. 346 346 /// … … 348 348 349 349 ///Add a new node to the digraph. 350 350 351 351 ///Add a new node to the digraph. 352 352 ///\return the new node. … … 354 354 355 355 ///Add a new arc to the digraph. 356 356 357 357 ///Add a new arc to the digraph with source node \c s 358 358 ///and target node \c t. 359 359 ///\return the new arc. 360 Arc addArc(const Node& s, const Node& t) { 361 return Parent::addArc(s, t); 360 Arc addArc(const Node& s, const Node& t) { 361 return Parent::addArc(s, t); 362 362 } 363 363 … … 365 365 366 366 /// This function gives back true if the given node is valid, 367 /// ie. it is a real node of the graph. 367 /// ie. it is a real node of the graph. 368 368 /// 369 369 /// \warning A Node pointing to a removed item … … 375 375 376 376 /// This function gives back true if the given arc is valid, 377 /// ie. it is a real arc of the graph. 377 /// ie. it is a real arc of the graph. 378 378 /// 379 379 /// \warning An Arc pointing to a removed item … … 392 392 ///\warning This functionality cannot be used together with the Snapshot 393 393 ///feature. 394 void changeTarget(Arc e, Node n) { 395 Parent::changeTarget(e,n); 394 void changeTarget(Arc e, Node n) { 395 Parent::changeTarget(e,n); 396 396 } 397 397 /// Change the source of \c e to \c n … … 405 405 ///\warning This functionality cannot be used together with the Snapshot 406 406 ///feature. 407 void changeSource(Arc e, Node n) { 407 void changeSource(Arc e, Node n) { 408 408 Parent::changeSource(e,n); 409 409 } … … 457 457 ///\warning This functionality cannot be used together with the Snapshot 458 458 ///feature. 459 void contract(Node a, Node b, bool r = true) 459 void contract(Node a, Node b, bool r = true) 460 460 { 461 461 for(OutArcIt e(*this,b);e!=INVALID;) { 462 463 464 465 466 462 OutArcIt f=e; 463 ++f; 464 if(r && target(e)==a) erase(e); 465 else changeSource(e,a); 466 e=f; 467 467 } 468 468 for(InArcIt e(*this,b);e!=INVALID;) { 469 470 471 472 473 469 InArcIt f=e; 470 ++f; 471 if(r && source(e)==a) erase(e); 472 else changeTarget(e,a); 473 e=f; 474 474 } 475 475 erase(b); … … 486 486 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 487 487 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may 488 ///be invalidated. 488 ///be invalidated. 489 489 /// 490 490 ///\warning This functionality cannot be used together with the … … 495 495 Node b = addNode(); 496 496 for(OutArcIt e(*this,n);e!=INVALID;) { 497 498 499 500 497 OutArcIt f=e; 498 ++f; 499 changeSource(e,b); 500 e=f; 501 501 } 502 502 if (connect) addArc(n,b); 503 503 return b; 504 504 } 505 505 506 506 ///Split an arc. 507 507 … … 520 520 return b; 521 521 } 522 522 523 523 /// \brief Class to make a snapshot of the digraph and restore 524 524 /// it later. … … 530 530 /// 531 531 /// \warning Arc and node deletions and other modifications (e.g. 532 /// contracting, splitting, reversing arcs or nodes) cannot be 533 /// restored. These events invalidate the snapshot. 532 /// contracting, splitting, reversing arcs or nodes) cannot be 533 /// restored. These events invalidate the snapshot. 534 534 class Snapshot { 535 535 protected: … … 546 546 using NodeNotifier::ObserverBase::detach; 547 547 using NodeNotifier::ObserverBase::attached; 548 548 549 549 protected: 550 550 551 551 virtual void add(const Node& node) { 552 552 snapshot.addNode(node); … … 568 568 Node node; 569 569 std::vector<Node> nodes; 570 for (notifier()>first(node); node != INVALID; 570 for (notifier()>first(node); node != INVALID; 571 571 notifier()>next(node)) { 572 572 nodes.push_back(node); … … 578 578 virtual void clear() { 579 579 Node node; 580 for (notifier()>first(node); node != INVALID; 580 for (notifier()>first(node); node != INVALID; 581 581 notifier()>next(node)) { 582 582 snapshot.eraseNode(node); … … 596 596 using ArcNotifier::ObserverBase::detach; 597 597 using ArcNotifier::ObserverBase::attached; 598 598 599 599 protected: 600 600 … … 618 618 Arc arc; 619 619 std::vector<Arc> arcs; 620 for (notifier()>first(arc); arc != INVALID; 620 for (notifier()>first(arc); arc != INVALID; 621 621 notifier()>next(arc)) { 622 622 arcs.push_back(arc); … … 628 628 virtual void clear() { 629 629 Arc arc; 630 for (notifier()>first(arc); arc != INVALID; 630 for (notifier()>first(arc); arc != INVALID; 631 631 notifier()>next(arc)) { 632 632 snapshot.eraseArc(arc); … … 636 636 Snapshot& snapshot; 637 637 }; 638 638 639 639 ListDigraph *digraph; 640 640 … … 647 647 648 648 void addNode(const Node& node) { 649 added_nodes.push_front(node); 649 added_nodes.push_front(node); 650 650 } 651 651 void eraseNode(const Node& node) { 652 std::list<Node>::iterator it = 652 std::list<Node>::iterator it = 653 653 std::find(added_nodes.begin(), added_nodes.end(), node); 654 654 if (it == added_nodes.end()) { … … 662 662 663 663 void addArc(const Arc& arc) { 664 added_arcs.push_front(arc); 664 added_arcs.push_front(arc); 665 665 } 666 666 void eraseArc(const Arc& arc) { 667 std::list<Arc>::iterator it = 667 std::list<Arc>::iterator it = 668 668 std::find(added_arcs.begin(), added_arcs.end(), arc); 669 669 if (it == added_arcs.end()) { 670 670 clear(); 671 node_observer_proxy.detach(); 671 node_observer_proxy.detach(); 672 672 throw ArcNotifier::ImmediateDetach(); 673 673 } else { 674 674 added_arcs.erase(it); 675 } 675 } 676 676 } 677 677 678 678 void attach(ListDigraph &_digraph) { 679 680 679 digraph = &_digraph; 680 node_observer_proxy.attach(digraph>notifier(Node())); 681 681 arc_observer_proxy.attach(digraph>notifier(Arc())); 682 682 } 683 683 684 684 void detach() { 685 686 685 node_observer_proxy.detach(); 686 arc_observer_proxy.detach(); 687 687 } 688 688 … … 693 693 void clear() { 694 694 added_nodes.clear(); 695 added_arcs.clear(); 695 added_arcs.clear(); 696 696 } 697 697 … … 702 702 /// Default constructor. 703 703 /// To actually make a snapshot you must call save(). 704 Snapshot() 705 : digraph(0), node_observer_proxy(*this), 704 Snapshot() 705 : digraph(0), node_observer_proxy(*this), 706 706 arc_observer_proxy(*this) {} 707 707 708 708 /// \brief Constructor that immediately makes a snapshot. 709 /// 709 /// 710 710 /// This constructor immediately makes a snapshot of the digraph. 711 711 /// \param _digraph The digraph we make a snapshot of. 712 Snapshot(ListDigraph &_digraph) 713 : node_observer_proxy(*this), 712 Snapshot(ListDigraph &_digraph) 713 : node_observer_proxy(*this), 714 714 arc_observer_proxy(*this) { 715 716 } 717 715 attach(_digraph); 716 } 717 718 718 /// \brief Make a snapshot. 719 719 /// … … 730 730 attach(_digraph); 731 731 } 732 732 733 733 /// \brief Undo the changes until the last snapshot. 734 // 734 // 735 735 /// Undo the changes until the last snapshot created by save(). 736 736 void restore() { 737 738 for(std::list<Arc>::iterator it = added_arcs.begin(); 737 detach(); 738 for(std::list<Arc>::iterator it = added_arcs.begin(); 739 739 it != added_arcs.end(); ++it) { 740 741 742 for(std::list<Node>::iterator it = added_nodes.begin(); 740 digraph>erase(*it); 741 } 742 for(std::list<Node>::iterator it = added_nodes.begin(); 743 743 it != added_nodes.end(); ++it) { 744 745 744 digraph>erase(*it); 745 } 746 746 clear(); 747 747 } … … 754 754 } 755 755 }; 756 756 757 757 }; 758 758 … … 767 767 int prev, next; 768 768 }; 769 769 770 770 struct ArcT { 771 771 int target; … … 782 782 783 783 int first_free_arc; 784 784 785 785 public: 786 786 787 787 typedef ListGraphBase Digraph; 788 788 … … 790 790 class Arc; 791 791 class Edge; 792 792 793 793 class Node { 794 794 friend class ListGraphBase; … … 842 842 ListGraphBase() 843 843 : nodes(), first_node(1), 844 845 846 847 int maxNodeId() const { return nodes.size()1; } 844 first_free_node(1), arcs(), first_free_arc(1) {} 845 846 847 int maxNodeId() const { return nodes.size()1; } 848 848 int maxEdgeId() const { return arcs.size() / 2  1; } 849 849 int maxArcId() const { return arcs.size()1; } … … 863 863 } 864 864 865 void first(Node& node) const { 865 void first(Node& node) const { 866 866 node.id = first_node; 867 867 } … … 871 871 } 872 872 873 void first(Arc& e) const { 873 void first(Arc& e) const { 874 874 int n = first_node; 875 875 while (n != 1 && nodes[n].first_out == 1) { … … 881 881 void next(Arc& e) const { 882 882 if (arcs[e.id].next_out != 1) { 883 884 } else { 885 883 e.id = arcs[e.id].next_out; 884 } else { 885 int n = nodes[arcs[e.id ^ 1].target].next; 886 886 while(n != 1 && nodes[n].first_out == 1) { 887 887 n = nodes[n].next; 888 888 } 889 890 } 891 } 892 893 void first(Edge& e) const { 889 e.id = (n == 1) ? 1 : nodes[n].first_out; 890 } 891 } 892 893 void first(Edge& e) const { 894 894 int n = first_node; 895 895 while (n != 1) { … … 901 901 e.id /= 2; 902 902 return; 903 } 903 } 904 904 n = nodes[n].next; 905 905 } … … 916 916 e.id /= 2; 917 917 return; 918 } 918 } 919 919 n = nodes[n].next; 920 920 while (n != 1) { … … 926 926 e.id /= 2; 927 927 return; 928 } 928 } 929 929 n = nodes[n].next; 930 930 } … … 968 968 } 969 969 } 970 970 971 971 static int id(Node v) { return v.id; } 972 972 static int id(Arc e) { return e.id; } … … 977 977 static Edge edgeFromId(int id) { return Edge(id);} 978 978 979 bool valid(Node n) const { 980 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 981 982 } 983 984 bool valid(Arc a) const { 985 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 986 987 } 988 989 bool valid(Edge e) const { 990 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && 991 992 } 993 994 Node addNode() { 979 bool valid(Node n) const { 980 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 981 nodes[n.id].prev != 2; 982 } 983 984 bool valid(Arc a) const { 985 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 986 arcs[a.id].prev_out != 2; 987 } 988 989 bool valid(Edge e) const { 990 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && 991 arcs[2 * e.id].prev_out != 2; 992 } 993 994 Node addNode() { 995 995 int n; 996 996 997 997 if(first_free_node==1) { 998 999 1000 } else { 1001 1002 1003 } 1004 998 n = nodes.size(); 999 nodes.push_back(NodeT()); 1000 } else { 1001 n = first_free_node; 1002 first_free_node = nodes[n].next; 1003 } 1004 1005 1005 nodes[n].next = first_node; 1006 1006 if (first_node != 1) nodes[first_node].prev = n; 1007 1007 first_node = n; 1008 1008 nodes[n].prev = 1; 1009 1009 1010 1010 nodes[n].first_out = 1; 1011 1011 1012 1012 return Node(n); 1013 1013 } 1014 1014 1015 1015 Edge addEdge(Node u, Node v) { 1016 int n; 1016 int n; 1017 1017 1018 1018 if (first_free_arc == 1) { 1019 1020 1021 1022 } else { 1023 1024 1025 } 1026 1019 n = arcs.size(); 1020 arcs.push_back(ArcT()); 1021 arcs.push_back(ArcT()); 1022 } else { 1023 n = first_free_arc; 1024 first_free_arc = arcs[n].next_out; 1025 } 1026 1027 1027 arcs[n].target = u.id; 1028 1028 arcs[n  1].target = v.id; … … 1030 1030 arcs[n].next_out = nodes[v.id].first_out; 1031 1031 if (nodes[v.id].first_out != 1) { 1032 1033 } 1032 arcs[nodes[v.id].first_out].prev_out = n; 1033 } 1034 1034 arcs[n].prev_out = 1; 1035 1035 nodes[v.id].first_out = n; 1036 1036 1037 1037 arcs[n  1].next_out = nodes[u.id].first_out; 1038 1038 if (nodes[u.id].first_out != 1) { 1039 1040 } 1041 arcs[n  1].prev_out = 1; 1039 arcs[nodes[u.id].first_out].prev_out = (n  1); 1040 } 1041 arcs[n  1].prev_out = 1; 1042 1042 nodes[u.id].first_out = (n  1); 1043 1043 1044 1044 return Edge(n / 2); 1045 1045 } 1046 1046 1047 1047 void erase(const Node& node) { 1048 1048 int n = node.id; 1049 1049 1050 1050 if(nodes[n].next != 1) { 1051 1052 } 1053 1051 nodes[nodes[n].next].prev = nodes[n].prev; 1052 } 1053 1054 1054 if(nodes[n].prev != 1) { 1055 1056 } else { 1057 1058 } 1059 1055 nodes[nodes[n].prev].next = nodes[n].next; 1056 } else { 1057 first_node = nodes[n].next; 1058 } 1059 1060 1060 nodes[n].next = first_free_node; 1061 1061 first_free_node = n; 1062 1062 nodes[n].prev = 2; 1063 1063 } 1064 1064 1065 1065 void erase(const Edge& edge) { 1066 1066 int n = edge.id * 2; 1067 1067 1068 1068 if (arcs[n].next_out != 1) { 1069 1070 } 1069 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; 1070 } 1071 1071 1072 1072 if (arcs[n].prev_out != 1) { 1073 1074 } else { 1075 1073 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; 1074 } else { 1075 nodes[arcs[n  1].target].first_out = arcs[n].next_out; 1076 1076 } 1077 1077 1078 1078 if (arcs[n  1].next_out != 1) { 1079 1080 } 1079 arcs[arcs[n  1].next_out].prev_out = arcs[n  1].prev_out; 1080 } 1081 1081 1082 1082 if (arcs[n  1].prev_out != 1) { 1083 1084 } else { 1085 1086 } 1087 1083 arcs[arcs[n  1].prev_out].next_out = arcs[n  1].next_out; 1084 } else { 1085 nodes[arcs[n].target].first_out = arcs[n  1].next_out; 1086 } 1087 1088 1088 arcs[n].next_out = first_free_arc; 1089 first_free_arc = n; 1089 first_free_arc = n; 1090 1090 arcs[n].prev_out = 2; 1091 1091 arcs[n  1].prev_out = 2; … … 1103 1103 void changeTarget(Edge e, Node n) { 1104 1104 if(arcs[2 * e.id].next_out != 1) { 1105 1105 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; 1106 1106 } 1107 1107 if(arcs[2 * e.id].prev_out != 1) { 1108 arcs[arcs[2 * e.id].prev_out].next_out = 1108 arcs[arcs[2 * e.id].prev_out].next_out = 1109 1109 arcs[2 * e.id].next_out; 1110 1110 } else { 1111 nodes[arcs[(2 * e.id)  1].target].first_out = 1111 nodes[arcs[(2 * e.id)  1].target].first_out = 1112 1112 arcs[2 * e.id].next_out; 1113 1113 } 1114 1114 1115 1115 if (nodes[n.id].first_out != 1) { 1116 1116 arcs[nodes[n.id].first_out].prev_out = 2 * e.id; 1117 1117 } 1118 1118 arcs[(2 * e.id)  1].target = n.id; … … 1124 1124 void changeSource(Edge e, Node n) { 1125 1125 if(arcs[(2 * e.id)  1].next_out != 1) { 1126 arcs[arcs[(2 * e.id)  1].next_out].prev_out = 1126 arcs[arcs[(2 * e.id)  1].next_out].prev_out = 1127 1127 arcs[(2 * e.id)  1].prev_out; 1128 1128 } 1129 1129 if(arcs[(2 * e.id)  1].prev_out != 1) { 1130 arcs[arcs[(2 * e.id)  1].prev_out].next_out = 1130 arcs[arcs[(2 * e.id)  1].prev_out].next_out = 1131 1131 arcs[(2 * e.id)  1].next_out; 1132 1132 } else { 1133 nodes[arcs[2 * e.id].target].first_out = 1133 nodes[arcs[2 * e.id].target].first_out = 1134 1134 arcs[(2 * e.id)  1].next_out; 1135 1135 } 1136 1136 1137 1137 if (nodes[n.id].first_out != 1) { 1138 1138 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id)  1); 1139 1139 } 1140 1140 arcs[2 * e.id].target = n.id; … … 1154 1154 ///A general undirected graph structure. 1155 1155 1156 ///\ref ListGraph is a simple and fast <em>undirected graph</em> 1157 ///implementation based on static linked lists that are stored in 1158 ///\c std::vector structures. 1156 ///\ref ListGraph is a simple and fast <em>undirected graph</em> 1157 ///implementation based on static linked lists that are stored in 1158 ///\c std::vector structures. 1159 1159 /// 1160 1160 ///It conforms to the \ref concepts::Graph "Graph concept" and it … … 1183 1183 public: 1184 1184 /// Constructor 1185 1185 1186 1186 /// Constructor. 1187 1187 /// … … 1203 1203 /// and target node \c t. 1204 1204 /// \return the new edge. 1205 Edge addEdge(const Node& s, const Node& t) { 1206 return Parent::addEdge(s, t); 1205 Edge addEdge(const Node& s, const Node& t) { 1206 return Parent::addEdge(s, t); 1207 1207 } 1208 1208 /// Node validity check 1209 1209 1210 1210 /// This function gives back true if the given node is valid, 1211 /// ie. it is a real node of the graph. 1211 /// ie. it is a real node of the graph. 1212 1212 /// 1213 1213 /// \warning A Node pointing to a removed item … … 1218 1218 1219 1219 /// This function gives back true if the given arc is valid, 1220 /// ie. it is a real arc of the graph. 1220 /// ie. it is a real arc of the graph. 1221 1221 /// 1222 1222 /// \warning An Arc pointing to a removed item … … 1227 1227 1228 1228 /// This function gives back true if the given edge is valid, 1229 /// ie. it is a real arc of the graph. 1229 /// ie. it is a real arc of the graph. 1230 1230 /// 1231 1231 /// \warning A Edge pointing to a removed item … … 1243 1243 ///\warning This functionality cannot be used together with the 1244 1244 ///Snapshot feature. 1245 void changeSource(Edge e, Node n) { 1246 Parent::changeSource(e,n); 1247 } 1245 void changeSource(Edge e, Node n) { 1246 Parent::changeSource(e,n); 1247 } 1248 1248 /// \brief Change the target of \c e to \c n 1249 1249 /// … … 1255 1255 ///\warning This functionality cannot be used together with the 1256 1256 ///Snapshot feature. 1257 void changeTarget(Edge e, Node n) { 1258 Parent::changeTarget(e,n); 1257 void changeTarget(Edge e, Node n) { 1258 Parent::changeTarget(e,n); 1259 1259 } 1260 1260 /// \brief Change the source of \c e to \c n 1261 1261 /// 1262 /// This function changes the source of \c e to \c n. 1262 /// This function changes the source of \c e to \c n. 1263 1263 /// It also changes the proper node of the represented edge. 1264 1264 /// … … 1269 1269 ///\warning This functionality cannot be used together with the 1270 1270 ///Snapshot feature. 1271 void changeSource(Arc e, Node n) { 1271 void changeSource(Arc e, Node n) { 1272 1272 if (Parent::direction(e)) { 1273 1273 Parent::changeSource(e,n); 1274 1274 } else { 1275 1275 Parent::changeTarget(e,n); 1276 } 1276 } 1277 1277 } 1278 1278 /// \brief Change the target of \c e to \c n 1279 1279 /// 1280 /// This function changes the target of \c e to \c n. 1280 /// This function changes the target of \c e to \c n. 1281 1281 /// It also changes the proper node of the represented edge. 1282 1282 /// … … 1287 1287 ///\warning This functionality cannot be used together with the 1288 1288 ///Snapshot feature. 1289 void changeTarget(Arc e, Node n) { 1289 void changeTarget(Arc e, Node n) { 1290 1290 if (Parent::direction(e)) { 1291 1291 Parent::changeTarget(e,n); 1292 1292 } else { 1293 1293 Parent::changeSource(e,n); 1294 } 1294 } 1295 1295 } 1296 1296 /// \brief Contract two nodes. … … 1309 1309 void contract(Node a, Node b, bool r = true) { 1310 1310 for(IncEdgeIt e(*this, b); e!=INVALID;) { 1311 1312 1313 1314 1315 1316 1317 1318 1319 1311 IncEdgeIt f = e; ++f; 1312 if (r && runningNode(e) == a) { 1313 erase(e); 1314 } else if (source(e) == b) { 1315 changeSource(e, a); 1316 } else { 1317 changeTarget(e, a); 1318 } 1319 e = f; 1320 1320 } 1321 1321 erase(b); … … 1332 1332 /// 1333 1333 /// \warning Edge and node deletions and other modifications 1334 /// (e.g. changing nodes of edges, contracting nodes) cannot be 1334 /// (e.g. changing nodes of edges, contracting nodes) cannot be 1335 1335 /// restored. These events invalidate the snapshot. 1336 1336 class Snapshot { … … 1348 1348 using NodeNotifier::ObserverBase::detach; 1349 1349 using NodeNotifier::ObserverBase::attached; 1350 1350 1351 1351 protected: 1352 1352 1353 1353 virtual void add(const Node& node) { 1354 1354 snapshot.addNode(node); … … 1370 1370 Node node; 1371 1371 std::vector<Node> nodes; 1372 for (notifier()>first(node); node != INVALID; 1372 for (notifier()>first(node); node != INVALID; 1373 1373 notifier()>next(node)) { 1374 1374 nodes.push_back(node); … … 1380 1380 virtual void clear() { 1381 1381 Node node; 1382 for (notifier()>first(node); node != INVALID; 1382 for (notifier()>first(node); node != INVALID; 1383 1383 notifier()>next(node)) { 1384 1384 snapshot.eraseNode(node); … … 1398 1398 using EdgeNotifier::ObserverBase::detach; 1399 1399 using EdgeNotifier::ObserverBase::attached; 1400 1400 1401 1401 protected: 1402 1402 … … 1420 1420 Edge edge; 1421 1421 std::vector<Edge> edges; 1422 for (notifier()>first(edge); edge != INVALID; 1422 for (notifier()>first(edge); edge != INVALID; 1423 1423 notifier()>next(edge)) { 1424 1424 edges.push_back(edge); … … 1430 1430 virtual void clear() { 1431 1431 Edge edge; 1432 for (notifier()>first(edge); edge != INVALID; 1432 for (notifier()>first(edge); edge != INVALID; 1433 1433 notifier()>next(edge)) { 1434 1434 snapshot.eraseEdge(edge); … … 1449 1449 1450 1450 void addNode(const Node& node) { 1451 added_nodes.push_front(node); 1451 added_nodes.push_front(node); 1452 1452 } 1453 1453 void eraseNode(const Node& node) { 1454 std::list<Node>::iterator it = 1454 std::list<Node>::iterator it = 1455 1455 std::find(added_nodes.begin(), added_nodes.end(), node); 1456 1456 if (it == added_nodes.end()) { … … 1464 1464 1465 1465 void addEdge(const Edge& edge) { 1466 added_edges.push_front(edge); 1466 added_edges.push_front(edge); 1467 1467 } 1468 1468 void eraseEdge(const Edge& edge) { 1469 std::list<Edge>::iterator it = 1469 std::list<Edge>::iterator it = 1470 1470 std::find(added_edges.begin(), added_edges.end(), edge); 1471 1471 if (it == added_edges.end()) { … … 1479 1479 1480 1480 void attach(ListGraph &_graph) { 1481 1482 1481 graph = &_graph; 1482 node_observer_proxy.attach(graph>notifier(Node())); 1483 1483 edge_observer_proxy.attach(graph>notifier(Edge())); 1484 1484 } 1485 1485 1486 1486 void detach() { 1487 1488 1487 node_observer_proxy.detach(); 1488 edge_observer_proxy.detach(); 1489 1489 } 1490 1490 … … 1495 1495 void clear() { 1496 1496 added_nodes.clear(); 1497 added_edges.clear(); 1497 added_edges.clear(); 1498 1498 } 1499 1499 … … 1504 1504 /// Default constructor. 1505 1505 /// To actually make a snapshot you must call save(). 1506 Snapshot() 1507 : graph(0), node_observer_proxy(*this), 1506 Snapshot() 1507 : graph(0), node_observer_proxy(*this), 1508 1508 edge_observer_proxy(*this) {} 1509 1509 1510 1510 /// \brief Constructor that immediately makes a snapshot. 1511 /// 1511 /// 1512 1512 /// This constructor immediately makes a snapshot of the graph. 1513 1513 /// \param _graph The graph we make a snapshot of. 1514 Snapshot(ListGraph &_graph) 1515 : node_observer_proxy(*this), 1514 Snapshot(ListGraph &_graph) 1515 : node_observer_proxy(*this), 1516 1516 edge_observer_proxy(*this) { 1517 1518 } 1519 1517 attach(_graph); 1518 } 1519 1520 1520 /// \brief Make a snapshot. 1521 1521 /// … … 1532 1532 attach(_graph); 1533 1533 } 1534 1534 1535 1535 /// \brief Undo the changes until the last snapshot. 1536 // 1536 // 1537 1537 /// Undo the changes until the last snapshot created by save(). 1538 1538 void restore() { 1539 1540 for(std::list<Edge>::iterator it = added_edges.begin(); 1539 detach(); 1540 for(std::list<Edge>::iterator it = added_edges.begin(); 1541 1541 it != added_edges.end(); ++it) { 1542 1543 1544 for(std::list<Node>::iterator it = added_nodes.begin(); 1542 graph>erase(*it); 1543 } 1544 for(std::list<Node>::iterator it = added_nodes.begin(); 1545 1545 it != added_nodes.end(); ++it) { 1546 1547 1546 graph>erase(*it); 1547 } 1548 1548 clear(); 1549 1549 } … … 1557 1557 }; 1558 1558 }; 1559 1560 /// @} 1559 1560 /// @} 1561 1561 } //namespace lemon 1562 1562 1563 1563 1564 1564 #endif
Note: See TracChangeset
for help on using the changeset viewer.