COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.h @ 2390:8450951a8e2d

Last change on this file since 2390:8450951a8e2d was 2386:81b47fc5c444, checked in by Balazs Dezso, 13 years ago

Hard Warning checking

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