COIN-OR::LEMON - Graph Library

source: lemon/lemon/list_graph.h @ 222:f9a18c21dba8

Last change on this file since 222:f9a18c21dba8 was 220:a5d8c039f218, checked in by Balazs Dezso <deba@…>, 13 years ago

Reorganize header files (Ticket #97)

In addition on some places the DefaultMap?<G, K, V> is replaced with
ItemSetTraits?<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.

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