COIN-OR::LEMON - Graph Library

Changeset 1011:5bd6c7671c9e in lemon-0.x


Ignore:
Timestamp:
11/20/04 11:19:06 (16 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1401
Message:
  • snapshot-rollback functionarity added to ListGraph?
  • The iterface of the snapshot-rollback functionarity in SmartGraph? has changed to be compatible with ListGraph::SnapShot?.
Location:
src/lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/list_graph.h

    r1010 r1011  
    3232#include <lemon/default_map.h>
    3333
     34#include <list>
    3435
    3536namespace lemon {
     
    387388      erase(b);
    388389    }
     390
     391
     392    ///Class to make a snapshot of the graph and to restrore to it later.
     393
     394    ///Class to make a snapshot of the graph and to restrore to it later.
     395    ///
     396    ///The newly added nodes and edges can be removed using the
     397    ///restore() function.
     398    ///
     399    ///\warning Edge and node deletions cannot be restored.
     400    ///\warning SnapShots cannot be nested.
     401    ///\ingroup graphs
     402    class SnapShot : public AlterationObserverRegistry<Node>::ObserverBase,
     403                     public AlterationObserverRegistry<Edge>::ObserverBase
     404    {
     405      protected:
     406     
     407      ListGraph *g;
     408      std::list<Node> added_nodes;
     409      std::list<Edge> added_edges;
     410     
     411      bool active;
     412      virtual void add(const Node& n) {
     413        added_nodes.push_back(n);
     414      };
     415      ///\bug Exception...
     416      ///
     417      virtual void erase(const Node&)
     418      {
     419        exit(1);
     420      }
     421      virtual void add(const Edge& n) {
     422        added_edges.push_back(n);
     423      };
     424      ///\bug Exception...
     425      ///
     426      virtual void erase(const Edge&)
     427      {
     428        exit(1);
     429      }
     430
     431      void regist(ListGraph &_g) {
     432        g=&_g;
     433        AlterationObserverRegistry<Node>::ObserverBase::
     434          attach(g->node_observers);
     435        AlterationObserverRegistry<Edge>::ObserverBase::
     436          attach(g->edge_observers);
     437      }
     438           
     439      void deregist() {
     440        AlterationObserverRegistry<Node>::ObserverBase::
     441          detach();
     442        AlterationObserverRegistry<Edge>::ObserverBase::
     443          detach();
     444        g=0;
     445      }
     446           
     447    public:
     448      ///Default constructur.
     449     
     450      ///Default constructur.
     451      ///To actually make a snapshot you must call save().
     452      ///
     453      SnapShot() : g(0) {}
     454      ///Constructor that immediately makes a snapshot.
     455     
     456      ///This constructor immediately makes a snapshot of the graph.
     457      ///\param _g The graph we make a snapshot of.
     458      SnapShot(ListGraph &_g) {
     459        regist(_g);
     460      }
     461      ///\bug Is it necessary?
     462      ///
     463      ~SnapShot()
     464      {
     465        if(g) deregist();
     466      }
     467     
     468      ///Make a snapshot.
     469
     470      ///Make a snapshot of the graph.
     471      ///
     472      ///This function can be called more than once. In case of a repeated
     473      ///call, the previous snapshot gets lost.
     474      ///\param _g The graph we make the snapshot of.
     475      void save(ListGraph &_g)
     476      {
     477        if(g!=&_g) {
     478          if(g) deregist();
     479          regist(_g);
     480        }
     481        added_nodes.clear();
     482        added_edges.clear();
     483      }
     484     
     485    ///Undo the changes until the last snapshot.
     486
     487    ///Undo the changes until last snapshot created by save().
     488    ///
     489    ///\todo This function might be called undo().
     490      void restore() {
     491        deregist();
     492        while(!added_edges.empty()) {
     493          g->erase(added_edges.front());
     494          added_edges.pop_front();
     495        }
     496        while(!added_nodes.empty()) {
     497          g->erase(added_nodes.front());
     498          added_nodes.pop_front();
     499        }
     500      }
     501    };
     502   
    389503  };
    390504 
  • src/lemon/smart_graph.h

    r986 r1011  
    261261    }
    262262   
    263     ///Internal data structure to store snapshots
    264    
    265     ///\ingroup graphs
    266     ///\sa makeSnapShot()
    267     ///\sa rollBack()
    268     struct SnapShot
    269     {
    270       unsigned int node_num;
    271       unsigned int edge_num;
    272     };
    273    
    274     ///Make a snapshot of the graph.
    275 
    276     ///Make a snapshot of the graph.
    277     ///
    278     ///The newly added nodes and edges can be removed using the
    279     ///rollBack() function.
    280     ///
    281     ///\return An stucture SnapShot describing the pesent state of the
    282     ///graph.
    283     ///\note After you rolled back to a state, you cannot roll "back" to
    284     ///a later state, in other word you cannot add again the edges deleted
    285     ///by rollBack().
    286     ///\todo This function might be called saveState() or getState().
    287     SnapShot makeSnapShot()
    288     {
    289       SnapShot s;
    290       s.node_num=nodes.size();
    291       s.edge_num=edges.size();
    292       return s;
    293     }
    294    
    295     ///Undo the changes until a snapshot.
    296 
    297     ///Undo the changes until a snapshot created by makeSnapShot().
    298     ///
    299     ///\param s an internal stucture given back by makeSnapShot()
    300     ///\note After you rolled back to a state, you cannot "roll forward" to
    301     ///a later state, in other word you cannot add again the edges deleted
    302     ///by rollBack().
    303     ///
    304     ///\todo This function might be called undo().
    305    
    306     void rollBack(const SnapShot &s)
     263    class SnapShot;
     264    friend class SnapShot;
     265
     266  protected:
     267    void restoreSnapShot(const SnapShot &s)
    307268    {
    308269      while(s.edge_num>edges.size()) {
     
    317278        nodes.pop_back();
    318279      }
    319     }
     280    }   
     281
     282  public:
     283    ///Class to make a snapshot of the graph and to restrore to it later.
     284
     285    ///Class to make a snapshot of the graph and to restrore to it later.
     286    ///
     287    ///The newly added nodes and edges can be removed using the
     288    ///restore() function.
     289    ///\note After you restore a state, you cannot restore
     290    ///a later state, in other word you cannot add again the edges deleted
     291    ///by restore() using another SnapShot instance.
     292    ///
     293    ///\ingroup graphs
     294    class SnapShot
     295    {
     296      SmartGraph *g;
     297    protected:
     298      friend class SmartGraph;
     299      unsigned int node_num;
     300      unsigned int edge_num;
     301    public:
     302      ///Default constructur.
     303     
     304      ///Default constructur.
     305      ///To actually make a snapshot you must call save().
     306      ///
     307      SnapShot() : g(0) {}
     308      ///Constructor that immediately makes a snapshot
     309     
     310      ///This constructor immediately makes a snapshot of the graph.
     311      ///\param _g The graph we make a snapshot of.
     312      SnapShot(SmartGraph &_g) :g(&_g) {
     313        node_num=g->nodes.size();
     314        edge_num=g->edges.size();
     315      }
     316
     317      ///Make a snapshot.
     318
     319      ///Make a snapshot of the graph.
     320      ///
     321      ///This function can be called more than once. In case of a repeated
     322      ///call, the previous snapshot gets lost.
     323      ///\param _g The graph we make the snapshot of.
     324      void save(SmartGraph &_g)
     325      {
     326        g=&_g;
     327        node_num=g->nodes.size();
     328        edge_num=g->edges.size();
     329      }
     330
     331      ///Undo the changes until a snapshot.
     332     
     333      ///Undo the changes until a snapshot created by save().
     334      ///
     335      ///\param s an internal stucture given back by save()
     336      ///\note After you restored a state, you cannot restore
     337      ///a later state, in other word you cannot add again the edges deleted
     338      ///by restore().
     339      ///
     340      ///\todo This function might be called undo().
     341     
     342      void restore()
     343      {
     344        g->restoreSnapShot(*this);
     345      }
     346    };
    320347  };
    321348 
Note: See TracChangeset for help on using the changeset viewer.