COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2342:4dd3eb348641

Last change on this file since 2342:4dd3eb348641 was 2342:4dd3eb348641, checked in by Balazs Dezso, 13 years ago

Bug fix

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