Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/smart_graph.h
changeset 1380 04f57dad1b07
parent 1270 dceba191c00d
child 1432 da87dbdf3daf
equal deleted inserted replaced
34:41b19523364d 35:913e13159591 
    45     {
 
    45     {
 
    46       int target, source, next_in, next_out;
 
    46       int target, source, next_in, next_out;
 
    47       ArcT() {}
 
    47       ArcT() {}
 
    48     };
 
    48     };
 
    49 
    49 
    50     std::vector<NodeT> nodes;
 
    50     std::vector<NodeT> _nodes;
 
    51     std::vector<ArcT> arcs;
 
    51     std::vector<ArcT> _arcs;
 
    52 
    52 
    53   public:
 
    53   public:
 
    54 
    54 
    55     typedef SmartDigraphBase Digraph;
 
    55     typedef SmartDigraphBase Digraph;
 
    56 
    56 
    57     class Node;
 
    57     class Node;
 
    58     class Arc;
 
    58     class Arc;
 
    59 
    59 
    60   public:
 
    60   public:
 
    61 
    61 
    62     SmartDigraphBase() : nodes(), arcs() { }
 
    62     SmartDigraphBase() : _nodes(), _arcs() { }
 
    63     SmartDigraphBase(const SmartDigraphBase &_g)
 
    63     SmartDigraphBase(const SmartDigraphBase &_g)
 
    64       : nodes(_g.nodes), arcs(_g.arcs) { }
 
    64       : _nodes(_g._nodes), _arcs(_g._arcs) { }
 
    65 
    65 
    66     typedef True NodeNumTag;
 
    66     typedef True NodeNumTag;
 
    67     typedef True ArcNumTag;
 
    67     typedef True ArcNumTag;
 
    68 
    68 
    69     int nodeNum() const { return nodes.size(); }
 
    69     int nodeNum() const { return _nodes.size(); }
 
    70     int arcNum() const { return arcs.size(); }
 
    70     int arcNum() const { return _arcs.size(); }
 
    71 
    71 
    72     int maxNodeId() const { return nodes.size()-1; }
 
    72     int maxNodeId() const { return _nodes.size()-1; }
 
    73     int maxArcId() const { return arcs.size()-1; }
 
    73     int maxArcId() const { return _arcs.size()-1; }
 
    74 
    74 
    75     Node addNode() {
 
    75     Node addNode() {
 
    76       int n = nodes.size();
 
    76       int n = _nodes.size();
 
    77       nodes.push_back(NodeT());
 
    77       _nodes.push_back(NodeT());
 
    78       nodes[n].first_in = -1;
 
    78       _nodes[n].first_in = -1;
 
    79       nodes[n].first_out = -1;
 
    79       _nodes[n].first_out = -1;
 
    80       return Node(n);
 
    80       return Node(n);
 
    81     }
 
    81     }
 
    82 
    82 
    83     Arc addArc(Node u, Node v) {
 
    83     Arc addArc(Node u, Node v) {
 
    84       int n = arcs.size();
 
    84       int n = _arcs.size();
 
    85       arcs.push_back(ArcT());
 
    85       _arcs.push_back(ArcT());
 
    86       arcs[n].source = u._id;
 
    86       _arcs[n].source = u._id;
 
    87       arcs[n].target = v._id;
 
    87       _arcs[n].target = v._id;
 
    88       arcs[n].next_out = nodes[u._id].first_out;
 
    88       _arcs[n].next_out = _nodes[u._id].first_out;
 
    89       arcs[n].next_in = nodes[v._id].first_in;
 
    89       _arcs[n].next_in = _nodes[v._id].first_in;
 
    90       nodes[u._id].first_out = nodes[v._id].first_in = n;
 
    90       _nodes[u._id].first_out = _nodes[v._id].first_in = n;
 
    91 
    91 
    92       return Arc(n);
 
    92       return Arc(n);
 
    93     }
 
    93     }
 
    94 
    94 
    95     void clear() {
 
    95     void clear() {
 
    96       arcs.clear();
 
    96       _arcs.clear();
 
    97       nodes.clear();
 
    97       _nodes.clear();
 
    98     }
 
    98     }
 
    99 
    99 
   100     Node source(Arc a) const { return Node(arcs[a._id].source); }
 
   100     Node source(Arc a) const { return Node(_arcs[a._id].source); }
 
   101     Node target(Arc a) const { return Node(arcs[a._id].target); }
 
   101     Node target(Arc a) const { return Node(_arcs[a._id].target); }
 
   102 
   102 
   103     static int id(Node v) { return v._id; }
 
   103     static int id(Node v) { return v._id; }
 
   104     static int id(Arc a) { return a._id; }
 
   104     static int id(Arc a) { return a._id; }
 
   105 
   105 
   106     static Node nodeFromId(int id) { return Node(id);}
 
   106     static Node nodeFromId(int id) { return Node(id);}
 
   107     static Arc arcFromId(int id) { return Arc(id);}
 
   107     static Arc arcFromId(int id) { return Arc(id);}
 
   108 
   108 
   109     bool valid(Node n) const {
 
   109     bool valid(Node n) const {
 
   110       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
 
   110       return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
 
   111     }
 
   111     }
 
   112     bool valid(Arc a) const {
 
   112     bool valid(Arc a) const {
 
   113       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
 
   113       return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
 
   114     }
 
   114     }
 
   115 
   115 
   116     class Node {
 
   116     class Node {
 
   117       friend class SmartDigraphBase;
 
   117       friend class SmartDigraphBase;
 
   118       friend class SmartDigraph;
 
   118       friend class SmartDigraph;
 
   143       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;}
 
   144       bool operator<(const Arc i) const {return _id < i._id;}
 
   145     };
 
   145     };
 
   146 
   146 
   147     void first(Node& node) const {
 
   147     void first(Node& node) const {
 
   148       node._id = nodes.size() - 1;
 
   148       node._id = _nodes.size() - 1;
 
   149     }
 
   149     }
 
   150 
   150 
   151     static void next(Node& node) {
 
   151     static void next(Node& node) {
 
   152       --node._id;
 
   152       --node._id;
 
   153     }
 
   153     }
 
   154 
   154 
   155     void first(Arc& arc) const {
 
   155     void first(Arc& arc) const {
 
   156       arc._id = arcs.size() - 1;
 
   156       arc._id = _arcs.size() - 1;
 
   157     }
 
   157     }
 
   158 
   158 
   159     static void next(Arc& arc) {
 
   159     static void next(Arc& arc) {
 
   160       --arc._id;
 
   160       --arc._id;
 
   161     }
 
   161     }
 
   162 
   162 
   163     void firstOut(Arc& arc, const Node& node) const {
 
   163     void firstOut(Arc& arc, const Node& node) const {
 
   164       arc._id = nodes[node._id].first_out;
 
   164       arc._id = _nodes[node._id].first_out;
 
   165     }
 
   165     }
 
   166 
   166 
   167     void nextOut(Arc& arc) const {
 
   167     void nextOut(Arc& arc) const {
 
   168       arc._id = arcs[arc._id].next_out;
 
   168       arc._id = _arcs[arc._id].next_out;
 
   169     }
 
   169     }
 
   170 
   170 
   171     void firstIn(Arc& arc, const Node& node) const {
 
   171     void firstIn(Arc& arc, const Node& node) const {
 
   172       arc._id = nodes[node._id].first_in;
 
   172       arc._id = _nodes[node._id].first_in;
 
   173     }
 
   173     }
 
   174 
   174 
   175     void nextIn(Arc& arc) const {
 
   175     void nextIn(Arc& arc) const {
 
   176       arc._id = arcs[arc._id].next_in;
 
   176       arc._id = _arcs[arc._id].next_in;
 
   177     }
 
   177     }
 
   178 
   178 
   179   };
 
   179   };
 
   180 
   180 
   181   typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
 
   181   typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
 
   264     ///\warning This functionality cannot be used together with the Snapshot
 
   264     ///\warning This functionality cannot be used together with the Snapshot
 
   265     ///feature.
 
   265     ///feature.
 
   266     Node split(Node n, bool connect = true)
 
   266     Node split(Node n, bool connect = true)
 
   267     {
 
   267     {
 
   268       Node b = addNode();
 
   268       Node b = addNode();
 
   269       nodes[b._id].first_out=nodes[n._id].first_out;
 
   269       _nodes[b._id].first_out=_nodes[n._id].first_out;
 
   270       nodes[n._id].first_out=-1;
 
   270       _nodes[n._id].first_out=-1;
 
   271       for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
 
   271       for(int i=_nodes[b._id].first_out; i!=-1; i=_arcs[i].next_out) {
 
   272         arcs[i].source=b._id;
 
   272         _arcs[i].source=b._id;
 
   273       }
 
   273       }
 
   274       if(connect) addArc(n,b);
 
   274       if(connect) addArc(n,b);
 
   275       return b;
 
   275       return b;
 
   276     }
 
   276     }
 
   277 
   277 
   289     /// allocation: if you know that the digraph you want to build will
 
   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),
 
   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
 
   291     /// then it is worth reserving space for this amount before starting
 
   292     /// to build the digraph.
 
   292     /// to build the digraph.
 
   293     /// \sa reserveArc()
 
   293     /// \sa reserveArc()
 
   294     void reserveNode(int n) { nodes.reserve(n); };
 
   294     void reserveNode(int n) { _nodes.reserve(n); };
 
   295 
   295 
   296     /// Reserve memory for arcs.
 
   296     /// Reserve memory for arcs.
 
   297 
   297 
   298     /// Using this function, it is possible to avoid superfluous memory
 
   298     /// Using this function, it is possible to avoid superfluous memory
 
   299     /// allocation: if you know that the digraph you want to build will
 
   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),
 
   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
 
   301     /// then it is worth reserving space for this amount before starting
 
   302     /// to build the digraph.
 
   302     /// to build the digraph.
 
   303     /// \sa reserveNode()
 
   303     /// \sa reserveNode()
 
   304     void reserveArc(int m) { arcs.reserve(m); };
 
   304     void reserveArc(int m) { _arcs.reserve(m); };
 
   305 
   305 
   306   public:
 
   306   public:
 
   307 
   307 
   308     class Snapshot;
 
   308     class Snapshot;
 
   309 
   309 
   310   protected:
 
   310   protected:
 
   311 
   311 
   312     void restoreSnapshot(const Snapshot &s)
 
   312     void restoreSnapshot(const Snapshot &s)
 
   313     {
 
   313     {
 
   314       while(s.arc_num<arcs.size()) {
 
   314       while(s.arc_num<_arcs.size()) {
 
   315         Arc arc = arcFromId(arcs.size()-1);
 
   315         Arc arc = arcFromId(_arcs.size()-1);
 
   316         Parent::notifier(Arc()).erase(arc);
 
   316         Parent::notifier(Arc()).erase(arc);
 
   317         nodes[arcs.back().source].first_out=arcs.back().next_out;
 
   317         _nodes[_arcs.back().source].first_out=_arcs.back().next_out;
 
   318         nodes[arcs.back().target].first_in=arcs.back().next_in;
 
   318         _nodes[_arcs.back().target].first_in=_arcs.back().next_in;
 
   319         arcs.pop_back();
 
   319         _arcs.pop_back();
 
   320       }
 
   320       }
 
   321       while(s.node_num<nodes.size()) {
 
   321       while(s.node_num<_nodes.size()) {
 
   322         Node node = nodeFromId(nodes.size()-1);
 
   322         Node node = nodeFromId(_nodes.size()-1);
 
   323         Parent::notifier(Node()).erase(node);
 
   323         Parent::notifier(Node()).erase(node);
 
   324         nodes.pop_back();
 
   324         _nodes.pop_back();
 
   325       }
 
   325       }
 
   326     }
 
   326     }
 
   327 
   327 
   328   public:
 
   328   public:
 
   329 
   329 
   360       ///Constructor that immediately makes a snapshot
 
   360       ///Constructor that immediately makes a snapshot
 
   361 
   361 
   362       ///This constructor immediately makes a snapshot of the given digraph.
 
   362       ///This constructor immediately makes a snapshot of the given digraph.
 
   363       ///
 
   363       ///
 
   364       Snapshot(SmartDigraph &gr) : _graph(&gr) {
 
   364       Snapshot(SmartDigraph &gr) : _graph(&gr) {
 
   365         node_num=_graph->nodes.size();
 
   365         node_num=_graph->_nodes.size();
 
   366         arc_num=_graph->arcs.size();
 
   366         arc_num=_graph->_arcs.size();
 
   367       }
 
   367       }
 
   368 
   368 
   369       ///Make a snapshot.
 
   369       ///Make a snapshot.
 
   370 
   370 
   371       ///This function makes a snapshot of the given digraph.
 
   371       ///This function makes a snapshot of the given digraph.
 
   372       ///It can be called more than once. In case of a repeated
 
   372       ///It can be called more than once. In case of a repeated
 
   373       ///call, the previous snapshot gets lost.
 
   373       ///call, the previous snapshot gets lost.
 
   374       void save(SmartDigraph &gr) {
 
   374       void save(SmartDigraph &gr) {
 
   375         _graph=&gr;
 
   375         _graph=&gr;
 
   376         node_num=_graph->nodes.size();
 
   376         node_num=_graph->_nodes.size();
 
   377         arc_num=_graph->arcs.size();
 
   377         arc_num=_graph->_arcs.size();
 
   378       }
 
   378       }
 
   379 
   379 
   380       ///Undo the changes until a snapshot.
 
   380       ///Undo the changes until a snapshot.
 
   381 
   381 
   382       ///This function undos the changes until the last snapshot
 
   382       ///This function undos the changes until the last snapshot
 
   400     struct ArcT {
 
   400     struct ArcT {
 
   401       int target;
 
   401       int target;
 
   402       int next_out;
 
   402       int next_out;
 
   403     };
 
   403     };
 
   404 
   404 
   405     std::vector<NodeT> nodes;
 
   405     std::vector<NodeT> _nodes;
 
   406     std::vector<ArcT> arcs;
 
   406     std::vector<ArcT> _arcs;
 
   407 
   407 
   408   public:
 
   408   public:
 
   409 
   409 
   410     typedef SmartGraphBase Graph;
 
   410     typedef SmartGraphBase Graph;
 
   411 
   411 
   463     };
 
   463     };
 
   464 
   464 
   465 
   465 
   466 
   466 
   467     SmartGraphBase()
 
   467     SmartGraphBase()
 
   468       : nodes(), arcs() {}
 
   468       : _nodes(), _arcs() {}
 
   469 
   469 
   470     typedef True NodeNumTag;
 
   470     typedef True NodeNumTag;
 
   471     typedef True EdgeNumTag;
 
   471     typedef True EdgeNumTag;
 
   472     typedef True ArcNumTag;
 
   472     typedef True ArcNumTag;
 
   473 
   473 
   474     int nodeNum() const { return nodes.size(); }
 
   474     int nodeNum() const { return _nodes.size(); }
 
   475     int edgeNum() const { return arcs.size() / 2; }
 
   475     int edgeNum() const { return _arcs.size() / 2; }
 
   476     int arcNum() const { return arcs.size(); }
 
   476     int arcNum() const { return _arcs.size(); }
 
   477 
   477 
   478     int maxNodeId() const { return nodes.size()-1; }
 
   478     int maxNodeId() const { return _nodes.size()-1; }
 
   479     int maxEdgeId() const { return arcs.size() / 2 - 1; }
 
   479     int maxEdgeId() const { return _arcs.size() / 2 - 1; }
 
   480     int maxArcId() const { return arcs.size()-1; }
 
   480     int maxArcId() const { return _arcs.size()-1; }
 
   481 
   481 
   482     Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
 
   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); }
 
   483     Node target(Arc e) const { return Node(_arcs[e._id].target); }
 
   484 
   484 
   485     Node u(Edge e) const { return Node(arcs[2 * e._id].target); }
 
   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); }
 
   486     Node v(Edge e) const { return Node(_arcs[2 * e._id + 1].target); }
 
   487 
   487 
   488     static bool direction(Arc e) {
 
   488     static bool direction(Arc e) {
 
   489       return (e._id & 1) == 1;
 
   489       return (e._id & 1) == 1;
 
   490     }
 
   490     }
 
   491 
   491 
   492     static Arc direct(Edge e, bool d) {
 
   492     static Arc direct(Edge e, bool d) {
 
   493       return Arc(e._id * 2 + (d ? 1 : 0));
 
   493       return Arc(e._id * 2 + (d ? 1 : 0));
 
   494     }
 
   494     }
 
   495 
   495 
   496     void first(Node& node) const {
 
   496     void first(Node& node) const {
 
   497       node._id = nodes.size() - 1;
 
   497       node._id = _nodes.size() - 1;
 
   498     }
 
   498     }
 
   499 
   499 
   500     static void next(Node& node) {
 
   500     static void next(Node& node) {
 
   501       --node._id;
 
   501       --node._id;
 
   502     }
 
   502     }
 
   503 
   503 
   504     void first(Arc& arc) const {
 
   504     void first(Arc& arc) const {
 
   505       arc._id = arcs.size() - 1;
 
   505       arc._id = _arcs.size() - 1;
 
   506     }
 
   506     }
 
   507 
   507 
   508     static void next(Arc& arc) {
 
   508     static void next(Arc& arc) {
 
   509       --arc._id;
 
   509       --arc._id;
 
   510     }
 
   510     }
 
   511 
   511 
   512     void first(Edge& arc) const {
 
   512     void first(Edge& arc) const {
 
   513       arc._id = arcs.size() / 2 - 1;
 
   513       arc._id = _arcs.size() / 2 - 1;
 
   514     }
 
   514     }
 
   515 
   515 
   516     static void next(Edge& arc) {
 
   516     static void next(Edge& arc) {
 
   517       --arc._id;
 
   517       --arc._id;
 
   518     }
 
   518     }
 
   519 
   519 
   520     void firstOut(Arc &arc, const Node& v) const {
 
   520     void firstOut(Arc &arc, const Node& v) const {
 
   521       arc._id = nodes[v._id].first_out;
 
   521       arc._id = _nodes[v._id].first_out;
 
   522     }
 
   522     }
 
   523     void nextOut(Arc &arc) const {
 
   523     void nextOut(Arc &arc) const {
 
   524       arc._id = arcs[arc._id].next_out;
 
   524       arc._id = _arcs[arc._id].next_out;
 
   525     }
 
   525     }
 
   526 
   526 
   527     void firstIn(Arc &arc, const Node& v) const {
 
   527     void firstIn(Arc &arc, const Node& v) const {
 
   528       arc._id = ((nodes[v._id].first_out) ^ 1);
 
   528       arc._id = ((_nodes[v._id].first_out) ^ 1);
 
   529       if (arc._id == -2) arc._id = -1;
 
   529       if (arc._id == -2) arc._id = -1;
 
   530     }
 
   530     }
 
   531     void nextIn(Arc &arc) const {
 
   531     void nextIn(Arc &arc) const {
 
   532       arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
 
   532       arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1);
 
   533       if (arc._id == -2) arc._id = -1;
 
   533       if (arc._id == -2) arc._id = -1;
 
   534     }
 
   534     }
 
   535 
   535 
   536     void firstInc(Edge &arc, bool& d, const Node& v) const {
 
   536     void firstInc(Edge &arc, bool& d, const Node& v) const {
 
   537       int de = nodes[v._id].first_out;
 
   537       int de = _nodes[v._id].first_out;
 
   538       if (de != -1) {
 
   538       if (de != -1) {
 
   539         arc._id = de / 2;
 
   539         arc._id = de / 2;
 
   540         d = ((de & 1) == 1);
 
   540         d = ((de & 1) == 1);
 
   541       } else {
 
   541       } else {
 
   542         arc._id = -1;
 
   542         arc._id = -1;
 
   543         d = true;
 
   543         d = true;
 
   544       }
 
   544       }
 
   545     }
 
   545     }
 
   546     void nextInc(Edge &arc, bool& d) const {
 
   546     void nextInc(Edge &arc, bool& d) const {
 
   547       int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
 
   547       int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
 
   548       if (de != -1) {
 
   548       if (de != -1) {
 
   549         arc._id = de / 2;
 
   549         arc._id = de / 2;
 
   550         d = ((de & 1) == 1);
 
   550         d = ((de & 1) == 1);
 
   551       } else {
 
   551       } else {
 
   552         arc._id = -1;
 
   552         arc._id = -1;
 
   561     static Node nodeFromId(int id) { return Node(id);}
 
   561     static Node nodeFromId(int id) { return Node(id);}
 
   562     static Arc arcFromId(int id) { return Arc(id);}
 
   562     static Arc arcFromId(int id) { return Arc(id);}
 
   563     static Edge edgeFromId(int id) { return Edge(id);}
 
   563     static Edge edgeFromId(int id) { return Edge(id);}
 
   564 
   564 
   565     bool valid(Node n) const {
 
   565     bool valid(Node n) const {
 
   566       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
 
   566       return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
 
   567     }
 
   567     }
 
   568     bool valid(Arc a) const {
 
   568     bool valid(Arc a) const {
 
   569       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
 
   569       return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
 
   570     }
 
   570     }
 
   571     bool valid(Edge e) const {
 
   571     bool valid(Edge e) const {
 
   572       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
 
   572       return e._id >= 0 && 2 * e._id < static_cast<int>(_arcs.size());
 
   573     }
 
   573     }
 
   574 
   574 
   575     Node addNode() {
 
   575     Node addNode() {
 
   576       int n = nodes.size();
 
   576       int n = _nodes.size();
 
   577       nodes.push_back(NodeT());
 
   577       _nodes.push_back(NodeT());
 
   578       nodes[n].first_out = -1;
 
   578       _nodes[n].first_out = -1;
 
   579 
   579 
   580       return Node(n);
 
   580       return Node(n);
 
   581     }
 
   581     }
 
   582 
   582 
   583     Edge addEdge(Node u, Node v) {
 
   583     Edge addEdge(Node u, Node v) {
 
   584       int n = arcs.size();
 
   584       int n = _arcs.size();
 
   585       arcs.push_back(ArcT());
 
   585       _arcs.push_back(ArcT());
 
   586       arcs.push_back(ArcT());
 
   586       _arcs.push_back(ArcT());
 
   587 
   587 
   588       arcs[n].target = u._id;
 
   588       _arcs[n].target = u._id;
 
   589       arcs[n | 1].target = v._id;
 
   589       _arcs[n | 1].target = v._id;
 
   590 
   590 
   591       arcs[n].next_out = nodes[v._id].first_out;
 
   591       _arcs[n].next_out = _nodes[v._id].first_out;
 
   592       nodes[v._id].first_out = n;
 
   592       _nodes[v._id].first_out = n;
 
   593 
   593 
   594       arcs[n | 1].next_out = nodes[u._id].first_out;
 
   594       _arcs[n | 1].next_out = _nodes[u._id].first_out;
 
   595       nodes[u._id].first_out = (n | 1);
 
   595       _nodes[u._id].first_out = (n | 1);
 
   596 
   596 
   597       return Edge(n / 2);
 
   597       return Edge(n / 2);
 
   598     }
 
   598     }
 
   599 
   599 
   600     void clear() {
 
   600     void clear() {
 
   601       arcs.clear();
 
   601       _arcs.clear();
 
   602       nodes.clear();
 
   602       _nodes.clear();
 
   603     }
 
   603     }
 
   604 
   604 
   605   };
 
   605   };
 
   606 
   606 
   607   typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
 
   607   typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
 
   699     /// allocation: if you know that the graph you want to build will
 
   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),
 
   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
 
   701     /// then it is worth reserving space for this amount before starting
 
   702     /// to build the graph.
 
   702     /// to build the graph.
 
   703     /// \sa reserveEdge()
 
   703     /// \sa reserveEdge()
 
   704     void reserveNode(int n) { nodes.reserve(n); };
 
   704     void reserveNode(int n) { _nodes.reserve(n); };
 
   705 
   705 
   706     /// Reserve memory for edges.
 
   706     /// Reserve memory for edges.
 
   707 
   707 
   708     /// Using this function, it is possible to avoid superfluous memory
 
   708     /// Using this function, it is possible to avoid superfluous memory
 
   709     /// allocation: if you know that the graph you want to build will
 
   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),
 
   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
 
   711     /// then it is worth reserving space for this amount before starting
 
   712     /// to build the graph.
 
   712     /// to build the graph.
 
   713     /// \sa reserveNode()
 
   713     /// \sa reserveNode()
 
   714     void reserveEdge(int m) { arcs.reserve(2 * m); };
 
   714     void reserveEdge(int m) { _arcs.reserve(2 * m); };
 
   715 
   715 
   716   public:
 
   716   public:
 
   717 
   717 
   718     class Snapshot;
 
   718     class Snapshot;
 
   719 
   719 
   720   protected:
 
   720   protected:
 
   721 
   721 
   722     void saveSnapshot(Snapshot &s)
 
   722     void saveSnapshot(Snapshot &s)
 
   723     {
 
   723     {
 
   724       s._graph = this;
 
   724       s._graph = this;
 
   725       s.node_num = nodes.size();
 
   725       s.node_num = _nodes.size();
 
   726       s.arc_num = arcs.size();
 
   726       s.arc_num = _arcs.size();
 
   727     }
 
   727     }
 
   728 
   728 
   729     void restoreSnapshot(const Snapshot &s)
 
   729     void restoreSnapshot(const Snapshot &s)
 
   730     {
 
   730     {
 
   731       while(s.arc_num<arcs.size()) {
 
   731       while(s.arc_num<_arcs.size()) {
 
   732         int n=arcs.size()-1;
 
   732         int n=_arcs.size()-1;
 
   733         Edge arc=edgeFromId(n/2);
 
   733         Edge arc=edgeFromId(n/2);
 
   734         Parent::notifier(Edge()).erase(arc);
 
   734         Parent::notifier(Edge()).erase(arc);
 
   735         std::vector<Arc> dir;
 
   735         std::vector<Arc> dir;
 
   736         dir.push_back(arcFromId(n));
 
   736         dir.push_back(arcFromId(n));
 
   737         dir.push_back(arcFromId(n-1));
 
   737         dir.push_back(arcFromId(n-1));
 
   738         Parent::notifier(Arc()).erase(dir);
 
   738         Parent::notifier(Arc()).erase(dir);
 
   739         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
 
   739         _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out;
 
   740         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
 
   740         _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out;
 
   741         arcs.pop_back();
 
   741         _arcs.pop_back();
 
   742         arcs.pop_back();
 
   742         _arcs.pop_back();
 
   743       }
 
   743       }
 
   744       while(s.node_num<nodes.size()) {
 
   744       while(s.node_num<_nodes.size()) {
 
   745         int n=nodes.size()-1;
 
   745         int n=_nodes.size()-1;
 
   746         Node node = nodeFromId(n);
 
   746         Node node = nodeFromId(n);
 
   747         Parent::notifier(Node()).erase(node);
 
   747         Parent::notifier(Node()).erase(node);
 
   748         nodes.pop_back();
 
   748         _nodes.pop_back();
 
   749       }
 
   749       }
 
   750     }
 
   750     }
 
   751 
   751 
   752   public:
 
   752   public:
 
   753 
   753 
   823     struct ArcT {
 
   823     struct ArcT {
 
   824       int target;
 
   824       int target;
 
   825       int next_out;
 
   825       int next_out;
 
   826     };
 
   826     };
 
   827 
   827 
   828     std::vector<NodeT> nodes;
 
   828     std::vector<NodeT> _nodes;
 
   829     std::vector<ArcT> arcs;
 
   829     std::vector<ArcT> _arcs;
 
   830 
   830 
   831     int first_red, first_blue;
 
   831     int first_red, first_blue;
 
   832     int max_red, max_blue;
 
   832     int max_red, max_blue;
 
   833 
   833 
   834   public:
 
   834   public:
 
   913     };
 
   913     };
 
   914 
   914 
   915 
   915 
   916 
   916 
   917     SmartBpGraphBase()
 
   917     SmartBpGraphBase()
 
   918       : nodes(), arcs(), first_red(-1), first_blue(-1),
 
   918       : _nodes(), _arcs(), first_red(-1), first_blue(-1),
 
   919         max_red(-1), max_blue(-1) {}
 
   919         max_red(-1), max_blue(-1) {}
 
   920 
   920 
   921     typedef True NodeNumTag;
 
   921     typedef True NodeNumTag;
 
   922     typedef True EdgeNumTag;
 
   922     typedef True EdgeNumTag;
 
   923     typedef True ArcNumTag;
 
   923     typedef True ArcNumTag;
 
   924 
   924 
   925     int nodeNum() const { return nodes.size(); }
 
   925     int nodeNum() const { return _nodes.size(); }
 
   926     int redNum() const { return max_red + 1; }
 
   926     int redNum() const { return max_red + 1; }
 
   927     int blueNum() const { return max_blue + 1; }
 
   927     int blueNum() const { return max_blue + 1; }
 
   928     int edgeNum() const { return arcs.size() / 2; }
 
   928     int edgeNum() const { return _arcs.size() / 2; }
 
   929     int arcNum() const { return arcs.size(); }
 
   929     int arcNum() const { return _arcs.size(); }
 
   930 
   930 
   931     int maxNodeId() const { return nodes.size()-1; }
 
   931     int maxNodeId() const { return _nodes.size()-1; }
 
   932     int maxRedId() const { return max_red; }
 
   932     int maxRedId() const { return max_red; }
 
   933     int maxBlueId() const { return max_blue; }
 
   933     int maxBlueId() const { return max_blue; }
 
   934     int maxEdgeId() const { return arcs.size() / 2 - 1; }
 
   934     int maxEdgeId() const { return _arcs.size() / 2 - 1; }
 
   935     int maxArcId() const { return arcs.size()-1; }
 
   935     int maxArcId() const { return _arcs.size()-1; }
 
   936 
   936 
   937     bool red(Node n) const { return nodes[n._id].red; }
 
   937     bool red(Node n) const { return _nodes[n._id].red; }
 
   938     bool blue(Node n) const { return !nodes[n._id].red; }
 
   938     bool blue(Node n) const { return !_nodes[n._id].red; }
 
   939 
   939 
   940     static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
 
   940     static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
 
   941     static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
 
   941     static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
 
   942 
   942 
   943     Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
 
   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); }
 
   944     Node target(Arc a) const { return Node(_arcs[a._id].target); }
 
   945 
   945 
   946     RedNode redNode(Edge e) const {
 
   946     RedNode redNode(Edge e) const {
 
   947       return RedNode(arcs[2 * e._id].target);
 
   947       return RedNode(_arcs[2 * e._id].target);
 
   948     }
 
   948     }
 
   949     BlueNode blueNode(Edge e) const {
 
   949     BlueNode blueNode(Edge e) const {
 
   950       return BlueNode(arcs[2 * e._id + 1].target);
 
   950       return BlueNode(_arcs[2 * e._id + 1].target);
 
   951     }
 
   951     }
 
   952 
   952 
   953     static bool direction(Arc a) {
 
   953     static bool direction(Arc a) {
 
   954       return (a._id & 1) == 1;
 
   954       return (a._id & 1) == 1;
 
   955     }
 
   955     }
 
   957     static Arc direct(Edge e, bool d) {
 
   957     static Arc direct(Edge e, bool d) {
 
   958       return Arc(e._id * 2 + (d ? 1 : 0));
 
   958       return Arc(e._id * 2 + (d ? 1 : 0));
 
   959     }
 
   959     }
 
   960 
   960 
   961     void first(Node& node) const {
 
   961     void first(Node& node) const {
 
   962       node._id = nodes.size() - 1;
 
   962       node._id = _nodes.size() - 1;
 
   963     }
 
   963     }
 
   964 
   964 
   965     static void next(Node& node) {
 
   965     static void next(Node& node) {
 
   966       --node._id;
 
   966       --node._id;
 
   967     }
 
   967     }
 
   969     void first(RedNode& node) const {
 
   969     void first(RedNode& node) const {
 
   970       node._id = first_red;
 
   970       node._id = first_red;
 
   971     }
 
   971     }
 
   972 
   972 
   973     void next(RedNode& node) const {
 
   973     void next(RedNode& node) const {
 
   974       node._id = nodes[node._id].partition_next;
 
   974       node._id = _nodes[node._id].partition_next;
 
   975     }
 
   975     }
 
   976 
   976 
   977     void first(BlueNode& node) const {
 
   977     void first(BlueNode& node) const {
 
   978       node._id = first_blue;
 
   978       node._id = first_blue;
 
   979     }
 
   979     }
 
   980 
   980 
   981     void next(BlueNode& node) const {
 
   981     void next(BlueNode& node) const {
 
   982       node._id = nodes[node._id].partition_next;
 
   982       node._id = _nodes[node._id].partition_next;
 
   983     }
 
   983     }
 
   984 
   984 
   985     void first(Arc& arc) const {
 
   985     void first(Arc& arc) const {
 
   986       arc._id = arcs.size() - 1;
 
   986       arc._id = _arcs.size() - 1;
 
   987     }
 
   987     }
 
   988 
   988 
   989     static void next(Arc& arc) {
 
   989     static void next(Arc& arc) {
 
   990       --arc._id;
 
   990       --arc._id;
 
   991     }
 
   991     }
 
   992 
   992 
   993     void first(Edge& arc) const {
 
   993     void first(Edge& arc) const {
 
   994       arc._id = arcs.size() / 2 - 1;
 
   994       arc._id = _arcs.size() / 2 - 1;
 
   995     }
 
   995     }
 
   996 
   996 
   997     static void next(Edge& arc) {
 
   997     static void next(Edge& arc) {
 
   998       --arc._id;
 
   998       --arc._id;
 
   999     }
 
   999     }
 
  1000 
  1000 
  1001     void firstOut(Arc &arc, const Node& v) const {
 
  1001     void firstOut(Arc &arc, const Node& v) const {
 
  1002       arc._id = nodes[v._id].first_out;
 
  1002       arc._id = _nodes[v._id].first_out;
 
  1003     }
 
  1003     }
 
  1004     void nextOut(Arc &arc) const {
 
  1004     void nextOut(Arc &arc) const {
 
  1005       arc._id = arcs[arc._id].next_out;
 
  1005       arc._id = _arcs[arc._id].next_out;
 
  1006     }
 
  1006     }
 
  1007 
  1007 
  1008     void firstIn(Arc &arc, const Node& v) const {
 
  1008     void firstIn(Arc &arc, const Node& v) const {
 
  1009       arc._id = ((nodes[v._id].first_out) ^ 1);
 
  1009       arc._id = ((_nodes[v._id].first_out) ^ 1);
 
  1010       if (arc._id == -2) arc._id = -1;
 
  1010       if (arc._id == -2) arc._id = -1;
 
  1011     }
 
  1011     }
 
  1012     void nextIn(Arc &arc) const {
 
  1012     void nextIn(Arc &arc) const {
 
  1013       arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
 
  1013       arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1);
 
  1014       if (arc._id == -2) arc._id = -1;
 
  1014       if (arc._id == -2) arc._id = -1;
 
  1015     }
 
  1015     }
 
  1016 
  1016 
  1017     void firstInc(Edge &arc, bool& d, const Node& v) const {
 
  1017     void firstInc(Edge &arc, bool& d, const Node& v) const {
 
  1018       int de = nodes[v._id].first_out;
 
  1018       int de = _nodes[v._id].first_out;
 
  1019       if (de != -1) {
 
  1019       if (de != -1) {
 
  1020         arc._id = de / 2;
 
  1020         arc._id = de / 2;
 
  1021         d = ((de & 1) == 1);
 
  1021         d = ((de & 1) == 1);
 
  1022       } else {
 
  1022       } else {
 
  1023         arc._id = -1;
 
  1023         arc._id = -1;
 
  1024         d = true;
 
  1024         d = true;
 
  1025       }
 
  1025       }
 
  1026     }
 
  1026     }
 
  1027     void nextInc(Edge &arc, bool& d) const {
 
  1027     void nextInc(Edge &arc, bool& d) const {
 
  1028       int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
 
  1028       int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
 
  1029       if (de != -1) {
 
  1029       if (de != -1) {
 
  1030         arc._id = de / 2;
 
  1030         arc._id = de / 2;
 
  1031         d = ((de & 1) == 1);
 
  1031         d = ((de & 1) == 1);
 
  1032       } else {
 
  1032       } else {
 
  1033         arc._id = -1;
 
  1033         arc._id = -1;
 
  1034         d = true;
 
  1034         d = true;
 
  1035       }
 
  1035       }
 
  1036     }
 
  1036     }
 
  1037 
  1037 
  1038     static int id(Node v) { return v._id; }
 
  1038     static int id(Node v) { return v._id; }
 
  1039     int id(RedNode v) const { return nodes[v._id].partition_index; }
 
  1039     int id(RedNode v) const { return _nodes[v._id].partition_index; }
 
  1040     int id(BlueNode 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; }
 
  1041     static int id(Arc e) { return e._id; }
 
  1042     static int id(Edge e) { return e._id; }
 
  1042     static int id(Edge e) { return e._id; }
 
  1043 
  1043 
  1044     static Node nodeFromId(int id) { return Node(id);}
 
  1044     static Node nodeFromId(int id) { return Node(id);}
 
  1045     static Arc arcFromId(int id) { return Arc(id);}
 
  1045     static Arc arcFromId(int id) { return Arc(id);}
 
  1046     static Edge edgeFromId(int id) { return Edge(id);}
 
  1046     static Edge edgeFromId(int id) { return Edge(id);}
 
  1047 
  1047 
  1048     bool valid(Node n) const {
 
  1048     bool valid(Node n) const {
 
  1049       return n._id >= 0 && n._id < static_cast<int>(nodes.size());
 
  1049       return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
 
  1050     }
 
  1050     }
 
  1051     bool valid(Arc a) const {
 
  1051     bool valid(Arc a) const {
 
  1052       return a._id >= 0 && a._id < static_cast<int>(arcs.size());
 
  1052       return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
 
  1053     }
 
  1053     }
 
  1054     bool valid(Edge e) const {
 
  1054     bool valid(Edge e) const {
 
  1055       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
 
  1055       return e._id >= 0 && 2 * e._id < static_cast<int>(_arcs.size());
 
  1056     }
 
  1056     }
 
  1057 
  1057 
  1058     RedNode addRedNode() {
 
  1058     RedNode addRedNode() {
 
  1059       int n = nodes.size();
 
  1059       int n = _nodes.size();
 
  1060       nodes.push_back(NodeT());
 
  1060       _nodes.push_back(NodeT());
 
  1061       nodes[n].first_out = -1;
 
  1061       _nodes[n].first_out = -1;
 
  1062       nodes[n].red = true;
 
  1062       _nodes[n].red = true;
 
  1063       nodes[n].partition_index = ++max_red;
 
  1063       _nodes[n].partition_index = ++max_red;
 
  1064       nodes[n].partition_next = first_red;
 
  1064       _nodes[n].partition_next = first_red;
 
  1065       first_red = n;
 
  1065       first_red = n;
 
  1066 
  1066 
  1067       return RedNode(n);
 
  1067       return RedNode(n);
 
  1068     }
 
  1068     }
 
  1069 
  1069 
  1070     BlueNode addBlueNode() {
 
  1070     BlueNode addBlueNode() {
 
  1071       int n = nodes.size();
 
  1071       int n = _nodes.size();
 
  1072       nodes.push_back(NodeT());
 
  1072       _nodes.push_back(NodeT());
 
  1073       nodes[n].first_out = -1;
 
  1073       _nodes[n].first_out = -1;
 
  1074       nodes[n].red = false;
 
  1074       _nodes[n].red = false;
 
  1075       nodes[n].partition_index = ++max_blue;
 
  1075       _nodes[n].partition_index = ++max_blue;
 
  1076       nodes[n].partition_next = first_blue;
 
  1076       _nodes[n].partition_next = first_blue;
 
  1077       first_blue = n;
 
  1077       first_blue = n;
 
  1078 
  1078 
  1079       return BlueNode(n);
 
  1079       return BlueNode(n);
 
  1080     }
 
  1080     }
 
  1081 
  1081 
  1082     Edge addEdge(RedNode u, BlueNode v) {
 
  1082     Edge addEdge(RedNode u, BlueNode v) {
 
  1083       int n = arcs.size();
 
  1083       int n = _arcs.size();
 
  1084       arcs.push_back(ArcT());
 
  1084       _arcs.push_back(ArcT());
 
  1085       arcs.push_back(ArcT());
 
  1085       _arcs.push_back(ArcT());
 
  1086 
  1086 
  1087       arcs[n].target = u._id;
 
  1087       _arcs[n].target = u._id;
 
  1088       arcs[n | 1].target = v._id;
 
  1088       _arcs[n | 1].target = v._id;
 
  1089 
  1089 
  1090       arcs[n].next_out = nodes[v._id].first_out;
 
  1090       _arcs[n].next_out = _nodes[v._id].first_out;
 
  1091       nodes[v._id].first_out = n;
 
  1091       _nodes[v._id].first_out = n;
 
  1092 
  1092 
  1093       arcs[n | 1].next_out = nodes[u._id].first_out;
 
  1093       _arcs[n | 1].next_out = _nodes[u._id].first_out;
 
  1094       nodes[u._id].first_out = (n | 1);
 
  1094       _nodes[u._id].first_out = (n | 1);
 
  1095 
  1095 
  1096       return Edge(n / 2);
 
  1096       return Edge(n / 2);
 
  1097     }
 
  1097     }
 
  1098 
  1098 
  1099     void clear() {
 
  1099     void clear() {
 
  1100       arcs.clear();
 
  1100       _arcs.clear();
 
  1101       nodes.clear();
 
  1101       _nodes.clear();
 
  1102       first_red = -1;
 
  1102       first_red = -1;
 
  1103       first_blue = -1;
 
  1103       first_blue = -1;
 
  1104       max_blue = -1;
 
  1104       max_blue = -1;
 
  1105       max_red = -1;
 
  1105       max_red = -1;
 
  1106     }
 
  1106     }
 
  1211     /// allocation: if you know that the graph you want to build will
 
  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),
 
  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
 
  1213     /// then it is worth reserving space for this amount before starting
 
  1214     /// to build the graph.
 
  1214     /// to build the graph.
 
  1215     /// \sa reserveEdge()
 
  1215     /// \sa reserveEdge()
 
  1216     void reserveNode(int n) { nodes.reserve(n); };
 
  1216     void reserveNode(int n) { _nodes.reserve(n); };
 
  1217 
  1217 
  1218     /// Reserve memory for edges.
 
  1218     /// Reserve memory for edges.
 
  1219 
  1219 
  1220     /// Using this function, it is possible to avoid superfluous memory
 
  1220     /// Using this function, it is possible to avoid superfluous memory
 
  1221     /// allocation: if you know that the graph you want to build will
 
  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),
 
  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
 
  1223     /// then it is worth reserving space for this amount before starting
 
  1224     /// to build the graph.
 
  1224     /// to build the graph.
 
  1225     /// \sa reserveNode()
 
  1225     /// \sa reserveNode()
 
  1226     void reserveEdge(int m) { arcs.reserve(2 * m); };
 
  1226     void reserveEdge(int m) { _arcs.reserve(2 * m); };
 
  1227 
  1227 
  1228   public:
 
  1228   public:
 
  1229 
  1229 
  1230     class Snapshot;
 
  1230     class Snapshot;
 
  1231 
  1231 
  1232   protected:
 
  1232   protected:
 
  1233 
  1233 
  1234     void saveSnapshot(Snapshot &s)
 
  1234     void saveSnapshot(Snapshot &s)
 
  1235     {
 
  1235     {
 
  1236       s._graph = this;
 
  1236       s._graph = this;
 
  1237       s.node_num = nodes.size();
 
  1237       s.node_num = _nodes.size();
 
  1238       s.arc_num = arcs.size();
 
  1238       s.arc_num = _arcs.size();
 
  1239     }
 
  1239     }
 
  1240 
  1240 
  1241     void restoreSnapshot(const Snapshot &s)
 
  1241     void restoreSnapshot(const Snapshot &s)
 
  1242     {
 
  1242     {
 
  1243       while(s.arc_num<arcs.size()) {
 
  1243       while(s.arc_num<_arcs.size()) {
 
  1244         int n=arcs.size()-1;
 
  1244         int n=_arcs.size()-1;
 
  1245         Edge arc=edgeFromId(n/2);
 
  1245         Edge arc=edgeFromId(n/2);
 
  1246         Parent::notifier(Edge()).erase(arc);
 
  1246         Parent::notifier(Edge()).erase(arc);
 
  1247         std::vector<Arc> dir;
 
  1247         std::vector<Arc> dir;
 
  1248         dir.push_back(arcFromId(n));
 
  1248         dir.push_back(arcFromId(n));
 
  1249         dir.push_back(arcFromId(n-1));
 
  1249         dir.push_back(arcFromId(n-1));
 
  1250         Parent::notifier(Arc()).erase(dir);
 
  1250         Parent::notifier(Arc()).erase(dir);
 
  1251         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
 
  1251         _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out;
 
  1252         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
 
  1252         _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out;
 
  1253         arcs.pop_back();
 
  1253         _arcs.pop_back();
 
  1254         arcs.pop_back();
 
  1254         _arcs.pop_back();
 
  1255       }
 
  1255       }
 
  1256       while(s.node_num<nodes.size()) {
 
  1256       while(s.node_num<_nodes.size()) {
 
  1257         int n=nodes.size()-1;
 
  1257         int n=_nodes.size()-1;
 
  1258         Node node = nodeFromId(n);
 
  1258         Node node = nodeFromId(n);
 
  1259         if (Parent::red(node)) {
 
  1259         if (Parent::red(node)) {
 
  1260           first_red = nodes[n].partition_next;
 
  1260           first_red = _nodes[n].partition_next;
 
  1261           if (first_red != -1) {
 
  1261           if (first_red != -1) {
 
  1262             max_red = nodes[first_red].partition_index;
 
  1262             max_red = _nodes[first_red].partition_index;
 
  1263           } else {
 
  1263           } else {
 
  1264             max_red = -1;
 
  1264             max_red = -1;
 
  1265           }
 
  1265           }
 
  1266           Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
 
  1266           Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
 
  1267         } else {
 
  1267         } else {
 
  1268           first_blue = nodes[n].partition_next;
 
  1268           first_blue = _nodes[n].partition_next;
 
  1269           if (first_blue != -1) {
 
  1269           if (first_blue != -1) {
 
  1270             max_blue = nodes[first_blue].partition_index;
 
  1270             max_blue = _nodes[first_blue].partition_index;
 
  1271           } else {
 
  1271           } else {
 
  1272             max_blue = -1;
 
  1272             max_blue = -1;
 
  1273           }
 
  1273           }
 
  1274           Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
 
  1274           Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
 
  1275         }
 
  1275         }
 
  1276         Parent::notifier(Node()).erase(node);
 
  1276         Parent::notifier(Node()).erase(node);
 
  1277         nodes.pop_back();
 
  1277         _nodes.pop_back();
 
  1278       }
 
  1278       }
 
  1279     }
 
  1279     }
 
  1280 
  1280 
  1281   public:
 
  1281   public:
 
  1282 
  1282
lemon