COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2282:9d7b12f83daa

Last change on this file since 2282:9d7b12f83daa was 2261:c52b572c294f, checked in by Alpar Juttner, 17 years ago

Doc update

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