COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/list_graph.h @ 2301:eb378706bd3d

Last change on this file since 2301:eb378706bd3d was 2301:eb378706bd3d, checked in by Alpar Juttner, 13 years ago

Test the automatic compilation checker 1/2: make a bug

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