Changeset 2190:dd887831e9c1 in lemon-0.x

Timestamp:

09/04/06 13:09:13 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2915

Message:

Snapshot for SmartUGraph an SmartBpUGraph

File:

• lemon/smart_graph.h (modified) (17 diffs)

lemon/smart_graph.h

@@ -44 +44 @@
   ///
   class SmartGraphBase {
-
-    friend class SmatGraph;
-
   protected:
+
     struct NodeT 
     {
-      int first_in,first_out;      
-      NodeT() : first_in(-1), first_out(-1) {}
+      int first_in, first_out;      
+      NodeT() {}
     };
     struct EdgeT 
     {
       int target, source, next_in, next_out;      
-      //FIXME: is this necessary?
-      EdgeT() : next_in(-1), next_out(-1) {}  
+      EdgeT() {}  
     };
 
@@ -82 +79 @@
     typedef True EdgeNumTag;
 
-    ///Number of nodes.
     int nodeNum() const { return nodes.size(); }
-    ///Number of edges.
     int edgeNum() const { return edges.size(); }
 
-    /// Maximum node ID.
-    
-    /// Maximum node ID.
-    ///\sa id(Node)
     int maxNodeId() const { return nodes.size()-1; }
-    /// Maximum edge ID.
-    
-    /// Maximum edge ID.
-    ///\sa id(Edge)
     int maxEdgeId() const { return edges.size()-1; }
 
     Node addNode() {
-      Node n; n.n=nodes.size();
-      nodes.push_back(NodeT()); //FIXME: Hmmm...
-      return n;
+      int n = nodes.size();     
+      nodes.push_back(NodeT());
+      nodes[n].first_in = -1;
+      nodes[n].first_out = -1;
+      return Node(n);
     }
     
     Edge addEdge(Node u, Node v) {
-      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
-      edges[e.n].source=u.n; edges[e.n].target=v.n;
-      edges[e.n].next_out=nodes[u.n].first_out;
-      edges[e.n].next_in=nodes[v.n].first_in;
-      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
-
-      return e;
-    }
-
-
-    Node source(Edge e) const { return edges[e.n].source; }
-    Node target(Edge e) const { return edges[e.n].target; }
-
-    /// Node ID.
-    
-    /// The ID of a valid Node is a nonnegative integer not greater than
-    /// \ref maxNodeId(). The range of the ID's is not surely continuous
-    /// and the greatest node ID can be actually less then \ref maxNodeId().
-    ///
-    /// The ID of the \ref INVALID node is -1.
-    ///\return The ID of the node \c v. 
-    static int id(Node v) { return v.n; }
-    /// Edge ID.
-    
-    /// The ID of a valid Edge is a nonnegative integer not greater than
-    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
-    ///
-    /// The ID of the \ref INVALID edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(Edge e) { return e.n; }
-
-    /// \brief Returns the node from its \c id.
-    ///
-    /// Returns the node from its \c id. If there is not node
-    /// with the given id the effect of the function is undefinied.
+      int n = edges.size(); 
+      edges.push_back(EdgeT());
+      edges[n].source = u.id; 
+      edges[n].target = v.id;
+      edges[n].next_out = nodes[u.id].first_out;
+      edges[n].next_in = nodes[v.id].first_in;
+      nodes[u.id].first_out = nodes[v.id].first_in = n;
+
+      return Edge(n);
+    }
+
+    void clear() {
+      edges.clear();
+      nodes.clear();
+    }
+
+    Node source(Edge e) const { return Node(edges[e.id].source); }
+    Node target(Edge e) const { return Node(edges[e.id].target); }
+
+    static int id(Node v) { return v.id; }
+    static int id(Edge e) { return e.id; }
+
     static Node nodeFromId(int id) { return Node(id);}
-
-    /// \brief Returns the edge from its \c id.
-    ///
-    /// Returns the edge from its \c id. If there is not edge
-    /// with the given id the effect of the function is undefinied.
     static Edge edgeFromId(int id) { return Edge(id);}
 
