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.