lemon/smart_graph.h
author Balazs Dezso <deba@inf.elte.hu>
Sun, 04 Oct 2009 00:28:42 +0200
changeset 746 e4554cd6b2bf
parent 735 853fcddcf282
child 780 580af8cf2f6a
permissions -rw-r--r--
Faster add row operation (#203)

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