@@ -154 +124 @@
 
     protected:
-      int n;
-      Node(int nn) {n=nn;}
+      int id;
+      explicit Node(int _id) : id(_id) {}
     public:
       Node() {}
-      Node (Invalid) { n=-1; }
-      bool operator==(const Node i) const {return n==i.n;}
-      bool operator!=(const Node i) const {return n!=i.n;}
-      bool operator<(const Node i) const {return n<i.n;}
+      Node (Invalid) : id(-1) {}
+      bool operator==(const Node i) const {return id == i.id;}
+      bool operator!=(const Node i) const {return id != i.id;}
+      bool operator<(const Node i) const {return id < i.id;}
     };
     
@@ -170 +140 @@
 
     protected:
-      int n;
-      Edge(int nn) {n=nn;}
+      int id;
+      explicit Edge(int _id) : id(_id) {}
     public:
       Edge() { }
-      Edge (Invalid) { n=-1; }
-      bool operator==(const Edge i) const {return n==i.n;}
-      bool operator!=(const Edge i) const {return n!=i.n;}
-      bool operator<(const Edge i) const {return n<i.n;}
+      Edge (Invalid) : id(-1) {}
+      bool operator==(const Edge i) const {return id == i.id;}
+      bool operator!=(const Edge i) const {return id != i.id;}
+      bool operator<(const Edge i) const {return id < i.id;}
     };
 
     void first(Node& node) const {
-      node.n = nodes.size() - 1;
+      node.id = nodes.size() - 1;
     }
 
     static void next(Node& node) {
-      --node.n;
+      --node.id;
     }
 
     void first(Edge& edge) const {
-      edge.n = edges.size() - 1;
+      edge.id = edges.size() - 1;
     }
 
     static void next(Edge& edge) {
-      --edge.n;
+      --edge.id;
     }
 
     void firstOut(Edge& edge, const Node& node) const {
-      edge.n = nodes[node.n].first_out;
+      edge.id = nodes[node.id].first_out;
     }
 
     void nextOut(Edge& edge) const {
-      edge.n = edges[edge.n].next_out;
+      edge.id = edges[edge.id].next_out;
     }
 
     void firstIn(Edge& edge, const Node& node) const {
-      edge.n = nodes[node.n].first_in;
+      edge.id = nodes[node.id].first_in;
     }
     
     void nextIn(Edge& edge) const {
-      edge.n = edges[edge.n].next_in;
+      edge.id = edges[edge.id].next_in;
     }
 
@@ -234 +204 @@
     typedef ExtendedSmartGraphBase Parent;
 
-    class Snapshot;
-    friend class Snapshot;
-
   private:
+
     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
 
     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
     ///
-    SmartGraph(const SmartGraph &) :ExtendedSmartGraphBase() {};
+    SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
     ///\brief Assignment of SmartGraph to another one is \e not allowed.
     ///Use GraphCopy() instead.
@@ -249 +217 @@
     ///Use GraphCopy() instead.
     void operator=(const SmartGraph &) {}
-  protected:
-    void restoreSnapshot(const Snapshot &s)
-    {
-      while(s.edge_num<edges.size()) {
-        Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
-        nodes[edges.back().target].first_in=edges.back().next_in;
-        nodes[edges.back().source].first_out=edges.back().next_out;
-        edges.pop_back();
-      }
-      //nodes.resize(s.nodes_num);
-      while(s.node_num<nodes.size()) {
-        Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
-        nodes.pop_back();
-      }
-    }    
 
   public:
@@ -288 +241 @@
     }
 
-    ///\e
-    
-    ///\bug Undocumented
-    ///\bug Doesn't destruct the maps.
+    ///Clear the graph.
+    
+    ///Erase all the nodes and edges from the graph.
+    ///
     void clear() {
-      edges.clear();
-      nodes.clear();
+      Parent::clear();
     }
 
