COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2343:21587bc5922b

Last change on this file since 2343:21587bc5922b was 2343:21587bc5922b, checked in by Balazs Dezso, 13 years ago

G++-3.3 conform solution

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    class Edge;
393    class UEdge;
394   
395    class Node {
396      friend class SmartUGraphBase;
397    protected:
398
399      int id;
400      explicit Node(int pid) { id = pid;}
401
402    public:
403      Node() {}
404      Node (Invalid) { id = -1; }
405      bool operator==(const Node& node) const {return id == node.id;}
406      bool operator!=(const Node& node) const {return id != node.id;}
407      bool operator<(const Node& node) const {return id < node.id;}
408    };
409
410    class UEdge {
411      friend class SmartUGraphBase;
412    protected:
413
414      int id;
415      explicit UEdge(int pid) { id = pid;}
416
417    public:
418      UEdge() {}
419      UEdge (Invalid) { id = -1; }
420      bool operator==(const UEdge& edge) const {return id == edge.id;}
421      bool operator!=(const UEdge& edge) const {return id != edge.id;}
422      bool operator<(const UEdge& edge) const {return id < edge.id;}
423    };
424
425    class Edge {
426      friend class SmartUGraphBase;
427    protected:
428
429      int id;
430      explicit Edge(int pid) { id = pid;}
431
432    public:
433      operator UEdge() const { return uEdgeFromId(id / 2); }
434
435      Edge() {}
436      Edge (Invalid) { id = -1; }
437      bool operator==(const Edge& edge) const {return id == edge.id;}
438      bool operator!=(const Edge& edge) const {return id != edge.id;}
439      bool operator<(const Edge& edge) const {return id < edge.id;}
440    };
441
442
443
444    SmartUGraphBase()
445      : nodes(), edges() {}
446
447   
448    int maxNodeId() const { return nodes.size()-1; }
449    int maxUEdgeId() const { return edges.size() / 2 - 1; }
450    int maxEdgeId() const { return edges.size()-1; }
451
452    Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
453    Node target(Edge e) const { return Node(edges[e.id].target); }
454
455    Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
456    Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
457
458    static bool direction(Edge e) {
459      return (e.id & 1) == 1;
460    }
461
462    static Edge direct(UEdge e, bool d) {
463      return Edge(e.id * 2 + (d ? 1 : 0));
464    }
465
466    void first(Node& node) const {
467      node.id = nodes.size() - 1;
468    }
469
470    void next(Node& node) const {
471      --node.id;
472    }
473
474    void first(Edge& edge) const {
475      edge.id = edges.size() - 1;
476    }
477
478    void next(Edge& edge) const {
479      --edge.id;
480    }
481
482    void first(UEdge& edge) const {
483      edge.id = edges.size() / 2 - 1;
484    }
485
486    void next(UEdge& edge) const {
487      --edge.id;
488    }
489
490    void firstOut(Edge &edge, const Node& v) const {
491      edge.id = nodes[v.id].first_out;
492    }
493    void nextOut(Edge &edge) const {
494      edge.id = edges[edge.id].next_out;
495    }
496
497    void firstIn(Edge &edge, const Node& v) const {
498      edge.id = ((nodes[v.id].first_out) ^ 1);
499      if (edge.id == -2) edge.id = -1;
500    }
501    void nextIn(Edge &edge) const {
502      edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
503      if (edge.id == -2) edge.id = -1;
504    }
505
506    void firstInc(UEdge &edge, bool& d, const Node& v) const {
507      int de = nodes[v.id].first_out;
508      edge.id = de / 2;
509      d = ((de & 1) == 1);
510    }
511    void nextInc(UEdge &edge, bool& d) const {
512      int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out);
513      edge.id = de / 2;
514      d = ((de & 1) == 1);
515    }
516   
517    static int id(Node v) { return v.id; }
518    static int id(Edge e) { return e.id; }
519    static int id(UEdge e) { return e.id; }
520
521    static Node nodeFromId(int id) { return Node(id);}
522    static Edge edgeFromId(int id) { return Edge(id);}
523    static UEdge uEdgeFromId(int id) { return UEdge(id);}
524
525    Node addNode() {     
526      int n = nodes.size();
527      nodes.push_back(NodeT());
528      nodes[n].first_out = -1;
529     
530      return Node(n);
531    }
532   
533    UEdge addEdge(Node u, Node v) {
534      int n = edges.size();
535      edges.push_back(EdgeT());
536      edges.push_back(EdgeT());
537     
538      edges[n].target = u.id;
539      edges[n | 1].target = v.id;
540
541      edges[n].next_out = nodes[v.id].first_out;
542      edges[n | 1].next_out = nodes[u.id].first_out;
543       
544      nodes[v.id].first_out = n;
545      nodes[u.id].first_out = (n | 1);
546
547      return UEdge(n / 2);
548    }
549   
550    void clear() {
551      edges.clear();
552      nodes.clear();
553    }
554
555  };
556
557  typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase;
558
559  /// \ingroup graphs
560  ///
561  /// \brief A smart undirected graph class.
562  ///
563  /// This is a simple and fast undirected graph implementation.
564  /// It is also quite memory efficient, but at the price
565  /// that <b> it does support only limited (only stack-like)
566  /// node and edge deletions</b>.
567  /// Except from this it conforms to
568  /// the \ref concepts::UGraph "UGraph concept".
569  ///
570  ///It also has an
571  ///important extra feature that
572  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
573  ///
574  /// \sa concepts::UGraph.
575  ///
576  class SmartUGraph : public ExtendedSmartUGraphBase {
577  private:
578
579    ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
580
581    ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
582    ///
583    SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {};
584
585    ///\brief Assignment of SmartUGraph to another one is \e not allowed.
586    ///Use UGraphCopy() instead.
587
588    ///Assignment of SmartUGraph to another one is \e not allowed.
589    ///Use UGraphCopy() instead.
590    void operator=(const SmartUGraph &) {}
591
592  public:
593
594    typedef ExtendedSmartUGraphBase Parent;
595    typedef Parent::OutEdgeIt IncEdgeIt;
596
597    /// Constructor
598   
599    /// Constructor.
600    ///
601    SmartUGraph() {}
602
603    ///Add a new node to the graph.
604   
605    /// \return the new node.
606    ///
607    Node addNode() { return Parent::addNode(); }
608   
609    ///Add a new undirected edge to the graph.
610   
611    ///Add a new undirected edge to the graph with node \c s
612    ///and \c t.
613    ///\return the new undirected edge.
614    UEdge addEdge(const Node& s, const Node& t) {
615      return Parent::addEdge(s, t);
616    }
617
618    ///Clear the graph.
619   
620    ///Erase all the nodes and edges from the graph.
621    ///
622    void clear() {
623      Parent::clear();
624    }
625
626  public:
627   
628    class Snapshot;
629
630  protected:
631
632    void saveSnapshot(Snapshot &s)
633    {
634      s.g = this;
635      s.node_num = nodes.size();
636      s.edge_num = edges.size();
637    }
638
639    void restoreSnapshot(const Snapshot &s)
640    {
641      while(s.edge_num<edges.size()) {
642        int n=edges.size()-1;
643        UEdge edge=uEdgeFromId(n/2);
644        Parent::getNotifier(UEdge()).erase(edge);
645        std::vector<Edge> dir;
646        dir.push_back(edgeFromId(n));
647        dir.push_back(edgeFromId(n-1));
648        Parent::getNotifier(Edge()).erase(dir);
649        nodes[edges[n].target].first_out=edges[n].next_out;
650        nodes[edges[n-1].target].first_out=edges[n-1].next_out;
651        edges.pop_back();
652        edges.pop_back();
653      }
654      while(s.node_num<nodes.size()) {
655        int n=nodes.size()-1;
656        Node node = nodeFromId(n);
657        Parent::getNotifier(Node()).erase(node);
658        nodes.pop_back();
659      }
660    }   
661
662  public:
663
664    ///Class to make a snapshot of the graph and to restrore to it later.
665
666    ///Class to make a snapshot of the graph and to restrore to it later.
667    ///
668    ///The newly added nodes and edges can be removed using the
669    ///restore() function.
670    ///
671    ///\note After you restore a state, you cannot restore
672    ///a later state, in other word you cannot add again the edges deleted
673    ///by restore() using another one Snapshot instance.
674    ///
675    ///\warning If you do not use correctly the snapshot that can cause
676    ///either broken program, invalid state of the graph, valid but
677    ///not the restored graph or no change. Because the runtime performance
678    ///the validity of the snapshot is not stored.
679    class Snapshot
680    {
681      SmartUGraph *g;
682    protected:
683      friend class SmartUGraph;
684      unsigned int node_num;
685      unsigned int edge_num;
686    public:
687      ///Default constructor.
688     
689      ///Default constructor.
690      ///To actually make a snapshot you must call save().
691      ///
692      Snapshot() : g(0) {}
693      ///Constructor that immediately makes a snapshot
694     
695      ///This constructor immediately makes a snapshot of the graph.
696      ///\param _g The graph we make a snapshot of.
697      Snapshot(SmartUGraph &g) {
698        g.saveSnapshot(*this);
699      }
700
701      ///Make a snapshot.
702
703      ///Make a snapshot of the graph.
704      ///
705      ///This function can be called more than once. In case of a repeated
706      ///call, the previous snapshot gets lost.
707      ///\param _g The graph we make the snapshot of.
708      void save(SmartUGraph &g)
709      {
710        g.saveSnapshot(*this);
711      }
712
713      ///Undo the changes until a snapshot.
714     
715      ///Undo the changes until a snapshot created by save().
716      ///
717      ///\note After you restored a state, you cannot restore
718      ///a later state, in other word you cannot add again the edges deleted
719      ///by restore().
720      void restore()
721      {
722        g->restoreSnapshot(*this);
723      }
724    };
725  };
726
727
728  class SmartBpUGraphBase {
729  public:
730
731    class NodeSetError : public LogicError {
732    public:
733      virtual const char* what() const throw() {
734        return "lemon::SmartBpUGraph::NodeSetError";
735      }
736    };
737
738  protected:
739
740    struct NodeT {
741      int first;
742      NodeT() {}
743      NodeT(int _first) : first(_first) {}
744    };
745
746    struct UEdgeT {
747      int aNode, next_out;
748      int bNode, next_in;
749    };
750
751    std::vector<NodeT> aNodes;
752    std::vector<NodeT> bNodes;
753
754    std::vector<UEdgeT> edges;
755
756  public:
757 
758    class Node {
759      friend class SmartBpUGraphBase;
760    protected:
761      int id;
762
763      explicit Node(int _id) : id(_id) {}
764    public:
765      Node() {}
766      Node(Invalid) : id(-1) {}
767      bool operator==(const Node i) const {return id==i.id;}
768      bool operator!=(const Node i) const {return id!=i.id;}
769      bool operator<(const Node i) const {return id<i.id;}
770    };
771
772    class UEdge {
773      friend class SmartBpUGraphBase;
774    protected:
775      int id;
776
777      UEdge(int _id) : id(_id) {}
778    public:
779      UEdge() {}
780      UEdge(Invalid) : id(-1) {}
781      bool operator==(const UEdge i) const {return id==i.id;}
782      bool operator!=(const UEdge i) const {return id!=i.id;}
783      bool operator<(const UEdge i) const {return id<i.id;}
784    };
785
786    void firstANode(Node& node) const {
787      node.id = 2 * aNodes.size() - 2;
788      if (node.id < 0) node.id = -1;
789    }
790    void nextANode(Node& node) const {
791      node.id -= 2;
792      if (node.id < 0) node.id = -1;
793    }
794
795    void firstBNode(Node& node) const {
796      node.id = 2 * bNodes.size() - 1;
797    }
798    void nextBNode(Node& node) const {
799      node.id -= 2;
800    }
801
802    void first(Node& node) const {
803      if (aNodes.size() > 0) {
804        node.id = 2 * aNodes.size() - 2;
805      } else {
806        node.id = 2 * bNodes.size() - 1;
807      }
808    }
809    void next(Node& node) const {
810      node.id -= 2;
811      if (node.id == -2) {
812        node.id = 2 * bNodes.size() - 1;
813      }
814    }
815 
816    void first(UEdge& edge) const {
817      edge.id = edges.size() - 1;
818    }
819    void next(UEdge& edge) const {
820      --edge.id;
821    }
822
823    void firstFromANode(UEdge& edge, const Node& node) const {
824      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
825      edge.id = aNodes[node.id >> 1].first;
826    }
827    void nextFromANode(UEdge& edge) const {
828      edge.id = edges[edge.id].next_out;
829    }
830
831    void firstFromBNode(UEdge& edge, const Node& node) const {
832      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
833      edge.id = bNodes[node.id >> 1].first;
834    }
835    void nextFromBNode(UEdge& edge) const {
836      edge.id = edges[edge.id].next_in;
837    }
838
839    static int id(const Node& node) {
840      return node.id;
841    }
842    static Node nodeFromId(int id) {
843      return Node(id);
844    }
845    int maxNodeId() const {
846      return aNodes.size() > bNodes.size() ?
847        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
848    }
849 
850    static int id(const UEdge& edge) {
851      return edge.id;
852    }
853    static UEdge uEdgeFromId(int id) {
854      return UEdge(id);
855    }
856    int maxUEdgeId() const {
857      return edges.size();
858    }
859 
860    static int aNodeId(const Node& node) {
861      return node.id >> 1;
862    }
863    static Node nodeFromANodeId(int id) {
864      return Node(id << 1);
865    }
866    int maxANodeId() const {
867      return aNodes.size();
868    }
869
870    static int bNodeId(const Node& node) {
871      return node.id >> 1;
872    }
873    static Node nodeFromBNodeId(int id) {
874      return Node((id << 1) + 1);
875    }
876    int maxBNodeId() const {
877      return bNodes.size();
878    }
879
880    Node aNode(const UEdge& edge) const {
881      return Node(edges[edge.id].aNode);
882    }
883    Node bNode(const UEdge& edge) const {
884      return Node(edges[edge.id].bNode);
885    }
886
887    static bool aNode(const Node& node) {
888      return (node.id & 1) == 0;
889    }
890
891    static bool bNode(const Node& node) {
892      return (node.id & 1) == 1;
893    }
894
895    Node addANode() {
896      NodeT nodeT;
897      nodeT.first = -1;
898      aNodes.push_back(nodeT);
899      return Node(aNodes.size() * 2 - 2);
900    }
901
902    Node addBNode() {
903      NodeT nodeT;
904      nodeT.first = -1;
905      bNodes.push_back(nodeT);
906      return Node(bNodes.size() * 2 - 1);
907    }
908
909    UEdge addEdge(const Node& source, const Node& target) {
910      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
911      UEdgeT edgeT;
912      if ((source.id & 1) == 0) {
913        edgeT.aNode = source.id;
914        edgeT.bNode = target.id;
915      } else {
916        edgeT.aNode = target.id;
917        edgeT.bNode = source.id;
918      }
919      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
920      aNodes[edgeT.aNode >> 1].first = edges.size();
921      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
922      bNodes[edgeT.bNode >> 1].first = edges.size();
923      edges.push_back(edgeT);
924      return UEdge(edges.size() - 1);
925    }
926
927    void clear() {
928      aNodes.clear();
929      bNodes.clear();
930      edges.clear();
931    }
932
933    typedef True NodeNumTag;
934    int nodeNum() const { return aNodes.size() + bNodes.size(); }
935    int aNodeNum() const { return aNodes.size(); }
936    int bNodeNum() const { return bNodes.size(); }
937
938    typedef True EdgeNumTag;
939    int uEdgeNum() const { return edges.size(); }
940
941  };
942
943
944  typedef BpUGraphExtender<BidirBpUGraphExtender<SmartBpUGraphBase> >
945  ExtendedSmartBpUGraphBase;
946
947  /// \ingroup graphs
948  ///
949  /// \brief A smart bipartite undirected graph class.
950  ///
951  /// This is a simple and fast bipartite undirected graph implementation.
952  /// It is also quite memory efficient, but at the price
953  /// that <b> it does not support node and edge deletions</b>.
954  /// Except from this it conforms to
955  /// the \ref concepts::BpUGraph "BpUGraph concept".
956  ///
957  ///It also has an
958  ///important extra feature that
959  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
960  ///
961  /// \sa concepts::BpUGraph.
962  ///
963  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {
964  private:
965
966    /// \brief SmartBpUGraph is \e not copy constructible.
967    ///
968    ///SmartBpUGraph is \e not copy constructible.
969    SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {};
970
971    /// \brief Assignment of SmartBpUGraph to another one is \e not
972    /// allowed.
973    ///
974    /// Assignment of SmartBpUGraph to another one is \e not allowed.
975    void operator=(const SmartBpUGraph &) {}
976
977  public:
978
979    typedef ExtendedSmartBpUGraphBase Parent;
980
981    ///Constructor
982   
983    ///Constructor.
984    ///
985    SmartBpUGraph() : ExtendedSmartBpUGraphBase() {}
986
987    ///Add a new ANode to the graph.
988   
989    /// \return the new node.
990    ///
991    Node addANode() { return Parent::addANode(); }
992
993    ///Add a new BNode to the graph.
994   
995    /// \return the new node.
996    ///
997    Node addBNode() { return Parent::addBNode(); }
998   
999    ///Add a new undirected edge to the graph.
1000   
1001    ///Add a new undirected edge to the graph with node \c s
1002    ///and \c t.
1003    ///\return the new undirected edge.
1004    UEdge addEdge(const Node& s, const Node& t) {
1005      return Parent::addEdge(s, t);
1006    }
1007
1008    ///Clear the graph.
1009   
1010    ///Erase all the nodes and edges from the graph.
1011    ///
1012    void clear() {
1013      Parent::clear();
1014    }
1015   
1016  public:
1017
1018    class Snapshot;
1019
1020  protected:
1021   
1022    void restoreSnapshot(const Snapshot &s)
1023    {
1024      while(s.edge_num<edges.size()) {
1025        UEdge edge = uEdgeFromId(edges.size()-1);
1026        Parent::getNotifier(UEdge()).erase(edge);
1027        std::vector<Edge> dir;
1028        dir.push_back(Parent::direct(edge, true));
1029        dir.push_back(Parent::direct(edge, false));
1030        Parent::getNotifier(Edge()).erase(dir);
1031        aNodes[edges.back().aNode >> 1].first=edges.back().next_out;
1032        bNodes[edges.back().bNode >> 1].first=edges.back().next_in;
1033        edges.pop_back();
1034      }
1035      while(s.anode_num<aNodes.size()) {
1036        Node node = nodeFromANodeId(aNodes.size() - 1);
1037        Parent::getNotifier(ANode()).erase(node);
1038        Parent::getNotifier(Node()).erase(node);
1039        aNodes.pop_back();
1040      }
1041      while(s.bnode_num<bNodes.size()) {
1042        Node node = nodeFromBNodeId(bNodes.size() - 1);
1043        Parent::getNotifier(BNode()).erase(node);
1044        Parent::getNotifier(Node()).erase(node);
1045        bNodes.pop_back();
1046      }
1047    }   
1048
1049  public:
1050
1051    ///Class to make a snapshot of the graph and to restrore to it later.
1052
1053    ///Class to make a snapshot of the graph and to restrore to it later.
1054    ///
1055    ///The newly added nodes and edges can be removed using the
1056    ///restore() function.
1057    ///
1058    ///\note After you restore a state, you cannot restore
1059    ///a later state, in other word you cannot add again the edges deleted
1060    ///by restore() using another one Snapshot instance.
1061    ///
1062    ///\warning If you do not use correctly the snapshot that can cause
1063    ///either broken program, invalid state of the graph, valid but
1064    ///not the restored graph or no change. Because the runtime performance
1065    ///the validity of the snapshot is not stored.
1066    class Snapshot
1067    {
1068      SmartBpUGraph *g;
1069    protected:
1070      friend class SmartBpUGraph;
1071      unsigned int anode_num;
1072      unsigned int bnode_num;
1073      unsigned int edge_num;
1074    public:
1075      ///Default constructor.
1076     
1077      ///Default constructor.
1078      ///To actually make a snapshot you must call save().
1079      ///
1080      Snapshot() : g(0) {}
1081
1082      ///Constructor that immediately makes a snapshot
1083     
1084      ///This constructor immediately makes a snapshot of the graph.
1085      ///\param _g The graph we make a snapshot of.
1086      Snapshot(SmartBpUGraph &_g) : g(&_g) {
1087        anode_num=g->aNodes.size();
1088        bnode_num=g->bNodes.size();
1089        edge_num=g->edges.size();
1090      }
1091
1092      ///Make a snapshot.
1093
1094      ///Make a snapshot of the graph.
1095      ///
1096      ///This function can be called more than once. In case of a repeated
1097      ///call, the previous snapshot gets lost.
1098      ///\param _g The graph we make the snapshot of.
1099      void save(SmartBpUGraph &_g)
1100      {
1101        g=&_g;
1102        anode_num=g->aNodes.size();
1103        bnode_num=g->bNodes.size();
1104        edge_num=g->edges.size();
1105      }
1106
1107      ///Undo the changes until a snapshot.
1108     
1109      ///Undo the changes until a snapshot created by save().
1110      ///
1111      ///\note After you restored a state, you cannot restore
1112      ///a later state, in other word you cannot add again the edges deleted
1113      ///by restore().
1114      void restore()
1115      {
1116        g->restoreSnapshot(*this);
1117      }
1118    };
1119  };
1120
1121 
1122  /// @} 
1123} //namespace lemon
1124
1125
1126#endif //LEMON_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.