COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

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-2008
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.