COIN-OR::LEMON - Graph Library

source: lemon/lemon/list_graph.h @ 664:4137ef9aacc6

Last change on this file since 664:4137ef9aacc6 was 664:4137ef9aacc6, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Fix and uniform the usage of Graph and Parent typedefs (#268)

  • Rename Graph typedefs to GraphType? in the implementation of graph maps and MapExtender? to prevent conflicts (especially using VS). They are not public.
  • Make Parent typedefs private in all classes.
  • Replace Digraph with Graph in some places (fix faulty renamings of the script).
  • Use Graph and Digraph typedefs (more) consequently.
File size: 41.7 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_LIST_GRAPH_H
20#define LEMON_LIST_GRAPH_H
21
22///\ingroup graphs
23///\file
24///\brief ListDigraph, ListGraph classes.
25
26#include <lemon/core.h>
27#include <lemon/error.h>
28#include <lemon/bits/graph_extender.h>
29
30#include <vector>
31#include <list>
32
33namespace lemon {
34
35  class ListDigraphBase {
36
37  protected:
38    struct NodeT {
39      int first_in, first_out;
40      int prev, next;
41    };
42
43    struct ArcT {
44      int target, source;
45      int prev_in, prev_out;
46      int next_in, next_out;
47    };
48
49    std::vector<NodeT> nodes;
50
51    int first_node;
52
53    int first_free_node;
54
55    std::vector<ArcT> arcs;
56
57    int first_free_arc;
58
59  public:
60
61    typedef ListDigraphBase Digraph;
62
63    class Node {
64      friend class ListDigraphBase;
65    protected:
66
67      int id;
68      explicit Node(int pid) { id = pid;}
69
70    public:
71      Node() {}
72      Node (Invalid) { id = -1; }
73      bool operator==(const Node& node) const {return id == node.id;}
74      bool operator!=(const Node& node) const {return id != node.id;}
75      bool operator<(const Node& node) const {return id < node.id;}
76    };
77
78    class Arc {
79      friend class ListDigraphBase;
80    protected:
81
82      int id;
83      explicit Arc(int pid) { id = pid;}
84
85    public:
86      Arc() {}
87      Arc (Invalid) { id = -1; }
88      bool operator==(const Arc& arc) const {return id == arc.id;}
89      bool operator!=(const Arc& arc) const {return id != arc.id;}
90      bool operator<(const Arc& arc) const {return id < arc.id;}
91    };
92
93
94
95    ListDigraphBase()
96      : nodes(), first_node(-1),
97        first_free_node(-1), arcs(), first_free_arc(-1) {}
98
99
100    int maxNodeId() const { return nodes.size()-1; }
101    int maxArcId() const { return arcs.size()-1; }
102
103    Node source(Arc e) const { return Node(arcs[e.id].source); }
104    Node target(Arc e) const { return Node(arcs[e.id].target); }
105
106
107    void first(Node& node) const {
108      node.id = first_node;
109    }
110
111    void next(Node& node) const {
112      node.id = nodes[node.id].next;
113    }
114
115
116    void first(Arc& arc) const {
117      int n;
118      for(n = first_node;
119          n!=-1 && nodes[n].first_in == -1;
120          n = nodes[n].next) {}
121      arc.id = (n == -1) ? -1 : nodes[n].first_in;
122    }
123
124    void next(Arc& arc) const {
125      if (arcs[arc.id].next_in != -1) {
126        arc.id = arcs[arc.id].next_in;
127      } else {
128        int n;
129        for(n = nodes[arcs[arc.id].target].next;
130            n!=-1 && nodes[n].first_in == -1;
131            n = nodes[n].next) {}
132        arc.id = (n == -1) ? -1 : nodes[n].first_in;
133      }
134    }
135
136    void firstOut(Arc &e, const Node& v) const {
137      e.id = nodes[v.id].first_out;
138    }
139    void nextOut(Arc &e) const {
140      e.id=arcs[e.id].next_out;
141    }
142
143    void firstIn(Arc &e, const Node& v) const {
144      e.id = nodes[v.id].first_in;
145    }
146    void nextIn(Arc &e) const {
147      e.id=arcs[e.id].next_in;
148    }
149
150
151    static int id(Node v) { return v.id; }
152    static int id(Arc e) { return e.id; }
153
154    static Node nodeFromId(int id) { return Node(id);}
155    static Arc arcFromId(int id) { return Arc(id);}
156
157    bool valid(Node n) const {
158      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
159        nodes[n.id].prev != -2;
160    }
161
162    bool valid(Arc a) const {
163      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
164        arcs[a.id].prev_in != -2;
165    }
166
167    Node addNode() {
168      int n;
169
170      if(first_free_node==-1) {
171        n = nodes.size();
172        nodes.push_back(NodeT());
173      } else {
174        n = first_free_node;
175        first_free_node = nodes[n].next;
176      }
177
178      nodes[n].next = first_node;
179      if(first_node != -1) nodes[first_node].prev = n;
180      first_node = n;
181      nodes[n].prev = -1;
182
183      nodes[n].first_in = nodes[n].first_out = -1;
184
185      return Node(n);
186    }
187
188    Arc addArc(Node u, Node v) {
189      int n;
190
191      if (first_free_arc == -1) {
192        n = arcs.size();
193        arcs.push_back(ArcT());
194      } else {
195        n = first_free_arc;
196        first_free_arc = arcs[n].next_in;
197      }
198
199      arcs[n].source = u.id;
200      arcs[n].target = v.id;
201
202      arcs[n].next_out = nodes[u.id].first_out;
203      if(nodes[u.id].first_out != -1) {
204        arcs[nodes[u.id].first_out].prev_out = n;
205      }
206
207      arcs[n].next_in = nodes[v.id].first_in;
208      if(nodes[v.id].first_in != -1) {
209        arcs[nodes[v.id].first_in].prev_in = n;
210      }
211
212      arcs[n].prev_in = arcs[n].prev_out = -1;
213
214      nodes[u.id].first_out = nodes[v.id].first_in = n;
215
216      return Arc(n);
217    }
218
219    void erase(const Node& node) {
220      int n = node.id;
221
222      if(nodes[n].next != -1) {
223        nodes[nodes[n].next].prev = nodes[n].prev;
224      }
225
226      if(nodes[n].prev != -1) {
227        nodes[nodes[n].prev].next = nodes[n].next;
228      } else {
229        first_node = nodes[n].next;
230      }
231
232      nodes[n].next = first_free_node;
233      first_free_node = n;
234      nodes[n].prev = -2;
235
236    }
237
238    void erase(const Arc& arc) {
239      int n = arc.id;
240
241      if(arcs[n].next_in!=-1) {
242        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
243      }
244
245      if(arcs[n].prev_in!=-1) {
246        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
247      } else {
248        nodes[arcs[n].target].first_in = arcs[n].next_in;
249      }
250
251
252      if(arcs[n].next_out!=-1) {
253        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
254      }
255
256      if(arcs[n].prev_out!=-1) {
257        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
258      } else {
259        nodes[arcs[n].source].first_out = arcs[n].next_out;
260      }
261
262      arcs[n].next_in = first_free_arc;
263      first_free_arc = n;
264      arcs[n].prev_in = -2;
265    }
266
267    void clear() {
268      arcs.clear();
269      nodes.clear();
270      first_node = first_free_node = first_free_arc = -1;
271    }
272
273  protected:
274    void changeTarget(Arc e, Node n)
275    {
276      if(arcs[e.id].next_in != -1)
277        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
278      if(arcs[e.id].prev_in != -1)
279        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
280      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
281      if (nodes[n.id].first_in != -1) {
282        arcs[nodes[n.id].first_in].prev_in = e.id;
283      }
284      arcs[e.id].target = n.id;
285      arcs[e.id].prev_in = -1;
286      arcs[e.id].next_in = nodes[n.id].first_in;
287      nodes[n.id].first_in = e.id;
288    }
289    void changeSource(Arc e, Node n)
290    {
291      if(arcs[e.id].next_out != -1)
292        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
293      if(arcs[e.id].prev_out != -1)
294        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
295      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
296      if (nodes[n.id].first_out != -1) {
297        arcs[nodes[n.id].first_out].prev_out = e.id;
298      }
299      arcs[e.id].source = n.id;
300      arcs[e.id].prev_out = -1;
301      arcs[e.id].next_out = nodes[n.id].first_out;
302      nodes[n.id].first_out = e.id;
303    }
304
305  };
306
307  typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
308
309  /// \addtogroup graphs
310  /// @{
311
312  ///A general directed graph structure.
313
314  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
315  ///implementation based on static linked lists that are stored in
316  ///\c std::vector structures.
317  ///
318  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
319  ///also provides several useful additional functionalities.
320  ///Most of the member functions and nested classes are documented
321  ///only in the concept class.
322  ///
323  ///\sa concepts::Digraph
324
325  class ListDigraph : public ExtendedListDigraphBase {
326    typedef ExtendedListDigraphBase Parent;
327
328  private:
329    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
330
331    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
332    ///
333    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
334    ///\brief Assignment of ListDigraph to another one is \e not allowed.
335    ///Use copyDigraph() instead.
336
337    ///Assignment of ListDigraph to another one is \e not allowed.
338    ///Use copyDigraph() instead.
339    void operator=(const ListDigraph &) {}
340  public:
341
342    /// Constructor
343
344    /// Constructor.
345    ///
346    ListDigraph() {}
347
348    ///Add a new node to the digraph.
349
350    ///Add a new node to the digraph.
351    ///\return The new node.
352    Node addNode() { return Parent::addNode(); }
353
354    ///Add a new arc to the digraph.
355
356    ///Add a new arc to the digraph with source node \c s
357    ///and target node \c t.
358    ///\return The new arc.
359    Arc addArc(const Node& s, const Node& t) {
360      return Parent::addArc(s, t);
361    }
362
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
375    /// Node validity check
376
377    /// This function gives back true if the given node is valid,
378    /// ie. it is a real node of the graph.
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,
388    /// ie. it is a real arc of the graph.
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
395    /// Change the target of \c a to \c n
396
397    /// Change the target of \c a to \c n
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.
402    ///
403    ///\warning This functionality cannot be used together with the Snapshot
404    ///feature.
405    void changeTarget(Arc a, Node n) {
406      Parent::changeTarget(a,n);
407    }
408    /// Change the source of \c a to \c n
409
410    /// Change the source of \c a to \c n
411    ///
412    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
413    ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are
414    ///invalidated.
415    ///
416    ///\warning This functionality cannot be used together with the Snapshot
417    ///feature.
418    void changeSource(Arc a, Node n) {
419      Parent::changeSource(a,n);
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.
427    ///
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
436    /// Reserve memory for nodes.
437
438    /// Using this function it is possible to avoid the superfluous memory
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
446    /// Reserve memory for arcs.
447
448    /// Using this function it is possible to avoid the superfluous memory
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    ///
464    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
465    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
466    ///may be invalidated.
467    ///
468    ///\warning This functionality cannot be used together with the Snapshot
469    ///feature.
470    void contract(Node a, Node b, bool r = true)
471    {
472      for(OutArcIt e(*this,b);e!=INVALID;) {
473        OutArcIt f=e;
474        ++f;
475        if(r && target(e)==a) erase(e);
476        else changeSource(e,a);
477        e=f;
478      }
479      for(InArcIt e(*this,b);e!=INVALID;) {
480        InArcIt f=e;
481        ++f;
482        if(r && source(e)==a) erase(e);
483        else changeTarget(e,a);
484        e=f;
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
499    ///be invalidated.
500    ///
501    ///\warning This functionality cannot be used in conjunction with the
502    ///Snapshot feature.
503    Node split(Node n, bool connect = true) {
504      Node b = addNode();
505      for(OutArcIt e(*this,n);e!=INVALID;) {
506        OutArcIt f=e;
507        ++f;
508        changeSource(e,b);
509        e=f;
510      }
511      if (connect) addArc(n,b);
512      return b;
513    }
514
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.
520    ///
521    ///\return The newly created node.
522    ///
523    ///\warning This functionality cannot be used together with the
524    ///Snapshot feature.
525    Node split(Arc e) {
526      Node b = addNode();
527      addArc(b,target(e));
528      changeTarget(e,b);
529      return b;
530    }
531
532    /// \brief Class to make a snapshot of the digraph and restore
533    /// it later.
534    ///
535    /// Class to make a snapshot of the digraph and restore it later.
536    ///
537    /// The newly added nodes and arcs can be removed using the
538    /// restore() function.
539    ///
540    /// \warning Arc and node deletions and other modifications (e.g.
541    /// contracting, splitting, reversing arcs or nodes) cannot be
542    /// restored. These events invalidate the snapshot.
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;
557
558      protected:
559
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;
579          for (notifier()->first(node); node != INVALID;
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;
589          for (notifier()->first(node); node != INVALID;
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;
607
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;
629          for (notifier()->first(arc); arc != INVALID;
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;
639          for (notifier()->first(arc); arc != INVALID;
640               notifier()->next(arc)) {
641            snapshot.eraseArc(arc);
642          }
643        }
644
645        Snapshot& snapshot;
646      };
647
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) {
658        added_nodes.push_front(node);
659      }
660      void eraseNode(const Node& node) {
661        std::list<Node>::iterator it =
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) {
673        added_arcs.push_front(arc);
674      }
675      void eraseArc(const Arc& arc) {
676        std::list<Arc>::iterator it =
677          std::find(added_arcs.begin(), added_arcs.end(), arc);
678        if (it == added_arcs.end()) {
679          clear();
680          node_observer_proxy.detach();
681          throw ArcNotifier::ImmediateDetach();
682        } else {
683          added_arcs.erase(it);
684        }
685      }
686
687      void attach(ListDigraph &_digraph) {
688        digraph = &_digraph;
689        node_observer_proxy.attach(digraph->notifier(Node()));
690        arc_observer_proxy.attach(digraph->notifier(Arc()));
691      }
692
693      void detach() {
694        node_observer_proxy.detach();
695        arc_observer_proxy.detach();
696      }
697
698      bool attached() const {
699        return node_observer_proxy.attached();
700      }
701
702      void clear() {
703        added_nodes.clear();
704        added_arcs.clear();
705      }
706
707    public:
708
709      /// \brief Default constructor.
710      ///
711      /// Default constructor.
712      /// To actually make a snapshot you must call save().
713      Snapshot()
714        : digraph(0), node_observer_proxy(*this),
715          arc_observer_proxy(*this) {}
716
717      /// \brief Constructor that immediately makes a snapshot.
718      ///
719      /// This constructor immediately makes a snapshot of the digraph.
720      /// \param _digraph The digraph we make a snapshot of.
721      Snapshot(ListDigraph &_digraph)
722        : node_observer_proxy(*this),
723          arc_observer_proxy(*this) {
724        attach(_digraph);
725      }
726
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      }
741
742      /// \brief Undo the changes until the last snapshot.
743      //
744      /// Undo the changes until the last snapshot created by save().
745      void restore() {
746        detach();
747        for(std::list<Arc>::iterator it = added_arcs.begin();
748            it != added_arcs.end(); ++it) {
749          digraph->erase(*it);
750        }
751        for(std::list<Node>::iterator it = added_nodes.begin();
752            it != added_nodes.end(); ++it) {
753          digraph->erase(*it);
754        }
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    };
765
766  };
767
768  ///@}
769
770  class ListGraphBase {
771
772  protected:
773
774    struct NodeT {
775      int first_out;
776      int prev, next;
777    };
778
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;
793
794  public:
795
796    typedef ListGraphBase Graph;
797
798    class Node;
799    class Arc;
800    class Edge;
801
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; }
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;}
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:
840      operator Edge() const {
841        return id != -1 ? edgeFromId(id / 2) : INVALID;
842      }
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),
855        first_free_node(-1), arcs(), first_free_arc(-1) {}
856
857
858    int maxNodeId() const { return nodes.size()-1; }
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
876    void first(Node& node) const {
877      node.id = first_node;
878    }
879
880    void next(Node& node) const {
881      node.id = nodes[node.id].next;
882    }
883
884    void first(Arc& e) const {
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) {
894        e.id = arcs[e.id].next_out;
895      } else {
896        int n = nodes[arcs[e.id ^ 1].target].next;
897        while(n != -1 && nodes[n].first_out == -1) {
898          n = nodes[n].next;
899        }
900        e.id = (n == -1) ? -1 : nodes[n].first_out;
901      }
902    }
903
904    void first(Edge& e) const {
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;
914        }
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;
929      }
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;
939        }
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 {
962      int a = nodes[v.id].first_out;
963      if (a != -1 ) {
964        e.id = a / 2;
965        d = ((a & 1) == 1);
966      } else {
967        e.id = -1;
968        d = true;
969      }
970    }
971    void nextInc(Edge &e, bool& d) const {
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);
976      } else {
977        e.id = -1;
978        d = true;
979      }
980    }
981
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
990    bool valid(Node n) const {
991      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
992        nodes[n.id].prev != -2;
993    }
994
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;
998    }
999
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;
1003    }
1004
1005    Node addNode() {
1006      int n;
1007
1008      if(first_free_node==-1) {
1009        n = nodes.size();
1010        nodes.push_back(NodeT());
1011      } else {
1012        n = first_free_node;
1013        first_free_node = nodes[n].next;
1014      }
1015
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;
1020
1021      nodes[n].first_out = -1;
1022
1023      return Node(n);
1024    }
1025
1026    Edge addEdge(Node u, Node v) {
1027      int n;
1028
1029      if (first_free_arc == -1) {
1030        n = arcs.size();
1031        arcs.push_back(ArcT());
1032        arcs.push_back(ArcT());
1033      } else {
1034        n = first_free_arc;
1035        first_free_arc = arcs[n].next_out;
1036      }
1037
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) {
1043        arcs[nodes[v.id].first_out].prev_out = n;
1044      }
1045      arcs[n].prev_out = -1;
1046      nodes[v.id].first_out = n;
1047
1048      arcs[n | 1].next_out = nodes[u.id].first_out;
1049      if (nodes[u.id].first_out != -1) {
1050        arcs[nodes[u.id].first_out].prev_out = (n | 1);
1051      }
1052      arcs[n | 1].prev_out = -1;
1053      nodes[u.id].first_out = (n | 1);
1054
1055      return Edge(n / 2);
1056    }
1057
1058    void erase(const Node& node) {
1059      int n = node.id;
1060
1061      if(nodes[n].next != -1) {
1062        nodes[nodes[n].next].prev = nodes[n].prev;
1063      }
1064
1065      if(nodes[n].prev != -1) {
1066        nodes[nodes[n].prev].next = nodes[n].next;
1067      } else {
1068        first_node = nodes[n].next;
1069      }
1070
1071      nodes[n].next = first_free_node;
1072      first_free_node = n;
1073      nodes[n].prev = -2;
1074    }
1075
1076    void erase(const Edge& edge) {
1077      int n = edge.id * 2;
1078
1079      if (arcs[n].next_out != -1) {
1080        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1081      }
1082
1083      if (arcs[n].prev_out != -1) {
1084        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1085      } else {
1086        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1087      }
1088
1089      if (arcs[n | 1].next_out != -1) {
1090        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1091      }
1092
1093      if (arcs[n | 1].prev_out != -1) {
1094        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1095      } else {
1096        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1097      }
1098
1099      arcs[n].next_out = first_free_arc;
1100      first_free_arc = n;
1101      arcs[n].prev_out = -2;
1102      arcs[n | 1].prev_out = -2;
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
1114    void changeV(Edge e, Node n) {
1115      if(arcs[2 * e.id].next_out != -1) {
1116        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1117      }
1118      if(arcs[2 * e.id].prev_out != -1) {
1119        arcs[arcs[2 * e.id].prev_out].next_out =
1120          arcs[2 * e.id].next_out;
1121      } else {
1122        nodes[arcs[(2 * e.id) | 1].target].first_out =
1123          arcs[2 * e.id].next_out;
1124      }
1125
1126      if (nodes[n.id].first_out != -1) {
1127        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
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
1135    void changeU(Edge e, Node n) {
1136      if(arcs[(2 * e.id) | 1].next_out != -1) {
1137        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1138          arcs[(2 * e.id) | 1].prev_out;
1139      }
1140      if(arcs[(2 * e.id) | 1].prev_out != -1) {
1141        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1142          arcs[(2 * e.id) | 1].next_out;
1143      } else {
1144        nodes[arcs[2 * e.id].target].first_out =
1145          arcs[(2 * e.id) | 1].next_out;
1146      }
1147
1148      if (nodes[n.id].first_out != -1) {
1149        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
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
1162  /// \addtogroup graphs
1163  /// @{
1164
1165  ///A general undirected graph structure.
1166
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.
1170  ///
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
1178  class ListGraph : public ExtendedListGraphBase {
1179    typedef ExtendedListGraphBase Parent;
1180
1181  private:
1182    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
1183
1184    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
1185    ///
1186    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
1187    ///\brief Assignment of ListGraph to another one is \e not allowed.
1188    ///Use copyGraph() instead.
1189
1190    ///Assignment of ListGraph to another one is \e not allowed.
1191    ///Use copyGraph() instead.
1192    void operator=(const ListGraph &) {}
1193  public:
1194    /// Constructor
1195
1196    /// Constructor.
1197    ///
1198    ListGraph() {}
1199
1200    typedef Parent::OutArcIt IncEdgeIt;
1201
1202    /// \brief Add a new node to the graph.
1203    ///
1204    /// Add a new node to the graph.
1205    /// \return The new node.
1206    Node addNode() { return Parent::addNode(); }
1207
1208    /// \brief Add a new edge to the graph.
1209    ///
1210    /// Add a new edge to the graph with source node \c s
1211    /// and target node \c t.
1212    /// \return The new edge.
1213    Edge addEdge(const Node& s, const Node& t) {
1214      return Parent::addEdge(s, t);
1215    }
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); }
1228    /// Node validity check
1229
1230    /// This function gives back true if the given node is valid,
1231    /// ie. it is a real node of the graph.
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,
1240    /// ie. it is a real arc of the graph.
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,
1249    /// ie. it is a real arc of the graph.
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); }
1255    /// \brief Change the end \c u of \c e to \c n
1256    ///
1257    /// This function changes the end \c u of \c e to node \c n.
1258    ///
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.
1263    ///
1264    ///\warning This functionality cannot be used together with the
1265    ///Snapshot feature.
1266    void changeU(Edge e, Node n) {
1267      Parent::changeU(e,n);
1268    }
1269    /// \brief Change the end \c v of \c e to \c n
1270    ///
1271    /// This function changes the end \c v of \c e to \c n.
1272    ///
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.
1276    ///
1277    ///\warning This functionality cannot be used together with the
1278    ///Snapshot feature.
1279    void changeV(Edge e, Node n) {
1280      Parent::changeV(e,n);
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.
1292    ///
1293    ///\warning This functionality cannot be used together with the
1294    ///Snapshot feature.
1295    void contract(Node a, Node b, bool r = true) {
1296      for(IncEdgeIt e(*this, b); e!=INVALID;) {
1297        IncEdgeIt f = e; ++f;
1298        if (r && runningNode(e) == a) {
1299          erase(e);
1300        } else if (u(e) == b) {
1301          changeU(e, a);
1302        } else {
1303          changeV(e, a);
1304        }
1305        e = f;
1306      }
1307      erase(b);
1308    }
1309
1310
1311    /// \brief Class to make a snapshot of the graph and restore
1312    /// it later.
1313    ///
1314    /// Class to make a snapshot of the graph and restore it later.
1315    ///
1316    /// The newly added nodes and edges can be removed
1317    /// using the restore() function.
1318    ///
1319    /// \warning Edge and node deletions and other modifications
1320    /// (e.g. changing nodes of edges, contracting nodes) cannot be
1321    /// restored. These events invalidate the snapshot.
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;
1336
1337      protected:
1338
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;
1358          for (notifier()->first(node); node != INVALID;
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;
1368          for (notifier()->first(node); node != INVALID;
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;
1386
1387      protected:
1388
1389        virtual void add(const Edge& edge) {
1390          snapshot.addEdge(edge);
1391        }
1392        virtual void add(const std::vector<Edge>& edges) {
1393          for (int i = edges.size() - 1; i >= 0; ++i) {
1394            snapshot.addEdge(edges[i]);
1395          }
1396        }
1397        virtual void erase(const Edge& edge) {
1398          snapshot.eraseEdge(edge);
1399        }
1400        virtual void erase(const std::vector<Edge>& edges) {
1401          for (int i = 0; i < int(edges.size()); ++i) {
1402            snapshot.eraseEdge(edges[i]);
1403          }
1404        }
1405        virtual void build() {
1406          Edge edge;
1407          std::vector<Edge> edges;
1408          for (notifier()->first(edge); edge != INVALID;
1409               notifier()->next(edge)) {
1410            edges.push_back(edge);
1411          }
1412          for (int i = edges.size() - 1; i >= 0; --i) {
1413            snapshot.addEdge(edges[i]);
1414          }
1415        }
1416        virtual void clear() {
1417          Edge edge;
1418          for (notifier()->first(edge); edge != INVALID;
1419               notifier()->next(edge)) {
1420            snapshot.eraseEdge(edge);
1421          }
1422        }
1423
1424        Snapshot& snapshot;
1425      };
1426
1427      ListGraph *graph;
1428
1429      NodeObserverProxy node_observer_proxy;
1430      EdgeObserverProxy edge_observer_proxy;
1431
1432      std::list<Node> added_nodes;
1433      std::list<Edge> added_edges;
1434
1435
1436      void addNode(const Node& node) {
1437        added_nodes.push_front(node);
1438      }
1439      void eraseNode(const Node& node) {
1440        std::list<Node>::iterator it =
1441          std::find(added_nodes.begin(), added_nodes.end(), node);
1442        if (it == added_nodes.end()) {
1443          clear();
1444          edge_observer_proxy.detach();
1445          throw NodeNotifier::ImmediateDetach();
1446        } else {
1447          added_nodes.erase(it);
1448        }
1449      }
1450
1451      void addEdge(const Edge& edge) {
1452        added_edges.push_front(edge);
1453      }
1454      void eraseEdge(const Edge& edge) {
1455        std::list<Edge>::iterator it =
1456          std::find(added_edges.begin(), added_edges.end(), edge);
1457        if (it == added_edges.end()) {
1458          clear();
1459          node_observer_proxy.detach();
1460          throw EdgeNotifier::ImmediateDetach();
1461        } else {
1462          added_edges.erase(it);
1463        }
1464      }
1465
1466      void attach(ListGraph &_graph) {
1467        graph = &_graph;
1468        node_observer_proxy.attach(graph->notifier(Node()));
1469        edge_observer_proxy.attach(graph->notifier(Edge()));
1470      }
1471
1472      void detach() {
1473        node_observer_proxy.detach();
1474        edge_observer_proxy.detach();
1475      }
1476
1477      bool attached() const {
1478        return node_observer_proxy.attached();
1479      }
1480
1481      void clear() {
1482        added_nodes.clear();
1483        added_edges.clear();
1484      }
1485
1486    public:
1487
1488      /// \brief Default constructor.
1489      ///
1490      /// Default constructor.
1491      /// To actually make a snapshot you must call save().
1492      Snapshot()
1493        : graph(0), node_observer_proxy(*this),
1494          edge_observer_proxy(*this) {}
1495
1496      /// \brief Constructor that immediately makes a snapshot.
1497      ///
1498      /// This constructor immediately makes a snapshot of the graph.
1499      /// \param _graph The graph we make a snapshot of.
1500      Snapshot(ListGraph &_graph)
1501        : node_observer_proxy(*this),
1502          edge_observer_proxy(*this) {
1503        attach(_graph);
1504      }
1505
1506      /// \brief Make a snapshot.
1507      ///
1508      /// Make a snapshot of the graph.
1509      ///
1510      /// This function can be called more than once. In case of a repeated
1511      /// call, the previous snapshot gets lost.
1512      /// \param _graph The graph we make the snapshot of.
1513      void save(ListGraph &_graph) {
1514        if (attached()) {
1515          detach();
1516          clear();
1517        }
1518        attach(_graph);
1519      }
1520
1521      /// \brief Undo the changes until the last snapshot.
1522      //
1523      /// Undo the changes until the last snapshot created by save().
1524      void restore() {
1525        detach();
1526        for(std::list<Edge>::iterator it = added_edges.begin();
1527            it != added_edges.end(); ++it) {
1528          graph->erase(*it);
1529        }
1530        for(std::list<Node>::iterator it = added_nodes.begin();
1531            it != added_nodes.end(); ++it) {
1532          graph->erase(*it);
1533        }
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  };
1545
1546  /// @}
1547} //namespace lemon
1548
1549
1550#endif
Note: See TracBrowser for help on using the repository browser.