COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2528:e6bc5c0032e9

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

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

Redesigned undirected edgesets (like the smart or ugraph)

File size: 29.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_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  ///\brief 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 concepts::Graph "Graph concept" with an
198  ///important extra feature that
199  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
200  ///
201  ///\sa concepts::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    /// \brief Using this it is possible to avoid the superfluous memory
247    /// allocation.
248
249    /// Using this it is possible to avoid the superfluous memory
250    /// allocation: if you know that the graph you want to build will
251    /// be very large (e.g. it will contain millions of nodes and/or edges)
252    /// then it is worth reserving space for this amount before starting
253    /// to build the graph.
254    /// \sa reserveEdge
255    void reserveNode(int n) { nodes.reserve(n); };
256
257    /// \brief Using this it is possible to avoid the superfluous memory
258    /// allocation.
259
260    /// Using this it is possible to avoid the superfluous memory
261    /// allocation: if you know that the graph you want to build will
262    /// be very large (e.g. it will contain millions of nodes and/or edges)
263    /// then it is worth reserving space for this amount before starting
264    /// to build the graph.
265    /// \sa reserveNode
266    void reserveEdge(int m) { edges.reserve(m); };
267
268    ///Clear the graph.
269   
270    ///Erase all the nodes and edges from the graph.
271    ///
272    void clear() {
273      Parent::clear();
274    }
275
276    ///Split a node.
277   
278    ///This function splits a node. First a new node is added to the graph,
279    ///then the source of each outgoing edge of \c n is moved to this new node.
280    ///If \c connect is \c true (this is the default value), then a new edge
281    ///from \c n to the newly created node is also added.
282    ///\return The newly created node.
283    ///
284    ///\note The <tt>Edge</tt>s
285    ///referencing a moved edge remain
286    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
287    ///may be invalidated.
288    ///\warning This functionality cannot be used together with the Snapshot
289    ///feature.
290    ///\todo It could be implemented in a bit faster way.
291    Node split(Node n, bool connect = true)
292    {
293      Node b = addNode();
294      nodes[b.id].first_out=nodes[n.id].first_out;
295      nodes[n.id].first_out=-1;
296      for(int i=nodes[b.id].first_out;i!=-1;i++) edges[i].source=b.id;
297      if(connect) addEdge(n,b);
298      return b;
299    }
300
301  public:
302   
303    class Snapshot;
304
305  protected:
306
307    void restoreSnapshot(const Snapshot &s)
308    {
309      while(s.edge_num<edges.size()) {
310        Edge edge = edgeFromId(edges.size()-1);
311        Parent::notifier(Edge()).erase(edge);
312        nodes[edges.back().source].first_out=edges.back().next_out;
313        nodes[edges.back().target].first_in=edges.back().next_in;
314        edges.pop_back();
315      }
316      while(s.node_num<nodes.size()) {
317        Node node = nodeFromId(nodes.size()-1);
318        Parent::notifier(Node()).erase(node);
319        nodes.pop_back();
320      }
321    }   
322
323  public:
324
325    ///Class to make a snapshot of the graph and to restrore to it later.
326
327    ///Class to make a snapshot of the graph and to restrore to it later.
328    ///
329    ///The newly added nodes and edges can be removed using the
330    ///restore() function.
331    ///\note After you restore a state, you cannot restore
332    ///a later state, in other word you cannot add again the edges deleted
333    ///by restore() using another one Snapshot instance.
334    ///
335    ///\warning If you do not use correctly the snapshot that can cause
336    ///either broken program, invalid state of the graph, valid but
337    ///not the restored graph or no change. Because the runtime performance
338    ///the validity of the snapshot is not stored.
339    class Snapshot
340    {
341      SmartGraph *g;
342    protected:
343      friend class SmartGraph;
344      unsigned int node_num;
345      unsigned int edge_num;
346    public:
347      ///Default constructor.
348     
349      ///Default constructor.
350      ///To actually make a snapshot you must call save().
351      ///
352      Snapshot() : g(0) {}
353      ///Constructor that immediately makes a snapshot
354     
355      ///This constructor immediately makes a snapshot of the graph.
356      ///\param _g The graph we make a snapshot of.
357      Snapshot(SmartGraph &_g) :g(&_g) {
358        node_num=g->nodes.size();
359        edge_num=g->edges.size();
360      }
361
362      ///Make a snapshot.
363
364      ///Make a snapshot of the graph.
365      ///
366      ///This function can be called more than once. In case of a repeated
367      ///call, the previous snapshot gets lost.
368      ///\param _g The graph we make the snapshot of.
369      void save(SmartGraph &_g)
370      {
371        g=&_g;
372        node_num=g->nodes.size();
373        edge_num=g->edges.size();
374      }
375
376      ///Undo the changes until a snapshot.
377     
378      ///Undo the changes until a snapshot created by save().
379      ///
380      ///\note After you restored a state, you cannot restore
381      ///a later state, in other word you cannot add again the edges deleted
382      ///by restore().
383      void restore()
384      {
385        g->restoreSnapshot(*this);
386      }
387    };
388  };
389
390
391  class SmartUGraphBase {
392
393  protected:
394
395    struct NodeT {
396      int first_out;
397    };
398 
399    struct EdgeT {
400      int target;
401      int next_out;
402    };
403
404    std::vector<NodeT> nodes;
405    std::vector<EdgeT> edges;
406
407    int first_free_edge;
408   
409  public:
410   
411    typedef SmartUGraphBase Graph;
412
413    class Node;
414    class Edge;
415    class UEdge;
416   
417    class Node {
418      friend class SmartUGraphBase;
419    protected:
420
421      int id;
422      explicit Node(int pid) { id = pid;}
423
424    public:
425      Node() {}
426      Node (Invalid) { id = -1; }
427      bool operator==(const Node& node) const {return id == node.id;}
428      bool operator!=(const Node& node) const {return id != node.id;}
429      bool operator<(const Node& node) const {return id < node.id;}
430    };
431
432    class UEdge {
433      friend class SmartUGraphBase;
434    protected:
435
436      int id;
437      explicit UEdge(int pid) { id = pid;}
438
439    public:
440      UEdge() {}
441      UEdge (Invalid) { id = -1; }
442      bool operator==(const UEdge& edge) const {return id == edge.id;}
443      bool operator!=(const UEdge& edge) const {return id != edge.id;}
444      bool operator<(const UEdge& edge) const {return id < edge.id;}
445    };
446
447    class Edge {
448      friend class SmartUGraphBase;
449    protected:
450
451      int id;
452      explicit Edge(int pid) { id = pid;}
453
454    public:
455      operator UEdge() const { return uEdgeFromId(id / 2); }
456
457      Edge() {}
458      Edge (Invalid) { id = -1; }
459      bool operator==(const Edge& edge) const {return id == edge.id;}
460      bool operator!=(const Edge& edge) const {return id != edge.id;}
461      bool operator<(const Edge& edge) const {return id < edge.id;}
462    };
463
464
465
466    SmartUGraphBase()
467      : nodes(), edges() {}
468
469   
470    int maxNodeId() const { return nodes.size()-1; }
471    int maxUEdgeId() const { return edges.size() / 2 - 1; }
472    int maxEdgeId() const { return edges.size()-1; }
473
474    Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
475    Node target(Edge e) const { return Node(edges[e.id].target); }
476
477    Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
478    Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
479
480    static bool direction(Edge e) {
481      return (e.id & 1) == 1;
482    }
483
484    static Edge direct(UEdge e, bool d) {
485      return Edge(e.id * 2 + (d ? 1 : 0));
486    }
487
488    void first(Node& node) const {
489      node.id = nodes.size() - 1;
490    }
491
492    void next(Node& node) const {
493      --node.id;
494    }
495
496    void first(Edge& edge) const {
497      edge.id = edges.size() - 1;
498    }
499
500    void next(Edge& edge) const {
501      --edge.id;
502    }
503
504    void first(UEdge& edge) const {
505      edge.id = edges.size() / 2 - 1;
506    }
507
508    void next(UEdge& edge) const {
509      --edge.id;
510    }
511
512    void firstOut(Edge &edge, const Node& v) const {
513      edge.id = nodes[v.id].first_out;
514    }
515    void nextOut(Edge &edge) const {
516      edge.id = edges[edge.id].next_out;
517    }
518
519    void firstIn(Edge &edge, const Node& v) const {
520      edge.id = ((nodes[v.id].first_out) ^ 1);
521      if (edge.id == -2) edge.id = -1;
522    }
523    void nextIn(Edge &edge) const {
524      edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
525      if (edge.id == -2) edge.id = -1;
526    }
527
528    void firstInc(UEdge &edge, bool& d, const Node& v) const {
529      int de = nodes[v.id].first_out;
530      if (de != -1) {
531        edge.id = de / 2;
532        d = ((de & 1) == 1);
533      } else {
534        edge.id = -1;
535        d = true;
536      }
537    }
538    void nextInc(UEdge &edge, bool& d) const {
539      int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out);
540      if (de != -1) {
541        edge.id = de / 2;
542        d = ((de & 1) == 1);
543      } else {
544        edge.id = -1;
545        d = true;     
546      }
547    }
548   
549    static int id(Node v) { return v.id; }
550    static int id(Edge e) { return e.id; }
551    static int id(UEdge e) { return e.id; }
552
553    static Node nodeFromId(int id) { return Node(id);}
554    static Edge edgeFromId(int id) { return Edge(id);}
555    static UEdge uEdgeFromId(int id) { return UEdge(id);}
556
557    Node addNode() {     
558      int n = nodes.size();
559      nodes.push_back(NodeT());
560      nodes[n].first_out = -1;
561     
562      return Node(n);
563    }
564   
565    UEdge addEdge(Node u, Node v) {
566      int n = edges.size();
567      edges.push_back(EdgeT());
568      edges.push_back(EdgeT());
569     
570      edges[n].target = u.id;
571      edges[n | 1].target = v.id;
572
573      edges[n].next_out = nodes[v.id].first_out;
574      nodes[v.id].first_out = n;
575
576      edges[n | 1].next_out = nodes[u.id].first_out;   
577      nodes[u.id].first_out = (n | 1);
578
579      return UEdge(n / 2);
580    }
581   
582    void clear() {
583      edges.clear();
584      nodes.clear();
585    }
586
587  };
588
589  typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase;
590
591  /// \ingroup graphs
592  ///
593  /// \brief A smart undirected graph class.
594  ///
595  /// This is a simple and fast undirected graph implementation.
596  /// It is also quite memory efficient, but at the price
597  /// that <b> it does support only limited (only stack-like)
598  /// node and edge deletions</b>.
599  /// Except from this it conforms to
600  /// the \ref concepts::UGraph "UGraph concept".
601  ///
602  ///It also has an
603  ///important extra feature that
604  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
605  ///
606  /// \sa concepts::UGraph.
607  ///
608  class SmartUGraph : public ExtendedSmartUGraphBase {
609  private:
610
611    ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
612
613    ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
614    ///
615    SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {};
616
617    ///\brief Assignment of SmartUGraph to another one is \e not allowed.
618    ///Use UGraphCopy() instead.
619
620    ///Assignment of SmartUGraph to another one is \e not allowed.
621    ///Use UGraphCopy() instead.
622    void operator=(const SmartUGraph &) {}
623
624  public:
625
626    typedef ExtendedSmartUGraphBase Parent;
627    typedef Parent::OutEdgeIt IncEdgeIt;
628
629    /// Constructor
630   
631    /// Constructor.
632    ///
633    SmartUGraph() {}
634
635    ///Add a new node to the graph.
636   
637    /// \return the new node.
638    ///
639    Node addNode() { return Parent::addNode(); }
640   
641    ///Add a new undirected edge to the graph.
642   
643    ///Add a new undirected edge to the graph with node \c s
644    ///and \c t.
645    ///\return the new undirected edge.
646    UEdge addEdge(const Node& s, const Node& t) {
647      return Parent::addEdge(s, t);
648    }
649
650    ///Clear the graph.
651   
652    ///Erase all the nodes and edges from the graph.
653    ///
654    void clear() {
655      Parent::clear();
656    }
657
658  public:
659   
660    class Snapshot;
661
662  protected:
663
664    void saveSnapshot(Snapshot &s)
665    {
666      s.graph = this;
667      s.node_num = nodes.size();
668      s.edge_num = edges.size();
669    }
670
671    void restoreSnapshot(const Snapshot &s)
672    {
673      while(s.edge_num<edges.size()) {
674        int n=edges.size()-1;
675        UEdge edge=uEdgeFromId(n/2);
676        Parent::notifier(UEdge()).erase(edge);
677        std::vector<Edge> dir;
678        dir.push_back(edgeFromId(n));
679        dir.push_back(edgeFromId(n-1));
680        Parent::notifier(Edge()).erase(dir);
681        nodes[edges[n].target].first_out=edges[n].next_out;
682        nodes[edges[n-1].target].first_out=edges[n-1].next_out;
683        edges.pop_back();
684        edges.pop_back();
685      }
686      while(s.node_num<nodes.size()) {
687        int n=nodes.size()-1;
688        Node node = nodeFromId(n);
689        Parent::notifier(Node()).erase(node);
690        nodes.pop_back();
691      }
692    }   
693
694  public:
695
696    ///Class to make a snapshot of the graph and to restrore to it later.
697
698    ///Class to make a snapshot of the graph and to restrore to it later.
699    ///
700    ///The newly added nodes and edges can be removed using the
701    ///restore() function.
702    ///
703    ///\note After you restore a state, you cannot restore
704    ///a later state, in other word you cannot add again the edges deleted
705    ///by restore() using another one Snapshot instance.
706    ///
707    ///\warning If you do not use correctly the snapshot that can cause
708    ///either broken program, invalid state of the graph, valid but
709    ///not the restored graph or no change. Because the runtime performance
710    ///the validity of the snapshot is not stored.
711    class Snapshot
712    {
713      SmartUGraph *graph;
714    protected:
715      friend class SmartUGraph;
716      unsigned int node_num;
717      unsigned int edge_num;
718    public:
719      ///Default constructor.
720     
721      ///Default constructor.
722      ///To actually make a snapshot you must call save().
723      ///
724      Snapshot() : graph(0) {}
725      ///Constructor that immediately makes a snapshot
726     
727      ///This constructor immediately makes a snapshot of the graph.
728      ///\param g The graph we make a snapshot of.
729      Snapshot(SmartUGraph &g) {
730        g.saveSnapshot(*this);
731      }
732
733      ///Make a snapshot.
734
735      ///Make a snapshot of the graph.
736      ///
737      ///This function can be called more than once. In case of a repeated
738      ///call, the previous snapshot gets lost.
739      ///\param g The graph we make the snapshot of.
740      void save(SmartUGraph &g)
741      {
742        g.saveSnapshot(*this);
743      }
744
745      ///Undo the changes until a snapshot.
746     
747      ///Undo the changes until a snapshot created by save().
748      ///
749      ///\note After you restored a state, you cannot restore
750      ///a later state, in other word you cannot add again the edges deleted
751      ///by restore().
752      void restore()
753      {
754        graph->restoreSnapshot(*this);
755      }
756    };
757  };
758
759
760  class SmartBpUGraphBase {
761  public:
762
763    class NodeSetError : public LogicError {
764    public:
765      virtual const char* what() const throw() {
766        return "lemon::SmartBpUGraph::NodeSetError";
767      }
768    };
769
770  protected:
771
772    struct NodeT {
773      int first;
774      NodeT() {}
775      NodeT(int _first) : first(_first) {}
776    };
777
778    struct UEdgeT {
779      int aNode, next_out;
780      int bNode, next_in;
781    };
782
783    std::vector<NodeT> aNodes;
784    std::vector<NodeT> bNodes;
785
786    std::vector<UEdgeT> edges;
787
788  public:
789 
790    class Node {
791      friend class SmartBpUGraphBase;
792    protected:
793      int id;
794
795      explicit Node(int _id) : id(_id) {}
796    public:
797      Node() {}
798      Node(Invalid) : id(-1) {}
799      bool operator==(const Node i) const {return id==i.id;}
800      bool operator!=(const Node i) const {return id!=i.id;}
801      bool operator<(const Node i) const {return id<i.id;}
802    };
803
804    class UEdge {
805      friend class SmartBpUGraphBase;
806    protected:
807      int id;
808
809      UEdge(int _id) : id(_id) {}
810    public:
811      UEdge() {}
812      UEdge(Invalid) : id(-1) {}
813      bool operator==(const UEdge i) const {return id==i.id;}
814      bool operator!=(const UEdge i) const {return id!=i.id;}
815      bool operator<(const UEdge i) const {return id<i.id;}
816    };
817
818    void firstANode(Node& node) const {
819      node.id = 2 * aNodes.size() - 2;
820      if (node.id < 0) node.id = -1;
821    }
822    void nextANode(Node& node) const {
823      node.id -= 2;
824      if (node.id < 0) node.id = -1;
825    }
826
827    void firstBNode(Node& node) const {
828      node.id = 2 * bNodes.size() - 1;
829    }
830    void nextBNode(Node& node) const {
831      node.id -= 2;
832    }
833
834    void first(Node& node) const {
835      if (aNodes.size() > 0) {
836        node.id = 2 * aNodes.size() - 2;
837      } else {
838        node.id = 2 * bNodes.size() - 1;
839      }
840    }
841    void next(Node& node) const {
842      node.id -= 2;
843      if (node.id == -2) {
844        node.id = 2 * bNodes.size() - 1;
845      }
846    }
847 
848    void first(UEdge& edge) const {
849      edge.id = edges.size() - 1;
850    }
851    void next(UEdge& edge) const {
852      --edge.id;
853    }
854
855    void firstFromANode(UEdge& edge, const Node& node) const {
856      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
857      edge.id = aNodes[node.id >> 1].first;
858    }
859    void nextFromANode(UEdge& edge) const {
860      edge.id = edges[edge.id].next_out;
861    }
862
863    void firstFromBNode(UEdge& edge, const Node& node) const {
864      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
865      edge.id = bNodes[node.id >> 1].first;
866    }
867    void nextFromBNode(UEdge& edge) const {
868      edge.id = edges[edge.id].next_in;
869    }
870
871    static int id(const Node& node) {
872      return node.id;
873    }
874    static Node nodeFromId(int id) {
875      return Node(id);
876    }
877    int maxNodeId() const {
878      return aNodes.size() > bNodes.size() ?
879        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
880    }
881 
882    static int id(const UEdge& edge) {
883      return edge.id;
884    }
885    static UEdge uEdgeFromId(int id) {
886      return UEdge(id);
887    }
888    int maxUEdgeId() const {
889      return edges.size();
890    }
891 
892    static int aNodeId(const Node& node) {
893      return node.id >> 1;
894    }
895    static Node nodeFromANodeId(int id) {
896      return Node(id << 1);
897    }
898    int maxANodeId() const {
899      return aNodes.size();
900    }
901
902    static int bNodeId(const Node& node) {
903      return node.id >> 1;
904    }
905    static Node nodeFromBNodeId(int id) {
906      return Node((id << 1) + 1);
907    }
908    int maxBNodeId() const {
909      return bNodes.size();
910    }
911
912    Node aNode(const UEdge& edge) const {
913      return Node(edges[edge.id].aNode);
914    }
915    Node bNode(const UEdge& edge) const {
916      return Node(edges[edge.id].bNode);
917    }
918
919    static bool aNode(const Node& node) {
920      return (node.id & 1) == 0;
921    }
922
923    static bool bNode(const Node& node) {
924      return (node.id & 1) == 1;
925    }
926
927    Node addANode() {
928      NodeT nodeT;
929      nodeT.first = -1;
930      aNodes.push_back(nodeT);
931      return Node(aNodes.size() * 2 - 2);
932    }
933
934    Node addBNode() {
935      NodeT nodeT;
936      nodeT.first = -1;
937      bNodes.push_back(nodeT);
938      return Node(bNodes.size() * 2 - 1);
939    }
940
941    UEdge addEdge(const Node& source, const Node& target) {
942      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
943      UEdgeT edgeT;
944      if ((source.id & 1) == 0) {
945        edgeT.aNode = source.id;
946        edgeT.bNode = target.id;
947      } else {
948        edgeT.aNode = target.id;
949        edgeT.bNode = source.id;
950      }
951      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
952      aNodes[edgeT.aNode >> 1].first = edges.size();
953      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
954      bNodes[edgeT.bNode >> 1].first = edges.size();
955      edges.push_back(edgeT);
956      return UEdge(edges.size() - 1);
957    }
958
959    void clear() {
960      aNodes.clear();
961      bNodes.clear();
962      edges.clear();
963    }
964
965    typedef True NodeNumTag;
966    int nodeNum() const { return aNodes.size() + bNodes.size(); }
967    int aNodeNum() const { return aNodes.size(); }
968    int bNodeNum() const { return bNodes.size(); }
969
970    typedef True EdgeNumTag;
971    int uEdgeNum() const { return edges.size(); }
972
973  };
974
975
976  typedef BpUGraphExtender<BidirBpUGraphExtender<SmartBpUGraphBase> >
977  ExtendedSmartBpUGraphBase;
978
979  /// \ingroup graphs
980  ///
981  /// \brief A smart bipartite undirected graph class.
982  ///
983  /// This is a simple and fast bipartite undirected graph implementation.
984  /// It is also quite memory efficient, but at the price
985  /// that <b> it does not support node and edge deletions</b>.
986  /// Except from this it conforms to
987  /// the \ref concepts::BpUGraph "BpUGraph concept".
988  ///
989  ///It also has an
990  ///important extra feature that
991  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
992  ///
993  /// \sa concepts::BpUGraph.
994  ///
995  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {
996  private:
997
998    /// \brief SmartBpUGraph is \e not copy constructible.
999    ///
1000    ///SmartBpUGraph is \e not copy constructible.
1001    SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {};
1002
1003    /// \brief Assignment of SmartBpUGraph to another one is \e not
1004    /// allowed.
1005    ///
1006    /// Assignment of SmartBpUGraph to another one is \e not allowed.
1007    void operator=(const SmartBpUGraph &) {}
1008
1009  public:
1010
1011    typedef ExtendedSmartBpUGraphBase Parent;
1012
1013    ///Constructor
1014   
1015    ///Constructor.
1016    ///
1017    SmartBpUGraph() : ExtendedSmartBpUGraphBase() {}
1018
1019    ///Add a new ANode to the graph.
1020   
1021    /// \return the new node.
1022    ///
1023    Node addANode() { return Parent::addANode(); }
1024
1025    ///Add a new BNode to the graph.
1026   
1027    /// \return the new node.
1028    ///
1029    Node addBNode() { return Parent::addBNode(); }
1030   
1031    ///Add a new undirected edge to the graph.
1032   
1033    ///Add a new undirected edge to the graph with node \c s
1034    ///and \c t.
1035    ///\return the new undirected edge.
1036    UEdge addEdge(const Node& s, const Node& t) {
1037      return Parent::addEdge(s, t);
1038    }
1039
1040    ///Clear the graph.
1041   
1042    ///Erase all the nodes and edges from the graph.
1043    ///
1044    void clear() {
1045      Parent::clear();
1046    }
1047   
1048  public:
1049
1050    class Snapshot;
1051
1052  protected:
1053   
1054    void restoreSnapshot(const Snapshot &s)
1055    {
1056      while(s.edge_num<edges.size()) {
1057        UEdge edge = uEdgeFromId(edges.size()-1);
1058        Parent::notifier(UEdge()).erase(edge);
1059        std::vector<Edge> dir;
1060        dir.push_back(Parent::direct(edge, true));
1061        dir.push_back(Parent::direct(edge, false));
1062        Parent::notifier(Edge()).erase(dir);
1063        aNodes[edges.back().aNode >> 1].first=edges.back().next_out;
1064        bNodes[edges.back().bNode >> 1].first=edges.back().next_in;
1065        edges.pop_back();
1066      }
1067      while(s.anode_num<aNodes.size()) {
1068        Node node = nodeFromANodeId(aNodes.size() - 1);
1069        Parent::notifier(ANode()).erase(node);
1070        Parent::notifier(Node()).erase(node);
1071        aNodes.pop_back();
1072      }
1073      while(s.bnode_num<bNodes.size()) {
1074        Node node = nodeFromBNodeId(bNodes.size() - 1);
1075        Parent::notifier(BNode()).erase(node);
1076        Parent::notifier(Node()).erase(node);
1077        bNodes.pop_back();
1078      }
1079    }   
1080
1081  public:
1082
1083    ///Class to make a snapshot of the graph and to restrore to it later.
1084
1085    ///Class to make a snapshot of the graph and to restrore to it later.
1086    ///
1087    ///The newly added nodes and edges can be removed using the
1088    ///restore() function.
1089    ///
1090    ///\note After you restore a state, you cannot restore
1091    ///a later state, in other word you cannot add again the edges deleted
1092    ///by restore() using another one Snapshot instance.
1093    ///
1094    ///\warning If you do not use correctly the snapshot that can cause
1095    ///either broken program, invalid state of the graph, valid but
1096    ///not the restored graph or no change. Because the runtime performance
1097    ///the validity of the snapshot is not stored.
1098    class Snapshot
1099    {
1100      SmartBpUGraph *g;
1101    protected:
1102      friend class SmartBpUGraph;
1103      unsigned int anode_num;
1104      unsigned int bnode_num;
1105      unsigned int edge_num;
1106    public:
1107      ///Default constructor.
1108     
1109      ///Default constructor.
1110      ///To actually make a snapshot you must call save().
1111      ///
1112      Snapshot() : g(0) {}
1113
1114      ///Constructor that immediately makes a snapshot
1115     
1116      ///This constructor immediately makes a snapshot of the graph.
1117      ///\param _g The graph we make a snapshot of.
1118      Snapshot(SmartBpUGraph &_g) : g(&_g) {
1119        anode_num=g->aNodes.size();
1120        bnode_num=g->bNodes.size();
1121        edge_num=g->edges.size();
1122      }
1123
1124      ///Make a snapshot.
1125
1126      ///Make a snapshot of the graph.
1127      ///
1128      ///This function can be called more than once. In case of a repeated
1129      ///call, the previous snapshot gets lost.
1130      ///\param _g The graph we make the snapshot of.
1131      void save(SmartBpUGraph &_g)
1132      {
1133        g=&_g;
1134        anode_num=g->aNodes.size();
1135        bnode_num=g->bNodes.size();
1136        edge_num=g->edges.size();
1137      }
1138
1139      ///Undo the changes until a snapshot.
1140     
1141      ///Undo the changes until a snapshot created by save().
1142      ///
1143      ///\note After you restored a state, you cannot restore
1144      ///a later state, in other word you cannot add again the edges deleted
1145      ///by restore().
1146      void restore()
1147      {
1148        g->restoreSnapshot(*this);
1149      }
1150    };
1151  };
1152
1153 
1154  /// @} 
1155} //namespace lemon
1156
1157
1158#endif //LEMON_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.