lemon/smart_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:30:45 +0100
changeset 809 22bb98ca0101
parent 780 580af8cf2f6a
child 877 141f9c0db4a3
permissions -rw-r--r--
Entirely rework CostScaling (#180)

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