COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2192:d6e4efb477d8

Last change on this file since 2192:d6e4efb477d8 was 2190:dd887831e9c1, checked in by Balazs Dezso, 13 years ago

Snapshot for SmartUGraph an SmartBpUGraph

File size: 23.7 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_SMART_GRAPH_H
20#define LEMON_SMART_GRAPH_H
21
22///\ingroup graphs
23///\file
24///\brief SmartGraph and SmartUGraph classes.
25
26#include <vector>
27
28#include <lemon/bits/invalid.h>
29
30#include <lemon/bits/base_extender.h>
31#include <lemon/bits/graph_extender.h>
32
33#include <lemon/bits/utility.h>
34#include <lemon/error.h>
35
36#include <lemon/bits/graph_extender.h>
37
38namespace lemon {
39
40  class SmartGraph;
41  ///Base of SmartGraph
42
43  ///Base of SmartGraph
44  ///
45  class SmartGraphBase {
46  protected:
47
48    struct NodeT
49    {
50      int first_in, first_out;     
51      NodeT() {}
52    };
53    struct EdgeT
54    {
55      int target, source, next_in, next_out;     
56      EdgeT() {} 
57    };
58
59    std::vector<NodeT> nodes;
60
61    std::vector<EdgeT> edges;
62   
63   
64  public:
65
66    typedef SmartGraphBase Graph;
67
68    class Node;
69    class Edge;
70
71   
72  public:
73
74    SmartGraphBase() : nodes(), edges() { }
75    SmartGraphBase(const SmartGraphBase &_g)
76      : nodes(_g.nodes), edges(_g.edges) { }
77   
78    typedef True NodeNumTag;
79    typedef True EdgeNumTag;
80
81    int nodeNum() const { return nodes.size(); }
82    int edgeNum() const { return edges.size(); }
83
84    int maxNodeId() const { return nodes.size()-1; }
85    int maxEdgeId() const { return edges.size()-1; }
86
87    Node addNode() {
88      int n = nodes.size();     
89      nodes.push_back(NodeT());
90      nodes[n].first_in = -1;
91      nodes[n].first_out = -1;
92      return Node(n);
93    }
94   
95    Edge addEdge(Node u, Node v) {
96      int n = edges.size();
97      edges.push_back(EdgeT());
98      edges[n].source = u.id;
99      edges[n].target = v.id;
100      edges[n].next_out = nodes[u.id].first_out;
101      edges[n].next_in = nodes[v.id].first_in;
102      nodes[u.id].first_out = nodes[v.id].first_in = n;
103
104      return Edge(n);
105    }
106
107    void clear() {
108      edges.clear();
109      nodes.clear();
110    }
111
112    Node source(Edge e) const { return Node(edges[e.id].source); }
113    Node target(Edge e) const { return Node(edges[e.id].target); }
114
115    static int id(Node v) { return v.id; }
116    static int id(Edge e) { return e.id; }
117
118    static Node nodeFromId(int id) { return Node(id);}
119    static Edge edgeFromId(int id) { return Edge(id);}
120
121    class Node {
122      friend class SmartGraphBase;
123      friend class SmartGraph;
124
125    protected:
126      int id;
127      explicit Node(int _id) : id(_id) {}
128    public:
129      Node() {}
130      Node (Invalid) : id(-1) {}
131      bool operator==(const Node i) const {return id == i.id;}
132      bool operator!=(const Node i) const {return id != i.id;}
133      bool operator<(const Node i) const {return id < i.id;}
134    };
135   
136
137    class Edge {
138      friend class SmartGraphBase;
139      friend class SmartGraph;
140
141    protected:
142      int id;
143      explicit Edge(int _id) : id(_id) {}
144    public:
145      Edge() { }
146      Edge (Invalid) : id(-1) {}
147      bool operator==(const Edge i) const {return id == i.id;}
148      bool operator!=(const Edge i) const {return id != i.id;}
149      bool operator<(const Edge i) const {return id < i.id;}
150    };
151
152    void first(Node& node) const {
153      node.id = nodes.size() - 1;
154    }
155
156    static void next(Node& node) {
157      --node.id;
158    }
159
160    void first(Edge& edge) const {
161      edge.id = edges.size() - 1;
162    }
163
164    static void next(Edge& edge) {
165      --edge.id;
166    }
167
168    void firstOut(Edge& edge, const Node& node) const {
169      edge.id = nodes[node.id].first_out;
170    }
171
172    void nextOut(Edge& edge) const {
173      edge.id = edges[edge.id].next_out;
174    }
175
176    void firstIn(Edge& edge, const Node& node) const {
177      edge.id = nodes[node.id].first_in;
178    }
179   
180    void nextIn(Edge& edge) const {
181      edge.id = edges[edge.id].next_in;
182    }
183
184  };
185
186  typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
187
188  /// \ingroup graphs
189
190  ///A smart graph class.
191
192  ///This is a simple and fast graph implementation.
193  ///It is also quite memory efficient, but at the price
194  ///that <b> it does support only limited (only stack-like)
195  ///node and edge deletions</b>.
196  ///It conforms to
197  ///the \ref concept::Graph "Graph concept".
198  ///\sa concept::Graph.
199  ///
200  ///\author Alpar Juttner
201  class SmartGraph : public ExtendedSmartGraphBase {
202  public:
203
204    typedef ExtendedSmartGraphBase Parent;
205
206  private:
207
208    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
209
210    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
211    ///
212    SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
213    ///\brief Assignment of SmartGraph to another one is \e not allowed.
214    ///Use GraphCopy() instead.
215
216    ///Assignment of SmartGraph to another one is \e not allowed.
217    ///Use GraphCopy() instead.
218    void operator=(const SmartGraph &) {}
219
220  public:
221   
222    /// Constructor
223   
224    /// Constructor.
225    ///
226    SmartGraph() {};
227   
228    ///Add a new node to the graph.
229   
230    /// \return the new node.
231    ///
232    Node addNode() { return Parent::addNode(); }
233   
234    ///Add a new edge to the graph.
235   
236    ///Add a new edge to the graph with source node \c s
237    ///and target node \c t.
238    ///\return the new edge.
239    Edge addEdge(const Node& s, const Node& t) {
240      return Parent::addEdge(s, t);
241    }
242
243    ///Clear the graph.
244   
245    ///Erase all the nodes and edges from the graph.
246    ///
247    void clear() {
248      Parent::clear();
249    }
250
251    ///Split a node.
252   
253    ///This function splits a node. First a new node is added to the graph,
254    ///then the source of each outgoing edge of \c n is moved to this new node.
255    ///If \c connect is \c true (this is the default value), then a new edge
256    ///from \c n to the newly created node is also added.
257    ///\return The newly created node.
258    ///
259    ///\note The <tt>Edge</tt>s
260    ///referencing a moved edge remain
261    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
262    ///may be invalidated.
263    ///\warning This functionality cannot be used together with the Snapshot
264    ///feature.
265    ///\todo It could be implemented in a bit faster way.
266    Node split(Node n, bool connect = true)
267    {
268      Node b = addNode();
269      nodes[b.id].first_out=nodes[n.id].first_out;
270      nodes[n.id].first_out=-1;
271      for(int i=nodes[b.id].first_out;i!=-1;i++) edges[i].source=b.id;
272      if(connect) addEdge(n,b);
273      return b;
274    }
275
276  public:
277   
278    class Snapshot;
279
280  protected:
281
282    void restoreSnapshot(const Snapshot &s)
283    {
284      while(s.edge_num<edges.size()) {
285        Edge edge = edgeFromId(edges.size()-1);
286        Parent::getNotifier(Edge()).erase(edge);
287        nodes[edges.back().source].first_out=edges.back().next_out;
288        nodes[edges.back().target].first_in=edges.back().next_in;
289        edges.pop_back();
290      }
291      while(s.node_num<nodes.size()) {
292        Node node = nodeFromId(nodes.size()-1);
293        Parent::getNotifier(Node()).erase(node);
294        nodes.pop_back();
295      }
296    }   
297
298  public:
299
300    ///Class to make a snapshot of the graph and to restrore to it later.
301
302    ///Class to make a snapshot of the graph and to restrore to it later.
303    ///
304    ///The newly added nodes and edges can be removed using the
305    ///restore() function.
306    ///\note After you restore a state, you cannot restore
307    ///a later state, in other word you cannot add again the edges deleted
308    ///by restore() using another one Snapshot instance.
309    ///
310    ///\warning If you do not use correctly the snapshot that can cause
311    ///either broken program, invalid state of the graph, valid but
312    ///not the restored graph or no change. Because the runtime performance
313    ///the validity of the snapshot is not stored.
314    class Snapshot
315    {
316      SmartGraph *g;
317    protected:
318      friend class SmartGraph;
319      unsigned int node_num;
320      unsigned int edge_num;
321    public:
322      ///Default constructor.
323     
324      ///Default constructor.
325      ///To actually make a snapshot you must call save().
326      ///
327      Snapshot() : g(0) {}
328      ///Constructor that immediately makes a snapshot
329     
330      ///This constructor immediately makes a snapshot of the graph.
331      ///\param _g The graph we make a snapshot of.
332      Snapshot(SmartGraph &_g) :g(&_g) {
333        node_num=g->nodes.size();
334        edge_num=g->edges.size();
335      }
336
337      ///Make a snapshot.
338
339      ///Make a snapshot of the graph.
340      ///
341      ///This function can be called more than once. In case of a repeated
342      ///call, the previous snapshot gets lost.
343      ///\param _g The graph we make the snapshot of.
344      void save(SmartGraph &_g)
345      {
346        g=&_g;
347        node_num=g->nodes.size();
348        edge_num=g->edges.size();
349      }
350
351      ///Undo the changes until a snapshot.
352     
353      ///Undo the changes until a snapshot created by save().
354      ///
355      ///\note After you restored a state, you cannot restore
356      ///a later state, in other word you cannot add again the edges deleted
357      ///by restore().
358      void restore()
359      {
360        g->restoreSnapshot(*this);
361      }
362    };
363  };
364
365
366  /**************** Undirected List Graph ****************/
367
368  typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
369  ExtendedSmartUGraphBase;
370
371  /// \ingroup graphs
372  ///
373  /// \brief A smart undirected graph class.
374  ///
375  /// This is a simple and fast undirected graph implementation.
376  /// It is also quite memory efficient, but at the price
377  /// that <b> it does support only limited (only stack-like)
378  /// node and edge deletions</b>.
379  /// Except from this it conforms to
380  /// the \ref concept::UGraph "UGraph concept".
381  /// \sa concept::UGraph.
382  ///
383  /// \todo Snapshot hasn't been implemented yet.
384  ///
385  class SmartUGraph : public ExtendedSmartUGraphBase {
386  private:
387
388    ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
389
390    ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
391    ///
392    SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {};
393
394    ///\brief Assignment of SmartUGraph to another one is \e not allowed.
395    ///Use UGraphCopy() instead.
396
397    ///Assignment of SmartUGraph to another one is \e not allowed.
398    ///Use UGraphCopy() instead.
399    void operator=(const SmartUGraph &) {}
400
401  public:
402
403    typedef ExtendedSmartUGraphBase Parent;
404
405    /// Constructor
406   
407    /// Constructor.
408    ///
409    SmartUGraph() {}
410
411    ///Add a new node to the graph.
412   
413    /// \return the new node.
414    ///
415    Node addNode() { return Parent::addNode(); }
416   
417    ///Add a new undirected edge to the graph.
418   
419    ///Add a new undirected edge to the graph with node \c s
420    ///and \c t.
421    ///\return the new undirected edge.
422    UEdge addEdge(const Node& s, const Node& t) {
423      return Parent::addEdge(s, t);
424    }
425
426    ///Clear the graph.
427   
428    ///Erase all the nodes and edges from the graph.
429    ///
430    void clear() {
431      Parent::clear();
432    }
433
434  public:
435   
436    class Snapshot;
437
438  protected:
439
440
441    void restoreSnapshot(const Snapshot &s)
442    {
443      while(s.edge_num<edges.size()) {
444        UEdge edge = uEdgeFromId(edges.size()-1);
445        Parent::getNotifier(UEdge()).erase(edge);
446        std::vector<Edge> dir;
447        dir.push_back(Parent::direct(edge, true));
448        dir.push_back(Parent::direct(edge, false));
449        Parent::getNotifier(Edge()).erase(dir);
450        nodes[edges.back().source].first_out=edges.back().next_out;
451        nodes[edges.back().target].first_in=edges.back().next_in;
452        edges.pop_back();
453      }
454      while(s.node_num<nodes.size()) {
455        Node node = nodeFromId(nodes.size()-1);
456        Parent::getNotifier(Node()).erase(node);
457        nodes.pop_back();
458      }
459    }   
460
461  public:
462
463    ///Class to make a snapshot of the graph and to restrore to it later.
464
465    ///Class to make a snapshot of the graph and to restrore to it later.
466    ///
467    ///The newly added nodes and edges can be removed using the
468    ///restore() function.
469    ///
470    ///\note After you restore a state, you cannot restore
471    ///a later state, in other word you cannot add again the edges deleted
472    ///by restore() using another one Snapshot instance.
473    ///
474    ///\warning If you do not use correctly the snapshot that can cause
475    ///either broken program, invalid state of the graph, valid but
476    ///not the restored graph or no change. Because the runtime performance
477    ///the validity of the snapshot is not stored.
478    class Snapshot
479    {
480      SmartUGraph *g;
481    protected:
482      friend class SmartUGraph;
483      unsigned int node_num;
484      unsigned int edge_num;
485    public:
486      ///Default constructor.
487     
488      ///Default constructor.
489      ///To actually make a snapshot you must call save().
490      ///
491      Snapshot() : g(0) {}
492      ///Constructor that immediately makes a snapshot
493     
494      ///This constructor immediately makes a snapshot of the graph.
495      ///\param _g The graph we make a snapshot of.
496      Snapshot(SmartUGraph &_g) :g(&_g) {
497        node_num=g->nodes.size();
498        edge_num=g->edges.size();
499      }
500
501      ///Make a snapshot.
502
503      ///Make a snapshot of the graph.
504      ///
505      ///This function can be called more than once. In case of a repeated
506      ///call, the previous snapshot gets lost.
507      ///\param _g The graph we make the snapshot of.
508      void save(SmartUGraph &_g)
509      {
510        g=&_g;
511        node_num=g->nodes.size();
512        edge_num=g->edges.size();
513      }
514
515      ///Undo the changes until a snapshot.
516     
517      ///Undo the changes until a snapshot created by save().
518      ///
519      ///\note After you restored a state, you cannot restore
520      ///a later state, in other word you cannot add again the edges deleted
521      ///by restore().
522      void restore()
523      {
524        g->restoreSnapshot(*this);
525      }
526    };
527  };
528
529
530  class SmartBpUGraphBase {
531  public:
532
533    class NodeSetError : public LogicError {
534    public:
535      virtual const char* what() const throw() {
536        return "lemon::SmartBpUGraph::NodeSetError";
537      }
538    };
539
540  protected:
541
542    struct NodeT {
543      int first;
544      NodeT() {}
545      NodeT(int _first) : first(_first) {}
546    };
547
548    struct UEdgeT {
549      int aNode, next_out;
550      int bNode, next_in;
551    };
552
553    std::vector<NodeT> aNodes;
554    std::vector<NodeT> bNodes;
555
556    std::vector<UEdgeT> edges;
557
558  public:
559 
560    class Node {
561      friend class SmartBpUGraphBase;
562    protected:
563      int id;
564
565      explicit Node(int _id) : id(_id) {}
566    public:
567      Node() {}
568      Node(Invalid) : id(-1) {}
569      bool operator==(const Node i) const {return id==i.id;}
570      bool operator!=(const Node i) const {return id!=i.id;}
571      bool operator<(const Node i) const {return id<i.id;}
572    };
573
574    class UEdge {
575      friend class SmartBpUGraphBase;
576    protected:
577      int id;
578
579      UEdge(int _id) : id(_id) {}
580    public:
581      UEdge() {}
582      UEdge(Invalid) : id(-1) {}
583      bool operator==(const UEdge i) const {return id==i.id;}
584      bool operator!=(const UEdge i) const {return id!=i.id;}
585      bool operator<(const UEdge i) const {return id<i.id;}
586    };
587
588    void firstANode(Node& node) const {
589      node.id = 2 * aNodes.size() - 2;
590      if (node.id < 0) node.id = -1;
591    }
592    void nextANode(Node& node) const {
593      node.id -= 2;
594      if (node.id < 0) node.id = -1;
595    }
596
597    void firstBNode(Node& node) const {
598      node.id = 2 * bNodes.size() - 1;
599    }
600    void nextBNode(Node& node) const {
601      node.id -= 2;
602    }
603
604    void first(Node& node) const {
605      if (aNodes.size() > 0) {
606        node.id = 2 * aNodes.size() - 2;
607      } else {
608        node.id = 2 * bNodes.size() - 1;
609      }
610    }
611    void next(Node& node) const {
612      node.id -= 2;
613      if (node.id == -2) {
614        node.id = 2 * bNodes.size() - 1;
615      }
616    }
617 
618    void first(UEdge& edge) const {
619      edge.id = edges.size() - 1;
620    }
621    void next(UEdge& edge) const {
622      --edge.id;
623    }
624
625    void firstFromANode(UEdge& edge, const Node& node) const {
626      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
627      edge.id = aNodes[node.id >> 1].first;
628    }
629    void nextFromANode(UEdge& edge) const {
630      edge.id = edges[edge.id].next_out;
631    }
632
633    void firstFromBNode(UEdge& edge, const Node& node) const {
634      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
635      edge.id = bNodes[node.id >> 1].first;
636    }
637    void nextFromBNode(UEdge& edge) const {
638      edge.id = edges[edge.id].next_in;
639    }
640
641    static int id(const Node& node) {
642      return node.id;
643    }
644    static Node nodeFromId(int id) {
645      return Node(id);
646    }
647    int maxNodeId() const {
648      return aNodes.size() > bNodes.size() ?
649        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
650    }
651 
652    static int id(const UEdge& edge) {
653      return edge.id;
654    }
655    static UEdge uEdgeFromId(int id) {
656      return UEdge(id);
657    }
658    int maxUEdgeId() const {
659      return edges.size();
660    }
661 
662    static int aNodeId(const Node& node) {
663      return node.id >> 1;
664    }
665    static Node fromANodeId(int id) {
666      return Node(id << 1);
667    }
668    int maxANodeId() const {
669      return aNodes.size();
670    }
671
672    static int bNodeId(const Node& node) {
673      return node.id >> 1;
674    }
675    static Node fromBNodeId(int id) {
676      return Node((id << 1) + 1);
677    }
678    int maxBNodeId() const {
679      return bNodes.size();
680    }
681
682    Node aNode(const UEdge& edge) const {
683      return Node(edges[edge.id].aNode);
684    }
685    Node bNode(const UEdge& edge) const {
686      return Node(edges[edge.id].bNode);
687    }
688
689    static bool aNode(const Node& node) {
690      return (node.id & 1) == 0;
691    }
692
693    static bool bNode(const Node& node) {
694      return (node.id & 1) == 1;
695    }
696
697    Node addANode() {
698      NodeT nodeT;
699      nodeT.first = -1;
700      aNodes.push_back(nodeT);
701      return Node(aNodes.size() * 2 - 2);
702    }
703
704    Node addBNode() {
705      NodeT nodeT;
706      nodeT.first = -1;
707      bNodes.push_back(nodeT);
708      return Node(bNodes.size() * 2 - 1);
709    }
710
711    UEdge addEdge(const Node& source, const Node& target) {
712      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
713      UEdgeT edgeT;
714      if ((source.id & 1) == 0) {
715        edgeT.aNode = source.id;
716        edgeT.bNode = target.id;
717      } else {
718        edgeT.aNode = target.id;
719        edgeT.bNode = source.id;
720      }
721      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
722      aNodes[edgeT.aNode >> 1].first = edges.size();
723      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
724      bNodes[edgeT.bNode >> 1].first = edges.size();
725      edges.push_back(edgeT);
726      return UEdge(edges.size() - 1);
727    }
728
729    void clear() {
730      aNodes.clear();
731      bNodes.clear();
732      edges.clear();
733    }
734
735    typedef True NodeNumTag;
736    int nodeNum() const { return aNodes.size() + bNodes.size(); }
737    int aNodeNum() const { return aNodes.size(); }
738    int bNodeNum() const { return bNodes.size(); }
739
740    typedef True EdgeNumTag;
741    int uEdgeNum() const { return edges.size(); }
742
743  };
744
745
746  typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
747
748  /// \ingroup graphs
749  ///
750  /// \brief A smart bipartite undirected graph class.
751  ///
752  /// This is a simple and fast bipartite undirected graph implementation.
753  /// It is also quite memory efficient, but at the price
754  /// that <b> it does not support node and edge deletions</b>.
755  /// Except from this it conforms to
756  /// the \ref concept::BpUGraph "BpUGraph concept".
757  /// \sa concept::BpUGraph.
758  ///
759  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {
760  private:
761
762    /// \brief SmartBpUGraph is \e not copy constructible.
763    ///
764    ///SmartBpUGraph is \e not copy constructible.
765    SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {};
766
767    /// \brief Assignment of SmartBpUGraph to another one is \e not
768    /// allowed.
769    ///
770    /// Assignment of SmartBpUGraph to another one is \e not allowed.
771    void operator=(const SmartBpUGraph &) {}
772
773  public:
774
775    typedef ExtendedSmartBpUGraphBase Parent;
776
777    ///Constructor
778   
779    ///Constructor.
780    ///
781    SmartBpUGraph() : ExtendedSmartBpUGraphBase() {}
782
783    ///Add a new ANode to the graph.
784   
785    /// \return the new node.
786    ///
787    Node addANode() { return Parent::addANode(); }
788
789    ///Add a new BNode to the graph.
790   
791    /// \return the new node.
792    ///
793    Node addBNode() { return Parent::addBNode(); }
794   
795    ///Add a new undirected edge to the graph.
796   
797    ///Add a new undirected edge to the graph with node \c s
798    ///and \c t.
799    ///\return the new undirected edge.
800    UEdge addEdge(const Node& s, const Node& t) {
801      return Parent::addEdge(s, t);
802    }
803
804    ///Clear the graph.
805   
806    ///Erase all the nodes and edges from the graph.
807    ///
808    void clear() {
809      Parent::clear();
810    }
811   
812  public:
813
814    class Snapshot;
815
816  protected:
817   
818    void restoreSnapshot(const Snapshot &s)
819    {
820      while(s.edge_num<edges.size()) {
821        UEdge edge = uEdgeFromId(edges.size()-1);
822        Parent::getNotifier(UEdge()).erase(edge);
823        std::vector<Edge> dir;
824        dir.push_back(Parent::direct(edge, true));
825        dir.push_back(Parent::direct(edge, false));
826        Parent::getNotifier(Edge()).erase(dir);
827        aNodes[edges.back().aNode >> 1].first=edges.back().next_out;
828        bNodes[edges.back().bNode >> 1].first=edges.back().next_in;
829        edges.pop_back();
830      }
831      while(s.anode_num<aNodes.size()) {
832        Node node = fromANodeId(aNodes.size() - 1);
833        Parent::getNotifier(ANode()).erase(node);
834        Parent::getNotifier(Node()).erase(node);
835        aNodes.pop_back();
836      }
837      while(s.bnode_num<bNodes.size()) {
838        Node node = fromBNodeId(bNodes.size() - 1);
839        Parent::getNotifier(BNode()).erase(node);
840        Parent::getNotifier(Node()).erase(node);
841        bNodes.pop_back();
842      }
843    }   
844
845  public:
846
847    ///Class to make a snapshot of the graph and to restrore to it later.
848
849    ///Class to make a snapshot of the graph and to restrore to it later.
850    ///
851    ///The newly added nodes and edges can be removed using the
852    ///restore() function.
853    ///
854    ///\note After you restore a state, you cannot restore
855    ///a later state, in other word you cannot add again the edges deleted
856    ///by restore() using another one Snapshot instance.
857    ///
858    ///\warning If you do not use correctly the snapshot that can cause
859    ///either broken program, invalid state of the graph, valid but
860    ///not the restored graph or no change. Because the runtime performance
861    ///the validity of the snapshot is not stored.
862    class Snapshot
863    {
864      SmartBpUGraph *g;
865    protected:
866      friend class SmartBpUGraph;
867      unsigned int anode_num;
868      unsigned int bnode_num;
869      unsigned int edge_num;
870    public:
871      ///Default constructor.
872     
873      ///Default constructor.
874      ///To actually make a snapshot you must call save().
875      ///
876      Snapshot() : g(0) {}
877
878      ///Constructor that immediately makes a snapshot
879     
880      ///This constructor immediately makes a snapshot of the graph.
881      ///\param _g The graph we make a snapshot of.
882      Snapshot(SmartBpUGraph &_g) : g(&_g) {
883        anode_num=g->aNodes.size();
884        bnode_num=g->bNodes.size();
885        edge_num=g->edges.size();
886      }
887
888      ///Make a snapshot.
889
890      ///Make a snapshot of the graph.
891      ///
892      ///This function can be called more than once. In case of a repeated
893      ///call, the previous snapshot gets lost.
894      ///\param _g The graph we make the snapshot of.
895      void save(SmartBpUGraph &_g)
896      {
897        g=&_g;
898        anode_num=g->aNodes.size();
899        bnode_num=g->bNodes.size();
900        edge_num=g->edges.size();
901      }
902
903      ///Undo the changes until a snapshot.
904     
905      ///Undo the changes until a snapshot created by save().
906      ///
907      ///\note After you restored a state, you cannot restore
908      ///a later state, in other word you cannot add again the edges deleted
909      ///by restore().
910      void restore()
911      {
912        g->restoreSnapshot(*this);
913      }
914    };
915  };
916
917 
918  /// @} 
919} //namespace lemon
920
921
922#endif //LEMON_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.