COIN-OR::LEMON - Graph Library

Changeset 1359:3ec484b11733 in lemon


Ignore:
Timestamp:
05/22/15 17:53:08 (9 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1354:1de908281369 (diff), 1357:2126945deb6a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge bugfix #598

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r1337 r1359  
    583583        }
    584584        virtual void add(const std::vector<Node>& nodes) {
    585           for (int i = nodes.size() - 1; i >= 0; ++i) {
     585          for (int i = nodes.size() - 1; i >= 0; --i) {
    586586            snapshot.addNode(nodes[i]);
    587587          }
     
    633633        }
    634634        virtual void add(const std::vector<Arc>& arcs) {
    635           for (int i = arcs.size() - 1; i >= 0; ++i) {
     635          for (int i = arcs.size() - 1; i >= 0; --i) {
    636636            snapshot.addArc(arcs[i]);
    637637          }
     
    13951395        }
    13961396        virtual void add(const std::vector<Node>& nodes) {
    1397           for (int i = nodes.size() - 1; i >= 0; ++i) {
     1397          for (int i = nodes.size() - 1; i >= 0; --i) {
    13981398            snapshot.addNode(nodes[i]);
    13991399          }
     
    14451445        }
    14461446        virtual void add(const std::vector<Edge>& edges) {
    1447           for (int i = edges.size() - 1; i >= 0; ++i) {
     1447          for (int i = edges.size() - 1; i >= 0; --i) {
    14481448            snapshot.addEdge(edges[i]);
    14491449          }
     
    23002300        }
    23012301        virtual void add(const std::vector<Node>& nodes) {
    2302           for (int i = nodes.size() - 1; i >= 0; ++i) {
     2302          for (int i = nodes.size() - 1; i >= 0; --i) {
    23032303            snapshot.addNode(nodes[i]);
    23042304          }
     
    23502350        }
    23512351        virtual void add(const std::vector<Edge>& edges) {
    2352           for (int i = edges.size() - 1; i >= 0; ++i) {
     2352          for (int i = edges.size() - 1; i >= 0; --i) {
    23532353            snapshot.addEdge(edges[i]);
    23542354          }
  • lemon/list_graph.h

    r1357 r1359  
    4949    };
    5050
    51     std::vector<NodeT> nodes;
     51    std::vector<NodeT> _nodes;
    5252
    5353    int first_node;
     
    5555    int first_free_node;
    5656
    57     std::vector<ArcT> arcs;
     57    std::vector<ArcT> _arcs;
    5858
    5959    int first_free_arc;
     
    9898
    9999    ListDigraphBase()
    100       : nodes(), first_node(-1),
    101         first_free_node(-1), arcs(), first_free_arc(-1) {}
    102 
    103 
    104     int maxNodeId() const { return nodes.size()-1; }
    105     int maxArcId() const { return arcs.size()-1; }
    106 
    107     Node source(Arc e) const { return Node(arcs[e.id].source); }
    108     Node target(Arc e) const { return Node(arcs[e.id].target); }
     100      : _nodes(), first_node(-1),
     101        first_free_node(-1), _arcs(), first_free_arc(-1) {}
     102
     103
     104    int maxNodeId() const { return _nodes.size()-1; }
     105    int maxArcId() const { return _arcs.size()-1; }
     106
     107    Node source(Arc e) const { return Node(_arcs[e.id].source); }
     108    Node target(Arc e) const { return Node(_arcs[e.id].target); }
    109109
    110110
     
    114114
    115115    void next(Node& node) const {
    116       node.id = nodes[node.id].next;
     116      node.id = _nodes[node.id].next;
    117117    }
    118118
     
    121121      int n;
    122122      for(n = first_node;
    123           n != -1 && nodes[n].first_out == -1;
    124           n = nodes[n].next) {}
    125       arc.id = (n == -1) ? -1 : nodes[n].first_out;
     123          n != -1 && _nodes[n].first_out == -1;
     124          n = _nodes[n].next) {}
     125      arc.id = (n == -1) ? -1 : _nodes[n].first_out;
    126126    }
    127127
    128128    void next(Arc& arc) const {
    129       if (arcs[arc.id].next_out != -1) {
    130         arc.id = arcs[arc.id].next_out;
     129      if (_arcs[arc.id].next_out != -1) {
     130        arc.id = _arcs[arc.id].next_out;
    131131      } else {
    132132        int n;
    133         for(n = nodes[arcs[arc.id].source].next;
    134             n != -1 && nodes[n].first_out == -1;
    135             n = nodes[n].next) {}
    136         arc.id = (n == -1) ? -1 : nodes[n].first_out;
     133        for(n = _nodes[_arcs[arc.id].source].next;
     134            n != -1 && _nodes[n].first_out == -1;
     135            n = _nodes[n].next) {}
     136        arc.id = (n == -1) ? -1 : _nodes[n].first_out;
    137137      }
    138138    }
    139139
    140140    void firstOut(Arc &e, const Node& v) const {
    141       e.id = nodes[v.id].first_out;
     141      e.id = _nodes[v.id].first_out;
    142142    }
    143143    void nextOut(Arc &e) const {
    144       e.id=arcs[e.id].next_out;
     144      e.id=_arcs[e.id].next_out;
    145145    }
    146146
    147147    void firstIn(Arc &e, const Node& v) const {
    148       e.id = nodes[v.id].first_in;
     148      e.id = _nodes[v.id].first_in;
    149149    }
    150150    void nextIn(Arc &e) const {
    151       e.id=arcs[e.id].next_in;
     151      e.id=_arcs[e.id].next_in;
    152152    }
    153153
     
    160160
    161161    bool valid(Node n) const {
    162       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
    163         nodes[n.id].prev != -2;
     162      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
     163        _nodes[n.id].prev != -2;
    164164    }
    165165
    166166    bool valid(Arc a) const {
    167       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
    168         arcs[a.id].prev_in != -2;
     167      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
     168        _arcs[a.id].prev_in != -2;
    169169    }
    170170
     
    173173
    174174      if(first_free_node==-1) {
    175         n = nodes.size();
    176         nodes.push_back(NodeT());
     175        n = _nodes.size();
     176        _nodes.push_back(NodeT());
    177177      } else {
    178178        n = first_free_node;
    179         first_free_node = nodes[n].next;
    180       }
    181 
    182       nodes[n].next = first_node;
    183       if(first_node != -1) nodes[first_node].prev = n;
     179        first_free_node = _nodes[n].next;
     180      }
     181
     182      _nodes[n].next = first_node;
     183      if(first_node != -1) _nodes[first_node].prev = n;
    184184      first_node = n;
    185       nodes[n].prev = -1;
    186 
    187       nodes[n].first_in = nodes[n].first_out = -1;
     185      _nodes[n].prev = -1;
     186
     187      _nodes[n].first_in = _nodes[n].first_out = -1;
    188188
    189189      return Node(n);
     
    194194
    195195      if (first_free_arc == -1) {
    196         n = arcs.size();
    197         arcs.push_back(ArcT());
     196        n = _arcs.size();
     197        _arcs.push_back(ArcT());
    198198      } else {
    199199        n = first_free_arc;
    200         first_free_arc = arcs[n].next_in;
    201       }
    202 
    203       arcs[n].source = u.id;
    204       arcs[n].target = v.id;
    205 
    206       arcs[n].next_out = nodes[u.id].first_out;
    207       if(nodes[u.id].first_out != -1) {
    208         arcs[nodes[u.id].first_out].prev_out = n;
    209       }
    210 
    211       arcs[n].next_in = nodes[v.id].first_in;
    212       if(nodes[v.id].first_in != -1) {
    213         arcs[nodes[v.id].first_in].prev_in = n;
    214       }
    215 
    216       arcs[n].prev_in = arcs[n].prev_out = -1;
    217 
    218       nodes[u.id].first_out = nodes[v.id].first_in = n;
     200        first_free_arc = _arcs[n].next_in;
     201      }
     202
     203      _arcs[n].source = u.id;
     204      _arcs[n].target = v.id;
     205
     206      _arcs[n].next_out = _nodes[u.id].first_out;
     207      if(_nodes[u.id].first_out != -1) {
     208        _arcs[_nodes[u.id].first_out].prev_out = n;
     209      }
     210
     211      _arcs[n].next_in = _nodes[v.id].first_in;
     212      if(_nodes[v.id].first_in != -1) {
     213        _arcs[_nodes[v.id].first_in].prev_in = n;
     214      }
     215
     216      _arcs[n].prev_in = _arcs[n].prev_out = -1;
     217
     218      _nodes[u.id].first_out = _nodes[v.id].first_in = n;
    219219
    220220      return Arc(n);
     
    224224      int n = node.id;
    225225
    226       if(nodes[n].next != -1) {
    227         nodes[nodes[n].next].prev = nodes[n].prev;
    228       }
    229 
    230       if(nodes[n].prev != -1) {
    231         nodes[nodes[n].prev].next = nodes[n].next;
    232       } else {
    233         first_node = nodes[n].next;
    234       }
    235 
    236       nodes[n].next = first_free_node;
     226      if(_nodes[n].next != -1) {
     227        _nodes[_nodes[n].next].prev = _nodes[n].prev;
     228      }
     229
     230      if(_nodes[n].prev != -1) {
     231        _nodes[_nodes[n].prev].next = _nodes[n].next;
     232      } else {
     233        first_node = _nodes[n].next;
     234      }
     235
     236      _nodes[n].next = first_free_node;
    237237      first_free_node = n;
    238       nodes[n].prev = -2;
     238      _nodes[n].prev = -2;
    239239
    240240    }
     
    243243      int n = arc.id;
    244244
    245       if(arcs[n].next_in!=-1) {
    246         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
    247       }
    248 
    249       if(arcs[n].prev_in!=-1) {
    250         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
    251       } else {
    252         nodes[arcs[n].target].first_in = arcs[n].next_in;
    253       }
    254 
    255 
    256       if(arcs[n].next_out!=-1) {
    257         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    258       }
    259 
    260       if(arcs[n].prev_out!=-1) {
    261         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    262       } else {
    263         nodes[arcs[n].source].first_out = arcs[n].next_out;
    264       }
    265 
    266       arcs[n].next_in = first_free_arc;
     245      if(_arcs[n].next_in!=-1) {
     246        _arcs[_arcs[n].next_in].prev_in = _arcs[n].prev_in;
     247      }
     248
     249      if(_arcs[n].prev_in!=-1) {
     250        _arcs[_arcs[n].prev_in].next_in = _arcs[n].next_in;
     251      } else {
     252        _nodes[_arcs[n].target].first_in = _arcs[n].next_in;
     253      }
     254
     255
     256      if(_arcs[n].next_out!=-1) {
     257        _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
     258      }
     259
     260      if(_arcs[n].prev_out!=-1) {
     261        _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
     262      } else {
     263        _nodes[_arcs[n].source].first_out = _arcs[n].next_out;
     264      }
     265
     266      _arcs[n].next_in = first_free_arc;
    267267      first_free_arc = n;
    268       arcs[n].prev_in = -2;
     268      _arcs[n].prev_in = -2;
    269269    }
    270270
    271271    void clear() {
    272       arcs.clear();
    273       nodes.clear();
     272      _arcs.clear();
     273      _nodes.clear();
    274274      first_node = first_free_node = first_free_arc = -1;
    275275    }
     
    278278    void changeTarget(Arc e, Node n)
    279279    {
    280       if(arcs[e.id].next_in != -1)
    281         arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
    282       if(arcs[e.id].prev_in != -1)
    283         arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
    284       else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
    285       if (nodes[n.id].first_in != -1) {
    286         arcs[nodes[n.id].first_in].prev_in = e.id;
    287       }
    288       arcs[e.id].target = n.id;
    289       arcs[e.id].prev_in = -1;
    290       arcs[e.id].next_in = nodes[n.id].first_in;
    291       nodes[n.id].first_in = e.id;
     280      if(_arcs[e.id].next_in != -1)
     281        _arcs[_arcs[e.id].next_in].prev_in = _arcs[e.id].prev_in;
     282      if(_arcs[e.id].prev_in != -1)
     283        _arcs[_arcs[e.id].prev_in].next_in = _arcs[e.id].next_in;
     284      else _nodes[_arcs[e.id].target].first_in = _arcs[e.id].next_in;
     285      if (_nodes[n.id].first_in != -1) {
     286        _arcs[_nodes[n.id].first_in].prev_in = e.id;
     287      }
     288      _arcs[e.id].target = n.id;
     289      _arcs[e.id].prev_in = -1;
     290      _arcs[e.id].next_in = _nodes[n.id].first_in;
     291      _nodes[n.id].first_in = e.id;
    292292    }
    293293    void changeSource(Arc e, Node n)
    294294    {
    295       if(arcs[e.id].next_out != -1)
    296         arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
    297       if(arcs[e.id].prev_out != -1)
    298         arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
    299       else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
    300       if (nodes[n.id].first_out != -1) {
    301         arcs[nodes[n.id].first_out].prev_out = e.id;
    302       }
    303       arcs[e.id].source = n.id;
    304       arcs[e.id].prev_out = -1;
    305       arcs[e.id].next_out = nodes[n.id].first_out;
    306       nodes[n.id].first_out = e.id;
     295      if(_arcs[e.id].next_out != -1)
     296        _arcs[_arcs[e.id].next_out].prev_out = _arcs[e.id].prev_out;
     297      if(_arcs[e.id].prev_out != -1)
     298        _arcs[_arcs[e.id].prev_out].next_out = _arcs[e.id].next_out;
     299      else _nodes[_arcs[e.id].source].first_out = _arcs[e.id].next_out;
     300      if (_nodes[n.id].first_out != -1) {
     301        _arcs[_nodes[n.id].first_out].prev_out = e.id;
     302      }
     303      _arcs[e.id].source = n.id;
     304      _arcs[e.id].prev_out = -1;
     305      _arcs[e.id].next_out = _nodes[n.id].first_out;
     306      _nodes[n.id].first_out = e.id;
    307307    }
    308308
     
    487487    Node split(Node n, bool connect = true) {
    488488      Node b = addNode();
    489       nodes[b.id].first_out=nodes[n.id].first_out;
    490       nodes[n.id].first_out=-1;
    491       for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
    492         arcs[i].source=b.id;
     489      _nodes[b.id].first_out=_nodes[n.id].first_out;
     490      _nodes[n.id].first_out=-1;
     491      for(int i=_nodes[b.id].first_out; i!=-1; i=_arcs[i].next_out) {
     492        _arcs[i].source=b.id;
    493493      }
    494494      if (connect) addArc(n,b);
     
    533533    /// to build the digraph.
    534534    /// \sa reserveArc()
    535     void reserveNode(int n) { nodes.reserve(n); };
     535    void reserveNode(int n) { _nodes.reserve(n); };
    536536
    537537    /// Reserve memory for arcs.
     
    543543    /// to build the digraph.
    544544    /// \sa reserveNode()
    545     void reserveArc(int m) { arcs.reserve(m); };
     545    void reserveArc(int m) { _arcs.reserve(m); };
    546546
    547547    /// \brief Class to make a snapshot of the digraph and restore
     
    804804    };
    805805
    806     std::vector<NodeT> nodes;
     806    std::vector<NodeT> _nodes;
    807807
    808808    int first_node;
     
    810810    int first_free_node;
    811811
    812     std::vector<ArcT> arcs;
     812    std::vector<ArcT> _arcs;
    813813
    814814    int first_free_arc;
     
    868868
    869869    ListGraphBase()
    870       : nodes(), first_node(-1),
    871         first_free_node(-1), arcs(), first_free_arc(-1) {}
    872 
    873 
    874     int maxNodeId() const { return nodes.size()-1; }
    875     int maxEdgeId() const { return arcs.size() / 2 - 1; }
    876     int maxArcId() const { return arcs.size()-1; }
    877 
    878     Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
    879     Node target(Arc e) const { return Node(arcs[e.id].target); }
    880 
    881     Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
    882     Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
     870      : _nodes(), first_node(-1),
     871        first_free_node(-1), _arcs(), first_free_arc(-1) {}
     872
     873
     874    int maxNodeId() const { return _nodes.size()-1; }
     875    int maxEdgeId() const { return _arcs.size() / 2 - 1; }
     876    int maxArcId() const { return _arcs.size()-1; }
     877
     878    Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); }
     879    Node target(Arc e) const { return Node(_arcs[e.id].target); }
     880
     881    Node u(Edge e) const { return Node(_arcs[2 * e.id].target); }
     882    Node v(Edge e) const { return Node(_arcs[2 * e.id + 1].target); }
    883883
    884884    static bool direction(Arc e) {
     
    895895
    896896    void next(Node& node) const {
    897       node.id = nodes[node.id].next;
     897      node.id = _nodes[node.id].next;
    898898    }
    899899
    900900    void first(Arc& e) const {
    901901      int n = first_node;
    902       while (n != -1 && nodes[n].first_out == -1) {
    903         n = nodes[n].next;
    904       }
    905       e.id = (n == -1) ? -1 : nodes[n].first_out;
     902      while (n != -1 && _nodes[n].first_out == -1) {
     903        n = _nodes[n].next;
     904      }
     905      e.id = (n == -1) ? -1 : _nodes[n].first_out;
    906906    }
    907907
    908908    void next(Arc& e) const {
    909       if (arcs[e.id].next_out != -1) {
    910         e.id = arcs[e.id].next_out;
    911       } else {
    912         int n = nodes[arcs[e.id ^ 1].target].next;
    913         while(n != -1 && nodes[n].first_out == -1) {
    914           n = nodes[n].next;
    915         }
    916         e.id = (n == -1) ? -1 : nodes[n].first_out;
     909      if (_arcs[e.id].next_out != -1) {
     910        e.id = _arcs[e.id].next_out;
     911      } else {
     912        int n = _nodes[_arcs[e.id ^ 1].target].next;
     913        while(n != -1 && _nodes[n].first_out == -1) {
     914          n = _nodes[n].next;
     915        }
     916        e.id = (n == -1) ? -1 : _nodes[n].first_out;
    917917      }
    918918    }
     
    921921      int n = first_node;
    922922      while (n != -1) {
    923         e.id = nodes[n].first_out;
     923        e.id = _nodes[n].first_out;
    924924        while ((e.id & 1) != 1) {
    925           e.id = arcs[e.id].next_out;
     925          e.id = _arcs[e.id].next_out;
    926926        }
    927927        if (e.id != -1) {
     
    929929          return;
    930930        }
    931         n = nodes[n].next;
     931        n = _nodes[n].next;
    932932      }
    933933      e.id = -1;
     
    935935
    936936    void next(Edge& e) const {
    937       int n = arcs[e.id * 2].target;
    938       e.id = arcs[(e.id * 2) | 1].next_out;
     937      int n = _arcs[e.id * 2].target;
     938      e.id = _arcs[(e.id * 2) | 1].next_out;
    939939      while ((e.id & 1) != 1) {
    940         e.id = arcs[e.id].next_out;
     940        e.id = _arcs[e.id].next_out;
    941941      }
    942942      if (e.id != -1) {
     
    944944        return;
    945945      }
    946       n = nodes[n].next;
     946      n = _nodes[n].next;
    947947      while (n != -1) {
    948         e.id = nodes[n].first_out;
     948        e.id = _nodes[n].first_out;
    949949        while ((e.id & 1) != 1) {
    950           e.id = arcs[e.id].next_out;
     950          e.id = _arcs[e.id].next_out;
    951951        }
    952952        if (e.id != -1) {
     
    954954          return;
    955955        }
    956         n = nodes[n].next;
     956        n = _nodes[n].next;
    957957      }
    958958      e.id = -1;
     
    960960
    961961    void firstOut(Arc &e, const Node& v) const {
    962       e.id = nodes[v.id].first_out;
     962      e.id = _nodes[v.id].first_out;
    963963    }
    964964    void nextOut(Arc &e) const {
    965       e.id = arcs[e.id].next_out;
     965      e.id = _arcs[e.id].next_out;
    966966    }
    967967
    968968    void firstIn(Arc &e, const Node& v) const {
    969       e.id = ((nodes[v.id].first_out) ^ 1);
     969      e.id = ((_nodes[v.id].first_out) ^ 1);
    970970      if (e.id == -2) e.id = -1;
    971971    }
    972972    void nextIn(Arc &e) const {
    973       e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
     973      e.id = ((_arcs[e.id ^ 1].next_out) ^ 1);
    974974      if (e.id == -2) e.id = -1;
    975975    }
    976976
    977977    void firstInc(Edge &e, bool& d, const Node& v) const {
    978       int a = nodes[v.id].first_out;
     978      int a = _nodes[v.id].first_out;
    979979      if (a != -1 ) {
    980980        e.id = a / 2;
     
    986986    }
    987987    void nextInc(Edge &e, bool& d) const {
    988       int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
     988      int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
    989989      if (a != -1 ) {
    990990        e.id = a / 2;
     
    10051005
    10061006    bool valid(Node n) const {
    1007       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
    1008         nodes[n.id].prev != -2;
     1007      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
     1008        _nodes[n.id].prev != -2;
    10091009    }
    10101010
    10111011    bool valid(Arc a) const {
    1012       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
    1013         arcs[a.id].prev_out != -2;
     1012      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
     1013        _arcs[a.id].prev_out != -2;
    10141014    }
    10151015
    10161016    bool valid(Edge e) const {
    1017       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
    1018         arcs[2 * e.id].prev_out != -2;
     1017      return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
     1018        _arcs[2 * e.id].prev_out != -2;
    10191019    }
    10201020
     
    10231023
    10241024      if(first_free_node==-1) {
    1025         n = nodes.size();
    1026         nodes.push_back(NodeT());
     1025        n = _nodes.size();
     1026        _nodes.push_back(NodeT());
    10271027      } else {
    10281028        n = first_free_node;
    1029         first_free_node = nodes[n].next;
    1030       }
    1031 
    1032       nodes[n].next = first_node;
    1033       if (first_node != -1) nodes[first_node].prev = n;
     1029        first_free_node = _nodes[n].next;
     1030      }
     1031
     1032      _nodes[n].next = first_node;
     1033      if (first_node != -1) _nodes[first_node].prev = n;
    10341034      first_node = n;
    1035       nodes[n].prev = -1;
    1036 
    1037       nodes[n].first_out = -1;
     1035      _nodes[n].prev = -1;
     1036
     1037      _nodes[n].first_out = -1;
    10381038
    10391039      return Node(n);
     
    10441044
    10451045      if (first_free_arc == -1) {
    1046         n = arcs.size();
    1047         arcs.push_back(ArcT());
    1048         arcs.push_back(ArcT());
     1046        n = _arcs.size();
     1047        _arcs.push_back(ArcT());
     1048        _arcs.push_back(ArcT());
    10491049      } else {
    10501050        n = first_free_arc;
    1051         first_free_arc = arcs[n].next_out;
    1052       }
    1053 
    1054       arcs[n].target = u.id;
    1055       arcs[n | 1].target = v.id;
    1056 
    1057       arcs[n].next_out = nodes[v.id].first_out;
    1058       if (nodes[v.id].first_out != -1) {
    1059         arcs[nodes[v.id].first_out].prev_out = n;
    1060       }
    1061       arcs[n].prev_out = -1;
    1062       nodes[v.id].first_out = n;
    1063 
    1064       arcs[n | 1].next_out = nodes[u.id].first_out;
    1065       if (nodes[u.id].first_out != -1) {
    1066         arcs[nodes[u.id].first_out].prev_out = (n | 1);
    1067       }
    1068       arcs[n | 1].prev_out = -1;
    1069       nodes[u.id].first_out = (n | 1);
     1051        first_free_arc = _arcs[n].next_out;
     1052      }
     1053
     1054      _arcs[n].target = u.id;
     1055      _arcs[n | 1].target = v.id;
     1056
     1057      _arcs[n].next_out = _nodes[v.id].first_out;
     1058      if (_nodes[v.id].first_out != -1) {
     1059        _arcs[_nodes[v.id].first_out].prev_out = n;
     1060      }
     1061      _arcs[n].prev_out = -1;
     1062      _nodes[v.id].first_out = n;
     1063
     1064      _arcs[n | 1].next_out = _nodes[u.id].first_out;
     1065      if (_nodes[u.id].first_out != -1) {
     1066        _arcs[_nodes[u.id].first_out].prev_out = (n | 1);
     1067      }
     1068      _arcs[n | 1].prev_out = -1;
     1069      _nodes[u.id].first_out = (n | 1);
    10701070
    10711071      return Edge(n / 2);
     
    10751075      int n = node.id;
    10761076
    1077       if(nodes[n].next != -1) {
    1078         nodes[nodes[n].next].prev = nodes[n].prev;
    1079       }
    1080 
    1081       if(nodes[n].prev != -1) {
    1082         nodes[nodes[n].prev].next = nodes[n].next;
    1083       } else {
    1084         first_node = nodes[n].next;
    1085       }
    1086 
    1087       nodes[n].next = first_free_node;
     1077      if(_nodes[n].next != -1) {
     1078        _nodes[_nodes[n].next].prev = _nodes[n].prev;
     1079      }
     1080
     1081      if(_nodes[n].prev != -1) {
     1082        _nodes[_nodes[n].prev].next = _nodes[n].next;
     1083      } else {
     1084        first_node = _nodes[n].next;
     1085      }
     1086
     1087      _nodes[n].next = first_free_node;
    10881088      first_free_node = n;
    1089       nodes[n].prev = -2;
     1089      _nodes[n].prev = -2;
    10901090    }
    10911091
     
    10931093      int n = edge.id * 2;
    10941094
    1095       if (arcs[n].next_out != -1) {
    1096         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    1097       }
    1098 
    1099       if (arcs[n].prev_out != -1) {
    1100         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    1101       } else {
    1102         nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
    1103       }
    1104 
    1105       if (arcs[n | 1].next_out != -1) {
    1106         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
    1107       }
    1108 
    1109       if (arcs[n | 1].prev_out != -1) {
    1110         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
    1111       } else {
    1112         nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
    1113       }
    1114 
    1115       arcs[n].next_out = first_free_arc;
     1095      if (_arcs[n].next_out != -1) {
     1096        _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
     1097      }
     1098
     1099      if (_arcs[n].prev_out != -1) {
     1100        _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
     1101      } else {
     1102        _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;
     1103      }
     1104
     1105      if (_arcs[n | 1].next_out != -1) {
     1106        _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;
     1107      }
     1108
     1109      if (_arcs[n | 1].prev_out != -1) {
     1110        _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;
     1111      } else {
     1112        _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;
     1113      }
     1114
     1115      _arcs[n].next_out = first_free_arc;
    11161116      first_free_arc = n;
    1117       arcs[n].prev_out = -2;
    1118       arcs[n | 1].prev_out = -2;
     1117      _arcs[n].prev_out = -2;
     1118      _arcs[n | 1].prev_out = -2;
    11191119
    11201120    }
    11211121
    11221122    void clear() {
    1123       arcs.clear();
    1124       nodes.clear();
     1123      _arcs.clear();
     1124      _nodes.clear();
    11251125      first_node = first_free_node = first_free_arc = -1;
    11261126    }
     
    11291129
    11301130    void changeV(Edge e, Node n) {
    1131       if(arcs[2 * e.id].next_out != -1) {
    1132         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
    1133       }
    1134       if(arcs[2 * e.id].prev_out != -1) {
    1135         arcs[arcs[2 * e.id].prev_out].next_out =
    1136           arcs[2 * e.id].next_out;
    1137       } else {
    1138         nodes[arcs[(2 * e.id) | 1].target].first_out =
    1139           arcs[2 * e.id].next_out;
    1140       }
    1141 
    1142       if (nodes[n.id].first_out != -1) {
    1143         arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
    1144       }
    1145       arcs[(2 * e.id) | 1].target = n.id;
    1146       arcs[2 * e.id].prev_out = -1;
    1147       arcs[2 * e.id].next_out = nodes[n.id].first_out;
    1148       nodes[n.id].first_out = 2 * e.id;
     1131      if(_arcs[2 * e.id].next_out != -1) {
     1132        _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;
     1133      }
     1134      if(_arcs[2 * e.id].prev_out != -1) {
     1135        _arcs[_arcs[2 * e.id].prev_out].next_out =
     1136          _arcs[2 * e.id].next_out;
     1137      } else {
     1138        _nodes[_arcs[(2 * e.id) | 1].target].first_out =
     1139          _arcs[2 * e.id].next_out;
     1140      }
     1141
     1142      if (_nodes[n.id].first_out != -1) {
     1143        _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;
     1144      }
     1145      _arcs[(2 * e.id) | 1].target = n.id;
     1146      _arcs[2 * e.id].prev_out = -1;
     1147      _arcs[2 * e.id].next_out = _nodes[n.id].first_out;
     1148      _nodes[n.id].first_out = 2 * e.id;
    11491149    }
    11501150
    11511151    void changeU(Edge e, Node n) {
    1152       if(arcs[(2 * e.id) | 1].next_out != -1) {
    1153         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
    1154           arcs[(2 * e.id) | 1].prev_out;
    1155       }
    1156       if(arcs[(2 * e.id) | 1].prev_out != -1) {
    1157         arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
    1158           arcs[(2 * e.id) | 1].next_out;
    1159       } else {
    1160         nodes[arcs[2 * e.id].target].first_out =
    1161           arcs[(2 * e.id) | 1].next_out;
    1162       }
    1163 
    1164       if (nodes[n.id].first_out != -1) {
    1165         arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
    1166       }
    1167       arcs[2 * e.id].target = n.id;
    1168       arcs[(2 * e.id) | 1].prev_out = -1;
    1169       arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
    1170       nodes[n.id].first_out = ((2 * e.id) | 1);
     1152      if(_arcs[(2 * e.id) | 1].next_out != -1) {
     1153        _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =
     1154          _arcs[(2 * e.id) | 1].prev_out;
     1155      }
     1156      if(_arcs[(2 * e.id) | 1].prev_out != -1) {
     1157        _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =
     1158          _arcs[(2 * e.id) | 1].next_out;
     1159      } else {
     1160        _nodes[_arcs[2 * e.id].target].first_out =
     1161          _arcs[(2 * e.id) | 1].next_out;
     1162      }
     1163
     1164      if (_nodes[n.id].first_out != -1) {
     1165        _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
     1166      }
     1167      _arcs[2 * e.id].target = n.id;
     1168      _arcs[(2 * e.id) | 1].prev_out = -1;
     1169      _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;
     1170      _nodes[n.id].first_out = ((2 * e.id) | 1);
    11711171    }
    11721172
     
    12101210    ListGraph() {}
    12111211
    1212     typedef Parent::OutArcIt IncEdgeIt;
     1212    typedef Parent::IncEdgeIt IncEdgeIt;
    12131213
    12141214    /// \brief Add a new node to the graph.
     
    13451345    /// to build the graph.
    13461346    /// \sa reserveEdge()
    1347     void reserveNode(int n) { nodes.reserve(n); };
     1347    void reserveNode(int n) { _nodes.reserve(n); };
    13481348
    13491349    /// Reserve memory for edges.
     
    13551355    /// to build the graph.
    13561356    /// \sa reserveNode()
    1357     void reserveEdge(int m) { arcs.reserve(2 * m); };
     1357    void reserveEdge(int m) { _arcs.reserve(2 * m); };
    13581358
    13591359    /// \brief Class to make a snapshot of the graph and restore
     
    16181618    };
    16191619
    1620     std::vector<NodeT> nodes;
     1620    std::vector<NodeT> _nodes;
    16211621
    16221622    int first_node, first_red, first_blue;
     
    16251625    int first_free_red, first_free_blue;
    16261626
    1627     std::vector<ArcT> arcs;
     1627    std::vector<ArcT> _arcs;
    16281628
    16291629    int first_free_arc;
     
    17071707
    17081708    ListBpGraphBase()
    1709       : nodes(), first_node(-1),
     1709      : _nodes(), first_node(-1),
    17101710        first_red(-1), first_blue(-1),
    17111711        max_red(-1), max_blue(-1),
    17121712        first_free_red(-1), first_free_blue(-1),
    1713         arcs(), first_free_arc(-1) {}
    1714 
    1715 
    1716     bool red(Node n) const { return nodes[n.id].red; }
    1717     bool blue(Node n) const { return !nodes[n.id].red; }
     1713        _arcs(), first_free_arc(-1) {}
     1714
     1715
     1716    bool red(Node n) const { return _nodes[n.id].red; }
     1717    bool blue(Node n) const { return !_nodes[n.id].red; }
    17181718
    17191719    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
    17201720    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
    17211721
    1722     int maxNodeId() const { return nodes.size()-1; }
     1722    int maxNodeId() const { return _nodes.size()-1; }
    17231723    int maxRedId() const { return max_red; }
    17241724    int maxBlueId() const { return max_blue; }
    1725     int maxEdgeId() const { return arcs.size() / 2 - 1; }
    1726     int maxArcId() const { return arcs.size()-1; }
    1727 
    1728     Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
    1729     Node target(Arc e) const { return Node(arcs[e.id].target); }
     1725    int maxEdgeId() const { return _arcs.size() / 2 - 1; }
     1726    int maxArcId() const { return _arcs.size()-1; }
     1727
     1728    Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); }
     1729    Node target(Arc e) const { return Node(_arcs[e.id].target); }
    17301730
    17311731    RedNode redNode(Edge e) const {
    1732       return RedNode(arcs[2 * e.id].target);
     1732      return RedNode(_arcs[2 * e.id].target);
    17331733    }
    17341734    BlueNode blueNode(Edge e) const {
    1735       return BlueNode(arcs[2 * e.id + 1].target);
     1735      return BlueNode(_arcs[2 * e.id + 1].target);
    17361736    }
    17371737
     
    17491749
    17501750    void next(Node& node) const {
    1751       node.id = nodes[node.id].next;
     1751      node.id = _nodes[node.id].next;
    17521752    }
    17531753
     
    17571757
    17581758    void next(RedNode& node) const {
    1759       node.id = nodes[node.id].partition_next;
     1759      node.id = _nodes[node.id].partition_next;
    17601760    }
    17611761
     
    17651765
    17661766    void next(BlueNode& node) const {
    1767       node.id = nodes[node.id].partition_next;
     1767      node.id = _nodes[node.id].partition_next;
    17681768    }
    17691769
    17701770    void first(Arc& e) const {
    17711771      int n = first_node;
    1772       while (n != -1 && nodes[n].first_out == -1) {
    1773         n = nodes[n].next;
    1774       }
    1775       e.id = (n == -1) ? -1 : nodes[n].first_out;
     1772      while (n != -1 && _nodes[n].first_out == -1) {
     1773        n = _nodes[n].next;
     1774      }
     1775      e.id = (n == -1) ? -1 : _nodes[n].first_out;
    17761776    }
    17771777
    17781778    void next(Arc& e) const {
    1779       if (arcs[e.id].next_out != -1) {
    1780         e.id = arcs[e.id].next_out;
    1781       } else {
    1782         int n = nodes[arcs[e.id ^ 1].target].next;
    1783         while(n != -1 && nodes[n].first_out == -1) {
    1784           n = nodes[n].next;
    1785         }
    1786         e.id = (n == -1) ? -1 : nodes[n].first_out;
     1779      if (_arcs[e.id].next_out != -1) {
     1780        e.id = _arcs[e.id].next_out;
     1781      } else {
     1782        int n = _nodes[_arcs[e.id ^ 1].target].next;
     1783        while(n != -1 && _nodes[n].first_out == -1) {
     1784          n = _nodes[n].next;
     1785        }
     1786        e.id = (n == -1) ? -1 : _nodes[n].first_out;
    17871787      }
    17881788    }
     
    17911791      int n = first_node;
    17921792      while (n != -1) {
    1793         e.id = nodes[n].first_out;
     1793        e.id = _nodes[n].first_out;
    17941794        while ((e.id & 1) != 1) {
    1795           e.id = arcs[e.id].next_out;
     1795          e.id = _arcs[e.id].next_out;
    17961796        }
    17971797        if (e.id != -1) {
     
    17991799          return;
    18001800        }
    1801         n = nodes[n].next;
     1801        n = _nodes[n].next;
    18021802      }
    18031803      e.id = -1;
     
    18051805
    18061806    void next(Edge& e) const {
    1807       int n = arcs[e.id * 2].target;
    1808       e.id = arcs[(e.id * 2) | 1].next_out;
     1807      int n = _arcs[e.id * 2].target;
     1808      e.id = _arcs[(e.id * 2) | 1].next_out;
    18091809      while ((e.id & 1) != 1) {
    1810         e.id = arcs[e.id].next_out;
     1810        e.id = _arcs[e.id].next_out;
    18111811      }
    18121812      if (e.id != -1) {
     
    18141814        return;
    18151815      }
    1816       n = nodes[n].next;
     1816      n = _nodes[n].next;
    18171817      while (n != -1) {
    1818         e.id = nodes[n].first_out;
     1818        e.id = _nodes[n].first_out;
    18191819        while ((e.id & 1) != 1) {
    1820           e.id = arcs[e.id].next_out;
     1820          e.id = _arcs[e.id].next_out;
    18211821        }
    18221822        if (e.id != -1) {
     
    18241824          return;
    18251825        }
    1826         n = nodes[n].next;
     1826        n = _nodes[n].next;
    18271827      }
    18281828      e.id = -1;
     
    18301830
    18311831    void firstOut(Arc &e, const Node& v) const {
    1832       e.id = nodes[v.id].first_out;
     1832      e.id = _nodes[v.id].first_out;
    18331833    }
    18341834    void nextOut(Arc &e) const {
    1835       e.id = arcs[e.id].next_out;
     1835      e.id = _arcs[e.id].next_out;
    18361836    }
    18371837
    18381838    void firstIn(Arc &e, const Node& v) const {
    1839       e.id = ((nodes[v.id].first_out) ^ 1);
     1839      e.id = ((_nodes[v.id].first_out) ^ 1);
    18401840      if (e.id == -2) e.id = -1;
    18411841    }
    18421842    void nextIn(Arc &e) const {
    1843       e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
     1843      e.id = ((_arcs[e.id ^ 1].next_out) ^ 1);
    18441844      if (e.id == -2) e.id = -1;
    18451845    }
    18461846
    18471847    void firstInc(Edge &e, bool& d, const Node& v) const {
    1848       int a = nodes[v.id].first_out;
     1848      int a = _nodes[v.id].first_out;
    18491849      if (a != -1 ) {
    18501850        e.id = a / 2;
     
    18561856    }
    18571857    void nextInc(Edge &e, bool& d) const {
    1858       int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
     1858      int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
    18591859      if (a != -1 ) {
    18601860        e.id = a / 2;
     
    18671867
    18681868    static int id(Node v) { return v.id; }
    1869     int id(RedNode v) const { return nodes[v.id].partition_index; }
    1870     int id(BlueNode v) const { return nodes[v.id].partition_index; }
     1869    int id(RedNode v) const { return _nodes[v.id].partition_index; }
     1870    int id(BlueNode v) const { return _nodes[v.id].partition_index; }
    18711871    static int id(Arc e) { return e.id; }
    18721872    static int id(Edge e) { return e.id; }
     
    18771877
    18781878    bool valid(Node n) const {
    1879       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
    1880         nodes[n.id].prev != -2;
     1879      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
     1880        _nodes[n.id].prev != -2;
    18811881    }
    18821882
    18831883    bool valid(Arc a) const {
    1884       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
    1885         arcs[a.id].prev_out != -2;
     1884      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
     1885        _arcs[a.id].prev_out != -2;
    18861886    }
    18871887
    18881888    bool valid(Edge e) const {
    1889       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
    1890         arcs[2 * e.id].prev_out != -2;
     1889      return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
     1890        _arcs[2 * e.id].prev_out != -2;
    18911891    }
    18921892
     
    18951895
    18961896      if(first_free_red==-1) {
    1897         n = nodes.size();
    1898         nodes.push_back(NodeT());
    1899         nodes[n].partition_index = ++max_red;
    1900         nodes[n].red = true;
     1897        n = _nodes.size();
     1898        _nodes.push_back(NodeT());
     1899        _nodes[n].partition_index = ++max_red;
     1900        _nodes[n].red = true;
    19011901      } else {
    19021902        n = first_free_red;
    1903         first_free_red = nodes[n].next;
    1904       }
    1905 
    1906       nodes[n].next = first_node;
    1907       if (first_node != -1) nodes[first_node].prev = n;
     1903        first_free_red = _nodes[n].next;
     1904      }
     1905
     1906      _nodes[n].next = first_node;
     1907      if (first_node != -1) _nodes[first_node].prev = n;
    19081908      first_node = n;
    1909       nodes[n].prev = -1;
    1910 
    1911       nodes[n].partition_next = first_red;
    1912       if (first_red != -1) nodes[first_red].partition_prev = n;
     1909      _nodes[n].prev = -1;
     1910
     1911      _nodes[n].partition_next = first_red;
     1912      if (first_red != -1) _nodes[first_red].partition_prev = n;
    19131913      first_red = n;
    1914       nodes[n].partition_prev = -1;
    1915 
    1916       nodes[n].first_out = -1;
     1914      _nodes[n].partition_prev = -1;
     1915
     1916      _nodes[n].first_out = -1;
    19171917
    19181918      return RedNode(n);
     
    19231923
    19241924      if(first_free_blue==-1) {
    1925         n = nodes.size();
    1926         nodes.push_back(NodeT());
    1927         nodes[n].partition_index = ++max_blue;
    1928         nodes[n].red = false;
     1925        n = _nodes.size();
     1926        _nodes.push_back(NodeT());
     1927        _nodes[n].partition_index = ++max_blue;
     1928        _nodes[n].red = false;
    19291929      } else {
    19301930        n = first_free_blue;
    1931         first_free_blue = nodes[n].next;
    1932       }
    1933 
    1934       nodes[n].next = first_node;
    1935       if (first_node != -1) nodes[first_node].prev = n;
     1931        first_free_blue = _nodes[n].next;
     1932      }
     1933
     1934      _nodes[n].next = first_node;
     1935      if (first_node != -1) _nodes[first_node].prev = n;
    19361936      first_node = n;
    1937       nodes[n].prev = -1;
    1938 
    1939       nodes[n].partition_next = first_blue;
    1940       if (first_blue != -1) nodes[first_blue].partition_prev = n;
     1937      _nodes[n].prev = -1;
     1938
     1939      _nodes[n].partition_next = first_blue;
     1940      if (first_blue != -1) _nodes[first_blue].partition_prev = n;
    19411941      first_blue = n;
    1942       nodes[n].partition_prev = -1;
    1943 
    1944       nodes[n].first_out = -1;
     1942      _nodes[n].partition_prev = -1;
     1943
     1944      _nodes[n].first_out = -1;
    19451945
    19461946      return BlueNode(n);
     
    19511951
    19521952      if (first_free_arc == -1) {
    1953         n = arcs.size();
    1954         arcs.push_back(ArcT());
    1955         arcs.push_back(ArcT());
     1953        n = _arcs.size();
     1954        _arcs.push_back(ArcT());
     1955        _arcs.push_back(ArcT());
    19561956      } else {
    19571957        n = first_free_arc;
    1958         first_free_arc = arcs[n].next_out;
    1959       }
    1960 
    1961       arcs[n].target = u.id;
    1962       arcs[n | 1].target = v.id;
    1963 
    1964       arcs[n].next_out = nodes[v.id].first_out;
    1965       if (nodes[v.id].first_out != -1) {
    1966         arcs[nodes[v.id].first_out].prev_out = n;
    1967       }
    1968       arcs[n].prev_out = -1;
    1969       nodes[v.id].first_out = n;
    1970 
    1971       arcs[n | 1].next_out = nodes[u.id].first_out;
    1972       if (nodes[u.id].first_out != -1) {
    1973         arcs[nodes[u.id].first_out].prev_out = (n | 1);
    1974       }
    1975       arcs[n | 1].prev_out = -1;
    1976       nodes[u.id].first_out = (n | 1);
     1958        first_free_arc = _arcs[n].next_out;
     1959      }
     1960
     1961      _arcs[n].target = u.id;
     1962      _arcs[n | 1].target = v.id;
     1963
     1964      _arcs[n].next_out = _nodes[v.id].first_out;
     1965      if (_nodes[v.id].first_out != -1) {
     1966        _arcs[_nodes[v.id].first_out].prev_out = n;
     1967      }
     1968      _arcs[n].prev_out = -1;
     1969      _nodes[v.id].first_out = n;
     1970
     1971      _arcs[n | 1].next_out = _nodes[u.id].first_out;
     1972      if (_nodes[u.id].first_out != -1) {
     1973        _arcs[_nodes[u.id].first_out].prev_out = (n | 1);
     1974      }
     1975      _arcs[n | 1].prev_out = -1;
     1976      _nodes[u.id].first_out = (n | 1);
    19771977
    19781978      return Edge(n / 2);
     
    19821982      int n = node.id;
    19831983
    1984       if(nodes[n].next != -1) {
    1985         nodes[nodes[n].next].prev = nodes[n].prev;
    1986       }
    1987 
    1988       if(nodes[n].prev != -1) {
    1989         nodes[nodes[n].prev].next = nodes[n].next;
    1990       } else {
    1991         first_node = nodes[n].next;
    1992       }
    1993 
    1994       if (nodes[n].partition_next != -1) {
    1995         nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
    1996       }
    1997 
    1998       if (nodes[n].partition_prev != -1) {
    1999         nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
    2000       } else {
    2001         if (nodes[n].red) {
    2002           first_red = nodes[n].partition_next;
     1984      if(_nodes[n].next != -1) {
     1985        _nodes[_nodes[n].next].prev = _nodes[n].prev;
     1986      }
     1987
     1988      if(_nodes[n].prev != -1) {
     1989        _nodes[_nodes[n].prev].next = _nodes[n].next;
     1990      } else {
     1991        first_node = _nodes[n].next;
     1992      }
     1993
     1994      if (_nodes[n].partition_next != -1) {
     1995        _nodes[_nodes[n].partition_next].partition_prev = _nodes[n].partition_prev;
     1996      }
     1997
     1998      if (_nodes[n].partition_prev != -1) {
     1999        _nodes[_nodes[n].partition_prev].partition_next = _nodes[n].partition_next;
     2000      } else {
     2001        if (_nodes[n].red) {
     2002          first_red = _nodes[n].partition_next;
    20032003        } else {
    2004           first_blue = nodes[n].partition_next;
    2005         }
    2006       }
    2007 
    2008       if (nodes[n].red) {
    2009         nodes[n].next = first_free_red;
     2004          first_blue = _nodes[n].partition_next;
     2005        }
     2006      }
     2007
     2008      if (_nodes[n].red) {
     2009        _nodes[n].next = first_free_red;
    20102010        first_free_red = n;
    20112011      } else {
    2012         nodes[n].next = first_free_blue;
     2012        _nodes[n].next = first_free_blue;
    20132013        first_free_blue = n;
    20142014      }
    2015       nodes[n].prev = -2;
     2015      _nodes[n].prev = -2;
    20162016    }
    20172017
     
    20192019      int n = edge.id * 2;
    20202020
    2021       if (arcs[n].next_out != -1) {
    2022         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    2023       }
    2024 
    2025       if (arcs[n].prev_out != -1) {
    2026         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    2027       } else {
    2028         nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
    2029       }
    2030 
    2031       if (arcs[n | 1].next_out != -1) {
    2032         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
    2033       }
    2034 
    2035       if (arcs[n | 1].prev_out != -1) {
    2036         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
    2037       } else {
    2038         nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
    2039       }
    2040 
    2041       arcs[n].next_out = first_free_arc;
     2021      if (_arcs[n].next_out != -1) {
     2022        _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
     2023      }
     2024
     2025      if (_arcs[n].prev_out != -1) {
     2026        _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
     2027      } else {
     2028        _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;
     2029      }
     2030
     2031      if (_arcs[n | 1].next_out != -1) {
     2032        _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;
     2033      }
     2034
     2035      if (_arcs[n | 1].prev_out != -1) {
     2036        _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;
     2037      } else {
     2038        _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;
     2039      }
     2040
     2041      _arcs[n].next_out = first_free_arc;
    20422042      first_free_arc = n;
    2043       arcs[n].prev_out = -2;
    2044       arcs[n | 1].prev_out = -2;
     2043      _arcs[n].prev_out = -2;
     2044      _arcs[n | 1].prev_out = -2;
    20452045
    20462046    }
    20472047
    20482048    void clear() {
    2049       arcs.clear();
    2050       nodes.clear();
     2049      _arcs.clear();
     2050      _nodes.clear();
    20512051      first_node = first_free_arc = first_red = first_blue =
    20522052        max_red = max_blue = first_free_red = first_free_blue = -1;
     
    20562056
    20572057    void changeRed(Edge e, RedNode n) {
    2058       if(arcs[(2 * e.id) | 1].next_out != -1) {
    2059         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
    2060           arcs[(2 * e.id) | 1].prev_out;
    2061       }
    2062       if(arcs[(2 * e.id) | 1].prev_out != -1) {
    2063         arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
    2064           arcs[(2 * e.id) | 1].next_out;
    2065       } else {
    2066         nodes[arcs[2 * e.id].target].first_out =
    2067           arcs[(2 * e.id) | 1].next_out;
    2068       }
    2069 
    2070       if (nodes[n.id].first_out != -1) {
    2071         arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
    2072       }
    2073       arcs[2 * e.id].target = n.id;
    2074       arcs[(2 * e.id) | 1].prev_out = -1;
    2075       arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
    2076       nodes[n.id].first_out = ((2 * e.id) | 1);
     2058      if(_arcs[(2 * e.id) | 1].next_out != -1) {
     2059        _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =
     2060          _arcs[(2 * e.id) | 1].prev_out;
     2061      }
     2062      if(_arcs[(2 * e.id) | 1].prev_out != -1) {
     2063        _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =
     2064          _arcs[(2 * e.id) | 1].next_out;
     2065      } else {
     2066        _nodes[_arcs[2 * e.id].target].first_out =
     2067          _arcs[(2 * e.id) | 1].next_out;
     2068      }
     2069
     2070      if (_nodes[n.id].first_out != -1) {
     2071        _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
     2072      }
     2073      _arcs[2 * e.id].target = n.id;
     2074      _arcs[(2 * e.id) | 1].prev_out = -1;
     2075      _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;
     2076      _nodes[n.id].first_out = ((2 * e.id) | 1);
    20772077    }
    20782078
    20792079    void changeBlue(Edge e, BlueNode n) {
    2080        if(arcs[2 * e.id].next_out != -1) {
    2081         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
    2082       }
    2083       if(arcs[2 * e.id].prev_out != -1) {
    2084         arcs[arcs[2 * e.id].prev_out].next_out =
    2085           arcs[2 * e.id].next_out;
    2086       } else {
    2087         nodes[arcs[(2 * e.id) | 1].target].first_out =
    2088           arcs[2 * e.id].next_out;
    2089       }
    2090 
    2091       if (nodes[n.id].first_out != -1) {
    2092         arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
    2093       }
    2094       arcs[(2 * e.id) | 1].target = n.id;
    2095       arcs[2 * e.id].prev_out = -1;
    2096       arcs[2 * e.id].next_out = nodes[n.id].first_out;
    2097       nodes[n.id].first_out = 2 * e.id;
     2080       if(_arcs[2 * e.id].next_out != -1) {
     2081        _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;
     2082      }
     2083      if(_arcs[2 * e.id].prev_out != -1) {
     2084        _arcs[_arcs[2 * e.id].prev_out].next_out =
     2085          _arcs[2 * e.id].next_out;
     2086      } else {
     2087        _nodes[_arcs[(2 * e.id) | 1].target].first_out =
     2088          _arcs[2 * e.id].next_out;
     2089      }
     2090
     2091      if (_nodes[n.id].first_out != -1) {
     2092        _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;
     2093      }
     2094      _arcs[(2 * e.id) | 1].target = n.id;
     2095      _arcs[2 * e.id].prev_out = -1;
     2096      _arcs[2 * e.id].next_out = _nodes[n.id].first_out;
     2097      _nodes[n.id].first_out = 2 * e.id;
    20982098    }
    20992099
     
    21372137    ListBpGraph() {}
    21382138
    2139     typedef Parent::OutArcIt IncEdgeIt;
     2139    typedef Parent::IncEdgeIt IncEdgeIt;
    21402140
    21412141    /// \brief Add a new red node to the graph.
     
    22502250    /// to build the graph.
    22512251    /// \sa reserveEdge()
    2252     void reserveNode(int n) { nodes.reserve(n); };
     2252    void reserveNode(int n) { _nodes.reserve(n); };
    22532253
    22542254    /// Reserve memory for edges.
     
    22602260    /// to build the graph.
    22612261    /// \sa reserveNode()
    2262     void reserveEdge(int m) { arcs.reserve(2 * m); };
     2262    void reserveEdge(int m) { _arcs.reserve(2 * m); };
    22632263
    22642264    /// \brief Class to make a snapshot of the graph and restore
Note: See TracChangeset for help on using the changeset viewer.