COIN-OR::LEMON - Graph Library

source: lemon/lemon/list_graph.h @ 238:79643f6e8c52

Last change on this file since 238:79643f6e8c52 was 238:79643f6e8c52, checked in by Balazs Dezso <deba@…>, 16 years ago

Converting INVALID arc to INVALID edge

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