lemon/list_graph.h
author Balazs Dezso <deba@inf.elte.hu>
Wed, 23 Jul 2008 19:32:48 +0200
changeset 233 28239207a8a3
parent 212 1ae84dea7d09
child 234 ad6b8c47bd56
permissions -rw-r--r--
Unify DynArcLookUp interface (ticket #127)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_LIST_GRAPH_H
    20 #define LEMON_LIST_GRAPH_H
    21 
    22 ///\ingroup graphs
    23 ///\file
    24 ///\brief ListDigraph, ListGraph classes.
    25 
    26 #include <lemon/core.h>
    27 #include <lemon/error.h>
    28 #include <lemon/bits/graph_extender.h>
    29 
    30 #include <vector>
    31 #include <list>
    32 
    33 namespace lemon {
    34 
    35   class ListDigraphBase {
    36 
    37   protected:
    38     struct NodeT {
    39       int first_in, first_out;
    40       int prev, next;
    41     };
    42 
    43     struct ArcT {
    44       int target, source;
    45       int prev_in, prev_out;
    46       int next_in, next_out;
    47     };
    48 
    49     std::vector<NodeT> nodes;
    50 
    51     int first_node;
    52 
    53     int first_free_node;
    54 
    55     std::vector<ArcT> arcs;
    56 
    57     int first_free_arc;
    58 
    59   public:
    60 
    61     typedef ListDigraphBase Digraph;
    62 
    63     class Node {
    64       friend class ListDigraphBase;
    65     protected:
    66 
    67       int id;
    68       explicit Node(int pid) { id = pid;}
    69 
    70     public:
    71       Node() {}
    72       Node (Invalid) { id = -1; }
    73       bool operator==(const Node& node) const {return id == node.id;}
    74       bool operator!=(const Node& node) const {return id != node.id;}
    75       bool operator<(const Node& node) const {return id < node.id;}
    76     };
    77 
    78     class Arc {
    79       friend class ListDigraphBase;
    80     protected:
    81 
    82       int id;
    83       explicit Arc(int pid) { id = pid;}
    84 
    85     public:
    86       Arc() {}
    87       Arc (Invalid) { id = -1; }
    88       bool operator==(const Arc& arc) const {return id == arc.id;}
    89       bool operator!=(const Arc& arc) const {return id != arc.id;}
    90       bool operator<(const Arc& arc) const {return id < arc.id;}
    91     };
    92 
    93 
    94 
    95     ListDigraphBase()
    96       : nodes(), first_node(-1),
    97         first_free_node(-1), arcs(), first_free_arc(-1) {}
    98 
    99 
   100     int maxNodeId() const { return nodes.size()-1; }
   101     int maxArcId() const { return arcs.size()-1; }
   102 
   103     Node source(Arc e) const { return Node(arcs[e.id].source); }
   104     Node target(Arc e) const { return Node(arcs[e.id].target); }
   105 
   106 
   107     void first(Node& node) const {
   108       node.id = first_node;
   109     }
   110 
   111     void next(Node& node) const {
   112       node.id = nodes[node.id].next;
   113     }
   114 
   115 
   116     void first(Arc& arc) const {
   117       int n;
   118       for(n = first_node;
   119           n!=-1 && nodes[n].first_in == -1;
   120           n = nodes[n].next) {}
   121       arc.id = (n == -1) ? -1 : nodes[n].first_in;
   122     }
   123 
   124     void next(Arc& arc) const {
   125       if (arcs[arc.id].next_in != -1) {
   126         arc.id = arcs[arc.id].next_in;
   127       } else {
   128         int n;
   129         for(n = nodes[arcs[arc.id].target].next;
   130             n!=-1 && nodes[n].first_in == -1;
   131             n = nodes[n].next) {}
   132         arc.id = (n == -1) ? -1 : nodes[n].first_in;
   133       }
   134     }
   135 
   136     void firstOut(Arc &e, const Node& v) const {
   137       e.id = nodes[v.id].first_out;
   138     }
   139     void nextOut(Arc &e) const {
   140       e.id=arcs[e.id].next_out;
   141     }
   142 
   143     void firstIn(Arc &e, const Node& v) const {
   144       e.id = nodes[v.id].first_in;
   145     }
   146     void nextIn(Arc &e) const {
   147       e.id=arcs[e.id].next_in;
   148     }
   149 
   150 
   151     static int id(Node v) { return v.id; }
   152     static int id(Arc e) { return e.id; }
   153 
   154     static Node nodeFromId(int id) { return Node(id);}
   155     static Arc arcFromId(int id) { return Arc(id);}
   156 
   157     bool valid(Node n) const {
   158       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
   159         nodes[n.id].prev != -2;
   160     }
   161 
   162     bool valid(Arc a) const {
   163       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
   164         arcs[a.id].prev_in != -2;
   165     }
   166 
   167     Node addNode() {
   168       int n;
   169 
   170       if(first_free_node==-1) {
   171         n = nodes.size();
   172         nodes.push_back(NodeT());
   173       } else {
   174         n = first_free_node;
   175         first_free_node = nodes[n].next;
   176       }
   177 
   178       nodes[n].next = first_node;
   179       if(first_node != -1) nodes[first_node].prev = n;
   180       first_node = n;
   181       nodes[n].prev = -1;
   182 
   183       nodes[n].first_in = nodes[n].first_out = -1;
   184 
   185       return Node(n);
   186     }
   187 
   188     Arc addArc(Node u, Node v) {
   189       int n;
   190 
   191       if (first_free_arc == -1) {
   192         n = arcs.size();
   193         arcs.push_back(ArcT());
   194       } else {
   195         n = first_free_arc;
   196         first_free_arc = arcs[n].next_in;
   197       }
   198 
   199       arcs[n].source = u.id;
   200       arcs[n].target = v.id;
   201 
   202       arcs[n].next_out = nodes[u.id].first_out;
   203       if(nodes[u.id].first_out != -1) {
   204         arcs[nodes[u.id].first_out].prev_out = n;
   205       }
   206 
   207       arcs[n].next_in = nodes[v.id].first_in;
   208       if(nodes[v.id].first_in != -1) {
   209         arcs[nodes[v.id].first_in].prev_in = n;
   210       }
   211 
   212       arcs[n].prev_in = arcs[n].prev_out = -1;
   213 
   214       nodes[u.id].first_out = nodes[v.id].first_in = n;
   215 
   216       return Arc(n);
   217     }
   218 
   219     void erase(const Node& node) {
   220       int n = node.id;
   221 
   222       if(nodes[n].next != -1) {
   223         nodes[nodes[n].next].prev = nodes[n].prev;
   224       }
   225 
   226       if(nodes[n].prev != -1) {
   227         nodes[nodes[n].prev].next = nodes[n].next;
   228       } else {
   229         first_node = nodes[n].next;
   230       }
   231 
   232       nodes[n].next = first_free_node;
   233       first_free_node = n;
   234       nodes[n].prev = -2;
   235 
   236     }
   237 
   238     void erase(const Arc& arc) {
   239       int n = arc.id;
   240 
   241       if(arcs[n].next_in!=-1) {
   242         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
   243       }
   244 
   245       if(arcs[n].prev_in!=-1) {
   246         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
   247       } else {
   248         nodes[arcs[n].target].first_in = arcs[n].next_in;
   249       }
   250 
   251 
   252       if(arcs[n].next_out!=-1) {
   253         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   254       }
   255 
   256       if(arcs[n].prev_out!=-1) {
   257         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   258       } else {
   259         nodes[arcs[n].source].first_out = arcs[n].next_out;
   260       }
   261 
   262       arcs[n].next_in = first_free_arc;
   263       first_free_arc = n;
   264       arcs[n].prev_in = -2;
   265     }
   266 
   267     void clear() {
   268       arcs.clear();
   269       nodes.clear();
   270       first_node = first_free_node = first_free_arc = -1;
   271     }
   272 
   273   protected:
   274     void changeTarget(Arc e, Node n)
   275     {
   276       if(arcs[e.id].next_in != -1)
   277         arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
   278       if(arcs[e.id].prev_in != -1)
   279         arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
   280       else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
   281       if (nodes[n.id].first_in != -1) {
   282         arcs[nodes[n.id].first_in].prev_in = e.id;
   283       }
   284       arcs[e.id].target = n.id;
   285       arcs[e.id].prev_in = -1;
   286       arcs[e.id].next_in = nodes[n.id].first_in;
   287       nodes[n.id].first_in = e.id;
   288     }
   289     void changeSource(Arc e, Node n)
   290     {
   291       if(arcs[e.id].next_out != -1)
   292         arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
   293       if(arcs[e.id].prev_out != -1)
   294         arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
   295       else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
   296       if (nodes[n.id].first_out != -1) {
   297         arcs[nodes[n.id].first_out].prev_out = e.id;
   298       }
   299       arcs[e.id].source = n.id;
   300       arcs[e.id].prev_out = -1;
   301       arcs[e.id].next_out = nodes[n.id].first_out;
   302       nodes[n.id].first_out = e.id;
   303     }
   304 
   305   };
   306 
   307   typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
   308 
   309   /// \addtogroup graphs
   310   /// @{
   311 
   312   ///A general directed graph structure.
   313 
   314   ///\ref ListDigraph is a simple and fast <em>directed graph</em>
   315   ///implementation based on static linked lists that are stored in
   316   ///\c std::vector structures.
   317   ///
   318   ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
   319   ///also provides several useful additional functionalities.
   320   ///Most of the member functions and nested classes are documented
   321   ///only in the concept class.
   322   ///
   323   ///An important extra feature of this digraph implementation is that
   324   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
   325   ///
   326   ///\sa concepts::Digraph
   327 
   328   class ListDigraph : public ExtendedListDigraphBase {
   329   private:
   330     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
   331 
   332     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
   333     ///
   334     ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
   335     ///\brief Assignment of ListDigraph to another one is \e not allowed.
   336     ///Use copyDigraph() instead.
   337 
   338     ///Assignment of ListDigraph to another one is \e not allowed.
   339     ///Use copyDigraph() instead.
   340     void operator=(const ListDigraph &) {}
   341   public:
   342 
   343     typedef ExtendedListDigraphBase Parent;
   344 
   345     /// Constructor
   346 
   347     /// Constructor.
   348     ///
   349     ListDigraph() {}
   350 
   351     ///Add a new node to the digraph.
   352 
   353     ///Add a new node to the digraph.
   354     ///\return the new node.
   355     Node addNode() { return Parent::addNode(); }
   356 
   357     ///Add a new arc to the digraph.
   358 
   359     ///Add a new arc to the digraph with source node \c s
   360     ///and target node \c t.
   361     ///\return the new arc.
   362     Arc addArc(const Node& s, const Node& t) {
   363       return Parent::addArc(s, t);
   364     }
   365 
   366     /// Node validity check
   367 
   368     /// This function gives back true if the given node is valid,
   369     /// ie. it is a real node of the graph.
   370     ///
   371     /// \warning A Node pointing to a removed item
   372     /// could become valid again later if new nodes are
   373     /// added to the graph.
   374     bool valid(Node n) const { return Parent::valid(n); }
   375 
   376     /// Arc validity check
   377 
   378     /// This function gives back true if the given arc is valid,
   379     /// ie. it is a real arc of the graph.
   380     ///
   381     /// \warning An Arc pointing to a removed item
   382     /// could become valid again later if new nodes are
   383     /// added to the graph.
   384     bool valid(Arc a) const { return Parent::valid(a); }
   385 
   386     /// Change the target of \c e to \c n
   387 
   388     /// Change the target of \c e to \c n
   389     ///
   390     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
   391     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
   392     ///invalidated.
   393     ///
   394     ///\warning This functionality cannot be used together with the Snapshot
   395     ///feature.
   396     void changeTarget(Arc e, Node n) {
   397       Parent::changeTarget(e,n);
   398     }
   399     /// Change the source of \c e to \c n
   400 
   401     /// Change the source of \c e to \c n
   402     ///
   403     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
   404     ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
   405     ///invalidated.
   406     ///
   407     ///\warning This functionality cannot be used together with the Snapshot
   408     ///feature.
   409     void changeSource(Arc e, Node n) {
   410       Parent::changeSource(e,n);
   411     }
   412 
   413     /// Invert the direction of an arc.
   414 
   415     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
   416     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
   417     ///invalidated.
   418     ///
   419     ///\warning This functionality cannot be used together with the Snapshot
   420     ///feature.
   421     void reverseArc(Arc e) {
   422       Node t=target(e);
   423       changeTarget(e,source(e));
   424       changeSource(e,t);
   425     }
   426 
   427     /// Reserve memory for nodes.
   428 
   429     /// Using this function it is possible to avoid the superfluous memory
   430     /// allocation: if you know that the digraph you want to build will
   431     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   432     /// then it is worth reserving space for this amount before starting
   433     /// to build the digraph.
   434     /// \sa reserveArc
   435     void reserveNode(int n) { nodes.reserve(n); };
   436 
   437     /// Reserve memory for arcs.
   438 
   439     /// Using this function it is possible to avoid the superfluous memory
   440     /// allocation: if you know that the digraph you want to build will
   441     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   442     /// then it is worth reserving space for this amount before starting
   443     /// to build the digraph.
   444     /// \sa reserveNode
   445     void reserveArc(int m) { arcs.reserve(m); };
   446 
   447     ///Contract two nodes.
   448 
   449     ///This function contracts two nodes.
   450     ///Node \p b will be removed but instead of deleting
   451     ///incident arcs, they will be joined to \p a.
   452     ///The last parameter \p r controls whether to remove loops. \c true
   453     ///means that loops will be removed.
   454     ///
   455     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
   456     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
   457     ///may be invalidated.
   458     ///
   459     ///\warning This functionality cannot be used together with the Snapshot
   460     ///feature.
   461     void contract(Node a, Node b, bool r = true)
   462     {
   463       for(OutArcIt e(*this,b);e!=INVALID;) {
   464         OutArcIt f=e;
   465         ++f;
   466         if(r && target(e)==a) erase(e);
   467         else changeSource(e,a);
   468         e=f;
   469       }
   470       for(InArcIt e(*this,b);e!=INVALID;) {
   471         InArcIt f=e;
   472         ++f;
   473         if(r && source(e)==a) erase(e);
   474         else changeTarget(e,a);
   475         e=f;
   476       }
   477       erase(b);
   478     }
   479 
   480     ///Split a node.
   481 
   482     ///This function splits a node. First a new node is added to the digraph,
   483     ///then the source of each outgoing arc of \c n is moved to this new node.
   484     ///If \c connect is \c true (this is the default value), then a new arc
   485     ///from \c n to the newly created node is also added.
   486     ///\return The newly created node.
   487     ///
   488     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
   489     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
   490     ///be invalidated.
   491     ///
   492     ///\warning This functionality cannot be used together with the
   493     ///Snapshot feature.
   494     ///
   495     ///\todo It could be implemented in a bit faster way.
   496     Node split(Node n, bool connect = true) {
   497       Node b = addNode();
   498       for(OutArcIt e(*this,n);e!=INVALID;) {
   499         OutArcIt f=e;
   500         ++f;
   501         changeSource(e,b);
   502         e=f;
   503       }
   504       if (connect) addArc(n,b);
   505       return b;
   506     }
   507 
   508     ///Split an arc.
   509 
   510     ///This function splits an arc. First a new node \c b is added to
   511     ///the digraph, then the original arc is re-targeted to \c
   512     ///b. Finally an arc from \c b to the original target is added.
   513     ///
   514     ///\return The newly created node.
   515     ///
   516     ///\warning This functionality cannot be used together with the
   517     ///Snapshot feature.
   518     Node split(Arc e) {
   519       Node b = addNode();
   520       addArc(b,target(e));
   521       changeTarget(e,b);
   522       return b;
   523     }
   524 
   525     /// \brief Class to make a snapshot of the digraph and restore
   526     /// it later.
   527     ///
   528     /// Class to make a snapshot of the digraph and restore it later.
   529     ///
   530     /// The newly added nodes and arcs can be removed using the
   531     /// restore() function.
   532     ///
   533     /// \warning Arc and node deletions and other modifications (e.g.
   534     /// contracting, splitting, reversing arcs or nodes) cannot be
   535     /// restored. These events invalidate the snapshot.
   536     class Snapshot {
   537     protected:
   538 
   539       typedef Parent::NodeNotifier NodeNotifier;
   540 
   541       class NodeObserverProxy : public NodeNotifier::ObserverBase {
   542       public:
   543 
   544         NodeObserverProxy(Snapshot& _snapshot)
   545           : snapshot(_snapshot) {}
   546 
   547         using NodeNotifier::ObserverBase::attach;
   548         using NodeNotifier::ObserverBase::detach;
   549         using NodeNotifier::ObserverBase::attached;
   550 
   551       protected:
   552 
   553         virtual void add(const Node& node) {
   554           snapshot.addNode(node);
   555         }
   556         virtual void add(const std::vector<Node>& nodes) {
   557           for (int i = nodes.size() - 1; i >= 0; ++i) {
   558             snapshot.addNode(nodes[i]);
   559           }
   560         }
   561         virtual void erase(const Node& node) {
   562           snapshot.eraseNode(node);
   563         }
   564         virtual void erase(const std::vector<Node>& nodes) {
   565           for (int i = 0; i < int(nodes.size()); ++i) {
   566             snapshot.eraseNode(nodes[i]);
   567           }
   568         }
   569         virtual void build() {
   570           Node node;
   571           std::vector<Node> nodes;
   572           for (notifier()->first(node); node != INVALID;
   573                notifier()->next(node)) {
   574             nodes.push_back(node);
   575           }
   576           for (int i = nodes.size() - 1; i >= 0; --i) {
   577             snapshot.addNode(nodes[i]);
   578           }
   579         }
   580         virtual void clear() {
   581           Node node;
   582           for (notifier()->first(node); node != INVALID;
   583                notifier()->next(node)) {
   584             snapshot.eraseNode(node);
   585           }
   586         }
   587 
   588         Snapshot& snapshot;
   589       };
   590 
   591       class ArcObserverProxy : public ArcNotifier::ObserverBase {
   592       public:
   593 
   594         ArcObserverProxy(Snapshot& _snapshot)
   595           : snapshot(_snapshot) {}
   596 
   597         using ArcNotifier::ObserverBase::attach;
   598         using ArcNotifier::ObserverBase::detach;
   599         using ArcNotifier::ObserverBase::attached;
   600 
   601       protected:
   602 
   603         virtual void add(const Arc& arc) {
   604           snapshot.addArc(arc);
   605         }
   606         virtual void add(const std::vector<Arc>& arcs) {
   607           for (int i = arcs.size() - 1; i >= 0; ++i) {
   608             snapshot.addArc(arcs[i]);
   609           }
   610         }
   611         virtual void erase(const Arc& arc) {
   612           snapshot.eraseArc(arc);
   613         }
   614         virtual void erase(const std::vector<Arc>& arcs) {
   615           for (int i = 0; i < int(arcs.size()); ++i) {
   616             snapshot.eraseArc(arcs[i]);
   617           }
   618         }
   619         virtual void build() {
   620           Arc arc;
   621           std::vector<Arc> arcs;
   622           for (notifier()->first(arc); arc != INVALID;
   623                notifier()->next(arc)) {
   624             arcs.push_back(arc);
   625           }
   626           for (int i = arcs.size() - 1; i >= 0; --i) {
   627             snapshot.addArc(arcs[i]);
   628           }
   629         }
   630         virtual void clear() {
   631           Arc arc;
   632           for (notifier()->first(arc); arc != INVALID;
   633                notifier()->next(arc)) {
   634             snapshot.eraseArc(arc);
   635           }
   636         }
   637 
   638         Snapshot& snapshot;
   639       };
   640 
   641       ListDigraph *digraph;
   642 
   643       NodeObserverProxy node_observer_proxy;
   644       ArcObserverProxy arc_observer_proxy;
   645 
   646       std::list<Node> added_nodes;
   647       std::list<Arc> added_arcs;
   648 
   649 
   650       void addNode(const Node& node) {
   651         added_nodes.push_front(node);
   652       }
   653       void eraseNode(const Node& node) {
   654         std::list<Node>::iterator it =
   655           std::find(added_nodes.begin(), added_nodes.end(), node);
   656         if (it == added_nodes.end()) {
   657           clear();
   658           arc_observer_proxy.detach();
   659           throw NodeNotifier::ImmediateDetach();
   660         } else {
   661           added_nodes.erase(it);
   662         }
   663       }
   664 
   665       void addArc(const Arc& arc) {
   666         added_arcs.push_front(arc);
   667       }
   668       void eraseArc(const Arc& arc) {
   669         std::list<Arc>::iterator it =
   670           std::find(added_arcs.begin(), added_arcs.end(), arc);
   671         if (it == added_arcs.end()) {
   672           clear();
   673           node_observer_proxy.detach();
   674           throw ArcNotifier::ImmediateDetach();
   675         } else {
   676           added_arcs.erase(it);
   677         }
   678       }
   679 
   680       void attach(ListDigraph &_digraph) {
   681         digraph = &_digraph;
   682         node_observer_proxy.attach(digraph->notifier(Node()));
   683         arc_observer_proxy.attach(digraph->notifier(Arc()));
   684       }
   685 
   686       void detach() {
   687         node_observer_proxy.detach();
   688         arc_observer_proxy.detach();
   689       }
   690 
   691       bool attached() const {
   692         return node_observer_proxy.attached();
   693       }
   694 
   695       void clear() {
   696         added_nodes.clear();
   697         added_arcs.clear();
   698       }
   699 
   700     public:
   701 
   702       /// \brief Default constructor.
   703       ///
   704       /// Default constructor.
   705       /// To actually make a snapshot you must call save().
   706       Snapshot()
   707         : digraph(0), node_observer_proxy(*this),
   708           arc_observer_proxy(*this) {}
   709 
   710       /// \brief Constructor that immediately makes a snapshot.
   711       ///
   712       /// This constructor immediately makes a snapshot of the digraph.
   713       /// \param _digraph The digraph we make a snapshot of.
   714       Snapshot(ListDigraph &_digraph)
   715         : node_observer_proxy(*this),
   716           arc_observer_proxy(*this) {
   717         attach(_digraph);
   718       }
   719 
   720       /// \brief Make a snapshot.
   721       ///
   722       /// Make a snapshot of the digraph.
   723       ///
   724       /// This function can be called more than once. In case of a repeated
   725       /// call, the previous snapshot gets lost.
   726       /// \param _digraph The digraph we make the snapshot of.
   727       void save(ListDigraph &_digraph) {
   728         if (attached()) {
   729           detach();
   730           clear();
   731         }
   732         attach(_digraph);
   733       }
   734 
   735       /// \brief Undo the changes until the last snapshot.
   736       //
   737       /// Undo the changes until the last snapshot created by save().
   738       void restore() {
   739         detach();
   740         for(std::list<Arc>::iterator it = added_arcs.begin();
   741             it != added_arcs.end(); ++it) {
   742           digraph->erase(*it);
   743         }
   744         for(std::list<Node>::iterator it = added_nodes.begin();
   745             it != added_nodes.end(); ++it) {
   746           digraph->erase(*it);
   747         }
   748         clear();
   749       }
   750 
   751       /// \brief Gives back true when the snapshot is valid.
   752       ///
   753       /// Gives back true when the snapshot is valid.
   754       bool valid() const {
   755         return attached();
   756       }
   757     };
   758 
   759   };
   760 
   761   ///@}
   762 
   763   class ListGraphBase {
   764 
   765   protected:
   766 
   767     struct NodeT {
   768       int first_out;
   769       int prev, next;
   770     };
   771 
   772     struct ArcT {
   773       int target;
   774       int prev_out, next_out;
   775     };
   776 
   777     std::vector<NodeT> nodes;
   778 
   779     int first_node;
   780 
   781     int first_free_node;
   782 
   783     std::vector<ArcT> arcs;
   784 
   785     int first_free_arc;
   786 
   787   public:
   788 
   789     typedef ListGraphBase Digraph;
   790 
   791     class Node;
   792     class Arc;
   793     class Edge;
   794 
   795     class Node {
   796       friend class ListGraphBase;
   797     protected:
   798 
   799       int id;
   800       explicit Node(int pid) { id = pid;}
   801 
   802     public:
   803       Node() {}
   804       Node (Invalid) { id = -1; }
   805       bool operator==(const Node& node) const {return id == node.id;}
   806       bool operator!=(const Node& node) const {return id != node.id;}
   807       bool operator<(const Node& node) const {return id < node.id;}
   808     };
   809 
   810     class Edge {
   811       friend class ListGraphBase;
   812     protected:
   813 
   814       int id;
   815       explicit Edge(int pid) { id = pid;}
   816 
   817     public:
   818       Edge() {}
   819       Edge (Invalid) { id = -1; }
   820       bool operator==(const Edge& edge) const {return id == edge.id;}
   821       bool operator!=(const Edge& edge) const {return id != edge.id;}
   822       bool operator<(const Edge& edge) const {return id < edge.id;}
   823     };
   824 
   825     class Arc {
   826       friend class ListGraphBase;
   827     protected:
   828 
   829       int id;
   830       explicit Arc(int pid) { id = pid;}
   831 
   832     public:
   833       operator Edge() const { return edgeFromId(id / 2); }
   834 
   835       Arc() {}
   836       Arc (Invalid) { id = -1; }
   837       bool operator==(const Arc& arc) const {return id == arc.id;}
   838       bool operator!=(const Arc& arc) const {return id != arc.id;}
   839       bool operator<(const Arc& arc) const {return id < arc.id;}
   840     };
   841 
   842 
   843 
   844     ListGraphBase()
   845       : nodes(), first_node(-1),
   846         first_free_node(-1), arcs(), first_free_arc(-1) {}
   847 
   848 
   849     int maxNodeId() const { return nodes.size()-1; }
   850     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   851     int maxArcId() const { return arcs.size()-1; }
   852 
   853     Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
   854     Node target(Arc e) const { return Node(arcs[e.id].target); }
   855 
   856     Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
   857     Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
   858 
   859     static bool direction(Arc e) {
   860       return (e.id & 1) == 1;
   861     }
   862 
   863     static Arc direct(Edge e, bool d) {
   864       return Arc(e.id * 2 + (d ? 1 : 0));
   865     }
   866 
   867     void first(Node& node) const {
   868       node.id = first_node;
   869     }
   870 
   871     void next(Node& node) const {
   872       node.id = nodes[node.id].next;
   873     }
   874 
   875     void first(Arc& e) const {
   876       int n = first_node;
   877       while (n != -1 && nodes[n].first_out == -1) {
   878         n = nodes[n].next;
   879       }
   880       e.id = (n == -1) ? -1 : nodes[n].first_out;
   881     }
   882 
   883     void next(Arc& e) const {
   884       if (arcs[e.id].next_out != -1) {
   885         e.id = arcs[e.id].next_out;
   886       } else {
   887         int n = nodes[arcs[e.id ^ 1].target].next;
   888         while(n != -1 && nodes[n].first_out == -1) {
   889           n = nodes[n].next;
   890         }
   891         e.id = (n == -1) ? -1 : nodes[n].first_out;
   892       }
   893     }
   894 
   895     void first(Edge& e) const {
   896       int n = first_node;
   897       while (n != -1) {
   898         e.id = nodes[n].first_out;
   899         while ((e.id & 1) != 1) {
   900           e.id = arcs[e.id].next_out;
   901         }
   902         if (e.id != -1) {
   903           e.id /= 2;
   904           return;
   905         }
   906         n = nodes[n].next;
   907       }
   908       e.id = -1;
   909     }
   910 
   911     void next(Edge& e) const {
   912       int n = arcs[e.id * 2].target;
   913       e.id = arcs[(e.id * 2) | 1].next_out;
   914       while ((e.id & 1) != 1) {
   915         e.id = arcs[e.id].next_out;
   916       }
   917       if (e.id != -1) {
   918         e.id /= 2;
   919         return;
   920       }
   921       n = nodes[n].next;
   922       while (n != -1) {
   923         e.id = nodes[n].first_out;
   924         while ((e.id & 1) != 1) {
   925           e.id = arcs[e.id].next_out;
   926         }
   927         if (e.id != -1) {
   928           e.id /= 2;
   929           return;
   930         }
   931         n = nodes[n].next;
   932       }
   933       e.id = -1;
   934     }
   935 
   936     void firstOut(Arc &e, const Node& v) const {
   937       e.id = nodes[v.id].first_out;
   938     }
   939     void nextOut(Arc &e) const {
   940       e.id = arcs[e.id].next_out;
   941     }
   942 
   943     void firstIn(Arc &e, const Node& v) const {
   944       e.id = ((nodes[v.id].first_out) ^ 1);
   945       if (e.id == -2) e.id = -1;
   946     }
   947     void nextIn(Arc &e) const {
   948       e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
   949       if (e.id == -2) e.id = -1;
   950     }
   951 
   952     void firstInc(Edge &e, bool& d, const Node& v) const {
   953       int a = nodes[v.id].first_out;
   954       if (a != -1 ) {
   955         e.id = a / 2;
   956         d = ((a & 1) == 1);
   957       } else {
   958         e.id = -1;
   959         d = true;
   960       }
   961     }
   962     void nextInc(Edge &e, bool& d) const {
   963       int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   964       if (a != -1 ) {
   965         e.id = a / 2;
   966         d = ((a & 1) == 1);
   967       } else {
   968         e.id = -1;
   969         d = true;
   970       }
   971     }
   972 
   973     static int id(Node v) { return v.id; }
   974     static int id(Arc e) { return e.id; }
   975     static int id(Edge e) { return e.id; }
   976 
   977     static Node nodeFromId(int id) { return Node(id);}
   978     static Arc arcFromId(int id) { return Arc(id);}
   979     static Edge edgeFromId(int id) { return Edge(id);}
   980 
   981     bool valid(Node n) const {
   982       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
   983         nodes[n.id].prev != -2;
   984     }
   985 
   986     bool valid(Arc a) const {
   987       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
   988         arcs[a.id].prev_out != -2;
   989     }
   990 
   991     bool valid(Edge e) const {
   992       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
   993         arcs[2 * e.id].prev_out != -2;
   994     }
   995 
   996     Node addNode() {
   997       int n;
   998 
   999       if(first_free_node==-1) {
  1000         n = nodes.size();
  1001         nodes.push_back(NodeT());
  1002       } else {
  1003         n = first_free_node;
  1004         first_free_node = nodes[n].next;
  1005       }
  1006 
  1007       nodes[n].next = first_node;
  1008       if (first_node != -1) nodes[first_node].prev = n;
  1009       first_node = n;
  1010       nodes[n].prev = -1;
  1011 
  1012       nodes[n].first_out = -1;
  1013 
  1014       return Node(n);
  1015     }
  1016 
  1017     Edge addEdge(Node u, Node v) {
  1018       int n;
  1019 
  1020       if (first_free_arc == -1) {
  1021         n = arcs.size();
  1022         arcs.push_back(ArcT());
  1023         arcs.push_back(ArcT());
  1024       } else {
  1025         n = first_free_arc;
  1026         first_free_arc = arcs[n].next_out;
  1027       }
  1028 
  1029       arcs[n].target = u.id;
  1030       arcs[n | 1].target = v.id;
  1031 
  1032       arcs[n].next_out = nodes[v.id].first_out;
  1033       if (nodes[v.id].first_out != -1) {
  1034         arcs[nodes[v.id].first_out].prev_out = n;
  1035       }
  1036       arcs[n].prev_out = -1;
  1037       nodes[v.id].first_out = n;
  1038 
  1039       arcs[n | 1].next_out = nodes[u.id].first_out;
  1040       if (nodes[u.id].first_out != -1) {
  1041         arcs[nodes[u.id].first_out].prev_out = (n | 1);
  1042       }
  1043       arcs[n | 1].prev_out = -1;
  1044       nodes[u.id].first_out = (n | 1);
  1045 
  1046       return Edge(n / 2);
  1047     }
  1048 
  1049     void erase(const Node& node) {
  1050       int n = node.id;
  1051 
  1052       if(nodes[n].next != -1) {
  1053         nodes[nodes[n].next].prev = nodes[n].prev;
  1054       }
  1055 
  1056       if(nodes[n].prev != -1) {
  1057         nodes[nodes[n].prev].next = nodes[n].next;
  1058       } else {
  1059         first_node = nodes[n].next;
  1060       }
  1061 
  1062       nodes[n].next = first_free_node;
  1063       first_free_node = n;
  1064       nodes[n].prev = -2;
  1065     }
  1066 
  1067     void erase(const Edge& edge) {
  1068       int n = edge.id * 2;
  1069 
  1070       if (arcs[n].next_out != -1) {
  1071         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
  1072       }
  1073 
  1074       if (arcs[n].prev_out != -1) {
  1075         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
  1076       } else {
  1077         nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
  1078       }
  1079 
  1080       if (arcs[n | 1].next_out != -1) {
  1081         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
  1082       }
  1083 
  1084       if (arcs[n | 1].prev_out != -1) {
  1085         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
  1086       } else {
  1087         nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
  1088       }
  1089 
  1090       arcs[n].next_out = first_free_arc;
  1091       first_free_arc = n;
  1092       arcs[n].prev_out = -2;
  1093       arcs[n | 1].prev_out = -2;
  1094 
  1095     }
  1096 
  1097     void clear() {
  1098       arcs.clear();
  1099       nodes.clear();
  1100       first_node = first_free_node = first_free_arc = -1;
  1101     }
  1102 
  1103   protected:
  1104 
  1105     void changeTarget(Edge e, Node n) {
  1106       if(arcs[2 * e.id].next_out != -1) {
  1107         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1108       }
  1109       if(arcs[2 * e.id].prev_out != -1) {
  1110         arcs[arcs[2 * e.id].prev_out].next_out =
  1111           arcs[2 * e.id].next_out;
  1112       } else {
  1113         nodes[arcs[(2 * e.id) | 1].target].first_out =
  1114           arcs[2 * e.id].next_out;
  1115       }
  1116 
  1117       if (nodes[n.id].first_out != -1) {
  1118         arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
  1119       }
  1120       arcs[(2 * e.id) | 1].target = n.id;
  1121       arcs[2 * e.id].prev_out = -1;
  1122       arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1123       nodes[n.id].first_out = 2 * e.id;
  1124     }
  1125 
  1126     void changeSource(Edge e, Node n) {
  1127       if(arcs[(2 * e.id) | 1].next_out != -1) {
  1128         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  1129           arcs[(2 * e.id) | 1].prev_out;
  1130       }
  1131       if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1132         arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
  1133           arcs[(2 * e.id) | 1].next_out;
  1134       } else {
  1135         nodes[arcs[2 * e.id].target].first_out =
  1136           arcs[(2 * e.id) | 1].next_out;
  1137       }
  1138 
  1139       if (nodes[n.id].first_out != -1) {
  1140         arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  1141       }
  1142       arcs[2 * e.id].target = n.id;
  1143       arcs[(2 * e.id) | 1].prev_out = -1;
  1144       arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
  1145       nodes[n.id].first_out = ((2 * e.id) | 1);
  1146     }
  1147 
  1148   };
  1149 
  1150   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
  1151 
  1152 
  1153   /// \addtogroup graphs
  1154   /// @{
  1155 
  1156   ///A general undirected graph structure.
  1157 
  1158   ///\ref ListGraph is a simple and fast <em>undirected graph</em>
  1159   ///implementation based on static linked lists that are stored in
  1160   ///\c std::vector structures.
  1161   ///
  1162   ///It conforms to the \ref concepts::Graph "Graph concept" and it
  1163   ///also provides several useful additional functionalities.
  1164   ///Most of the member functions and nested classes are documented
  1165   ///only in the concept class.
  1166   ///
  1167   ///An important extra feature of this graph implementation is that
  1168   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
  1169   ///
  1170   ///\sa concepts::Graph
  1171 
  1172   class ListGraph : public ExtendedListGraphBase {
  1173   private:
  1174     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
  1175 
  1176     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
  1177     ///
  1178     ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
  1179     ///\brief Assignment of ListGraph to another one is \e not allowed.
  1180     ///Use copyGraph() instead.
  1181 
  1182     ///Assignment of ListGraph to another one is \e not allowed.
  1183     ///Use copyGraph() instead.
  1184     void operator=(const ListGraph &) {}
  1185   public:
  1186     /// Constructor
  1187 
  1188     /// Constructor.
  1189     ///
  1190     ListGraph() {}
  1191 
  1192     typedef ExtendedListGraphBase Parent;
  1193 
  1194     typedef Parent::OutArcIt IncEdgeIt;
  1195 
  1196     /// \brief Add a new node to the graph.
  1197     ///
  1198     /// Add a new node to the graph.
  1199     /// \return the new node.
  1200     Node addNode() { return Parent::addNode(); }
  1201 
  1202     /// \brief Add a new edge to the graph.
  1203     ///
  1204     /// Add a new edge to the graph with source node \c s
  1205     /// and target node \c t.
  1206     /// \return the new edge.
  1207     Edge addEdge(const Node& s, const Node& t) {
  1208       return Parent::addEdge(s, t);
  1209     }
  1210     /// Node validity check
  1211 
  1212     /// This function gives back true if the given node is valid,
  1213     /// ie. it is a real node of the graph.
  1214     ///
  1215     /// \warning A Node pointing to a removed item
  1216     /// could become valid again later if new nodes are
  1217     /// added to the graph.
  1218     bool valid(Node n) const { return Parent::valid(n); }
  1219     /// Arc validity check
  1220 
  1221     /// This function gives back true if the given arc is valid,
  1222     /// ie. it is a real arc of the graph.
  1223     ///
  1224     /// \warning An Arc pointing to a removed item
  1225     /// could become valid again later if new edges are
  1226     /// added to the graph.
  1227     bool valid(Arc a) const { return Parent::valid(a); }
  1228     /// Edge validity check
  1229 
  1230     /// This function gives back true if the given edge is valid,
  1231     /// ie. it is a real arc of the graph.
  1232     ///
  1233     /// \warning A Edge pointing to a removed item
  1234     /// could become valid again later if new edges are
  1235     /// added to the graph.
  1236     bool valid(Edge e) const { return Parent::valid(e); }
  1237     /// \brief Change the source of \c e to \c n
  1238     ///
  1239     /// This function changes the source of \c e to \c n.
  1240     ///
  1241     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1242     ///referencing the changed arc remain
  1243     ///valid. However <tt>OutArcIt</tt>s are invalidated.
  1244     ///
  1245     ///\warning This functionality cannot be used together with the
  1246     ///Snapshot feature.
  1247     void changeSource(Edge e, Node n) {
  1248       Parent::changeSource(e,n);
  1249     }
  1250     /// \brief Change the target of \c e to \c n
  1251     ///
  1252     /// This function changes the target of \c e to \c n.
  1253     ///
  1254     /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
  1255     /// valid. However the other iterators may be invalidated.
  1256     ///
  1257     ///\warning This functionality cannot be used together with the
  1258     ///Snapshot feature.
  1259     void changeTarget(Edge e, Node n) {
  1260       Parent::changeTarget(e,n);
  1261     }
  1262     /// \brief Change the source of \c e to \c n
  1263     ///
  1264     /// This function changes the source of \c e to \c n.
  1265     /// It also changes the proper node of the represented edge.
  1266     ///
  1267     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1268     ///referencing the changed arc remain
  1269     ///valid. However <tt>OutArcIt</tt>s are invalidated.
  1270     ///
  1271     ///\warning This functionality cannot be used together with the
  1272     ///Snapshot feature.
  1273     void changeSource(Arc e, Node n) {
  1274       if (Parent::direction(e)) {
  1275         Parent::changeSource(e,n);
  1276       } else {
  1277         Parent::changeTarget(e,n);
  1278       }
  1279     }
  1280     /// \brief Change the target of \c e to \c n
  1281     ///
  1282     /// This function changes the target of \c e to \c n.
  1283     /// It also changes the proper node of the represented edge.
  1284     ///
  1285     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
  1286     ///referencing the changed arc remain
  1287     ///valid. However <tt>InArcIt</tt>s are invalidated.
  1288     ///
  1289     ///\warning This functionality cannot be used together with the
  1290     ///Snapshot feature.
  1291     void changeTarget(Arc e, Node n) {
  1292       if (Parent::direction(e)) {
  1293         Parent::changeTarget(e,n);
  1294       } else {
  1295         Parent::changeSource(e,n);
  1296       }
  1297     }
  1298     /// \brief Contract two nodes.
  1299     ///
  1300     /// This function contracts two nodes.
  1301     /// Node \p b will be removed but instead of deleting
  1302     /// its neighboring arcs, they will be joined to \p a.
  1303     /// The last parameter \p r controls whether to remove loops. \c true
  1304     /// means that loops will be removed.
  1305     ///
  1306     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
  1307     /// valid.
  1308     ///
  1309     ///\warning This functionality cannot be used together with the
  1310     ///Snapshot feature.
  1311     void contract(Node a, Node b, bool r = true) {
  1312       for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1313         IncEdgeIt f = e; ++f;
  1314         if (r && runningNode(e) == a) {
  1315           erase(e);
  1316         } else if (source(e) == b) {
  1317           changeSource(e, a);
  1318         } else {
  1319           changeTarget(e, a);
  1320         }
  1321         e = f;
  1322       }
  1323       erase(b);
  1324     }
  1325 
  1326 
  1327     /// \brief Class to make a snapshot of the graph and restore
  1328     /// it later.
  1329     ///
  1330     /// Class to make a snapshot of the graph and restore it later.
  1331     ///
  1332     /// The newly added nodes and edges can be removed
  1333     /// using the restore() function.
  1334     ///
  1335     /// \warning Edge and node deletions and other modifications
  1336     /// (e.g. changing nodes of edges, contracting nodes) cannot be
  1337     /// restored. These events invalidate the snapshot.
  1338     class Snapshot {
  1339     protected:
  1340 
  1341       typedef Parent::NodeNotifier NodeNotifier;
  1342 
  1343       class NodeObserverProxy : public NodeNotifier::ObserverBase {
  1344       public:
  1345 
  1346         NodeObserverProxy(Snapshot& _snapshot)
  1347           : snapshot(_snapshot) {}
  1348 
  1349         using NodeNotifier::ObserverBase::attach;
  1350         using NodeNotifier::ObserverBase::detach;
  1351         using NodeNotifier::ObserverBase::attached;
  1352 
  1353       protected:
  1354 
  1355         virtual void add(const Node& node) {
  1356           snapshot.addNode(node);
  1357         }
  1358         virtual void add(const std::vector<Node>& nodes) {
  1359           for (int i = nodes.size() - 1; i >= 0; ++i) {
  1360             snapshot.addNode(nodes[i]);
  1361           }
  1362         }
  1363         virtual void erase(const Node& node) {
  1364           snapshot.eraseNode(node);
  1365         }
  1366         virtual void erase(const std::vector<Node>& nodes) {
  1367           for (int i = 0; i < int(nodes.size()); ++i) {
  1368             snapshot.eraseNode(nodes[i]);
  1369           }
  1370         }
  1371         virtual void build() {
  1372           Node node;
  1373           std::vector<Node> nodes;
  1374           for (notifier()->first(node); node != INVALID;
  1375                notifier()->next(node)) {
  1376             nodes.push_back(node);
  1377           }
  1378           for (int i = nodes.size() - 1; i >= 0; --i) {
  1379             snapshot.addNode(nodes[i]);
  1380           }
  1381         }
  1382         virtual void clear() {
  1383           Node node;
  1384           for (notifier()->first(node); node != INVALID;
  1385                notifier()->next(node)) {
  1386             snapshot.eraseNode(node);
  1387           }
  1388         }
  1389 
  1390         Snapshot& snapshot;
  1391       };
  1392 
  1393       class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
  1394       public:
  1395 
  1396         EdgeObserverProxy(Snapshot& _snapshot)
  1397           : snapshot(_snapshot) {}
  1398 
  1399         using EdgeNotifier::ObserverBase::attach;
  1400         using EdgeNotifier::ObserverBase::detach;
  1401         using EdgeNotifier::ObserverBase::attached;
  1402 
  1403       protected:
  1404 
  1405         virtual void add(const Edge& edge) {
  1406           snapshot.addEdge(edge);
  1407         }
  1408         virtual void add(const std::vector<Edge>& edges) {
  1409           for (int i = edges.size() - 1; i >= 0; ++i) {
  1410             snapshot.addEdge(edges[i]);
  1411           }
  1412         }
  1413         virtual void erase(const Edge& edge) {
  1414           snapshot.eraseEdge(edge);
  1415         }
  1416         virtual void erase(const std::vector<Edge>& edges) {
  1417           for (int i = 0; i < int(edges.size()); ++i) {
  1418             snapshot.eraseEdge(edges[i]);
  1419           }
  1420         }
  1421         virtual void build() {
  1422           Edge edge;
  1423           std::vector<Edge> edges;
  1424           for (notifier()->first(edge); edge != INVALID;
  1425                notifier()->next(edge)) {
  1426             edges.push_back(edge);
  1427           }
  1428           for (int i = edges.size() - 1; i >= 0; --i) {
  1429             snapshot.addEdge(edges[i]);
  1430           }
  1431         }
  1432         virtual void clear() {
  1433           Edge edge;
  1434           for (notifier()->first(edge); edge != INVALID;
  1435                notifier()->next(edge)) {
  1436             snapshot.eraseEdge(edge);
  1437           }
  1438         }
  1439 
  1440         Snapshot& snapshot;
  1441       };
  1442 
  1443       ListGraph *graph;
  1444 
  1445       NodeObserverProxy node_observer_proxy;
  1446       EdgeObserverProxy edge_observer_proxy;
  1447 
  1448       std::list<Node> added_nodes;
  1449       std::list<Edge> added_edges;
  1450 
  1451 
  1452       void addNode(const Node& node) {
  1453         added_nodes.push_front(node);
  1454       }
  1455       void eraseNode(const Node& node) {
  1456         std::list<Node>::iterator it =
  1457           std::find(added_nodes.begin(), added_nodes.end(), node);
  1458         if (it == added_nodes.end()) {
  1459           clear();
  1460           edge_observer_proxy.detach();
  1461           throw NodeNotifier::ImmediateDetach();
  1462         } else {
  1463           added_nodes.erase(it);
  1464         }
  1465       }
  1466 
  1467       void addEdge(const Edge& edge) {
  1468         added_edges.push_front(edge);
  1469       }
  1470       void eraseEdge(const Edge& edge) {
  1471         std::list<Edge>::iterator it =
  1472           std::find(added_edges.begin(), added_edges.end(), edge);
  1473         if (it == added_edges.end()) {
  1474           clear();
  1475           node_observer_proxy.detach();
  1476           throw EdgeNotifier::ImmediateDetach();
  1477         } else {
  1478           added_edges.erase(it);
  1479         }
  1480       }
  1481 
  1482       void attach(ListGraph &_graph) {
  1483         graph = &_graph;
  1484         node_observer_proxy.attach(graph->notifier(Node()));
  1485         edge_observer_proxy.attach(graph->notifier(Edge()));
  1486       }
  1487 
  1488       void detach() {
  1489         node_observer_proxy.detach();
  1490         edge_observer_proxy.detach();
  1491       }
  1492 
  1493       bool attached() const {
  1494         return node_observer_proxy.attached();
  1495       }
  1496 
  1497       void clear() {
  1498         added_nodes.clear();
  1499         added_edges.clear();
  1500       }
  1501 
  1502     public:
  1503 
  1504       /// \brief Default constructor.
  1505       ///
  1506       /// Default constructor.
  1507       /// To actually make a snapshot you must call save().
  1508       Snapshot()
  1509         : graph(0), node_observer_proxy(*this),
  1510           edge_observer_proxy(*this) {}
  1511 
  1512       /// \brief Constructor that immediately makes a snapshot.
  1513       ///
  1514       /// This constructor immediately makes a snapshot of the graph.
  1515       /// \param _graph The graph we make a snapshot of.
  1516       Snapshot(ListGraph &_graph)
  1517         : node_observer_proxy(*this),
  1518           edge_observer_proxy(*this) {
  1519         attach(_graph);
  1520       }
  1521 
  1522       /// \brief Make a snapshot.
  1523       ///
  1524       /// Make a snapshot of the graph.
  1525       ///
  1526       /// This function can be called more than once. In case of a repeated
  1527       /// call, the previous snapshot gets lost.
  1528       /// \param _graph The graph we make the snapshot of.
  1529       void save(ListGraph &_graph) {
  1530         if (attached()) {
  1531           detach();
  1532           clear();
  1533         }
  1534         attach(_graph);
  1535       }
  1536 
  1537       /// \brief Undo the changes until the last snapshot.
  1538       //
  1539       /// Undo the changes until the last snapshot created by save().
  1540       void restore() {
  1541         detach();
  1542         for(std::list<Edge>::iterator it = added_edges.begin();
  1543             it != added_edges.end(); ++it) {
  1544           graph->erase(*it);
  1545         }
  1546         for(std::list<Node>::iterator it = added_nodes.begin();
  1547             it != added_nodes.end(); ++it) {
  1548           graph->erase(*it);
  1549         }
  1550         clear();
  1551       }
  1552 
  1553       /// \brief Gives back true when the snapshot is valid.
  1554       ///
  1555       /// Gives back true when the snapshot is valid.
  1556       bool valid() const {
  1557         return attached();
  1558       }
  1559     };
  1560   };
  1561 
  1562   /// @}
  1563 } //namespace lemon
  1564 
  1565 
  1566 #endif