COIN-OR::LEMON - Graph Library

source: lemon/lemon/list_graph.h @ 629:7a28e215f715

Last change on this file since 629:7a28e215f715 was 629:7a28e215f715, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Remove notes about reference maps as extra features (#190)

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