1.1 --- a/lemon/smart_graph.h Thu Apr 02 22:34:03 2015 +0200
1.2 +++ b/lemon/smart_graph.h Sun Jan 05 22:24:56 2014 +0100
1.3 @@ -47,8 +47,8 @@
1.4 ArcT() {}
1.5 };
1.6
1.7 - std::vector<NodeT> nodes;
1.8 - std::vector<ArcT> arcs;
1.9 + std::vector<NodeT> _nodes;
1.10 + std::vector<ArcT> _arcs;
1.11
1.12 public:
1.13
1.14 @@ -59,46 +59,46 @@
1.15
1.16 public:
1.17
1.18 - SmartDigraphBase() : nodes(), arcs() { }
1.19 + SmartDigraphBase() : _nodes(), _arcs() { }
1.20 SmartDigraphBase(const SmartDigraphBase &_g)
1.21 - : nodes(_g.nodes), arcs(_g.arcs) { }
1.22 + : _nodes(_g._nodes), _arcs(_g._arcs) { }
1.23
1.24 typedef True NodeNumTag;
1.25 typedef True ArcNumTag;
1.26
1.27 - int nodeNum() const { return nodes.size(); }
1.28 - int arcNum() const { return arcs.size(); }
1.29 + int nodeNum() const { return _nodes.size(); }
1.30 + int arcNum() const { return _arcs.size(); }
1.31
1.32 - int maxNodeId() const { return nodes.size()-1; }
1.33 - int maxArcId() const { return arcs.size()-1; }
1.34 + int maxNodeId() const { return _nodes.size()-1; }
1.35 + int maxArcId() const { return _arcs.size()-1; }
1.36
1.37 Node addNode() {
1.38 - int n = nodes.size();
1.39 - nodes.push_back(NodeT());
1.40 - nodes[n].first_in = -1;
1.41 - nodes[n].first_out = -1;
1.42 + int n = _nodes.size();
1.43 + _nodes.push_back(NodeT());
1.44 + _nodes[n].first_in = -1;
1.45 + _nodes[n].first_out = -1;
1.46 return Node(n);
1.47 }
1.48
1.49 Arc addArc(Node u, Node v) {
1.50 - int n = arcs.size();
1.51 - arcs.push_back(ArcT());
1.52 - arcs[n].source = u._id;
1.53 - arcs[n].target = v._id;
1.54 - arcs[n].next_out = nodes[u._id].first_out;
1.55 - arcs[n].next_in = nodes[v._id].first_in;
1.56 - nodes[u._id].first_out = nodes[v._id].first_in = n;
1.57 + int n = _arcs.size();
1.58 + _arcs.push_back(ArcT());
1.59 + _arcs[n].source = u._id;
1.60 + _arcs[n].target = v._id;
1.61 + _arcs[n].next_out = _nodes[u._id].first_out;
1.62 + _arcs[n].next_in = _nodes[v._id].first_in;
1.63 + _nodes[u._id].first_out = _nodes[v._id].first_in = n;
1.64
1.65 return Arc(n);
1.66 }
1.67
1.68 void clear() {
1.69 - arcs.clear();
1.70 - nodes.clear();
1.71 + _arcs.clear();
1.72 + _nodes.clear();
1.73 }
1.74
1.75 - Node source(Arc a) const { return Node(arcs[a._id].source); }
1.76 - Node target(Arc a) const { return Node(arcs[a._id].target); }
1.77 + Node source(Arc a) const { return Node(_arcs[a._id].source); }
1.78 + Node target(Arc a) const { return Node(_arcs[a._id].target); }
1.79
1.80 static int id(Node v) { return v._id; }
1.81 static int id(Arc a) { return a._id; }
1.82 @@ -107,10 +107,10 @@
1.83 static Arc arcFromId(int id) { return Arc(id);}
1.84
1.85 bool valid(Node n) const {
1.86 - return n._id >= 0 && n._id < static_cast<int>(nodes.size());
1.87 + return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
1.88 }
1.89 bool valid(Arc a) const {
1.90 - return a._id >= 0 && a._id < static_cast<int>(arcs.size());
1.91 + return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
1.92 }
1.93
1.94 class Node {
1.95 @@ -145,7 +145,7 @@
1.96 };
1.97
1.98 void first(Node& node) const {
1.99 - node._id = nodes.size() - 1;
1.100 + node._id = _nodes.size() - 1;
1.101 }
1.102
1.103 static void next(Node& node) {
1.104 @@ -153,7 +153,7 @@
1.105 }
1.106
1.107 void first(Arc& arc) const {
1.108 - arc._id = arcs.size() - 1;
1.109 + arc._id = _arcs.size() - 1;
1.110 }
1.111
1.112 static void next(Arc& arc) {
1.113 @@ -161,19 +161,19 @@
1.114 }
1.115
1.116 void firstOut(Arc& arc, const Node& node) const {
1.117 - arc._id = nodes[node._id].first_out;
1.118 + arc._id = _nodes[node._id].first_out;
1.119 }
1.120
1.121 void nextOut(Arc& arc) const {
1.122 - arc._id = arcs[arc._id].next_out;
1.123 + arc._id = _arcs[arc._id].next_out;
1.124 }
1.125
1.126 void firstIn(Arc& arc, const Node& node) const {
1.127 - arc._id = nodes[node._id].first_in;
1.128 + arc._id = _nodes[node._id].first_in;
1.129 }
1.130
1.131 void nextIn(Arc& arc) const {
1.132 - arc._id = arcs[arc._id].next_in;
1.133 + arc._id = _arcs[arc._id].next_in;
1.134 }
1.135
1.136 };
1.137 @@ -266,10 +266,10 @@
1.138 Node split(Node n, bool connect = true)
1.139 {
1.140 Node b = addNode();
1.141 - nodes[b._id].first_out=nodes[n._id].first_out;
1.142 - nodes[n._id].first_out=-1;
1.143 - for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
1.144 - arcs[i].source=b._id;
1.145 + _nodes[b._id].first_out=_nodes[n._id].first_out;
1.146 + _nodes[n._id].first_out=-1;
1.147 + for(int i=_nodes[b._id].first_out; i!=-1; i=_arcs[i].next_out) {
1.148 + _arcs[i].source=b._id;
1.149 }
1.150 if(connect) addArc(n,b);
1.151 return b;
1.152 @@ -291,7 +291,7 @@
1.153 /// then it is worth reserving space for this amount before starting
1.154 /// to build the digraph.
1.155 /// \sa reserveArc()
1.156 - void reserveNode(int n) { nodes.reserve(n); };
1.157 + void reserveNode(int n) { _nodes.reserve(n); };
1.158
1.159 /// Reserve memory for arcs.
1.160
1.161 @@ -301,7 +301,7 @@
1.162 /// then it is worth reserving space for this amount before starting
1.163 /// to build the digraph.
1.164 /// \sa reserveNode()
1.165 - void reserveArc(int m) { arcs.reserve(m); };
1.166 + void reserveArc(int m) { _arcs.reserve(m); };
1.167
1.168 public:
1.169
1.170 @@ -311,17 +311,17 @@
1.171
1.172 void restoreSnapshot(const Snapshot &s)
1.173 {
1.174 - while(s.arc_num<arcs.size()) {
1.175 - Arc arc = arcFromId(arcs.size()-1);
1.176 + while(s.arc_num<_arcs.size()) {
1.177 + Arc arc = arcFromId(_arcs.size()-1);
1.178 Parent::notifier(Arc()).erase(arc);
1.179 - nodes[arcs.back().source].first_out=arcs.back().next_out;
1.180 - nodes[arcs.back().target].first_in=arcs.back().next_in;
1.181 - arcs.pop_back();
1.182 + _nodes[_arcs.back().source].first_out=_arcs.back().next_out;
1.183 + _nodes[_arcs.back().target].first_in=_arcs.back().next_in;
1.184 + _arcs.pop_back();
1.185 }
1.186 - while(s.node_num<nodes.size()) {
1.187 - Node node = nodeFromId(nodes.size()-1);
1.188 + while(s.node_num<_nodes.size()) {
1.189 + Node node = nodeFromId(_nodes.size()-1);
1.190 Parent::notifier(Node()).erase(node);
1.191 - nodes.pop_back();
1.192 + _nodes.pop_back();
1.193 }
1.194 }
1.195
1.196 @@ -362,8 +362,8 @@
1.197 ///This constructor immediately makes a snapshot of the given digraph.
1.198 ///
1.199 Snapshot(SmartDigraph &gr) : _graph(&gr) {
1.200 - node_num=_graph->nodes.size();
1.201 - arc_num=_graph->arcs.size();
1.202 + node_num=_graph->_nodes.size();
1.203 + arc_num=_graph->_arcs.size();
1.204 }
1.205
1.206 ///Make a snapshot.
1.207 @@ -373,8 +373,8 @@
1.208 ///call, the previous snapshot gets lost.
1.209 void save(SmartDigraph &gr) {
1.210 _graph=&gr;
1.211 - node_num=_graph->nodes.size();
1.212 - arc_num=_graph->arcs.size();
1.213 + node_num=_graph->_nodes.size();
1.214 + arc_num=_graph->_arcs.size();
1.215 }
1.216
1.217 ///Undo the changes until a snapshot.
1.218 @@ -402,8 +402,8 @@
1.219 int next_out;
1.220 };
1.221
1.222 - std::vector<NodeT> nodes;
1.223 - std::vector<ArcT> arcs;
1.224 + std::vector<NodeT> _nodes;
1.225 + std::vector<ArcT> _arcs;
1.226
1.227 public:
1.228
1.229 @@ -465,25 +465,25 @@
1.230
1.231
1.232 SmartGraphBase()
1.233 - : nodes(), arcs() {}
1.234 + : _nodes(), _arcs() {}
1.235
1.236 typedef True NodeNumTag;
1.237 typedef True EdgeNumTag;
1.238 typedef True ArcNumTag;
1.239
1.240 - int nodeNum() const { return nodes.size(); }
1.241 - int edgeNum() const { return arcs.size() / 2; }
1.242 - int arcNum() const { return arcs.size(); }
1.243 + int nodeNum() const { return _nodes.size(); }
1.244 + int edgeNum() const { return _arcs.size() / 2; }
1.245 + int arcNum() const { return _arcs.size(); }
1.246
1.247 - int maxNodeId() const { return nodes.size()-1; }
1.248 - int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.249 - int maxArcId() const { return arcs.size()-1; }
1.250 + int maxNodeId() const { return _nodes.size()-1; }
1.251 + int maxEdgeId() const { return _arcs.size() / 2 - 1; }
1.252 + int maxArcId() const { return _arcs.size()-1; }
1.253
1.254 - Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
1.255 - Node target(Arc e) const { return Node(arcs[e._id].target); }
1.256 + Node source(Arc e) const { return Node(_arcs[e._id ^ 1].target); }
1.257 + Node target(Arc e) const { return Node(_arcs[e._id].target); }
1.258
1.259 - Node u(Edge e) const { return Node(arcs[2 * e._id].target); }
1.260 - Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
1.261 + Node u(Edge e) const { return Node(_arcs[2 * e._id].target); }
1.262 + Node v(Edge e) const { return Node(_arcs[2 * e._id + 1].target); }
1.263
1.264 static bool direction(Arc e) {
1.265 return (e._id & 1) == 1;
1.266 @@ -494,7 +494,7 @@
1.267 }
1.268
1.269 void first(Node& node) const {
1.270 - node._id = nodes.size() - 1;
1.271 + node._id = _nodes.size() - 1;
1.272 }
1.273
1.274 static void next(Node& node) {
1.275 @@ -502,7 +502,7 @@
1.276 }
1.277
1.278 void first(Arc& arc) const {
1.279 - arc._id = arcs.size() - 1;
1.280 + arc._id = _arcs.size() - 1;
1.281 }
1.282
1.283 static void next(Arc& arc) {
1.284 @@ -510,7 +510,7 @@
1.285 }
1.286
1.287 void first(Edge& arc) const {
1.288 - arc._id = arcs.size() / 2 - 1;
1.289 + arc._id = _arcs.size() / 2 - 1;
1.290 }
1.291
1.292 static void next(Edge& arc) {
1.293 @@ -518,23 +518,23 @@
1.294 }
1.295
1.296 void firstOut(Arc &arc, const Node& v) const {
1.297 - arc._id = nodes[v._id].first_out;
1.298 + arc._id = _nodes[v._id].first_out;
1.299 }
1.300 void nextOut(Arc &arc) const {
1.301 - arc._id = arcs[arc._id].next_out;
1.302 + arc._id = _arcs[arc._id].next_out;
1.303 }
1.304
1.305 void firstIn(Arc &arc, const Node& v) const {
1.306 - arc._id = ((nodes[v._id].first_out) ^ 1);
1.307 + arc._id = ((_nodes[v._id].first_out) ^ 1);
1.308 if (arc._id == -2) arc._id = -1;
1.309 }
1.310 void nextIn(Arc &arc) const {
1.311 - arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
1.312 + arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1);
1.313 if (arc._id == -2) arc._id = -1;
1.314 }
1.315
1.316 void firstInc(Edge &arc, bool& d, const Node& v) const {
1.317 - int de = nodes[v._id].first_out;
1.318 + int de = _nodes[v._id].first_out;
1.319 if (de != -1) {
1.320 arc._id = de / 2;
1.321 d = ((de & 1) == 1);
1.322 @@ -544,7 +544,7 @@
1.323 }
1.324 }
1.325 void nextInc(Edge &arc, bool& d) const {
1.326 - int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
1.327 + int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
1.328 if (de != -1) {
1.329 arc._id = de / 2;
1.330 d = ((de & 1) == 1);
1.331 @@ -563,43 +563,43 @@
1.332 static Edge edgeFromId(int id) { return Edge(id);}
1.333
1.334 bool valid(Node n) const {
1.335 - return n._id >= 0 && n._id < static_cast<int>(nodes.size());
1.336 + return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
1.337 }
1.338 bool valid(Arc a) const {
1.339 - return a._id >= 0 && a._id < static_cast<int>(arcs.size());
1.340 + return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
1.341 }
1.342 bool valid(Edge e) const {
1.343 - return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
1.344 + return e._id >= 0 && 2 * e._id < static_cast<int>(_arcs.size());
1.345 }
1.346
1.347 Node addNode() {
1.348 - int n = nodes.size();
1.349 - nodes.push_back(NodeT());
1.350 - nodes[n].first_out = -1;
1.351 + int n = _nodes.size();
1.352 + _nodes.push_back(NodeT());
1.353 + _nodes[n].first_out = -1;
1.354
1.355 return Node(n);
1.356 }
1.357
1.358 Edge addEdge(Node u, Node v) {
1.359 - int n = arcs.size();
1.360 - arcs.push_back(ArcT());
1.361 - arcs.push_back(ArcT());
1.362 + int n = _arcs.size();
1.363 + _arcs.push_back(ArcT());
1.364 + _arcs.push_back(ArcT());
1.365
1.366 - arcs[n].target = u._id;
1.367 - arcs[n | 1].target = v._id;
1.368 + _arcs[n].target = u._id;
1.369 + _arcs[n | 1].target = v._id;
1.370
1.371 - arcs[n].next_out = nodes[v._id].first_out;
1.372 - nodes[v._id].first_out = n;
1.373 + _arcs[n].next_out = _nodes[v._id].first_out;
1.374 + _nodes[v._id].first_out = n;
1.375
1.376 - arcs[n | 1].next_out = nodes[u._id].first_out;
1.377 - nodes[u._id].first_out = (n | 1);
1.378 + _arcs[n | 1].next_out = _nodes[u._id].first_out;
1.379 + _nodes[u._id].first_out = (n | 1);
1.380
1.381 return Edge(n / 2);
1.382 }
1.383
1.384 void clear() {
1.385 - arcs.clear();
1.386 - nodes.clear();
1.387 + _arcs.clear();
1.388 + _nodes.clear();
1.389 }
1.390
1.391 };
1.392 @@ -701,7 +701,7 @@
1.393 /// then it is worth reserving space for this amount before starting
1.394 /// to build the graph.
1.395 /// \sa reserveEdge()
1.396 - void reserveNode(int n) { nodes.reserve(n); };
1.397 + void reserveNode(int n) { _nodes.reserve(n); };
1.398
1.399 /// Reserve memory for edges.
1.400
1.401 @@ -711,7 +711,7 @@
1.402 /// then it is worth reserving space for this amount before starting
1.403 /// to build the graph.
1.404 /// \sa reserveNode()
1.405 - void reserveEdge(int m) { arcs.reserve(2 * m); };
1.406 + void reserveEdge(int m) { _arcs.reserve(2 * m); };
1.407
1.408 public:
1.409
1.410 @@ -722,30 +722,30 @@
1.411 void saveSnapshot(Snapshot &s)
1.412 {
1.413 s._graph = this;
1.414 - s.node_num = nodes.size();
1.415 - s.arc_num = arcs.size();
1.416 + s.node_num = _nodes.size();
1.417 + s.arc_num = _arcs.size();
1.418 }
1.419
1.420 void restoreSnapshot(const Snapshot &s)
1.421 {
1.422 - while(s.arc_num<arcs.size()) {
1.423 - int n=arcs.size()-1;
1.424 + while(s.arc_num<_arcs.size()) {
1.425 + int n=_arcs.size()-1;
1.426 Edge arc=edgeFromId(n/2);
1.427 Parent::notifier(Edge()).erase(arc);
1.428 std::vector<Arc> dir;
1.429 dir.push_back(arcFromId(n));
1.430 dir.push_back(arcFromId(n-1));
1.431 Parent::notifier(Arc()).erase(dir);
1.432 - nodes[arcs[n-1].target].first_out=arcs[n].next_out;
1.433 - nodes[arcs[n].target].first_out=arcs[n-1].next_out;
1.434 - arcs.pop_back();
1.435 - arcs.pop_back();
1.436 + _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out;
1.437 + _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out;
1.438 + _arcs.pop_back();
1.439 + _arcs.pop_back();
1.440 }
1.441 - while(s.node_num<nodes.size()) {
1.442 - int n=nodes.size()-1;
1.443 + while(s.node_num<_nodes.size()) {
1.444 + int n=_nodes.size()-1;
1.445 Node node = nodeFromId(n);
1.446 Parent::notifier(Node()).erase(node);
1.447 - nodes.pop_back();
1.448 + _nodes.pop_back();
1.449 }
1.450 }
1.451
1.452 @@ -825,8 +825,8 @@
1.453 int next_out;
1.454 };
1.455
1.456 - std::vector<NodeT> nodes;
1.457 - std::vector<ArcT> arcs;
1.458 + std::vector<NodeT> _nodes;
1.459 + std::vector<ArcT> _arcs;
1.460
1.461 int first_red, first_blue;
1.462 int max_red, max_blue;
1.463 @@ -915,39 +915,39 @@
1.464
1.465
1.466 SmartBpGraphBase()
1.467 - : nodes(), arcs(), first_red(-1), first_blue(-1),
1.468 + : _nodes(), _arcs(), first_red(-1), first_blue(-1),
1.469 max_red(-1), max_blue(-1) {}
1.470
1.471 typedef True NodeNumTag;
1.472 typedef True EdgeNumTag;
1.473 typedef True ArcNumTag;
1.474
1.475 - int nodeNum() const { return nodes.size(); }
1.476 + int nodeNum() const { return _nodes.size(); }
1.477 int redNum() const { return max_red + 1; }
1.478 int blueNum() const { return max_blue + 1; }
1.479 - int edgeNum() const { return arcs.size() / 2; }
1.480 - int arcNum() const { return arcs.size(); }
1.481 + int edgeNum() const { return _arcs.size() / 2; }
1.482 + int arcNum() const { return _arcs.size(); }
1.483
1.484 - int maxNodeId() const { return nodes.size()-1; }
1.485 + int maxNodeId() const { return _nodes.size()-1; }
1.486 int maxRedId() const { return max_red; }
1.487 int maxBlueId() const { return max_blue; }
1.488 - int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.489 - int maxArcId() const { return arcs.size()-1; }
1.490 + int maxEdgeId() const { return _arcs.size() / 2 - 1; }
1.491 + int maxArcId() const { return _arcs.size()-1; }
1.492
1.493 - bool red(Node n) const { return nodes[n._id].red; }
1.494 - bool blue(Node n) const { return !nodes[n._id].red; }
1.495 + bool red(Node n) const { return _nodes[n._id].red; }
1.496 + bool blue(Node n) const { return !_nodes[n._id].red; }
1.497
1.498 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
1.499 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
1.500
1.501 - Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
1.502 - Node target(Arc a) const { return Node(arcs[a._id].target); }
1.503 + Node source(Arc a) const { return Node(_arcs[a._id ^ 1].target); }
1.504 + Node target(Arc a) const { return Node(_arcs[a._id].target); }
1.505
1.506 RedNode redNode(Edge e) const {
1.507 - return RedNode(arcs[2 * e._id].target);
1.508 + return RedNode(_arcs[2 * e._id].target);
1.509 }
1.510 BlueNode blueNode(Edge e) const {
1.511 - return BlueNode(arcs[2 * e._id + 1].target);
1.512 + return BlueNode(_arcs[2 * e._id + 1].target);
1.513 }
1.514
1.515 static bool direction(Arc a) {
1.516 @@ -959,7 +959,7 @@
1.517 }
1.518
1.519 void first(Node& node) const {
1.520 - node._id = nodes.size() - 1;
1.521 + node._id = _nodes.size() - 1;
1.522 }
1.523
1.524 static void next(Node& node) {
1.525 @@ -971,7 +971,7 @@
1.526 }
1.527
1.528 void next(RedNode& node) const {
1.529 - node._id = nodes[node._id].partition_next;
1.530 + node._id = _nodes[node._id].partition_next;
1.531 }
1.532
1.533 void first(BlueNode& node) const {
1.534 @@ -979,11 +979,11 @@
1.535 }
1.536
1.537 void next(BlueNode& node) const {
1.538 - node._id = nodes[node._id].partition_next;
1.539 + node._id = _nodes[node._id].partition_next;
1.540 }
1.541
1.542 void first(Arc& arc) const {
1.543 - arc._id = arcs.size() - 1;
1.544 + arc._id = _arcs.size() - 1;
1.545 }
1.546
1.547 static void next(Arc& arc) {
1.548 @@ -991,7 +991,7 @@
1.549 }
1.550
1.551 void first(Edge& arc) const {
1.552 - arc._id = arcs.size() / 2 - 1;
1.553 + arc._id = _arcs.size() / 2 - 1;
1.554 }
1.555
1.556 static void next(Edge& arc) {
1.557 @@ -999,23 +999,23 @@
1.558 }
1.559
1.560 void firstOut(Arc &arc, const Node& v) const {
1.561 - arc._id = nodes[v._id].first_out;
1.562 + arc._id = _nodes[v._id].first_out;
1.563 }
1.564 void nextOut(Arc &arc) const {
1.565 - arc._id = arcs[arc._id].next_out;
1.566 + arc._id = _arcs[arc._id].next_out;
1.567 }
1.568
1.569 void firstIn(Arc &arc, const Node& v) const {
1.570 - arc._id = ((nodes[v._id].first_out) ^ 1);
1.571 + arc._id = ((_nodes[v._id].first_out) ^ 1);
1.572 if (arc._id == -2) arc._id = -1;
1.573 }
1.574 void nextIn(Arc &arc) const {
1.575 - arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
1.576 + arc._id = ((_arcs[arc._id ^ 1].next_out) ^ 1);
1.577 if (arc._id == -2) arc._id = -1;
1.578 }
1.579
1.580 void firstInc(Edge &arc, bool& d, const Node& v) const {
1.581 - int de = nodes[v._id].first_out;
1.582 + int de = _nodes[v._id].first_out;
1.583 if (de != -1) {
1.584 arc._id = de / 2;
1.585 d = ((de & 1) == 1);
1.586 @@ -1025,7 +1025,7 @@
1.587 }
1.588 }
1.589 void nextInc(Edge &arc, bool& d) const {
1.590 - int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
1.591 + int de = (_arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
1.592 if (de != -1) {
1.593 arc._id = de / 2;
1.594 d = ((de & 1) == 1);
1.595 @@ -1036,8 +1036,8 @@
1.596 }
1.597
1.598 static int id(Node v) { return v._id; }
1.599 - int id(RedNode v) const { return nodes[v._id].partition_index; }
1.600 - int id(BlueNode v) const { return nodes[v._id].partition_index; }
1.601 + int id(RedNode v) const { return _nodes[v._id].partition_index; }
1.602 + int id(BlueNode v) const { return _nodes[v._id].partition_index; }
1.603 static int id(Arc e) { return e._id; }
1.604 static int id(Edge e) { return e._id; }
1.605
1.606 @@ -1046,59 +1046,59 @@
1.607 static Edge edgeFromId(int id) { return Edge(id);}
1.608
1.609 bool valid(Node n) const {
1.610 - return n._id >= 0 && n._id < static_cast<int>(nodes.size());
1.611 + return n._id >= 0 && n._id < static_cast<int>(_nodes.size());
1.612 }
1.613 bool valid(Arc a) const {
1.614 - return a._id >= 0 && a._id < static_cast<int>(arcs.size());
1.615 + return a._id >= 0 && a._id < static_cast<int>(_arcs.size());
1.616 }
1.617 bool valid(Edge e) const {
1.618 - return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
1.619 + return e._id >= 0 && 2 * e._id < static_cast<int>(_arcs.size());
1.620 }
1.621
1.622 RedNode addRedNode() {
1.623 - int n = nodes.size();
1.624 - nodes.push_back(NodeT());
1.625 - nodes[n].first_out = -1;
1.626 - nodes[n].red = true;
1.627 - nodes[n].partition_index = ++max_red;
1.628 - nodes[n].partition_next = first_red;
1.629 + int n = _nodes.size();
1.630 + _nodes.push_back(NodeT());
1.631 + _nodes[n].first_out = -1;
1.632 + _nodes[n].red = true;
1.633 + _nodes[n].partition_index = ++max_red;
1.634 + _nodes[n].partition_next = first_red;
1.635 first_red = n;
1.636
1.637 return RedNode(n);
1.638 }
1.639
1.640 BlueNode addBlueNode() {
1.641 - int n = nodes.size();
1.642 - nodes.push_back(NodeT());
1.643 - nodes[n].first_out = -1;
1.644 - nodes[n].red = false;
1.645 - nodes[n].partition_index = ++max_blue;
1.646 - nodes[n].partition_next = first_blue;
1.647 + int n = _nodes.size();
1.648 + _nodes.push_back(NodeT());
1.649 + _nodes[n].first_out = -1;
1.650 + _nodes[n].red = false;
1.651 + _nodes[n].partition_index = ++max_blue;
1.652 + _nodes[n].partition_next = first_blue;
1.653 first_blue = n;
1.654
1.655 return BlueNode(n);
1.656 }
1.657
1.658 Edge addEdge(RedNode u, BlueNode v) {
1.659 - int n = arcs.size();
1.660 - arcs.push_back(ArcT());
1.661 - arcs.push_back(ArcT());
1.662 + int n = _arcs.size();
1.663 + _arcs.push_back(ArcT());
1.664 + _arcs.push_back(ArcT());
1.665
1.666 - arcs[n].target = u._id;
1.667 - arcs[n | 1].target = v._id;
1.668 + _arcs[n].target = u._id;
1.669 + _arcs[n | 1].target = v._id;
1.670
1.671 - arcs[n].next_out = nodes[v._id].first_out;
1.672 - nodes[v._id].first_out = n;
1.673 + _arcs[n].next_out = _nodes[v._id].first_out;
1.674 + _nodes[v._id].first_out = n;
1.675
1.676 - arcs[n | 1].next_out = nodes[u._id].first_out;
1.677 - nodes[u._id].first_out = (n | 1);
1.678 + _arcs[n | 1].next_out = _nodes[u._id].first_out;
1.679 + _nodes[u._id].first_out = (n | 1);
1.680
1.681 return Edge(n / 2);
1.682 }
1.683
1.684 void clear() {
1.685 - arcs.clear();
1.686 - nodes.clear();
1.687 + _arcs.clear();
1.688 + _nodes.clear();
1.689 first_red = -1;
1.690 first_blue = -1;
1.691 max_blue = -1;
1.692 @@ -1213,7 +1213,7 @@
1.693 /// then it is worth reserving space for this amount before starting
1.694 /// to build the graph.
1.695 /// \sa reserveEdge()
1.696 - void reserveNode(int n) { nodes.reserve(n); };
1.697 + void reserveNode(int n) { _nodes.reserve(n); };
1.698
1.699 /// Reserve memory for edges.
1.700
1.701 @@ -1223,7 +1223,7 @@
1.702 /// then it is worth reserving space for this amount before starting
1.703 /// to build the graph.
1.704 /// \sa reserveNode()
1.705 - void reserveEdge(int m) { arcs.reserve(2 * m); };
1.706 + void reserveEdge(int m) { _arcs.reserve(2 * m); };
1.707
1.708 public:
1.709
1.710 @@ -1234,47 +1234,47 @@
1.711 void saveSnapshot(Snapshot &s)
1.712 {
1.713 s._graph = this;
1.714 - s.node_num = nodes.size();
1.715 - s.arc_num = arcs.size();
1.716 + s.node_num = _nodes.size();
1.717 + s.arc_num = _arcs.size();
1.718 }
1.719
1.720 void restoreSnapshot(const Snapshot &s)
1.721 {
1.722 - while(s.arc_num<arcs.size()) {
1.723 - int n=arcs.size()-1;
1.724 + while(s.arc_num<_arcs.size()) {
1.725 + int n=_arcs.size()-1;
1.726 Edge arc=edgeFromId(n/2);
1.727 Parent::notifier(Edge()).erase(arc);
1.728 std::vector<Arc> dir;
1.729 dir.push_back(arcFromId(n));
1.730 dir.push_back(arcFromId(n-1));
1.731 Parent::notifier(Arc()).erase(dir);
1.732 - nodes[arcs[n-1].target].first_out=arcs[n].next_out;
1.733 - nodes[arcs[n].target].first_out=arcs[n-1].next_out;
1.734 - arcs.pop_back();
1.735 - arcs.pop_back();
1.736 + _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out;
1.737 + _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out;
1.738 + _arcs.pop_back();
1.739 + _arcs.pop_back();
1.740 }
1.741 - while(s.node_num<nodes.size()) {
1.742 - int n=nodes.size()-1;
1.743 + while(s.node_num<_nodes.size()) {
1.744 + int n=_nodes.size()-1;
1.745 Node node = nodeFromId(n);
1.746 if (Parent::red(node)) {
1.747 - first_red = nodes[n].partition_next;
1.748 + first_red = _nodes[n].partition_next;
1.749 if (first_red != -1) {
1.750 - max_red = nodes[first_red].partition_index;
1.751 + max_red = _nodes[first_red].partition_index;
1.752 } else {
1.753 max_red = -1;
1.754 }
1.755 Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
1.756 } else {
1.757 - first_blue = nodes[n].partition_next;
1.758 + first_blue = _nodes[n].partition_next;
1.759 if (first_blue != -1) {
1.760 - max_blue = nodes[first_blue].partition_index;
1.761 + max_blue = _nodes[first_blue].partition_index;
1.762 } else {
1.763 max_blue = -1;
1.764 }
1.765 Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
1.766 }
1.767 Parent::notifier(Node()).erase(node);
1.768 - nodes.pop_back();
1.769 + _nodes.pop_back();
1.770 }
1.771 }
1.772