COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2338:359f0b71919b

Last change on this file since 2338:359f0b71919b was 2338:359f0b71919b, checked in by Balazs Dezso, 13 years ago

Changing implementation of undirected graphs
slightly faster, 10% speed-up

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