lemon/smart_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 18 Mar 2013 17:41:19 +0100
changeset 1053 1c978b5bcc65
parent 1023 939ee6d1e525
child 1092 dceba191c00d
permissions -rw-r--r--
Use doxygen's own bibtex support (#456)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     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 SmartDigraph and SmartGraph classes.
    25 
    26 #include <vector>
    27 
    28 #include <lemon/core.h>
    29 #include <lemon/error.h>
    30 #include <lemon/bits/graph_extender.h>
    31 
    32 namespace lemon {
    33 
    34   class SmartDigraph;
    35 
    36   class SmartDigraphBase {
    37   protected:
    38 
    39     struct NodeT
    40     {
    41       int first_in, first_out;
    42       NodeT() {}
    43     };
    44     struct ArcT
    45     {
    46       int target, source, next_in, next_out;
    47       ArcT() {}
    48     };
    49 
    50     std::vector<NodeT> nodes;
    51     std::vector<ArcT> arcs;
    52 
    53   public:
    54 
    55     typedef SmartDigraphBase Digraph;
    56 
    57     class Node;
    58     class Arc;
    59 
    60   public:
    61 
    62     SmartDigraphBase() : nodes(), arcs() { }
    63     SmartDigraphBase(const SmartDigraphBase &_g)
    64       : nodes(_g.nodes), arcs(_g.arcs) { }
    65 
    66     typedef True NodeNumTag;
    67     typedef True ArcNumTag;
    68 
    69     int nodeNum() const { return nodes.size(); }
    70     int arcNum() const { return arcs.size(); }
    71 
    72     int maxNodeId() const { return nodes.size()-1; }
    73     int maxArcId() const { return arcs.size()-1; }
    74 
    75     Node addNode() {
    76       int n = nodes.size();
    77       nodes.push_back(NodeT());
    78       nodes[n].first_in = -1;
    79       nodes[n].first_out = -1;
    80       return Node(n);
    81     }
    82 
    83     Arc addArc(Node u, Node v) {
    84       int n = arcs.size();
    85       arcs.push_back(ArcT());
    86       arcs[n].source = u._id;
    87       arcs[n].target = v._id;
    88       arcs[n].next_out = nodes[u._id].first_out;
    89       arcs[n].next_in = nodes[v._id].first_in;
    90       nodes[u._id].first_out = nodes[v._id].first_in = n;
    91 
    92       return Arc(n);
    93     }
    94 
    95     void clear() {
    96       arcs.clear();
    97       nodes.clear();
    98     }
    99 
   100     Node source(Arc a) const { return Node(arcs[a._id].source); }
   101     Node target(Arc a) const { return Node(arcs[a._id].target); }
   102 
   103     static int id(Node v) { return v._id; }
   104     static int id(Arc a) { return a._id; }
   105 
   106     static Node nodeFromId(int id) { return Node(id);}
   107     static Arc arcFromId(int id) { return Arc(id);}
   108 
   109     bool valid(Node n) const {
   110       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
   111     }
   112     bool valid(Arc a) const {
   113       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
   114     }
   115 
   116     class Node {
   117       friend class SmartDigraphBase;
   118       friend class SmartDigraph;
   119 
   120     protected:
   121       int _id;
   122       explicit Node(int id) : _id(id) {}
   123     public:
   124       Node() {}
   125       Node (Invalid) : _id(-1) {}
   126       bool operator==(const Node i) const {return _id == i._id;}
   127       bool operator!=(const Node i) const {return _id != i._id;}
   128       bool operator<(const Node i) const {return _id < i._id;}
   129     };
   130 
   131 
   132     class Arc {
   133       friend class SmartDigraphBase;
   134       friend class SmartDigraph;
   135 
   136     protected:
   137       int _id;
   138       explicit Arc(int id) : _id(id) {}
   139     public:
   140       Arc() { }
   141       Arc (Invalid) : _id(-1) {}
   142       bool operator==(const Arc i) const {return _id == i._id;}
   143       bool operator!=(const Arc i) const {return _id != i._id;}
   144       bool operator<(const Arc i) const {return _id < i._id;}
   145     };
   146 
   147     void first(Node& node) const {
   148       node._id = nodes.size() - 1;
   149     }
   150 
   151     static void next(Node& node) {
   152       --node._id;
   153     }
   154 
   155     void first(Arc& arc) const {
   156       arc._id = arcs.size() - 1;
   157     }
   158 
   159     static void next(Arc& arc) {
   160       --arc._id;
   161     }
   162 
   163     void firstOut(Arc& arc, const Node& node) const {
   164       arc._id = nodes[node._id].first_out;
   165     }
   166 
   167     void nextOut(Arc& arc) const {
   168       arc._id = arcs[arc._id].next_out;
   169     }
   170 
   171     void firstIn(Arc& arc, const Node& node) const {
   172       arc._id = nodes[node._id].first_in;
   173     }
   174 
   175     void nextIn(Arc& arc) const {
   176       arc._id = arcs[arc._id].next_in;
   177     }
   178 
   179   };
   180 
   181   typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
   182 
   183   ///\ingroup graphs
   184   ///
   185   ///\brief A smart directed graph class.
   186   ///
   187   ///\ref SmartDigraph is a simple and fast digraph implementation.
   188   ///It is also quite memory efficient but at the price
   189   ///that it does not support node and arc deletion
   190   ///(except for the Snapshot feature).
   191   ///
   192   ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
   193   ///and it also provides some additional functionalities.
   194   ///Most of its member functions and nested classes are documented
   195   ///only in the concept class.
   196   ///
   197   ///This class provides constant time counting for nodes and arcs.
   198   ///
   199   ///\sa concepts::Digraph
   200   ///\sa SmartGraph
   201   class SmartDigraph : public ExtendedSmartDigraphBase {
   202     typedef ExtendedSmartDigraphBase Parent;
   203 
   204   private:
   205     /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
   206     SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
   207     /// \brief Assignment of a digraph to another one is \e not allowed.
   208     /// Use DigraphCopy instead.
   209     void operator=(const SmartDigraph &) {}
   210 
   211   public:
   212 
   213     /// Constructor
   214 
   215     /// Constructor.
   216     ///
   217     SmartDigraph() {};
   218 
   219     ///Add a new node to the digraph.
   220 
   221     ///This function adds a new node to the digraph.
   222     ///\return The new node.
   223     Node addNode() { return Parent::addNode(); }
   224 
   225     ///Add a new arc to the digraph.
   226 
   227     ///This function adds a new arc to the digraph with source node \c s
   228     ///and target node \c t.
   229     ///\return The new arc.
   230     Arc addArc(Node s, Node t) {
   231       return Parent::addArc(s, t);
   232     }
   233 
   234     /// \brief Node validity check
   235     ///
   236     /// This function gives back \c true if the given node is valid,
   237     /// i.e. it is a real node of the digraph.
   238     ///
   239     /// \warning A removed node (using Snapshot) could become valid again
   240     /// if new nodes are added to the digraph.
   241     bool valid(Node n) const { return Parent::valid(n); }
   242 
   243     /// \brief Arc validity check
   244     ///
   245     /// This function gives back \c true if the given arc is valid,
   246     /// i.e. it is a real arc of the digraph.
   247     ///
   248     /// \warning A removed arc (using Snapshot) could become valid again
   249     /// if new arcs are added to the graph.
   250     bool valid(Arc a) const { return Parent::valid(a); }
   251 
   252     ///Split a node.
   253 
   254     ///This function splits the given node. First, a new node is added
   255     ///to the digraph, then the source of each outgoing arc of node \c n
   256     ///is moved to this new node.
   257     ///If the second parameter \c connect is \c true (this is the default
   258     ///value), then a new arc from node \c n to the newly created node
   259     ///is also added.
   260     ///\return The newly created node.
   261     ///
   262     ///\note All iterators remain valid.
   263     ///
   264     ///\warning This functionality cannot be used together with the Snapshot
   265     ///feature.
   266     Node split(Node n, bool connect = true)
   267     {
   268       Node b = addNode();
   269       nodes[b._id].first_out=nodes[n._id].first_out;
   270       nodes[n._id].first_out=-1;
   271       for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
   272         arcs[i].source=b._id;
   273       }
   274       if(connect) addArc(n,b);
   275       return b;
   276     }
   277 
   278     ///Clear the digraph.
   279 
   280     ///This function erases all nodes and arcs from the digraph.
   281     ///
   282     void clear() {
   283       Parent::clear();
   284     }
   285 
   286     /// Reserve memory for nodes.
   287 
   288     /// Using this function, it is possible to avoid superfluous memory
   289     /// allocation: if you know that the digraph you want to build will
   290     /// be large (e.g. it will contain millions of nodes and/or arcs),
   291     /// then it is worth reserving space for this amount before starting
   292     /// to build the digraph.
   293     /// \sa reserveArc()
   294     void reserveNode(int n) { nodes.reserve(n); };
   295 
   296     /// Reserve memory for arcs.
   297 
   298     /// Using this function, it is possible to avoid superfluous memory
   299     /// allocation: if you know that the digraph you want to build will
   300     /// be large (e.g. it will contain millions of nodes and/or arcs),
   301     /// then it is worth reserving space for this amount before starting
   302     /// to build the digraph.
   303     /// \sa reserveNode()
   304     void reserveArc(int m) { arcs.reserve(m); };
   305 
   306   public:
   307 
   308     class Snapshot;
   309 
   310   protected:
   311 
   312     void restoreSnapshot(const Snapshot &s)
   313     {
   314       while(s.arc_num<arcs.size()) {
   315         Arc arc = arcFromId(arcs.size()-1);
   316         Parent::notifier(Arc()).erase(arc);
   317         nodes[arcs.back().source].first_out=arcs.back().next_out;
   318         nodes[arcs.back().target].first_in=arcs.back().next_in;
   319         arcs.pop_back();
   320       }
   321       while(s.node_num<nodes.size()) {
   322         Node node = nodeFromId(nodes.size()-1);
   323         Parent::notifier(Node()).erase(node);
   324         nodes.pop_back();
   325       }
   326     }
   327 
   328   public:
   329 
   330     ///Class to make a snapshot of the digraph and to restore it later.
   331 
   332     ///Class to make a snapshot of the digraph and to restore it later.
   333     ///
   334     ///The newly added nodes and arcs can be removed using the
   335     ///restore() function. This is the only way for deleting nodes and/or
   336     ///arcs from a SmartDigraph structure.
   337     ///
   338     ///\note After a state is restored, you cannot restore a later state,
   339     ///i.e. you cannot add the removed nodes and arcs again using
   340     ///another Snapshot instance.
   341     ///
   342     ///\warning Node splitting cannot be restored.
   343     ///\warning The validity of the snapshot is not stored due to
   344     ///performance reasons. If you do not use the snapshot correctly,
   345     ///it can cause broken program, invalid or not restored state of
   346     ///the digraph or no change.
   347     class Snapshot
   348     {
   349       SmartDigraph *_graph;
   350     protected:
   351       friend class SmartDigraph;
   352       unsigned int node_num;
   353       unsigned int arc_num;
   354     public:
   355       ///Default constructor.
   356 
   357       ///Default constructor.
   358       ///You have to call save() to actually make a snapshot.
   359       Snapshot() : _graph(0) {}
   360       ///Constructor that immediately makes a snapshot
   361 
   362       ///This constructor immediately makes a snapshot of the given digraph.
   363       ///
   364       Snapshot(SmartDigraph &gr) : _graph(&gr) {
   365         node_num=_graph->nodes.size();
   366         arc_num=_graph->arcs.size();
   367       }
   368 
   369       ///Make a snapshot.
   370 
   371       ///This function makes a snapshot of the given digraph.
   372       ///It can be called more than once. In case of a repeated
   373       ///call, the previous snapshot gets lost.
   374       void save(SmartDigraph &gr) {
   375         _graph=&gr;
   376         node_num=_graph->nodes.size();
   377         arc_num=_graph->arcs.size();
   378       }
   379 
   380       ///Undo the changes until a snapshot.
   381 
   382       ///This function undos the changes until the last snapshot
   383       ///created by save() or Snapshot(SmartDigraph&).
   384       void restore()
   385       {
   386         _graph->restoreSnapshot(*this);
   387       }
   388     };
   389   };
   390 
   391 
   392   class SmartGraphBase {
   393 
   394   protected:
   395 
   396     struct NodeT {
   397       int first_out;
   398     };
   399 
   400     struct ArcT {
   401       int target;
   402       int next_out;
   403     };
   404 
   405     std::vector<NodeT> nodes;
   406     std::vector<ArcT> arcs;
   407 
   408   public:
   409 
   410     typedef SmartGraphBase Graph;
   411 
   412     class Node;
   413     class Arc;
   414     class Edge;
   415 
   416     class Node {
   417       friend class SmartGraphBase;
   418     protected:
   419 
   420       int _id;
   421       explicit Node(int id) { _id = id;}
   422 
   423     public:
   424       Node() {}
   425       Node (Invalid) { _id = -1; }
   426       bool operator==(const Node& node) const {return _id == node._id;}
   427       bool operator!=(const Node& node) const {return _id != node._id;}
   428       bool operator<(const Node& node) const {return _id < node._id;}
   429     };
   430 
   431     class Edge {
   432       friend class SmartGraphBase;
   433     protected:
   434 
   435       int _id;
   436       explicit Edge(int id) { _id = id;}
   437 
   438     public:
   439       Edge() {}
   440       Edge (Invalid) { _id = -1; }
   441       bool operator==(const Edge& arc) const {return _id == arc._id;}
   442       bool operator!=(const Edge& arc) const {return _id != arc._id;}
   443       bool operator<(const Edge& arc) const {return _id < arc._id;}
   444     };
   445 
   446     class Arc {
   447       friend class SmartGraphBase;
   448     protected:
   449 
   450       int _id;
   451       explicit Arc(int id) { _id = id;}
   452 
   453     public:
   454       operator Edge() const {
   455         return _id != -1 ? edgeFromId(_id / 2) : INVALID;
   456       }
   457 
   458       Arc() {}
   459       Arc (Invalid) { _id = -1; }
   460       bool operator==(const Arc& arc) const {return _id == arc._id;}
   461       bool operator!=(const Arc& arc) const {return _id != arc._id;}
   462       bool operator<(const Arc& arc) const {return _id < arc._id;}
   463     };
   464 
   465 
   466 
   467     SmartGraphBase()
   468       : nodes(), arcs() {}
   469 
   470     typedef True NodeNumTag;
   471     typedef True EdgeNumTag;
   472     typedef True ArcNumTag;
   473 
   474     int nodeNum() const { return nodes.size(); }
   475     int edgeNum() const { return arcs.size() / 2; }
   476     int arcNum() const { return arcs.size(); }
   477 
   478     int maxNodeId() const { return nodes.size()-1; }
   479     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   480     int maxArcId() const { return arcs.size()-1; }
   481 
   482     Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
   483     Node target(Arc e) const { return Node(arcs[e._id].target); }
   484 
   485     Node u(Edge e) const { return Node(arcs[2 * e._id].target); }
   486     Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
   487 
   488     static bool direction(Arc e) {
   489       return (e._id & 1) == 1;
   490     }
   491 
   492     static Arc direct(Edge e, bool d) {
   493       return Arc(e._id * 2 + (d ? 1 : 0));
   494     }
   495 
   496     void first(Node& node) const {
   497       node._id = nodes.size() - 1;
   498     }
   499 
   500     static void next(Node& node) {
   501       --node._id;
   502     }
   503 
   504     void first(Arc& arc) const {
   505       arc._id = arcs.size() - 1;
   506     }
   507 
   508     static void next(Arc& arc) {
   509       --arc._id;
   510     }
   511 
   512     void first(Edge& arc) const {
   513       arc._id = arcs.size() / 2 - 1;
   514     }
   515 
   516     static void next(Edge& arc) {
   517       --arc._id;
   518     }
   519 
   520     void firstOut(Arc &arc, const Node& v) const {
   521       arc._id = nodes[v._id].first_out;
   522     }
   523     void nextOut(Arc &arc) const {
   524       arc._id = arcs[arc._id].next_out;
   525     }
   526 
   527     void firstIn(Arc &arc, const Node& v) const {
   528       arc._id = ((nodes[v._id].first_out) ^ 1);
   529       if (arc._id == -2) arc._id = -1;
   530     }
   531     void nextIn(Arc &arc) const {
   532       arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
   533       if (arc._id == -2) arc._id = -1;
   534     }
   535 
   536     void firstInc(Edge &arc, bool& d, const Node& v) const {
   537       int de = nodes[v._id].first_out;
   538       if (de != -1) {
   539         arc._id = de / 2;
   540         d = ((de & 1) == 1);
   541       } else {
   542         arc._id = -1;
   543         d = true;
   544       }
   545     }
   546     void nextInc(Edge &arc, bool& d) const {
   547       int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
   548       if (de != -1) {
   549         arc._id = de / 2;
   550         d = ((de & 1) == 1);
   551       } else {
   552         arc._id = -1;
   553         d = true;
   554       }
   555     }
   556 
   557     static int id(Node v) { return v._id; }
   558     static int id(Arc e) { return e._id; }
   559     static int id(Edge e) { return e._id; }
   560 
   561     static Node nodeFromId(int id) { return Node(id);}
   562     static Arc arcFromId(int id) { return Arc(id);}
   563     static Edge edgeFromId(int id) { return Edge(id);}
   564 
   565     bool valid(Node n) const {
   566       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
   567     }
   568     bool valid(Arc a) const {
   569       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
   570     }
   571     bool valid(Edge e) const {
   572       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
   573     }
   574 
   575     Node addNode() {
   576       int n = nodes.size();
   577       nodes.push_back(NodeT());
   578       nodes[n].first_out = -1;
   579 
   580       return Node(n);
   581     }
   582 
   583     Edge addEdge(Node u, Node v) {
   584       int n = arcs.size();
   585       arcs.push_back(ArcT());
   586       arcs.push_back(ArcT());
   587 
   588       arcs[n].target = u._id;
   589       arcs[n | 1].target = v._id;
   590 
   591       arcs[n].next_out = nodes[v._id].first_out;
   592       nodes[v._id].first_out = n;
   593 
   594       arcs[n | 1].next_out = nodes[u._id].first_out;
   595       nodes[u._id].first_out = (n | 1);
   596 
   597       return Edge(n / 2);
   598     }
   599 
   600     void clear() {
   601       arcs.clear();
   602       nodes.clear();
   603     }
   604 
   605   };
   606 
   607   typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
   608 
   609   /// \ingroup graphs
   610   ///
   611   /// \brief A smart undirected graph class.
   612   ///
   613   /// \ref SmartGraph is a simple and fast graph implementation.
   614   /// It is also quite memory efficient but at the price
   615   /// that it does not support node and edge deletion
   616   /// (except for the Snapshot feature).
   617   ///
   618   /// This type fully conforms to the \ref concepts::Graph "Graph concept"
   619   /// and it also provides some additional functionalities.
   620   /// Most of its member functions and nested classes are documented
   621   /// only in the concept class.
   622   ///
   623   /// This class provides constant time counting for nodes, edges and arcs.
   624   ///
   625   /// \sa concepts::Graph
   626   /// \sa SmartDigraph
   627   class SmartGraph : public ExtendedSmartGraphBase {
   628     typedef ExtendedSmartGraphBase Parent;
   629 
   630   private:
   631     /// Graphs are \e not copy constructible. Use GraphCopy instead.
   632     SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
   633     /// \brief Assignment of a graph to another one is \e not allowed.
   634     /// Use GraphCopy instead.
   635     void operator=(const SmartGraph &) {}
   636 
   637   public:
   638 
   639     /// Constructor
   640 
   641     /// Constructor.
   642     ///
   643     SmartGraph() {}
   644 
   645     /// \brief Add a new node to the graph.
   646     ///
   647     /// This function adds a new node to the graph.
   648     /// \return The new node.
   649     Node addNode() { return Parent::addNode(); }
   650 
   651     /// \brief Add a new edge to the graph.
   652     ///
   653     /// This function adds a new edge to the graph between nodes
   654     /// \c u and \c v with inherent orientation from node \c u to
   655     /// node \c v.
   656     /// \return The new edge.
   657     Edge addEdge(Node u, Node v) {
   658       return Parent::addEdge(u, v);
   659     }
   660 
   661     /// \brief Node validity check
   662     ///
   663     /// This function gives back \c true if the given node is valid,
   664     /// i.e. it is a real node of the graph.
   665     ///
   666     /// \warning A removed node (using Snapshot) could become valid again
   667     /// if new nodes are added to the graph.
   668     bool valid(Node n) const { return Parent::valid(n); }
   669 
   670     /// \brief Edge validity check
   671     ///
   672     /// This function gives back \c true if the given edge is valid,
   673     /// i.e. it is a real edge of the graph.
   674     ///
   675     /// \warning A removed edge (using Snapshot) could become valid again
   676     /// if new edges are added to the graph.
   677     bool valid(Edge e) const { return Parent::valid(e); }
   678 
   679     /// \brief Arc validity check
   680     ///
   681     /// This function gives back \c true if the given arc is valid,
   682     /// i.e. it is a real arc of the graph.
   683     ///
   684     /// \warning A removed arc (using Snapshot) could become valid again
   685     /// if new edges are added to the graph.
   686     bool valid(Arc a) const { return Parent::valid(a); }
   687 
   688     ///Clear the graph.
   689 
   690     ///This function erases all nodes and arcs from the graph.
   691     ///
   692     void clear() {
   693       Parent::clear();
   694     }
   695 
   696     /// Reserve memory for nodes.
   697 
   698     /// Using this function, it is possible to avoid superfluous memory
   699     /// allocation: if you know that the graph you want to build will
   700     /// be large (e.g. it will contain millions of nodes and/or edges),
   701     /// then it is worth reserving space for this amount before starting
   702     /// to build the graph.
   703     /// \sa reserveEdge()
   704     void reserveNode(int n) { nodes.reserve(n); };
   705 
   706     /// Reserve memory for edges.
   707 
   708     /// Using this function, it is possible to avoid superfluous memory
   709     /// allocation: if you know that the graph you want to build will
   710     /// be large (e.g. it will contain millions of nodes and/or edges),
   711     /// then it is worth reserving space for this amount before starting
   712     /// to build the graph.
   713     /// \sa reserveNode()
   714     void reserveEdge(int m) { arcs.reserve(2 * m); };
   715 
   716   public:
   717 
   718     class Snapshot;
   719 
   720   protected:
   721 
   722     void saveSnapshot(Snapshot &s)
   723     {
   724       s._graph = this;
   725       s.node_num = nodes.size();
   726       s.arc_num = arcs.size();
   727     }
   728 
   729     void restoreSnapshot(const Snapshot &s)
   730     {
   731       while(s.arc_num<arcs.size()) {
   732         int n=arcs.size()-1;
   733         Edge arc=edgeFromId(n/2);
   734         Parent::notifier(Edge()).erase(arc);
   735         std::vector<Arc> dir;
   736         dir.push_back(arcFromId(n));
   737         dir.push_back(arcFromId(n-1));
   738         Parent::notifier(Arc()).erase(dir);
   739         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
   740         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
   741         arcs.pop_back();
   742         arcs.pop_back();
   743       }
   744       while(s.node_num<nodes.size()) {
   745         int n=nodes.size()-1;
   746         Node node = nodeFromId(n);
   747         Parent::notifier(Node()).erase(node);
   748         nodes.pop_back();
   749       }
   750     }
   751 
   752   public:
   753 
   754     ///Class to make a snapshot of the graph and to restore it later.
   755 
   756     ///Class to make a snapshot of the graph and to restore it later.
   757     ///
   758     ///The newly added nodes and edges can be removed using the
   759     ///restore() function. This is the only way for deleting nodes and/or
   760     ///edges from a SmartGraph structure.
   761     ///
   762     ///\note After a state is restored, you cannot restore a later state,
   763     ///i.e. you cannot add the removed nodes and edges again using
   764     ///another Snapshot instance.
   765     ///
   766     ///\warning The validity of the snapshot is not stored due to
   767     ///performance reasons. If you do not use the snapshot correctly,
   768     ///it can cause broken program, invalid or not restored state of
   769     ///the graph or no change.
   770     class Snapshot
   771     {
   772       SmartGraph *_graph;
   773     protected:
   774       friend class SmartGraph;
   775       unsigned int node_num;
   776       unsigned int arc_num;
   777     public:
   778       ///Default constructor.
   779 
   780       ///Default constructor.
   781       ///You have to call save() to actually make a snapshot.
   782       Snapshot() : _graph(0) {}
   783       ///Constructor that immediately makes a snapshot
   784 
   785       /// This constructor immediately makes a snapshot of the given graph.
   786       ///
   787       Snapshot(SmartGraph &gr) {
   788         gr.saveSnapshot(*this);
   789       }
   790 
   791       ///Make a snapshot.
   792 
   793       ///This function makes a snapshot of the given graph.
   794       ///It can be called more than once. In case of a repeated
   795       ///call, the previous snapshot gets lost.
   796       void save(SmartGraph &gr)
   797       {
   798         gr.saveSnapshot(*this);
   799       }
   800 
   801       ///Undo the changes until the last snapshot.
   802 
   803       ///This function undos the changes until the last snapshot
   804       ///created by save() or Snapshot(SmartGraph&).
   805       void restore()
   806       {
   807         _graph->restoreSnapshot(*this);
   808       }
   809     };
   810   };
   811 
   812   class SmartBpGraphBase {
   813 
   814   protected:
   815 
   816     struct NodeT {
   817       int first_out;
   818       int partition_next;
   819       int partition_index;
   820       bool red;
   821     };
   822 
   823     struct ArcT {
   824       int target;
   825       int next_out;
   826     };
   827 
   828     std::vector<NodeT> nodes;
   829     std::vector<ArcT> arcs;
   830 
   831     int first_red, first_blue;
   832     int max_red, max_blue;
   833 
   834   public:
   835 
   836     typedef SmartBpGraphBase Graph;
   837 
   838     class Node;
   839     class Arc;
   840     class Edge;
   841 
   842     class Node {
   843       friend class SmartBpGraphBase;
   844     protected:
   845 
   846       int _id;
   847       explicit Node(int id) { _id = id;}
   848 
   849     public:
   850       Node() {}
   851       Node (Invalid) { _id = -1; }
   852       bool operator==(const Node& node) const {return _id == node._id;}
   853       bool operator!=(const Node& node) const {return _id != node._id;}
   854       bool operator<(const Node& node) const {return _id < node._id;}
   855     };
   856 
   857     class RedNode : public Node {
   858       friend class SmartBpGraphBase;
   859     protected:
   860 
   861       explicit RedNode(int pid) : Node(pid) {}
   862 
   863     public:
   864       RedNode() {}
   865       RedNode(const RedNode& node) : Node(node) {}
   866       RedNode(Invalid) : Node(INVALID){}
   867     };
   868 
   869     class BlueNode : public Node {
   870       friend class SmartBpGraphBase;
   871     protected:
   872 
   873       explicit BlueNode(int pid) : Node(pid) {}
   874 
   875     public:
   876       BlueNode() {}
   877       BlueNode(const BlueNode& node) : Node(node) {}
   878       BlueNode(Invalid) : Node(INVALID){}
   879     };
   880 
   881     class Edge {
   882       friend class SmartBpGraphBase;
   883     protected:
   884 
   885       int _id;
   886       explicit Edge(int id) { _id = id;}
   887 
   888     public:
   889       Edge() {}
   890       Edge (Invalid) { _id = -1; }
   891       bool operator==(const Edge& arc) const {return _id == arc._id;}
   892       bool operator!=(const Edge& arc) const {return _id != arc._id;}
   893       bool operator<(const Edge& arc) const {return _id < arc._id;}
   894     };
   895 
   896     class Arc {
   897       friend class SmartBpGraphBase;
   898     protected:
   899 
   900       int _id;
   901       explicit Arc(int id) { _id = id;}
   902 
   903     public:
   904       operator Edge() const {
   905         return _id != -1 ? edgeFromId(_id / 2) : INVALID;
   906       }
   907 
   908       Arc() {}
   909       Arc (Invalid) { _id = -1; }
   910       bool operator==(const Arc& arc) const {return _id == arc._id;}
   911       bool operator!=(const Arc& arc) const {return _id != arc._id;}
   912       bool operator<(const Arc& arc) const {return _id < arc._id;}
   913     };
   914 
   915 
   916 
   917     SmartBpGraphBase()
   918       : nodes(), arcs(), first_red(-1), first_blue(-1),
   919         max_red(-1), max_blue(-1) {}
   920 
   921     typedef True NodeNumTag;
   922     typedef True EdgeNumTag;
   923     typedef True ArcNumTag;
   924 
   925     int nodeNum() const { return nodes.size(); }
   926     int redNum() const { return max_red + 1; }
   927     int blueNum() const { return max_blue + 1; }
   928     int edgeNum() const { return arcs.size() / 2; }
   929     int arcNum() const { return arcs.size(); }
   930 
   931     int maxNodeId() const { return nodes.size()-1; }
   932     int maxRedId() const { return max_red; }
   933     int maxBlueId() const { return max_blue; }
   934     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   935     int maxArcId() const { return arcs.size()-1; }
   936 
   937     bool red(Node n) const { return nodes[n._id].red; }
   938     bool blue(Node n) const { return !nodes[n._id].red; }
   939 
   940     static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
   941     static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
   942 
   943     Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
   944     Node target(Arc a) const { return Node(arcs[a._id].target); }
   945 
   946     RedNode redNode(Edge e) const {
   947       return RedNode(arcs[2 * e._id].target);
   948     }
   949     BlueNode blueNode(Edge e) const {
   950       return BlueNode(arcs[2 * e._id + 1].target);
   951     }
   952 
   953     static bool direction(Arc a) {
   954       return (a._id & 1) == 1;
   955     }
   956 
   957     static Arc direct(Edge e, bool d) {
   958       return Arc(e._id * 2 + (d ? 1 : 0));
   959     }
   960 
   961     void first(Node& node) const {
   962       node._id = nodes.size() - 1;
   963     }
   964 
   965     static void next(Node& node) {
   966       --node._id;
   967     }
   968 
   969     void first(RedNode& node) const {
   970       node._id = first_red;
   971     }
   972 
   973     void next(RedNode& node) const {
   974       node._id = nodes[node._id].partition_next;
   975     }
   976 
   977     void first(BlueNode& node) const {
   978       node._id = first_blue;
   979     }
   980 
   981     void next(BlueNode& node) const {
   982       node._id = nodes[node._id].partition_next;
   983     }
   984 
   985     void first(Arc& arc) const {
   986       arc._id = arcs.size() - 1;
   987     }
   988 
   989     static void next(Arc& arc) {
   990       --arc._id;
   991     }
   992 
   993     void first(Edge& arc) const {
   994       arc._id = arcs.size() / 2 - 1;
   995     }
   996 
   997     static void next(Edge& arc) {
   998       --arc._id;
   999     }
  1000 
  1001     void firstOut(Arc &arc, const Node& v) const {
  1002       arc._id = nodes[v._id].first_out;
  1003     }
  1004     void nextOut(Arc &arc) const {
  1005       arc._id = arcs[arc._id].next_out;
  1006     }
  1007 
  1008     void firstIn(Arc &arc, const Node& v) const {
  1009       arc._id = ((nodes[v._id].first_out) ^ 1);
  1010       if (arc._id == -2) arc._id = -1;
  1011     }
  1012     void nextIn(Arc &arc) const {
  1013       arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
  1014       if (arc._id == -2) arc._id = -1;
  1015     }
  1016 
  1017     void firstInc(Edge &arc, bool& d, const Node& v) const {
  1018       int de = nodes[v._id].first_out;
  1019       if (de != -1) {
  1020         arc._id = de / 2;
  1021         d = ((de & 1) == 1);
  1022       } else {
  1023         arc._id = -1;
  1024         d = true;
  1025       }
  1026     }
  1027     void nextInc(Edge &arc, bool& d) const {
  1028       int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
  1029       if (de != -1) {
  1030         arc._id = de / 2;
  1031         d = ((de & 1) == 1);
  1032       } else {
  1033         arc._id = -1;
  1034         d = true;
  1035       }
  1036     }
  1037 
  1038     static int id(Node v) { return v._id; }
  1039     int id(RedNode v) const { return nodes[v._id].partition_index; }
  1040     int id(BlueNode v) const { return nodes[v._id].partition_index; }
  1041     static int id(Arc e) { return e._id; }
  1042     static int id(Edge e) { return e._id; }
  1043 
  1044     static Node nodeFromId(int id) { return Node(id);}
  1045     static Arc arcFromId(int id) { return Arc(id);}
  1046     static Edge edgeFromId(int id) { return Edge(id);}
  1047 
  1048     bool valid(Node n) const {
  1049       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
  1050     }
  1051     bool valid(Arc a) const {
  1052       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
  1053     }
  1054     bool valid(Edge e) const {
  1055       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
  1056     }
  1057 
  1058     RedNode addRedNode() {
  1059       int n = nodes.size();
  1060       nodes.push_back(NodeT());
  1061       nodes[n].first_out = -1;
  1062       nodes[n].red = true;
  1063       nodes[n].partition_index = ++max_red;
  1064       nodes[n].partition_next = first_red;
  1065       first_red = n;
  1066 
  1067       return RedNode(n);
  1068     }
  1069 
  1070     BlueNode addBlueNode() {
  1071       int n = nodes.size();
  1072       nodes.push_back(NodeT());
  1073       nodes[n].first_out = -1;
  1074       nodes[n].red = false;
  1075       nodes[n].partition_index = ++max_blue;
  1076       nodes[n].partition_next = first_blue;
  1077       first_blue = n;
  1078 
  1079       return BlueNode(n);
  1080     }
  1081 
  1082     Edge addEdge(RedNode u, BlueNode v) {
  1083       int n = arcs.size();
  1084       arcs.push_back(ArcT());
  1085       arcs.push_back(ArcT());
  1086 
  1087       arcs[n].target = u._id;
  1088       arcs[n | 1].target = v._id;
  1089 
  1090       arcs[n].next_out = nodes[v._id].first_out;
  1091       nodes[v._id].first_out = n;
  1092 
  1093       arcs[n | 1].next_out = nodes[u._id].first_out;
  1094       nodes[u._id].first_out = (n | 1);
  1095 
  1096       return Edge(n / 2);
  1097     }
  1098 
  1099     void clear() {
  1100       arcs.clear();
  1101       nodes.clear();
  1102       first_red = -1;
  1103       first_blue = -1;
  1104       max_blue = -1;
  1105       max_red = -1;
  1106     }
  1107 
  1108   };
  1109 
  1110   typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase;
  1111 
  1112   /// \ingroup graphs
  1113   ///
  1114   /// \brief A smart undirected bipartite graph class.
  1115   ///
  1116   /// \ref SmartBpGraph is a simple and fast bipartite graph implementation.
  1117   /// It is also quite memory efficient but at the price
  1118   /// that it does not support node and edge deletion
  1119   /// (except for the Snapshot feature).
  1120   ///
  1121   /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
  1122   /// and it also provides some additional functionalities.
  1123   /// Most of its member functions and nested classes are documented
  1124   /// only in the concept class.
  1125   ///
  1126   /// This class provides constant time counting for nodes, edges and arcs.
  1127   ///
  1128   /// \sa concepts::BpGraph
  1129   /// \sa SmartGraph
  1130   class SmartBpGraph : public ExtendedSmartBpGraphBase {
  1131     typedef ExtendedSmartBpGraphBase Parent;
  1132 
  1133   private:
  1134     /// Graphs are \e not copy constructible. Use GraphCopy instead.
  1135     SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {};
  1136     /// \brief Assignment of a graph to another one is \e not allowed.
  1137     /// Use GraphCopy instead.
  1138     void operator=(const SmartBpGraph &) {}
  1139 
  1140   public:
  1141 
  1142     /// Constructor
  1143 
  1144     /// Constructor.
  1145     ///
  1146     SmartBpGraph() {}
  1147 
  1148     /// \brief Add a new red node to the graph.
  1149     ///
  1150     /// This function adds a red new node to the graph.
  1151     /// \return The new node.
  1152     RedNode addRedNode() { return Parent::addRedNode(); }
  1153 
  1154     /// \brief Add a new blue node to the graph.
  1155     ///
  1156     /// This function adds a blue new node to the graph.
  1157     /// \return The new node.
  1158     BlueNode addBlueNode() { return Parent::addBlueNode(); }
  1159 
  1160     /// \brief Add a new edge to the graph.
  1161     ///
  1162     /// This function adds a new edge to the graph between nodes
  1163     /// \c u and \c v with inherent orientation from node \c u to
  1164     /// node \c v.
  1165     /// \return The new edge.
  1166     Edge addEdge(RedNode u, BlueNode v) {
  1167       return Parent::addEdge(u, v);
  1168     }
  1169     Edge addEdge(BlueNode v, RedNode u) {
  1170       return Parent::addEdge(u, v);
  1171     }
  1172 
  1173     /// \brief Node validity check
  1174     ///
  1175     /// This function gives back \c true if the given node is valid,
  1176     /// i.e. it is a real node of the graph.
  1177     ///
  1178     /// \warning A removed node (using Snapshot) could become valid again
  1179     /// if new nodes are added to the graph.
  1180     bool valid(Node n) const { return Parent::valid(n); }
  1181 
  1182     /// \brief Edge validity check
  1183     ///
  1184     /// This function gives back \c true if the given edge is valid,
  1185     /// i.e. it is a real edge of the graph.
  1186     ///
  1187     /// \warning A removed edge (using Snapshot) could become valid again
  1188     /// if new edges are added to the graph.
  1189     bool valid(Edge e) const { return Parent::valid(e); }
  1190 
  1191     /// \brief Arc validity check
  1192     ///
  1193     /// This function gives back \c true if the given arc is valid,
  1194     /// i.e. it is a real arc of the graph.
  1195     ///
  1196     /// \warning A removed arc (using Snapshot) could become valid again
  1197     /// if new edges are added to the graph.
  1198     bool valid(Arc a) const { return Parent::valid(a); }
  1199 
  1200     ///Clear the graph.
  1201 
  1202     ///This function erases all nodes and arcs from the graph.
  1203     ///
  1204     void clear() {
  1205       Parent::clear();
  1206     }
  1207 
  1208     /// Reserve memory for nodes.
  1209 
  1210     /// Using this function, it is possible to avoid superfluous memory
  1211     /// allocation: if you know that the graph you want to build will
  1212     /// be large (e.g. it will contain millions of nodes and/or edges),
  1213     /// then it is worth reserving space for this amount before starting
  1214     /// to build the graph.
  1215     /// \sa reserveEdge()
  1216     void reserveNode(int n) { nodes.reserve(n); };
  1217 
  1218     /// Reserve memory for edges.
  1219 
  1220     /// Using this function, it is possible to avoid superfluous memory
  1221     /// allocation: if you know that the graph you want to build will
  1222     /// be large (e.g. it will contain millions of nodes and/or edges),
  1223     /// then it is worth reserving space for this amount before starting
  1224     /// to build the graph.
  1225     /// \sa reserveNode()
  1226     void reserveEdge(int m) { arcs.reserve(2 * m); };
  1227 
  1228   public:
  1229 
  1230     class Snapshot;
  1231 
  1232   protected:
  1233 
  1234     void saveSnapshot(Snapshot &s)
  1235     {
  1236       s._graph = this;
  1237       s.node_num = nodes.size();
  1238       s.arc_num = arcs.size();
  1239     }
  1240 
  1241     void restoreSnapshot(const Snapshot &s)
  1242     {
  1243       while(s.arc_num<arcs.size()) {
  1244         int n=arcs.size()-1;
  1245         Edge arc=edgeFromId(n/2);
  1246         Parent::notifier(Edge()).erase(arc);
  1247         std::vector<Arc> dir;
  1248         dir.push_back(arcFromId(n));
  1249         dir.push_back(arcFromId(n-1));
  1250         Parent::notifier(Arc()).erase(dir);
  1251         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
  1252         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
  1253         arcs.pop_back();
  1254         arcs.pop_back();
  1255       }
  1256       while(s.node_num<nodes.size()) {
  1257         int n=nodes.size()-1;
  1258         Node node = nodeFromId(n);
  1259         if (Parent::red(node)) {
  1260           first_red = nodes[n].partition_next;
  1261           if (first_red != -1) {
  1262             max_red = nodes[first_red].partition_index;
  1263           } else {
  1264             max_red = -1;
  1265           }
  1266           Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));          
  1267         } else {
  1268           first_blue = nodes[n].partition_next;
  1269           if (first_blue != -1) {
  1270             max_blue = nodes[first_blue].partition_index;
  1271           } else {
  1272             max_blue = -1;
  1273           }
  1274           Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
  1275         }
  1276         Parent::notifier(Node()).erase(node);
  1277         nodes.pop_back();
  1278       }
  1279     }
  1280 
  1281   public:
  1282 
  1283     ///Class to make a snapshot of the graph and to restore it later.
  1284 
  1285     ///Class to make a snapshot of the graph and to restore it later.
  1286     ///
  1287     ///The newly added nodes and edges can be removed using the
  1288     ///restore() function. This is the only way for deleting nodes and/or
  1289     ///edges from a SmartBpGraph structure.
  1290     ///
  1291     ///\note After a state is restored, you cannot restore a later state,
  1292     ///i.e. you cannot add the removed nodes and edges again using
  1293     ///another Snapshot instance.
  1294     ///
  1295     ///\warning The validity of the snapshot is not stored due to
  1296     ///performance reasons. If you do not use the snapshot correctly,
  1297     ///it can cause broken program, invalid or not restored state of
  1298     ///the graph or no change.
  1299     class Snapshot
  1300     {
  1301       SmartBpGraph *_graph;
  1302     protected:
  1303       friend class SmartBpGraph;
  1304       unsigned int node_num;
  1305       unsigned int arc_num;
  1306     public:
  1307       ///Default constructor.
  1308 
  1309       ///Default constructor.
  1310       ///You have to call save() to actually make a snapshot.
  1311       Snapshot() : _graph(0) {}
  1312       ///Constructor that immediately makes a snapshot
  1313 
  1314       /// This constructor immediately makes a snapshot of the given graph.
  1315       ///
  1316       Snapshot(SmartBpGraph &gr) {
  1317         gr.saveSnapshot(*this);
  1318       }
  1319 
  1320       ///Make a snapshot.
  1321 
  1322       ///This function makes a snapshot of the given graph.
  1323       ///It can be called more than once. In case of a repeated
  1324       ///call, the previous snapshot gets lost.
  1325       void save(SmartBpGraph &gr)
  1326       {
  1327         gr.saveSnapshot(*this);
  1328       }
  1329 
  1330       ///Undo the changes until the last snapshot.
  1331 
  1332       ///This function undos the changes until the last snapshot
  1333       ///created by save() or Snapshot(SmartBpGraph&).
  1334       void restore()
  1335       {
  1336         _graph->restoreSnapshot(*this);
  1337       }
  1338     };
  1339   };
  1340 
  1341 } //namespace lemon
  1342 
  1343 
  1344 #endif //LEMON_SMART_GRAPH_H