COIN-OR::LEMON - Graph Library

Changeset 2114:677ea6c8169a in lemon-0.x for lemon/list_graph.h


Ignore:
Timestamp:
06/28/06 18:27:44 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2820
Message:

new snapshot

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r2111 r2114  
    347347    /// Changes the target of \c e to \c n
    348348    ///
    349     ///\note The <tt>Edge</tt>s and <tt>OutEdge</tt>s
    350     ///referencing the changed edge remain
    351     ///valid. However <tt>InEdge</tt>s are invalidated.
     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.
    352352    void changeTarget(Edge e, Node n) {
    353353      Parent::changeTarget(e,n);
     
    357357    /// Changes the source of \c e to \c n
    358358    ///
    359     ///\note The <tt>Edge</tt>s and <tt>InEdge</tt>s
    360     ///referencing the changed edge remain
    361     ///valid. However <tt>OutEdge</tt>s are invalidated.
     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.
    362362    void changeSource(Edge e, Node n) {
    363363      Parent::changeSource(e,n);
     
    366366    /// Invert the direction of an edge.
    367367
    368     ///\note The <tt>Edge</tt>s
    369     ///referencing the changed edge remain
    370     ///valid. However <tt>OutEdge</tt>s  and <tt>InEdge</tt>s are invalidated.
     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.
    371371    void reverseEdge(Edge e) {
    372372      Node t=target(e);
     
    439439    ///feature.
    440440    ///\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) {
    443442      Node b = addNode();
    444443      for(OutEdgeIt e(*this,n);e!=INVALID;) {
     
    448447        e=f;
    449448      }
    450       if(connect) addEdge(n,b);
     449      if (connect) addEdge(n,b);
    451450      return b;
    452451    }
     
    460459    ///\warning This functionality
    461460    ///cannot be used together with the Snapshot feature.
    462     Node split(Edge e)
    463     {
     461    Node split(Edge e) {
    464462      Node b = addNode();
    465463      addEdge(b,target(e));
     
    468466    }
    469467     
    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 {
    482479    public:
    483480     
     
    491488
    492489    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
    495598      std::list<Node> added_nodes;
    496599      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.
    515652      ///
    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.
    518670      ///
    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.
    538672      ///
    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().
    548684      ///
    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().
    576686      void restore() {
    577         ListGraph &old_g=*g;
    578         deregist();
     687        detach();
    579688        while(!added_edges.empty()) {
    580           old_g.erase(added_edges.front());
     689          graph->erase(added_edges.front());
    581690          added_edges.pop_front();
    582691        }
    583692        while(!added_nodes.empty()) {
    584           old_g.erase(added_nodes.front());
     693          graph->erase(added_nodes.front());
    585694          added_nodes.pop_front();
    586695        }
     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();
    587703      }
    588704    };
Note: See TracChangeset for help on using the changeset viewer.