COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/list_graph.h @ 740:819ca5b50de0

Last change on this file since 740:819ca5b50de0 was 740:819ca5b50de0, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Add a warning for List(Di)Graph::Snapshot (#311)
and extend tests for snapshots

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