COIN-OR::LEMON - Graph Library

source: lemon/lemon/list_graph.h @ 788:10c9c3a35b83

Last change on this file since 788:10c9c3a35b83 was 788:10c9c3a35b83, checked in by Alpar Juttner <alpar@…>, 15 years ago

Merge

File size: 44.0 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 ListDigraph;
36
37  class ListDigraphBase {
38
39  protected:
40    struct NodeT {
41      int first_in, first_out;
42      int prev, next;
43    };
44
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;
60
61  public:
62
63    typedef ListDigraphBase Digraph;
64
65    class Node {
66      friend class ListDigraphBase;
67      friend class ListDigraph;
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;
83      friend class ListDigraph;
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),
101        first_free_node(-1), arcs(), first_free_arc(-1) {}
102
103
104    int maxNodeId() const { return nodes.size()-1; }
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
111    void first(Node& node) const {
112      node.id = first_node;
113    }
114
115    void next(Node& node) const {
116      node.id = nodes[node.id].next;
117    }
118
119
120    void first(Arc& arc) const {
121      int n;
122      for(n = first_node;
123          n != -1 && nodes[n].first_out == -1;
124          n = nodes[n].next) {}
125      arc.id = (n == -1) ? -1 : nodes[n].first_out;
126    }
127
128    void next(Arc& arc) const {
129      if (arcs[arc.id].next_out != -1) {
130        arc.id = arcs[arc.id].next_out;
131      } else {
132        int n;
133        for(n = nodes[arcs[arc.id].source].next;
134            n != -1 && nodes[n].first_out == -1;
135            n = nodes[n].next) {}
136        arc.id = (n == -1) ? -1 : nodes[n].first_out;
137      }
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
154
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
161    bool valid(Node n) const {
162      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
163        nodes[n.id].prev != -2;
164    }
165
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;
169    }
170
171    Node addNode() {
172      int n;
173
174      if(first_free_node==-1) {
175        n = nodes.size();
176        nodes.push_back(NodeT());
177      } else {
178        n = first_free_node;
179        first_free_node = nodes[n].next;
180      }
181
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;
186
187      nodes[n].first_in = nodes[n].first_out = -1;
188
189      return Node(n);
190    }
191
192    Arc addArc(Node u, Node v) {
193      int n;
194
195      if (first_free_arc == -1) {
196        n = arcs.size();
197        arcs.push_back(ArcT());
198      } else {
199        n = first_free_arc;
200        first_free_arc = arcs[n].next_in;
201      }
202
203      arcs[n].source = u.id;
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) {
208        arcs[nodes[u.id].first_out].prev_out = n;
209      }
210
211      arcs[n].next_in = nodes[v.id].first_in;
212      if(nodes[v.id].first_in != -1) {
213        arcs[nodes[v.id].first_in].prev_in = n;
214      }
215
216      arcs[n].prev_in = arcs[n].prev_out = -1;
217
218      nodes[u.id].first_out = nodes[v.id].first_in = n;
219
220      return Arc(n);
221    }
222
223    void erase(const Node& node) {
224      int n = node.id;
225
226      if(nodes[n].next != -1) {
227        nodes[nodes[n].next].prev = nodes[n].prev;
228      }
229
230      if(nodes[n].prev != -1) {
231        nodes[nodes[n].prev].next = nodes[n].next;
232      } else {
233        first_node = nodes[n].next;
234      }
235
236      nodes[n].next = first_free_node;
237      first_free_node = n;
238      nodes[n].prev = -2;
239
240    }
241
242    void erase(const Arc& arc) {
243      int n = arc.id;
244
245      if(arcs[n].next_in!=-1) {
246        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
247      }
248
249      if(arcs[n].prev_in!=-1) {
250        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
251      } else {
252        nodes[arcs[n].target].first_in = arcs[n].next_in;
253      }
254
255
256      if(arcs[n].next_out!=-1) {
257        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
258      }
259
260      if(arcs[n].prev_out!=-1) {
261        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
262      } else {
263        nodes[arcs[n].source].first_out = arcs[n].next_out;
264      }
265
266      arcs[n].next_in = first_free_arc;
267      first_free_arc = n;
268      arcs[n].prev_in = -2;
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:
278    void changeTarget(Arc e, Node n)
279    {
280      if(arcs[e.id].next_in != -1)
281        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
282      if(arcs[e.id].prev_in != -1)
283        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
284      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
285      if (nodes[n.id].first_in != -1) {
286        arcs[nodes[n.id].first_in].prev_in = e.id;
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    }
293    void changeSource(Arc e, Node n)
294    {
295      if(arcs[e.id].next_out != -1)
296        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
297      if(arcs[e.id].prev_out != -1)
298        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
299      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
300      if (nodes[n.id].first_out != -1) {
301        arcs[nodes[n.id].first_out].prev_out = e.id;
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
313  /// \addtogroup graphs
314  /// @{
315
316  ///A general directed graph structure.
317
318  ///\ref ListDigraph is a versatile and fast directed graph
319  ///implementation based on linked lists that are stored in
320  ///\c std::vector structures.
321  ///
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
325  ///only in the concept class.
326  ///
327  ///\sa concepts::Digraph
328  ///\sa ListGraph
329  class ListDigraph : public ExtendedListDigraphBase {
330    typedef ExtendedListDigraphBase Parent;
331
332  private:
333    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
334    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
335    /// \brief Assignment of a digraph to another one is \e not allowed.
336    /// Use DigraphCopy instead.
337    void operator=(const ListDigraph &) {}
338  public:
339
340    /// Constructor
341
342    /// Constructor.
343    ///
344    ListDigraph() {}
345
346    ///Add a new node to the digraph.
347
348    ///This function adds a new node to the digraph.
349    ///\return The new node.
350    Node addNode() { return Parent::addNode(); }
351
352    ///Add a new arc to the digraph.
353
354    ///This function adds a new arc to the digraph with source node \c s
355    ///and target node \c t.
356    ///\return The new arc.
357    Arc addArc(Node s, Node t) {
358      return Parent::addArc(s, t);
359    }
360
361    ///\brief Erase a node from the digraph.
362    ///
363    ///This function erases the given node from the digraph.
364    void erase(Node n) { Parent::erase(n); }
365
366    ///\brief Erase an arc from the digraph.
367    ///
368    ///This function erases the given arc from the digraph.
369    void erase(Arc a) { Parent::erase(a); }
370
371    /// Node validity check
372
373    /// This function gives back \c true if the given node is valid,
374    /// i.e. it is a real node of the digraph.
375    ///
376    /// \warning A removed node could become valid again if new nodes are
377    /// added to the digraph.
378    bool valid(Node n) const { return Parent::valid(n); }
379
380    /// Arc validity check
381
382    /// This function gives back \c true if the given arc is valid,
383    /// i.e. it is a real arc of the digraph.
384    ///
385    /// \warning A removed arc could become valid again if new arcs are
386    /// added to the digraph.
387    bool valid(Arc a) const { return Parent::valid(a); }
388
389    /// Change the target node of an arc
390
391    /// This function changes the target node of the given arc \c a to \c n.
392    ///
393    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
394    ///arc remain valid, however \c InArcIt iterators are invalidated.
395    ///
396    ///\warning This functionality cannot be used together with the Snapshot
397    ///feature.
398    void changeTarget(Arc a, Node n) {
399      Parent::changeTarget(a,n);
400    }
401    /// Change the source node of an arc
402
403    /// This function changes the source node of the given arc \c a to \c n.
404    ///
405    ///\note \c InArcIt iterators referencing the changed arc remain
406    ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
407    ///
408    ///\warning This functionality cannot be used together with the Snapshot
409    ///feature.
410    void changeSource(Arc a, Node n) {
411      Parent::changeSource(a,n);
412    }
413
414    /// Reverse the direction of an arc.
415
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.
419    ///
420    ///\warning This functionality cannot be used together with the Snapshot
421    ///feature.
422    void reverseArc(Arc a) {
423      Node t=target(a);
424      changeTarget(a,source(a));
425      changeSource(a,t);
426    }
427
428    ///Contract two nodes.
429
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.
435    ///
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.
442    ///
443    ///\warning This functionality cannot be used together with the Snapshot
444    ///feature.
445    void contract(Node u, Node v, bool r = true)
446    {
447      for(OutArcIt e(*this,v);e!=INVALID;) {
448        OutArcIt f=e;
449        ++f;
450        if(r && target(e)==u) erase(e);
451        else changeSource(e,u);
452        e=f;
453      }
454      for(InArcIt e(*this,v);e!=INVALID;) {
455        InArcIt f=e;
456        ++f;
457        if(r && source(e)==u) erase(e);
458        else changeTarget(e,u);
459        e=f;
460      }
461      erase(v);
462    }
463
464    ///Split a node.
465
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.
472    ///\return The newly created node.
473    ///
474    ///\note All iterators remain valid.
475    ///
476    ///\warning This functionality cannot be used together with the
477    ///Snapshot feature.
478    Node split(Node n, bool connect = true) {
479      Node b = addNode();
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;
484      }
485      if (connect) addArc(n,b);
486      return b;
487    }
488
489    ///Split an arc.
490
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.
496    ///
497    ///\note \c InArcIt iterators referencing the original arc are
498    ///invalidated. Other iterators remain valid.
499    ///
500    ///\warning This functionality cannot be used together with the
501    ///Snapshot feature.
502    Node split(Arc a) {
503      Node v = addNode();
504      addArc(v,target(a));
505      changeTarget(a,v);
506      return v;
507    }
508
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
537    /// \brief Class to make a snapshot of the digraph and restore
538    /// it later.
539    ///
540    /// Class to make a snapshot of the digraph and restore it later.
541    ///
542    /// The newly added nodes and arcs can be removed using the
543    /// restore() function.
544    ///
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
551    /// restored. These events invalidate the snapshot.
552    /// However the arcs and nodes that were added to the digraph after
553    /// making the current snapshot can be removed without invalidating it.
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;
568
569      protected:
570
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;
590          for (notifier()->first(node); node != INVALID;
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;
600          for (notifier()->first(node); node != INVALID;
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;
618
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;
640          for (notifier()->first(arc); arc != INVALID;
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;
650          for (notifier()->first(arc); arc != INVALID;
651               notifier()->next(arc)) {
652            snapshot.eraseArc(arc);
653          }
654        }
655
656        Snapshot& snapshot;
657      };
658
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) {
669        added_nodes.push_front(node);
670      }
671      void eraseNode(const Node& node) {
672        std::list<Node>::iterator it =
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) {
684        added_arcs.push_front(arc);
685      }
686      void eraseArc(const Arc& arc) {
687        std::list<Arc>::iterator it =
688          std::find(added_arcs.begin(), added_arcs.end(), arc);
689        if (it == added_arcs.end()) {
690          clear();
691          node_observer_proxy.detach();
692          throw ArcNotifier::ImmediateDetach();
693        } else {
694          added_arcs.erase(it);
695        }
696      }
697
698      void attach(ListDigraph &_digraph) {
699        digraph = &_digraph;
700        node_observer_proxy.attach(digraph->notifier(Node()));
701        arc_observer_proxy.attach(digraph->notifier(Arc()));
702      }
703
704      void detach() {
705        node_observer_proxy.detach();
706        arc_observer_proxy.detach();
707      }
708
709      bool attached() const {
710        return node_observer_proxy.attached();
711      }
712
713      void clear() {
714        added_nodes.clear();
715        added_arcs.clear();
716      }
717
718    public:
719
720      /// \brief Default constructor.
721      ///
722      /// Default constructor.
723      /// You have to call save() to actually make a snapshot.
724      Snapshot()
725        : digraph(0), node_observer_proxy(*this),
726          arc_observer_proxy(*this) {}
727
728      /// \brief Constructor that immediately makes a snapshot.
729      ///
730      /// This constructor immediately makes a snapshot of the given digraph.
731      Snapshot(ListDigraph &gr)
732        : node_observer_proxy(*this),
733          arc_observer_proxy(*this) {
734        attach(gr);
735      }
736
737      /// \brief Make a snapshot.
738      ///
739      /// This function makes a snapshot of the given digraph.
740      /// It can be called more than once. In case of a repeated
741      /// call, the previous snapshot gets lost.
742      void save(ListDigraph &gr) {
743        if (attached()) {
744          detach();
745          clear();
746        }
747        attach(gr);
748      }
749
750      /// \brief Undo the changes until the last snapshot.
751      ///
752      /// This function undos the changes until the last snapshot
753      /// created by save() or Snapshot(ListDigraph&).
754      ///
755      /// \warning This method invalidates the snapshot, i.e. repeated
756      /// restoring is not supported unless you call save() again.
757      void restore() {
758        detach();
759        for(std::list<Arc>::iterator it = added_arcs.begin();
760            it != added_arcs.end(); ++it) {
761          digraph->erase(*it);
762        }
763        for(std::list<Node>::iterator it = added_nodes.begin();
764            it != added_nodes.end(); ++it) {
765          digraph->erase(*it);
766        }
767        clear();
768      }
769
770      /// \brief Returns \c true if the snapshot is valid.
771      ///
772      /// This function returns \c true if the snapshot is valid.
773      bool valid() const {
774        return attached();
775      }
776    };
777
778  };
779
780  ///@}
781
782  class ListGraphBase {
783
784  protected:
785
786    struct NodeT {
787      int first_out;
788      int prev, next;
789    };
790
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;
805
806  public:
807
808    typedef ListGraphBase Graph;
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; }
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;}
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:
848      operator Edge() const {
849        return id != -1 ? edgeFromId(id / 2) : INVALID;
850      }
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),
861        first_free_node(-1), arcs(), first_free_arc(-1) {}
862
863
864    int maxNodeId() const { return nodes.size()-1; }
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
882    void first(Node& node) const {
883      node.id = first_node;
884    }
885
886    void next(Node& node) const {
887      node.id = nodes[node.id].next;
888    }
889
890    void first(Arc& e) const {
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) {
900        e.id = arcs[e.id].next_out;
901      } else {
902        int n = nodes[arcs[e.id ^ 1].target].next;
903        while(n != -1 && nodes[n].first_out == -1) {
904          n = nodes[n].next;
905        }
906        e.id = (n == -1) ? -1 : nodes[n].first_out;
907      }
908    }
909
910    void first(Edge& e) const {
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;
920        }
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;
935      }
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;
945        }
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 {
968      int a = nodes[v.id].first_out;
969      if (a != -1 ) {
970        e.id = a / 2;
971        d = ((a & 1) == 1);
972      } else {
973        e.id = -1;
974        d = true;
975      }
976    }
977    void nextInc(Edge &e, bool& d) const {
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);
982      } else {
983        e.id = -1;
984        d = true;
985      }
986    }
987
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
996    bool valid(Node n) const {
997      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
998        nodes[n.id].prev != -2;
999    }
1000
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;
1004    }
1005
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;
1009    }
1010
1011    Node addNode() {
1012      int n;
1013
1014      if(first_free_node==-1) {
1015        n = nodes.size();
1016        nodes.push_back(NodeT());
1017      } else {
1018        n = first_free_node;
1019        first_free_node = nodes[n].next;
1020      }
1021
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;
1026
1027      nodes[n].first_out = -1;
1028
1029      return Node(n);
1030    }
1031
1032    Edge addEdge(Node u, Node v) {
1033      int n;
1034
1035      if (first_free_arc == -1) {
1036        n = arcs.size();
1037        arcs.push_back(ArcT());
1038        arcs.push_back(ArcT());
1039      } else {
1040        n = first_free_arc;
1041        first_free_arc = arcs[n].next_out;
1042      }
1043
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) {
1049        arcs[nodes[v.id].first_out].prev_out = n;
1050      }
1051      arcs[n].prev_out = -1;
1052      nodes[v.id].first_out = n;
1053
1054      arcs[n | 1].next_out = nodes[u.id].first_out;
1055      if (nodes[u.id].first_out != -1) {
1056        arcs[nodes[u.id].first_out].prev_out = (n | 1);
1057      }
1058      arcs[n | 1].prev_out = -1;
1059      nodes[u.id].first_out = (n | 1);
1060
1061      return Edge(n / 2);
1062    }
1063
1064    void erase(const Node& node) {
1065      int n = node.id;
1066
1067      if(nodes[n].next != -1) {
1068        nodes[nodes[n].next].prev = nodes[n].prev;
1069      }
1070
1071      if(nodes[n].prev != -1) {
1072        nodes[nodes[n].prev].next = nodes[n].next;
1073      } else {
1074        first_node = nodes[n].next;
1075      }
1076
1077      nodes[n].next = first_free_node;
1078      first_free_node = n;
1079      nodes[n].prev = -2;
1080    }
1081
1082    void erase(const Edge& edge) {
1083      int n = edge.id * 2;
1084
1085      if (arcs[n].next_out != -1) {
1086        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1087      }
1088
1089      if (arcs[n].prev_out != -1) {
1090        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1091      } else {
1092        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1093      }
1094
1095      if (arcs[n | 1].next_out != -1) {
1096        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1097      }
1098
1099      if (arcs[n | 1].prev_out != -1) {
1100        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1101      } else {
1102        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1103      }
1104
1105      arcs[n].next_out = first_free_arc;
1106      first_free_arc = n;
1107      arcs[n].prev_out = -2;
1108      arcs[n | 1].prev_out = -2;
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
1120    void changeV(Edge e, Node n) {
1121      if(arcs[2 * e.id].next_out != -1) {
1122        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1123      }
1124      if(arcs[2 * e.id].prev_out != -1) {
1125        arcs[arcs[2 * e.id].prev_out].next_out =
1126          arcs[2 * e.id].next_out;
1127      } else {
1128        nodes[arcs[(2 * e.id) | 1].target].first_out =
1129          arcs[2 * e.id].next_out;
1130      }
1131
1132      if (nodes[n.id].first_out != -1) {
1133        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
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
1141    void changeU(Edge e, Node n) {
1142      if(arcs[(2 * e.id) | 1].next_out != -1) {
1143        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1144          arcs[(2 * e.id) | 1].prev_out;
1145      }
1146      if(arcs[(2 * e.id) | 1].prev_out != -1) {
1147        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1148          arcs[(2 * e.id) | 1].next_out;
1149      } else {
1150        nodes[arcs[2 * e.id].target].first_out =
1151          arcs[(2 * e.id) | 1].next_out;
1152      }
1153
1154      if (nodes[n.id].first_out != -1) {
1155        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
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
1168  /// \addtogroup graphs
1169  /// @{
1170
1171  ///A general undirected graph structure.
1172
1173  ///\ref ListGraph is a versatile and fast undirected graph
1174  ///implementation based on linked lists that are stored in
1175  ///\c std::vector structures.
1176  ///
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
1180  ///only in the concept class.
1181  ///
1182  ///\sa concepts::Graph
1183  ///\sa ListDigraph
1184  class ListGraph : public ExtendedListGraphBase {
1185    typedef ExtendedListGraphBase Parent;
1186
1187  private:
1188    /// Graphs are \e not copy constructible. Use GraphCopy instead.
1189    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
1190    /// \brief Assignment of a graph to another one is \e not allowed.
1191    /// Use GraphCopy instead.
1192    void operator=(const ListGraph &) {}
1193  public:
1194    /// Constructor
1195
1196    /// Constructor.
1197    ///
1198    ListGraph() {}
1199
1200    typedef Parent::OutArcIt IncEdgeIt;
1201
1202    /// \brief Add a new node to the graph.
1203    ///
1204    /// This function adds a new node to the graph.
1205    /// \return The new node.
1206    Node addNode() { return Parent::addNode(); }
1207
1208    /// \brief Add a new edge to the graph.
1209    ///
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.
1213    /// \return The new edge.
1214    Edge addEdge(Node u, Node v) {
1215      return Parent::addEdge(u, v);
1216    }
1217
1218    ///\brief Erase a node from the graph.
1219    ///
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.
1224    ///
1225    /// This function erases the given edge from the graph.
1226    void erase(Edge e) { Parent::erase(e); }
1227    /// Node validity check
1228
1229    /// This function gives back \c true if the given node is valid,
1230    /// i.e. it is a real node of the graph.
1231    ///
1232    /// \warning A removed node could become valid again if new nodes are
1233    /// added to the graph.
1234    bool valid(Node n) const { return Parent::valid(n); }
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); }
1243    /// Arc validity check
1244
1245    /// This function gives back \c true if the given arc is valid,
1246    /// i.e. it is a real arc of the graph.
1247    ///
1248    /// \warning A removed arc could become valid again if new edges are
1249    /// added to the graph.
1250    bool valid(Arc a) const { return Parent::valid(a); }
1251
1252    /// \brief Change the first node of an edge.
1253    ///
1254    /// This function changes the first node of the given edge \c e to \c n.
1255    ///
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.
1259    ///
1260    ///\warning This functionality cannot be used together with the
1261    ///Snapshot feature.
1262    void changeU(Edge e, Node n) {
1263      Parent::changeU(e,n);
1264    }
1265    /// \brief Change the second node of an edge.
1266    ///
1267    /// This function changes the second node of the given edge \c e to \c n.
1268    ///
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.
1273    ///
1274    ///\warning This functionality cannot be used together with the
1275    ///Snapshot feature.
1276    void changeV(Edge e, Node n) {
1277      Parent::changeV(e,n);
1278    }
1279
1280    /// \brief Contract two nodes.
1281    ///
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.
1287    ///
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.
1293    ///
1294    ///\warning This functionality cannot be used together with the
1295    ///Snapshot feature.
1296    void contract(Node a, Node b, bool r = true) {
1297      for(IncEdgeIt e(*this, b); e!=INVALID;) {
1298        IncEdgeIt f = e; ++f;
1299        if (r && runningNode(e) == a) {
1300          erase(e);
1301        } else if (u(e) == b) {
1302          changeU(e, a);
1303        } else {
1304          changeV(e, a);
1305        }
1306        e = f;
1307      }
1308      erase(b);
1309    }
1310
1311    ///Clear the graph.
1312
1313    ///This function erases all nodes and arcs from the graph.
1314    ///
1315    void clear() {
1316      Parent::clear();
1317    }
1318
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
1339    /// \brief Class to make a snapshot of the graph and restore
1340    /// it later.
1341    ///
1342    /// Class to make a snapshot of the graph and restore it later.
1343    ///
1344    /// The newly added nodes and edges can be removed
1345    /// using the restore() function.
1346    ///
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.
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;
1370
1371      protected:
1372
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;
1392          for (notifier()->first(node); node != INVALID;
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;
1402          for (notifier()->first(node); node != INVALID;
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;
1420
1421      protected:
1422
1423        virtual void add(const Edge& edge) {
1424          snapshot.addEdge(edge);
1425        }
1426        virtual void add(const std::vector<Edge>& edges) {
1427          for (int i = edges.size() - 1; i >= 0; ++i) {
1428            snapshot.addEdge(edges[i]);
1429          }
1430        }
1431        virtual void erase(const Edge& edge) {
1432          snapshot.eraseEdge(edge);
1433        }
1434        virtual void erase(const std::vector<Edge>& edges) {
1435          for (int i = 0; i < int(edges.size()); ++i) {
1436            snapshot.eraseEdge(edges[i]);
1437          }
1438        }
1439        virtual void build() {
1440          Edge edge;
1441          std::vector<Edge> edges;
1442          for (notifier()->first(edge); edge != INVALID;
1443               notifier()->next(edge)) {
1444            edges.push_back(edge);
1445          }
1446          for (int i = edges.size() - 1; i >= 0; --i) {
1447            snapshot.addEdge(edges[i]);
1448          }
1449        }
1450        virtual void clear() {
1451          Edge edge;
1452          for (notifier()->first(edge); edge != INVALID;
1453               notifier()->next(edge)) {
1454            snapshot.eraseEdge(edge);
1455          }
1456        }
1457
1458        Snapshot& snapshot;
1459      };
1460
1461      ListGraph *graph;
1462
1463      NodeObserverProxy node_observer_proxy;
1464      EdgeObserverProxy edge_observer_proxy;
1465
1466      std::list<Node> added_nodes;
1467      std::list<Edge> added_edges;
1468
1469
1470      void addNode(const Node& node) {
1471        added_nodes.push_front(node);
1472      }
1473      void eraseNode(const Node& node) {
1474        std::list<Node>::iterator it =
1475          std::find(added_nodes.begin(), added_nodes.end(), node);
1476        if (it == added_nodes.end()) {
1477          clear();
1478          edge_observer_proxy.detach();
1479          throw NodeNotifier::ImmediateDetach();
1480        } else {
1481          added_nodes.erase(it);
1482        }
1483      }
1484
1485      void addEdge(const Edge& edge) {
1486        added_edges.push_front(edge);
1487      }
1488      void eraseEdge(const Edge& edge) {
1489        std::list<Edge>::iterator it =
1490          std::find(added_edges.begin(), added_edges.end(), edge);
1491        if (it == added_edges.end()) {
1492          clear();
1493          node_observer_proxy.detach();
1494          throw EdgeNotifier::ImmediateDetach();
1495        } else {
1496          added_edges.erase(it);
1497        }
1498      }
1499
1500      void attach(ListGraph &_graph) {
1501        graph = &_graph;
1502        node_observer_proxy.attach(graph->notifier(Node()));
1503        edge_observer_proxy.attach(graph->notifier(Edge()));
1504      }
1505
1506      void detach() {
1507        node_observer_proxy.detach();
1508        edge_observer_proxy.detach();
1509      }
1510
1511      bool attached() const {
1512        return node_observer_proxy.attached();
1513      }
1514
1515      void clear() {
1516        added_nodes.clear();
1517        added_edges.clear();
1518      }
1519
1520    public:
1521
1522      /// \brief Default constructor.
1523      ///
1524      /// Default constructor.
1525      /// You have to call save() to actually make a snapshot.
1526      Snapshot()
1527        : graph(0), node_observer_proxy(*this),
1528          edge_observer_proxy(*this) {}
1529
1530      /// \brief Constructor that immediately makes a snapshot.
1531      ///
1532      /// This constructor immediately makes a snapshot of the given graph.
1533      Snapshot(ListGraph &gr)
1534        : node_observer_proxy(*this),
1535          edge_observer_proxy(*this) {
1536        attach(gr);
1537      }
1538
1539      /// \brief Make a snapshot.
1540      ///
1541      /// This function makes a snapshot of the given graph.
1542      /// It can be called more than once. In case of a repeated
1543      /// call, the previous snapshot gets lost.
1544      void save(ListGraph &gr) {
1545        if (attached()) {
1546          detach();
1547          clear();
1548        }
1549        attach(gr);
1550      }
1551
1552      /// \brief Undo the changes until the last snapshot.
1553      ///
1554      /// This function undos the changes until the last snapshot
1555      /// created by save() or Snapshot(ListGraph&).
1556      ///
1557      /// \warning This method invalidates the snapshot, i.e. repeated
1558      /// restoring is not supported unless you call save() again.
1559      void restore() {
1560        detach();
1561        for(std::list<Edge>::iterator it = added_edges.begin();
1562            it != added_edges.end(); ++it) {
1563          graph->erase(*it);
1564        }
1565        for(std::list<Node>::iterator it = added_nodes.begin();
1566            it != added_nodes.end(); ++it) {
1567          graph->erase(*it);
1568        }
1569        clear();
1570      }
1571
1572      /// \brief Returns \c true if the snapshot is valid.
1573      ///
1574      /// This function returns \c true if the snapshot is valid.
1575      bool valid() const {
1576        return attached();
1577      }
1578    };
1579  };
1580
1581  /// @}
1582} //namespace lemon
1583
1584
1585#endif
Note: See TracBrowser for help on using the repository browser.