lemon/list_graph.h
changeset 1130 0759d974de81
parent 1092 dceba191c00d
child 1131 4add05447ca0
     1.1 --- a/lemon/list_graph.h	Thu Apr 02 22:34:03 2015 +0200
     1.2 +++ b/lemon/list_graph.h	Sun Jan 05 22:24:56 2014 +0100
     1.3 @@ -48,13 +48,13 @@
     1.4        int next_in, next_out;
     1.5      };
     1.6  
     1.7 -    std::vector<NodeT> nodes;
     1.8 +    std::vector<NodeT> _nodes;
     1.9  
    1.10      int first_node;
    1.11  
    1.12      int first_free_node;
    1.13  
    1.14 -    std::vector<ArcT> arcs;
    1.15 +    std::vector<ArcT> _arcs;
    1.16  
    1.17      int first_free_arc;
    1.18  
    1.19 @@ -97,15 +97,15 @@
    1.20  
    1.21  
    1.22      ListDigraphBase()
    1.23 -      : nodes(), first_node(-1),
    1.24 -        first_free_node(-1), arcs(), first_free_arc(-1) {}
    1.25 -
    1.26 -
    1.27 -    int maxNodeId() const { return nodes.size()-1; }
    1.28 -    int maxArcId() const { return arcs.size()-1; }
    1.29 -
    1.30 -    Node source(Arc e) const { return Node(arcs[e.id].source); }
    1.31 -    Node target(Arc e) const { return Node(arcs[e.id].target); }
    1.32 +      : _nodes(), first_node(-1),
    1.33 +        first_free_node(-1), _arcs(), first_free_arc(-1) {}
    1.34 +
    1.35 +
    1.36 +    int maxNodeId() const { return _nodes.size()-1; }
    1.37 +    int maxArcId() const { return _arcs.size()-1; }
    1.38 +
    1.39 +    Node source(Arc e) const { return Node(_arcs[e.id].source); }
    1.40 +    Node target(Arc e) const { return Node(_arcs[e.id].target); }
    1.41  
    1.42  
    1.43      void first(Node& node) const {
    1.44 @@ -113,42 +113,42 @@
    1.45      }
    1.46  
    1.47      void next(Node& node) const {
    1.48 -      node.id = nodes[node.id].next;
    1.49 +      node.id = _nodes[node.id].next;
    1.50      }
    1.51  
    1.52  
    1.53      void first(Arc& arc) const {
    1.54        int n;
    1.55        for(n = first_node;
    1.56 -          n != -1 && nodes[n].first_out == -1;
    1.57 -          n = nodes[n].next) {}
    1.58 -      arc.id = (n == -1) ? -1 : nodes[n].first_out;
    1.59 +          n != -1 && _nodes[n].first_out == -1;
    1.60 +          n = _nodes[n].next) {}
    1.61 +      arc.id = (n == -1) ? -1 : _nodes[n].first_out;
    1.62      }
    1.63  
    1.64      void next(Arc& arc) const {
    1.65 -      if (arcs[arc.id].next_out != -1) {
    1.66 -        arc.id = arcs[arc.id].next_out;
    1.67 +      if (_arcs[arc.id].next_out != -1) {
    1.68 +        arc.id = _arcs[arc.id].next_out;
    1.69        } else {
    1.70          int n;
    1.71 -        for(n = nodes[arcs[arc.id].source].next;
    1.72 -            n != -1 && nodes[n].first_out == -1;
    1.73 -            n = nodes[n].next) {}
    1.74 -        arc.id = (n == -1) ? -1 : nodes[n].first_out;
    1.75 +        for(n = _nodes[_arcs[arc.id].source].next;
    1.76 +            n != -1 && _nodes[n].first_out == -1;
    1.77 +            n = _nodes[n].next) {}
    1.78 +        arc.id = (n == -1) ? -1 : _nodes[n].first_out;
    1.79        }
    1.80      }
    1.81  
    1.82      void firstOut(Arc &e, const Node& v) const {
    1.83 -      e.id = nodes[v.id].first_out;
    1.84 +      e.id = _nodes[v.id].first_out;
    1.85      }
    1.86      void nextOut(Arc &e) const {
    1.87 -      e.id=arcs[e.id].next_out;
    1.88 +      e.id=_arcs[e.id].next_out;
    1.89      }
    1.90  
    1.91      void firstIn(Arc &e, const Node& v) const {
    1.92 -      e.id = nodes[v.id].first_in;
    1.93 +      e.id = _nodes[v.id].first_in;
    1.94      }
    1.95      void nextIn(Arc &e) const {
    1.96 -      e.id=arcs[e.id].next_in;
    1.97 +      e.id=_arcs[e.id].next_in;
    1.98      }
    1.99  
   1.100  
   1.101 @@ -159,32 +159,32 @@
   1.102      static Arc arcFromId(int id) { return Arc(id);}
   1.103  
   1.104      bool valid(Node n) const {
   1.105 -      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
   1.106 -        nodes[n.id].prev != -2;
   1.107 +      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
   1.108 +        _nodes[n.id].prev != -2;
   1.109      }
   1.110  
   1.111      bool valid(Arc a) const {
   1.112 -      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
   1.113 -        arcs[a.id].prev_in != -2;
   1.114 +      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
   1.115 +        _arcs[a.id].prev_in != -2;
   1.116      }
   1.117  
   1.118      Node addNode() {
   1.119        int n;
   1.120  
   1.121        if(first_free_node==-1) {
   1.122 -        n = nodes.size();
   1.123 -        nodes.push_back(NodeT());
   1.124 +        n = _nodes.size();
   1.125 +        _nodes.push_back(NodeT());
   1.126        } else {
   1.127          n = first_free_node;
   1.128 -        first_free_node = nodes[n].next;
   1.129 +        first_free_node = _nodes[n].next;
   1.130        }
   1.131  
   1.132 -      nodes[n].next = first_node;
   1.133 -      if(first_node != -1) nodes[first_node].prev = n;
   1.134 +      _nodes[n].next = first_node;
   1.135 +      if(first_node != -1) _nodes[first_node].prev = n;
   1.136        first_node = n;
   1.137 -      nodes[n].prev = -1;
   1.138 -
   1.139 -      nodes[n].first_in = nodes[n].first_out = -1;
   1.140 +      _nodes[n].prev = -1;
   1.141 +
   1.142 +      _nodes[n].first_in = _nodes[n].first_out = -1;
   1.143  
   1.144        return Node(n);
   1.145      }
   1.146 @@ -193,29 +193,29 @@
   1.147        int n;
   1.148  
   1.149        if (first_free_arc == -1) {
   1.150 -        n = arcs.size();
   1.151 -        arcs.push_back(ArcT());
   1.152 +        n = _arcs.size();
   1.153 +        _arcs.push_back(ArcT());
   1.154        } else {
   1.155          n = first_free_arc;
   1.156 -        first_free_arc = arcs[n].next_in;
   1.157 +        first_free_arc = _arcs[n].next_in;
   1.158        }
   1.159  
   1.160 -      arcs[n].source = u.id;
   1.161 -      arcs[n].target = v.id;
   1.162 -
   1.163 -      arcs[n].next_out = nodes[u.id].first_out;
   1.164 -      if(nodes[u.id].first_out != -1) {
   1.165 -        arcs[nodes[u.id].first_out].prev_out = n;
   1.166 +      _arcs[n].source = u.id;
   1.167 +      _arcs[n].target = v.id;
   1.168 +
   1.169 +      _arcs[n].next_out = _nodes[u.id].first_out;
   1.170 +      if(_nodes[u.id].first_out != -1) {
   1.171 +        _arcs[_nodes[u.id].first_out].prev_out = n;
   1.172        }
   1.173  
   1.174 -      arcs[n].next_in = nodes[v.id].first_in;
   1.175 -      if(nodes[v.id].first_in != -1) {
   1.176 -        arcs[nodes[v.id].first_in].prev_in = n;
   1.177 +      _arcs[n].next_in = _nodes[v.id].first_in;
   1.178 +      if(_nodes[v.id].first_in != -1) {
   1.179 +        _arcs[_nodes[v.id].first_in].prev_in = n;
   1.180        }
   1.181  
   1.182 -      arcs[n].prev_in = arcs[n].prev_out = -1;
   1.183 -
   1.184 -      nodes[u.id].first_out = nodes[v.id].first_in = n;
   1.185 +      _arcs[n].prev_in = _arcs[n].prev_out = -1;
   1.186 +
   1.187 +      _nodes[u.id].first_out = _nodes[v.id].first_in = n;
   1.188  
   1.189        return Arc(n);
   1.190      }
   1.191 @@ -223,87 +223,87 @@
   1.192      void erase(const Node& node) {
   1.193        int n = node.id;
   1.194  
   1.195 -      if(nodes[n].next != -1) {
   1.196 -        nodes[nodes[n].next].prev = nodes[n].prev;
   1.197 +      if(_nodes[n].next != -1) {
   1.198 +        _nodes[_nodes[n].next].prev = _nodes[n].prev;
   1.199        }
   1.200  
   1.201 -      if(nodes[n].prev != -1) {
   1.202 -        nodes[nodes[n].prev].next = nodes[n].next;
   1.203 +      if(_nodes[n].prev != -1) {
   1.204 +        _nodes[_nodes[n].prev].next = _nodes[n].next;
   1.205        } else {
   1.206 -        first_node = nodes[n].next;
   1.207 +        first_node = _nodes[n].next;
   1.208        }
   1.209  
   1.210 -      nodes[n].next = first_free_node;
   1.211 +      _nodes[n].next = first_free_node;
   1.212        first_free_node = n;
   1.213 -      nodes[n].prev = -2;
   1.214 +      _nodes[n].prev = -2;
   1.215  
   1.216      }
   1.217  
   1.218      void erase(const Arc& arc) {
   1.219        int n = arc.id;
   1.220  
   1.221 -      if(arcs[n].next_in!=-1) {
   1.222 -        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
   1.223 +      if(_arcs[n].next_in!=-1) {
   1.224 +        _arcs[_arcs[n].next_in].prev_in = _arcs[n].prev_in;
   1.225        }
   1.226  
   1.227 -      if(arcs[n].prev_in!=-1) {
   1.228 -        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
   1.229 +      if(_arcs[n].prev_in!=-1) {
   1.230 +        _arcs[_arcs[n].prev_in].next_in = _arcs[n].next_in;
   1.231        } else {
   1.232 -        nodes[arcs[n].target].first_in = arcs[n].next_in;
   1.233 +        _nodes[_arcs[n].target].first_in = _arcs[n].next_in;
   1.234        }
   1.235  
   1.236  
   1.237 -      if(arcs[n].next_out!=-1) {
   1.238 -        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   1.239 +      if(_arcs[n].next_out!=-1) {
   1.240 +        _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
   1.241        }
   1.242  
   1.243 -      if(arcs[n].prev_out!=-1) {
   1.244 -        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   1.245 +      if(_arcs[n].prev_out!=-1) {
   1.246 +        _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
   1.247        } else {
   1.248 -        nodes[arcs[n].source].first_out = arcs[n].next_out;
   1.249 +        _nodes[_arcs[n].source].first_out = _arcs[n].next_out;
   1.250        }
   1.251  
   1.252 -      arcs[n].next_in = first_free_arc;
   1.253 +      _arcs[n].next_in = first_free_arc;
   1.254        first_free_arc = n;
   1.255 -      arcs[n].prev_in = -2;
   1.256 +      _arcs[n].prev_in = -2;
   1.257      }
   1.258  
   1.259      void clear() {
   1.260 -      arcs.clear();
   1.261 -      nodes.clear();
   1.262 +      _arcs.clear();
   1.263 +      _nodes.clear();
   1.264        first_node = first_free_node = first_free_arc = -1;
   1.265      }
   1.266  
   1.267    protected:
   1.268      void changeTarget(Arc e, Node n)
   1.269      {
   1.270 -      if(arcs[e.id].next_in != -1)
   1.271 -        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
   1.272 -      if(arcs[e.id].prev_in != -1)
   1.273 -        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
   1.274 -      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
   1.275 -      if (nodes[n.id].first_in != -1) {
   1.276 -        arcs[nodes[n.id].first_in].prev_in = e.id;
   1.277 +      if(_arcs[e.id].next_in != -1)
   1.278 +        _arcs[_arcs[e.id].next_in].prev_in = _arcs[e.id].prev_in;
   1.279 +      if(_arcs[e.id].prev_in != -1)
   1.280 +        _arcs[_arcs[e.id].prev_in].next_in = _arcs[e.id].next_in;
   1.281 +      else _nodes[_arcs[e.id].target].first_in = _arcs[e.id].next_in;
   1.282 +      if (_nodes[n.id].first_in != -1) {
   1.283 +        _arcs[_nodes[n.id].first_in].prev_in = e.id;
   1.284        }
   1.285 -      arcs[e.id].target = n.id;
   1.286 -      arcs[e.id].prev_in = -1;
   1.287 -      arcs[e.id].next_in = nodes[n.id].first_in;
   1.288 -      nodes[n.id].first_in = e.id;
   1.289 +      _arcs[e.id].target = n.id;
   1.290 +      _arcs[e.id].prev_in = -1;
   1.291 +      _arcs[e.id].next_in = _nodes[n.id].first_in;
   1.292 +      _nodes[n.id].first_in = e.id;
   1.293      }
   1.294      void changeSource(Arc e, Node n)
   1.295      {
   1.296 -      if(arcs[e.id].next_out != -1)
   1.297 -        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
   1.298 -      if(arcs[e.id].prev_out != -1)
   1.299 -        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
   1.300 -      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
   1.301 -      if (nodes[n.id].first_out != -1) {
   1.302 -        arcs[nodes[n.id].first_out].prev_out = e.id;
   1.303 +      if(_arcs[e.id].next_out != -1)
   1.304 +        _arcs[_arcs[e.id].next_out].prev_out = _arcs[e.id].prev_out;
   1.305 +      if(_arcs[e.id].prev_out != -1)
   1.306 +        _arcs[_arcs[e.id].prev_out].next_out = _arcs[e.id].next_out;
   1.307 +      else _nodes[_arcs[e.id].source].first_out = _arcs[e.id].next_out;
   1.308 +      if (_nodes[n.id].first_out != -1) {
   1.309 +        _arcs[_nodes[n.id].first_out].prev_out = e.id;
   1.310        }
   1.311 -      arcs[e.id].source = n.id;
   1.312 -      arcs[e.id].prev_out = -1;
   1.313 -      arcs[e.id].next_out = nodes[n.id].first_out;
   1.314 -      nodes[n.id].first_out = e.id;
   1.315 +      _arcs[e.id].source = n.id;
   1.316 +      _arcs[e.id].prev_out = -1;
   1.317 +      _arcs[e.id].next_out = _nodes[n.id].first_out;
   1.318 +      _nodes[n.id].first_out = e.id;
   1.319      }
   1.320  
   1.321    };
   1.322 @@ -486,10 +486,10 @@
   1.323      ///Snapshot feature.
   1.324      Node split(Node n, bool connect = true) {
   1.325        Node b = addNode();
   1.326 -      nodes[b.id].first_out=nodes[n.id].first_out;
   1.327 -      nodes[n.id].first_out=-1;
   1.328 -      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
   1.329 -        arcs[i].source=b.id;
   1.330 +      _nodes[b.id].first_out=_nodes[n.id].first_out;
   1.331 +      _nodes[n.id].first_out=-1;
   1.332 +      for(int i=_nodes[b.id].first_out; i!=-1; i=_arcs[i].next_out) {
   1.333 +        _arcs[i].source=b.id;
   1.334        }
   1.335        if (connect) addArc(n,b);
   1.336        return b;
   1.337 @@ -532,7 +532,7 @@
   1.338      /// then it is worth reserving space for this amount before starting
   1.339      /// to build the digraph.
   1.340      /// \sa reserveArc()
   1.341 -    void reserveNode(int n) { nodes.reserve(n); };
   1.342 +    void reserveNode(int n) { _nodes.reserve(n); };
   1.343  
   1.344      /// Reserve memory for arcs.
   1.345  
   1.346 @@ -542,7 +542,7 @@
   1.347      /// then it is worth reserving space for this amount before starting
   1.348      /// to build the digraph.
   1.349      /// \sa reserveNode()
   1.350 -    void reserveArc(int m) { arcs.reserve(m); };
   1.351 +    void reserveArc(int m) { _arcs.reserve(m); };
   1.352  
   1.353      /// \brief Class to make a snapshot of the digraph and restore
   1.354      /// it later.
   1.355 @@ -803,13 +803,13 @@
   1.356        int prev_out, next_out;
   1.357      };
   1.358  
   1.359 -    std::vector<NodeT> nodes;
   1.360 +    std::vector<NodeT> _nodes;
   1.361  
   1.362      int first_node;
   1.363  
   1.364      int first_free_node;
   1.365  
   1.366 -    std::vector<ArcT> arcs;
   1.367 +    std::vector<ArcT> _arcs;
   1.368  
   1.369      int first_free_arc;
   1.370  
   1.371 @@ -867,19 +867,19 @@
   1.372      };
   1.373  
   1.374      ListGraphBase()
   1.375 -      : nodes(), first_node(-1),
   1.376 -        first_free_node(-1), arcs(), first_free_arc(-1) {}
   1.377 -
   1.378 -
   1.379 -    int maxNodeId() const { return nodes.size()-1; }
   1.380 -    int maxEdgeId() const { return arcs.size() / 2 - 1; }
   1.381 -    int maxArcId() const { return arcs.size()-1; }
   1.382 -
   1.383 -    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
   1.384 -    Node target(Arc e) const { return Node(arcs[e.id].target); }
   1.385 -
   1.386 -    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
   1.387 -    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
   1.388 +      : _nodes(), first_node(-1),
   1.389 +        first_free_node(-1), _arcs(), first_free_arc(-1) {}
   1.390 +
   1.391 +
   1.392 +    int maxNodeId() const { return _nodes.size()-1; }
   1.393 +    int maxEdgeId() const { return _arcs.size() / 2 - 1; }
   1.394 +    int maxArcId() const { return _arcs.size()-1; }
   1.395 +
   1.396 +    Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); }
   1.397 +    Node target(Arc e) const { return Node(_arcs[e.id].target); }
   1.398 +
   1.399 +    Node u(Edge e) const { return Node(_arcs[2 * e.id].target); }
   1.400 +    Node v(Edge e) const { return Node(_arcs[2 * e.id + 1].target); }
   1.401  
   1.402      static bool direction(Arc e) {
   1.403        return (e.id & 1) == 1;
   1.404 @@ -894,88 +894,88 @@
   1.405      }
   1.406  
   1.407      void next(Node& node) const {
   1.408 -      node.id = nodes[node.id].next;
   1.409 +      node.id = _nodes[node.id].next;
   1.410      }
   1.411  
   1.412      void first(Arc& e) const {
   1.413        int n = first_node;
   1.414 -      while (n != -1 && nodes[n].first_out == -1) {
   1.415 -        n = nodes[n].next;
   1.416 +      while (n != -1 && _nodes[n].first_out == -1) {
   1.417 +        n = _nodes[n].next;
   1.418        }
   1.419 -      e.id = (n == -1) ? -1 : nodes[n].first_out;
   1.420 +      e.id = (n == -1) ? -1 : _nodes[n].first_out;
   1.421      }
   1.422  
   1.423      void next(Arc& e) const {
   1.424 -      if (arcs[e.id].next_out != -1) {
   1.425 -        e.id = arcs[e.id].next_out;
   1.426 +      if (_arcs[e.id].next_out != -1) {
   1.427 +        e.id = _arcs[e.id].next_out;
   1.428        } else {
   1.429 -        int n = nodes[arcs[e.id ^ 1].target].next;
   1.430 -        while(n != -1 && nodes[n].first_out == -1) {
   1.431 -          n = nodes[n].next;
   1.432 +        int n = _nodes[_arcs[e.id ^ 1].target].next;
   1.433 +        while(n != -1 && _nodes[n].first_out == -1) {
   1.434 +          n = _nodes[n].next;
   1.435          }
   1.436 -        e.id = (n == -1) ? -1 : nodes[n].first_out;
   1.437 +        e.id = (n == -1) ? -1 : _nodes[n].first_out;
   1.438        }
   1.439      }
   1.440  
   1.441      void first(Edge& e) const {
   1.442        int n = first_node;
   1.443        while (n != -1) {
   1.444 -        e.id = nodes[n].first_out;
   1.445 +        e.id = _nodes[n].first_out;
   1.446          while ((e.id & 1) != 1) {
   1.447 -          e.id = arcs[e.id].next_out;
   1.448 +          e.id = _arcs[e.id].next_out;
   1.449          }
   1.450          if (e.id != -1) {
   1.451            e.id /= 2;
   1.452            return;
   1.453          }
   1.454 -        n = nodes[n].next;
   1.455 +        n = _nodes[n].next;
   1.456        }
   1.457        e.id = -1;
   1.458      }
   1.459  
   1.460      void next(Edge& e) const {
   1.461 -      int n = arcs[e.id * 2].target;
   1.462 -      e.id = arcs[(e.id * 2) | 1].next_out;
   1.463 +      int n = _arcs[e.id * 2].target;
   1.464 +      e.id = _arcs[(e.id * 2) | 1].next_out;
   1.465        while ((e.id & 1) != 1) {
   1.466 -        e.id = arcs[e.id].next_out;
   1.467 +        e.id = _arcs[e.id].next_out;
   1.468        }
   1.469        if (e.id != -1) {
   1.470          e.id /= 2;
   1.471          return;
   1.472        }
   1.473 -      n = nodes[n].next;
   1.474 +      n = _nodes[n].next;
   1.475        while (n != -1) {
   1.476 -        e.id = nodes[n].first_out;
   1.477 +        e.id = _nodes[n].first_out;
   1.478          while ((e.id & 1) != 1) {
   1.479 -          e.id = arcs[e.id].next_out;
   1.480 +          e.id = _arcs[e.id].next_out;
   1.481          }
   1.482          if (e.id != -1) {
   1.483            e.id /= 2;
   1.484            return;
   1.485          }
   1.486 -        n = nodes[n].next;
   1.487 +        n = _nodes[n].next;
   1.488        }
   1.489        e.id = -1;
   1.490      }
   1.491  
   1.492      void firstOut(Arc &e, const Node& v) const {
   1.493 -      e.id = nodes[v.id].first_out;
   1.494 +      e.id = _nodes[v.id].first_out;
   1.495      }
   1.496      void nextOut(Arc &e) const {
   1.497 -      e.id = arcs[e.id].next_out;
   1.498 +      e.id = _arcs[e.id].next_out;
   1.499      }
   1.500  
   1.501      void firstIn(Arc &e, const Node& v) const {
   1.502 -      e.id = ((nodes[v.id].first_out) ^ 1);
   1.503 +      e.id = ((_nodes[v.id].first_out) ^ 1);
   1.504        if (e.id == -2) e.id = -1;
   1.505      }
   1.506      void nextIn(Arc &e) const {
   1.507 -      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
   1.508 +      e.id = ((_arcs[e.id ^ 1].next_out) ^ 1);
   1.509        if (e.id == -2) e.id = -1;
   1.510      }
   1.511  
   1.512      void firstInc(Edge &e, bool& d, const Node& v) const {
   1.513 -      int a = nodes[v.id].first_out;
   1.514 +      int a = _nodes[v.id].first_out;
   1.515        if (a != -1 ) {
   1.516          e.id = a / 2;
   1.517          d = ((a & 1) == 1);
   1.518 @@ -985,7 +985,7 @@
   1.519        }
   1.520      }
   1.521      void nextInc(Edge &e, bool& d) const {
   1.522 -      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   1.523 +      int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   1.524        if (a != -1 ) {
   1.525          e.id = a / 2;
   1.526          d = ((a & 1) == 1);
   1.527 @@ -1004,37 +1004,37 @@
   1.528      static Edge edgeFromId(int id) { return Edge(id);}
   1.529  
   1.530      bool valid(Node n) const {
   1.531 -      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
   1.532 -        nodes[n.id].prev != -2;
   1.533 +      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
   1.534 +        _nodes[n.id].prev != -2;
   1.535      }
   1.536  
   1.537      bool valid(Arc a) const {
   1.538 -      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
   1.539 -        arcs[a.id].prev_out != -2;
   1.540 +      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
   1.541 +        _arcs[a.id].prev_out != -2;
   1.542      }
   1.543  
   1.544      bool valid(Edge e) const {
   1.545 -      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
   1.546 -        arcs[2 * e.id].prev_out != -2;
   1.547 +      return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
   1.548 +        _arcs[2 * e.id].prev_out != -2;
   1.549      }
   1.550  
   1.551      Node addNode() {
   1.552        int n;
   1.553  
   1.554        if(first_free_node==-1) {
   1.555 -        n = nodes.size();
   1.556 -        nodes.push_back(NodeT());
   1.557 +        n = _nodes.size();
   1.558 +        _nodes.push_back(NodeT());
   1.559        } else {
   1.560          n = first_free_node;
   1.561 -        first_free_node = nodes[n].next;
   1.562 +        first_free_node = _nodes[n].next;
   1.563        }
   1.564  
   1.565 -      nodes[n].next = first_node;
   1.566 -      if (first_node != -1) nodes[first_node].prev = n;
   1.567 +      _nodes[n].next = first_node;
   1.568 +      if (first_node != -1) _nodes[first_node].prev = n;
   1.569        first_node = n;
   1.570 -      nodes[n].prev = -1;
   1.571 -
   1.572 -      nodes[n].first_out = -1;
   1.573 +      _nodes[n].prev = -1;
   1.574 +
   1.575 +      _nodes[n].first_out = -1;
   1.576  
   1.577        return Node(n);
   1.578      }
   1.579 @@ -1043,30 +1043,30 @@
   1.580        int n;
   1.581  
   1.582        if (first_free_arc == -1) {
   1.583 -        n = arcs.size();
   1.584 -        arcs.push_back(ArcT());
   1.585 -        arcs.push_back(ArcT());
   1.586 +        n = _arcs.size();
   1.587 +        _arcs.push_back(ArcT());
   1.588 +        _arcs.push_back(ArcT());
   1.589        } else {
   1.590          n = first_free_arc;
   1.591 -        first_free_arc = arcs[n].next_out;
   1.592 +        first_free_arc = _arcs[n].next_out;
   1.593        }
   1.594  
   1.595 -      arcs[n].target = u.id;
   1.596 -      arcs[n | 1].target = v.id;
   1.597 -
   1.598 -      arcs[n].next_out = nodes[v.id].first_out;
   1.599 -      if (nodes[v.id].first_out != -1) {
   1.600 -        arcs[nodes[v.id].first_out].prev_out = n;
   1.601 +      _arcs[n].target = u.id;
   1.602 +      _arcs[n | 1].target = v.id;
   1.603 +
   1.604 +      _arcs[n].next_out = _nodes[v.id].first_out;
   1.605 +      if (_nodes[v.id].first_out != -1) {
   1.606 +        _arcs[_nodes[v.id].first_out].prev_out = n;
   1.607        }
   1.608 -      arcs[n].prev_out = -1;
   1.609 -      nodes[v.id].first_out = n;
   1.610 -
   1.611 -      arcs[n | 1].next_out = nodes[u.id].first_out;
   1.612 -      if (nodes[u.id].first_out != -1) {
   1.613 -        arcs[nodes[u.id].first_out].prev_out = (n | 1);
   1.614 +      _arcs[n].prev_out = -1;
   1.615 +      _nodes[v.id].first_out = n;
   1.616 +
   1.617 +      _arcs[n | 1].next_out = _nodes[u.id].first_out;
   1.618 +      if (_nodes[u.id].first_out != -1) {
   1.619 +        _arcs[_nodes[u.id].first_out].prev_out = (n | 1);
   1.620        }
   1.621 -      arcs[n | 1].prev_out = -1;
   1.622 -      nodes[u.id].first_out = (n | 1);
   1.623 +      _arcs[n | 1].prev_out = -1;
   1.624 +      _nodes[u.id].first_out = (n | 1);
   1.625  
   1.626        return Edge(n / 2);
   1.627      }
   1.628 @@ -1074,100 +1074,100 @@
   1.629      void erase(const Node& node) {
   1.630        int n = node.id;
   1.631  
   1.632 -      if(nodes[n].next != -1) {
   1.633 -        nodes[nodes[n].next].prev = nodes[n].prev;
   1.634 +      if(_nodes[n].next != -1) {
   1.635 +        _nodes[_nodes[n].next].prev = _nodes[n].prev;
   1.636        }
   1.637  
   1.638 -      if(nodes[n].prev != -1) {
   1.639 -        nodes[nodes[n].prev].next = nodes[n].next;
   1.640 +      if(_nodes[n].prev != -1) {
   1.641 +        _nodes[_nodes[n].prev].next = _nodes[n].next;
   1.642        } else {
   1.643 -        first_node = nodes[n].next;
   1.644 +        first_node = _nodes[n].next;
   1.645        }
   1.646  
   1.647 -      nodes[n].next = first_free_node;
   1.648 +      _nodes[n].next = first_free_node;
   1.649        first_free_node = n;
   1.650 -      nodes[n].prev = -2;
   1.651 +      _nodes[n].prev = -2;
   1.652      }
   1.653  
   1.654      void erase(const Edge& edge) {
   1.655        int n = edge.id * 2;
   1.656  
   1.657 -      if (arcs[n].next_out != -1) {
   1.658 -        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   1.659 +      if (_arcs[n].next_out != -1) {
   1.660 +        _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
   1.661        }
   1.662  
   1.663 -      if (arcs[n].prev_out != -1) {
   1.664 -        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   1.665 +      if (_arcs[n].prev_out != -1) {
   1.666 +        _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
   1.667        } else {
   1.668 -        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
   1.669 +        _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;
   1.670        }
   1.671  
   1.672 -      if (arcs[n | 1].next_out != -1) {
   1.673 -        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
   1.674 +      if (_arcs[n | 1].next_out != -1) {
   1.675 +        _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;
   1.676        }
   1.677  
   1.678 -      if (arcs[n | 1].prev_out != -1) {
   1.679 -        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
   1.680 +      if (_arcs[n | 1].prev_out != -1) {
   1.681 +        _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;
   1.682        } else {
   1.683 -        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
   1.684 +        _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;
   1.685        }
   1.686  
   1.687 -      arcs[n].next_out = first_free_arc;
   1.688 +      _arcs[n].next_out = first_free_arc;
   1.689        first_free_arc = n;
   1.690 -      arcs[n].prev_out = -2;
   1.691 -      arcs[n | 1].prev_out = -2;
   1.692 +      _arcs[n].prev_out = -2;
   1.693 +      _arcs[n | 1].prev_out = -2;
   1.694  
   1.695      }
   1.696  
   1.697      void clear() {
   1.698 -      arcs.clear();
   1.699 -      nodes.clear();
   1.700 +      _arcs.clear();
   1.701 +      _nodes.clear();
   1.702        first_node = first_free_node = first_free_arc = -1;
   1.703      }
   1.704  
   1.705    protected:
   1.706  
   1.707      void changeV(Edge e, Node n) {
   1.708 -      if(arcs[2 * e.id].next_out != -1) {
   1.709 -        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
   1.710 +      if(_arcs[2 * e.id].next_out != -1) {
   1.711 +        _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;
   1.712        }
   1.713 -      if(arcs[2 * e.id].prev_out != -1) {
   1.714 -        arcs[arcs[2 * e.id].prev_out].next_out =
   1.715 -          arcs[2 * e.id].next_out;
   1.716 +      if(_arcs[2 * e.id].prev_out != -1) {
   1.717 +        _arcs[_arcs[2 * e.id].prev_out].next_out =
   1.718 +          _arcs[2 * e.id].next_out;
   1.719        } else {
   1.720 -        nodes[arcs[(2 * e.id) | 1].target].first_out =
   1.721 -          arcs[2 * e.id].next_out;
   1.722 +        _nodes[_arcs[(2 * e.id) | 1].target].first_out =
   1.723 +          _arcs[2 * e.id].next_out;
   1.724        }
   1.725  
   1.726 -      if (nodes[n.id].first_out != -1) {
   1.727 -        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
   1.728 +      if (_nodes[n.id].first_out != -1) {
   1.729 +        _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;
   1.730        }
   1.731 -      arcs[(2 * e.id) | 1].target = n.id;
   1.732 -      arcs[2 * e.id].prev_out = -1;
   1.733 -      arcs[2 * e.id].next_out = nodes[n.id].first_out;
   1.734 -      nodes[n.id].first_out = 2 * e.id;
   1.735 +      _arcs[(2 * e.id) | 1].target = n.id;
   1.736 +      _arcs[2 * e.id].prev_out = -1;
   1.737 +      _arcs[2 * e.id].next_out = _nodes[n.id].first_out;
   1.738 +      _nodes[n.id].first_out = 2 * e.id;
   1.739      }
   1.740  
   1.741      void changeU(Edge e, Node n) {
   1.742 -      if(arcs[(2 * e.id) | 1].next_out != -1) {
   1.743 -        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
   1.744 -          arcs[(2 * e.id) | 1].prev_out;
   1.745 +      if(_arcs[(2 * e.id) | 1].next_out != -1) {
   1.746 +        _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =
   1.747 +          _arcs[(2 * e.id) | 1].prev_out;
   1.748        }
   1.749 -      if(arcs[(2 * e.id) | 1].prev_out != -1) {
   1.750 -        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
   1.751 -          arcs[(2 * e.id) | 1].next_out;
   1.752 +      if(_arcs[(2 * e.id) | 1].prev_out != -1) {
   1.753 +        _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =
   1.754 +          _arcs[(2 * e.id) | 1].next_out;
   1.755        } else {
   1.756 -        nodes[arcs[2 * e.id].target].first_out =
   1.757 -          arcs[(2 * e.id) | 1].next_out;
   1.758 +        _nodes[_arcs[2 * e.id].target].first_out =
   1.759 +          _arcs[(2 * e.id) | 1].next_out;
   1.760        }
   1.761  
   1.762 -      if (nodes[n.id].first_out != -1) {
   1.763 -        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
   1.764 +      if (_nodes[n.id].first_out != -1) {
   1.765 +        _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
   1.766        }
   1.767 -      arcs[2 * e.id].target = n.id;
   1.768 -      arcs[(2 * e.id) | 1].prev_out = -1;
   1.769 -      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
   1.770 -      nodes[n.id].first_out = ((2 * e.id) | 1);
   1.771 +      _arcs[2 * e.id].target = n.id;
   1.772 +      _arcs[(2 * e.id) | 1].prev_out = -1;
   1.773 +      _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;
   1.774 +      _nodes[n.id].first_out = ((2 * e.id) | 1);
   1.775      }
   1.776  
   1.777    };
   1.778 @@ -1344,7 +1344,7 @@
   1.779      /// then it is worth reserving space for this amount before starting
   1.780      /// to build the graph.
   1.781      /// \sa reserveEdge()
   1.782 -    void reserveNode(int n) { nodes.reserve(n); };
   1.783 +    void reserveNode(int n) { _nodes.reserve(n); };
   1.784  
   1.785      /// Reserve memory for edges.
   1.786  
   1.787 @@ -1354,7 +1354,7 @@
   1.788      /// then it is worth reserving space for this amount before starting
   1.789      /// to build the graph.
   1.790      /// \sa reserveNode()
   1.791 -    void reserveEdge(int m) { arcs.reserve(2 * m); };
   1.792 +    void reserveEdge(int m) { _arcs.reserve(2 * m); };
   1.793  
   1.794      /// \brief Class to make a snapshot of the graph and restore
   1.795      /// it later.
   1.796 @@ -1617,14 +1617,14 @@
   1.797        int prev_out, next_out;
   1.798      };
   1.799  
   1.800 -    std::vector<NodeT> nodes;
   1.801 +    std::vector<NodeT> _nodes;
   1.802  
   1.803      int first_node, first_red, first_blue;
   1.804      int max_red, max_blue;
   1.805  
   1.806      int first_free_red, first_free_blue;
   1.807  
   1.808 -    std::vector<ArcT> arcs;
   1.809 +    std::vector<ArcT> _arcs;
   1.810  
   1.811      int first_free_arc;
   1.812  
   1.813 @@ -1706,33 +1706,33 @@
   1.814      };
   1.815  
   1.816      ListBpGraphBase()
   1.817 -      : nodes(), first_node(-1),
   1.818 +      : _nodes(), first_node(-1),
   1.819          first_red(-1), first_blue(-1),
   1.820          max_red(-1), max_blue(-1),
   1.821          first_free_red(-1), first_free_blue(-1),
   1.822 -        arcs(), first_free_arc(-1) {}
   1.823 -
   1.824 -
   1.825 -    bool red(Node n) const { return nodes[n.id].red; }
   1.826 -    bool blue(Node n) const { return !nodes[n.id].red; }
   1.827 +        _arcs(), first_free_arc(-1) {}
   1.828 +
   1.829 +
   1.830 +    bool red(Node n) const { return _nodes[n.id].red; }
   1.831 +    bool blue(Node n) const { return !_nodes[n.id].red; }
   1.832  
   1.833      static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
   1.834      static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
   1.835  
   1.836 -    int maxNodeId() const { return nodes.size()-1; }
   1.837 +    int maxNodeId() const { return _nodes.size()-1; }
   1.838      int maxRedId() const { return max_red; }
   1.839      int maxBlueId() const { return max_blue; }
   1.840 -    int maxEdgeId() const { return arcs.size() / 2 - 1; }
   1.841 -    int maxArcId() const { return arcs.size()-1; }
   1.842 -
   1.843 -    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
   1.844 -    Node target(Arc e) const { return Node(arcs[e.id].target); }
   1.845 +    int maxEdgeId() const { return _arcs.size() / 2 - 1; }
   1.846 +    int maxArcId() const { return _arcs.size()-1; }
   1.847 +
   1.848 +    Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); }
   1.849 +    Node target(Arc e) const { return Node(_arcs[e.id].target); }
   1.850  
   1.851      RedNode redNode(Edge e) const {
   1.852 -      return RedNode(arcs[2 * e.id].target);
   1.853 +      return RedNode(_arcs[2 * e.id].target);
   1.854      }
   1.855      BlueNode blueNode(Edge e) const {
   1.856 -      return BlueNode(arcs[2 * e.id + 1].target);
   1.857 +      return BlueNode(_arcs[2 * e.id + 1].target);
   1.858      }
   1.859  
   1.860      static bool direction(Arc e) {
   1.861 @@ -1748,7 +1748,7 @@
   1.862      }
   1.863  
   1.864      void next(Node& node) const {
   1.865 -      node.id = nodes[node.id].next;
   1.866 +      node.id = _nodes[node.id].next;
   1.867      }
   1.868  
   1.869      void first(RedNode& node) const {
   1.870 @@ -1756,7 +1756,7 @@
   1.871      }
   1.872  
   1.873      void next(RedNode& node) const {
   1.874 -      node.id = nodes[node.id].partition_next;
   1.875 +      node.id = _nodes[node.id].partition_next;
   1.876      }
   1.877  
   1.878      void first(BlueNode& node) const {
   1.879 @@ -1764,88 +1764,88 @@
   1.880      }
   1.881  
   1.882      void next(BlueNode& node) const {
   1.883 -      node.id = nodes[node.id].partition_next;
   1.884 +      node.id = _nodes[node.id].partition_next;
   1.885      }
   1.886  
   1.887      void first(Arc& e) const {
   1.888        int n = first_node;
   1.889 -      while (n != -1 && nodes[n].first_out == -1) {
   1.890 -        n = nodes[n].next;
   1.891 +      while (n != -1 && _nodes[n].first_out == -1) {
   1.892 +        n = _nodes[n].next;
   1.893        }
   1.894 -      e.id = (n == -1) ? -1 : nodes[n].first_out;
   1.895 +      e.id = (n == -1) ? -1 : _nodes[n].first_out;
   1.896      }
   1.897  
   1.898      void next(Arc& e) const {
   1.899 -      if (arcs[e.id].next_out != -1) {
   1.900 -        e.id = arcs[e.id].next_out;
   1.901 +      if (_arcs[e.id].next_out != -1) {
   1.902 +        e.id = _arcs[e.id].next_out;
   1.903        } else {
   1.904 -        int n = nodes[arcs[e.id ^ 1].target].next;
   1.905 -        while(n != -1 && nodes[n].first_out == -1) {
   1.906 -          n = nodes[n].next;
   1.907 +        int n = _nodes[_arcs[e.id ^ 1].target].next;
   1.908 +        while(n != -1 && _nodes[n].first_out == -1) {
   1.909 +          n = _nodes[n].next;
   1.910          }
   1.911 -        e.id = (n == -1) ? -1 : nodes[n].first_out;
   1.912 +        e.id = (n == -1) ? -1 : _nodes[n].first_out;
   1.913        }
   1.914      }
   1.915  
   1.916      void first(Edge& e) const {
   1.917        int n = first_node;
   1.918        while (n != -1) {
   1.919 -        e.id = nodes[n].first_out;
   1.920 +        e.id = _nodes[n].first_out;
   1.921          while ((e.id & 1) != 1) {
   1.922 -          e.id = arcs[e.id].next_out;
   1.923 +          e.id = _arcs[e.id].next_out;
   1.924          }
   1.925          if (e.id != -1) {
   1.926            e.id /= 2;
   1.927            return;
   1.928          }
   1.929 -        n = nodes[n].next;
   1.930 +        n = _nodes[n].next;
   1.931        }
   1.932        e.id = -1;
   1.933      }
   1.934  
   1.935      void next(Edge& e) const {
   1.936 -      int n = arcs[e.id * 2].target;
   1.937 -      e.id = arcs[(e.id * 2) | 1].next_out;
   1.938 +      int n = _arcs[e.id * 2].target;
   1.939 +      e.id = _arcs[(e.id * 2) | 1].next_out;
   1.940        while ((e.id & 1) != 1) {
   1.941 -        e.id = arcs[e.id].next_out;
   1.942 +        e.id = _arcs[e.id].next_out;
   1.943        }
   1.944        if (e.id != -1) {
   1.945          e.id /= 2;
   1.946          return;
   1.947        }
   1.948 -      n = nodes[n].next;
   1.949 +      n = _nodes[n].next;
   1.950        while (n != -1) {
   1.951 -        e.id = nodes[n].first_out;
   1.952 +        e.id = _nodes[n].first_out;
   1.953          while ((e.id & 1) != 1) {
   1.954 -          e.id = arcs[e.id].next_out;
   1.955 +          e.id = _arcs[e.id].next_out;
   1.956          }
   1.957          if (e.id != -1) {
   1.958            e.id /= 2;
   1.959            return;
   1.960          }
   1.961 -        n = nodes[n].next;
   1.962 +        n = _nodes[n].next;
   1.963        }
   1.964        e.id = -1;
   1.965      }
   1.966  
   1.967      void firstOut(Arc &e, const Node& v) const {
   1.968 -      e.id = nodes[v.id].first_out;
   1.969 +      e.id = _nodes[v.id].first_out;
   1.970      }
   1.971      void nextOut(Arc &e) const {
   1.972 -      e.id = arcs[e.id].next_out;
   1.973 +      e.id = _arcs[e.id].next_out;
   1.974      }
   1.975  
   1.976      void firstIn(Arc &e, const Node& v) const {
   1.977 -      e.id = ((nodes[v.id].first_out) ^ 1);
   1.978 +      e.id = ((_nodes[v.id].first_out) ^ 1);
   1.979        if (e.id == -2) e.id = -1;
   1.980      }
   1.981      void nextIn(Arc &e) const {
   1.982 -      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
   1.983 +      e.id = ((_arcs[e.id ^ 1].next_out) ^ 1);
   1.984        if (e.id == -2) e.id = -1;
   1.985      }
   1.986  
   1.987      void firstInc(Edge &e, bool& d, const Node& v) const {
   1.988 -      int a = nodes[v.id].first_out;
   1.989 +      int a = _nodes[v.id].first_out;
   1.990        if (a != -1 ) {
   1.991          e.id = a / 2;
   1.992          d = ((a & 1) == 1);
   1.993 @@ -1855,7 +1855,7 @@
   1.994        }
   1.995      }
   1.996      void nextInc(Edge &e, bool& d) const {
   1.997 -      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   1.998 +      int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   1.999        if (a != -1 ) {
  1.1000          e.id = a / 2;
  1.1001          d = ((a & 1) == 1);
  1.1002 @@ -1866,8 +1866,8 @@
  1.1003      }
  1.1004  
  1.1005      static int id(Node v) { return v.id; }
  1.1006 -    int id(RedNode v) const { return nodes[v.id].partition_index; }
  1.1007 -    int id(BlueNode v) const { return nodes[v.id].partition_index; }
  1.1008 +    int id(RedNode v) const { return _nodes[v.id].partition_index; }
  1.1009 +    int id(BlueNode v) const { return _nodes[v.id].partition_index; }
  1.1010      static int id(Arc e) { return e.id; }
  1.1011      static int id(Edge e) { return e.id; }
  1.1012  
  1.1013 @@ -1876,44 +1876,44 @@
  1.1014      static Edge edgeFromId(int id) { return Edge(id);}
  1.1015  
  1.1016      bool valid(Node n) const {
  1.1017 -      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
  1.1018 -        nodes[n.id].prev != -2;
  1.1019 +      return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
  1.1020 +        _nodes[n.id].prev != -2;
  1.1021      }
  1.1022  
  1.1023      bool valid(Arc a) const {
  1.1024 -      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
  1.1025 -        arcs[a.id].prev_out != -2;
  1.1026 +      return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
  1.1027 +        _arcs[a.id].prev_out != -2;
  1.1028      }
  1.1029  
  1.1030      bool valid(Edge e) const {
  1.1031 -      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
  1.1032 -        arcs[2 * e.id].prev_out != -2;
  1.1033 +      return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
  1.1034 +        _arcs[2 * e.id].prev_out != -2;
  1.1035      }
  1.1036  
  1.1037      RedNode addRedNode() {
  1.1038        int n;
  1.1039  
  1.1040        if(first_free_red==-1) {
  1.1041 -        n = nodes.size();
  1.1042 -        nodes.push_back(NodeT());
  1.1043 -        nodes[n].partition_index = ++max_red;
  1.1044 -        nodes[n].red = true;
  1.1045 +        n = _nodes.size();
  1.1046 +        _nodes.push_back(NodeT());
  1.1047 +        _nodes[n].partition_index = ++max_red;
  1.1048 +        _nodes[n].red = true;
  1.1049        } else {
  1.1050          n = first_free_red;
  1.1051 -        first_free_red = nodes[n].next;
  1.1052 +        first_free_red = _nodes[n].next;
  1.1053        }
  1.1054  
  1.1055 -      nodes[n].next = first_node;
  1.1056 -      if (first_node != -1) nodes[first_node].prev = n;
  1.1057 +      _nodes[n].next = first_node;
  1.1058 +      if (first_node != -1) _nodes[first_node].prev = n;
  1.1059        first_node = n;
  1.1060 -      nodes[n].prev = -1;
  1.1061 -
  1.1062 -      nodes[n].partition_next = first_red;
  1.1063 -      if (first_red != -1) nodes[first_red].partition_prev = n;
  1.1064 +      _nodes[n].prev = -1;
  1.1065 +
  1.1066 +      _nodes[n].partition_next = first_red;
  1.1067 +      if (first_red != -1) _nodes[first_red].partition_prev = n;
  1.1068        first_red = n;
  1.1069 -      nodes[n].partition_prev = -1;
  1.1070 -
  1.1071 -      nodes[n].first_out = -1;
  1.1072 +      _nodes[n].partition_prev = -1;
  1.1073 +
  1.1074 +      _nodes[n].first_out = -1;
  1.1075  
  1.1076        return RedNode(n);
  1.1077      }
  1.1078 @@ -1922,26 +1922,26 @@
  1.1079        int n;
  1.1080  
  1.1081        if(first_free_blue==-1) {
  1.1082 -        n = nodes.size();
  1.1083 -        nodes.push_back(NodeT());
  1.1084 -        nodes[n].partition_index = ++max_blue;
  1.1085 -        nodes[n].red = false;
  1.1086 +        n = _nodes.size();
  1.1087 +        _nodes.push_back(NodeT());
  1.1088 +        _nodes[n].partition_index = ++max_blue;
  1.1089 +        _nodes[n].red = false;
  1.1090        } else {
  1.1091          n = first_free_blue;
  1.1092 -        first_free_blue = nodes[n].next;
  1.1093 +        first_free_blue = _nodes[n].next;
  1.1094        }
  1.1095  
  1.1096 -      nodes[n].next = first_node;
  1.1097 -      if (first_node != -1) nodes[first_node].prev = n;
  1.1098 +      _nodes[n].next = first_node;
  1.1099 +      if (first_node != -1) _nodes[first_node].prev = n;
  1.1100        first_node = n;
  1.1101 -      nodes[n].prev = -1;
  1.1102 -
  1.1103 -      nodes[n].partition_next = first_blue;
  1.1104 -      if (first_blue != -1) nodes[first_blue].partition_prev = n;
  1.1105 +      _nodes[n].prev = -1;
  1.1106 +
  1.1107 +      _nodes[n].partition_next = first_blue;
  1.1108 +      if (first_blue != -1) _nodes[first_blue].partition_prev = n;
  1.1109        first_blue = n;
  1.1110 -      nodes[n].partition_prev = -1;
  1.1111 -
  1.1112 -      nodes[n].first_out = -1;
  1.1113 +      _nodes[n].partition_prev = -1;
  1.1114 +
  1.1115 +      _nodes[n].first_out = -1;
  1.1116  
  1.1117        return BlueNode(n);
  1.1118      }
  1.1119 @@ -1950,30 +1950,30 @@
  1.1120        int n;
  1.1121  
  1.1122        if (first_free_arc == -1) {
  1.1123 -        n = arcs.size();
  1.1124 -        arcs.push_back(ArcT());
  1.1125 -        arcs.push_back(ArcT());
  1.1126 +        n = _arcs.size();
  1.1127 +        _arcs.push_back(ArcT());
  1.1128 +        _arcs.push_back(ArcT());
  1.1129        } else {
  1.1130          n = first_free_arc;
  1.1131 -        first_free_arc = arcs[n].next_out;
  1.1132 +        first_free_arc = _arcs[n].next_out;
  1.1133        }
  1.1134  
  1.1135 -      arcs[n].target = u.id;
  1.1136 -      arcs[n | 1].target = v.id;
  1.1137 -
  1.1138 -      arcs[n].next_out = nodes[v.id].first_out;
  1.1139 -      if (nodes[v.id].first_out != -1) {
  1.1140 -        arcs[nodes[v.id].first_out].prev_out = n;
  1.1141 +      _arcs[n].target = u.id;
  1.1142 +      _arcs[n | 1].target = v.id;
  1.1143 +
  1.1144 +      _arcs[n].next_out = _nodes[v.id].first_out;
  1.1145 +      if (_nodes[v.id].first_out != -1) {
  1.1146 +        _arcs[_nodes[v.id].first_out].prev_out = n;
  1.1147        }
  1.1148 -      arcs[n].prev_out = -1;
  1.1149 -      nodes[v.id].first_out = n;
  1.1150 -
  1.1151 -      arcs[n | 1].next_out = nodes[u.id].first_out;
  1.1152 -      if (nodes[u.id].first_out != -1) {
  1.1153 -        arcs[nodes[u.id].first_out].prev_out = (n | 1);
  1.1154 +      _arcs[n].prev_out = -1;
  1.1155 +      _nodes[v.id].first_out = n;
  1.1156 +
  1.1157 +      _arcs[n | 1].next_out = _nodes[u.id].first_out;
  1.1158 +      if (_nodes[u.id].first_out != -1) {
  1.1159 +        _arcs[_nodes[u.id].first_out].prev_out = (n | 1);
  1.1160        }
  1.1161 -      arcs[n | 1].prev_out = -1;
  1.1162 -      nodes[u.id].first_out = (n | 1);
  1.1163 +      _arcs[n | 1].prev_out = -1;
  1.1164 +      _nodes[u.id].first_out = (n | 1);
  1.1165  
  1.1166        return Edge(n / 2);
  1.1167      }
  1.1168 @@ -1981,73 +1981,73 @@
  1.1169      void erase(const Node& node) {
  1.1170        int n = node.id;
  1.1171  
  1.1172 -      if(nodes[n].next != -1) {
  1.1173 -        nodes[nodes[n].next].prev = nodes[n].prev;
  1.1174 +      if(_nodes[n].next != -1) {
  1.1175 +        _nodes[_nodes[n].next].prev = _nodes[n].prev;
  1.1176        }
  1.1177  
  1.1178 -      if(nodes[n].prev != -1) {
  1.1179 -        nodes[nodes[n].prev].next = nodes[n].next;
  1.1180 +      if(_nodes[n].prev != -1) {
  1.1181 +        _nodes[_nodes[n].prev].next = _nodes[n].next;
  1.1182        } else {
  1.1183 -        first_node = nodes[n].next;
  1.1184 +        first_node = _nodes[n].next;
  1.1185        }
  1.1186  
  1.1187 -      if (nodes[n].partition_next != -1) {
  1.1188 -        nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
  1.1189 +      if (_nodes[n].partition_next != -1) {
  1.1190 +        _nodes[_nodes[n].partition_next].partition_prev = _nodes[n].partition_prev;
  1.1191        }
  1.1192  
  1.1193 -      if (nodes[n].partition_prev != -1) {
  1.1194 -        nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
  1.1195 +      if (_nodes[n].partition_prev != -1) {
  1.1196 +        _nodes[_nodes[n].partition_prev].partition_next = _nodes[n].partition_next;
  1.1197        } else {
  1.1198 -        if (nodes[n].red) {
  1.1199 -          first_red = nodes[n].partition_next;
  1.1200 +        if (_nodes[n].red) {
  1.1201 +          first_red = _nodes[n].partition_next;
  1.1202          } else {
  1.1203 -          first_blue = nodes[n].partition_next;
  1.1204 +          first_blue = _nodes[n].partition_next;
  1.1205          }
  1.1206        }
  1.1207  
  1.1208 -      if (nodes[n].red) {
  1.1209 -        nodes[n].next = first_free_red;
  1.1210 +      if (_nodes[n].red) {
  1.1211 +        _nodes[n].next = first_free_red;
  1.1212          first_free_red = n;
  1.1213        } else {
  1.1214 -        nodes[n].next = first_free_blue;
  1.1215 +        _nodes[n].next = first_free_blue;
  1.1216          first_free_blue = n;
  1.1217        }
  1.1218 -      nodes[n].prev = -2;
  1.1219 +      _nodes[n].prev = -2;
  1.1220      }
  1.1221  
  1.1222      void erase(const Edge& edge) {
  1.1223        int n = edge.id * 2;
  1.1224  
  1.1225 -      if (arcs[n].next_out != -1) {
  1.1226 -        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
  1.1227 +      if (_arcs[n].next_out != -1) {
  1.1228 +        _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
  1.1229        }
  1.1230  
  1.1231 -      if (arcs[n].prev_out != -1) {
  1.1232 -        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
  1.1233 +      if (_arcs[n].prev_out != -1) {
  1.1234 +        _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
  1.1235        } else {
  1.1236 -        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
  1.1237 +        _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;
  1.1238        }
  1.1239  
  1.1240 -      if (arcs[n | 1].next_out != -1) {
  1.1241 -        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
  1.1242 +      if (_arcs[n | 1].next_out != -1) {
  1.1243 +        _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;
  1.1244        }
  1.1245  
  1.1246 -      if (arcs[n | 1].prev_out != -1) {
  1.1247 -        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
  1.1248 +      if (_arcs[n | 1].prev_out != -1) {
  1.1249 +        _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;
  1.1250        } else {
  1.1251 -        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
  1.1252 +        _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;
  1.1253        }
  1.1254  
  1.1255 -      arcs[n].next_out = first_free_arc;
  1.1256 +      _arcs[n].next_out = first_free_arc;
  1.1257        first_free_arc = n;
  1.1258 -      arcs[n].prev_out = -2;
  1.1259 -      arcs[n | 1].prev_out = -2;
  1.1260 +      _arcs[n].prev_out = -2;
  1.1261 +      _arcs[n | 1].prev_out = -2;
  1.1262  
  1.1263      }
  1.1264  
  1.1265      void clear() {
  1.1266 -      arcs.clear();
  1.1267 -      nodes.clear();
  1.1268 +      _arcs.clear();
  1.1269 +      _nodes.clear();
  1.1270        first_node = first_free_arc = first_red = first_blue =
  1.1271          max_red = max_blue = first_free_red = first_free_blue = -1;
  1.1272      }
  1.1273 @@ -2055,46 +2055,46 @@
  1.1274    protected:
  1.1275  
  1.1276      void changeRed(Edge e, RedNode n) {
  1.1277 -      if(arcs[(2 * e.id) | 1].next_out != -1) {
  1.1278 -        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  1.1279 -          arcs[(2 * e.id) | 1].prev_out;
  1.1280 +      if(_arcs[(2 * e.id) | 1].next_out != -1) {
  1.1281 +        _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =
  1.1282 +          _arcs[(2 * e.id) | 1].prev_out;
  1.1283        }
  1.1284 -      if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1.1285 -        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
  1.1286 -          arcs[(2 * e.id) | 1].next_out;
  1.1287 +      if(_arcs[(2 * e.id) | 1].prev_out != -1) {
  1.1288 +        _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =
  1.1289 +          _arcs[(2 * e.id) | 1].next_out;
  1.1290        } else {
  1.1291 -        nodes[arcs[2 * e.id].target].first_out =
  1.1292 -          arcs[(2 * e.id) | 1].next_out;
  1.1293 +        _nodes[_arcs[2 * e.id].target].first_out =
  1.1294 +          _arcs[(2 * e.id) | 1].next_out;
  1.1295        }
  1.1296  
  1.1297 -      if (nodes[n.id].first_out != -1) {
  1.1298 -        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  1.1299 +      if (_nodes[n.id].first_out != -1) {
  1.1300 +        _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  1.1301        }
  1.1302 -      arcs[2 * e.id].target = n.id;
  1.1303 -      arcs[(2 * e.id) | 1].prev_out = -1;
  1.1304 -      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
  1.1305 -      nodes[n.id].first_out = ((2 * e.id) | 1);
  1.1306 +      _arcs[2 * e.id].target = n.id;
  1.1307 +      _arcs[(2 * e.id) | 1].prev_out = -1;
  1.1308 +      _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;
  1.1309 +      _nodes[n.id].first_out = ((2 * e.id) | 1);
  1.1310      }
  1.1311  
  1.1312      void changeBlue(Edge e, BlueNode n) {
  1.1313 -       if(arcs[2 * e.id].next_out != -1) {
  1.1314 -        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1.1315 +       if(_arcs[2 * e.id].next_out != -1) {
  1.1316 +        _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;
  1.1317        }
  1.1318 -      if(arcs[2 * e.id].prev_out != -1) {
  1.1319 -        arcs[arcs[2 * e.id].prev_out].next_out =
  1.1320 -          arcs[2 * e.id].next_out;
  1.1321 +      if(_arcs[2 * e.id].prev_out != -1) {
  1.1322 +        _arcs[_arcs[2 * e.id].prev_out].next_out =
  1.1323 +          _arcs[2 * e.id].next_out;
  1.1324        } else {
  1.1325 -        nodes[arcs[(2 * e.id) | 1].target].first_out =
  1.1326 -          arcs[2 * e.id].next_out;
  1.1327 +        _nodes[_arcs[(2 * e.id) | 1].target].first_out =
  1.1328 +          _arcs[2 * e.id].next_out;
  1.1329        }
  1.1330  
  1.1331 -      if (nodes[n.id].first_out != -1) {
  1.1332 -        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
  1.1333 +      if (_nodes[n.id].first_out != -1) {
  1.1334 +        _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;
  1.1335        }
  1.1336 -      arcs[(2 * e.id) | 1].target = n.id;
  1.1337 -      arcs[2 * e.id].prev_out = -1;
  1.1338 -      arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1.1339 -      nodes[n.id].first_out = 2 * e.id;
  1.1340 +      _arcs[(2 * e.id) | 1].target = n.id;
  1.1341 +      _arcs[2 * e.id].prev_out = -1;
  1.1342 +      _arcs[2 * e.id].next_out = _nodes[n.id].first_out;
  1.1343 +      _nodes[n.id].first_out = 2 * e.id;
  1.1344      }
  1.1345  
  1.1346    };
  1.1347 @@ -2249,7 +2249,7 @@
  1.1348      /// then it is worth reserving space for this amount before starting
  1.1349      /// to build the graph.
  1.1350      /// \sa reserveEdge()
  1.1351 -    void reserveNode(int n) { nodes.reserve(n); };
  1.1352 +    void reserveNode(int n) { _nodes.reserve(n); };
  1.1353  
  1.1354      /// Reserve memory for edges.
  1.1355  
  1.1356 @@ -2259,7 +2259,7 @@
  1.1357      /// then it is worth reserving space for this amount before starting
  1.1358      /// to build the graph.
  1.1359      /// \sa reserveNode()
  1.1360 -    void reserveEdge(int m) { arcs.reserve(2 * m); };
  1.1361 +    void reserveEdge(int m) { _arcs.reserve(2 * m); };
  1.1362  
  1.1363      /// \brief Class to make a snapshot of the graph and restore
  1.1364      /// it later.