lemon/smart_graph.h
author deba
Fri, 16 Feb 2007 19:11:31 +0000
changeset 2366 bfbdded3763a
parent 2343 21587bc5922b
child 2381 0248790c66ea
permissions -rw-r--r--
Using const in lp interface
colByName functionality
     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 
    38 namespace 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