Changeset 2114:677ea6c8169a in lemon0.x for lemon/list_graph.h
 Timestamp:
 06/28/06 18:27:44 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2820
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/list_graph.h
r2111 r2114 347 347 /// Changes the target of \c e to \c n 348 348 /// 349 ///\note The <tt>Edge</tt>s and <tt>OutEdge </tt>s350 /// referencing the changed edge remain351 /// valid. However <tt>InEdge</tt>s areinvalidated.349 ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing 350 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are 351 ///invalidated. 352 352 void changeTarget(Edge e, Node n) { 353 353 Parent::changeTarget(e,n); … … 357 357 /// Changes the source of \c e to \c n 358 358 /// 359 ///\note The <tt>Edge</tt>s and <tt>InEdge </tt>s360 /// referencing the changed edge remain361 /// valid. However <tt>OutEdge</tt>s areinvalidated.359 ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing 360 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are 361 ///invalidated. 362 362 void changeSource(Edge e, Node n) { 363 363 Parent::changeSource(e,n); … … 366 366 /// Invert the direction of an edge. 367 367 368 ///\note The <tt>Edge</tt>s 369 /// referencing the changed edge remain370 /// valid. However <tt>OutEdge</tt>s and <tt>InEdge</tt>s areinvalidated.368 ///\note The <tt>Edge</tt>s referencing the changed edge remain 369 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are 370 ///invalidated. 371 371 void reverseEdge(Edge e) { 372 372 Node t=target(e); … … 439 439 ///feature. 440 440 ///\todo It could be implemented in a bit faster way. 441 Node split(Node n, bool connect = true) 442 { 441 Node split(Node n, bool connect = true) { 443 442 Node b = addNode(); 444 443 for(OutEdgeIt e(*this,n);e!=INVALID;) { … … 448 447 e=f; 449 448 } 450 if (connect) addEdge(n,b);449 if (connect) addEdge(n,b); 451 450 return b; 452 451 } … … 460 459 ///\warning This functionality 461 460 ///cannot be used together with the Snapshot feature. 462 Node split(Edge e) 463 { 461 Node split(Edge e) { 464 462 Node b = addNode(); 465 463 addEdge(b,target(e)); … … 468 466 } 469 467 470 ///Class to make a snapshot of the graph and to restore it later. 471 472 ///Class to make a snapshot of the graph and to restore it later. 473 /// 474 ///The newly added nodes and edges can be removed using the 475 ///restore() function. 476 /// 477 ///\warning Edge and node deletions cannot be restored. 478 ///\warning Snapshots cannot be nested. 479 class Snapshot : protected Parent::NodeNotifier::ObserverBase, 480 protected Parent::EdgeNotifier::ObserverBase 481 { 468 /// \brief Class to make a snapshot of the graph and restore 469 /// to it later. 470 /// 471 /// Class to make a snapshot of the graph and to restore it 472 /// later. 473 /// 474 /// The newly added nodes and edges can be removed using the 475 /// restore() function. 476 /// 477 /// \warning Edge and node deletions cannot be restored. 478 class Snapshot { 482 479 public: 483 480 … … 491 488 492 489 protected: 493 494 ListGraph *g; 490 491 typedef Parent::NodeNotifier NodeNotifier; 492 493 class NodeObserverProxy : public NodeNotifier::ObserverBase { 494 public: 495 496 NodeObserverProxy(Snapshot& _snapshot) 497 : snapshot(_snapshot) {} 498 499 using NodeNotifier::ObserverBase::attach; 500 using NodeNotifier::ObserverBase::detach; 501 using NodeNotifier::ObserverBase::attached; 502 503 protected: 504 505 virtual void add(const Node& node) { 506 snapshot.addNode(node); 507 } 508 virtual void add(const std::vector<Node>& nodes) { 509 for (int i = nodes.size()  1; i >= 0; ++i) { 510 snapshot.addNode(nodes[i]); 511 } 512 } 513 virtual void erase(const Node& node) { 514 snapshot.eraseNode(node); 515 } 516 virtual void erase(const std::vector<Node>& nodes) { 517 for (int i = 0; i < (int)nodes.size(); ++i) { 518 if (!snapshot.eraseNode(nodes[i])) break; 519 } 520 } 521 virtual void build() { 522 NodeNotifier* notifier = getNotifier(); 523 Node node; 524 std::vector<Node> nodes; 525 for (notifier>first(node); node != INVALID; notifier>next(node)) { 526 nodes.push_back(node); 527 } 528 for (int i = nodes.size()  1; i >= 0; i) { 529 snapshot.addNode(nodes[i]); 530 } 531 } 532 virtual void clear() { 533 NodeNotifier* notifier = getNotifier(); 534 Node node; 535 for (notifier>first(node); node != INVALID; notifier>next(node)) { 536 if (!snapshot.eraseNode(node)) break; 537 } 538 } 539 540 Snapshot& snapshot; 541 }; 542 543 class EdgeObserverProxy : public EdgeNotifier::ObserverBase { 544 public: 545 546 EdgeObserverProxy(Snapshot& _snapshot) 547 : snapshot(_snapshot) {} 548 549 using EdgeNotifier::ObserverBase::attach; 550 using EdgeNotifier::ObserverBase::detach; 551 using EdgeNotifier::ObserverBase::attached; 552 553 protected: 554 555 virtual void add(const Edge& edge) { 556 snapshot.addEdge(edge); 557 } 558 virtual void add(const std::vector<Edge>& edges) { 559 for (int i = edges.size()  1; i >= 0; ++i) { 560 snapshot.addEdge(edges[i]); 561 } 562 } 563 virtual void erase(const Edge& edge) { 564 snapshot.eraseEdge(edge); 565 } 566 virtual void erase(const std::vector<Edge>& edges) { 567 for (int i = 0; i < (int)edges.size(); ++i) { 568 if (!snapshot.eraseEdge(edges[i])) break; 569 } 570 } 571 virtual void build() { 572 EdgeNotifier* notifier = getNotifier(); 573 Edge edge; 574 std::vector<Edge> edges; 575 for (notifier>first(edge); edge != INVALID; notifier>next(edge)) { 576 edges.push_back(edge); 577 } 578 for (int i = edges.size()  1; i >= 0; i) { 579 snapshot.addEdge(edges[i]); 580 } 581 } 582 virtual void clear() { 583 EdgeNotifier* notifier = getNotifier(); 584 Edge edge; 585 for (notifier>first(edge); edge != INVALID; notifier>next(edge)) { 586 if (!snapshot.eraseEdge(edge)) break; 587 } 588 } 589 590 Snapshot& snapshot; 591 }; 592 593 ListGraph *graph; 594 595 NodeObserverProxy node_observer_proxy; 596 EdgeObserverProxy edge_observer_proxy; 597 495 598 std::list<Node> added_nodes; 496 599 std::list<Edge> added_edges; 497 498 bool active; 499 virtual void add(const Node& n) { 500 added_nodes.push_back(n); 501 }; 502 virtual void erase(const Node&) 503 { 504 throw UnsupportedOperation(); 505 } 506 virtual void add(const Edge& n) { 507 added_edges.push_back(n); 508 }; 509 virtual void erase(const Edge&) 510 { 511 throw UnsupportedOperation(); 512 } 513 514 ///\bug What is this used for? 600 601 602 void addNode(const Node& node) { 603 added_nodes.push_front(node); 604 } 605 bool eraseNode(const Node& node) { 606 std::list<Node>::iterator it = 607 std::find(added_nodes.begin(), added_nodes.end(), node); 608 if (it == added_nodes.end()) { 609 clear(); 610 return false; 611 } else { 612 added_nodes.erase(it); 613 return true; 614 } 615 } 616 617 void addEdge(const Edge& edge) { 618 added_edges.push_front(edge); 619 } 620 bool eraseEdge(const Edge& edge) { 621 std::list<Edge>::iterator it = 622 std::find(added_edges.begin(), added_edges.end(), edge); 623 if (it == added_edges.end()) { 624 clear(); 625 return false; 626 } else { 627 added_edges.erase(it); 628 return true; 629 } 630 } 631 632 void attach(ListGraph &_graph) { 633 graph = &_graph; 634 node_observer_proxy.attach(graph>getNotifier(Node())); 635 edge_observer_proxy.attach(graph>getNotifier(Edge())); 636 } 637 638 void detach() { 639 node_observer_proxy.detach(); 640 edge_observer_proxy.detach(); 641 } 642 643 void clear() { 644 detach(); 645 added_nodes.clear(); 646 added_edges.clear(); 647 } 648 649 public: 650 651 /// \brief Default constructur. 515 652 /// 516 virtual void build() {} 517 ///\bug What is this used for? 653 /// Default constructor. 654 /// To actually make a snapshot you must call save(). 655 Snapshot() 656 : graph(0), node_observer_proxy(*this), 657 edge_observer_proxy(*this) {} 658 659 /// \brief Constructor that immediately makes a snapshot. 660 /// 661 /// This constructor immediately makes a snapshot of the graph. 662 /// \param _graph The graph we make a snapshot of. 663 Snapshot(ListGraph &_graph) 664 : node_observer_proxy(*this), 665 edge_observer_proxy(*this) { 666 attach(_graph); 667 } 668 669 /// \brief Make a snapshot. 518 670 /// 519 virtual void clear() {} 520 521 void regist(ListGraph &_g) { 522 g=&_g; 523 Parent::NodeNotifier::ObserverBase::attach(g>getNotifier(Node())); 524 Parent::EdgeNotifier::ObserverBase::attach(g>getNotifier(Edge())); 525 } 526 527 void deregist() { 528 Parent::NodeNotifier::ObserverBase::detach(); 529 Parent::EdgeNotifier::ObserverBase::detach(); 530 g=0; 531 } 532 533 public: 534 ///Default constructur. 535 536 ///Default constructur. 537 ///To actually make a snapshot you must call save(). 671 /// Make a snapshot of the graph. 538 672 /// 539 Snapshot() : g(0) {} 540 ///Constructor that immediately makes a snapshot. 541 542 ///This constructor immediately makes a snapshot of the graph. 543 ///\param _g The graph we make a snapshot of. 544 Snapshot(ListGraph &_g) { 545 regist(_g); 546 } 547 ///\bug Is it necessary? 673 /// This function can be called more than once. In case of a repeated 674 /// call, the previous snapshot gets lost. 675 /// \param _graph The graph we make the snapshot of. 676 void save(ListGraph &_graph) { 677 clear(); 678 attach(_graph); 679 } 680 681 /// \brief Undo the changes until the last snapshot. 682 // 683 /// Undo the changes until last snapshot created by save(). 548 684 /// 549 ~Snapshot() 550 { 551 if(g) deregist(); 552 } 553 554 ///Make a snapshot. 555 556 ///Make a snapshot of the graph. 557 /// 558 ///This function can be called more than once. In case of a repeated 559 ///call, the previous snapshot gets lost. 560 ///\param _g The graph we make the snapshot of. 561 void save(ListGraph &_g) 562 { 563 if(g!=&_g) { 564 if(g) deregist(); 565 regist(_g); 566 } 567 added_nodes.clear(); 568 added_edges.clear(); 569 } 570 571 ///Undo the changes until the last snapshot. 572 573 ///Undo the changes until last snapshot created by save(). 574 /// 575 ///\todo This function might be called undo(). 685 /// \todo This function might be called undo(). 576 686 void restore() { 577 ListGraph &old_g=*g; 578 deregist(); 687 detach(); 579 688 while(!added_edges.empty()) { 580 old_g.erase(added_edges.front());689 graph>erase(added_edges.front()); 581 690 added_edges.pop_front(); 582 691 } 583 692 while(!added_nodes.empty()) { 584 old_g.erase(added_nodes.front());693 graph>erase(added_nodes.front()); 585 694 added_nodes.pop_front(); 586 695 } 696 } 697 698 /// \brief Gives back true when the snapshot is valid. 699 /// 700 /// Gives back true when the snapshot is valid. 701 bool valid() const { 702 return node_observer_proxy.attached(); 587 703 } 588 704 };
Note: See TracChangeset
for help on using the changeset viewer.