lemon/smart_graph.h
author Balazs Dezso <deba@inf.elte.hu>
Tue, 22 Apr 2008 13:50:52 +0200
changeset 144 4e626dbbe408
parent 109 abddaa08b507
child 138 a0f755a30cf1
permissions -rw-r--r--
MSVC 2005 compatible path structure (ticket #87)
     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 u(Edge e) const { return Node(arcs[2 * e._id].target); }
   474     Node v(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