COIN-OR::LEMON - Graph Library

source: lemon/lemon/list_graph.h @ 783:2e20aad15754

Last change on this file since 783:2e20aad15754 was 783:2e20aad15754, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Add reserve functions to ListGraph? and SmartGraph? (#311)
ListDigraph? and SmartDigraph? already have such functions.

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