diff -r 984870a2dde4 -r de2b77e3868c lemon/list_graph.h
--- a/lemon/list_graph.h	Mon Sep 04 11:05:21 2006 +0000
+++ b/lemon/list_graph.h	Mon Sep 04 11:08:32 2006 +0000
@@ -502,18 +502,9 @@
     /// The newly added nodes and edges can be removed using the
     /// restore() function.
     ///
-    /// \warning Edge and node deletions cannot be restored.
+    /// \warning Edge and node deletions cannot be restored. This
+    /// events invalidate the snapshot. 
     class Snapshot {
-    public:
-      
-      class UnsupportedOperation : public LogicError {
-      public:
-	virtual const char* what() const throw() {
-	  return "lemon::ListGraph::Snapshot::UnsupportedOperation";
-	}
-      };
-            
-
     protected:
 
       typedef Parent::NodeNotifier NodeNotifier;
@@ -543,7 +534,7 @@
         }
         virtual void erase(const std::vector<Node>& nodes) {
           for (int i = 0; i < (int)nodes.size(); ++i) {
-            if (!snapshot.eraseNode(nodes[i])) break;
+            snapshot.eraseNode(nodes[i]);
           }
         }
         virtual void build() {
@@ -561,7 +552,7 @@
           NodeNotifier* notifier = getNotifier();
           Node node;
           for (notifier->first(node); node != INVALID; notifier->next(node)) {
-            if (!snapshot.eraseNode(node)) break;
+            snapshot.eraseNode(node);
           }
         }
 
@@ -593,7 +584,7 @@
         }
         virtual void erase(const std::vector<Edge>& edges) {
           for (int i = 0; i < (int)edges.size(); ++i) {
-            if (!snapshot.eraseEdge(edges[i])) break;
+            snapshot.eraseEdge(edges[i]);
           }
         }
         virtual void build() {
@@ -611,7 +602,7 @@
           EdgeNotifier* notifier = getNotifier();
           Edge edge;
           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
-            if (!snapshot.eraseEdge(edge)) break;
+            snapshot.eraseEdge(edge);
           }
         }
 
@@ -630,30 +621,30 @@
       void addNode(const Node& node) {
         added_nodes.push_front(node);        
       }
-      bool eraseNode(const Node& node) {
+      void eraseNode(const Node& node) {
         std::list<Node>::iterator it = 
           std::find(added_nodes.begin(), added_nodes.end(), node);
         if (it == added_nodes.end()) {
           clear();
-          return false;
+          edge_observer_proxy.detach();
+          throw NodeNotifier::ImmediateDetach();
         } else {
           added_nodes.erase(it);
-          return true;
         }
       }
 
       void addEdge(const Edge& edge) {
         added_edges.push_front(edge);        
       }
-      bool eraseEdge(const Edge& edge) {
+      void eraseEdge(const Edge& edge) {
         std::list<Edge>::iterator it = 
           std::find(added_edges.begin(), added_edges.end(), edge);
         if (it == added_edges.end()) {
           clear();
-          return false;
+          node_observer_proxy.detach(); 
+          throw EdgeNotifier::ImmediateDetach();
         } else {
           added_edges.erase(it);
-          return true;
         }        
       }
 
@@ -668,8 +659,11 @@
 	edge_observer_proxy.detach();
       }
 
+      bool attached() const {
+        return node_observer_proxy.attached();
+      }
+
       void clear() {
-        detach();
         added_nodes.clear();
         added_edges.clear();        
       }
@@ -702,7 +696,10 @@
       /// call, the previous snapshot gets lost.
       /// \param _graph The graph we make the snapshot of.
       void save(ListGraph &_graph) {
-        clear();
+        if (attached()) {
+          detach();
+          clear();
+        }
         attach(_graph);
       }
       
@@ -711,21 +708,22 @@
       /// Undo the changes until the last snapshot created by save().
       void restore() {
 	detach();
-	while(!added_edges.empty()) {
-	  graph->erase(added_edges.front());
-	  added_edges.pop_front();
+	for(std::list<Edge>::iterator it = added_edges.begin(); 
+            it != added_edges.end(); ++it) {
+	  graph->erase(*it);
 	}
- 	while(!added_nodes.empty()) {
-	  graph->erase(added_nodes.front());
-	  added_nodes.pop_front();
+	for(std::list<Node>::iterator it = added_nodes.begin(); 
+            it != added_nodes.end(); ++it) {
+	  graph->erase(*it);
 	}
+        clear();
       }
 
       /// \brief Gives back true when the snapshot is valid.
       ///
       /// Gives back true when the snapshot is valid.
       bool valid() const {
-        return node_observer_proxy.attached();
+        return attached();
       }
     };
     
@@ -859,6 +857,241 @@
       }
       erase(b);
     }
