lemon/smart_graph.h
changeset 132 50ff949140fa
child 125 19e82bda606a
equal deleted inserted replaced
-1:000000000000 0:9e0725a42c1d
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2008
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 #ifndef LEMON_SMART_GRAPH_H
       
    20 #define LEMON_SMART_GRAPH_H
       
    21 
       
    22 ///\ingroup graphs
       
    23 ///\file
       
    24 ///\brief SmartDigraph and SmartGraph classes.
       
    25 
       
    26 #include <vector>
       
    27 
       
    28 #include <lemon/bits/invalid.h>
       
    29 
       
    30 #include <lemon/bits/base_extender.h>
       
    31 #include <lemon/bits/graph_extender.h>
       
    32 
       
    33 #include <lemon/bits/utility.h>
       
    34 #include <lemon/error.h>
       
    35 
       
    36 #include <lemon/bits/graph_extender.h>
       
    37 
       
    38 namespace lemon {
       
    39 
       
    40   class SmartDigraph;
       
    41   ///Base of SmartDigraph
       
    42 
       
    43   ///Base of SmartDigraph
       
    44   ///
       
    45   class SmartDigraphBase {
       
    46   protected:
       
    47 
       
    48     struct NodeT 
       
    49     {
       
    50       int first_in, first_out;      
       
    51       NodeT() {}
       
    52     };
       
    53     struct ArcT 
       
    54     {
       
    55       int target, source, next_in, next_out;      
       
    56       ArcT() {}  
       
    57     };
       
    58 
       
    59     std::vector<NodeT> nodes;
       
    60     std::vector<ArcT> arcs;
       
    61         
       
    62   public:
       
    63 
       
    64     typedef SmartDigraphBase Graph;
       
    65 
       
    66     class Node;
       
    67     class Arc;
       
    68 
       
    69   public:
       
    70 
       
    71     SmartDigraphBase() : nodes(), arcs() { }
       
    72     SmartDigraphBase(const SmartDigraphBase &_g) 
       
    73       : nodes(_g.nodes), arcs(_g.arcs) { }
       
    74     
       
    75     typedef True NodeNumTag;
       
    76     typedef True ArcNumTag;
       
    77 
       
    78     int nodeNum() const { return nodes.size(); }
       
    79     int arcNum() const { return arcs.size(); }
       
    80 
       
    81     int maxNodeId() const { return nodes.size()-1; }
       
    82     int maxArcId() const { return arcs.size()-1; }
       
    83 
       
    84     Node addNode() {
       
    85       int n = nodes.size();     
       
    86       nodes.push_back(NodeT());
       
    87       nodes[n].first_in = -1;
       
    88       nodes[n].first_out = -1;
       
    89       return Node(n);
       
    90     }
       
    91     
       
    92     Arc addArc(Node u, Node v) {
       
    93       int n = arcs.size(); 
       
    94       arcs.push_back(ArcT());
       
    95       arcs[n].source = u._id; 
       
    96       arcs[n].target = v._id;
       
    97       arcs[n].next_out = nodes[u._id].first_out;
       
    98       arcs[n].next_in = nodes[v._id].first_in;
       
    99       nodes[u._id].first_out = nodes[v._id].first_in = n;
       
   100 
       
   101       return Arc(n);
       
   102     }
       
   103 
       
   104     void clear() {
       
   105       arcs.clear();
       
   106       nodes.clear();
       
   107     }
       
   108 
       
   109     Node source(Arc a) const { return Node(arcs[a._id].source); }
       
   110     Node target(Arc a) const { return Node(arcs[a._id].target); }
       
   111 
       
   112     static int id(Node v) { return v._id; }
       
   113     static int id(Arc a) { return a._id; }
       
   114 
       
   115     static Node nodeFromId(int id) { return Node(id);}
       
   116     static Arc arcFromId(int id) { return Arc(id);}
       
   117 
       
   118     class Node {
       
   119       friend class SmartDigraphBase;
       
   120       friend class SmartDigraph;
       
   121 
       
   122     protected:
       
   123       int _id;
       
   124       explicit Node(int id) : _id(id) {}
       
   125     public:
       
   126       Node() {}
       
   127       Node (Invalid) : _id(-1) {}
       
   128       bool operator==(const Node i) const {return _id == i._id;}
       
   129       bool operator!=(const Node i) const {return _id != i._id;}
       
   130       bool operator<(const Node i) const {return _id < i._id;}
       
   131     };
       
   132     
       
   133 
       
   134     class Arc {
       
   135       friend class SmartDigraphBase;
       
   136       friend class SmartDigraph;
       
   137 
       
   138     protected:
       
   139       int _id;
       
   140       explicit Arc(int id) : _id(id) {}
       
   141     public:
       
   142       Arc() { }
       
   143       Arc (Invalid) : _id(-1) {}
       
   144       bool operator==(const Arc i) const {return _id == i._id;}
       
   145       bool operator!=(const Arc i) const {return _id != i._id;}
       
   146       bool operator<(const Arc i) const {return _id < i._id;}
       
   147     };
       
   148 
       
   149     void first(Node& node) const {
       
   150       node._id = nodes.size() - 1;
       
   151     }
       
   152 
       
   153     static void next(Node& node) {
       
   154       --node._id;
       
   155     }
       
   156 
       
   157     void first(Arc& arc) const {
       
   158       arc._id = arcs.size() - 1;
       
   159     }
       
   160 
       
   161     static void next(Arc& arc) {
       
   162       --arc._id;
       
   163     }
       
   164 
       
   165     void firstOut(Arc& arc, const Node& node) const {
       
   166       arc._id = nodes[node._id].first_out;
       
   167     }
       
   168 
       
   169     void nextOut(Arc& arc) const {
       
   170       arc._id = arcs[arc._id].next_out;
       
   171     }
       
   172 
       
   173     void firstIn(Arc& arc, const Node& node) const {
       
   174       arc._id = nodes[node._id].first_in;
       
   175     }
       
   176     
       
   177     void nextIn(Arc& arc) const {
       
   178       arc._id = arcs[arc._id].next_in;
       
   179     }
       
   180 
       
   181   };
       
   182 
       
   183   typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
       
   184 
       
   185   ///\ingroup graphs
       
   186   ///
       
   187   ///\brief A smart directed graph class.
       
   188   ///
       
   189   ///This is a simple and fast digraph implementation.
       
   190   ///It is also quite memory efficient, but at the price
       
   191   ///that <b> it does support only limited (only stack-like)
       
   192   ///node and arc deletions</b>.
       
   193   ///It conforms to the \ref concepts::Digraph "Digraph concept" with
       
   194   ///an important extra feature that its maps are real \ref
       
   195   ///concepts::ReferenceMap "reference map"s.
       
   196   ///
       
   197   ///\sa concepts::Digraph.
       
   198   ///
       
   199   ///\author Alpar Juttner
       
   200   class SmartDigraph : public ExtendedSmartDigraphBase {
       
   201   public:
       
   202 
       
   203     typedef ExtendedSmartDigraphBase Parent;
       
   204 
       
   205   private:
       
   206 
       
   207     ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
       
   208 
       
   209     ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
       
   210     ///
       
   211     SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
       
   212     ///\brief Assignment of SmartDigraph to another one is \e not allowed.
       
   213     ///Use DigraphCopy() instead.
       
   214 
       
   215     ///Assignment of SmartDigraph to another one is \e not allowed.
       
   216     ///Use DigraphCopy() instead.
       
   217     void operator=(const SmartDigraph &) {}
       
   218 
       
   219   public:
       
   220     
       
   221     /// Constructor
       
   222     
       
   223     /// Constructor.
       
   224     ///
       
   225     SmartDigraph() {};
       
   226     
       
   227     ///Add a new node to the digraph.
       
   228     
       
   229     /// \return the new node.
       
   230     ///
       
   231     Node addNode() { return Parent::addNode(); }
       
   232     
       
   233     ///Add a new arc to the digraph.
       
   234     
       
   235     ///Add a new arc to the digraph with source node \c s
       
   236     ///and target node \c t.
       
   237     ///\return the new arc.
       
   238     Arc addArc(const Node& s, const Node& t) { 
       
   239       return Parent::addArc(s, t); 
       
   240     }
       
   241 
       
   242     /// \brief Using this it is possible to avoid the superfluous memory
       
   243     /// allocation.
       
   244 
       
   245     /// Using this it is possible to avoid the superfluous memory
       
   246     /// allocation: if you know that the digraph you want to build will
       
   247     /// be very large (e.g. it will contain millions of nodes and/or arcs)
       
   248     /// then it is worth reserving space for this amount before starting
       
   249     /// to build the digraph.
       
   250     /// \sa reserveArc
       
   251     void reserveNode(int n) { nodes.reserve(n); };
       
   252 
       
   253     /// \brief Using this it is possible to avoid the superfluous memory
       
   254     /// allocation.
       
   255 
       
   256     /// Using this it is possible to avoid the superfluous memory
       
   257     /// allocation: if you know that the digraph you want to build will
       
   258     /// be very large (e.g. it will contain millions of nodes and/or arcs)
       
   259     /// then it is worth reserving space for this amount before starting
       
   260     /// to build the digraph.
       
   261     /// \sa reserveNode
       
   262     void reserveArc(int m) { arcs.reserve(m); };
       
   263 
       
   264     ///Clear the digraph.
       
   265     
       
   266     ///Erase all the nodes and arcs from the digraph.
       
   267     ///
       
   268     void clear() {
       
   269       Parent::clear();
       
   270     }
       
   271 
       
   272     ///Split a node.
       
   273     
       
   274     ///This function splits a node. First a new node is added to the digraph,
       
   275     ///then the source of each outgoing arc of \c n is moved to this new node.
       
   276     ///If \c connect is \c true (this is the default value), then a new arc
       
   277     ///from \c n to the newly created node is also added.
       
   278     ///\return The newly created node.
       
   279     ///
       
   280     ///\note The <tt>Arc</tt>s
       
   281     ///referencing a moved arc remain
       
   282     ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
       
   283     ///may be invalidated.
       
   284     ///\warning This functionality cannot be used together with the Snapshot
       
   285     ///feature.
       
   286     ///\todo It could be implemented in a bit faster way.
       
   287     Node split(Node n, bool connect = true)
       
   288     {
       
   289       Node b = addNode();
       
   290       nodes[b._id].first_out=nodes[n._id].first_out;
       
   291       nodes[n._id].first_out=-1;
       
   292       for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
       
   293       if(connect) addArc(n,b);
       
   294       return b;
       
   295     }
       
   296 
       
   297   public:
       
   298     
       
   299     class Snapshot;
       
   300 
       
   301   protected:
       
   302 
       
   303     void restoreSnapshot(const Snapshot &s)
       
   304     {
       
   305       while(s.arc_num<arcs.size()) {
       
   306         Arc arc = arcFromId(arcs.size()-1);
       
   307 	Parent::notifier(Arc()).erase(arc);
       
   308 	nodes[arcs.back().source].first_out=arcs.back().next_out;
       
   309 	nodes[arcs.back().target].first_in=arcs.back().next_in;
       
   310 	arcs.pop_back();
       
   311       }
       
   312       while(s.node_num<nodes.size()) {
       
   313         Node node = nodeFromId(nodes.size()-1);
       
   314 	Parent::notifier(Node()).erase(node);
       
   315 	nodes.pop_back();
       
   316       }
       
   317     }    
       
   318 
       
   319   public:
       
   320 
       
   321     ///Class to make a snapshot of the digraph and to restrore to it later.
       
   322 
       
   323     ///Class to make a snapshot of the digraph and to restrore to it later.
       
   324     ///
       
   325     ///The newly added nodes and arcs can be removed using the
       
   326     ///restore() function.
       
   327     ///\note After you restore a state, you cannot restore
       
   328     ///a later state, in other word you cannot add again the arcs deleted
       
   329     ///by restore() using another one Snapshot instance.
       
   330     ///
       
   331     ///\warning If you do not use correctly the snapshot that can cause
       
   332     ///either broken program, invalid state of the digraph, valid but
       
   333     ///not the restored digraph or no change. Because the runtime performance
       
   334     ///the validity of the snapshot is not stored.
       
   335     class Snapshot 
       
   336     {
       
   337       SmartDigraph *_graph;
       
   338     protected:
       
   339       friend class SmartDigraph;
       
   340       unsigned int node_num;
       
   341       unsigned int arc_num;
       
   342     public:
       
   343       ///Default constructor.
       
   344       
       
   345       ///Default constructor.
       
   346       ///To actually make a snapshot you must call save().
       
   347       ///
       
   348       Snapshot() : _graph(0) {}
       
   349       ///Constructor that immediately makes a snapshot
       
   350       
       
   351       ///This constructor immediately makes a snapshot of the digraph.
       
   352       ///\param _g The digraph we make a snapshot of.
       
   353       Snapshot(SmartDigraph &graph) : _graph(&graph) {
       
   354 	node_num=_graph->nodes.size();
       
   355 	arc_num=_graph->arcs.size();
       
   356       }
       
   357 
       
   358       ///Make a snapshot.
       
   359 
       
   360       ///Make a snapshot of the digraph.
       
   361       ///
       
   362       ///This function can be called more than once. In case of a repeated
       
   363       ///call, the previous snapshot gets lost.
       
   364       ///\param _g The digraph we make the snapshot of.
       
   365       void save(SmartDigraph &graph) 
       
   366       {
       
   367 	_graph=&graph;
       
   368 	node_num=_graph->nodes.size();
       
   369 	arc_num=_graph->arcs.size();
       
   370       }
       
   371 
       
   372       ///Undo the changes until a snapshot.
       
   373       
       
   374       ///Undo the changes until a snapshot created by save().
       
   375       ///
       
   376       ///\note After you restored a state, you cannot restore
       
   377       ///a later state, in other word you cannot add again the arcs deleted
       
   378       ///by restore().
       
   379       void restore()
       
   380       {
       
   381 	_graph->restoreSnapshot(*this);
       
   382       }
       
   383     };
       
   384   };
       
   385 
       
   386 
       
   387   class SmartGraphBase {
       
   388 
       
   389   protected:
       
   390 
       
   391     struct NodeT {
       
   392       int first_out;
       
   393     };
       
   394  
       
   395     struct ArcT {
       
   396       int target;
       
   397       int next_out;
       
   398     };
       
   399 
       
   400     std::vector<NodeT> nodes;
       
   401     std::vector<ArcT> arcs;
       
   402 
       
   403     int first_free_arc;
       
   404     
       
   405   public:
       
   406     
       
   407     typedef SmartGraphBase Digraph;
       
   408 
       
   409     class Node;
       
   410     class Arc;
       
   411     class Edge;
       
   412     
       
   413     class Node {
       
   414       friend class SmartGraphBase;
       
   415     protected:
       
   416 
       
   417       int _id;
       
   418       explicit Node(int id) { _id = id;}
       
   419 
       
   420     public:
       
   421       Node() {}
       
   422       Node (Invalid) { _id = -1; }
       
   423       bool operator==(const Node& node) const {return _id == node._id;}
       
   424       bool operator!=(const Node& node) const {return _id != node._id;}
       
   425       bool operator<(const Node& node) const {return _id < node._id;}
       
   426     };
       
   427 
       
   428     class Edge {
       
   429       friend class SmartGraphBase;
       
   430     protected:
       
   431 
       
   432       int _id;
       
   433       explicit Edge(int id) { _id = id;}
       
   434 
       
   435     public:
       
   436       Edge() {}
       
   437       Edge (Invalid) { _id = -1; }
       
   438       bool operator==(const Edge& arc) const {return _id == arc._id;}
       
   439       bool operator!=(const Edge& arc) const {return _id != arc._id;}
       
   440       bool operator<(const Edge& arc) const {return _id < arc._id;}
       
   441     };
       
   442 
       
   443     class Arc {
       
   444       friend class SmartGraphBase;
       
   445     protected:
       
   446 
       
   447       int _id;
       
   448       explicit Arc(int id) { _id = id;}
       
   449 
       
   450     public:
       
   451       operator Edge() const { return edgeFromId(_id / 2); }
       
   452 
       
   453       Arc() {}
       
   454       Arc (Invalid) { _id = -1; }
       
   455       bool operator==(const Arc& arc) const {return _id == arc._id;}
       
   456       bool operator!=(const Arc& arc) const {return _id != arc._id;}
       
   457       bool operator<(const Arc& arc) const {return _id < arc._id;}
       
   458     };
       
   459 
       
   460 
       
   461 
       
   462     SmartGraphBase()
       
   463       : nodes(), arcs() {}
       
   464 
       
   465     
       
   466     int maxNodeId() const { return nodes.size()-1; } 
       
   467     int maxEdgeId() const { return arcs.size() / 2 - 1; }
       
   468     int maxArcId() const { return arcs.size()-1; }
       
   469 
       
   470     Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
       
   471     Node target(Arc e) const { return Node(arcs[e._id].target); }
       
   472 
       
   473     Node source(Edge e) const { return Node(arcs[2 * e._id].target); }
       
   474     Node target(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
       
   475 
       
   476     static bool direction(Arc e) {
       
   477       return (e._id & 1) == 1;
       
   478     }
       
   479 
       
   480     static Arc direct(Edge e, bool d) {
       
   481       return Arc(e._id * 2 + (d ? 1 : 0));
       
   482     }
       
   483 
       
   484     void first(Node& node) const { 
       
   485       node._id = nodes.size() - 1;
       
   486     }
       
   487 
       
   488     void next(Node& node) const {
       
   489       --node._id;
       
   490     }
       
   491 
       
   492     void first(Arc& arc) const { 
       
   493       arc._id = arcs.size() - 1;
       
   494     }
       
   495 
       
   496     void next(Arc& arc) const {
       
   497       --arc._id;
       
   498     }
       
   499 
       
   500     void first(Edge& arc) const { 
       
   501       arc._id = arcs.size() / 2 - 1;
       
   502     }
       
   503 
       
   504     void next(Edge& arc) const {
       
   505       --arc._id;
       
   506     }
       
   507 
       
   508     void firstOut(Arc &arc, const Node& v) const {
       
   509       arc._id = nodes[v._id].first_out;
       
   510     }
       
   511     void nextOut(Arc &arc) const {
       
   512       arc._id = arcs[arc._id].next_out;
       
   513     }
       
   514 
       
   515     void firstIn(Arc &arc, const Node& v) const {
       
   516       arc._id = ((nodes[v._id].first_out) ^ 1);
       
   517       if (arc._id == -2) arc._id = -1;
       
   518     }
       
   519     void nextIn(Arc &arc) const {
       
   520       arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
       
   521       if (arc._id == -2) arc._id = -1;
       
   522     }
       
   523 
       
   524     void firstInc(Edge &arc, bool& d, const Node& v) const {
       
   525       int de = nodes[v._id].first_out;
       
   526       if (de != -1) {
       
   527         arc._id = de / 2;
       
   528         d = ((de & 1) == 1);
       
   529       } else {
       
   530         arc._id = -1;
       
   531         d = true;
       
   532       }
       
   533     }
       
   534     void nextInc(Edge &arc, bool& d) const {
       
   535       int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
       
   536       if (de != -1) {
       
   537         arc._id = de / 2;
       
   538         d = ((de & 1) == 1);
       
   539       } else {
       
   540         arc._id = -1;
       
   541         d = true;      
       
   542       }
       
   543     }
       
   544     
       
   545     static int id(Node v) { return v._id; }
       
   546     static int id(Arc e) { return e._id; }
       
   547     static int id(Edge e) { return e._id; }
       
   548 
       
   549     static Node nodeFromId(int id) { return Node(id);}
       
   550     static Arc arcFromId(int id) { return Arc(id);}
       
   551     static Edge edgeFromId(int id) { return Edge(id);}
       
   552 
       
   553     Node addNode() {     
       
   554       int n = nodes.size();
       
   555       nodes.push_back(NodeT());
       
   556       nodes[n].first_out = -1;
       
   557       
       
   558       return Node(n);
       
   559     }
       
   560     
       
   561     Edge addArc(Node u, Node v) {
       
   562       int n = arcs.size();
       
   563       arcs.push_back(ArcT());
       
   564       arcs.push_back(ArcT());
       
   565       
       
   566       arcs[n].target = u._id;
       
   567       arcs[n | 1].target = v._id;
       
   568 
       
   569       arcs[n].next_out = nodes[v._id].first_out;
       
   570       nodes[v._id].first_out = n;
       
   571 
       
   572       arcs[n | 1].next_out = nodes[u._id].first_out;	
       
   573       nodes[u._id].first_out = (n | 1);
       
   574 
       
   575       return Edge(n / 2);
       
   576     }
       
   577     
       
   578     void clear() {
       
   579       arcs.clear();
       
   580       nodes.clear();
       
   581     }
       
   582 
       
   583   };
       
   584 
       
   585   typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
       
   586 
       
   587   /// \ingroup graphs
       
   588   ///
       
   589   /// \brief A smart undirected graph class.
       
   590   ///
       
   591   /// This is a simple and fast graph implementation.
       
   592   /// It is also quite memory efficient, but at the price
       
   593   /// that <b> it does support only limited (only stack-like)
       
   594   /// node and arc deletions</b>.
       
   595   /// Except from this it conforms to 
       
   596   /// the \ref concepts::Graph "Graph concept".
       
   597   ///
       
   598   /// It also has an
       
   599   /// important extra feature that
       
   600   /// its maps are real \ref concepts::ReferenceMap "reference map"s.
       
   601   ///
       
   602   /// \sa concepts::Graph.
       
   603   ///
       
   604   class SmartGraph : public ExtendedSmartGraphBase {
       
   605   private:
       
   606 
       
   607     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
       
   608 
       
   609     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
       
   610     ///
       
   611     SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
       
   612 
       
   613     ///\brief Assignment of SmartGraph to another one is \e not allowed.
       
   614     ///Use GraphCopy() instead.
       
   615 
       
   616     ///Assignment of SmartGraph to another one is \e not allowed.
       
   617     ///Use GraphCopy() instead.
       
   618     void operator=(const SmartGraph &) {}
       
   619 
       
   620   public:
       
   621 
       
   622     typedef ExtendedSmartGraphBase Parent;
       
   623 
       
   624     /// Constructor
       
   625     
       
   626     /// Constructor.
       
   627     ///
       
   628     SmartGraph() {}
       
   629 
       
   630     ///Add a new node to the graph.
       
   631     
       
   632     /// \return the new node.
       
   633     ///
       
   634     Node addNode() { return Parent::addNode(); }
       
   635     
       
   636     ///Add a new edge to the graph.
       
   637     
       
   638     ///Add a new edge to the graph with node \c s
       
   639     ///and \c t.
       
   640     ///\return the new edge.
       
   641     Edge addEdge(const Node& s, const Node& t) { 
       
   642       return Parent::addArc(s, t); 
       
   643     }
       
   644 
       
   645     ///Clear the graph.
       
   646     
       
   647     ///Erase all the nodes and edges from the graph.
       
   648     ///
       
   649     void clear() {
       
   650       Parent::clear();
       
   651     }
       
   652 
       
   653   public:
       
   654     
       
   655     class Snapshot;
       
   656 
       
   657   protected:
       
   658 
       
   659     void saveSnapshot(Snapshot &s)
       
   660     {
       
   661       s._graph = this;
       
   662       s.node_num = nodes.size();
       
   663       s.arc_num = arcs.size();
       
   664     }
       
   665 
       
   666     void restoreSnapshot(const Snapshot &s)
       
   667     {
       
   668       while(s.arc_num<arcs.size()) {
       
   669         int n=arcs.size()-1;
       
   670         Edge arc=edgeFromId(n/2);
       
   671 	Parent::notifier(Edge()).erase(arc);
       
   672         std::vector<Arc> dir;
       
   673         dir.push_back(arcFromId(n));
       
   674         dir.push_back(arcFromId(n-1));
       
   675 	Parent::notifier(Arc()).erase(dir);
       
   676 	nodes[arcs[n].target].first_out=arcs[n].next_out;
       
   677 	nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
       
   678 	arcs.pop_back();
       
   679 	arcs.pop_back();
       
   680       }
       
   681       while(s.node_num<nodes.size()) {
       
   682         int n=nodes.size()-1;
       
   683         Node node = nodeFromId(n);
       
   684 	Parent::notifier(Node()).erase(node);
       
   685 	nodes.pop_back();
       
   686       }
       
   687     }    
       
   688 
       
   689   public:
       
   690 
       
   691     ///Class to make a snapshot of the digraph and to restrore to it later.
       
   692 
       
   693     ///Class to make a snapshot of the digraph and to restrore to it later.
       
   694     ///
       
   695     ///The newly added nodes and arcs can be removed using the
       
   696     ///restore() function.
       
   697     ///
       
   698     ///\note After you restore a state, you cannot restore
       
   699     ///a later state, in other word you cannot add again the arcs deleted
       
   700     ///by restore() using another one Snapshot instance.
       
   701     ///
       
   702     ///\warning If you do not use correctly the snapshot that can cause
       
   703     ///either broken program, invalid state of the digraph, valid but
       
   704     ///not the restored digraph or no change. Because the runtime performance
       
   705     ///the validity of the snapshot is not stored.
       
   706     class Snapshot 
       
   707     {
       
   708       SmartGraph *_graph;
       
   709     protected:
       
   710       friend class SmartGraph;
       
   711       unsigned int node_num;
       
   712       unsigned int arc_num;
       
   713     public:
       
   714       ///Default constructor.
       
   715       
       
   716       ///Default constructor.
       
   717       ///To actually make a snapshot you must call save().
       
   718       ///
       
   719       Snapshot() : _graph(0) {}
       
   720       ///Constructor that immediately makes a snapshot
       
   721       
       
   722       ///This constructor immediately makes a snapshot of the digraph.
       
   723       ///\param g The digraph we make a snapshot of.
       
   724       Snapshot(SmartGraph &graph) {
       
   725         graph.saveSnapshot(*this);
       
   726       }
       
   727 
       
   728       ///Make a snapshot.
       
   729 
       
   730       ///Make a snapshot of the graph.
       
   731       ///
       
   732       ///This function can be called more than once. In case of a repeated
       
   733       ///call, the previous snapshot gets lost.
       
   734       ///\param g The digraph we make the snapshot of.
       
   735       void save(SmartGraph &graph) 
       
   736       {
       
   737         graph.saveSnapshot(*this);
       
   738       }
       
   739 
       
   740       ///Undo the changes until a snapshot.
       
   741       
       
   742       ///Undo the changes until a snapshot created by save().
       
   743       ///
       
   744       ///\note After you restored a state, you cannot restore
       
   745       ///a later state, in other word you cannot add again the arcs deleted
       
   746       ///by restore().
       
   747       void restore()
       
   748       {
       
   749         _graph->restoreSnapshot(*this);
       
   750       }
       
   751     };
       
   752   };
       
   753   
       
   754 } //namespace lemon
       
   755 
       
   756 
       
   757 #endif //LEMON_SMART_GRAPH_H