COIN-OR::LEMON - Graph Library

Changeset 973:6a6f3ac07b20 in lemon-0.x


Ignore:
Timestamp:
11/09/04 18:48:52 (16 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1361
Message:
  • Add makeSnapshot()/rollBack() functionality
  • Remove an unnecessary #include
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/smart_graph.h

    r969 r973  
    2626#include <lemon/invalid.h>
    2727
    28 #include <lemon/erasable_graph_extender.h>
    2928#include <lemon/clearable_graph_extender.h>
    3029#include <lemon/extendable_graph_extender.h>
     
    4645  /// @{
    4746
     47  class SmartGraph;
    4848  ///Base of SmartGraph
    4949
     
    5252  class SmartGraphBase {
    5353
     54    friend class SmatGraph;
     55
     56  protected:
    5457    struct NodeT
    5558    {
     
    144147    class Node {
    145148      friend class SmartGraphBase;
     149      friend class SmartGraph;
    146150
    147151    protected:
    148152      int n;
     153      ///\todo It should be removed (or at least define a setToId() instead).
     154      ///
    149155      Node(int nn) {n=nn;}
    150156    public:
     
    159165    class Edge {
    160166      friend class SmartGraphBase;
     167      friend class SmartGraph;
    161168
    162169    protected:
    163170      int n;
     171      ///\todo It should be removed (or at least define a setToId() instead).
     172      ///
    164173      Edge(int nn) {n=nn;}
    165174    public:
     
    210219      return prev;
    211220    }
     221
    212222  };
    213223
     
    241251  public:
    242252    /// Finds an edge between two nodes.
    243 
     253   
    244254    /// Finds an edge from node \c u to node \c v.
    245255    ///
     
    260270      return _findEdge(u,v,prev);
    261271    }
    262 };
     272   
     273    ///Internal data structure to store snapshots
     274   
     275    ///\ingroup graphs
     276    ///\sa makeSnapShot()
     277    ///\sa rollBack()
     278    struct SnapShot
     279    {
     280      unsigned int node_num;
     281      unsigned int edge_num;
     282    };
     283   
     284    ///Make a snapshot of the graph.
     285
     286    ///Make a snapshot of the graph.
     287    ///
     288    ///The newly added nodes and edges can be removed using the
     289    ///rollBack() function.
     290    ///
     291    ///\return An stucture SnapShot describing the pesent state of the
     292    ///graph.
     293    ///\note After you rolled back to a state, you cannot roll "back" to
     294    ///a later state, in other word you cannot add again the edges deleted
     295    ///by rollBack().
     296    SnapShot makeSnapShot()
     297    {
     298      SnapShot s;
     299      s.node_num=nodes.size();
     300      s.edge_num=edges.size();
     301      return s;
     302    }
     303   
     304    ///Undo the changes until a snapshot.
     305
     306    ///Undo the changes until a snapshot created by makeSnapShot().
     307    ///
     308    ///\param s an internal stucture given back by makeSnapShot()
     309    ///\note After you rolled back to a state, you cannot "roll forward" to
     310    ///a later state, in other word you cannot add again the edges deleted
     311    ///by rollBack().
     312    ///
     313    ///\todo This function might be called undo().
     314   
     315    void rollBack(const SnapShot &s)
     316    {
     317      while(s.edge_num>edges.size()) {
     318        edge_observers.erase(Edge(edges.size()-1));
     319        nodes[edges.back().head].first_in=edges.back().next_in;
     320        nodes[edges.back().tail].first_out=edges.back().next_out;
     321        edges.pop_back();
     322      }
     323      //nodes.resize(s.nodes_num);
     324      while(s.node_num>nodes.size()) {
     325        node_observers.erase(Node(nodes.size()-1));
     326        nodes.pop_back();
     327      }
     328    }
     329  };
    263330 
    264331  template <>
Note: See TracChangeset for help on using the changeset viewer.