@@ -315 +267 @@
     {
       Node b = addNode();
-      nodes[b.n].first_out=nodes[n.n].first_out;
-      nodes[n.n].first_out=-1;
-      for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
+      nodes[b.id].first_out=nodes[n.id].first_out;
+      nodes[n.id].first_out=-1;
+      for(int i=nodes[b.id].first_out;i!=-1;i++) edges[i].source=b.id;
       if(connect) addEdge(n,b);
       return b;
     }
+
+  public:
+    
+    class Snapshot;
+
+  protected:
+
+    void restoreSnapshot(const Snapshot &s)
+    {
+      while(s.edge_num<edges.size()) {
+        Edge edge = edgeFromId(edges.size()-1);
+        Parent::getNotifier(Edge()).erase(edge);
+        nodes[edges.back().source].first_out=edges.back().next_out;
+        nodes[edges.back().target].first_in=edges.back().next_in;
+        edges.pop_back();
+      }
+      while(s.node_num<nodes.size()) {
+        Node node = nodeFromId(nodes.size()-1);
+        Parent::getNotifier(Node()).erase(node);
+        nodes.pop_back();
+      }
+    }    
+
+  public:
 
     ///Class to make a snapshot of the graph and to restrore to it later.
@@ -332 +308 @@
     ///by restore() using another one Snapshot instance.
     ///
