1.1 --- a/lemon/list_graph.h Mon Jul 16 16:21:40 2018 +0200
1.2 +++ b/lemon/list_graph.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2010
1.8 + * Copyright (C) 2003-2013
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -445,7 +445,7 @@
1.13 ///\note The moved arcs are joined to node \c u using changeSource()
1.14 ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
1.15 ///invalidated for the outgoing arcs of node \c v and \c InArcIt
1.16 - ///iterators are invalidated for the incomming arcs of \c v.
1.17 + ///iterators are invalidated for the incoming arcs of \c v.
1.18 ///Moreover all iterators referencing node \c v or the removed
1.19 ///loops are also invalidated. Other iterators remain valid.
1.20 ///
1.21 @@ -582,7 +582,7 @@
1.22 snapshot.addNode(node);
1.23 }
1.24 virtual void add(const std::vector<Node>& nodes) {
1.25 - for (int i = nodes.size() - 1; i >= 0; ++i) {
1.26 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.27 snapshot.addNode(nodes[i]);
1.28 }
1.29 }
1.30 @@ -632,7 +632,7 @@
1.31 snapshot.addArc(arc);
1.32 }
1.33 virtual void add(const std::vector<Arc>& arcs) {
1.34 - for (int i = arcs.size() - 1; i >= 0; ++i) {
1.35 + for (int i = arcs.size() - 1; i >= 0; --i) {
1.36 snapshot.addArc(arcs[i]);
1.37 }
1.38 }
1.39 @@ -1394,7 +1394,7 @@
1.40 snapshot.addNode(node);
1.41 }
1.42 virtual void add(const std::vector<Node>& nodes) {
1.43 - for (int i = nodes.size() - 1; i >= 0; ++i) {
1.44 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.45 snapshot.addNode(nodes[i]);
1.46 }
1.47 }
1.48 @@ -1444,7 +1444,7 @@
1.49 snapshot.addEdge(edge);
1.50 }
1.51 virtual void add(const std::vector<Edge>& edges) {
1.52 - for (int i = edges.size() - 1; i >= 0; ++i) {
1.53 + for (int i = edges.size() - 1; i >= 0; --i) {
1.54 snapshot.addEdge(edges[i]);
1.55 }
1.56 }
1.57 @@ -1599,6 +1599,911 @@
1.58 };
1.59
1.60 /// @}
1.61 +
1.62 + class ListBpGraphBase {
1.63 +
1.64 + protected:
1.65 +
1.66 + struct NodeT {
1.67 + int first_out;
1.68 + int prev, next;
1.69 + int partition_prev, partition_next;
1.70 + int partition_index;
1.71 + bool red;
1.72 + };
1.73 +
1.74 + struct ArcT {
1.75 + int target;
1.76 + int prev_out, next_out;
1.77 + };
1.78 +
1.79 + std::vector<NodeT> nodes;
1.80 +
1.81 + int first_node, first_red, first_blue;
1.82 + int max_red, max_blue;
1.83 +
1.84 + int first_free_red, first_free_blue;
1.85 +
1.86 + std::vector<ArcT> arcs;
1.87 +
1.88 + int first_free_arc;
1.89 +
1.90 + public:
1.91 +
1.92 + typedef ListBpGraphBase BpGraph;
1.93 +
1.94 + class Node {
1.95 + friend class ListBpGraphBase;
1.96 + protected:
1.97 +
1.98 + int id;
1.99 + explicit Node(int pid) { id = pid;}
1.100 +
1.101 + public:
1.102 + Node() {}
1.103 + Node (Invalid) { id = -1; }
1.104 + bool operator==(const Node& node) const {return id == node.id;}
1.105 + bool operator!=(const Node& node) const {return id != node.id;}
1.106 + bool operator<(const Node& node) const {return id < node.id;}
1.107 + };
1.108 +
1.109 + class RedNode : public Node {
1.110 + friend class ListBpGraphBase;
1.111 + protected:
1.112 +
1.113 + explicit RedNode(int pid) : Node(pid) {}
1.114 +
1.115 + public:
1.116 + RedNode() {}
1.117 + RedNode(const RedNode& node) : Node(node) {}
1.118 + RedNode(Invalid) : Node(INVALID){}
1.119 + };
1.120 +
1.121 + class BlueNode : public Node {
1.122 + friend class ListBpGraphBase;
1.123 + protected:
1.124 +
1.125 + explicit BlueNode(int pid) : Node(pid) {}
1.126 +
1.127 + public:
1.128 + BlueNode() {}
1.129 + BlueNode(const BlueNode& node) : Node(node) {}
1.130 + BlueNode(Invalid) : Node(INVALID){}
1.131 + };
1.132 +
1.133 + class Edge {
1.134 + friend class ListBpGraphBase;
1.135 + protected:
1.136 +
1.137 + int id;
1.138 + explicit Edge(int pid) { id = pid;}
1.139 +
1.140 + public:
1.141 + Edge() {}
1.142 + Edge (Invalid) { id = -1; }
1.143 + bool operator==(const Edge& edge) const {return id == edge.id;}
1.144 + bool operator!=(const Edge& edge) const {return id != edge.id;}
1.145 + bool operator<(const Edge& edge) const {return id < edge.id;}
1.146 + };
1.147 +
1.148 + class Arc {
1.149 + friend class ListBpGraphBase;
1.150 + protected:
1.151 +
1.152 + int id;
1.153 + explicit Arc(int pid) { id = pid;}
1.154 +
1.155 + public:
1.156 + operator Edge() const {
1.157 + return id != -1 ? edgeFromId(id / 2) : INVALID;
1.158 + }
1.159 +
1.160 + Arc() {}
1.161 + Arc (Invalid) { id = -1; }
1.162 + bool operator==(const Arc& arc) const {return id == arc.id;}
1.163 + bool operator!=(const Arc& arc) const {return id != arc.id;}
1.164 + bool operator<(const Arc& arc) const {return id < arc.id;}
1.165 + };
1.166 +
1.167 + ListBpGraphBase()
1.168 + : nodes(), first_node(-1),
1.169 + first_red(-1), first_blue(-1),
1.170 + max_red(-1), max_blue(-1),
1.171 + first_free_red(-1), first_free_blue(-1),
1.172 + arcs(), first_free_arc(-1) {}
1.173 +
1.174 +
1.175 + bool red(Node n) const { return nodes[n.id].red; }
1.176 + bool blue(Node n) const { return !nodes[n.id].red; }
1.177 +
1.178 + static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
1.179 + static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
1.180 +
1.181 + int maxNodeId() const { return nodes.size()-1; }
1.182 + int maxRedId() const { return max_red; }
1.183 + int maxBlueId() const { return max_blue; }
1.184 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.185 + int maxArcId() const { return arcs.size()-1; }
1.186 +
1.187 + Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
1.188 + Node target(Arc e) const { return Node(arcs[e.id].target); }
1.189 +
1.190 + RedNode redNode(Edge e) const {
1.191 + return RedNode(arcs[2 * e.id].target);
1.192 + }
1.193 + BlueNode blueNode(Edge e) const {
1.194 + return BlueNode(arcs[2 * e.id + 1].target);
1.195 + }
1.196 +
1.197 + static bool direction(Arc e) {
1.198 + return (e.id & 1) == 1;
1.199 + }
1.200 +
1.201 + static Arc direct(Edge e, bool d) {
1.202 + return Arc(e.id * 2 + (d ? 1 : 0));
1.203 + }
1.204 +
1.205 + void first(Node& node) const {
1.206 + node.id = first_node;
1.207 + }
1.208 +
1.209 + void next(Node& node) const {
1.210 + node.id = nodes[node.id].next;
1.211 + }
1.212 +
1.213 + void first(RedNode& node) const {
1.214 + node.id = first_red;
1.215 + }
1.216 +
1.217 + void next(RedNode& node) const {
1.218 + node.id = nodes[node.id].partition_next;
1.219 + }
1.220 +
1.221 + void first(BlueNode& node) const {
1.222 + node.id = first_blue;
1.223 + }
1.224 +
1.225 + void next(BlueNode& node) const {
1.226 + node.id = nodes[node.id].partition_next;
1.227 + }
1.228 +
1.229 + void first(Arc& e) const {
1.230 + int n = first_node;
1.231 + while (n != -1 && nodes[n].first_out == -1) {
1.232 + n = nodes[n].next;
1.233 + }
1.234 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.235 + }
1.236 +
1.237 + void next(Arc& e) const {
1.238 + if (arcs[e.id].next_out != -1) {
1.239 + e.id = arcs[e.id].next_out;
1.240 + } else {
1.241 + int n = nodes[arcs[e.id ^ 1].target].next;
1.242 + while(n != -1 && nodes[n].first_out == -1) {
1.243 + n = nodes[n].next;
1.244 + }
1.245 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.246 + }
1.247 + }
1.248 +
1.249 + void first(Edge& e) const {
1.250 + int n = first_node;
1.251 + while (n != -1) {
1.252 + e.id = nodes[n].first_out;
1.253 + while ((e.id & 1) != 1) {
1.254 + e.id = arcs[e.id].next_out;
1.255 + }
1.256 + if (e.id != -1) {
1.257 + e.id /= 2;
1.258 + return;
1.259 + }
1.260 + n = nodes[n].next;
1.261 + }
1.262 + e.id = -1;
1.263 + }
1.264 +
1.265 + void next(Edge& e) const {
1.266 + int n = arcs[e.id * 2].target;
1.267 + e.id = arcs[(e.id * 2) | 1].next_out;
1.268 + while ((e.id & 1) != 1) {
1.269 + e.id = arcs[e.id].next_out;
1.270 + }
1.271 + if (e.id != -1) {
1.272 + e.id /= 2;
1.273 + return;
1.274 + }
1.275 + n = nodes[n].next;
1.276 + while (n != -1) {
1.277 + e.id = nodes[n].first_out;
1.278 + while ((e.id & 1) != 1) {
1.279 + e.id = arcs[e.id].next_out;
1.280 + }
1.281 + if (e.id != -1) {
1.282 + e.id /= 2;
1.283 + return;
1.284 + }
1.285 + n = nodes[n].next;
1.286 + }
1.287 + e.id = -1;
1.288 + }
1.289 +
1.290 + void firstOut(Arc &e, const Node& v) const {
1.291 + e.id = nodes[v.id].first_out;
1.292 + }
1.293 + void nextOut(Arc &e) const {
1.294 + e.id = arcs[e.id].next_out;
1.295 + }
1.296 +
1.297 + void firstIn(Arc &e, const Node& v) const {
1.298 + e.id = ((nodes[v.id].first_out) ^ 1);
1.299 + if (e.id == -2) e.id = -1;
1.300 + }
1.301 + void nextIn(Arc &e) const {
1.302 + e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
1.303 + if (e.id == -2) e.id = -1;
1.304 + }
1.305 +
1.306 + void firstInc(Edge &e, bool& d, const Node& v) const {
1.307 + int a = nodes[v.id].first_out;
1.308 + if (a != -1 ) {
1.309 + e.id = a / 2;
1.310 + d = ((a & 1) == 1);
1.311 + } else {
1.312 + e.id = -1;
1.313 + d = true;
1.314 + }
1.315 + }
1.316 + void nextInc(Edge &e, bool& d) const {
1.317 + int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
1.318 + if (a != -1 ) {
1.319 + e.id = a / 2;
1.320 + d = ((a & 1) == 1);
1.321 + } else {
1.322 + e.id = -1;
1.323 + d = true;
1.324 + }
1.325 + }
1.326 +
1.327 + static int id(Node v) { return v.id; }
1.328 + int id(RedNode v) const { return nodes[v.id].partition_index; }
1.329 + int id(BlueNode v) const { return nodes[v.id].partition_index; }
1.330 + static int id(Arc e) { return e.id; }
1.331 + static int id(Edge e) { return e.id; }
1.332 +
1.333 + static Node nodeFromId(int id) { return Node(id);}
1.334 + static Arc arcFromId(int id) { return Arc(id);}
1.335 + static Edge edgeFromId(int id) { return Edge(id);}
1.336 +
1.337 + bool valid(Node n) const {
1.338 + return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
1.339 + nodes[n.id].prev != -2;
1.340 + }
1.341 +
1.342 + bool valid(Arc a) const {
1.343 + return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1.344 + arcs[a.id].prev_out != -2;
1.345 + }
1.346 +
1.347 + bool valid(Edge e) const {
1.348 + return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
1.349 + arcs[2 * e.id].prev_out != -2;
1.350 + }
1.351 +
1.352 + RedNode addRedNode() {
1.353 + int n;
1.354 +
1.355 + if(first_free_red==-1) {
1.356 + n = nodes.size();
1.357 + nodes.push_back(NodeT());
1.358 + nodes[n].partition_index = ++max_red;
1.359 + nodes[n].red = true;
1.360 + } else {
1.361 + n = first_free_red;
1.362 + first_free_red = nodes[n].next;
1.363 + }
1.364 +
1.365 + nodes[n].next = first_node;
1.366 + if (first_node != -1) nodes[first_node].prev = n;
1.367 + first_node = n;
1.368 + nodes[n].prev = -1;
1.369 +
1.370 + nodes[n].partition_next = first_red;
1.371 + if (first_red != -1) nodes[first_red].partition_prev = n;
1.372 + first_red = n;
1.373 + nodes[n].partition_prev = -1;
1.374 +
1.375 + nodes[n].first_out = -1;
1.376 +
1.377 + return RedNode(n);
1.378 + }
1.379 +
1.380 + BlueNode addBlueNode() {
1.381 + int n;
1.382 +
1.383 + if(first_free_blue==-1) {
1.384 + n = nodes.size();
1.385 + nodes.push_back(NodeT());
1.386 + nodes[n].partition_index = ++max_blue;
1.387 + nodes[n].red = false;
1.388 + } else {
1.389 + n = first_free_blue;
1.390 + first_free_blue = nodes[n].next;
1.391 + }
1.392 +
1.393 + nodes[n].next = first_node;
1.394 + if (first_node != -1) nodes[first_node].prev = n;
1.395 + first_node = n;
1.396 + nodes[n].prev = -1;
1.397 +
1.398 + nodes[n].partition_next = first_blue;
1.399 + if (first_blue != -1) nodes[first_blue].partition_prev = n;
1.400 + first_blue = n;
1.401 + nodes[n].partition_prev = -1;
1.402 +
1.403 + nodes[n].first_out = -1;
1.404 +
1.405 + return BlueNode(n);
1.406 + }
1.407 +
1.408 + Edge addEdge(Node u, Node v) {
1.409 + int n;
1.410 +
1.411 + if (first_free_arc == -1) {
1.412 + n = arcs.size();
1.413 + arcs.push_back(ArcT());
1.414 + arcs.push_back(ArcT());
1.415 + } else {
1.416 + n = first_free_arc;
1.417 + first_free_arc = arcs[n].next_out;
1.418 + }
1.419 +
1.420 + arcs[n].target = u.id;
1.421 + arcs[n | 1].target = v.id;
1.422 +
1.423 + arcs[n].next_out = nodes[v.id].first_out;
1.424 + if (nodes[v.id].first_out != -1) {
1.425 + arcs[nodes[v.id].first_out].prev_out = n;
1.426 + }
1.427 + arcs[n].prev_out = -1;
1.428 + nodes[v.id].first_out = n;
1.429 +
1.430 + arcs[n | 1].next_out = nodes[u.id].first_out;
1.431 + if (nodes[u.id].first_out != -1) {
1.432 + arcs[nodes[u.id].first_out].prev_out = (n | 1);
1.433 + }
1.434 + arcs[n | 1].prev_out = -1;
1.435 + nodes[u.id].first_out = (n | 1);
1.436 +
1.437 + return Edge(n / 2);
1.438 + }
1.439 +
1.440 + void erase(const Node& node) {
1.441 + int n = node.id;
1.442 +
1.443 + if(nodes[n].next != -1) {
1.444 + nodes[nodes[n].next].prev = nodes[n].prev;
1.445 + }
1.446 +
1.447 + if(nodes[n].prev != -1) {
1.448 + nodes[nodes[n].prev].next = nodes[n].next;
1.449 + } else {
1.450 + first_node = nodes[n].next;
1.451 + }
1.452 +
1.453 + if (nodes[n].partition_next != -1) {
1.454 + nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
1.455 + }
1.456 +
1.457 + if (nodes[n].partition_prev != -1) {
1.458 + nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
1.459 + } else {
1.460 + if (nodes[n].red) {
1.461 + first_red = nodes[n].partition_next;
1.462 + } else {
1.463 + first_blue = nodes[n].partition_next;
1.464 + }
1.465 + }
1.466 +
1.467 + if (nodes[n].red) {
1.468 + nodes[n].next = first_free_red;
1.469 + first_free_red = n;
1.470 + } else {
1.471 + nodes[n].next = first_free_blue;
1.472 + first_free_blue = n;
1.473 + }
1.474 + nodes[n].prev = -2;
1.475 + }
1.476 +
1.477 + void erase(const Edge& edge) {
1.478 + int n = edge.id * 2;
1.479 +
1.480 + if (arcs[n].next_out != -1) {
1.481 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.482 + }
1.483 +
1.484 + if (arcs[n].prev_out != -1) {
1.485 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.486 + } else {
1.487 + nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1.488 + }
1.489 +
1.490 + if (arcs[n | 1].next_out != -1) {
1.491 + arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1.492 + }
1.493 +
1.494 + if (arcs[n | 1].prev_out != -1) {
1.495 + arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1.496 + } else {
1.497 + nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1.498 + }
1.499 +
1.500 + arcs[n].next_out = first_free_arc;
1.501 + first_free_arc = n;
1.502 + arcs[n].prev_out = -2;
1.503 + arcs[n | 1].prev_out = -2;
1.504 +
1.505 + }
1.506 +
1.507 + void clear() {
1.508 + arcs.clear();
1.509 + nodes.clear();
1.510 + first_node = first_free_arc = first_red = first_blue =
1.511 + max_red = max_blue = first_free_red = first_free_blue = -1;
1.512 + }
1.513 +
1.514 + protected:
1.515 +
1.516 + void changeRed(Edge e, RedNode n) {
1.517 + if(arcs[(2 * e.id) | 1].next_out != -1) {
1.518 + arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1.519 + arcs[(2 * e.id) | 1].prev_out;
1.520 + }
1.521 + if(arcs[(2 * e.id) | 1].prev_out != -1) {
1.522 + arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1.523 + arcs[(2 * e.id) | 1].next_out;
1.524 + } else {
1.525 + nodes[arcs[2 * e.id].target].first_out =
1.526 + arcs[(2 * e.id) | 1].next_out;
1.527 + }
1.528 +
1.529 + if (nodes[n.id].first_out != -1) {
1.530 + arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1.531 + }
1.532 + arcs[2 * e.id].target = n.id;
1.533 + arcs[(2 * e.id) | 1].prev_out = -1;
1.534 + arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1.535 + nodes[n.id].first_out = ((2 * e.id) | 1);
1.536 + }
1.537 +
1.538 + void changeBlue(Edge e, BlueNode n) {
1.539 + if(arcs[2 * e.id].next_out != -1) {
1.540 + arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1.541 + }
1.542 + if(arcs[2 * e.id].prev_out != -1) {
1.543 + arcs[arcs[2 * e.id].prev_out].next_out =
1.544 + arcs[2 * e.id].next_out;
1.545 + } else {
1.546 + nodes[arcs[(2 * e.id) | 1].target].first_out =
1.547 + arcs[2 * e.id].next_out;
1.548 + }
1.549 +
1.550 + if (nodes[n.id].first_out != -1) {
1.551 + arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1.552 + }
1.553 + arcs[(2 * e.id) | 1].target = n.id;
1.554 + arcs[2 * e.id].prev_out = -1;
1.555 + arcs[2 * e.id].next_out = nodes[n.id].first_out;
1.556 + nodes[n.id].first_out = 2 * e.id;
1.557 + }
1.558 +
1.559 + };
1.560 +
1.561 + typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
1.562 +
1.563 +
1.564 + /// \addtogroup graphs
1.565 + /// @{
1.566 +
1.567 + ///A general undirected graph structure.
1.568 +
1.569 + ///\ref ListBpGraph is a versatile and fast undirected graph
1.570 + ///implementation based on linked lists that are stored in
1.571 + ///\c std::vector structures.
1.572 + ///
1.573 + ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
1.574 + ///and it also provides several useful additional functionalities.
1.575 + ///Most of its member functions and nested classes are documented
1.576 + ///only in the concept class.
1.577 + ///
1.578 + ///This class provides only linear time counting for nodes, edges and arcs.
1.579 + ///
1.580 + ///\sa concepts::BpGraph
1.581 + ///\sa ListDigraph
1.582 + class ListBpGraph : public ExtendedListBpGraphBase {
1.583 + typedef ExtendedListBpGraphBase Parent;
1.584 +
1.585 + private:
1.586 + /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
1.587 + ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase() {};
1.588 + /// \brief Assignment of a graph to another one is \e not allowed.
1.589 + /// Use BpGraphCopy instead.
1.590 + void operator=(const ListBpGraph &) {}
1.591 + public:
1.592 + /// Constructor
1.593 +
1.594 + /// Constructor.
1.595 + ///
1.596 + ListBpGraph() {}
1.597 +
1.598 + typedef Parent::OutArcIt IncEdgeIt;
1.599 +
1.600 + /// \brief Add a new red node to the graph.
1.601 + ///
1.602 + /// This function adds a red new node to the graph.
1.603 + /// \return The new node.
1.604 + RedNode addRedNode() { return Parent::addRedNode(); }
1.605 +
1.606 + /// \brief Add a new blue node to the graph.
1.607 + ///
1.608 + /// This function adds a blue new node to the graph.
1.609 + /// \return The new node.
1.610 + BlueNode addBlueNode() { return Parent::addBlueNode(); }
1.611 +
1.612 + /// \brief Add a new edge to the graph.
1.613 + ///
1.614 + /// This function adds a new edge to the graph between nodes
1.615 + /// \c u and \c v with inherent orientation from node \c u to
1.616 + /// node \c v.
1.617 + /// \return The new edge.
1.618 + Edge addEdge(RedNode u, BlueNode v) {
1.619 + return Parent::addEdge(u, v);
1.620 + }
1.621 + Edge addEdge(BlueNode v, RedNode u) {
1.622 + return Parent::addEdge(u, v);
1.623 + }
1.624 +
1.625 + ///\brief Erase a node from the graph.
1.626 + ///
1.627 + /// This function erases the given node along with its incident arcs
1.628 + /// from the graph.
1.629 + ///
1.630 + /// \note All iterators referencing the removed node or the incident
1.631 + /// edges are invalidated, of course.
1.632 + void erase(Node n) { Parent::erase(n); }
1.633 +
1.634 + ///\brief Erase an edge from the graph.
1.635 + ///
1.636 + /// This function erases the given edge from the graph.
1.637 + ///
1.638 + /// \note All iterators referencing the removed edge are invalidated,
1.639 + /// of course.
1.640 + void erase(Edge e) { Parent::erase(e); }
1.641 + /// Node validity check
1.642 +
1.643 + /// This function gives back \c true if the given node is valid,
1.644 + /// i.e. it is a real node of the graph.
1.645 + ///
1.646 + /// \warning A removed node could become valid again if new nodes are
1.647 + /// added to the graph.
1.648 + bool valid(Node n) const { return Parent::valid(n); }
1.649 + /// Edge validity check
1.650 +
1.651 + /// This function gives back \c true if the given edge is valid,
1.652 + /// i.e. it is a real edge of the graph.
1.653 + ///
1.654 + /// \warning A removed edge could become valid again if new edges are
1.655 + /// added to the graph.
1.656 + bool valid(Edge e) const { return Parent::valid(e); }
1.657 + /// Arc validity check
1.658 +
1.659 + /// This function gives back \c true if the given arc is valid,
1.660 + /// i.e. it is a real arc of the graph.
1.661 + ///
1.662 + /// \warning A removed arc could become valid again if new edges are
1.663 + /// added to the graph.
1.664 + bool valid(Arc a) const { return Parent::valid(a); }
1.665 +
1.666 + /// \brief Change the red node of an edge.
1.667 + ///
1.668 + /// This function changes the red node of the given edge \c e to \c n.
1.669 + ///
1.670 + ///\note \c EdgeIt and \c ArcIt iterators referencing the
1.671 + ///changed edge are invalidated and all other iterators whose
1.672 + ///base node is the changed node are also invalidated.
1.673 + ///
1.674 + ///\warning This functionality cannot be used together with the
1.675 + ///Snapshot feature.
1.676 + void changeRed(Edge e, RedNode n) {
1.677 + Parent::changeRed(e, n);
1.678 + }
1.679 + /// \brief Change the blue node of an edge.
1.680 + ///
1.681 + /// This function changes the blue node of the given edge \c e to \c n.
1.682 + ///
1.683 + ///\note \c EdgeIt iterators referencing the changed edge remain
1.684 + ///valid, but \c ArcIt iterators referencing the changed edge and
1.685 + ///all other iterators whose base node is the changed node are also
1.686 + ///invalidated.
1.687 + ///
1.688 + ///\warning This functionality cannot be used together with the
1.689 + ///Snapshot feature.
1.690 + void changeBlue(Edge e, BlueNode n) {
1.691 + Parent::changeBlue(e, n);
1.692 + }
1.693 +
1.694 + ///Clear the graph.
1.695 +
1.696 + ///This function erases all nodes and arcs from the graph.
1.697 + ///
1.698 + ///\note All iterators of the graph are invalidated, of course.
1.699 + void clear() {
1.700 + Parent::clear();
1.701 + }
1.702 +
1.703 + /// Reserve memory for nodes.
1.704 +
1.705 + /// Using this function, it is possible to avoid superfluous memory
1.706 + /// allocation: if you know that the graph you want to build will
1.707 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.708 + /// then it is worth reserving space for this amount before starting
1.709 + /// to build the graph.
1.710 + /// \sa reserveEdge()
1.711 + void reserveNode(int n) { nodes.reserve(n); };
1.712 +
1.713 + /// Reserve memory for edges.
1.714 +
1.715 + /// Using this function, it is possible to avoid superfluous memory
1.716 + /// allocation: if you know that the graph you want to build will
1.717 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.718 + /// then it is worth reserving space for this amount before starting
1.719 + /// to build the graph.
1.720 + /// \sa reserveNode()
1.721 + void reserveEdge(int m) { arcs.reserve(2 * m); };
1.722 +
1.723 + /// \brief Class to make a snapshot of the graph and restore
1.724 + /// it later.
1.725 + ///
1.726 + /// Class to make a snapshot of the graph and restore it later.
1.727 + ///
1.728 + /// The newly added nodes and edges can be removed
1.729 + /// using the restore() function.
1.730 + ///
1.731 + /// \note After a state is restored, you cannot restore a later state,
1.732 + /// i.e. you cannot add the removed nodes and edges again using
1.733 + /// another Snapshot instance.
1.734 + ///
1.735 + /// \warning Node and edge deletions and other modifications
1.736 + /// (e.g. changing the end-nodes of edges or contracting nodes)
1.737 + /// cannot be restored. These events invalidate the snapshot.
1.738 + /// However, the edges and nodes that were added to the graph after
1.739 + /// making the current snapshot can be removed without invalidating it.
1.740 + class Snapshot {
1.741 + protected:
1.742 +
1.743 + typedef Parent::NodeNotifier NodeNotifier;
1.744 +
1.745 + class NodeObserverProxy : public NodeNotifier::ObserverBase {
1.746 + public:
1.747 +
1.748 + NodeObserverProxy(Snapshot& _snapshot)
1.749 + : snapshot(_snapshot) {}
1.750 +
1.751 + using NodeNotifier::ObserverBase::attach;
1.752 + using NodeNotifier::ObserverBase::detach;
1.753 + using NodeNotifier::ObserverBase::attached;
1.754 +
1.755 + protected:
1.756 +
1.757 + virtual void add(const Node& node) {
1.758 + snapshot.addNode(node);
1.759 + }
1.760 + virtual void add(const std::vector<Node>& nodes) {
1.761 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.762 + snapshot.addNode(nodes[i]);
1.763 + }
1.764 + }
1.765 + virtual void erase(const Node& node) {
1.766 + snapshot.eraseNode(node);
1.767 + }
1.768 + virtual void erase(const std::vector<Node>& nodes) {
1.769 + for (int i = 0; i < int(nodes.size()); ++i) {
1.770 + snapshot.eraseNode(nodes[i]);
1.771 + }
1.772 + }
1.773 + virtual void build() {
1.774 + Node node;
1.775 + std::vector<Node> nodes;
1.776 + for (notifier()->first(node); node != INVALID;
1.777 + notifier()->next(node)) {
1.778 + nodes.push_back(node);
1.779 + }
1.780 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.781 + snapshot.addNode(nodes[i]);
1.782 + }
1.783 + }
1.784 + virtual void clear() {
1.785 + Node node;
1.786 + for (notifier()->first(node); node != INVALID;
1.787 + notifier()->next(node)) {
1.788 + snapshot.eraseNode(node);
1.789 + }
1.790 + }
1.791 +
1.792 + Snapshot& snapshot;
1.793 + };
1.794 +
1.795 + class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1.796 + public:
1.797 +
1.798 + EdgeObserverProxy(Snapshot& _snapshot)
1.799 + : snapshot(_snapshot) {}
1.800 +
1.801 + using EdgeNotifier::ObserverBase::attach;
1.802 + using EdgeNotifier::ObserverBase::detach;
1.803 + using EdgeNotifier::ObserverBase::attached;
1.804 +
1.805 + protected:
1.806 +
1.807 + virtual void add(const Edge& edge) {
1.808 + snapshot.addEdge(edge);
1.809 + }
1.810 + virtual void add(const std::vector<Edge>& edges) {
1.811 + for (int i = edges.size() - 1; i >= 0; --i) {
1.812 + snapshot.addEdge(edges[i]);
1.813 + }
1.814 + }
1.815 + virtual void erase(const Edge& edge) {
1.816 + snapshot.eraseEdge(edge);
1.817 + }
1.818 + virtual void erase(const std::vector<Edge>& edges) {
1.819 + for (int i = 0; i < int(edges.size()); ++i) {
1.820 + snapshot.eraseEdge(edges[i]);
1.821 + }
1.822 + }
1.823 + virtual void build() {
1.824 + Edge edge;
1.825 + std::vector<Edge> edges;
1.826 + for (notifier()->first(edge); edge != INVALID;
1.827 + notifier()->next(edge)) {
1.828 + edges.push_back(edge);
1.829 + }
1.830 + for (int i = edges.size() - 1; i >= 0; --i) {
1.831 + snapshot.addEdge(edges[i]);
1.832 + }
1.833 + }
1.834 + virtual void clear() {
1.835 + Edge edge;
1.836 + for (notifier()->first(edge); edge != INVALID;
1.837 + notifier()->next(edge)) {
1.838 + snapshot.eraseEdge(edge);
1.839 + }
1.840 + }
1.841 +
1.842 + Snapshot& snapshot;
1.843 + };
1.844 +
1.845 + ListBpGraph *graph;
1.846 +
1.847 + NodeObserverProxy node_observer_proxy;
1.848 + EdgeObserverProxy edge_observer_proxy;
1.849 +
1.850 + std::list<Node> added_nodes;
1.851 + std::list<Edge> added_edges;
1.852 +
1.853 +
1.854 + void addNode(const Node& node) {
1.855 + added_nodes.push_front(node);
1.856 + }
1.857 + void eraseNode(const Node& node) {
1.858 + std::list<Node>::iterator it =
1.859 + std::find(added_nodes.begin(), added_nodes.end(), node);
1.860 + if (it == added_nodes.end()) {
1.861 + clear();
1.862 + edge_observer_proxy.detach();
1.863 + throw NodeNotifier::ImmediateDetach();
1.864 + } else {
1.865 + added_nodes.erase(it);
1.866 + }
1.867 + }
1.868 +
1.869 + void addEdge(const Edge& edge) {
1.870 + added_edges.push_front(edge);
1.871 + }
1.872 + void eraseEdge(const Edge& edge) {
1.873 + std::list<Edge>::iterator it =
1.874 + std::find(added_edges.begin(), added_edges.end(), edge);
1.875 + if (it == added_edges.end()) {
1.876 + clear();
1.877 + node_observer_proxy.detach();
1.878 + throw EdgeNotifier::ImmediateDetach();
1.879 + } else {
1.880 + added_edges.erase(it);
1.881 + }
1.882 + }
1.883 +
1.884 + void attach(ListBpGraph &_graph) {
1.885 + graph = &_graph;
1.886 + node_observer_proxy.attach(graph->notifier(Node()));
1.887 + edge_observer_proxy.attach(graph->notifier(Edge()));
1.888 + }
1.889 +
1.890 + void detach() {
1.891 + node_observer_proxy.detach();
1.892 + edge_observer_proxy.detach();
1.893 + }
1.894 +
1.895 + bool attached() const {
1.896 + return node_observer_proxy.attached();
1.897 + }
1.898 +
1.899 + void clear() {
1.900 + added_nodes.clear();
1.901 + added_edges.clear();
1.902 + }
1.903 +
1.904 + public:
1.905 +
1.906 + /// \brief Default constructor.
1.907 + ///
1.908 + /// Default constructor.
1.909 + /// You have to call save() to actually make a snapshot.
1.910 + Snapshot()
1.911 + : graph(0), node_observer_proxy(*this),
1.912 + edge_observer_proxy(*this) {}
1.913 +
1.914 + /// \brief Constructor that immediately makes a snapshot.
1.915 + ///
1.916 + /// This constructor immediately makes a snapshot of the given graph.
1.917 + Snapshot(ListBpGraph &gr)
1.918 + : node_observer_proxy(*this),
1.919 + edge_observer_proxy(*this) {
1.920 + attach(gr);
1.921 + }
1.922 +
1.923 + /// \brief Make a snapshot.
1.924 + ///
1.925 + /// This function makes a snapshot of the given graph.
1.926 + /// It can be called more than once. In case of a repeated
1.927 + /// call, the previous snapshot gets lost.
1.928 + void save(ListBpGraph &gr) {
1.929 + if (attached()) {
1.930 + detach();
1.931 + clear();
1.932 + }
1.933 + attach(gr);
1.934 + }
1.935 +
1.936 + /// \brief Undo the changes until the last snapshot.
1.937 + ///
1.938 + /// This function undos the changes until the last snapshot
1.939 + /// created by save() or Snapshot(ListBpGraph&).
1.940 + ///
1.941 + /// \warning This method invalidates the snapshot, i.e. repeated
1.942 + /// restoring is not supported unless you call save() again.
1.943 + void restore() {
1.944 + detach();
1.945 + for(std::list<Edge>::iterator it = added_edges.begin();
1.946 + it != added_edges.end(); ++it) {
1.947 + graph->erase(*it);
1.948 + }
1.949 + for(std::list<Node>::iterator it = added_nodes.begin();
1.950 + it != added_nodes.end(); ++it) {
1.951 + graph->erase(*it);
1.952 + }
1.953 + clear();
1.954 + }
1.955 +
1.956 + /// \brief Returns \c true if the snapshot is valid.
1.957 + ///
1.958 + /// This function returns \c true if the snapshot is valid.
1.959 + bool valid() const {
1.960 + return attached();
1.961 + }
1.962 + };
1.963 + };
1.964 +
1.965 + /// @}
1.966 } //namespace lemon
1.967
1.968