Changeset 57:c1acf0018c0a in lemon-main for lemon/list_graph.h
- Timestamp:
- 01/20/08 20:43:48 (17 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_graph.h
r39 r57 17 17 */ 18 18 19 #ifndef LEMON_LIST_GRAPH_H 20 #define LEMON_LIST_GRAPH_H 21 22 ///\ingroup graphs 23 ///\file 24 ///\brief ListDigraph, ListGraph classes. 25 26 #include <lemon/bits/graph_extender.h> 27 28 #include <vector> 29 #include <list> 30 31 namespace lemon { 32 33 class ListDigraphBase { 34 35 protected: 36 struct NodeT { 37 int first_in, first_out; 38 int prev, next; 39 }; 40 41 struct ArcT { 42 int target, source; 43 int prev_in, prev_out; 44 int next_in, next_out; 45 }; 46 47 std::vector<NodeT> nodes; 48 49 int first_node; 50 51 int first_free_node; 52 53 std::vector<ArcT> arcs; 54 55 int first_free_arc; 56 57 public: 58 59 typedef ListDigraphBase Digraph; 60 61 class Node { 62 friend class ListDigraphBase; 63 protected: 64 65 int id; 66 explicit Node(int pid) { id = pid;} 67 68 public: 69 Node() {} 70 Node (Invalid) { id = -1; } 71 bool operator==(const Node& node) const {return id == node.id;} 72 bool operator!=(const Node& node) const {return id != node.id;} 73 bool operator<(const Node& node) const {return id < node.id;} 74 }; 75 76 class Arc { 77 friend class ListDigraphBase; 78 protected: 79 80 int id; 81 explicit Arc(int pid) { id = pid;} 82 83 public: 84 Arc() {} 85 Arc (Invalid) { id = -1; } 86 bool operator==(const Arc& arc) const {return id == arc.id;} 87 bool operator!=(const Arc& arc) const {return id != arc.id;} 88 bool operator<(const Arc& arc) const {return id < arc.id;} 89 }; 90 91 92 93 ListDigraphBase() 94 : nodes(), first_node(-1), 95 first_free_node(-1), arcs(), first_free_arc(-1) {} 96 97 98 int maxNodeId() const { return nodes.size()-1; } 99 int maxArcId() const { return arcs.size()-1; } 100 101 Node source(Arc e) const { return Node(arcs[e.id].source); } 102 Node target(Arc e) const { return Node(arcs[e.id].target); } 103 104 105 void first(Node& node) const { 106 node.id = first_node; 107 } 108 109 void next(Node& node) const { 110 node.id = nodes[node.id].next; 111 } 112 113 114 void first(Arc& e) const { 115 int n; 116 for(n = first_node; 117 n!=-1 && nodes[n].first_in == -1; 118 n = nodes[n].next); 119 e.id = (n == -1) ? -1 : nodes[n].first_in; 120 } 121 122 void next(Arc& arc) const { 123 if (arcs[arc.id].next_in != -1) { 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 } 133 134 void firstOut(Arc &e, const Node& v) const { 135 e.id = nodes[v.id].first_out; 136 } 137 void nextOut(Arc &e) const { 138 e.id=arcs[e.id].next_out; 139 } 140 141 void firstIn(Arc &e, const Node& v) const { 142 e.id = nodes[v.id].first_in; 143 } 144 void nextIn(Arc &e) const { 145 e.id=arcs[e.id].next_in; 146 } 147 148 149 static int id(Node v) { return v.id; } 150 static int id(Arc e) { return e.id; } 151 152 static Node nodeFromId(int id) { return Node(id);} 153 static Arc arcFromId(int id) { return Arc(id);} 154 155 Node addNode() { 156 int n; 157 158 if(first_free_node==-1) { 159 n = nodes.size(); 160 nodes.push_back(NodeT()); 161 } else { 162 n = first_free_node; 163 first_free_node = nodes[n].next; 164 } 165 166 nodes[n].next = first_node; 167 if(first_node != -1) nodes[first_node].prev = n; 168 first_node = n; 169 nodes[n].prev = -1; 170 171 nodes[n].first_in = nodes[n].first_out = -1; 172 173 return Node(n); 174 } 175 176 Arc addArc(Node u, Node v) { 177 int n; 178 179 if (first_free_arc == -1) { 180 n = arcs.size(); 181 arcs.push_back(ArcT()); 182 } else { 183 n = first_free_arc; 184 first_free_arc = arcs[n].next_in; 185 } 186 187 arcs[n].source = u.id; 188 arcs[n].target = v.id; 189 190 arcs[n].next_out = nodes[u.id].first_out; 191 if(nodes[u.id].first_out != -1) { 192 arcs[nodes[u.id].first_out].prev_out = n; 193 } 194 195 arcs[n].next_in = nodes[v.id].first_in; 196 if(nodes[v.id].first_in != -1) { 197 arcs[nodes[v.id].first_in].prev_in = n; 198 } 199 200 arcs[n].prev_in = arcs[n].prev_out = -1; 201 202 nodes[u.id].first_out = nodes[v.id].first_in = n; 203 204 return Arc(n); 205 } 206 207 void erase(const Node& node) { 208 int n = node.id; 209 210 if(nodes[n].next != -1) { 211 nodes[nodes[n].next].prev = nodes[n].prev; 212 } 213 214 if(nodes[n].prev != -1) { 215 nodes[nodes[n].prev].next = nodes[n].next; 216 } else { 217 first_node = nodes[n].next; 218 } 219 220 nodes[n].next = first_free_node; 221 first_free_node = n; 222 223 } 224 225 void erase(const Arc& arc) { 226 int n = arc.id; 227 228 if(arcs[n].next_in!=-1) { 229 arcs[arcs[n].next_in].prev_in = arcs[n].prev_in; 230 } 231 232 if(arcs[n].prev_in!=-1) { 233 arcs[arcs[n].prev_in].next_in = arcs[n].next_in; 234 } else { 235 nodes[arcs[n].target].first_in = arcs[n].next_in; 236 } 237 238 239 if(arcs[n].next_out!=-1) { 240 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; 241 } 242 243 if(arcs[n].prev_out!=-1) { 244 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; 245 } else { 246 nodes[arcs[n].source].first_out = arcs[n].next_out; 247 } 248 249 arcs[n].next_in = first_free_arc; 250 first_free_arc = n; 251 252 } 253 254 void clear() { 255 arcs.clear(); 256 nodes.clear(); 257 first_node = first_free_node = first_free_arc = -1; 258 } 259 260 protected: 261 void changeTarget(Arc e, Node n) 262 { 263 if(arcs[e.id].next_in != -1) 264 arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in; 265 if(arcs[e.id].prev_in != -1) 266 arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in; 267 else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in; 268 if (nodes[n.id].first_in != -1) { 269 arcs[nodes[n.id].first_in].prev_in = e.id; 270 } 271 arcs[e.id].target = n.id; 272 arcs[e.id].prev_in = -1; 273 arcs[e.id].next_in = nodes[n.id].first_in; 274 nodes[n.id].first_in = e.id; 275 } 276 void changeSource(Arc e, Node n) 277 { 278 if(arcs[e.id].next_out != -1) 279 arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out; 280 if(arcs[e.id].prev_out != -1) 281 arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out; 282 else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out; 283 if (nodes[n.id].first_out != -1) { 284 arcs[nodes[n.id].first_out].prev_out = e.id; 285 } 286 arcs[e.id].source = n.id; 287 arcs[e.id].prev_out = -1; 288 arcs[e.id].next_out = nodes[n.id].first_out; 289 nodes[n.id].first_out = e.id; 290 } 291 292 }; 293 294 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase; 295 296 /// \addtogroup digraphs 297 /// @{ 298 299 ///A list digraph class. 300 301 ///This is a simple and fast digraph implementation. 302 /// 303 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it 304 ///also provides several additional useful extra functionalities. 305 ///The most of the member functions and nested classes are 306 ///documented only in the concept class. 307 /// 308 ///An important extra feature of this digraph implementation is that 309 ///its maps are real \ref concepts::ReferenceMap "reference map"s. 310 /// 311 ///\sa concepts::Digraph. 312 313 class ListDigraph : public ExtendedListDigraphBase { 314 private: 315 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. 316 317 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. 318 /// 319 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; 320 ///\brief Assignment of ListDigraph to another one is \e not allowed. 321 ///Use DigraphCopy() instead. 322 323 ///Assignment of ListDigraph to another one is \e not allowed. 324 ///Use DigraphCopy() instead. 325 void operator=(const ListDigraph &) {} 326 public: 327 328 typedef ExtendedListDigraphBase Parent; 329 330 /// Constructor 331 332 /// Constructor. 333 /// 334 ListDigraph() {} 335 336 ///Add a new node to the digraph. 337 338 /// \return the new node. 339 /// 340 Node addNode() { return Parent::addNode(); } 341 342 ///Add a new arc to the digraph. 343 344 ///Add a new arc to the digraph with source node \c s 345 ///and target node \c t. 346 ///\return the new arc. 347 Arc addArc(const Node& s, const Node& t) { 348 return Parent::addArc(s, t); 349 } 350 351 /// Changes the target of \c e to \c n 352 353 /// Changes the target of \c e to \c n 354 /// 355 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing 356 ///the changed arc remain valid. However <tt>InArcIt</tt>s are 357 ///invalidated. 358 ///\warning This functionality cannot be used together with the Snapshot 359 ///feature. 360 void changeTarget(Arc e, Node n) { 361 Parent::changeTarget(e,n); 362 } 363 /// Changes the source of \c e to \c n 364 365 /// Changes the source of \c e to \c n 366 /// 367 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing 368 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are 369 ///invalidated. 370 ///\warning This functionality cannot be used together with the Snapshot 371 ///feature. 372 void changeSource(Arc e, Node n) { 373 Parent::changeSource(e,n); 374 } 375 376 /// Invert the direction of an arc. 377 378 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain 379 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are 380 ///invalidated. 381 ///\warning This functionality cannot be used together with the Snapshot 382 ///feature. 383 void reverseArc(Arc e) { 384 Node t=target(e); 385 changeTarget(e,source(e)); 386 changeSource(e,t); 387 } 388 389 /// Using this it is possible to avoid the superfluous memory 390 /// allocation: if you know that the digraph you want to build will 391 /// be very large (e.g. it will contain millions of nodes and/or arcs) 392 /// then it is worth reserving space for this amount before starting 393 /// to build the digraph. 394 /// \sa reserveArc 395 void reserveNode(int n) { nodes.reserve(n); }; 396 397 /// \brief Using this it is possible to avoid the superfluous memory 398 /// allocation. 399 400 /// Using this it is possible to avoid the superfluous memory 401 /// allocation: if you know that the digraph you want to build will 402 /// be very large (e.g. it will contain millions of nodes and/or arcs) 403 /// then it is worth reserving space for this amount before starting 404 /// to build the digraph. 405 /// \sa reserveNode 406 void reserveArc(int m) { arcs.reserve(m); }; 407 408 ///Contract two nodes. 409 410 ///This function contracts two nodes. 411 /// 412 ///Node \p b will be removed but instead of deleting 413 ///incident arcs, they will be joined to \p a. 414 ///The last parameter \p r controls whether to remove loops. \c true 415 ///means that loops will be removed. 416 /// 417 ///\note The <tt>ArcIt</tt>s 418 ///referencing a moved arc remain 419 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s 420 ///may be invalidated. 421 ///\warning This functionality cannot be used together with the Snapshot 422 ///feature. 423 void contract(Node a, Node b, bool r = true) 424 { 425 for(OutArcIt e(*this,b);e!=INVALID;) { 426 OutArcIt f=e; 427 ++f; 428 if(r && target(e)==a) erase(e); 429 else changeSource(e,a); 430 e=f; 431 } 432 for(InArcIt e(*this,b);e!=INVALID;) { 433 InArcIt f=e; 434 ++f; 435 if(r && source(e)==a) erase(e); 436 else changeTarget(e,a); 437 e=f; 438 } 439 erase(b); 440 } 441 442 ///Split a node. 443 444 ///This function splits a node. First a new node is added to the digraph, 445 ///then the source of each outgoing arc of \c n is moved to this new node. 446 ///If \c connect is \c true (this is the default value), then a new arc 447 ///from \c n to the newly created node is also added. 448 ///\return The newly created node. 449 /// 450 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 451 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may 452 ///be invalidated. 453 /// 454 ///\warning This functionality cannot be used together with the 455 ///Snapshot feature. \todo It could be implemented in a bit 456 ///faster way. 457 Node split(Node n, bool connect = true) { 458 Node b = addNode(); 459 for(OutArcIt e(*this,n);e!=INVALID;) { 460 OutArcIt f=e; 461 ++f; 462 changeSource(e,b); 463 e=f; 464 } 465 if (connect) addArc(n,b); 466 return b; 467 } 468 469 ///Split an arc. 470 471 ///This function splits an arc. First a new node \c b is added to 472 ///the digraph, then the original arc is re-targeted to \c 473 ///b. Finally an arc from \c b to the original target is added. 474 ///\return The newly created node. 475 ///\warning This functionality 476 ///cannot be used together with the Snapshot feature. 477 Node split(Arc e) { 478 Node b = addNode(); 479 addArc(b,target(e)); 480 changeTarget(e,b); 481 return b; 482 } 483 484 /// \brief Class to make a snapshot of the digraph and restore 485 /// to it later. 486 /// 487 /// Class to make a snapshot of the digraph and to restore it 488 /// later. 489 /// 490 /// The newly added nodes and arcs can be removed using the 491 /// restore() function. 492 /// 493 /// \warning Arc and node deletions cannot be restored. This 494 /// events invalidate the snapshot. 495 class Snapshot { 496 protected: 497 498 typedef Parent::NodeNotifier NodeNotifier; 499 500 class NodeObserverProxy : public NodeNotifier::ObserverBase { 501 public: 502 503 NodeObserverProxy(Snapshot& _snapshot) 504 : snapshot(_snapshot) {} 505 506 using NodeNotifier::ObserverBase::attach; 507 using NodeNotifier::ObserverBase::detach; 508 using NodeNotifier::ObserverBase::attached; 509 510 protected: 511 512 virtual void add(const Node& node) { 513 snapshot.addNode(node); 514 } 515 virtual void add(const std::vector<Node>& nodes) { 516 for (int i = nodes.size() - 1; i >= 0; ++i) { 517 snapshot.addNode(nodes[i]); 518 } 519 } 520 virtual void erase(const Node& node) { 521 snapshot.eraseNode(node); 522 } 523 virtual void erase(const std::vector<Node>& nodes) { 524 for (int i = 0; i < int(nodes.size()); ++i) { 525 snapshot.eraseNode(nodes[i]); 526 } 527 } 528 virtual void build() { 529 Node node; 530 std::vector<Node> nodes; 531 for (notifier()->first(node); node != INVALID; 532 notifier()->next(node)) { 533 nodes.push_back(node); 534 } 535 for (int i = nodes.size() - 1; i >= 0; --i) { 536 snapshot.addNode(nodes[i]); 537 } 538 } 539 virtual void clear() { 540 Node node; 541 for (notifier()->first(node); node != INVALID; 542 notifier()->next(node)) { 543 snapshot.eraseNode(node); 544 } 545 } 546 547 Snapshot& snapshot; 548 }; 549 550 class ArcObserverProxy : public ArcNotifier::ObserverBase { 551 public: 552 553 ArcObserverProxy(Snapshot& _snapshot) 554 : snapshot(_snapshot) {} 555 556 using ArcNotifier::ObserverBase::attach; 557 using ArcNotifier::ObserverBase::detach; 558 using ArcNotifier::ObserverBase::attached; 559 560 protected: 561 562 virtual void add(const Arc& arc) { 563 snapshot.addArc(arc); 564 } 565 virtual void add(const std::vector<Arc>& arcs) { 566 for (int i = arcs.size() - 1; i >= 0; ++i) { 567 snapshot.addArc(arcs[i]); 568 } 569 } 570 virtual void erase(const Arc& arc) { 571 snapshot.eraseArc(arc); 572 } 573 virtual void erase(const std::vector<Arc>& arcs) { 574 for (int i = 0; i < int(arcs.size()); ++i) { 575 snapshot.eraseArc(arcs[i]); 576 } 577 } 578 virtual void build() { 579 Arc arc; 580 std::vector<Arc> arcs; 581 for (notifier()->first(arc); arc != INVALID; 582 notifier()->next(arc)) { 583 arcs.push_back(arc); 584 } 585 for (int i = arcs.size() - 1; i >= 0; --i) { 586 snapshot.addArc(arcs[i]); 587 } 588 } 589 virtual void clear() { 590 Arc arc; 591 for (notifier()->first(arc); arc != INVALID; 592 notifier()->next(arc)) { 593 snapshot.eraseArc(arc); 594 } 595 } 596 597 Snapshot& snapshot; 598 }; 599 600 ListDigraph *digraph; 601 602 NodeObserverProxy node_observer_proxy; 603 ArcObserverProxy arc_observer_proxy; 604 605 std::list<Node> added_nodes; 606 std::list<Arc> added_arcs; 607 608 609 void addNode(const Node& node) { 610 added_nodes.push_front(node); 611 } 612 void eraseNode(const Node& node) { 613 std::list<Node>::iterator it = 614 std::find(added_nodes.begin(), added_nodes.end(), node); 615 if (it == added_nodes.end()) { 616 clear(); 617 arc_observer_proxy.detach(); 618 throw NodeNotifier::ImmediateDetach(); 619 } else { 620 added_nodes.erase(it); 621 } 622 } 623 624 void addArc(const Arc& arc) { 625 added_arcs.push_front(arc); 626 } 627 void eraseArc(const Arc& arc) { 628 std::list<Arc>::iterator it = 629 std::find(added_arcs.begin(), added_arcs.end(), arc); 630 if (it == added_arcs.end()) { 631 clear(); 632 node_observer_proxy.detach(); 633 throw ArcNotifier::ImmediateDetach(); 634 } else { 635 added_arcs.erase(it); 636 } 637 } 638 639 void attach(ListDigraph &_digraph) { 640 digraph = &_digraph; 641 node_observer_proxy.attach(digraph->notifier(Node())); 642 arc_observer_proxy.attach(digraph->notifier(Arc())); 643 } 644 645 void detach() { 646 node_observer_proxy.detach(); 647 arc_observer_proxy.detach(); 648 } 649 650 bool attached() const { 651 return node_observer_proxy.attached(); 652 } 653 654 void clear() { 655 added_nodes.clear(); 656 added_arcs.clear(); 657 } 658 659 public: 660 661 /// \brief Default constructor. 662 /// 663 /// Default constructor. 664 /// To actually make a snapshot you must call save(). 665 Snapshot() 666 : digraph(0), node_observer_proxy(*this), 667 arc_observer_proxy(*this) {} 668 669 /// \brief Constructor that immediately makes a snapshot. 670 /// 671 /// This constructor immediately makes a snapshot of the digraph. 672 /// \param _digraph The digraph we make a snapshot of. 673 Snapshot(ListDigraph &_digraph) 674 : node_observer_proxy(*this), 675 arc_observer_proxy(*this) { 676 attach(_digraph); 677 } 678 679 /// \brief Make a snapshot. 680 /// 681 /// Make a snapshot of the digraph. 682 /// 683 /// This function can be called more than once. In case of a repeated 684 /// call, the previous snapshot gets lost. 685 /// \param _digraph The digraph we make the snapshot of. 686 void save(ListDigraph &_digraph) { 687 if (attached()) { 688 detach(); 689 clear(); 690 } 691 attach(_digraph); 692 } 693 694 /// \brief Undo the changes until the last snapshot. 695 // 696 /// Undo the changes until the last snapshot created by save(). 697 void restore() { 698 detach(); 699 for(std::list<Arc>::iterator it = added_arcs.begin(); 700 it != added_arcs.end(); ++it) { 701 digraph->erase(*it); 702 } 703 for(std::list<Node>::iterator it = added_nodes.begin(); 704 it != added_nodes.end(); ++it) { 705 digraph->erase(*it); 706 } 707 clear(); 708 } 709 710 /// \brief Gives back true when the snapshot is valid. 711 /// 712 /// Gives back true when the snapshot is valid. 713 bool valid() const { 714 return attached(); 715 } 716 }; 717 718 }; 719 720 ///@} 721 722 class ListGraphBase { 723 724 protected: 725 726 struct NodeT { 727 int first_out; 728 int prev, next; 729 }; 730 731 struct ArcT { 732 int target; 733 int prev_out, next_out; 734 }; 735 736 std::vector<NodeT> nodes; 737 738 int first_node; 739 740 int first_free_node; 741 742 std::vector<ArcT> arcs; 743 744 int first_free_arc; 745 746 public: 747 748 typedef ListGraphBase Digraph; 749 750 class Node; 751 class Arc; 752 class Edge; 753 754 class Node { 755 friend class ListGraphBase; 756 protected: 757 758 int id; 759 explicit Node(int pid) { id = pid;} 760 761 public: 762 Node() {} 763 Node (Invalid) { id = -1; } 764 bool operator==(const Node& node) const {return id == node.id;} 765 bool operator!=(const Node& node) const {return id != node.id;} 766 bool operator<(const Node& node) const {return id < node.id;} 767 }; 768 769 class Edge { 770 friend class ListGraphBase; 771 protected: 772 773 int id; 774 explicit Edge(int pid) { id = pid;} 775 776 public: 777 Edge() {} 778 Edge (Invalid) { id = -1; } 779 bool operator==(const Edge& arc) const {return id == arc.id;} 780 bool operator!=(const Edge& arc) const {return id != arc.id;} 781 bool operator<(const Edge& arc) const {return id < arc.id;} 782 }; 783 784 class Arc { 785 friend class ListGraphBase; 786 protected: 787 788 int id; 789 explicit Arc(int pid) { id = pid;} 790 791 public: 792 operator Edge() const { return edgeFromId(id / 2); } 793 794 Arc() {} 795 Arc (Invalid) { id = -1; } 796 bool operator==(const Arc& arc) const {return id == arc.id;} 797 bool operator!=(const Arc& arc) const {return id != arc.id;} 798 bool operator<(const Arc& arc) const {return id < arc.id;} 799 }; 800 801 802 803 ListGraphBase() 804 : nodes(), first_node(-1), 805 first_free_node(-1), arcs(), first_free_arc(-1) {} 806 807 808 int maxNodeId() const { return nodes.size()-1; } 809 int maxEdgeId() const { return arcs.size() / 2 - 1; } 810 int maxArcId() const { return arcs.size()-1; } 811 812 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } 813 Node target(Arc e) const { return Node(arcs[e.id].target); } 814 815 Node u(Edge e) const { return Node(arcs[2 * e.id].target); } 816 Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); } 817 818 static bool direction(Arc e) { 819 return (e.id & 1) == 1; 820 } 821 822 static Arc direct(Edge e, bool d) { 823 return Arc(e.id * 2 + (d ? 1 : 0)); 824 } 825 826 void first(Node& node) const { 827 node.id = first_node; 828 } 829 830 void next(Node& node) const { 831 node.id = nodes[node.id].next; 832 } 833 834 void first(Arc& e) const { 835 int n = first_node; 836 while (n != -1 && nodes[n].first_out == -1) { 837 n = nodes[n].next; 838 } 839 e.id = (n == -1) ? -1 : nodes[n].first_out; 840 } 841 842 void next(Arc& e) const { 843 if (arcs[e.id].next_out != -1) { 844 e.id = arcs[e.id].next_out; 845 } else { 846 int n = nodes[arcs[e.id ^ 1].target].next; 847 while(n != -1 && nodes[n].first_out == -1) { 848 n = nodes[n].next; 849 } 850 e.id = (n == -1) ? -1 : nodes[n].first_out; 851 } 852 } 853 854 void first(Edge& e) const { 855 int n = first_node; 856 while (n != -1) { 857 e.id = nodes[n].first_out; 858 while ((e.id & 1) != 1) { 859 e.id = arcs[e.id].next_out; 860 } 861 if (e.id != -1) { 862 e.id /= 2; 863 return; 864 } 865 n = nodes[n].next; 866 } 867 e.id = -1; 868 } 869 870 void next(Edge& e) const { 871 int n = arcs[e.id * 2].target; 872 e.id = arcs[(e.id * 2) | 1].next_out; 873 while ((e.id & 1) != 1) { 874 e.id = arcs[e.id].next_out; 875 } 876 if (e.id != -1) { 877 e.id /= 2; 878 return; 879 } 880 n = nodes[n].next; 881 while (n != -1) { 882 e.id = nodes[n].first_out; 883 while ((e.id & 1) != 1) { 884 e.id = arcs[e.id].next_out; 885 } 886 if (e.id != -1) { 887 e.id /= 2; 888 return; 889 } 890 n = nodes[n].next; 891 } 892 e.id = -1; 893 } 894 895 void firstOut(Arc &e, const Node& v) const { 896 e.id = nodes[v.id].first_out; 897 } 898 void nextOut(Arc &e) const { 899 e.id = arcs[e.id].next_out; 900 } 901 902 void firstIn(Arc &e, const Node& v) const { 903 e.id = ((nodes[v.id].first_out) ^ 1); 904 if (e.id == -2) e.id = -1; 905 } 906 void nextIn(Arc &e) const { 907 e.id = ((arcs[e.id ^ 1].next_out) ^ 1); 908 if (e.id == -2) e.id = -1; 909 } 910 911 void firstInc(Edge &e, bool& d, const Node& v) const { 912 int de = nodes[v.id].first_out; 913 if (de != -1 ) { 914 e.id = de / 2; 915 d = ((de & 1) == 1); 916 } else { 917 e.id = -1; 918 d = true; 919 } 920 } 921 void nextInc(Edge &e, bool& d) const { 922 int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); 923 if (de != -1 ) { 924 e.id = de / 2; 925 d = ((de & 1) == 1); 926 } else { 927 e.id = -1; 928 d = true; 929 } 930 } 931 932 static int id(Node v) { return v.id; } 933 static int id(Arc e) { return e.id; } 934 static int id(Edge e) { return e.id; } 935 936 static Node nodeFromId(int id) { return Node(id);} 937 static Arc arcFromId(int id) { return Arc(id);} 938 static Edge edgeFromId(int id) { return Edge(id);} 939 940 Node addNode() { 941 int n; 942 943 if(first_free_node==-1) { 944 n = nodes.size(); 945 nodes.push_back(NodeT()); 946 } else { 947 n = first_free_node; 948 first_free_node = nodes[n].next; 949 } 950 951 nodes[n].next = first_node; 952 if (first_node != -1) nodes[first_node].prev = n; 953 first_node = n; 954 nodes[n].prev = -1; 955 956 nodes[n].first_out = -1; 957 958 return Node(n); 959 } 960 961 Edge addEdge(Node u, Node v) { 962 int n; 963 964 if (first_free_arc == -1) { 965 n = arcs.size(); 966 arcs.push_back(ArcT()); 967 arcs.push_back(ArcT()); 968 } else { 969 n = first_free_arc; 970 first_free_arc = arcs[n].next_out; 971 } 972 973 arcs[n].target = u.id; 974 arcs[n | 1].target = v.id; 975 976 arcs[n].next_out = nodes[v.id].first_out; 977 if (nodes[v.id].first_out != -1) { 978 arcs[nodes[v.id].first_out].prev_out = n; 979 } 980 arcs[n].prev_out = -1; 981 nodes[v.id].first_out = n; 982 983 arcs[n | 1].next_out = nodes[u.id].first_out; 984 if (nodes[u.id].first_out != -1) { 985 arcs[nodes[u.id].first_out].prev_out = (n | 1); 986 } 987 arcs[n | 1].prev_out = -1; 988 nodes[u.id].first_out = (n | 1); 989 990 return Edge(n / 2); 991 } 992 993 void erase(const Node& node) { 994 int n = node.id; 995 996 if(nodes[n].next != -1) { 997 nodes[nodes[n].next].prev = nodes[n].prev; 998 } 999 1000 if(nodes[n].prev != -1) { 1001 nodes[nodes[n].prev].next = nodes[n].next; 1002 } else { 1003 first_node = nodes[n].next; 1004 } 1005 1006 nodes[n].next = first_free_node; 1007 first_free_node = n; 1008 1009 } 1010 1011 void erase(const Edge& arc) { 1012 int n = arc.id * 2; 1013 1014 if (arcs[n].next_out != -1) { 1015 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; 1016 } 1017 1018 if (arcs[n].prev_out != -1) { 1019 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; 1020 } else { 1021 nodes[arcs[n | 1].target].first_out = arcs[n].next_out; 1022 } 1023 1024 if (arcs[n | 1].next_out != -1) { 1025 arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out; 1026 } 1027 1028 if (arcs[n | 1].prev_out != -1) { 1029 arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out; 1030 } else { 1031 nodes[arcs[n].target].first_out = arcs[n | 1].next_out; 1032 } 1033 1034 arcs[n].next_out = first_free_arc; 1035 first_free_arc = n; 1036 1037 } 1038 1039 void clear() { 1040 arcs.clear(); 1041 nodes.clear(); 1042 first_node = first_free_node = first_free_arc = -1; 1043 } 1044 1045 protected: 1046 1047 void changeTarget(Edge e, Node n) { 1048 if(arcs[2 * e.id].next_out != -1) { 1049 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; 1050 } 1051 if(arcs[2 * e.id].prev_out != -1) { 1052 arcs[arcs[2 * e.id].prev_out].next_out = 1053 arcs[2 * e.id].next_out; 1054 } else { 1055 nodes[arcs[(2 * e.id) | 1].target].first_out = 1056 arcs[2 * e.id].next_out; 1057 } 1058 1059 if (nodes[n.id].first_out != -1) { 1060 arcs[nodes[n.id].first_out].prev_out = 2 * e.id; 1061 } 1062 arcs[(2 * e.id) | 1].target = n.id; 1063 arcs[2 * e.id].prev_out = -1; 1064 arcs[2 * e.id].next_out = nodes[n.id].first_out; 1065 nodes[n.id].first_out = 2 * e.id; 1066 } 1067 1068 void changeSource(Edge e, Node n) { 1069 if(arcs[(2 * e.id) | 1].next_out != -1) { 1070 arcs[arcs[(2 * e.id) | 1].next_out].prev_out = 1071 arcs[(2 * e.id) | 1].prev_out; 1072 } 1073 if(arcs[(2 * e.id) | 1].prev_out != -1) { 1074 arcs[arcs[(2 * e.id) | 1].prev_out].next_out = 1075 arcs[(2 * e.id) | 1].next_out; 1076 } else { 1077 nodes[arcs[2 * e.id].target].first_out = 1078 arcs[(2 * e.id) | 1].next_out; 1079 } 1080 1081 if (nodes[n.id].first_out != -1) { 1082 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); 1083 } 1084 arcs[2 * e.id].target = n.id; 1085 arcs[(2 * e.id) | 1].prev_out = -1; 1086 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out; 1087 nodes[n.id].first_out = ((2 * e.id) | 1); 1088 } 1089 1090 }; 1091 1092 // typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> > 1093 // ExtendedListGraphBase; 1094 1095 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; 1096 1097 1098 1099 /// \addtogroup digraphs 1100 /// @{ 1101 1102 ///An undirected list digraph class. 1103 1104 ///This is a simple and fast undirected digraph implementation. 1105 /// 1106 ///An important extra feature of this digraph implementation is that 1107 ///its maps are real \ref concepts::ReferenceMap "reference map"s. 1108 /// 1109 ///It conforms to the 1110 ///\ref concepts::Graph "Graph concept". 1111 /// 1112 ///\sa concepts::Graph. 1113 /// 1114 class ListGraph : public ExtendedListGraphBase { 1115 private: 1116 ///ListGraph is \e not copy constructible. Use GraphCopy() instead. 1117 1118 ///ListGraph is \e not copy constructible. Use GraphCopy() instead. 1119 /// 1120 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; 1121 ///\brief Assignment of ListGraph to another one is \e not allowed. 1122 ///Use GraphCopy() instead. 1123 1124 ///Assignment of ListGraph to another one is \e not allowed. 1125 ///Use GraphCopy() instead. 1126 void operator=(const ListGraph &) {} 1127 public: 1128 /// Constructor 1129 1130 /// Constructor. 1131 /// 1132 ListGraph() {} 1133 1134 typedef ExtendedListGraphBase Parent; 1135 1136 typedef Parent::OutArcIt IncArcIt; 1137 1138 /// \brief Add a new node to the digraph. 1139 /// 1140 /// \return the new node. 1141 /// 1142 Node addNode() { return Parent::addNode(); } 1143 1144 /// \brief Add a new edge to the digraph. 1145 /// 1146 /// Add a new arc to the digraph with source node \c s 1147 /// and target node \c t. 1148 /// \return the new edge. 1149 Edge addEdge(const Node& s, const Node& t) { 1150 return Parent::addEdge(s, t); 1151 } 1152 /// \brief Changes the source of \c e to \c n 1153 /// 1154 /// Changes the source of \c e to \c n 1155 /// 1156 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s 1157 ///referencing the changed arc remain 1158 ///valid. However <tt>OutArcIt</tt>s are invalidated. 1159 void changeSource(Edge e, Node n) { 1160 Parent::changeSource(e,n); 1161 } 1162 /// \brief Changes the target of \c e to \c n 1163 /// 1164 /// Changes the target of \c e to \c n 1165 /// 1166 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain 1167 /// valid. However the other iterators may be invalidated. 1168 void changeTarget(Edge e, Node n) { 1169 Parent::changeTarget(e,n); 1170 } 1171 /// \brief Changes the source of \c e to \c n 1172 /// 1173 /// Changes the source of \c e to \c n. It changes the proper 1174 /// node of the represented edge. 1175 /// 1176 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s 1177 ///referencing the changed arc remain 1178 ///valid. However <tt>OutArcIt</tt>s are invalidated. 1179 void changeSource(Arc e, Node n) { 1180 if (Parent::direction(e)) { 1181 Parent::changeSource(e,n); 1182 } else { 1183 Parent::changeTarget(e,n); 1184 } 1185 } 1186 /// \brief Changes the target of \c e to \c n 1187 /// 1188 /// Changes the target of \c e to \c n. It changes the proper 1189 /// node of the represented edge. 1190 /// 1191 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s 1192 ///referencing the changed arc remain 1193 ///valid. However <tt>InArcIt</tt>s are invalidated. 1194 void changeTarget(Arc e, Node n) { 1195 if (Parent::direction(e)) { 1196 Parent::changeTarget(e,n); 1197 } else { 1198 Parent::changeSource(e,n); 1199 } 1200 } 1201 /// \brief Contract two nodes. 1202 /// 1203 /// This function contracts two nodes. 1204 /// 1205 /// Node \p b will be removed but instead of deleting 1206 /// its neighboring arcs, they will be joined to \p a. 1207 /// The last parameter \p r controls whether to remove loops. \c true 1208 /// means that loops will be removed. 1209 /// 1210 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain 1211 /// valid. 1212 void contract(Node a, Node b, bool r = true) { 1213 for(IncArcIt e(*this, b); e!=INVALID;) { 1214 IncArcIt f = e; ++f; 1215 if (r && runningNode(e) == a) { 1216 erase(e); 1217 } else if (source(e) == b) { 1218 changeSource(e, a); 1219 } else { 1220 changeTarget(e, a); 1221 } 1222 e = f; 1223 } 1224 erase(b); 1225 } 1226 1227 1228 /// \brief Class to make a snapshot of the digraph and restore 1229 /// to it later. 1230 /// 1231 /// Class to make a snapshot of the digraph and to restore it 1232 /// later. 1233 /// 1234 /// The newly added nodes and edges can be removed 1235 /// using the restore() function. 1236 /// 1237 /// \warning Arc and node deletions cannot be restored. This 1238 /// events invalidate the snapshot. 1239 class Snapshot { 1240 protected: 1241 1242 typedef Parent::NodeNotifier NodeNotifier; 1243 1244 class NodeObserverProxy : public NodeNotifier::ObserverBase { 1245 public: 1246 1247 NodeObserverProxy(Snapshot& _snapshot) 1248 : snapshot(_snapshot) {} 1249 1250 using NodeNotifier::ObserverBase::attach; 1251 using NodeNotifier::ObserverBase::detach; 1252 using NodeNotifier::ObserverBase::attached; 1253 1254 protected: 1255 1256 virtual void add(const Node& node) { 1257 snapshot.addNode(node); 1258 } 1259 virtual void add(const std::vector<Node>& nodes) { 1260 for (int i = nodes.size() - 1; i >= 0; ++i) { 1261 snapshot.addNode(nodes[i]); 1262 } 1263 } 1264 virtual void erase(const Node& node) { 1265 snapshot.eraseNode(node); 1266 } 1267 virtual void erase(const std::vector<Node>& nodes) { 1268 for (int i = 0; i < int(nodes.size()); ++i) { 1269 snapshot.eraseNode(nodes[i]); 1270 } 1271 } 1272 virtual void build() { 1273 Node node; 1274 std::vector<Node> nodes; 1275 for (notifier()->first(node); node != INVALID; 1276 notifier()->next(node)) { 1277 nodes.push_back(node); 1278 } 1279 for (int i = nodes.size() - 1; i >= 0; --i) { 1280 snapshot.addNode(nodes[i]); 1281 } 1282 } 1283 virtual void clear() { 1284 Node node; 1285 for (notifier()->first(node); node != INVALID; 1286 notifier()->next(node)) { 1287 snapshot.eraseNode(node); 1288 } 1289 } 1290 1291 Snapshot& snapshot; 1292 }; 1293 1294 class EdgeObserverProxy : public EdgeNotifier::ObserverBase { 1295 public: 1296 1297 EdgeObserverProxy(Snapshot& _snapshot) 1298 : snapshot(_snapshot) {} 1299 1300 using EdgeNotifier::ObserverBase::attach; 1301 using EdgeNotifier::ObserverBase::detach; 1302 using EdgeNotifier::ObserverBase::attached; 1303 1304 protected: 1305 1306 virtual void add(const Edge& arc) { 1307 snapshot.addEdge(arc); 1308 } 1309 virtual void add(const std::vector<Edge>& arcs) { 1310 for (int i = arcs.size() - 1; i >= 0; ++i) { 1311 snapshot.addEdge(arcs[i]); 1312 } 1313 } 1314 virtual void erase(const Edge& arc) { 1315 snapshot.eraseEdge(arc); 1316 } 1317 virtual void erase(const std::vector<Edge>& arcs) { 1318 for (int i = 0; i < int(arcs.size()); ++i) { 1319 snapshot.eraseEdge(arcs[i]); 1320 } 1321 } 1322 virtual void build() { 1323 Edge arc; 1324 std::vector<Edge> arcs; 1325 for (notifier()->first(arc); arc != INVALID; 1326 notifier()->next(arc)) { 1327 arcs.push_back(arc); 1328 } 1329 for (int i = arcs.size() - 1; i >= 0; --i) { 1330 snapshot.addEdge(arcs[i]); 1331 } 1332 } 1333 virtual void clear() { 1334 Edge arc; 1335 for (notifier()->first(arc); arc != INVALID; 1336 notifier()->next(arc)) { 1337 snapshot.eraseEdge(arc); 1338 } 1339 } 1340 1341 Snapshot& snapshot; 1342 }; 1343 1344 ListGraph *digraph; 1345 1346 NodeObserverProxy node_observer_proxy; 1347 EdgeObserverProxy arc_observer_proxy; 1348 1349 std::list<Node> added_nodes; 1350 std::list<Edge> added_arcs; 1351 1352 1353 void addNode(const Node& node) { 1354 added_nodes.push_front(node); 1355 } 1356 void eraseNode(const Node& node) { 1357 std::list<Node>::iterator it = 1358 std::find(added_nodes.begin(), added_nodes.end(), node); 1359 if (it == added_nodes.end()) { 1360 clear(); 1361 arc_observer_proxy.detach(); 1362 throw NodeNotifier::ImmediateDetach(); 1363 } else { 1364 added_nodes.erase(it); 1365 } 1366 } 1367 1368 void addEdge(const Edge& arc) { 1369 added_arcs.push_front(arc); 1370 } 1371 void eraseEdge(const Edge& arc) { 1372 std::list<Edge>::iterator it = 1373 std::find(added_arcs.begin(), added_arcs.end(), arc); 1374 if (it == added_arcs.end()) { 1375 clear(); 1376 node_observer_proxy.detach(); 1377 throw EdgeNotifier::ImmediateDetach(); 1378 } else { 1379 added_arcs.erase(it); 1380 } 1381 } 1382 1383 void attach(ListGraph &_digraph) { 1384 digraph = &_digraph; 1385 node_observer_proxy.attach(digraph->notifier(Node())); 1386 arc_observer_proxy.attach(digraph->notifier(Edge())); 1387 } 1388 1389 void detach() { 1390 node_observer_proxy.detach(); 1391 arc_observer_proxy.detach(); 1392 } 1393 1394 bool attached() const { 1395 return node_observer_proxy.attached(); 1396 } 1397 1398 void clear() { 1399 added_nodes.clear(); 1400 added_arcs.clear(); 1401 } 1402 1403 public: 1404 1405 /// \brief Default constructor. 1406 /// 1407 /// Default constructor. 1408 /// To actually make a snapshot you must call save(). 1409 Snapshot() 1410 : digraph(0), node_observer_proxy(*this), 1411 arc_observer_proxy(*this) {} 1412 1413 /// \brief Constructor that immediately makes a snapshot. 1414 /// 1415 /// This constructor immediately makes a snapshot of the digraph. 1416 /// \param _digraph The digraph we make a snapshot of. 1417 Snapshot(ListGraph &_digraph) 1418 : node_observer_proxy(*this), 1419 arc_observer_proxy(*this) { 1420 attach(_digraph); 1421 } 1422 1423 /// \brief Make a snapshot. 1424 /// 1425 /// Make a snapshot of the digraph. 1426 /// 1427 /// This function can be called more than once. In case of a repeated 1428 /// call, the previous snapshot gets lost. 1429 /// \param _digraph The digraph we make the snapshot of. 1430 void save(ListGraph &_digraph) { 1431 if (attached()) { 1432 detach(); 1433 clear(); 1434 } 1435 attach(_digraph); 1436 } 1437 1438 /// \brief Undo the changes until the last snapshot. 1439 // 1440 /// Undo the changes until the last snapshot created by save(). 1441 void restore() { 1442 detach(); 1443 for(std::list<Edge>::iterator it = added_arcs.begin(); 1444 it != added_arcs.end(); ++it) { 1445 digraph->erase(*it); 1446 } 1447 for(std::list<Node>::iterator it = added_nodes.begin(); 1448 it != added_nodes.end(); ++it) { 1449 digraph->erase(*it); 1450 } 1451 clear(); 1452 } 1453 1454 /// \brief Gives back true when the snapshot is valid. 1455 /// 1456 /// Gives back true when the snapshot is valid. 1457 bool valid() const { 1458 return attached(); 1459 } 1460 }; 1461 }; 1462 1463 /// @} 1464 } //namespace lemon 1465 1466 1467 #endif
Note: See TracChangeset
for help on using the changeset viewer.