+
+
+    /// \brief Class to make a snapshot of the graph and restore
+    /// to it later.
+    ///
+    /// Class to make a snapshot of the graph and to restore it
+    /// later.
+    ///
+    /// The newly added nodes and undirected edges can be removed
+    /// using the restore() function.
+    ///
+    /// \warning Edge and node deletions cannot be restored. This
+    /// events invalidate the snapshot. 
+    class Snapshot {
+    protected:
+
+      typedef Parent::NodeNotifier NodeNotifier;
+
+      class NodeObserverProxy : public NodeNotifier::ObserverBase {
+      public:
+
+        NodeObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using NodeNotifier::ObserverBase::attach;
+        using NodeNotifier::ObserverBase::detach;
+        using NodeNotifier::ObserverBase::attached;
+        
+      protected:
+        
+        virtual void add(const Node& node) {
+          snapshot.addNode(node);
+        }
+        virtual void add(const std::vector<Node>& nodes) {
+          for (int i = nodes.size() - 1; i >= 0; ++i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void erase(const Node& node) {
+          snapshot.eraseNode(node);
+        }
+        virtual void erase(const std::vector<Node>& nodes) {
+          for (int i = 0; i < (int)nodes.size(); ++i) {
+            snapshot.eraseNode(nodes[i]);
+          }
+        }
+        virtual void build() {
+          NodeNotifier* notifier = getNotifier();
+          Node node;
+          std::vector<Node> nodes;
+          for (notifier->first(node); node != INVALID; notifier->next(node)) {
+            nodes.push_back(node);
+          }
+          for (int i = nodes.size() - 1; i >= 0; --i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void clear() {
+          NodeNotifier* notifier = getNotifier();
+          Node node;
+          for (notifier->first(node); node != INVALID; notifier->next(node)) {
+            snapshot.eraseNode(node);
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+
+      class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
+      public:
+
+        UEdgeObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using UEdgeNotifier::ObserverBase::attach;
+        using UEdgeNotifier::ObserverBase::detach;
+        using UEdgeNotifier::ObserverBase::attached;
+        
+      protected:
+
+        virtual void add(const UEdge& edge) {
+          snapshot.addUEdge(edge);
+        }
+        virtual void add(const std::vector<UEdge>& edges) {
+          for (int i = edges.size() - 1; i >= 0; ++i) {
+            snapshot.addUEdge(edges[i]);
+          }
+        }
+        virtual void erase(const UEdge& edge) {
+          snapshot.eraseUEdge(edge);
+        }
+        virtual void erase(const std::vector<UEdge>& edges) {
+          for (int i = 0; i < (int)edges.size(); ++i) {
+            snapshot.eraseUEdge(edges[i]);
+          }
+        }
+        virtual void build() {
+          UEdgeNotifier* notifier = getNotifier();
+          UEdge edge;
+          std::vector<UEdge> edges;
+          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+            edges.push_back(edge);
+          }
+          for (int i = edges.size() - 1; i >= 0; --i) {
+            snapshot.addUEdge(edges[i]);
+          }
+        }
+        virtual void clear() {
+          UEdgeNotifier* notifier = getNotifier();
+          UEdge edge;
+          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+            snapshot.eraseUEdge(edge);
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+      
+      ListUGraph *graph;
+
+      NodeObserverProxy node_observer_proxy;
+      UEdgeObserverProxy edge_observer_proxy;
+
+      std::list<Node> added_nodes;
+      std::list<UEdge> added_edges;
+
+
+      void addNode(const Node& node) {
+        added_nodes.push_front(node);        
+      }
+      void eraseNode(const Node& node) {
+        std::list<Node>::iterator it = 
+          std::find(added_nodes.begin(), added_nodes.end(), node);
+        if (it == added_nodes.end()) {
+          clear();
+          edge_observer_proxy.detach();
+          throw NodeNotifier::ImmediateDetach();
+        } else {
+          added_nodes.erase(it);
+        }
+      }
+
+      void addUEdge(const UEdge& edge) {
+        added_edges.push_front(edge);        
+      }
+      void eraseUEdge(const UEdge& edge) {
+        std::list<UEdge>::iterator it = 
+          std::find(added_edges.begin(), added_edges.end(), edge);
+        if (it == added_edges.end()) {
+          clear();
+          node_observer_proxy.detach();
+          throw UEdgeNotifier::ImmediateDetach();
+        } else {
+          added_edges.erase(it);
+        }        
+      }
+
+      void attach(ListUGraph &_graph) {
+	graph = &_graph;
+	node_observer_proxy.attach(graph->getNotifier(Node()));
+        edge_observer_proxy.attach(graph->getNotifier(UEdge()));
+      }
+            
+      void detach() {
+	node_observer_proxy.detach();
+	edge_observer_proxy.detach();
+      }
+
+      bool attached() const {
+        return node_observer_proxy.attached();
+      }
+
+      void clear() {
+        added_nodes.clear();
+        added_edges.clear();        
+      }
+
+    public:
+
+      /// \brief Default constructor.
+      ///
+      /// Default constructor.
+      /// To actually make a snapshot you must call save().
+      Snapshot() 
+        : graph(0), node_observer_proxy(*this), 
+          edge_observer_proxy(*this) {}
+      
+      /// \brief Constructor that immediately makes a snapshot.
+      ///      
+      /// This constructor immediately makes a snapshot of the graph.
+      /// \param _graph The graph we make a snapshot of.
+      Snapshot(ListUGraph &_graph) 
+        : node_observer_proxy(*this), 
+          edge_observer_proxy(*this) {
+	attach(_graph);
+      }
+      
+      /// \brief 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 _graph The graph we make the snapshot of.
+      void save(ListUGraph &_graph) {
+        if (attached()) {
+          detach();
+          clear();
+        }
+        attach(_graph);
+      }
+      
+      /// \brief Undo the changes until the last snapshot.
+      // 
+      /// Undo the changes until the last snapshot created by save().
+      void restore() {
+	detach();
+	for(std::list<UEdge>::iterator it = added_edges.begin(); 
+            it != added_edges.end(); ++it) {
+	  graph->erase(*it);
+	}
+	for(std::list<Node>::iterator it = added_nodes.begin(); 
+            it != added_nodes.end(); ++it) {
+	  graph->erase(*it);
+	}
+        clear();
+      }
+
+      /// \brief Gives back true when the snapshot is valid.
+      ///
+      /// Gives back true when the snapshot is valid.
+      bool valid() const {
+        return attached();
+      }
+    };
   };
 
 
@@ -1105,6 +1338,7 @@
       } else {
         bNodes[bNodeId].next = -1;
       }
+      bNodes[bNodeId].prev = -1;
       first_bnode = bNodeId;
       bNodes[bNodeId].first_edge = -1;
       return Node((bNodeId << 1) + 1);
@@ -1148,7 +1382,8 @@
         if (aNodes[aNodeId].prev != -1) {
           aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
         } else {
-          first_anode = aNodes[aNodeId].next >> 1;
+          first_anode = 
+            aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1;
         }
         if (aNodes[aNodeId].next != -1) {
           aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
@@ -1160,7 +1395,8 @@
         if (bNodes[bNodeId].prev != -1) {
           bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
         } else {
-          first_bnode = bNodes[bNodeId].next >> 1;
+          first_bnode = 
+            bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1;
         }
         if (bNodes[bNodeId].next != -1) {
           bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
@@ -1396,6 +1632,239 @@
       erase(b);
     }
 
+    /// \brief Class to make a snapshot of the graph and restore
+    /// to it later.
+    ///
+    /// Class to make a snapshot of the graph and to restore it
+    /// later.
+    ///
+    /// The newly added nodes and undirected edges can be removed
+    /// using the restore() function.
+    ///
+    /// \warning Edge and node deletions cannot be restored. This
+    /// events invalidate the snapshot. 
+    class Snapshot {
+    protected:
+
+      typedef Parent::NodeNotifier NodeNotifier;
+
+      class NodeObserverProxy : public NodeNotifier::ObserverBase {
+      public:
+
+        NodeObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using NodeNotifier::ObserverBase::attach;
+        using NodeNotifier::ObserverBase::detach;
+        using NodeNotifier::ObserverBase::attached;
+        
+      protected:
+        
+        virtual void add(const Node& node) {
+          snapshot.addNode(node);
+        }
+        virtual void add(const std::vector<Node>& nodes) {
+          for (int i = nodes.size() - 1; i >= 0; ++i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void erase(const Node& node) {
+          snapshot.eraseNode(node);
+        }
+        virtual void erase(const std::vector<Node>& nodes) {
+          for (int i = 0; i < (int)nodes.size(); ++i) {
+            snapshot.eraseNode(nodes[i]);
+          }
+        }
+        virtual void build() {
+          NodeNotifier* notifier = getNotifier();
+          Node node;
+          std::vector<Node> nodes;
+          for (notifier->first(node); node != INVALID; notifier->next(node)) {
+            nodes.push_back(node);
+          }
+          for (int i = nodes.size() - 1; i >= 0; --i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void clear() {
+          NodeNotifier* notifier = getNotifier();
+          Node node;
+          for (notifier->first(node); node != INVALID; notifier->next(node)) {
+            snapshot.eraseNode(node);
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+
+      class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
+      public:
+
+        UEdgeObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using UEdgeNotifier::ObserverBase::attach;
+        using UEdgeNotifier::ObserverBase::detach;
+        using UEdgeNotifier::ObserverBase::attached;
+        
+      protected:
+
+        virtual void add(const UEdge& edge) {
+          snapshot.addUEdge(edge);
+        }
+        virtual void add(const std::vector<UEdge>& edges) {
+          for (int i = edges.size() - 1; i >= 0; ++i) {
+            snapshot.addUEdge(edges[i]);
+          }
+        }
+        virtual void erase(const UEdge& edge) {
+          snapshot.eraseUEdge(edge);
+        }
+        virtual void erase(const std::vector<UEdge>& edges) {
+          for (int i = 0; i < (int)edges.size(); ++i) {
+            snapshot.eraseUEdge(edges[i]);
+          }
+        }
+        virtual void build() {
+          UEdgeNotifier* notifier = getNotifier();
+          UEdge edge;
+          std::vector<UEdge> edges;
+          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+            edges.push_back(edge);
+          }
+          for (int i = edges.size() - 1; i >= 0; --i) {
+            snapshot.addUEdge(edges[i]);
+          }
+        }
+        virtual void clear() {
+          UEdgeNotifier* notifier = getNotifier();
+          UEdge edge;
+          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+            snapshot.eraseUEdge(edge);
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+      
+      ListBpUGraph *graph;
+
+      NodeObserverProxy node_observer_proxy;
+      UEdgeObserverProxy edge_observer_proxy;
+
+      std::list<Node> added_nodes;
+      std::list<UEdge> added_edges;
+
+
+      void addNode(const Node& node) {
+        added_nodes.push_front(node);        
+      }
+      void eraseNode(const Node& node) {
+        std::list<Node>::iterator it = 
+          std::find(added_nodes.begin(), added_nodes.end(), node);
+        if (it == added_nodes.end()) {
+          clear();
+          edge_observer_proxy.detach();
+          throw NodeNotifier::ImmediateDetach();
+        } else {
+          added_nodes.erase(it);
+        }
+      }
+
+      void addUEdge(const UEdge& edge) {
+        added_edges.push_front(edge);        
+      }
+      void eraseUEdge(const UEdge& edge) {
+        std::list<UEdge>::iterator it = 
+          std::find(added_edges.begin(), added_edges.end(), edge);
+        if (it == added_edges.end()) {
+          clear();
+          node_observer_proxy.detach();
+          throw UEdgeNotifier::ImmediateDetach();
+        } else {
+          added_edges.erase(it);
+        }        
+      }
+
+      void attach(ListBpUGraph &_graph) {
+	graph = &_graph;
+	node_observer_proxy.attach(graph->getNotifier(Node()));
+        edge_observer_proxy.attach(graph->getNotifier(UEdge()));
+      }
+            
+      void detach() {
+	node_observer_proxy.detach();
+	edge_observer_proxy.detach();
+      }
+
+      bool attached() const {
+        return node_observer_proxy.attached();
+      }
+
+      void clear() {
+        added_nodes.clear();
+        added_edges.clear();        
+      }
+
+    public:
+
+      /// \brief Default constructor.
+      ///
+      /// Default constructor.
+      /// To actually make a snapshot you must call save().
+      Snapshot() 
+        : graph(0), node_observer_proxy(*this), 
+          edge_observer_proxy(*this) {}
+      
+      /// \brief Constructor that immediately makes a snapshot.
+      ///      
+      /// This constructor immediately makes a snapshot of the graph.
+      /// \param _graph The graph we make a snapshot of.
+      Snapshot(ListBpUGraph &_graph) 
+        : node_observer_proxy(*this), 
+          edge_observer_proxy(*this) {
+	attach(_graph);
+      }
+      
+      /// \brief 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 _graph The graph we make the snapshot of.
+      void save(ListBpUGraph &_graph) {
+        if (attached()) {
+          detach();
+          clear();
+        }
+        attach(_graph);
+      }
+      
+      /// \brief Undo the changes until the last snapshot.
+      // 
+      /// Undo the changes until the last snapshot created by save().
+      void restore() {
+	detach();
+	for(std::list<UEdge>::iterator it = added_edges.begin(); 
+            it != added_edges.end(); ++it) {
+	  graph->erase(*it);
+	}
+	for(std::list<Node>::iterator it = added_nodes.begin(); 
+            it != added_nodes.end(); ++it) {
+	  graph->erase(*it);
+	}
+        clear();
+      }
+
+      /// \brief Gives back true when the snapshot is valid.
+      ///
+      /// Gives back true when the snapshot is valid.
+      bool valid() const {
+        return attached();
+      }
+    };
   };