lemon/smart_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 29 Jul 2020 14:56:10 +0200
changeset 1433 a278d16bd2d0
parent 1336 0759d974de81
permissions -rw-r--r--
Fix clang compilation issue (#634)
     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-2013
     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       const RedNode& operator=(const RedNode& node) { Node::operator=(node); return *this;}
   868     };
   869 
   870     class BlueNode : public Node {
   871       friend class SmartBpGraphBase;
   872     protected:
   873 
   874       explicit BlueNode(int pid) : Node(pid) {}
   875 
   876     public:
   877       BlueNode() {}
   878       BlueNode(const BlueNode& node) : Node(node) {}
   879       BlueNode(Invalid) : Node(INVALID){}
   880       const BlueNode& operator=(const BlueNode& node) { Node::operator=(node); return *this;}
   881     };
   882 
   883     class Edge {
   884       friend class SmartBpGraphBase;
   885     protected:
   886 
   887       int _id;
   888       explicit Edge(int id) { _id = id;}
   889 
   890     public:
   891       Edge() {}
   892       Edge (Invalid) { _id = -1; }
   893       bool operator==(const Edge& arc) const {return _id == arc._id;}
   894       bool operator!=(const Edge& arc) const {return _id != arc._id;}
   895       bool operator<(const Edge& arc) const {return _id < arc._id;}
   896     };
   897 
   898     class Arc {
   899       friend class SmartBpGraphBase;
   900     protected:
   901 
   902       int _id;
   903       explicit Arc(int id) { _id = id;}
   904 
   905     public:
   906       operator Edge() const {
   907         return _id != -1 ? edgeFromId(_id / 2) : INVALID;
   908       }
   909 
   910       Arc() {}
   911       Arc (Invalid) { _id = -1; }
   912       bool operator==(const Arc& arc) const {return _id == arc._id;}
   913       bool operator!=(const Arc& arc) const {return _id != arc._id;}
   914       bool operator<(const Arc& arc) const {return _id < arc._id;}
   915     };
   916 
   917 
   918 
   919     SmartBpGraphBase()
   920       : _nodes(), _arcs(), first_red(-1), first_blue(-1),
   921         max_red(-1), max_blue(-1) {}
   922 
   923     typedef True NodeNumTag;
   924     typedef True EdgeNumTag;
   925     typedef True ArcNumTag;
   926 
   927     int nodeNum() const { return _nodes.size(); }
   928     int redNum() const { return max_red + 1; }
   929     int blueNum() const { return max_blue + 1; }
   930     int edgeNum() const { return _arcs.size() / 2; }
   931     int arcNum() const { return _arcs.size(); }
   932 
   933     int maxNodeId() const { return _nodes.size()-1; }
   934     int maxRedId() const { return max_red; }
   935     int maxBlueId() const { return max_blue; }
   936     int maxEdgeId() const { return _arcs.size() / 2 - 1; }
   937     int maxArcId() const { return _arcs.size()-1; }
   938 
   939     bool red(Node n) const { return _nodes[n._id].red; }
   940     bool blue(Node n) const { return !_nodes[n._id].red; }
   941 
   942     static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
   943     static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
   944 
   945     Node source(Arc a) const { return Node(_arcs[a._id ^ 1].target); }
   946     Node target(Arc a) const { return Node(_arcs[a._id].target); }
   947 
   948     RedNode redNode(Edge e) const {
   949       return RedNode(_arcs[2 * e._id].target);
   950     }
   951     BlueNode blueNode(Edge e) const {
   952       return BlueNode(_arcs[2 * e._id + 1].target);
   953     }
   954 
   955     static bool direction(Arc a) {
   956       return (a._id & 1) == 1;
   957     }
   958 
   959     static Arc direct(Edge e, bool d) {
   960       return Arc(e._id * 2 + (d ? 1 : 0));
   961     }
   962 
   963     void first(Node& node) const {
   964       node._id = _nodes.size() - 1;
   965     }
   966 
   967     static void next(Node& node) {
   968       --node._id;
   969     }
   970 
   971     void first(RedNode& node) const {
   972       node._id = first_red;
   973     }
   974 
   975     void next(RedNode& node) const {
   976       node._id = _nodes[node._id].partition_next;
   977     }
   978 
   979     void first(BlueNode& node) const {
   980       node._id = first_blue;
   981     }
   982 
   983     void next(BlueNode& node) const {
   984       node._id = _nodes[node._id].partition_next;
   985     }
   986 
   987     void first(Arc& arc) const {
   988       arc._id = _arcs.size() - 1;
   989     }
   990 
   991     static void next(Arc& arc) {
   992       --arc._id;
   993     }
   994 
   995     void first(Edge& arc) const {
   996       arc._id = _arcs.size() / 2 - 1;
   997     }
   998 
   999     static void next(Edge& arc) {
  1000       --arc._id;
  1001     }
  1002 
  1003     void firstOut(Arc &arc, const Node& v) const {
  1004       arc._id = _nodes[v._id].first_out;
  1005     }
  1006     void nextOut(Arc &arc) const {
  1007       arc._id = _arcs[arc._id].next_out;
  1008     }
  1009 
  1010     void firstIn(Arc &arc, const Node& v) const {
  1011       arc._id = ((_nodes[v._id].first_out) ^ 1);
  1012       if (arc._id == -2) arc._id = -1;
  1013     }
  1014     void nextIn(Arc &arc) const {
  1015       arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1);
  1016       if (arc._id == -2) arc._id = -1;
  1017     }
  1018 
  1019     void firstInc(Edge &arc, bool& d, const Node& v) const {
  1020       int de = _nodes[v._id].first_out;
  1021       if (de != -1) {
  1022         arc._id = de / 2;
  1023         d = ((de & 1) == 1);
  1024       } else {
  1025         arc._id = -1;
  1026         d = true;
  1027       }
  1028     }
  1029     void nextInc(Edge &arc, bool& d) const {
  1030       int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
  1031       if (de != -1) {
  1032         arc._id = de / 2;
  1033         d = ((de & 1) == 1);
  1034       } else {
  1035         arc._id = -1;
  1036         d = true;
  1037       }
  1038     }
  1039 
  1040     static int id(Node v) { return v._id; }
  1041     int id(RedNode v) const { return _nodes[v._id].partition_index; }
  1042     int id(BlueNode v) const { return _nodes[v._id].partition_index; }
  1043     static int id(Arc e) { return e._id; }
  1044     static int id(Edge e) { return e._id; }
  1045 
  1046     static Node nodeFromId(int id) { return Node(id);}
  1047     static Arc arcFromId(int id) { return Arc(id);}
  1048     static Edge edgeFromId(int id) { return Edge(id);}
  1049 
  1050     bool valid(Node n) const {
  1051       return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
  1052     }
  1053     bool valid(Arc a) const {
  1054       return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
  1055     }
  1056     bool valid(Edge e) const {
  1057       return e._id >= 0 && 2 * e._id < static_cast<int>(_arcs.size());
  1058     }
  1059 
  1060     RedNode addRedNode() {
  1061       int n = _nodes.size();
  1062       _nodes.push_back(NodeT());
  1063       _nodes[n].first_out = -1;
  1064       _nodes[n].red = true;
  1065       _nodes[n].partition_index = ++max_red;
  1066       _nodes[n].partition_next = first_red;
  1067       first_red = n;
  1068 
  1069       return RedNode(n);
  1070     }
  1071 
  1072     BlueNode addBlueNode() {
  1073       int n = _nodes.size();
  1074       _nodes.push_back(NodeT());
  1075       _nodes[n].first_out = -1;
  1076       _nodes[n].red = false;
  1077       _nodes[n].partition_index = ++max_blue;
  1078       _nodes[n].partition_next = first_blue;
  1079       first_blue = n;
  1080 
  1081       return BlueNode(n);
  1082     }
  1083 
  1084     Edge addEdge(RedNode u, BlueNode v) {
  1085       int n = _arcs.size();
  1086       _arcs.push_back(ArcT());
  1087       _arcs.push_back(ArcT());
  1088 
  1089       _arcs[n].target = u._id;
  1090       _arcs[n | 1].target = v._id;
  1091 
  1092       _arcs[n].next_out = _nodes[v._id].first_out;
  1093       _nodes[v._id].first_out = n;
  1094 
  1095       _arcs[n | 1].next_out = _nodes[u._id].first_out;
  1096       _nodes[u._id].first_out = (n | 1);
  1097 
  1098       return Edge(n / 2);
  1099     }
  1100 
  1101     void clear() {
  1102       _arcs.clear();
  1103       _nodes.clear();
  1104       first_red = -1;
  1105       first_blue = -1;
  1106       max_blue = -1;
  1107       max_red = -1;
  1108     }
  1109 
  1110   };
  1111 
  1112   typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase;
  1113 
  1114   /// \ingroup graphs
  1115   ///
  1116   /// \brief A smart undirected bipartite graph class.
  1117   ///
  1118   /// \ref SmartBpGraph is a simple and fast bipartite graph implementation.
  1119   /// It is also quite memory efficient but at the price
  1120   /// that it does not support node and edge deletion
  1121   /// (except for the Snapshot feature).
  1122   ///
  1123   /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
  1124   /// and it also provides some additional functionalities.
  1125   /// Most of its member functions and nested classes are documented
  1126   /// only in the concept class.
  1127   ///
  1128   /// This class provides constant time counting for nodes, edges and arcs.
  1129   ///
  1130   /// \sa concepts::BpGraph
  1131   /// \sa SmartGraph
  1132   class SmartBpGraph : public ExtendedSmartBpGraphBase {
  1133     typedef ExtendedSmartBpGraphBase Parent;
  1134 
  1135   private:
  1136     /// Graphs are \e not copy constructible. Use GraphCopy instead.
  1137     SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {};
  1138     /// \brief Assignment of a graph to another one is \e not allowed.
  1139     /// Use GraphCopy instead.
  1140     void operator=(const SmartBpGraph &) {}
  1141 
  1142   public:
  1143 
  1144     /// Constructor
  1145 
  1146     /// Constructor.
  1147     ///
  1148     SmartBpGraph() {}
  1149 
  1150     /// \brief Add a new red node to the graph.
  1151     ///
  1152     /// This function adds a red new node to the graph.
  1153     /// \return The new node.
  1154     RedNode addRedNode() { return Parent::addRedNode(); }
  1155 
  1156     /// \brief Add a new blue node to the graph.
  1157     ///
  1158     /// This function adds a blue new node to the graph.
  1159     /// \return The new node.
  1160     BlueNode addBlueNode() { return Parent::addBlueNode(); }
  1161 
  1162     /// \brief Add a new edge to the graph.
  1163     ///
  1164     /// This function adds a new edge to the graph between nodes
  1165     /// \c u and \c v with inherent orientation from node \c u to
  1166     /// node \c v.
  1167     /// \return The new edge.
  1168     Edge addEdge(RedNode u, BlueNode v) {
  1169       return Parent::addEdge(u, v);
  1170     }
  1171     Edge addEdge(BlueNode v, RedNode u) {
  1172       return Parent::addEdge(u, v);
  1173     }
  1174 
  1175     /// \brief Node validity check
  1176     ///
  1177     /// This function gives back \c true if the given node is valid,
  1178     /// i.e. it is a real node of the graph.
  1179     ///
  1180     /// \warning A removed node (using Snapshot) could become valid again
  1181     /// if new nodes are added to the graph.
  1182     bool valid(Node n) const { return Parent::valid(n); }
  1183 
  1184     /// \brief Edge validity check
  1185     ///
  1186     /// This function gives back \c true if the given edge is valid,
  1187     /// i.e. it is a real edge of the graph.
  1188     ///
  1189     /// \warning A removed edge (using Snapshot) could become valid again
  1190     /// if new edges are added to the graph.
  1191     bool valid(Edge e) const { return Parent::valid(e); }
  1192 
  1193     /// \brief Arc validity check
  1194     ///
  1195     /// This function gives back \c true if the given arc is valid,
  1196     /// i.e. it is a real arc of the graph.
  1197     ///
  1198     /// \warning A removed arc (using Snapshot) could become valid again
  1199     /// if new edges are added to the graph.
  1200     bool valid(Arc a) const { return Parent::valid(a); }
  1201 
  1202     ///Clear the graph.
  1203 
  1204     ///This function erases all nodes and arcs from the graph.
  1205     ///
  1206     void clear() {
  1207       Parent::clear();
  1208     }
  1209 
  1210     /// Reserve memory for nodes.
  1211 
  1212     /// Using this function, it is possible to avoid superfluous memory
  1213     /// allocation: if you know that the graph you want to build will
  1214     /// be large (e.g. it will contain millions of nodes and/or edges),
  1215     /// then it is worth reserving space for this amount before starting
  1216     /// to build the graph.
  1217     /// \sa reserveEdge()
  1218     void reserveNode(int n) { _nodes.reserve(n); };
  1219 
  1220     /// Reserve memory for edges.
  1221 
  1222     /// Using this function, it is possible to avoid superfluous memory
  1223     /// allocation: if you know that the graph you want to build will
  1224     /// be large (e.g. it will contain millions of nodes and/or edges),
  1225     /// then it is worth reserving space for this amount before starting
  1226     /// to build the graph.
  1227     /// \sa reserveNode()
  1228     void reserveEdge(int m) { _arcs.reserve(2 * m); };
  1229 
  1230   public:
  1231 
  1232     class Snapshot;
  1233 
  1234   protected:
  1235 
  1236     void saveSnapshot(Snapshot &s)
  1237     {
  1238       s._graph = this;
  1239       s.node_num = _nodes.size();
  1240       s.arc_num = _arcs.size();
  1241     }
  1242 
  1243     void restoreSnapshot(const Snapshot &s)
  1244     {
  1245       while(s.arc_num<_arcs.size()) {
  1246         int n=_arcs.size()-1;
  1247         Edge arc=edgeFromId(n/2);
  1248         Parent::notifier(Edge()).erase(arc);
  1249         std::vector<Arc> dir;
  1250         dir.push_back(arcFromId(n));
  1251         dir.push_back(arcFromId(n-1));
  1252         Parent::notifier(Arc()).erase(dir);
  1253         _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out;
  1254         _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out;
  1255         _arcs.pop_back();
  1256         _arcs.pop_back();
  1257       }
  1258       while(s.node_num<_nodes.size()) {
  1259         int n=_nodes.size()-1;
  1260         Node node = nodeFromId(n);
  1261         if (Parent::red(node)) {
  1262           first_red = _nodes[n].partition_next;
  1263           if (first_red != -1) {
  1264             max_red = _nodes[first_red].partition_index;
  1265           } else {
  1266             max_red = -1;
  1267           }
  1268           Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
  1269         } else {
  1270           first_blue = _nodes[n].partition_next;
  1271           if (first_blue != -1) {
  1272             max_blue = _nodes[first_blue].partition_index;
  1273           } else {
  1274             max_blue = -1;
  1275           }
  1276           Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
  1277         }
  1278         Parent::notifier(Node()).erase(node);
  1279         _nodes.pop_back();
  1280       }
  1281     }
  1282 
  1283   public:
  1284 
  1285     ///Class to make a snapshot of the graph and to restore it later.
  1286 
  1287     ///Class to make a snapshot of the graph and to restore it later.
  1288     ///
  1289     ///The newly added nodes and edges can be removed using the
  1290     ///restore() function. This is the only way for deleting nodes and/or
  1291     ///edges from a SmartBpGraph structure.
  1292     ///
  1293     ///\note After a state is restored, you cannot restore a later state,
  1294     ///i.e. you cannot add the removed nodes and edges again using
  1295     ///another Snapshot instance.
  1296     ///
  1297     ///\warning The validity of the snapshot is not stored due to
  1298     ///performance reasons. If you do not use the snapshot correctly,
  1299     ///it can cause broken program, invalid or not restored state of
  1300     ///the graph or no change.
  1301     class Snapshot
  1302     {
  1303       SmartBpGraph *_graph;
  1304     protected:
  1305       friend class SmartBpGraph;
  1306       unsigned int node_num;
  1307       unsigned int arc_num;
  1308     public:
  1309       ///Default constructor.
  1310 
  1311       ///Default constructor.
  1312       ///You have to call save() to actually make a snapshot.
  1313       Snapshot() : _graph(0) {}
  1314       ///Constructor that immediately makes a snapshot
  1315 
  1316       /// This constructor immediately makes a snapshot of the given graph.
  1317       ///
  1318       Snapshot(SmartBpGraph &gr) {
  1319         gr.saveSnapshot(*this);
  1320       }
  1321 
  1322       ///Make a snapshot.
  1323 
  1324       ///This function makes a snapshot of the given graph.
  1325       ///It can be called more than once. In case of a repeated
  1326       ///call, the previous snapshot gets lost.
  1327       void save(SmartBpGraph &gr)
  1328       {
  1329         gr.saveSnapshot(*this);
  1330       }
  1331 
  1332       ///Undo the changes until the last snapshot.
  1333 
  1334       ///This function undos the changes until the last snapshot
  1335       ///created by save() or Snapshot(SmartBpGraph&).
  1336       void restore()
  1337       {
  1338         _graph->restoreSnapshot(*this);
  1339       }
  1340     };
  1341   };
  1342 
  1343 } //namespace lemon
  1344 
  1345 
  1346 #endif //LEMON_SMART_GRAPH_H