lemon/smart_graph.h
changeset 215 17c644f5f98d
parent 157 2ccc1afc2c52
child 220 a5d8c039f218
equal deleted inserted replaced
5:d10ebfb4fc71 6:2f000c45b3ab
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    43   ///Base of SmartDigraph
    43   ///Base of SmartDigraph
    44   ///
    44   ///
    45   class SmartDigraphBase {
    45   class SmartDigraphBase {
    46   protected:
    46   protected:
    47 
    47 
    48     struct NodeT 
    48     struct NodeT
    49     {
    49     {
    50       int first_in, first_out;      
    50       int first_in, first_out;
    51       NodeT() {}
    51       NodeT() {}
    52     };
    52     };
    53     struct ArcT 
    53     struct ArcT
    54     {
    54     {
    55       int target, source, next_in, next_out;      
    55       int target, source, next_in, next_out;
    56       ArcT() {}  
    56       ArcT() {}
    57     };
    57     };
    58 
    58 
    59     std::vector<NodeT> nodes;
    59     std::vector<NodeT> nodes;
    60     std::vector<ArcT> arcs;
    60     std::vector<ArcT> arcs;
    61         
    61 
    62   public:
    62   public:
    63 
    63 
    64     typedef SmartDigraphBase Graph;
    64     typedef SmartDigraphBase Graph;
    65 
    65 
    66     class Node;
    66     class Node;
    67     class Arc;
    67     class Arc;
    68 
    68 
    69   public:
    69   public:
    70 
    70 
    71     SmartDigraphBase() : nodes(), arcs() { }
    71     SmartDigraphBase() : nodes(), arcs() { }
    72     SmartDigraphBase(const SmartDigraphBase &_g) 
    72     SmartDigraphBase(const SmartDigraphBase &_g)
    73       : nodes(_g.nodes), arcs(_g.arcs) { }
    73       : nodes(_g.nodes), arcs(_g.arcs) { }
    74     
    74 
    75     typedef True NodeNumTag;
    75     typedef True NodeNumTag;
    76     typedef True EdgeNumTag;
    76     typedef True EdgeNumTag;
    77 
    77 
    78     int nodeNum() const { return nodes.size(); }
    78     int nodeNum() const { return nodes.size(); }
    79     int arcNum() const { return arcs.size(); }
    79     int arcNum() const { return arcs.size(); }
    80 
    80 
    81     int maxNodeId() const { return nodes.size()-1; }
    81     int maxNodeId() const { return nodes.size()-1; }
    82     int maxArcId() const { return arcs.size()-1; }
    82     int maxArcId() const { return arcs.size()-1; }
    83 
    83 
    84     Node addNode() {
    84     Node addNode() {
    85       int n = nodes.size();     
    85       int n = nodes.size();
    86       nodes.push_back(NodeT());
    86       nodes.push_back(NodeT());
    87       nodes[n].first_in = -1;
    87       nodes[n].first_in = -1;
    88       nodes[n].first_out = -1;
    88       nodes[n].first_out = -1;
    89       return Node(n);
    89       return Node(n);
    90     }
    90     }
    91     
    91 
    92     Arc addArc(Node u, Node v) {
    92     Arc addArc(Node u, Node v) {
    93       int n = arcs.size(); 
    93       int n = arcs.size();
    94       arcs.push_back(ArcT());
    94       arcs.push_back(ArcT());
    95       arcs[n].source = u._id; 
    95       arcs[n].source = u._id;
    96       arcs[n].target = v._id;
    96       arcs[n].target = v._id;
    97       arcs[n].next_out = nodes[u._id].first_out;
    97       arcs[n].next_out = nodes[u._id].first_out;
    98       arcs[n].next_in = nodes[v._id].first_in;
    98       arcs[n].next_in = nodes[v._id].first_in;
    99       nodes[u._id].first_out = nodes[v._id].first_in = n;
    99       nodes[u._id].first_out = nodes[v._id].first_in = n;
   100 
   100 
   113     static int id(Arc a) { return a._id; }
   113     static int id(Arc a) { return a._id; }
   114 
   114 
   115     static Node nodeFromId(int id) { return Node(id);}
   115     static Node nodeFromId(int id) { return Node(id);}
   116     static Arc arcFromId(int id) { return Arc(id);}
   116     static Arc arcFromId(int id) { return Arc(id);}
   117 
   117 
   118     bool valid(Node n) const { 
   118     bool valid(Node n) const {
   119       return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 
   119       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
   120     }
   120     }
   121     bool valid(Arc a) const { 
   121     bool valid(Arc a) const {
   122       return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 
   122       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
   123     }
   123     }
   124 
   124 
   125     class Node {
   125     class Node {
   126       friend class SmartDigraphBase;
   126       friend class SmartDigraphBase;
   127       friend class SmartDigraph;
   127       friend class SmartDigraph;
   134       Node (Invalid) : _id(-1) {}
   134       Node (Invalid) : _id(-1) {}
   135       bool operator==(const Node i) const {return _id == i._id;}
   135       bool operator==(const Node i) const {return _id == i._id;}
   136       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;}
   137       bool operator<(const Node i) const {return _id < i._id;}
   138     };
   138     };
   139     
   139 
   140 
   140 
   141     class Arc {
   141     class Arc {
   142       friend class SmartDigraphBase;
   142       friend class SmartDigraphBase;
   143       friend class SmartDigraph;
   143       friend class SmartDigraph;
   144 
   144 
   178     }
   178     }
   179 
   179 
   180     void firstIn(Arc& arc, const Node& node) const {
   180     void firstIn(Arc& arc, const Node& node) const {
   181       arc._id = nodes[node._id].first_in;
   181       arc._id = nodes[node._id].first_in;
   182     }
   182     }
   183     
   183 
   184     void nextIn(Arc& arc) const {
   184     void nextIn(Arc& arc) const {
   185       arc._id = arcs[arc._id].next_in;
   185       arc._id = arcs[arc._id].next_in;
   186     }
   186     }
   187 
   187 
   188   };
   188   };
   220     ///Assignment of SmartDigraph to another one is \e not allowed.
   220     ///Assignment of SmartDigraph to another one is \e not allowed.
   221     ///Use DigraphCopy() instead.
   221     ///Use DigraphCopy() instead.
   222     void operator=(const SmartDigraph &) {}
   222     void operator=(const SmartDigraph &) {}
   223 
   223 
   224   public:
   224   public:
   225     
   225 
   226     /// Constructor
   226     /// Constructor
   227     
   227 
   228     /// Constructor.
   228     /// Constructor.
   229     ///
   229     ///
   230     SmartDigraph() {};
   230     SmartDigraph() {};
   231     
   231 
   232     ///Add a new node to the digraph.
   232     ///Add a new node to the digraph.
   233     
   233 
   234     /// \return the new node.
   234     /// \return the new node.
   235     ///
   235     ///
   236     Node addNode() { return Parent::addNode(); }
   236     Node addNode() { return Parent::addNode(); }
   237     
   237 
   238     ///Add a new arc to the digraph.
   238     ///Add a new arc to the digraph.
   239     
   239 
   240     ///Add a new arc to the digraph with source node \c s
   240     ///Add a new arc to the digraph with source node \c s
   241     ///and target node \c t.
   241     ///and target node \c t.
   242     ///\return the new arc.
   242     ///\return the new arc.
   243     Arc addArc(const Node& s, const Node& t) { 
   243     Arc addArc(const Node& s, const Node& t) {
   244       return Parent::addArc(s, t); 
   244       return Parent::addArc(s, t);
   245     }
   245     }
   246 
   246 
   247     /// \brief Using this it is possible to avoid the superfluous memory
   247     /// \brief Using this it is possible to avoid the superfluous memory
   248     /// allocation.
   248     /// allocation.
   249 
   249 
   267     void reserveArc(int m) { arcs.reserve(m); };
   267     void reserveArc(int m) { arcs.reserve(m); };
   268 
   268 
   269     /// \brief Node validity check
   269     /// \brief Node validity check
   270     ///
   270     ///
   271     /// This function gives back true if the given node is valid,
   271     /// This function gives back true if the given node is valid,
   272     /// ie. it is a real node of the graph.  
   272     /// ie. it is a real node of the graph.
   273     ///
   273     ///
   274     /// \warning A removed node (using Snapshot) could become valid again
   274     /// \warning A removed node (using Snapshot) could become valid again
   275     /// when new nodes are added to the graph.
   275     /// when new nodes are added to the graph.
   276     bool valid(Node n) const { return Parent::valid(n); }
   276     bool valid(Node n) const { return Parent::valid(n); }
   277 
   277 
   278     /// \brief Arc validity check
   278     /// \brief Arc validity check
   279     ///
   279     ///
   280     /// This function gives back true if the given arc is valid,
   280     /// This function gives back true if the given arc is valid,
   281     /// ie. it is a real arc of the graph.  
   281     /// ie. it is a real arc of the graph.
   282     ///
   282     ///
   283     /// \warning A removed arc (using Snapshot) could become valid again
   283     /// \warning A removed arc (using Snapshot) could become valid again
   284     /// when new arcs are added to the graph.
   284     /// when new arcs are added to the graph.
   285     bool valid(Arc a) const { return Parent::valid(a); }
   285     bool valid(Arc a) const { return Parent::valid(a); }
   286 
   286 
   287     ///Clear the digraph.
   287     ///Clear the digraph.
   288     
   288 
   289     ///Erase all the nodes and arcs from the digraph.
   289     ///Erase all the nodes and arcs from the digraph.
   290     ///
   290     ///
   291     void clear() {
   291     void clear() {
   292       Parent::clear();
   292       Parent::clear();
   293     }
   293     }
   294 
   294 
   295     ///Split a node.
   295     ///Split a node.
   296     
   296 
   297     ///This function splits a node. First a new node is added to the digraph,
   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.
   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
   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.
   300     ///from \c n to the newly created node is also added.
   301     ///\return The newly created node.
   301     ///\return The newly created node.
   316       if(connect) addArc(n,b);
   316       if(connect) addArc(n,b);
   317       return b;
   317       return b;
   318     }
   318     }
   319 
   319 
   320   public:
   320   public:
   321     
   321 
   322     class Snapshot;
   322     class Snapshot;
   323 
   323 
   324   protected:
   324   protected:
   325 
   325 
   326     void restoreSnapshot(const Snapshot &s)
   326     void restoreSnapshot(const Snapshot &s)
   327     {
   327     {
   328       while(s.arc_num<arcs.size()) {
   328       while(s.arc_num<arcs.size()) {
   329         Arc arc = arcFromId(arcs.size()-1);
   329         Arc arc = arcFromId(arcs.size()-1);
   330 	Parent::notifier(Arc()).erase(arc);
   330         Parent::notifier(Arc()).erase(arc);
   331 	nodes[arcs.back().source].first_out=arcs.back().next_out;
   331         nodes[arcs.back().source].first_out=arcs.back().next_out;
   332 	nodes[arcs.back().target].first_in=arcs.back().next_in;
   332         nodes[arcs.back().target].first_in=arcs.back().next_in;
   333 	arcs.pop_back();
   333         arcs.pop_back();
   334       }
   334       }
   335       while(s.node_num<nodes.size()) {
   335       while(s.node_num<nodes.size()) {
   336         Node node = nodeFromId(nodes.size()-1);
   336         Node node = nodeFromId(nodes.size()-1);
   337 	Parent::notifier(Node()).erase(node);
   337         Parent::notifier(Node()).erase(node);
   338 	nodes.pop_back();
   338         nodes.pop_back();
   339       }
   339       }
   340     }    
   340     }
   341 
   341 
   342   public:
   342   public:
   343 
   343 
   344     ///Class to make a snapshot of the digraph and to restrore to it later.
   344     ///Class to make a snapshot of the digraph and to restrore to it later.
   345 
   345 
   353     ///
   353     ///
   354     ///\warning If you do not use correctly the snapshot that can cause
   354     ///\warning If you do not use correctly the snapshot that can cause
   355     ///either broken program, invalid state of the digraph, valid but
   355     ///either broken program, invalid state of the digraph, valid but
   356     ///not the restored digraph or no change. Because the runtime performance
   356     ///not the restored digraph or no change. Because the runtime performance
   357     ///the validity of the snapshot is not stored.
   357     ///the validity of the snapshot is not stored.
   358     class Snapshot 
   358     class Snapshot
   359     {
   359     {
   360       SmartDigraph *_graph;
   360       SmartDigraph *_graph;
   361     protected:
   361     protected:
   362       friend class SmartDigraph;
   362       friend class SmartDigraph;
   363       unsigned int node_num;
   363       unsigned int node_num;
   364       unsigned int arc_num;
   364       unsigned int arc_num;
   365     public:
   365     public:
   366       ///Default constructor.
   366       ///Default constructor.
   367       
   367 
   368       ///Default constructor.
   368       ///Default constructor.
   369       ///To actually make a snapshot you must call save().
   369       ///To actually make a snapshot you must call save().
   370       ///
   370       ///
   371       Snapshot() : _graph(0) {}
   371       Snapshot() : _graph(0) {}
   372       ///Constructor that immediately makes a snapshot
   372       ///Constructor that immediately makes a snapshot
   373       
   373 
   374       ///This constructor immediately makes a snapshot of the digraph.
   374       ///This constructor immediately makes a snapshot of the digraph.
   375       ///\param _g The digraph we make a snapshot of.
   375       ///\param _g The digraph we make a snapshot of.
   376       Snapshot(SmartDigraph &graph) : _graph(&graph) {
   376       Snapshot(SmartDigraph &graph) : _graph(&graph) {
   377 	node_num=_graph->nodes.size();
   377         node_num=_graph->nodes.size();
   378 	arc_num=_graph->arcs.size();
   378         arc_num=_graph->arcs.size();
   379       }
   379       }
   380 
   380 
   381       ///Make a snapshot.
   381       ///Make a snapshot.
   382 
   382 
   383       ///Make a snapshot of the digraph.
   383       ///Make a snapshot of the digraph.
   384       ///
   384       ///
   385       ///This function can be called more than once. In case of a repeated
   385       ///This function can be called more than once. In case of a repeated
   386       ///call, the previous snapshot gets lost.
   386       ///call, the previous snapshot gets lost.
   387       ///\param _g The digraph we make the snapshot of.
   387       ///\param _g The digraph we make the snapshot of.
   388       void save(SmartDigraph &graph) 
   388       void save(SmartDigraph &graph)
   389       {
   389       {
   390 	_graph=&graph;
   390         _graph=&graph;
   391 	node_num=_graph->nodes.size();
   391         node_num=_graph->nodes.size();
   392 	arc_num=_graph->arcs.size();
   392         arc_num=_graph->arcs.size();
   393       }
   393       }
   394 
   394 
   395       ///Undo the changes until a snapshot.
   395       ///Undo the changes until a snapshot.
   396       
   396 
   397       ///Undo the changes until a snapshot created by save().
   397       ///Undo the changes until a snapshot created by save().
   398       ///
   398       ///
   399       ///\note After you restored a state, you cannot restore
   399       ///\note After you restored a state, you cannot restore
   400       ///a later state, in other word you cannot add again the arcs deleted
   400       ///a later state, in other word you cannot add again the arcs deleted
   401       ///by restore().
   401       ///by restore().
   402       void restore()
   402       void restore()
   403       {
   403       {
   404 	_graph->restoreSnapshot(*this);
   404         _graph->restoreSnapshot(*this);
   405       }
   405       }
   406     };
   406     };
   407   };
   407   };
   408 
   408 
   409 
   409 
   412   protected:
   412   protected:
   413 
   413 
   414     struct NodeT {
   414     struct NodeT {
   415       int first_out;
   415       int first_out;
   416     };
   416     };
   417  
   417 
   418     struct ArcT {
   418     struct ArcT {
   419       int target;
   419       int target;
   420       int next_out;
   420       int next_out;
   421     };
   421     };
   422 
   422 
   423     std::vector<NodeT> nodes;
   423     std::vector<NodeT> nodes;
   424     std::vector<ArcT> arcs;
   424     std::vector<ArcT> arcs;
   425 
   425 
   426     int first_free_arc;
   426     int first_free_arc;
   427     
   427 
   428   public:
   428   public:
   429     
   429 
   430     typedef SmartGraphBase Digraph;
   430     typedef SmartGraphBase Digraph;
   431 
   431 
   432     class Node;
   432     class Node;
   433     class Arc;
   433     class Arc;
   434     class Edge;
   434     class Edge;
   435     
   435 
   436     class Node {
   436     class Node {
   437       friend class SmartGraphBase;
   437       friend class SmartGraphBase;
   438     protected:
   438     protected:
   439 
   439 
   440       int _id;
   440       int _id;
   483 
   483 
   484 
   484 
   485     SmartGraphBase()
   485     SmartGraphBase()
   486       : nodes(), arcs() {}
   486       : nodes(), arcs() {}
   487 
   487 
   488     
   488 
   489     int maxNodeId() const { return nodes.size()-1; } 
   489     int maxNodeId() const { return nodes.size()-1; }
   490     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   490     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   491     int maxArcId() const { return arcs.size()-1; }
   491     int maxArcId() const { return arcs.size()-1; }
   492 
   492 
   493     Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
   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); }
   494     Node target(Arc e) const { return Node(arcs[e._id].target); }
   502 
   502 
   503     static Arc direct(Edge e, bool d) {
   503     static Arc direct(Edge e, bool d) {
   504       return Arc(e._id * 2 + (d ? 1 : 0));
   504       return Arc(e._id * 2 + (d ? 1 : 0));
   505     }
   505     }
   506 
   506 
   507     void first(Node& node) const { 
   507     void first(Node& node) const {
   508       node._id = nodes.size() - 1;
   508       node._id = nodes.size() - 1;
   509     }
   509     }
   510 
   510 
   511     void next(Node& node) const {
   511     void next(Node& node) const {
   512       --node._id;
   512       --node._id;
   513     }
   513     }
   514 
   514 
   515     void first(Arc& arc) const { 
   515     void first(Arc& arc) const {
   516       arc._id = arcs.size() - 1;
   516       arc._id = arcs.size() - 1;
   517     }
   517     }
   518 
   518 
   519     void next(Arc& arc) const {
   519     void next(Arc& arc) const {
   520       --arc._id;
   520       --arc._id;
   521     }
   521     }
   522 
   522 
   523     void first(Edge& arc) const { 
   523     void first(Edge& arc) const {
   524       arc._id = arcs.size() / 2 - 1;
   524       arc._id = arcs.size() / 2 - 1;
   525     }
   525     }
   526 
   526 
   527     void next(Edge& arc) const {
   527     void next(Edge& arc) const {
   528       --arc._id;
   528       --arc._id;
   559       if (de != -1) {
   559       if (de != -1) {
   560         arc._id = de / 2;
   560         arc._id = de / 2;
   561         d = ((de & 1) == 1);
   561         d = ((de & 1) == 1);
   562       } else {
   562       } else {
   563         arc._id = -1;
   563         arc._id = -1;
   564         d = true;      
   564         d = true;
   565       }
   565       }
   566     }
   566     }
   567     
   567 
   568     static int id(Node v) { return v._id; }
   568     static int id(Node v) { return v._id; }
   569     static int id(Arc e) { return e._id; }
   569     static int id(Arc e) { return e._id; }
   570     static int id(Edge e) { return e._id; }
   570     static int id(Edge e) { return e._id; }
   571 
   571 
   572     static Node nodeFromId(int id) { return Node(id);}
   572     static Node nodeFromId(int id) { return Node(id);}
   573     static Arc arcFromId(int id) { return Arc(id);}
   573     static Arc arcFromId(int id) { return Arc(id);}
   574     static Edge edgeFromId(int id) { return Edge(id);}
   574     static Edge edgeFromId(int id) { return Edge(id);}
   575 
   575 
   576     bool valid(Node n) const { 
   576     bool valid(Node n) const {
   577       return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 
   577       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
   578     }
   578     }
   579     bool valid(Arc a) const { 
   579     bool valid(Arc a) const {
   580       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
   580       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
   581     }
   581     }
   582     bool valid(Edge e) const { 
   582     bool valid(Edge e) const {
   583       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 
   583       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
   584     }
   584     }
   585 
   585 
   586     Node addNode() {     
   586     Node addNode() {
   587       int n = nodes.size();
   587       int n = nodes.size();
   588       nodes.push_back(NodeT());
   588       nodes.push_back(NodeT());
   589       nodes[n].first_out = -1;
   589       nodes[n].first_out = -1;
   590       
   590 
   591       return Node(n);
   591       return Node(n);
   592     }
   592     }
   593     
   593 
   594     Edge addEdge(Node u, Node v) {
   594     Edge addEdge(Node u, Node v) {
   595       int n = arcs.size();
   595       int n = arcs.size();
   596       arcs.push_back(ArcT());
   596       arcs.push_back(ArcT());
   597       arcs.push_back(ArcT());
   597       arcs.push_back(ArcT());
   598       
   598 
   599       arcs[n].target = u._id;
   599       arcs[n].target = u._id;
   600       arcs[n | 1].target = v._id;
   600       arcs[n | 1].target = v._id;
   601 
   601 
   602       arcs[n].next_out = nodes[v._id].first_out;
   602       arcs[n].next_out = nodes[v._id].first_out;
   603       nodes[v._id].first_out = n;
   603       nodes[v._id].first_out = n;
   604 
   604 
   605       arcs[n | 1].next_out = nodes[u._id].first_out;	
   605       arcs[n | 1].next_out = nodes[u._id].first_out;
   606       nodes[u._id].first_out = (n | 1);
   606       nodes[u._id].first_out = (n | 1);
   607 
   607 
   608       return Edge(n / 2);
   608       return Edge(n / 2);
   609     }
   609     }
   610     
   610 
   611     void clear() {
   611     void clear() {
   612       arcs.clear();
   612       arcs.clear();
   613       nodes.clear();
   613       nodes.clear();
   614     }
   614     }
   615 
   615 
   623   ///
   623   ///
   624   /// This is a simple and fast graph implementation.
   624   /// This is a simple and fast graph implementation.
   625   /// It is also quite memory efficient, but at the price
   625   /// It is also quite memory efficient, but at the price
   626   /// that <b> it does support only limited (only stack-like)
   626   /// that <b> it does support only limited (only stack-like)
   627   /// node and arc deletions</b>.
   627   /// node and arc deletions</b>.
   628   /// Except from this it conforms to 
   628   /// Except from this it conforms to
   629   /// the \ref concepts::Graph "Graph concept".
   629   /// the \ref concepts::Graph "Graph concept".
   630   ///
   630   ///
   631   /// It also has an
   631   /// It also has an
   632   /// important extra feature that
   632   /// important extra feature that
   633   /// its maps are real \ref concepts::ReferenceMap "reference map"s.
   633   /// its maps are real \ref concepts::ReferenceMap "reference map"s.
   653   public:
   653   public:
   654 
   654 
   655     typedef ExtendedSmartGraphBase Parent;
   655     typedef ExtendedSmartGraphBase Parent;
   656 
   656 
   657     /// Constructor
   657     /// Constructor
   658     
   658 
   659     /// Constructor.
   659     /// Constructor.
   660     ///
   660     ///
   661     SmartGraph() {}
   661     SmartGraph() {}
   662 
   662 
   663     ///Add a new node to the graph.
   663     ///Add a new node to the graph.
   664     
   664 
   665     /// \return the new node.
   665     /// \return the new node.
   666     ///
   666     ///
   667     Node addNode() { return Parent::addNode(); }
   667     Node addNode() { return Parent::addNode(); }
   668     
   668 
   669     ///Add a new edge to the graph.
   669     ///Add a new edge to the graph.
   670     
   670 
   671     ///Add a new edge to the graph with node \c s
   671     ///Add a new edge to the graph with node \c s
   672     ///and \c t.
   672     ///and \c t.
   673     ///\return the new edge.
   673     ///\return the new edge.
   674     Edge addEdge(const Node& s, const Node& t) { 
   674     Edge addEdge(const Node& s, const Node& t) {
   675       return Parent::addEdge(s, t); 
   675       return Parent::addEdge(s, t);
   676     }
   676     }
   677 
   677 
   678     /// \brief Node validity check
   678     /// \brief Node validity check
   679     ///
   679     ///
   680     /// This function gives back true if the given node is valid,
   680     /// This function gives back true if the given node is valid,
   681     /// ie. it is a real node of the graph.  
   681     /// ie. it is a real node of the graph.
   682     ///
   682     ///
   683     /// \warning A removed node (using Snapshot) could become valid again
   683     /// \warning A removed node (using Snapshot) could become valid again
   684     /// when new nodes are added to the graph.
   684     /// when new nodes are added to the graph.
   685     bool valid(Node n) const { return Parent::valid(n); }
   685     bool valid(Node n) const { return Parent::valid(n); }
   686 
   686 
   687     /// \brief Arc validity check
   687     /// \brief Arc validity check
   688     ///
   688     ///
   689     /// This function gives back true if the given arc is valid,
   689     /// This function gives back true if the given arc is valid,
   690     /// ie. it is a real arc of the graph.  
   690     /// ie. it is a real arc of the graph.
   691     ///
   691     ///
   692     /// \warning A removed arc (using Snapshot) could become valid again
   692     /// \warning A removed arc (using Snapshot) could become valid again
   693     /// when new edges are added to the graph.
   693     /// when new edges are added to the graph.
   694     bool valid(Arc a) const { return Parent::valid(a); }
   694     bool valid(Arc a) const { return Parent::valid(a); }
   695 
   695 
   696     /// \brief Edge validity check
   696     /// \brief Edge validity check
   697     ///
   697     ///
   698     /// This function gives back true if the given edge is valid,
   698     /// This function gives back true if the given edge is valid,
   699     /// ie. it is a real edge of the graph.  
   699     /// ie. it is a real edge of the graph.
   700     ///
   700     ///
   701     /// \warning A removed edge (using Snapshot) could become valid again
   701     /// \warning A removed edge (using Snapshot) could become valid again
   702     /// when new edges are added to the graph.
   702     /// when new edges are added to the graph.
   703     bool valid(Edge e) const { return Parent::valid(e); }
   703     bool valid(Edge e) const { return Parent::valid(e); }
   704 
   704 
   705     ///Clear the graph.
   705     ///Clear the graph.
   706     
   706 
   707     ///Erase all the nodes and edges from the graph.
   707     ///Erase all the nodes and edges from the graph.
   708     ///
   708     ///
   709     void clear() {
   709     void clear() {
   710       Parent::clear();
   710       Parent::clear();
   711     }
   711     }
   712 
   712 
   713   public:
   713   public:
   714     
   714 
   715     class Snapshot;
   715     class Snapshot;
   716 
   716 
   717   protected:
   717   protected:
   718 
   718 
   719     void saveSnapshot(Snapshot &s)
   719     void saveSnapshot(Snapshot &s)
   726     void restoreSnapshot(const Snapshot &s)
   726     void restoreSnapshot(const Snapshot &s)
   727     {
   727     {
   728       while(s.arc_num<arcs.size()) {
   728       while(s.arc_num<arcs.size()) {
   729         int n=arcs.size()-1;
   729         int n=arcs.size()-1;
   730         Edge arc=edgeFromId(n/2);
   730         Edge arc=edgeFromId(n/2);
   731 	Parent::notifier(Edge()).erase(arc);
   731         Parent::notifier(Edge()).erase(arc);
   732         std::vector<Arc> dir;
   732         std::vector<Arc> dir;
   733         dir.push_back(arcFromId(n));
   733         dir.push_back(arcFromId(n));
   734         dir.push_back(arcFromId(n-1));
   734         dir.push_back(arcFromId(n-1));
   735 	Parent::notifier(Arc()).erase(dir);
   735         Parent::notifier(Arc()).erase(dir);
   736 	nodes[arcs[n].target].first_out=arcs[n].next_out;
   736         nodes[arcs[n].target].first_out=arcs[n].next_out;
   737 	nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
   737         nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
   738 	arcs.pop_back();
   738         arcs.pop_back();
   739 	arcs.pop_back();
   739         arcs.pop_back();
   740       }
   740       }
   741       while(s.node_num<nodes.size()) {
   741       while(s.node_num<nodes.size()) {
   742         int n=nodes.size()-1;
   742         int n=nodes.size()-1;
   743         Node node = nodeFromId(n);
   743         Node node = nodeFromId(n);
   744 	Parent::notifier(Node()).erase(node);
   744         Parent::notifier(Node()).erase(node);
   745 	nodes.pop_back();
   745         nodes.pop_back();
   746       }
   746       }
   747     }    
   747     }
   748 
   748 
   749   public:
   749   public:
   750 
   750 
   751     ///Class to make a snapshot of the digraph and to restrore to it later.
   751     ///Class to make a snapshot of the digraph and to restrore to it later.
   752 
   752 
   761     ///
   761     ///
   762     ///\warning If you do not use correctly the snapshot that can cause
   762     ///\warning If you do not use correctly the snapshot that can cause
   763     ///either broken program, invalid state of the digraph, valid but
   763     ///either broken program, invalid state of the digraph, valid but
   764     ///not the restored digraph or no change. Because the runtime performance
   764     ///not the restored digraph or no change. Because the runtime performance
   765     ///the validity of the snapshot is not stored.
   765     ///the validity of the snapshot is not stored.
   766     class Snapshot 
   766     class Snapshot
   767     {
   767     {
   768       SmartGraph *_graph;
   768       SmartGraph *_graph;
   769     protected:
   769     protected:
   770       friend class SmartGraph;
   770       friend class SmartGraph;
   771       unsigned int node_num;
   771       unsigned int node_num;
   772       unsigned int arc_num;
   772       unsigned int arc_num;
   773     public:
   773     public:
   774       ///Default constructor.
   774       ///Default constructor.
   775       
   775 
   776       ///Default constructor.
   776       ///Default constructor.
   777       ///To actually make a snapshot you must call save().
   777       ///To actually make a snapshot you must call save().
   778       ///
   778       ///
   779       Snapshot() : _graph(0) {}
   779       Snapshot() : _graph(0) {}
   780       ///Constructor that immediately makes a snapshot
   780       ///Constructor that immediately makes a snapshot
   781       
   781 
   782       ///This constructor immediately makes a snapshot of the digraph.
   782       ///This constructor immediately makes a snapshot of the digraph.
   783       ///\param g The digraph we make a snapshot of.
   783       ///\param g The digraph we make a snapshot of.
   784       Snapshot(SmartGraph &graph) {
   784       Snapshot(SmartGraph &graph) {
   785         graph.saveSnapshot(*this);
   785         graph.saveSnapshot(*this);
   786       }
   786       }
   790       ///Make a snapshot of the graph.
   790       ///Make a snapshot of the graph.
   791       ///
   791       ///
   792       ///This function can be called more than once. In case of a repeated
   792       ///This function can be called more than once. In case of a repeated
   793       ///call, the previous snapshot gets lost.
   793       ///call, the previous snapshot gets lost.
   794       ///\param g The digraph we make the snapshot of.
   794       ///\param g The digraph we make the snapshot of.
   795       void save(SmartGraph &graph) 
   795       void save(SmartGraph &graph)
   796       {
   796       {
   797         graph.saveSnapshot(*this);
   797         graph.saveSnapshot(*this);
   798       }
   798       }
   799 
   799 
   800       ///Undo the changes until a snapshot.
   800       ///Undo the changes until a snapshot.
   801       
   801 
   802       ///Undo the changes until a snapshot created by save().
   802       ///Undo the changes until a snapshot created by save().
   803       ///
   803       ///
   804       ///\note After you restored a state, you cannot restore
   804       ///\note After you restored a state, you cannot restore
   805       ///a later state, in other word you cannot add again the arcs deleted
   805       ///a later state, in other word you cannot add again the arcs deleted
   806       ///by restore().
   806       ///by restore().
   808       {
   808       {
   809         _graph->restoreSnapshot(*this);
   809         _graph->restoreSnapshot(*this);
   810       }
   810       }
   811     };
   811     };
   812   };
   812   };
   813   
   813 
   814 } //namespace lemon
   814 } //namespace lemon
   815 
   815 
   816 
   816 
   817 #endif //LEMON_SMART_GRAPH_H
   817 #endif //LEMON_SMART_GRAPH_H