COIN-OR::LEMON - Graph Library

source: lemon/lemon/list_graph.h @ 280:e7f8647ce760

Last change on this file since 280:e7f8647ce760 was 280:e7f8647ce760, checked in by Alpar Juttner <alpar@…>, 16 years ago

Remove todo-s and convert them to trac tickets

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