COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2256:b22dfb6c5ff3

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

Graph imlementations actually provide ReferenceMaps?.

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