lemon/smart_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Mon, 14 Jul 2008 19:06:29 +0200
changeset 218 0d6511647639
parent 157 2ccc1afc2c52
child 220 a5d8c039f218
permissions -rw-r--r--
Bug fix in assert.h (ticket #125)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     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 EdgeNumTag;
    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     bool valid(Node n) const {
   119       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
   120     }
   121     bool valid(Arc a) const {
   122       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
   123     }
   124 
   125     class Node {
   126       friend class SmartDigraphBase;
   127       friend class SmartDigraph;
   128 
   129     protected:
   130       int _id;
   131       explicit Node(int id) : _id(id) {}
   132     public:
   133       Node() {}
   134       Node (Invalid) : _id(-1) {}
   135       bool operator==(const Node i) const {return _id == i._id;}
   136       bool operator!=(const Node i) const {return _id != i._id;}
   137       bool operator<(const Node i) const {return _id < i._id;}
   138     };
   139 
   140 
   141     class Arc {
   142       friend class SmartDigraphBase;
   143       friend class SmartDigraph;
   144 
   145     protected:
   146       int _id;
   147       explicit Arc(int id) : _id(id) {}
   148     public:
   149       Arc() { }
   150       Arc (Invalid) : _id(-1) {}
   151       bool operator==(const Arc i) const {return _id == i._id;}
   152       bool operator!=(const Arc i) const {return _id != i._id;}
   153       bool operator<(const Arc i) const {return _id < i._id;}
   154     };
   155 
   156     void first(Node& node) const {
   157       node._id = nodes.size() - 1;
   158     }
   159 
   160     static void next(Node& node) {
   161       --node._id;
   162     }
   163 
   164     void first(Arc& arc) const {
   165       arc._id = arcs.size() - 1;
   166     }
   167 
   168     static void next(Arc& arc) {
   169       --arc._id;
   170     }
   171 
   172     void firstOut(Arc& arc, const Node& node) const {
   173       arc._id = nodes[node._id].first_out;
   174     }
   175 
   176     void nextOut(Arc& arc) const {
   177       arc._id = arcs[arc._id].next_out;
   178     }
   179 
   180     void firstIn(Arc& arc, const Node& node) const {
   181       arc._id = nodes[node._id].first_in;
   182     }
   183 
   184     void nextIn(Arc& arc) const {
   185       arc._id = arcs[arc._id].next_in;
   186     }
   187 
   188   };
   189 
   190   typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
   191 
   192   ///\ingroup graphs
   193   ///
   194   ///\brief A smart directed graph class.
   195   ///
   196   ///This is a simple and fast digraph implementation.
   197   ///It is also quite memory efficient, but at the price
   198   ///that <b> it does support only limited (only stack-like)
   199   ///node and arc deletions</b>.
   200   ///It conforms to the \ref concepts::Digraph "Digraph concept" with
   201   ///an important extra feature that its maps are real \ref
   202   ///concepts::ReferenceMap "reference map"s.
   203   ///
   204   ///\sa concepts::Digraph.
   205   class SmartDigraph : public ExtendedSmartDigraphBase {
   206   public:
   207 
   208     typedef ExtendedSmartDigraphBase Parent;
   209 
   210   private:
   211 
   212     ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
   213 
   214     ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
   215     ///
   216     SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
   217     ///\brief Assignment of SmartDigraph to another one is \e not allowed.
   218     ///Use DigraphCopy() instead.
   219 
   220     ///Assignment of SmartDigraph to another one is \e not allowed.
   221     ///Use DigraphCopy() instead.
   222     void operator=(const SmartDigraph &) {}
   223 
   224   public:
   225 
   226     /// Constructor
   227 
   228     /// Constructor.
   229     ///
   230     SmartDigraph() {};
   231 
   232     ///Add a new node to the digraph.
   233 
   234     /// \return the new node.
   235     ///
   236     Node addNode() { return Parent::addNode(); }
   237 
   238     ///Add a new arc to the digraph.
   239 
   240     ///Add a new arc to the digraph with source node \c s
   241     ///and target node \c t.
   242     ///\return the new arc.
   243     Arc addArc(const Node& s, const Node& t) {
   244       return Parent::addArc(s, t);
   245     }
   246 
   247     /// \brief Using this it is possible to avoid the superfluous memory
   248     /// allocation.
   249 
   250     /// Using this it is possible to avoid the superfluous memory
   251     /// allocation: if you know that the digraph you want to build will
   252     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   253     /// then it is worth reserving space for this amount before starting
   254     /// to build the digraph.
   255     /// \sa reserveArc
   256     void reserveNode(int n) { nodes.reserve(n); };
   257 
   258     /// \brief Using this it is possible to avoid the superfluous memory
   259     /// allocation.
   260 
   261     /// Using this it is possible to avoid the superfluous memory
   262     /// allocation: if you know that the digraph you want to build will
   263     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   264     /// then it is worth reserving space for this amount before starting
   265     /// to build the digraph.
   266     /// \sa reserveNode
   267     void reserveArc(int m) { arcs.reserve(m); };
   268 
   269     /// \brief Node validity check
   270     ///
   271     /// This function gives back true if the given node is valid,
   272     /// ie. it is a real node of the graph.
   273     ///
   274     /// \warning A removed node (using Snapshot) could become valid again
   275     /// when new nodes are added to the graph.
   276     bool valid(Node n) const { return Parent::valid(n); }
   277 
   278     /// \brief Arc validity check
   279     ///
   280     /// This function gives back true if the given arc is valid,
   281     /// ie. it is a real arc of the graph.
   282     ///
   283     /// \warning A removed arc (using Snapshot) could become valid again
   284     /// when new arcs are added to the graph.
   285     bool valid(Arc a) const { return Parent::valid(a); }
   286 
   287     ///Clear the digraph.
   288 
   289     ///Erase all the nodes and arcs from the digraph.
   290     ///
   291     void clear() {
   292       Parent::clear();
   293     }
   294 
   295     ///Split a node.
   296 
   297     ///This function splits a node. First a new node is added to the digraph,
   298     ///then the source of each outgoing arc of \c n is moved to this new node.
   299     ///If \c connect is \c true (this is the default value), then a new arc
   300     ///from \c n to the newly created node is also added.
   301     ///\return The newly created node.
   302     ///
   303     ///\note The <tt>Arc</tt>s
   304     ///referencing a moved arc remain
   305     ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
   306     ///may be invalidated.
   307     ///\warning This functionality cannot be used together with the Snapshot
   308     ///feature.
   309     ///\todo It could be implemented in a bit faster way.
   310     Node split(Node n, bool connect = true)
   311     {
   312       Node b = addNode();
   313       nodes[b._id].first_out=nodes[n._id].first_out;
   314       nodes[n._id].first_out=-1;
   315       for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
   316       if(connect) addArc(n,b);
   317       return b;
   318     }
   319 
   320   public:
   321 
   322     class Snapshot;
   323 
   324   protected:
   325 
   326     void restoreSnapshot(const Snapshot &s)
   327     {
   328       while(s.arc_num<arcs.size()) {
   329         Arc arc = arcFromId(arcs.size()-1);
   330         Parent::notifier(Arc()).erase(arc);
   331         nodes[arcs.back().source].first_out=arcs.back().next_out;
   332         nodes[arcs.back().target].first_in=arcs.back().next_in;
   333         arcs.pop_back();
   334       }
   335       while(s.node_num<nodes.size()) {
   336         Node node = nodeFromId(nodes.size()-1);
   337         Parent::notifier(Node()).erase(node);
   338         nodes.pop_back();
   339       }
   340     }
   341 
   342   public:
   343 
   344     ///Class to make a snapshot of the digraph and to restrore to it later.
   345 
   346     ///Class to make a snapshot of the digraph and to restrore to it later.
   347     ///
   348     ///The newly added nodes and arcs can be removed using the
   349     ///restore() function.
   350     ///\note After you restore a state, you cannot restore
   351     ///a later state, in other word you cannot add again the arcs deleted
   352     ///by restore() using another one Snapshot instance.
   353     ///
   354     ///\warning If you do not use correctly the snapshot that can cause
   355     ///either broken program, invalid state of the digraph, valid but
   356     ///not the restored digraph or no change. Because the runtime performance
   357     ///the validity of the snapshot is not stored.
   358     class Snapshot
   359     {
   360       SmartDigraph *_graph;
   361     protected:
   362       friend class SmartDigraph;
   363       unsigned int node_num;
   364       unsigned int arc_num;
   365     public:
   366       ///Default constructor.
   367 
   368       ///Default constructor.
   369       ///To actually make a snapshot you must call save().
   370       ///
   371       Snapshot() : _graph(0) {}
   372       ///Constructor that immediately makes a snapshot
   373 
   374       ///This constructor immediately makes a snapshot of the digraph.
   375       ///\param _g The digraph we make a snapshot of.
   376       Snapshot(SmartDigraph &graph) : _graph(&graph) {
   377         node_num=_graph->nodes.size();
   378         arc_num=_graph->arcs.size();
   379       }
   380 
   381       ///Make a snapshot.
   382 
   383       ///Make a snapshot of the digraph.
   384       ///
   385       ///This function can be called more than once. In case of a repeated
   386       ///call, the previous snapshot gets lost.
   387       ///\param _g The digraph we make the snapshot of.
   388       void save(SmartDigraph &graph)
   389       {
   390         _graph=&graph;
   391         node_num=_graph->nodes.size();
   392         arc_num=_graph->arcs.size();
   393       }
   394 
   395       ///Undo the changes until a snapshot.
   396 
   397       ///Undo the changes until a snapshot created by save().
   398       ///
   399       ///\note After you restored a state, you cannot restore
   400       ///a later state, in other word you cannot add again the arcs deleted
   401       ///by restore().
   402       void restore()
   403       {
   404         _graph->restoreSnapshot(*this);
   405       }
   406     };
   407   };
   408 
   409 
   410   class SmartGraphBase {
   411 
   412   protected:
   413 
   414     struct NodeT {
   415       int first_out;
   416     };
   417 
   418     struct ArcT {
   419       int target;
   420       int next_out;
   421     };
   422 
   423     std::vector<NodeT> nodes;
   424     std::vector<ArcT> arcs;
   425 
   426     int first_free_arc;
   427 
   428   public:
   429 
   430     typedef SmartGraphBase Digraph;
   431 
   432     class Node;
   433     class Arc;
   434     class Edge;
   435 
   436     class Node {
   437       friend class SmartGraphBase;
   438     protected:
   439 
   440       int _id;
   441       explicit Node(int id) { _id = id;}
   442 
   443     public:
   444       Node() {}
   445       Node (Invalid) { _id = -1; }
   446       bool operator==(const Node& node) const {return _id == node._id;}
   447       bool operator!=(const Node& node) const {return _id != node._id;}
   448       bool operator<(const Node& node) const {return _id < node._id;}
   449     };
   450 
   451     class Edge {
   452       friend class SmartGraphBase;
   453     protected:
   454 
   455       int _id;
   456       explicit Edge(int id) { _id = id;}
   457 
   458     public:
   459       Edge() {}
   460       Edge (Invalid) { _id = -1; }
   461       bool operator==(const Edge& arc) const {return _id == arc._id;}
   462       bool operator!=(const Edge& arc) const {return _id != arc._id;}
   463       bool operator<(const Edge& arc) const {return _id < arc._id;}
   464     };
   465 
   466     class Arc {
   467       friend class SmartGraphBase;
   468     protected:
   469 
   470       int _id;
   471       explicit Arc(int id) { _id = id;}
   472 
   473     public:
   474       operator Edge() const { return edgeFromId(_id / 2); }
   475 
   476       Arc() {}
   477       Arc (Invalid) { _id = -1; }
   478       bool operator==(const Arc& arc) const {return _id == arc._id;}
   479       bool operator!=(const Arc& arc) const {return _id != arc._id;}
   480       bool operator<(const Arc& arc) const {return _id < arc._id;}
   481     };
   482 
   483 
   484 
   485     SmartGraphBase()
   486       : nodes(), arcs() {}
   487 
   488 
   489     int maxNodeId() const { return nodes.size()-1; }
   490     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   491     int maxArcId() const { return arcs.size()-1; }
   492 
   493     Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
   494     Node target(Arc e) const { return Node(arcs[e._id].target); }
   495 
   496     Node u(Edge e) const { return Node(arcs[2 * e._id].target); }
   497     Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
   498 
   499     static bool direction(Arc e) {
   500       return (e._id & 1) == 1;
   501     }
   502 
   503     static Arc direct(Edge e, bool d) {
   504       return Arc(e._id * 2 + (d ? 1 : 0));
   505     }
   506 
   507     void first(Node& node) const {
   508       node._id = nodes.size() - 1;
   509     }
   510 
   511     void next(Node& node) const {
   512       --node._id;
   513     }
   514 
   515     void first(Arc& arc) const {
   516       arc._id = arcs.size() - 1;
   517     }
   518 
   519     void next(Arc& arc) const {
   520       --arc._id;
   521     }
   522 
   523     void first(Edge& arc) const {
   524       arc._id = arcs.size() / 2 - 1;
   525     }
   526 
   527     void next(Edge& arc) const {
   528       --arc._id;
   529     }
   530 
   531     void firstOut(Arc &arc, const Node& v) const {
   532       arc._id = nodes[v._id].first_out;
   533     }
   534     void nextOut(Arc &arc) const {
   535       arc._id = arcs[arc._id].next_out;
   536     }
   537 
   538     void firstIn(Arc &arc, const Node& v) const {
   539       arc._id = ((nodes[v._id].first_out) ^ 1);
   540       if (arc._id == -2) arc._id = -1;
   541     }
   542     void nextIn(Arc &arc) const {
   543       arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
   544       if (arc._id == -2) arc._id = -1;
   545     }
   546 
   547     void firstInc(Edge &arc, bool& d, const Node& v) const {
   548       int de = nodes[v._id].first_out;
   549       if (de != -1) {
   550         arc._id = de / 2;
   551         d = ((de & 1) == 1);
   552       } else {
   553         arc._id = -1;
   554         d = true;
   555       }
   556     }
   557     void nextInc(Edge &arc, bool& d) const {
   558       int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
   559       if (de != -1) {
   560         arc._id = de / 2;
   561         d = ((de & 1) == 1);
   562       } else {
   563         arc._id = -1;
   564         d = true;
   565       }
   566     }
   567 
   568     static int id(Node v) { return v._id; }
   569     static int id(Arc e) { return e._id; }
   570     static int id(Edge e) { return e._id; }
   571 
   572     static Node nodeFromId(int id) { return Node(id);}
   573     static Arc arcFromId(int id) { return Arc(id);}
   574     static Edge edgeFromId(int id) { return Edge(id);}
   575 
   576     bool valid(Node n) const {
   577       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
   578     }
   579     bool valid(Arc a) const {
   580       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
   581     }
   582     bool valid(Edge e) const {
   583       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
   584     }
   585 
   586     Node addNode() {
   587       int n = nodes.size();
   588       nodes.push_back(NodeT());
   589       nodes[n].first_out = -1;
   590 
   591       return Node(n);
   592     }
   593 
   594     Edge addEdge(Node u, Node v) {
   595       int n = arcs.size();
   596       arcs.push_back(ArcT());
   597       arcs.push_back(ArcT());
   598 
   599       arcs[n].target = u._id;
   600       arcs[n | 1].target = v._id;
   601 
   602       arcs[n].next_out = nodes[v._id].first_out;
   603       nodes[v._id].first_out = n;
   604 
   605       arcs[n | 1].next_out = nodes[u._id].first_out;
   606       nodes[u._id].first_out = (n | 1);
   607 
   608       return Edge(n / 2);
   609     }
   610 
   611     void clear() {
   612       arcs.clear();
   613       nodes.clear();
   614     }
   615 
   616   };
   617 
   618   typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
   619 
   620   /// \ingroup graphs
   621   ///
   622   /// \brief A smart undirected graph class.
   623   ///
   624   /// This is a simple and fast graph implementation.
   625   /// It is also quite memory efficient, but at the price
   626   /// that <b> it does support only limited (only stack-like)
   627   /// node and arc deletions</b>.
   628   /// Except from this it conforms to
   629   /// the \ref concepts::Graph "Graph concept".
   630   ///
   631   /// It also has an
   632   /// important extra feature that
   633   /// its maps are real \ref concepts::ReferenceMap "reference map"s.
   634   ///
   635   /// \sa concepts::Graph.
   636   ///
   637   class SmartGraph : public ExtendedSmartGraphBase {
   638   private:
   639 
   640     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
   641 
   642     ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
   643     ///
   644     SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
   645 
   646     ///\brief Assignment of SmartGraph to another one is \e not allowed.
   647     ///Use GraphCopy() instead.
   648 
   649     ///Assignment of SmartGraph to another one is \e not allowed.
   650     ///Use GraphCopy() instead.
   651     void operator=(const SmartGraph &) {}
   652 
   653   public:
   654 
   655     typedef ExtendedSmartGraphBase Parent;
   656 
   657     /// Constructor
   658 
   659     /// Constructor.
   660     ///
   661     SmartGraph() {}
   662 
   663     ///Add a new node to the graph.
   664 
   665     /// \return the new node.
   666     ///
   667     Node addNode() { return Parent::addNode(); }
   668 
   669     ///Add a new edge to the graph.
   670 
   671     ///Add a new edge to the graph with node \c s
   672     ///and \c t.
   673     ///\return the new edge.
   674     Edge addEdge(const Node& s, const Node& t) {
   675       return Parent::addEdge(s, t);
   676     }
   677 
   678     /// \brief Node validity check
   679     ///
   680     /// This function gives back true if the given node is valid,
   681     /// ie. it is a real node of the graph.
   682     ///
   683     /// \warning A removed node (using Snapshot) could become valid again
   684     /// when new nodes are added to the graph.
   685     bool valid(Node n) const { return Parent::valid(n); }
   686 
   687     /// \brief Arc validity check
   688     ///
   689     /// This function gives back true if the given arc is valid,
   690     /// ie. it is a real arc of the graph.
   691     ///
   692     /// \warning A removed arc (using Snapshot) could become valid again
   693     /// when new edges are added to the graph.
   694     bool valid(Arc a) const { return Parent::valid(a); }
   695 
   696     /// \brief Edge validity check
   697     ///
   698     /// This function gives back true if the given edge is valid,
   699     /// ie. it is a real edge of the graph.
   700     ///
   701     /// \warning A removed edge (using Snapshot) could become valid again
   702     /// when new edges are added to the graph.
   703     bool valid(Edge e) const { return Parent::valid(e); }
   704 
   705     ///Clear the graph.
   706 
   707     ///Erase all the nodes and edges from the graph.
   708     ///
   709     void clear() {
   710       Parent::clear();
   711     }
   712 
   713   public:
   714 
   715     class Snapshot;
   716 
   717   protected:
   718 
   719     void saveSnapshot(Snapshot &s)
   720     {
   721       s._graph = this;
   722       s.node_num = nodes.size();
   723       s.arc_num = arcs.size();
   724     }
   725 
   726     void restoreSnapshot(const Snapshot &s)
   727     {
   728       while(s.arc_num<arcs.size()) {
   729         int n=arcs.size()-1;
   730         Edge arc=edgeFromId(n/2);
   731         Parent::notifier(Edge()).erase(arc);
   732         std::vector<Arc> dir;
   733         dir.push_back(arcFromId(n));
   734         dir.push_back(arcFromId(n-1));
   735         Parent::notifier(Arc()).erase(dir);
   736         nodes[arcs[n].target].first_out=arcs[n].next_out;
   737         nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
   738         arcs.pop_back();
   739         arcs.pop_back();
   740       }
   741       while(s.node_num<nodes.size()) {
   742         int n=nodes.size()-1;
   743         Node node = nodeFromId(n);
   744         Parent::notifier(Node()).erase(node);
   745         nodes.pop_back();
   746       }
   747     }
   748 
   749   public:
   750 
   751     ///Class to make a snapshot of the digraph and to restrore to it later.
   752 
   753     ///Class to make a snapshot of the digraph and to restrore to it later.
   754     ///
   755     ///The newly added nodes and arcs can be removed using the
   756     ///restore() function.
   757     ///
   758     ///\note After you restore a state, you cannot restore
   759     ///a later state, in other word you cannot add again the arcs deleted
   760     ///by restore() using another one Snapshot instance.
   761     ///
   762     ///\warning If you do not use correctly the snapshot that can cause
   763     ///either broken program, invalid state of the digraph, valid but
   764     ///not the restored digraph or no change. Because the runtime performance
   765     ///the validity of the snapshot is not stored.
   766     class Snapshot
   767     {
   768       SmartGraph *_graph;
   769     protected:
   770       friend class SmartGraph;
   771       unsigned int node_num;
   772       unsigned int arc_num;
   773     public:
   774       ///Default constructor.
   775 
   776       ///Default constructor.
   777       ///To actually make a snapshot you must call save().
   778       ///
   779       Snapshot() : _graph(0) {}
   780       ///Constructor that immediately makes a snapshot
   781 
   782       ///This constructor immediately makes a snapshot of the digraph.
   783       ///\param g The digraph we make a snapshot of.
   784       Snapshot(SmartGraph &graph) {
   785         graph.saveSnapshot(*this);
   786       }
   787 
   788       ///Make a snapshot.
   789 
   790       ///Make a snapshot of the graph.
   791       ///
   792       ///This function can be called more than once. In case of a repeated
   793       ///call, the previous snapshot gets lost.
   794       ///\param g The digraph we make the snapshot of.
   795       void save(SmartGraph &graph)
   796       {
   797         graph.saveSnapshot(*this);
   798       }
   799 
   800       ///Undo the changes until a snapshot.
   801 
   802       ///Undo the changes until a snapshot created by save().
   803       ///
   804       ///\note After you restored a state, you cannot restore
   805       ///a later state, in other word you cannot add again the arcs deleted
   806       ///by restore().
   807       void restore()
   808       {
   809         _graph->restoreSnapshot(*this);
   810       }
   811     };
   812   };
   813 
   814 } //namespace lemon
   815 
   816 
   817 #endif //LEMON_SMART_GRAPH_H