COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/list_graph.h @ 2498:290e43cddc1a

Last change on this file since 2498:290e43cddc1a was 2498:290e43cddc1a, checked in by Balazs Dezso, 16 years ago

Bug fix in undirected graphs (adding loops)
Bug fix in undirected edgesets (alteration notifying)

Redesigned undirected edgesets (like the smart or ugraph)

File size: 61.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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 ListGraph, ListUGraph classes.
25
26#include <lemon/bits/base_extender.h>
27#include <lemon/bits/graph_extender.h>
28
29#include <lemon/error.h>
30
31#include <vector>
32#include <list>
33
34namespace lemon {
35
36  class ListGraphBase {
37
38  protected:
39    struct NodeT {
40      int first_in, first_out;
41      int prev, next;
42    };
43 
44    struct EdgeT {
45      int target, source;
46      int prev_in, prev_out;
47      int next_in, next_out;
48    };
49
50    std::vector<NodeT> nodes;
51
52    int first_node;
53
54    int first_free_node;
55
56    std::vector<EdgeT> edges;
57
58    int first_free_edge;
59   
60  public:
61   
62    typedef ListGraphBase Graph;
63   
64    class Node {
65      friend class ListGraphBase;
66    protected:
67
68      int id;
69      explicit Node(int pid) { id = pid;}
70
71    public:
72      Node() {}
73      Node (Invalid) { id = -1; }
74      bool operator==(const Node& node) const {return id == node.id;}
75      bool operator!=(const Node& node) const {return id != node.id;}
76      bool operator<(const Node& node) const {return id < node.id;}
77    };
78
79    class Edge {
80      friend class ListGraphBase;
81    protected:
82
83      int id;
84      explicit Edge(int pid) { id = pid;}
85
86    public:
87      Edge() {}
88      Edge (Invalid) { id = -1; }
89      bool operator==(const Edge& edge) const {return id == edge.id;}
90      bool operator!=(const Edge& edge) const {return id != edge.id;}
91      bool operator<(const Edge& edge) const {return id < edge.id;}
92    };
93
94
95
96    ListGraphBase()
97      : nodes(), first_node(-1),
98        first_free_node(-1), edges(), first_free_edge(-1) {}
99
100   
101    int maxNodeId() const { return nodes.size()-1; }
102    int maxEdgeId() const { return edges.size()-1; }
103
104    Node source(Edge e) const { return Node(edges[e.id].source); }
105    Node target(Edge e) const { return Node(edges[e.id].target); }
106
107
108    void first(Node& node) const {
109      node.id = first_node;
110    }
111
112    void next(Node& node) const {
113      node.id = nodes[node.id].next;
114    }
115
116
117    void first(Edge& e) const {
118      int n;
119      for(n = first_node;
120          n!=-1 && nodes[n].first_in == -1;
121          n = nodes[n].next);
122      e.id = (n == -1) ? -1 : nodes[n].first_in;
123    }
124
125    void next(Edge& edge) const {
126      if (edges[edge.id].next_in != -1) {
127        edge.id = edges[edge.id].next_in;
128      } else {
129        int n;
130        for(n = nodes[edges[edge.id].target].next;
131          n!=-1 && nodes[n].first_in == -1;
132          n = nodes[n].next);
133        edge.id = (n == -1) ? -1 : nodes[n].first_in;
134      }     
135    }
136
137    void firstOut(Edge &e, const Node& v) const {
138      e.id = nodes[v.id].first_out;
139    }
140    void nextOut(Edge &e) const {
141      e.id=edges[e.id].next_out;
142    }
143
144    void firstIn(Edge &e, const Node& v) const {
145      e.id = nodes[v.id].first_in;
146    }
147    void nextIn(Edge &e) const {
148      e.id=edges[e.id].next_in;
149    }
150
151   
152    static int id(Node v) { return v.id; }
153    static int id(Edge e) { return e.id; }
154
155    static Node nodeFromId(int id) { return Node(id);}
156    static Edge edgeFromId(int id) { return Edge(id);}
157
158    Node addNode() {     
159      int n;
160     
161      if(first_free_node==-1) {
162        n = nodes.size();
163        nodes.push_back(NodeT());
164      } else {
165        n = first_free_node;
166        first_free_node = nodes[n].next;
167      }
168     
169      nodes[n].next = first_node;
170      if(first_node != -1) nodes[first_node].prev = n;
171      first_node = n;
172      nodes[n].prev = -1;
173     
174      nodes[n].first_in = nodes[n].first_out = -1;
175     
176      return Node(n);
177    }
178   
179    Edge addEdge(Node u, Node v) {
180      int n;     
181
182      if (first_free_edge == -1) {
183        n = edges.size();
184        edges.push_back(EdgeT());
185      } else {
186        n = first_free_edge;
187        first_free_edge = edges[n].next_in;
188      }
189     
190      edges[n].source = u.id;
191      edges[n].target = v.id;
192
193      edges[n].next_out = nodes[u.id].first_out;
194      if(nodes[u.id].first_out != -1) {
195        edges[nodes[u.id].first_out].prev_out = n;
196      }
197     
198      edges[n].next_in = nodes[v.id].first_in;
199      if(nodes[v.id].first_in != -1) {
200        edges[nodes[v.id].first_in].prev_in = n;
201      }
202     
203      edges[n].prev_in = edges[n].prev_out = -1;
204       
205      nodes[u.id].first_out = nodes[v.id].first_in = n;
206
207      return Edge(n);
208    }
209   
210    void erase(const Node& node) {
211      int n = node.id;
212     
213      if(nodes[n].next != -1) {
214        nodes[nodes[n].next].prev = nodes[n].prev;
215      }
216     
217      if(nodes[n].prev != -1) {
218        nodes[nodes[n].prev].next = nodes[n].next;
219      } else {
220        first_node = nodes[n].next;
221      }
222     
223      nodes[n].next = first_free_node;
224      first_free_node = n;
225
226    }
227   
228    void erase(const Edge& edge) {
229      int n = edge.id;
230     
231      if(edges[n].next_in!=-1) {
232        edges[edges[n].next_in].prev_in = edges[n].prev_in;
233      }
234
235      if(edges[n].prev_in!=-1) {
236        edges[edges[n].prev_in].next_in = edges[n].next_in;
237      } else {
238        nodes[edges[n].target].first_in = edges[n].next_in;
239      }
240
241     
242      if(edges[n].next_out!=-1) {
243        edges[edges[n].next_out].prev_out = edges[n].prev_out;
244      }
245
246      if(edges[n].prev_out!=-1) {
247        edges[edges[n].prev_out].next_out = edges[n].next_out;
248      } else {
249        nodes[edges[n].source].first_out = edges[n].next_out;
250      }
251     
252      edges[n].next_in = first_free_edge;
253      first_free_edge = n;     
254
255    }
256
257    void clear() {
258      edges.clear();
259      nodes.clear();
260      first_node = first_free_node = first_free_edge = -1;
261    }
262
263  protected:
264    void changeTarget(Edge e, Node n)
265    {
266      if(edges[e.id].next_in != -1)
267        edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
268      if(edges[e.id].prev_in != -1)
269        edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
270      else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
271      if (nodes[n.id].first_in != -1) {
272        edges[nodes[n.id].first_in].prev_in = e.id;
273      }
274      edges[e.id].target = n.id;
275      edges[e.id].prev_in = -1;
276      edges[e.id].next_in = nodes[n.id].first_in;
277      nodes[n.id].first_in = e.id;
278    }
279    void changeSource(Edge e, Node n)
280    {
281      if(edges[e.id].next_out != -1)
282        edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
283      if(edges[e.id].prev_out != -1)
284        edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
285      else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
286      if (nodes[n.id].first_out != -1) {
287        edges[nodes[n.id].first_out].prev_out = e.id;
288      }
289      edges[e.id].source = n.id;
290      edges[e.id].prev_out = -1;
291      edges[e.id].next_out = nodes[n.id].first_out;
292      nodes[n.id].first_out = e.id;
293    }
294
295  };
296
297  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
298
299  /// \addtogroup graphs
300  /// @{
301
302  ///A list graph class.
303
304  ///This is a simple and fast graph implementation.
305  ///
306  ///It conforms to the \ref concepts::Graph "Graph concept" and it
307  ///also provides several additional useful extra functionalities.
308  ///The most of the member functions and nested classes are
309  ///documented only in the concept class.
310  ///
311  ///An important extra feature of this graph implementation is that
312  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
313  ///
314  ///\sa concepts::Graph.
315
316  class ListGraph : public ExtendedListGraphBase {
317  private:
318    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
319   
320    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
321    ///
322    ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
323    ///\brief Assignment of ListGraph to another one is \e not allowed.
324    ///Use GraphCopy() instead.
325
326    ///Assignment of ListGraph to another one is \e not allowed.
327    ///Use GraphCopy() instead.
328    void operator=(const ListGraph &) {}
329  public:
330
331    typedef ExtendedListGraphBase Parent;
332
333    /// Constructor
334   
335    /// Constructor.
336    ///
337    ListGraph() {}
338
339    ///Add a new node to the graph.
340   
341    /// \return the new node.
342    ///
343    Node addNode() { return Parent::addNode(); }
344
345    ///Add a new edge to the graph.
346   
347    ///Add a new edge to the graph with source node \c s
348    ///and target node \c t.
349    ///\return the new edge.
350    Edge addEdge(const Node& s, const Node& t) {
351      return Parent::addEdge(s, t);
352    }
353
354    /// Changes the target of \c e to \c n
355
356    /// Changes the target of \c e to \c n
357    ///
358    ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
359    ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
360    ///invalidated.
361    ///\warning This functionality cannot be used together with the Snapshot
362    ///feature.
363    void changeTarget(Edge e, Node n) {
364      Parent::changeTarget(e,n);
365    }
366    /// Changes the source of \c e to \c n
367
368    /// Changes the source of \c e to \c n
369    ///
370    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
371    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
372    ///invalidated.
373    ///\warning This functionality cannot be used together with the Snapshot
374    ///feature.
375    void changeSource(Edge e, Node n) {
376      Parent::changeSource(e,n);
377    }
378
379    /// Invert the direction of an edge.
380
381    ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
382    ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
383    ///invalidated.
384    ///\warning This functionality cannot be used together with the Snapshot
385    ///feature.
386    void reverseEdge(Edge e) {
387      Node t=target(e);
388      changeTarget(e,source(e));
389      changeSource(e,t);
390    }
391
392    /// Using this it is possible to avoid the superfluous memory
393    /// allocation: if you know that the graph you want to build will
394    /// be very large (e.g. it will contain millions of nodes and/or edges)
395    /// then it is worth reserving space for this amount before starting
396    /// to build the graph.
397    /// \sa reserveEdge
398    void reserveNode(int n) { nodes.reserve(n); };
399
400    /// \brief Using this it is possible to avoid the superfluous memory
401    /// allocation.
402
403    /// Using this it is possible to avoid the superfluous memory
404    /// allocation: if you know that the graph you want to build will
405    /// be very large (e.g. it will contain millions of nodes and/or edges)
406    /// then it is worth reserving space for this amount before starting
407    /// to build the graph.
408    /// \sa reserveNode
409    void reserveEdge(int m) { edges.reserve(m); };
410
411    ///Contract two nodes.
412
413    ///This function contracts two nodes.
414    ///
415    ///Node \p b will be removed but instead of deleting
416    ///incident edges, they will be joined to \p a.
417    ///The last parameter \p r controls whether to remove loops. \c true
418    ///means that loops will be removed.
419    ///
420    ///\note The <tt>EdgeIt</tt>s
421    ///referencing a moved edge remain
422    ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
423    ///may be invalidated.
424    ///\warning This functionality cannot be used together with the Snapshot
425    ///feature.
426    void contract(Node a, Node b, bool r = true)
427    {
428      for(OutEdgeIt e(*this,b);e!=INVALID;) {
429        OutEdgeIt f=e;
430        ++f;
431        if(r && target(e)==a) erase(e);
432        else changeSource(e,a);
433        e=f;
434      }
435      for(InEdgeIt e(*this,b);e!=INVALID;) {
436        InEdgeIt f=e;
437        ++f;
438        if(r && source(e)==a) erase(e);
439        else changeTarget(e,a);
440        e=f;
441      }
442      erase(b);
443    }
444
445    ///Split a node.
446
447    ///This function splits a node. First a new node is added to the graph,
448    ///then the source of each outgoing edge of \c n is moved to this new node.
449    ///If \c connect is \c true (this is the default value), then a new edge
450    ///from \c n to the newly created node is also added.
451    ///\return The newly created node.
452    ///
453    ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
454    ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
455    ///be invalidated. 
456    ///
457    ///\warning This functionality cannot be used together with the
458    ///Snapshot feature.  \todo It could be implemented in a bit
459    ///faster way.
460    Node split(Node n, bool connect = true) {
461      Node b = addNode();
462      for(OutEdgeIt e(*this,n);e!=INVALID;) {
463        OutEdgeIt f=e;
464        ++f;
465        changeSource(e,b);
466        e=f;
467      }
468      if (connect) addEdge(n,b);
469      return b;
470    }
471     
472    ///Split an edge.
473
474    ///This function splits an edge. First a new node \c b is added to
475    ///the graph, then the original edge is re-targeted to \c
476    ///b. Finally an edge from \c b to the original target is added.
477    ///\return The newly created node. 
478    ///\warning This functionality
479    ///cannot be used together with the Snapshot feature.
480    Node split(Edge e) {
481      Node b = addNode();
482      addEdge(b,target(e));
483      changeTarget(e,b);
484      return b;
485    }
486     
487    /// \brief Class to make a snapshot of the graph and restore
488    /// to it later.
489    ///
490    /// Class to make a snapshot of the graph and to restore it
491    /// later.
492    ///
493    /// The newly added nodes and edges can be removed using the
494    /// restore() function.
495    ///
496    /// \warning Edge and node deletions cannot be restored. This
497    /// events invalidate the snapshot.
498    class Snapshot {
499    protected:
500
501      typedef Parent::NodeNotifier NodeNotifier;
502
503      class NodeObserverProxy : public NodeNotifier::ObserverBase {
504      public:
505
506        NodeObserverProxy(Snapshot& _snapshot)
507          : snapshot(_snapshot) {}
508
509        using NodeNotifier::ObserverBase::attach;
510        using NodeNotifier::ObserverBase::detach;
511        using NodeNotifier::ObserverBase::attached;
512       
513      protected:
514       
515        virtual void add(const Node& node) {
516          snapshot.addNode(node);
517        }
518        virtual void add(const std::vector<Node>& nodes) {
519          for (int i = nodes.size() - 1; i >= 0; ++i) {
520            snapshot.addNode(nodes[i]);
521          }
522        }
523        virtual void erase(const Node& node) {
524          snapshot.eraseNode(node);
525        }
526        virtual void erase(const std::vector<Node>& nodes) {
527          for (int i = 0; i < int(nodes.size()); ++i) {
528            snapshot.eraseNode(nodes[i]);
529          }
530        }
531        virtual void build() {
532          Node node;
533          std::vector<Node> nodes;
534          for (notifier()->first(node); node != INVALID;
535               notifier()->next(node)) {
536            nodes.push_back(node);
537          }
538          for (int i = nodes.size() - 1; i >= 0; --i) {
539            snapshot.addNode(nodes[i]);
540          }
541        }
542        virtual void clear() {
543          Node node;
544          for (notifier()->first(node); node != INVALID;
545               notifier()->next(node)) {
546            snapshot.eraseNode(node);
547          }
548        }
549
550        Snapshot& snapshot;
551      };
552
553      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
554      public:
555
556        EdgeObserverProxy(Snapshot& _snapshot)
557          : snapshot(_snapshot) {}
558
559        using EdgeNotifier::ObserverBase::attach;
560        using EdgeNotifier::ObserverBase::detach;
561        using EdgeNotifier::ObserverBase::attached;
562       
563      protected:
564
565        virtual void add(const Edge& edge) {
566          snapshot.addEdge(edge);
567        }
568        virtual void add(const std::vector<Edge>& edges) {
569          for (int i = edges.size() - 1; i >= 0; ++i) {
570            snapshot.addEdge(edges[i]);
571          }
572        }
573        virtual void erase(const Edge& edge) {
574          snapshot.eraseEdge(edge);
575        }
576        virtual void erase(const std::vector<Edge>& edges) {
577          for (int i = 0; i < int(edges.size()); ++i) {
578            snapshot.eraseEdge(edges[i]);
579          }
580        }
581        virtual void build() {
582          Edge edge;
583          std::vector<Edge> edges;
584          for (notifier()->first(edge); edge != INVALID;
585               notifier()->next(edge)) {
586            edges.push_back(edge);
587          }
588          for (int i = edges.size() - 1; i >= 0; --i) {
589            snapshot.addEdge(edges[i]);
590          }
591        }
592        virtual void clear() {
593          Edge edge;
594          for (notifier()->first(edge); edge != INVALID;
595               notifier()->next(edge)) {
596            snapshot.eraseEdge(edge);
597          }
598        }
599
600        Snapshot& snapshot;
601      };
602     
603      ListGraph *graph;
604
605      NodeObserverProxy node_observer_proxy;
606      EdgeObserverProxy edge_observer_proxy;
607
608      std::list<Node> added_nodes;
609      std::list<Edge> added_edges;
610
611
612      void addNode(const Node& node) {
613        added_nodes.push_front(node);       
614      }
615      void eraseNode(const Node& node) {
616        std::list<Node>::iterator it =
617          std::find(added_nodes.begin(), added_nodes.end(), node);
618        if (it == added_nodes.end()) {
619          clear();
620          edge_observer_proxy.detach();
621          throw NodeNotifier::ImmediateDetach();
622        } else {
623          added_nodes.erase(it);
624        }
625      }
626
627      void addEdge(const Edge& edge) {
628        added_edges.push_front(edge);       
629      }
630      void eraseEdge(const Edge& edge) {
631        std::list<Edge>::iterator it =
632          std::find(added_edges.begin(), added_edges.end(), edge);
633        if (it == added_edges.end()) {
634          clear();
635          node_observer_proxy.detach();
636          throw EdgeNotifier::ImmediateDetach();
637        } else {
638          added_edges.erase(it);
639        }       
640      }
641
642      void attach(ListGraph &_graph) {
643        graph = &_graph;
644        node_observer_proxy.attach(graph->notifier(Node()));
645        edge_observer_proxy.attach(graph->notifier(Edge()));
646      }
647           
648      void detach() {
649        node_observer_proxy.detach();
650        edge_observer_proxy.detach();
651      }
652
653      bool attached() const {
654        return node_observer_proxy.attached();
655      }
656
657      void clear() {
658        added_nodes.clear();
659        added_edges.clear();       
660      }
661
662    public:
663
664      /// \brief Default constructor.
665      ///
666      /// Default constructor.
667      /// To actually make a snapshot you must call save().
668      Snapshot()
669        : graph(0), node_observer_proxy(*this),
670          edge_observer_proxy(*this) {}
671     
672      /// \brief Constructor that immediately makes a snapshot.
673      ///     
674      /// This constructor immediately makes a snapshot of the graph.
675      /// \param _graph The graph we make a snapshot of.
676      Snapshot(ListGraph &_graph)
677        : node_observer_proxy(*this),
678          edge_observer_proxy(*this) {
679        attach(_graph);
680      }
681     
682      /// \brief Make a snapshot.
683      ///
684      /// Make a snapshot of the graph.
685      ///
686      /// This function can be called more than once. In case of a repeated
687      /// call, the previous snapshot gets lost.
688      /// \param _graph The graph we make the snapshot of.
689      void save(ListGraph &_graph) {
690        if (attached()) {
691          detach();
692          clear();
693        }
694        attach(_graph);
695      }
696     
697      /// \brief Undo the changes until the last snapshot.
698      //
699      /// Undo the changes until the last snapshot created by save().
700      void restore() {
701        detach();
702        for(std::list<Edge>::iterator it = added_edges.begin();
703            it != added_edges.end(); ++it) {
704          graph->erase(*it);
705        }
706        for(std::list<Node>::iterator it = added_nodes.begin();
707            it != added_nodes.end(); ++it) {
708          graph->erase(*it);
709        }
710        clear();
711      }
712
713      /// \brief Gives back true when the snapshot is valid.
714      ///
715      /// Gives back true when the snapshot is valid.
716      bool valid() const {
717        return attached();
718      }
719    };
720   
721  };
722
723  ///@}
724
725  class ListUGraphBase {
726
727  protected:
728
729    struct NodeT {
730      int first_out;
731      int prev, next;
732    };
733 
734    struct EdgeT {
735      int target;
736      int prev_out, next_out;
737    };
738
739    std::vector<NodeT> nodes;
740
741    int first_node;
742
743    int first_free_node;
744
745    std::vector<EdgeT> edges;
746
747    int first_free_edge;
748   
749  public:
750   
751    typedef ListUGraphBase Graph;
752
753    class Node;
754    class Edge;
755    class UEdge;
756   
757    class Node {
758      friend class ListUGraphBase;
759    protected:
760
761      int id;
762      explicit Node(int pid) { id = pid;}
763
764    public:
765      Node() {}
766      Node (Invalid) { id = -1; }
767      bool operator==(const Node& node) const {return id == node.id;}
768      bool operator!=(const Node& node) const {return id != node.id;}
769      bool operator<(const Node& node) const {return id < node.id;}
770    };
771
772    class UEdge {
773      friend class ListUGraphBase;
774    protected:
775
776      int id;
777      explicit UEdge(int pid) { id = pid;}
778
779    public:
780      UEdge() {}
781      UEdge (Invalid) { id = -1; }
782      bool operator==(const UEdge& edge) const {return id == edge.id;}
783      bool operator!=(const UEdge& edge) const {return id != edge.id;}
784      bool operator<(const UEdge& edge) const {return id < edge.id;}
785    };
786
787    class Edge {
788      friend class ListUGraphBase;
789    protected:
790
791      int id;
792      explicit Edge(int pid) { id = pid;}
793
794    public:
795      operator UEdge() const { return uEdgeFromId(id / 2); }
796
797      Edge() {}
798      Edge (Invalid) { id = -1; }
799      bool operator==(const Edge& edge) const {return id == edge.id;}
800      bool operator!=(const Edge& edge) const {return id != edge.id;}
801      bool operator<(const Edge& edge) const {return id < edge.id;}
802    };
803
804
805
806    ListUGraphBase()
807      : nodes(), first_node(-1),
808        first_free_node(-1), edges(), first_free_edge(-1) {}
809
810   
811    int maxNodeId() const { return nodes.size()-1; }
812    int maxUEdgeId() const { return edges.size() / 2 - 1; }
813    int maxEdgeId() const { return edges.size()-1; }
814
815    Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
816    Node target(Edge e) const { return Node(edges[e.id].target); }
817
818    Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
819    Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
820
821    static bool direction(Edge e) {
822      return (e.id & 1) == 1;
823    }
824
825    static Edge direct(UEdge e, bool d) {
826      return Edge(e.id * 2 + (d ? 1 : 0));
827    }
828
829    void first(Node& node) const {
830      node.id = first_node;
831    }
832
833    void next(Node& node) const {
834      node.id = nodes[node.id].next;
835    }
836
837    void first(Edge& e) const {
838      int n = first_node;
839      while (n != -1 && nodes[n].first_out == -1) {
840        n = nodes[n].next;
841      }
842      e.id = (n == -1) ? -1 : nodes[n].first_out;
843    }
844
845    void next(Edge& e) const {
846      if (edges[e.id].next_out != -1) {
847        e.id = edges[e.id].next_out;
848      } else {
849        int n = nodes[edges[e.id ^ 1].target].next;
850        while(n != -1 && nodes[n].first_out == -1) {
851          n = nodes[n].next;
852        }
853        e.id = (n == -1) ? -1 : nodes[n].first_out;
854      }     
855    }
856
857    void first(UEdge& e) const {
858      int n = first_node;
859      while (n != -1) {
860        e.id = nodes[n].first_out;
861        while ((e.id & 1) != 1) {
862          e.id = edges[e.id].next_out;
863        }
864        if (e.id != -1) {
865          e.id /= 2;
866          return;
867        }
868        n = nodes[n].next;
869      }
870      e.id = -1;
871    }
872
873    void next(UEdge& e) const {
874      int n = edges[e.id * 2].target;
875      e.id = edges[(e.id * 2) | 1].next_out;
876      while ((e.id & 1) != 1) {
877        e.id = edges[e.id].next_out;
878      }
879      if (e.id != -1) {
880        e.id /= 2;
881        return;
882      }
883      n = nodes[n].next;
884      while (n != -1) {
885        e.id = nodes[n].first_out;
886        while ((e.id & 1) != 1) {
887          e.id = edges[e.id].next_out;
888        }
889        if (e.id != -1) {
890          e.id /= 2;
891          return;
892        }
893        n = nodes[n].next;
894      }
895      e.id = -1;
896    }
897
898    void firstOut(Edge &e, const Node& v) const {
899      e.id = nodes[v.id].first_out;
900    }
901    void nextOut(Edge &e) const {
902      e.id = edges[e.id].next_out;
903    }
904
905    void firstIn(Edge &e, const Node& v) const {
906      e.id = ((nodes[v.id].first_out) ^ 1);
907      if (e.id == -2) e.id = -1;
908    }
909    void nextIn(Edge &e) const {
910      e.id = ((edges[e.id ^ 1].next_out) ^ 1);
911      if (e.id == -2) e.id = -1;
912    }
913
914    void firstInc(UEdge &e, bool& d, const Node& v) const {
915      int de = nodes[v.id].first_out;
916      if (de != -1 ) {
917        e.id = de / 2;
918        d = ((de & 1) == 1);
919      } else {
920        e.id = -1;
921        d = true;
922      }
923    }
924    void nextInc(UEdge &e, bool& d) const {
925      int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
926      if (de != -1 ) {
927        e.id = de / 2;
928        d = ((de & 1) == 1);
929      } else {
930        e.id = -1;
931        d = true;
932      }
933    }
934   
935    static int id(Node v) { return v.id; }
936    static int id(Edge e) { return e.id; }
937    static int id(UEdge e) { return e.id; }
938
939    static Node nodeFromId(int id) { return Node(id);}
940    static Edge edgeFromId(int id) { return Edge(id);}
941    static UEdge uEdgeFromId(int id) { return UEdge(id);}
942
943    Node addNode() {     
944      int n;
945     
946      if(first_free_node==-1) {
947        n = nodes.size();
948        nodes.push_back(NodeT());
949      } else {
950        n = first_free_node;
951        first_free_node = nodes[n].next;
952      }
953     
954      nodes[n].next = first_node;
955      if (first_node != -1) nodes[first_node].prev = n;
956      first_node = n;
957      nodes[n].prev = -1;
958     
959      nodes[n].first_out = -1;
960     
961      return Node(n);
962    }
963   
964    UEdge addEdge(Node u, Node v) {
965      int n;     
966
967      if (first_free_edge == -1) {
968        n = edges.size();
969        edges.push_back(EdgeT());
970        edges.push_back(EdgeT());
971      } else {
972        n = first_free_edge;
973        first_free_edge = edges[n].next_out;
974      }
975     
976      edges[n].target = u.id;
977      edges[n | 1].target = v.id;
978
979      edges[n].next_out = nodes[v.id].first_out;
980      if (nodes[v.id].first_out != -1) {
981        edges[nodes[v.id].first_out].prev_out = n;
982      }     
983      edges[n].prev_out = -1;
984      nodes[v.id].first_out = n;
985     
986      edges[n | 1].next_out = nodes[u.id].first_out;
987      if (nodes[u.id].first_out != -1) {
988        edges[nodes[u.id].first_out].prev_out = (n | 1);
989      }
990      edges[n | 1].prev_out = -1;     
991      nodes[u.id].first_out = (n | 1);
992
993      return UEdge(n / 2);
994    }
995   
996    void erase(const Node& node) {
997      int n = node.id;
998     
999      if(nodes[n].next != -1) {
1000        nodes[nodes[n].next].prev = nodes[n].prev;
1001      }
1002     
1003      if(nodes[n].prev != -1) {
1004        nodes[nodes[n].prev].next = nodes[n].next;
1005      } else {
1006        first_node = nodes[n].next;
1007      }
1008     
1009      nodes[n].next = first_free_node;
1010      first_free_node = n;
1011
1012    }
1013   
1014    void erase(const UEdge& edge) {
1015      int n = edge.id * 2;
1016     
1017      if (edges[n].next_out != -1) {
1018        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1019      }
1020
1021      if (edges[n].prev_out != -1) {
1022        edges[edges[n].prev_out].next_out = edges[n].next_out;
1023      } else {
1024        nodes[edges[n | 1].target].first_out = edges[n].next_out;
1025      }
1026
1027      if (edges[n | 1].next_out != -1) {
1028        edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
1029      }
1030
1031      if (edges[n | 1].prev_out != -1) {
1032        edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
1033      } else {
1034        nodes[edges[n].target].first_out = edges[n | 1].next_out;
1035      }
1036     
1037      edges[n].next_out = first_free_edge;
1038      first_free_edge = n;     
1039
1040    }
1041
1042    void clear() {
1043      edges.clear();
1044      nodes.clear();
1045      first_node = first_free_node = first_free_edge = -1;
1046    }
1047
1048  protected:
1049
1050    void changeTarget(UEdge e, Node n) {
1051      if(edges[2 * e.id].next_out != -1) {
1052        edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
1053      }
1054      if(edges[2 * e.id].prev_out != -1) {
1055        edges[edges[2 * e.id].prev_out].next_out =
1056          edges[2 * e.id].next_out;
1057      } else {
1058        nodes[edges[(2 * e.id) | 1].target].first_out =
1059          edges[2 * e.id].next_out;
1060      }
1061
1062      if (nodes[n.id].first_out != -1) {
1063        edges[nodes[n.id].first_out].prev_out = 2 * e.id;
1064      }
1065      edges[(2 * e.id) | 1].target = n.id;
1066      edges[2 * e.id].prev_out = -1;
1067      edges[2 * e.id].next_out = nodes[n.id].first_out;
1068      nodes[n.id].first_out = 2 * e.id;
1069    }
1070
1071    void changeSource(UEdge e, Node n) {
1072      if(edges[(2 * e.id) | 1].next_out != -1) {
1073        edges[edges[(2 * e.id) | 1].next_out].prev_out =
1074          edges[(2 * e.id) | 1].prev_out;
1075      }
1076      if(edges[(2 * e.id) | 1].prev_out != -1) {
1077        edges[edges[(2 * e.id) | 1].prev_out].next_out =
1078          edges[(2 * e.id) | 1].next_out;
1079      } else {
1080        nodes[edges[2 * e.id].target].first_out =
1081          edges[(2 * e.id) | 1].next_out;
1082      }
1083
1084      if (nodes[n.id].first_out != -1) {
1085        edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1086      }
1087      edges[2 * e.id].target = n.id;
1088      edges[(2 * e.id) | 1].prev_out = -1;
1089      edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1090      nodes[n.id].first_out = ((2 * e.id) | 1);
1091    }
1092
1093  };
1094
1095//   typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
1096//   ExtendedListUGraphBase;
1097
1098  typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
1099
1100
1101
1102  /// \addtogroup graphs
1103  /// @{
1104
1105  ///An undirected list graph class.
1106
1107  ///This is a simple and fast undirected graph implementation.
1108  ///
1109  ///An important extra feature of this graph implementation is that
1110  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1111  ///
1112  ///It conforms to the
1113  ///\ref concepts::UGraph "UGraph concept".
1114  ///
1115  ///\sa concepts::UGraph.
1116  ///
1117  class ListUGraph : public ExtendedListUGraphBase {
1118  private:
1119    ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
1120
1121    ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
1122    ///
1123    ListUGraph(const ListUGraph &) :ExtendedListUGraphBase()  {};
1124    ///\brief Assignment of ListUGraph to another one is \e not allowed.
1125    ///Use UGraphCopy() instead.
1126
1127    ///Assignment of ListUGraph to another one is \e not allowed.
1128    ///Use UGraphCopy() instead.
1129    void operator=(const ListUGraph &) {}
1130  public:
1131    /// Constructor
1132   
1133    /// Constructor.
1134    ///
1135    ListUGraph() {}
1136
1137    typedef ExtendedListUGraphBase Parent;
1138
1139    typedef Parent::OutEdgeIt IncEdgeIt;
1140
1141    /// \brief Add a new node to the graph.
1142    ///
1143    /// \return the new node.
1144    ///
1145    Node addNode() { return Parent::addNode(); }
1146
1147    /// \brief Add a new edge to the graph.
1148    ///
1149    /// Add a new edge to the graph with source node \c s
1150    /// and target node \c t.
1151    /// \return the new undirected edge.
1152    UEdge addEdge(const Node& s, const Node& t) {
1153      return Parent::addEdge(s, t);
1154    }
1155    /// \brief Changes the source of \c e to \c n
1156    ///
1157    /// Changes the source of \c e to \c n
1158    ///
1159    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1160    ///referencing the changed edge remain
1161    ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1162    void changeSource(UEdge e, Node n) {
1163      Parent::changeSource(e,n);
1164    }   
1165    /// \brief Changes the target of \c e to \c n
1166    ///
1167    /// Changes the target of \c e to \c n
1168    ///
1169    /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
1170    /// valid. However the other iterators may be invalidated.
1171    void changeTarget(UEdge e, Node n) {
1172      Parent::changeTarget(e,n);
1173    }
1174    /// \brief Changes the source of \c e to \c n
1175    ///
1176    /// Changes the source of \c e to \c n. It changes the proper
1177    /// node of the represented undirected edge.
1178    ///
1179    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1180    ///referencing the changed edge remain
1181    ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1182    void changeSource(Edge e, Node n) {
1183      if (Parent::direction(e)) {
1184        Parent::changeSource(e,n);
1185      } else {
1186        Parent::changeTarget(e,n);
1187      }
1188    }
1189    /// \brief Changes the target of \c e to \c n
1190    ///
1191    /// Changes the target of \c e to \c n. It changes the proper
1192    /// node of the represented undirected edge.
1193    ///
1194    ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1195    ///referencing the changed edge remain
1196    ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1197    void changeTarget(Edge e, Node n) {
1198      if (Parent::direction(e)) {
1199        Parent::changeTarget(e,n);
1200      } else {
1201        Parent::changeSource(e,n);
1202      }
1203    }
1204    /// \brief Contract two nodes.
1205    ///
1206    /// This function contracts two nodes.
1207    ///
1208    /// Node \p b will be removed but instead of deleting
1209    /// its neighboring edges, they will be joined to \p a.
1210    /// The last parameter \p r controls whether to remove loops. \c true
1211    /// means that loops will be removed.
1212    ///
1213    /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1214    /// valid.
1215    void contract(Node a, Node b, bool r = true) {
1216      for(IncEdgeIt e(*this, b); e!=INVALID;) {
1217        IncEdgeIt f = e; ++f;
1218        if (r && runningNode(e) == a) {
1219          erase(e);
1220        } else if (source(e) == b) {
1221          changeSource(e, a);
1222        } else {
1223          changeTarget(e, a);
1224        }
1225        e = f;
1226      }
1227      erase(b);
1228    }
1229
1230
1231    /// \brief Class to make a snapshot of the graph and restore
1232    /// to it later.
1233    ///
1234    /// Class to make a snapshot of the graph and to restore it
1235    /// later.
1236    ///
1237    /// The newly added nodes and undirected edges can be removed
1238    /// using the restore() function.
1239    ///
1240    /// \warning Edge and node deletions cannot be restored. This
1241    /// events invalidate the snapshot.
1242    class Snapshot {
1243    protected:
1244
1245      typedef Parent::NodeNotifier NodeNotifier;
1246
1247      class NodeObserverProxy : public NodeNotifier::ObserverBase {
1248      public:
1249
1250        NodeObserverProxy(Snapshot& _snapshot)
1251          : snapshot(_snapshot) {}
1252
1253        using NodeNotifier::ObserverBase::attach;
1254        using NodeNotifier::ObserverBase::detach;
1255        using NodeNotifier::ObserverBase::attached;
1256       
1257      protected:
1258       
1259        virtual void add(const Node& node) {
1260          snapshot.addNode(node);
1261        }
1262        virtual void add(const std::vector<Node>& nodes) {
1263          for (int i = nodes.size() - 1; i >= 0; ++i) {
1264            snapshot.addNode(nodes[i]);
1265          }
1266        }
1267        virtual void erase(const Node& node) {
1268          snapshot.eraseNode(node);
1269        }
1270        virtual void erase(const std::vector<Node>& nodes) {
1271          for (int i = 0; i < int(nodes.size()); ++i) {
1272            snapshot.eraseNode(nodes[i]);
1273          }
1274        }
1275        virtual void build() {
1276          Node node;
1277          std::vector<Node> nodes;
1278          for (notifier()->first(node); node != INVALID;
1279               notifier()->next(node)) {
1280            nodes.push_back(node);
1281          }
1282          for (int i = nodes.size() - 1; i >= 0; --i) {
1283            snapshot.addNode(nodes[i]);
1284          }
1285        }
1286        virtual void clear() {
1287          Node node;
1288          for (notifier()->first(node); node != INVALID;
1289               notifier()->next(node)) {
1290            snapshot.eraseNode(node);
1291          }
1292        }
1293
1294        Snapshot& snapshot;
1295      };
1296
1297      class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
1298      public:
1299
1300        UEdgeObserverProxy(Snapshot& _snapshot)
1301          : snapshot(_snapshot) {}
1302
1303        using UEdgeNotifier::ObserverBase::attach;
1304        using UEdgeNotifier::ObserverBase::detach;
1305        using UEdgeNotifier::ObserverBase::attached;
1306       
1307      protected:
1308
1309        virtual void add(const UEdge& edge) {
1310          snapshot.addUEdge(edge);
1311        }
1312        virtual void add(const std::vector<UEdge>& edges) {
1313          for (int i = edges.size() - 1; i >= 0; ++i) {
1314            snapshot.addUEdge(edges[i]);
1315          }
1316        }
1317        virtual void erase(const UEdge& edge) {
1318          snapshot.eraseUEdge(edge);
1319        }
1320        virtual void erase(const std::vector<UEdge>& edges) {
1321          for (int i = 0; i < int(edges.size()); ++i) {
1322            snapshot.eraseUEdge(edges[i]);
1323          }
1324        }
1325        virtual void build() {
1326          UEdge edge;
1327          std::vector<UEdge> edges;
1328          for (notifier()->first(edge); edge != INVALID;
1329               notifier()->next(edge)) {
1330            edges.push_back(edge);
1331          }
1332          for (int i = edges.size() - 1; i >= 0; --i) {
1333            snapshot.addUEdge(edges[i]);
1334          }
1335        }
1336        virtual void clear() {
1337          UEdge edge;
1338          for (notifier()->first(edge); edge != INVALID;
1339               notifier()->next(edge)) {
1340            snapshot.eraseUEdge(edge);
1341          }
1342        }
1343
1344        Snapshot& snapshot;
1345      };
1346     
1347      ListUGraph *graph;
1348
1349      NodeObserverProxy node_observer_proxy;
1350      UEdgeObserverProxy edge_observer_proxy;
1351
1352      std::list<Node> added_nodes;
1353      std::list<UEdge> added_edges;
1354
1355
1356      void addNode(const Node& node) {
1357        added_nodes.push_front(node);       
1358      }
1359      void eraseNode(const Node& node) {
1360        std::list<Node>::iterator it =
1361          std::find(added_nodes.begin(), added_nodes.end(), node);
1362        if (it == added_nodes.end()) {
1363          clear();
1364          edge_observer_proxy.detach();
1365          throw NodeNotifier::ImmediateDetach();
1366        } else {
1367          added_nodes.erase(it);
1368        }
1369      }
1370
1371      void addUEdge(const UEdge& edge) {
1372        added_edges.push_front(edge);       
1373      }
1374      void eraseUEdge(const UEdge& edge) {
1375        std::list<UEdge>::iterator it =
1376          std::find(added_edges.begin(), added_edges.end(), edge);
1377        if (it == added_edges.end()) {
1378          clear();
1379          node_observer_proxy.detach();
1380          throw UEdgeNotifier::ImmediateDetach();
1381        } else {
1382          added_edges.erase(it);
1383        }       
1384      }
1385
1386      void attach(ListUGraph &_graph) {
1387        graph = &_graph;
1388        node_observer_proxy.attach(graph->notifier(Node()));
1389        edge_observer_proxy.attach(graph->notifier(UEdge()));
1390      }
1391           
1392      void detach() {
1393        node_observer_proxy.detach();
1394        edge_observer_proxy.detach();
1395      }
1396
1397      bool attached() const {
1398        return node_observer_proxy.attached();
1399      }
1400
1401      void clear() {
1402        added_nodes.clear();
1403        added_edges.clear();       
1404      }
1405
1406    public:
1407
1408      /// \brief Default constructor.
1409      ///
1410      /// Default constructor.
1411      /// To actually make a snapshot you must call save().
1412      Snapshot()
1413        : graph(0), node_observer_proxy(*this),
1414          edge_observer_proxy(*this) {}
1415     
1416      /// \brief Constructor that immediately makes a snapshot.
1417      ///     
1418      /// This constructor immediately makes a snapshot of the graph.
1419      /// \param _graph The graph we make a snapshot of.
1420      Snapshot(ListUGraph &_graph)
1421        : node_observer_proxy(*this),
1422          edge_observer_proxy(*this) {
1423        attach(_graph);
1424      }
1425     
1426      /// \brief Make a snapshot.
1427      ///
1428      /// Make a snapshot of the graph.
1429      ///
1430      /// This function can be called more than once. In case of a repeated
1431      /// call, the previous snapshot gets lost.
1432      /// \param _graph The graph we make the snapshot of.
1433      void save(ListUGraph &_graph) {
1434        if (attached()) {
1435          detach();
1436          clear();
1437        }
1438        attach(_graph);
1439      }
1440     
1441      /// \brief Undo the changes until the last snapshot.
1442      //
1443      /// Undo the changes until the last snapshot created by save().
1444      void restore() {
1445        detach();
1446        for(std::list<UEdge>::iterator it = added_edges.begin();
1447            it != added_edges.end(); ++it) {
1448          graph->erase(*it);
1449        }
1450        for(std::list<Node>::iterator it = added_nodes.begin();
1451            it != added_nodes.end(); ++it) {
1452          graph->erase(*it);
1453        }
1454        clear();
1455      }
1456
1457      /// \brief Gives back true when the snapshot is valid.
1458      ///
1459      /// Gives back true when the snapshot is valid.
1460      bool valid() const {
1461        return attached();
1462      }
1463    };
1464  };
1465
1466
1467  class ListBpUGraphBase {
1468  public:
1469
1470    class NodeSetError : public LogicError {
1471    public:
1472      virtual const char* what() const throw() {
1473        return "lemon::ListBpUGraph::NodeSetError";
1474      }
1475    };
1476
1477  protected:
1478
1479    struct NodeT {
1480      int first_edge, prev, next;
1481    };
1482
1483    struct UEdgeT {
1484      int aNode, prev_out, next_out;
1485      int bNode, prev_in, next_in;
1486    };
1487
1488    std::vector<NodeT> aNodes;
1489    std::vector<NodeT> bNodes;
1490
1491    std::vector<UEdgeT> edges;
1492
1493    int first_anode;
1494    int first_free_anode;
1495
1496    int first_bnode;
1497    int first_free_bnode;
1498
1499    int first_free_edge;
1500
1501  public:
1502 
1503    class Node {
1504      friend class ListBpUGraphBase;
1505    protected:
1506      int id;
1507
1508      explicit Node(int _id) : id(_id) {}
1509    public:
1510      Node() {}
1511      Node(Invalid) { id = -1; }
1512      bool operator==(const Node i) const {return id==i.id;}
1513      bool operator!=(const Node i) const {return id!=i.id;}
1514      bool operator<(const Node i) const {return id<i.id;}
1515    };
1516
1517    class UEdge {
1518      friend class ListBpUGraphBase;
1519    protected:
1520      int id;
1521
1522      explicit UEdge(int _id) { id = _id;}
1523    public:
1524      UEdge() {}
1525      UEdge (Invalid) { id = -1; }
1526      bool operator==(const UEdge i) const {return id==i.id;}
1527      bool operator!=(const UEdge i) const {return id!=i.id;}
1528      bool operator<(const UEdge i) const {return id<i.id;}
1529    };
1530
1531    ListBpUGraphBase()
1532      : first_anode(-1), first_free_anode(-1),
1533        first_bnode(-1), first_free_bnode(-1),
1534        first_free_edge(-1) {}
1535
1536    void firstANode(Node& node) const {
1537      node.id = first_anode != -1 ? (first_anode << 1) : -1;
1538    }
1539    void nextANode(Node& node) const {
1540      node.id = aNodes[node.id >> 1].next;
1541    }
1542
1543    void firstBNode(Node& node) const {
1544      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1545    }
1546    void nextBNode(Node& node) const {
1547      node.id = bNodes[node.id >> 1].next;
1548    }
1549
1550    void first(Node& node) const {
1551      if (first_anode != -1) {
1552        node.id = (first_anode << 1);
1553      } else if (first_bnode != -1) {
1554        node.id = (first_bnode << 1) + 1;
1555      } else {
1556        node.id = -1;
1557      }
1558    }
1559    void next(Node& node) const {
1560      if (aNode(node)) {
1561        node.id = aNodes[node.id >> 1].next;
1562        if (node.id == -1) {
1563          if (first_bnode != -1) {
1564            node.id = (first_bnode << 1) + 1;
1565          }
1566        }
1567      } else {
1568        node.id = bNodes[node.id >> 1].next;
1569      }
1570    }
1571 
1572    void first(UEdge& edge) const {
1573      int aid = first_anode;
1574      while (aid != -1 && aNodes[aid].first_edge == -1) {
1575        aid = aNodes[aid].next != -1 ?
1576          aNodes[aid].next >> 1 : -1;
1577      }
1578      if (aid != -1) {
1579        edge.id = aNodes[aid].first_edge;
1580      } else {
1581        edge.id = -1;
1582      }
1583    }
1584    void next(UEdge& edge) const {
1585      int aid = edges[edge.id].aNode >> 1;
1586      edge.id = edges[edge.id].next_out;
1587      if (edge.id == -1) {
1588        aid = aNodes[aid].next != -1 ?
1589          aNodes[aid].next >> 1 : -1;
1590        while (aid != -1 && aNodes[aid].first_edge == -1) {
1591          aid = aNodes[aid].next != -1 ?
1592          aNodes[aid].next >> 1 : -1;
1593        }
1594        if (aid != -1) {
1595          edge.id = aNodes[aid].first_edge;
1596        } else {
1597          edge.id = -1;
1598        }
1599      }
1600    }
1601
1602    void firstFromANode(UEdge& edge, const Node& node) const {
1603      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1604      edge.id = aNodes[node.id >> 1].first_edge;
1605    }
1606    void nextFromANode(UEdge& edge) const {
1607      edge.id = edges[edge.id].next_out;
1608    }
1609
1610    void firstFromBNode(UEdge& edge, const Node& node) const {
1611      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1612      edge.id = bNodes[node.id >> 1].first_edge;
1613    }
1614    void nextFromBNode(UEdge& edge) const {
1615      edge.id = edges[edge.id].next_in;
1616    }
1617
1618    static int id(const Node& node) {
1619      return node.id;
1620    }
1621    static Node nodeFromId(int id) {
1622      return Node(id);
1623    }
1624    int maxNodeId() const {
1625      return aNodes.size() > bNodes.size() ?
1626        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
1627    }
1628 
1629    static int id(const UEdge& edge) {
1630      return edge.id;
1631    }
1632    static UEdge uEdgeFromId(int id) {
1633      return UEdge(id);
1634    }
1635    int maxUEdgeId() const {
1636      return edges.size();
1637    }
1638 
1639    static int aNodeId(const Node& node) {
1640      return node.id >> 1;
1641    }
1642    static Node nodeFromANodeId(int id) {
1643      return Node(id << 1);
1644    }
1645    int maxANodeId() const {
1646      return aNodes.size();
1647    }
1648
1649    static int bNodeId(const Node& node) {
1650      return node.id >> 1;
1651    }
1652    static Node nodeFromBNodeId(int id) {
1653      return Node((id << 1) + 1);
1654    }
1655    int maxBNodeId() const {
1656      return bNodes.size();
1657    }
1658
1659    Node aNode(const UEdge& edge) const {
1660      return Node(edges[edge.id].aNode);
1661    }
1662    Node bNode(const UEdge& edge) const {
1663      return Node(edges[edge.id].bNode);
1664    }
1665
1666    static bool aNode(const Node& node) {
1667      return (node.id & 1) == 0;
1668    }
1669
1670    static bool bNode(const Node& node) {
1671      return (node.id & 1) == 1;
1672    }
1673
1674    Node addANode() {
1675      int aid;
1676      if (first_free_anode == -1) {
1677        aid = aNodes.size();
1678        aNodes.push_back(NodeT());
1679      } else {
1680        aid = first_free_anode;
1681        first_free_anode = aNodes[first_free_anode].next;
1682      }
1683      if (first_anode != -1) {
1684        aNodes[aid].next = first_anode << 1;
1685        aNodes[first_anode].prev = aid << 1;
1686      } else {
1687        aNodes[aid].next = -1;
1688      }
1689      aNodes[aid].prev = -1;
1690      first_anode = aid;
1691      aNodes[aid].first_edge = -1;
1692      return Node(aid << 1);
1693    }
1694
1695    Node addBNode() {
1696      int bid;
1697      if (first_free_bnode == -1) {
1698        bid = bNodes.size();
1699        bNodes.push_back(NodeT());
1700      } else {
1701        bid = first_free_bnode;
1702        first_free_bnode = bNodes[first_free_bnode].next;
1703      }
1704      if (first_bnode != -1) {
1705        bNodes[bid].next = (first_bnode << 1) + 1;
1706        bNodes[first_bnode].prev = (bid << 1) + 1;
1707      } else {
1708        bNodes[bid].next = -1;
1709      }
1710      bNodes[bid].prev = -1;
1711      first_bnode = bid;
1712      bNodes[bid].first_edge = -1;
1713      return Node((bid << 1) + 1);
1714    }
1715
1716    UEdge addEdge(const Node& source, const Node& target) {
1717      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1718      int edgeId;
1719      if (first_free_edge != -1) {
1720        edgeId = first_free_edge;
1721        first_free_edge = edges[edgeId].next_out;
1722      } else {
1723        edgeId = edges.size();
1724        edges.push_back(UEdgeT());
1725      }
1726      if ((source.id & 1) == 0) {
1727        edges[edgeId].aNode = source.id;
1728        edges[edgeId].bNode = target.id;
1729      } else {
1730        edges[edgeId].aNode = target.id;
1731        edges[edgeId].bNode = source.id;
1732      }
1733      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
1734      edges[edgeId].prev_out = -1;
1735      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
1736        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
1737      }
1738      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
1739      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
1740      edges[edgeId].prev_in = -1;
1741      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
1742        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
1743      }
1744      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
1745      return UEdge(edgeId);
1746    }
1747
1748    void erase(const Node& node) {
1749      if (aNode(node)) {
1750        int aid = node.id >> 1;
1751        if (aNodes[aid].prev != -1) {
1752          aNodes[aNodes[aid].prev >> 1].next = aNodes[aid].next;
1753        } else {
1754          first_anode =
1755            aNodes[aid].next != -1 ? aNodes[aid].next >> 1 : -1;
1756        }
1757        if (aNodes[aid].next != -1) {
1758          aNodes[aNodes[aid].next >> 1].prev = aNodes[aid].prev;
1759        }
1760        aNodes[aid].next = first_free_anode;
1761        first_free_anode = aid;
1762      } else {
1763        int bid = node.id >> 1;
1764        if (bNodes[bid].prev != -1) {
1765          bNodes[bNodes[bid].prev >> 1].next = bNodes[bid].next;
1766        } else {
1767          first_bnode =
1768            bNodes[bid].next != -1 ? bNodes[bid].next >> 1 : -1;
1769        }
1770        if (bNodes[bid].next != -1) {
1771          bNodes[bNodes[bid].next >> 1].prev = bNodes[bid].prev;
1772        }
1773        bNodes[bid].next = first_free_bnode;
1774        first_free_bnode = bid;
1775      }
1776    }
1777
1778    void erase(const UEdge& edge) {
1779
1780      if (edges[edge.id].prev_out != -1) {
1781        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1782      } else {
1783        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1784      }
1785      if (edges[edge.id].next_out != -1) {
1786        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1787      }
1788
1789      if (edges[edge.id].prev_in != -1) {
1790        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1791      } else {
1792        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1793      }
1794      if (edges[edge.id].next_in != -1) {
1795        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1796      }
1797
1798      edges[edge.id].next_out = first_free_edge;
1799      first_free_edge = edge.id;
1800    }
1801 
1802    void clear() {
1803      aNodes.clear();
1804      bNodes.clear();
1805      edges.clear();
1806      first_anode = -1;
1807      first_free_anode = -1;
1808      first_bnode = -1;
1809      first_free_bnode = -1;
1810      first_free_edge = -1;
1811    }
1812
1813    void changeANode(const UEdge& edge, const Node& node) {
1814      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1815      if (edges[edge.id].prev_out != -1) {
1816        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1817      } else {
1818        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1819      }
1820      if (edges[edge.id].next_out != -1) {
1821        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; 
1822      }
1823      if (aNodes[node.id >> 1].first_edge != -1) {
1824        edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
1825      }
1826      edges[edge.id].prev_out = -1;
1827      edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
1828      aNodes[node.id >> 1].first_edge = edge.id;
1829      edges[edge.id].aNode = node.id;
1830    }
1831
1832    void changeBNode(const UEdge& edge, const Node& node) {
1833      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1834      if (edges[edge.id].prev_in != -1) {
1835        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1836      } else {
1837        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1838      }
1839      if (edges[edge.id].next_in != -1) {
1840        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; 
1841      }
1842      if (bNodes[node.id >> 1].first_edge != -1) {
1843        edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
1844      }
1845      edges[edge.id].prev_in = -1;
1846      edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
1847      bNodes[node.id >> 1].first_edge = edge.id;
1848      edges[edge.id].bNode = node.id;
1849    }
1850
1851  };
1852
1853
1854  typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> >
1855  ExtendedListBpUGraphBase;
1856
1857  /// \ingroup graphs
1858  ///
1859  /// \brief A smart bipartite undirected graph class.
1860  ///
1861  /// This is a bipartite undirected graph implementation.
1862  /// It is conforms to the \ref concepts::BpUGraph "BpUGraph concept".
1863  ///
1864  ///An important extra feature of this graph implementation is that
1865  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1866  ///
1867  /// \sa concepts::BpUGraph.
1868  ///
1869  class ListBpUGraph : public ExtendedListBpUGraphBase {
1870    /// \brief ListBpUGraph is \e not copy constructible.
1871    ///
1872    ///ListBpUGraph is \e not copy constructible.
1873    ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase()  {};
1874    /// \brief Assignment of ListBpUGraph to another one is \e not
1875    /// allowed.
1876    ///
1877    /// Assignment of ListBpUGraph to another one is \e not allowed.
1878    void operator=(const ListBpUGraph &) {}
1879  public:
1880    /// \brief Constructor
1881    ///   
1882    /// Constructor.
1883    ///
1884    ListBpUGraph() {}
1885
1886    typedef ExtendedListBpUGraphBase Parent;
1887    /// \brief Add a new ANode to the graph.
1888    ///
1889    /// \return the new node.
1890    ///
1891    Node addANode() { return Parent::addANode(); }
1892
1893    /// \brief Add a new BNode to the graph.
1894    ///
1895    /// \return the new node.
1896    ///
1897    Node addBNode() { return Parent::addBNode(); }
1898
1899    /// \brief Add a new edge to the graph.
1900    ///
1901    /// Add a new edge to the graph with an ANode and a BNode.
1902    /// \return the new undirected edge.
1903    UEdge addEdge(const Node& s, const Node& t) {
1904      return Parent::addEdge(s, t);
1905    }
1906
1907    /// \brief Changes the ANode of \c e to \c n
1908    ///
1909    /// Changes the ANode of \c e to \c n
1910    ///
1911    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1912    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1913    ///invalidated.
1914    void changeANode(UEdge e, Node n) {
1915      Parent::changeANode(e,n);
1916    }
1917
1918    /// \brief Changes the BNode of \c e to \c n
1919    ///
1920    /// Changes the BNode of \c e to \c n
1921    ///
1922    /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1923    /// referencing the changed edge remain
1924    /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1925    void changeBNode(UEdge e, Node n) {
1926      Parent::changeBNode(e,n);
1927    }
1928
1929    /// \brief Changes the source(ANode) of \c e to \c n
1930    ///
1931    /// Changes the source(ANode) of \c e to \c n
1932    ///
1933    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1934    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1935    ///invalidated.
1936    void changeSource(UEdge e, Node n) {
1937      Parent::changeANode(e,n);
1938    }
1939
1940    /// \brief Changes the target(BNode) of \c e to \c n
1941    ///
1942    /// Changes the target(BNode) of \c e to \c n
1943    ///
1944    /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1945    /// referencing the changed edge remain
1946    /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1947    void changeTarget(UEdge e, Node n) {
1948      Parent::changeBNode(e,n);
1949    }
1950
1951    /// \brief Changes the source of \c e to \c n
1952    ///
1953    /// Changes the source of \c e to \c n. It changes the proper
1954    /// node of the represented undirected edge.
1955    ///
1956    ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1957    ///referencing the changed edge remain
1958    ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1959    void changeSource(Edge e, Node n) {
1960      if (Parent::direction(e)) {
1961        Parent::changeANode(e,n);
1962      } else {
1963        Parent::changeBNode(e,n);
1964      }
1965    }
1966    /// \brief Changes the target of \c e to \c n
1967    ///
1968    /// Changes the target of \c e to \c n. It changes the proper
1969    /// node of the represented undirected edge.
1970    ///
1971    ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1972    ///referencing the changed edge remain
1973    ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1974    void changeTarget(Edge e, Node n) {
1975      if (Parent::direction(e)) {
1976        Parent::changeBNode(e,n);
1977      } else {
1978        Parent::changeANode(e,n);
1979      }
1980    }
1981    /// \brief Contract two nodes.
1982    ///
1983    /// This function contracts two nodes.
1984    ///
1985    /// Node \p b will be removed but instead of deleting its
1986    /// neighboring edges, they will be joined to \p a.  The two nodes
1987    /// should be from the same nodeset, of course.
1988    ///
1989    /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1990    /// valid.
1991    void contract(const Node& a, const Node& b) {
1992      LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
1993      if (Parent::aNode(a)) {
1994        for (IncEdgeIt e(*this, b); e!=INVALID;) {
1995          IncEdgeIt f = e; ++f;
1996          changeSource(e, a);
1997          e = f;
1998        }
1999      } else {
2000        for (IncEdgeIt e(*this, b); e!=INVALID;) {
2001          IncEdgeIt f = e; ++f;
2002          changeTarget(e, a);
2003          e = f;
2004        }
2005      }
2006      erase(b);
2007    }
2008
2009    /// \brief Class to make a snapshot of the graph and restore
2010    /// to it later.
2011    ///
2012    /// Class to make a snapshot of the graph and to restore it
2013    /// later.
2014    ///
2015    /// The newly added nodes and undirected edges can be removed
2016    /// using the restore() function.
2017    ///
2018    /// \warning Edge and node deletions cannot be restored. This
2019    /// events invalidate the snapshot.
2020    class Snapshot {
2021    protected:
2022
2023      typedef Parent::NodeNotifier NodeNotifier;
2024
2025      class NodeObserverProxy : public NodeNotifier::ObserverBase {
2026      public:
2027
2028        NodeObserverProxy(Snapshot& _snapshot)
2029          : snapshot(_snapshot) {}
2030
2031        using NodeNotifier::ObserverBase::attach;
2032        using NodeNotifier::ObserverBase::detach;
2033        using NodeNotifier::ObserverBase::attached;
2034       
2035      protected:
2036       
2037        virtual void add(const Node& node) {
2038          snapshot.addNode(node);
2039        }
2040        virtual void add(const std::vector<Node>& nodes) {
2041          for (int i = nodes.size() - 1; i >= 0; ++i) {
2042            snapshot.addNode(nodes[i]);
2043          }
2044        }
2045        virtual void erase(const Node& node) {
2046          snapshot.eraseNode(node);
2047        }
2048        virtual void erase(const std::vector<Node>& nodes) {
2049          for (int i = 0; i < int(nodes.size()); ++i) {
2050            snapshot.eraseNode(nodes[i]);
2051          }
2052        }
2053        virtual void build() {
2054          Node node;
2055          std::vector<Node> nodes;
2056          for (notifier()->first(node); node != INVALID;
2057               notifier()->next(node)) {
2058            nodes.push_back(node);
2059          }
2060          for (int i = nodes.size() - 1; i >= 0; --i) {
2061            snapshot.addNode(nodes[i]);
2062          }
2063        }
2064        virtual void clear() {
2065          Node node;
2066          for (notifier()->first(node); node != INVALID;
2067               notifier()->next(node)) {
2068            snapshot.eraseNode(node);
2069          }
2070        }
2071
2072        Snapshot& snapshot;
2073      };
2074
2075      class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
2076      public:
2077
2078        UEdgeObserverProxy(Snapshot& _snapshot)
2079          : snapshot(_snapshot) {}
2080
2081        using UEdgeNotifier::ObserverBase::attach;
2082        using UEdgeNotifier::ObserverBase::detach;
2083        using UEdgeNotifier::ObserverBase::attached;
2084       
2085      protected:
2086
2087        virtual void add(const UEdge& edge) {
2088          snapshot.addUEdge(edge);
2089        }
2090        virtual void add(const std::vector<UEdge>& edges) {
2091          for (int i = edges.size() - 1; i >= 0; ++i) {
2092            snapshot.addUEdge(edges[i]);
2093          }
2094        }
2095        virtual void erase(const UEdge& edge) {
2096          snapshot.eraseUEdge(edge);
2097        }
2098        virtual void erase(const std::vector<UEdge>& edges) {
2099          for (int i = 0; i < int(edges.size()); ++i) {
2100            snapshot.eraseUEdge(edges[i]);
2101          }
2102        }
2103        virtual void build() {
2104          UEdge edge;
2105          std::vector<UEdge> edges;
2106          for (notifier()->first(edge); edge != INVALID;
2107               notifier()->next(edge)) {
2108            edges.push_back(edge);
2109          }
2110          for (int i = edges.size() - 1; i >= 0; --i) {
2111            snapshot.addUEdge(edges[i]);
2112          }
2113        }
2114        virtual void clear() {
2115          UEdge edge;
2116          for (notifier()->first(edge); edge != INVALID;
2117               notifier()->next(edge)) {
2118            snapshot.eraseUEdge(edge);
2119          }
2120        }
2121
2122        Snapshot& snapshot;
2123      };
2124     
2125      ListBpUGraph *graph;
2126
2127      NodeObserverProxy node_observer_proxy;
2128      UEdgeObserverProxy edge_observer_proxy;
2129
2130      std::list<Node> added_nodes;
2131      std::list<UEdge> added_edges;
2132
2133
2134      void addNode(const Node& node) {
2135        added_nodes.push_front(node);       
2136      }
2137      void eraseNode(const Node& node) {
2138        std::list<Node>::iterator it =
2139          std::find(added_nodes.begin(), added_nodes.end(), node);
2140        if (it == added_nodes.end()) {
2141          clear();
2142          edge_observer_proxy.detach();
2143          throw NodeNotifier::ImmediateDetach();
2144        } else {
2145          added_nodes.erase(it);
2146        }
2147      }
2148
2149      void addUEdge(const UEdge& edge) {
2150        added_edges.push_front(edge);       
2151      }
2152      void eraseUEdge(const UEdge& edge) {
2153        std::list<UEdge>::iterator it =
2154          std::find(added_edges.begin(), added_edges.end(), edge);
2155        if (it == added_edges.end()) {
2156          clear();
2157          node_observer_proxy.detach();
2158          throw UEdgeNotifier::ImmediateDetach();
2159        } else {
2160          added_edges.erase(it);
2161        }       
2162      }
2163
2164      void attach(ListBpUGraph &_graph) {
2165        graph = &_graph;
2166        node_observer_proxy.attach(graph->notifier(Node()));
2167        edge_observer_proxy.attach(graph->notifier(UEdge()));
2168      }
2169           
2170      void detach() {
2171        node_observer_proxy.detach();
2172        edge_observer_proxy.detach();
2173      }
2174
2175      bool attached() const {
2176        return node_observer_proxy.attached();
2177      }
2178
2179      void clear() {
2180        added_nodes.clear();
2181        added_edges.clear();       
2182      }
2183
2184    public:
2185
2186      /// \brief Default constructor.
2187      ///
2188      /// Default constructor.
2189      /// To actually make a snapshot you must call save().
2190      Snapshot()
2191        : graph(0), node_observer_proxy(*this),
2192          edge_observer_proxy(*this) {}
2193     
2194      /// \brief Constructor that immediately makes a snapshot.
2195      ///     
2196      /// This constructor immediately makes a snapshot of the graph.
2197      /// \param _graph The graph we make a snapshot of.
2198      Snapshot(ListBpUGraph &_graph)
2199        : node_observer_proxy(*this),
2200          edge_observer_proxy(*this) {
2201        attach(_graph);
2202      }
2203     
2204      /// \brief Make a snapshot.
2205      ///
2206      /// Make a snapshot of the graph.
2207      ///
2208      /// This function can be called more than once. In case of a repeated
2209      /// call, the previous snapshot gets lost.
2210      /// \param _graph The graph we make the snapshot of.
2211      void save(ListBpUGraph &_graph) {
2212        if (attached()) {
2213          detach();
2214          clear();
2215        }
2216        attach(_graph);
2217      }
2218     
2219      /// \brief Undo the changes until the last snapshot.
2220      //
2221      /// Undo the changes until the last snapshot created by save().
2222      void restore() {
2223        detach();
2224        for(std::list<UEdge>::iterator it = added_edges.begin();
2225            it != added_edges.end(); ++it) {
2226          graph->erase(*it);
2227        }
2228        for(std::list<Node>::iterator it = added_nodes.begin();
2229            it != added_nodes.end(); ++it) {
2230          graph->erase(*it);
2231        }
2232        clear();
2233      }
2234
2235      /// \brief Gives back true when the snapshot is valid.
2236      ///
2237      /// Gives back true when the snapshot is valid.
2238      bool valid() const {
2239        return attached();
2240      }
2241    };
2242  };
2243
2244 
2245  /// @} 
2246} //namespace lemon
2247 
2248
2249#endif
Note: See TracBrowser for help on using the repository browser.