+    ///\warning If you do not use correctly the snapshot that can cause
+    ///either broken program, invalid state of the graph, valid but
+    ///not the restored graph or no change. Because the runtime performance
+    ///the validity of the snapshot is not stored.
     class Snapshot 
     {
@@ -376 +356 @@
       ///a later state, in other word you cannot add again the edges deleted
       ///by restore().
-      ///
-      ///\todo This function might be called undo().
-      
       void restore()
       {
@@ -408 +385 @@
   class SmartUGraph : public ExtendedSmartUGraphBase {
   private:
+
     ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
 
@@ -413 +391 @@
     ///
     SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {};
+
     ///\brief Assignment of SmartUGraph to another one is \e not allowed.
     ///Use UGraphCopy() instead.
@@ -419 +398 @@
     ///Use UGraphCopy() instead.
     void operator=(const SmartUGraph &) {}
-  public:
+
+  public:
+
+    typedef ExtendedSmartUGraphBase Parent;
+
     /// Constructor
     
@@ -425 +408 @@
     ///
     SmartUGraph() {}
+
+    ///Add a new node to the graph.
+    
+    /// \return the new node.
+    ///
+    Node addNode() { return Parent::addNode(); }
+    
+    ///Add a new undirected edge to the graph.
+    
+    ///Add a new undirected edge to the graph with node \c s
+    ///and \c t.
+    ///\return the new undirected edge.
+    UEdge addEdge(const Node& s, const Node& t) { 
+      return Parent::addEdge(s, t); 
+    }
+
+    ///Clear the graph.
+    
+    ///Erase all the nodes and edges from the graph.
+    ///
+    void clear() {
+      Parent::clear();
+    }
+
+  public:
+    
+    class Snapshot;
+
+  protected:
+
+
+    void restoreSnapshot(const Snapshot &s)
+    {
+      while(s.edge_num<edges.size()) {
+        UEdge edge = uEdgeFromId(edges.size()-1);
+        Parent::getNotifier(UEdge()).erase(edge);
+        std::vector<Edge> dir;
+        dir.push_back(Parent::direct(edge, true));
+        dir.push_back(Parent::direct(edge, false));
+        Parent::getNotifier(Edge()).erase(dir);
+        nodes[edges.back().source].first_out=edges.back().next_out;
+        nodes[edges.back().target].first_in=edges.back().next_in;
+        edges.pop_back();
+      }
+      while(s.node_num<nodes.size()) {
+        Node node = nodeFromId(nodes.size()-1);
+        Parent::getNotifier(Node()).erase(node);
+        nodes.pop_back();
+      }
+    }    
+
+  public:
+
+    ///Class to make a snapshot of the graph and to restrore to it later.
+
+    ///Class to make a snapshot of the graph and to restrore to it later.
+    ///
+    ///The newly added nodes and edges can be removed using the
+    ///restore() function.
+    ///
+    ///\note After you restore a state, you cannot restore
+    ///a later state, in other word you cannot add again the edges deleted
+    ///by restore() using another one Snapshot instance.
+    ///
+    ///\warning If you do not use correctly the snapshot that can cause
+    ///either broken program, invalid state of the graph, valid but
+    ///not the restored graph or no change. Because the runtime performance
+    ///the validity of the snapshot is not stored.
+    class Snapshot 
+    {
+      SmartUGraph *g;
+    protected:
+      friend class SmartUGraph;
+      unsigned int node_num;
+      unsigned int edge_num;
+    public:
+      ///Default constructor.
+      
+      ///Default constructor.
+      ///To actually make a snapshot you must call save().
+      ///
+      Snapshot() : g(0) {}
+      ///Constructor that immediately makes a snapshot
+      
+      ///This constructor immediately makes a snapshot of the graph.
+      ///\param _g The graph we make a snapshot of.
+      Snapshot(SmartUGraph &_g) :g(&_g) {
+        node_num=g->nodes.size();
+        edge_num=g->edges.size();
+      }
+
+      ///Make a snapshot.
+
+      ///Make a snapshot of the graph.
+      ///
+      ///This function can be called more than once. In case of a repeated
+      ///call, the previous snapshot gets lost.
+      ///\param _g The graph we make the snapshot of.
+      void save(SmartUGraph &_g) 
+      {
+        g=&_g;
+        node_num=g->nodes.size();
+        edge_num=g->edges.size();
+      }
+
+      ///Undo the changes until a snapshot.
+      
+      ///Undo the changes until a snapshot created by save().
+      ///
+      ///\note After you restored a state, you cannot restore
+      ///a later state, in other word you cannot add again the edges deleted
+      ///by restore().
+      void restore()
+      {
+        g->restoreSnapshot(*this);
+      }
+    };
   };
 
@@ -463 +563 @@
       int id;
 
-      Node(int _id) : id(_id) {}
+      explicit Node(int _id) : id(_id) {}
     public:
       Node() {}
-      Node(Invalid) { id = -1; }
+      Node(Invalid) : id(-1) {}
       bool operator==(const Node i) const {return id==i.id;}
       bool operator!=(const Node i) const {return id!=i.id;}
@@ -477 +577 @@
       int id;
 
-      UEdge(int _id) { id = _id;}
+      UEdge(int _id) : id(_id) {}
     public:
       UEdge() {}
-      UEdge (Invalid) { id = -1; }
+      UEdge(Invalid) : id(-1) {}
       bool operator==(const UEdge i) const {return id==i.id;}
       bool operator!=(const UEdge i) const {return id!=i.id;}
@@ -657 +757 @@
   /// \sa concept::BpUGraph.
   ///
-  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
+  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {
+  private:
+
+    /// \brief SmartBpUGraph is \e not copy constructible.
+    ///
+    ///SmartBpUGraph is \e not copy constructible.
+    SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {};
+
+    /// \brief Assignment of SmartBpUGraph to another one is \e not
+    /// allowed.
+    ///
+    /// Assignment of SmartBpUGraph to another one is \e not allowed.
+    void operator=(const SmartBpUGraph &) {}
+
+  public:
+
+    typedef ExtendedSmartBpUGraphBase Parent;
+
+    ///Constructor
+    
+    ///Constructor.
+    ///
+    SmartBpUGraph() : ExtendedSmartBpUGraphBase() {}
+
+    ///Add a new ANode to the graph.
+    
+    /// \return the new node.
+    ///
+    Node addANode() { return Parent::addANode(); }
+
+    ///Add a new BNode to the graph.
+    
+    /// \return the new node.
+    ///
+    Node addBNode() { return Parent::addBNode(); }
+    
+    ///Add a new undirected edge to the graph.
+    
+    ///Add a new undirected edge to the graph with node \c s
+    ///and \c t.
+    ///\return the new undirected edge.
+    UEdge addEdge(const Node& s, const Node& t) { 
+      return Parent::addEdge(s, t); 
+    }
+
+    ///Clear the graph.
+    
+    ///Erase all the nodes and edges from the graph.
+    ///
+    void clear() {
+      Parent::clear();
+    }
+    
+  public:
+
+    class Snapshot;
+
+  protected:
+    
+    void restoreSnapshot(const Snapshot &s)
+    {
+      while(s.edge_num<edges.size()) {
+        UEdge edge = uEdgeFromId(edges.size()-1);
+        Parent::getNotifier(UEdge()).erase(edge);
+        std::vector<Edge> dir;
+        dir.push_back(Parent::direct(edge, true));
+        dir.push_back(Parent::direct(edge, false));
+        Parent::getNotifier(Edge()).erase(dir);
+        aNodes[edges.back().aNode >> 1].first=edges.back().next_out;
+        bNodes[edges.back().bNode >> 1].first=edges.back().next_in;
+        edges.pop_back();
+      }
+      while(s.anode_num<aNodes.size()) {
+        Node node = fromANodeId(aNodes.size() - 1);
+        Parent::getNotifier(ANode()).erase(node);
+        Parent::getNotifier(Node()).erase(node);
+        aNodes.pop_back();
+      }
+      while(s.bnode_num<bNodes.size()) {
+        Node node = fromBNodeId(bNodes.size() - 1);
+        Parent::getNotifier(BNode()).erase(node);
+        Parent::getNotifier(Node()).erase(node);
+        bNodes.pop_back();
+      }
+    }    
+
+  public:
+
+    ///Class to make a snapshot of the graph and to restrore to it later.
+
+    ///Class to make a snapshot of the graph and to restrore to it later.
+    ///
+    ///The newly added nodes and edges can be removed using the
+    ///restore() function.
+    ///
+    ///\note After you restore a state, you cannot restore
+    ///a later state, in other word you cannot add again the edges deleted
+    ///by restore() using another one Snapshot instance.
+    ///
+    ///\warning If you do not use correctly the snapshot that can cause
+    ///either broken program, invalid state of the graph, valid but
+    ///not the restored graph or no change. Because the runtime performance
+    ///the validity of the snapshot is not stored.
+    class Snapshot 
+    {
+      SmartBpUGraph *g;
+    protected:
+      friend class SmartBpUGraph;
+      unsigned int anode_num;
+      unsigned int bnode_num;
+      unsigned int edge_num;
+    public:
+      ///Default constructor.
+      
+      ///Default constructor.
+      ///To actually make a snapshot you must call save().
+      ///
+      Snapshot() : g(0) {}
+
+      ///Constructor that immediately makes a snapshot
+      
+      ///This constructor immediately makes a snapshot of the graph.
+      ///\param _g The graph we make a snapshot of.
+      Snapshot(SmartBpUGraph &_g) : g(&_g) {
+        anode_num=g->aNodes.size();
+        bnode_num=g->bNodes.size();
+        edge_num=g->edges.size();
+      }
+
+      ///Make a snapshot.
+
+      ///Make a snapshot of the graph.
+      ///
+      ///This function can be called more than once. In case of a repeated
+      ///call, the previous snapshot gets lost.
+      ///\param _g The graph we make the snapshot of.
+      void save(SmartBpUGraph &_g) 
+      {
+        g=&_g;
+        anode_num=g->aNodes.size();
+        bnode_num=g->bNodes.size();
+        edge_num=g->edges.size();
+      }
+
+      ///Undo the changes until a snapshot.
+      
+      ///Undo the changes until a snapshot created by save().
+      ///
+      ///\note After you restored a state, you cannot restore
+      ///a later state, in other word you cannot add again the edges deleted
+      ///by restore().
+      void restore()
+      {
+        g->restoreSnapshot(*this);
+      }
+    };
+  };