1.1 --- a/lemon/list_graph.h Wed May 06 16:01:26 2015 +0200
1.2 +++ b/lemon/list_graph.h Fri May 22 17:44:29 2015 +0200
1.3 @@ -582,6 +582,1723 @@
1.4 snapshot.addNode(node);
1.5 }
1.6 virtual void add(const std::vector<Node>& nodes) {
1.7 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.8 + snapshot.addNode(nodes[i]);
1.9 + }
1.10 + }
1.11 + virtual void erase(const Node& node) {
1.12 + snapshot.eraseNode(node);
1.13 + }
1.14 + virtual void erase(const std::vector<Node>& nodes) {
1.15 + for (int i = 0; i < int(nodes.size()); ++i) {
1.16 + snapshot.eraseNode(nodes[i]);
1.17 + }
1.18 + }
1.19 + virtual void build() {
1.20 + Node node;
1.21 + std::vector<Node> nodes;
1.22 + for (notifier()->first(node); node != INVALID;
1.23 + notifier()->next(node)) {
1.24 + nodes.push_back(node);
1.25 + }
1.26 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.27 + snapshot.addNode(nodes[i]);
1.28 + }
1.29 + }
1.30 + virtual void clear() {
1.31 + Node node;
1.32 + for (notifier()->first(node); node != INVALID;
1.33 + notifier()->next(node)) {
1.34 + snapshot.eraseNode(node);
1.35 + }
1.36 + }
1.37 +
1.38 + Snapshot& snapshot;
1.39 + };
1.40 +
1.41 + class ArcObserverProxy : public ArcNotifier::ObserverBase {
1.42 + public:
1.43 +
1.44 + ArcObserverProxy(Snapshot& _snapshot)
1.45 + : snapshot(_snapshot) {}
1.46 +
1.47 + using ArcNotifier::ObserverBase::attach;
1.48 + using ArcNotifier::ObserverBase::detach;
1.49 + using ArcNotifier::ObserverBase::attached;
1.50 +
1.51 + protected:
1.52 +
1.53 + virtual void add(const Arc& arc) {
1.54 + snapshot.addArc(arc);
1.55 + }
1.56 + virtual void add(const std::vector<Arc>& arcs) {
1.57 + for (int i = arcs.size() - 1; i >= 0; --i) {
1.58 + snapshot.addArc(arcs[i]);
1.59 + }
1.60 + }
1.61 + virtual void erase(const Arc& arc) {
1.62 + snapshot.eraseArc(arc);
1.63 + }
1.64 + virtual void erase(const std::vector<Arc>& arcs) {
1.65 + for (int i = 0; i < int(arcs.size()); ++i) {
1.66 + snapshot.eraseArc(arcs[i]);
1.67 + }
1.68 + }
1.69 + virtual void build() {
1.70 + Arc arc;
1.71 + std::vector<Arc> arcs;
1.72 + for (notifier()->first(arc); arc != INVALID;
1.73 + notifier()->next(arc)) {
1.74 + arcs.push_back(arc);
1.75 + }
1.76 + for (int i = arcs.size() - 1; i >= 0; --i) {
1.77 + snapshot.addArc(arcs[i]);
1.78 + }
1.79 + }
1.80 + virtual void clear() {
1.81 + Arc arc;
1.82 + for (notifier()->first(arc); arc != INVALID;
1.83 + notifier()->next(arc)) {
1.84 + snapshot.eraseArc(arc);
1.85 + }
1.86 + }
1.87 +
1.88 + Snapshot& snapshot;
1.89 + };
1.90 +
1.91 + ListDigraph *digraph;
1.92 +
1.93 + NodeObserverProxy node_observer_proxy;
1.94 + ArcObserverProxy arc_observer_proxy;
1.95 +
1.96 + std::list<Node> added_nodes;
1.97 + std::list<Arc> added_arcs;
1.98 +
1.99 +
1.100 + void addNode(const Node& node) {
1.101 + added_nodes.push_front(node);
1.102 + }
1.103 + void eraseNode(const Node& node) {
1.104 + std::list<Node>::iterator it =
1.105 + std::find(added_nodes.begin(), added_nodes.end(), node);
1.106 + if (it == added_nodes.end()) {
1.107 + clear();
1.108 + arc_observer_proxy.detach();
1.109 + throw NodeNotifier::ImmediateDetach();
1.110 + } else {
1.111 + added_nodes.erase(it);
1.112 + }
1.113 + }
1.114 +
1.115 + void addArc(const Arc& arc) {
1.116 + added_arcs.push_front(arc);
1.117 + }
1.118 + void eraseArc(const Arc& arc) {
1.119 + std::list<Arc>::iterator it =
1.120 + std::find(added_arcs.begin(), added_arcs.end(), arc);
1.121 + if (it == added_arcs.end()) {
1.122 + clear();
1.123 + node_observer_proxy.detach();
1.124 + throw ArcNotifier::ImmediateDetach();
1.125 + } else {
1.126 + added_arcs.erase(it);
1.127 + }
1.128 + }
1.129 +
1.130 + void attach(ListDigraph &_digraph) {
1.131 + digraph = &_digraph;
1.132 + node_observer_proxy.attach(digraph->notifier(Node()));
1.133 + arc_observer_proxy.attach(digraph->notifier(Arc()));
1.134 + }
1.135 +
1.136 + void detach() {
1.137 + node_observer_proxy.detach();
1.138 + arc_observer_proxy.detach();
1.139 + }
1.140 +
1.141 + bool attached() const {
1.142 + return node_observer_proxy.attached();
1.143 + }
1.144 +
1.145 + void clear() {
1.146 + added_nodes.clear();
1.147 + added_arcs.clear();
1.148 + }
1.149 +
1.150 + public:
1.151 +
1.152 + /// \brief Default constructor.
1.153 + ///
1.154 + /// Default constructor.
1.155 + /// You have to call save() to actually make a snapshot.
1.156 + Snapshot()
1.157 + : digraph(0), node_observer_proxy(*this),
1.158 + arc_observer_proxy(*this) {}
1.159 +
1.160 + /// \brief Constructor that immediately makes a snapshot.
1.161 + ///
1.162 + /// This constructor immediately makes a snapshot of the given digraph.
1.163 + Snapshot(ListDigraph &gr)
1.164 + : node_observer_proxy(*this),
1.165 + arc_observer_proxy(*this) {
1.166 + attach(gr);
1.167 + }
1.168 +
1.169 + /// \brief Make a snapshot.
1.170 + ///
1.171 + /// This function makes a snapshot of the given digraph.
1.172 + /// It can be called more than once. In case of a repeated
1.173 + /// call, the previous snapshot gets lost.
1.174 + void save(ListDigraph &gr) {
1.175 + if (attached()) {
1.176 + detach();
1.177 + clear();
1.178 + }
1.179 + attach(gr);
1.180 + }
1.181 +
1.182 + /// \brief Undo the changes until the last snapshot.
1.183 + ///
1.184 + /// This function undos the changes until the last snapshot
1.185 + /// created by save() or Snapshot(ListDigraph&).
1.186 + ///
1.187 + /// \warning This method invalidates the snapshot, i.e. repeated
1.188 + /// restoring is not supported unless you call save() again.
1.189 + void restore() {
1.190 + detach();
1.191 + for(std::list<Arc>::iterator it = added_arcs.begin();
1.192 + it != added_arcs.end(); ++it) {
1.193 + digraph->erase(*it);
1.194 + }
1.195 + for(std::list<Node>::iterator it = added_nodes.begin();
1.196 + it != added_nodes.end(); ++it) {
1.197 + digraph->erase(*it);
1.198 + }
1.199 + clear();
1.200 + }
1.201 +
1.202 + /// \brief Returns \c true if the snapshot is valid.
1.203 + ///
1.204 + /// This function returns \c true if the snapshot is valid.
1.205 + bool valid() const {
1.206 + return attached();
1.207 + }
1.208 + };
1.209 +
1.210 + };
1.211 +
1.212 + ///@}
1.213 +
1.214 + class ListGraphBase {
1.215 +
1.216 + protected:
1.217 +
1.218 + struct NodeT {
1.219 + int first_out;
1.220 + int prev, next;
1.221 + };
1.222 +
1.223 + struct ArcT {
1.224 + int target;
1.225 + int prev_out, next_out;
1.226 + };
1.227 +
1.228 + std::vector<NodeT> nodes;
1.229 +
1.230 + int first_node;
1.231 +
1.232 + int first_free_node;
1.233 +
1.234 + std::vector<ArcT> arcs;
1.235 +
1.236 + int first_free_arc;
1.237 +
1.238 + public:
1.239 +
1.240 + typedef ListGraphBase Graph;
1.241 +
1.242 + class Node {
1.243 + friend class ListGraphBase;
1.244 + protected:
1.245 +
1.246 + int id;
1.247 + explicit Node(int pid) { id = pid;}
1.248 +
1.249 + public:
1.250 + Node() {}
1.251 + Node (Invalid) { id = -1; }
1.252 + bool operator==(const Node& node) const {return id == node.id;}
1.253 + bool operator!=(const Node& node) const {return id != node.id;}
1.254 + bool operator<(const Node& node) const {return id < node.id;}
1.255 + };
1.256 +
1.257 + class Edge {
1.258 + friend class ListGraphBase;
1.259 + protected:
1.260 +
1.261 + int id;
1.262 + explicit Edge(int pid) { id = pid;}
1.263 +
1.264 + public:
1.265 + Edge() {}
1.266 + Edge (Invalid) { id = -1; }
1.267 + bool operator==(const Edge& edge) const {return id == edge.id;}
1.268 + bool operator!=(const Edge& edge) const {return id != edge.id;}
1.269 + bool operator<(const Edge& edge) const {return id < edge.id;}
1.270 + };
1.271 +
1.272 + class Arc {
1.273 + friend class ListGraphBase;
1.274 + protected:
1.275 +
1.276 + int id;
1.277 + explicit Arc(int pid) { id = pid;}
1.278 +
1.279 + public:
1.280 + operator Edge() const {
1.281 + return id != -1 ? edgeFromId(id / 2) : INVALID;
1.282 + }
1.283 +
1.284 + Arc() {}
1.285 + Arc (Invalid) { id = -1; }
1.286 + bool operator==(const Arc& arc) const {return id == arc.id;}
1.287 + bool operator!=(const Arc& arc) const {return id != arc.id;}
1.288 + bool operator<(const Arc& arc) const {return id < arc.id;}
1.289 + };
1.290 +
1.291 + ListGraphBase()
1.292 + : nodes(), first_node(-1),
1.293 + first_free_node(-1), arcs(), first_free_arc(-1) {}
1.294 +
1.295 +
1.296 + int maxNodeId() const { return nodes.size()-1; }
1.297 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.298 + int maxArcId() const { return arcs.size()-1; }
1.299 +
1.300 + Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
1.301 + Node target(Arc e) const { return Node(arcs[e.id].target); }
1.302 +
1.303 + Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
1.304 + Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
1.305 +
1.306 + static bool direction(Arc e) {
1.307 + return (e.id & 1) == 1;
1.308 + }
1.309 +
1.310 + static Arc direct(Edge e, bool d) {
1.311 + return Arc(e.id * 2 + (d ? 1 : 0));
1.312 + }
1.313 +
1.314 + void first(Node& node) const {
1.315 + node.id = first_node;
1.316 + }
1.317 +
1.318 + void next(Node& node) const {
1.319 + node.id = nodes[node.id].next;
1.320 + }
1.321 +
1.322 + void first(Arc& e) const {
1.323 + int n = first_node;
1.324 + while (n != -1 && nodes[n].first_out == -1) {
1.325 + n = nodes[n].next;
1.326 + }
1.327 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.328 + }
1.329 +
1.330 + void next(Arc& e) const {
1.331 + if (arcs[e.id].next_out != -1) {
1.332 + e.id = arcs[e.id].next_out;
1.333 + } else {
1.334 + int n = nodes[arcs[e.id ^ 1].target].next;
1.335 + while(n != -1 && nodes[n].first_out == -1) {
1.336 + n = nodes[n].next;
1.337 + }
1.338 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.339 + }
1.340 + }
1.341 +
1.342 + void first(Edge& e) const {
1.343 + int n = first_node;
1.344 + while (n != -1) {
1.345 + e.id = nodes[n].first_out;
1.346 + while ((e.id & 1) != 1) {
1.347 + e.id = arcs[e.id].next_out;
1.348 + }
1.349 + if (e.id != -1) {
1.350 + e.id /= 2;
1.351 + return;
1.352 + }
1.353 + n = nodes[n].next;
1.354 + }
1.355 + e.id = -1;
1.356 + }
1.357 +
1.358 + void next(Edge& e) const {
1.359 + int n = arcs[e.id * 2].target;
1.360 + e.id = arcs[(e.id * 2) | 1].next_out;
1.361 + while ((e.id & 1) != 1) {
1.362 + e.id = arcs[e.id].next_out;
1.363 + }
1.364 + if (e.id != -1) {
1.365 + e.id /= 2;
1.366 + return;
1.367 + }
1.368 + n = nodes[n].next;
1.369 + while (n != -1) {
1.370 + e.id = nodes[n].first_out;
1.371 + while ((e.id & 1) != 1) {
1.372 + e.id = arcs[e.id].next_out;
1.373 + }
1.374 + if (e.id != -1) {
1.375 + e.id /= 2;
1.376 + return;
1.377 + }
1.378 + n = nodes[n].next;
1.379 + }
1.380 + e.id = -1;
1.381 + }
1.382 +
1.383 + void firstOut(Arc &e, const Node& v) const {
1.384 + e.id = nodes[v.id].first_out;
1.385 + }
1.386 + void nextOut(Arc &e) const {
1.387 + e.id = arcs[e.id].next_out;
1.388 + }
1.389 +
1.390 + void firstIn(Arc &e, const Node& v) const {
1.391 + e.id = ((nodes[v.id].first_out) ^ 1);
1.392 + if (e.id == -2) e.id = -1;
1.393 + }
1.394 + void nextIn(Arc &e) const {
1.395 + e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
1.396 + if (e.id == -2) e.id = -1;
1.397 + }
1.398 +
1.399 + void firstInc(Edge &e, bool& d, const Node& v) const {
1.400 + int a = nodes[v.id].first_out;
1.401 + if (a != -1 ) {
1.402 + e.id = a / 2;
1.403 + d = ((a & 1) == 1);
1.404 + } else {
1.405 + e.id = -1;
1.406 + d = true;
1.407 + }
1.408 + }
1.409 + void nextInc(Edge &e, bool& d) const {
1.410 + int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
1.411 + if (a != -1 ) {
1.412 + e.id = a / 2;
1.413 + d = ((a & 1) == 1);
1.414 + } else {
1.415 + e.id = -1;
1.416 + d = true;
1.417 + }
1.418 + }
1.419 +
1.420 + static int id(Node v) { return v.id; }
1.421 + static int id(Arc e) { return e.id; }
1.422 + static int id(Edge e) { return e.id; }
1.423 +
1.424 + static Node nodeFromId(int id) { return Node(id);}
1.425 + static Arc arcFromId(int id) { return Arc(id);}
1.426 + static Edge edgeFromId(int id) { return Edge(id);}
1.427 +
1.428 + bool valid(Node n) const {
1.429 + return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
1.430 + nodes[n.id].prev != -2;
1.431 + }
1.432 +
1.433 + bool valid(Arc a) const {
1.434 + return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1.435 + arcs[a.id].prev_out != -2;
1.436 + }
1.437 +
1.438 + bool valid(Edge e) const {
1.439 + return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
1.440 + arcs[2 * e.id].prev_out != -2;
1.441 + }
1.442 +
1.443 + Node addNode() {
1.444 + int n;
1.445 +
1.446 + if(first_free_node==-1) {
1.447 + n = nodes.size();
1.448 + nodes.push_back(NodeT());
1.449 + } else {
1.450 + n = first_free_node;
1.451 + first_free_node = nodes[n].next;
1.452 + }
1.453 +
1.454 + nodes[n].next = first_node;
1.455 + if (first_node != -1) nodes[first_node].prev = n;
1.456 + first_node = n;
1.457 + nodes[n].prev = -1;
1.458 +
1.459 + nodes[n].first_out = -1;
1.460 +
1.461 + return Node(n);
1.462 + }
1.463 +
1.464 + Edge addEdge(Node u, Node v) {
1.465 + int n;
1.466 +
1.467 + if (first_free_arc == -1) {
1.468 + n = arcs.size();
1.469 + arcs.push_back(ArcT());
1.470 + arcs.push_back(ArcT());
1.471 + } else {
1.472 + n = first_free_arc;
1.473 + first_free_arc = arcs[n].next_out;
1.474 + }
1.475 +
1.476 + arcs[n].target = u.id;
1.477 + arcs[n | 1].target = v.id;
1.478 +
1.479 + arcs[n].next_out = nodes[v.id].first_out;
1.480 + if (nodes[v.id].first_out != -1) {
1.481 + arcs[nodes[v.id].first_out].prev_out = n;
1.482 + }
1.483 + arcs[n].prev_out = -1;
1.484 + nodes[v.id].first_out = n;
1.485 +
1.486 + arcs[n | 1].next_out = nodes[u.id].first_out;
1.487 + if (nodes[u.id].first_out != -1) {
1.488 + arcs[nodes[u.id].first_out].prev_out = (n | 1);
1.489 + }
1.490 + arcs[n | 1].prev_out = -1;
1.491 + nodes[u.id].first_out = (n | 1);
1.492 +
1.493 + return Edge(n / 2);
1.494 + }
1.495 +
1.496 + void erase(const Node& node) {
1.497 + int n = node.id;
1.498 +
1.499 + if(nodes[n].next != -1) {
1.500 + nodes[nodes[n].next].prev = nodes[n].prev;
1.501 + }
1.502 +
1.503 + if(nodes[n].prev != -1) {
1.504 + nodes[nodes[n].prev].next = nodes[n].next;
1.505 + } else {
1.506 + first_node = nodes[n].next;
1.507 + }
1.508 +
1.509 + nodes[n].next = first_free_node;
1.510 + first_free_node = n;
1.511 + nodes[n].prev = -2;
1.512 + }
1.513 +
1.514 + void erase(const Edge& edge) {
1.515 + int n = edge.id * 2;
1.516 +
1.517 + if (arcs[n].next_out != -1) {
1.518 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.519 + }
1.520 +
1.521 + if (arcs[n].prev_out != -1) {
1.522 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.523 + } else {
1.524 + nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1.525 + }
1.526 +
1.527 + if (arcs[n | 1].next_out != -1) {
1.528 + arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1.529 + }
1.530 +
1.531 + if (arcs[n | 1].prev_out != -1) {
1.532 + arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1.533 + } else {
1.534 + nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1.535 + }
1.536 +
1.537 + arcs[n].next_out = first_free_arc;
1.538 + first_free_arc = n;
1.539 + arcs[n].prev_out = -2;
1.540 + arcs[n | 1].prev_out = -2;
1.541 +
1.542 + }
1.543 +
1.544 + void clear() {
1.545 + arcs.clear();
1.546 + nodes.clear();
1.547 + first_node = first_free_node = first_free_arc = -1;
1.548 + }
1.549 +
1.550 + protected:
1.551 +
1.552 + void changeV(Edge e, Node n) {
1.553 + if(arcs[2 * e.id].next_out != -1) {
1.554 + arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1.555 + }
1.556 + if(arcs[2 * e.id].prev_out != -1) {
1.557 + arcs[arcs[2 * e.id].prev_out].next_out =
1.558 + arcs[2 * e.id].next_out;
1.559 + } else {
1.560 + nodes[arcs[(2 * e.id) | 1].target].first_out =
1.561 + arcs[2 * e.id].next_out;
1.562 + }
1.563 +
1.564 + if (nodes[n.id].first_out != -1) {
1.565 + arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1.566 + }
1.567 + arcs[(2 * e.id) | 1].target = n.id;
1.568 + arcs[2 * e.id].prev_out = -1;
1.569 + arcs[2 * e.id].next_out = nodes[n.id].first_out;
1.570 + nodes[n.id].first_out = 2 * e.id;
1.571 + }
1.572 +
1.573 + void changeU(Edge e, Node n) {
1.574 + if(arcs[(2 * e.id) | 1].next_out != -1) {
1.575 + arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1.576 + arcs[(2 * e.id) | 1].prev_out;
1.577 + }
1.578 + if(arcs[(2 * e.id) | 1].prev_out != -1) {
1.579 + arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1.580 + arcs[(2 * e.id) | 1].next_out;
1.581 + } else {
1.582 + nodes[arcs[2 * e.id].target].first_out =
1.583 + arcs[(2 * e.id) | 1].next_out;
1.584 + }
1.585 +
1.586 + if (nodes[n.id].first_out != -1) {
1.587 + arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1.588 + }
1.589 + arcs[2 * e.id].target = n.id;
1.590 + arcs[(2 * e.id) | 1].prev_out = -1;
1.591 + arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1.592 + nodes[n.id].first_out = ((2 * e.id) | 1);
1.593 + }
1.594 +
1.595 + };
1.596 +
1.597 + typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
1.598 +
1.599 +
1.600 + /// \addtogroup graphs
1.601 + /// @{
1.602 +
1.603 + ///A general undirected graph structure.
1.604 +
1.605 + ///\ref ListGraph is a versatile and fast undirected graph
1.606 + ///implementation based on linked lists that are stored in
1.607 + ///\c std::vector structures.
1.608 + ///
1.609 + ///This type fully conforms to the \ref concepts::Graph "Graph concept"
1.610 + ///and it also provides several useful additional functionalities.
1.611 + ///Most of its member functions and nested classes are documented
1.612 + ///only in the concept class.
1.613 + ///
1.614 + ///This class provides only linear time counting for nodes, edges and arcs.
1.615 + ///
1.616 + ///\sa concepts::Graph
1.617 + ///\sa ListDigraph
1.618 + class ListGraph : public ExtendedListGraphBase {
1.619 + typedef ExtendedListGraphBase Parent;
1.620 +
1.621 + private:
1.622 + /// Graphs are \e not copy constructible. Use GraphCopy instead.
1.623 + ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
1.624 + /// \brief Assignment of a graph to another one is \e not allowed.
1.625 + /// Use GraphCopy instead.
1.626 + void operator=(const ListGraph &) {}
1.627 + public:
1.628 + /// Constructor
1.629 +
1.630 + /// Constructor.
1.631 + ///
1.632 + ListGraph() {}
1.633 +
1.634 + typedef Parent::OutArcIt IncEdgeIt;
1.635 +
1.636 + /// \brief Add a new node to the graph.
1.637 + ///
1.638 + /// This function adds a new node to the graph.
1.639 + /// \return The new node.
1.640 + Node addNode() { return Parent::addNode(); }
1.641 +
1.642 + /// \brief Add a new edge to the graph.
1.643 + ///
1.644 + /// This function adds a new edge to the graph between nodes
1.645 + /// \c u and \c v with inherent orientation from node \c u to
1.646 + /// node \c v.
1.647 + /// \return The new edge.
1.648 + Edge addEdge(Node u, Node v) {
1.649 + return Parent::addEdge(u, v);
1.650 + }
1.651 +
1.652 + ///\brief Erase a node from the graph.
1.653 + ///
1.654 + /// This function erases the given node along with its incident arcs
1.655 + /// from the graph.
1.656 + ///
1.657 + /// \note All iterators referencing the removed node or the incident
1.658 + /// edges are invalidated, of course.
1.659 + void erase(Node n) { Parent::erase(n); }
1.660 +
1.661 + ///\brief Erase an edge from the graph.
1.662 + ///
1.663 + /// This function erases the given edge from the graph.
1.664 + ///
1.665 + /// \note All iterators referencing the removed edge are invalidated,
1.666 + /// of course.
1.667 + void erase(Edge e) { Parent::erase(e); }
1.668 + /// Node validity check
1.669 +
1.670 + /// This function gives back \c true if the given node is valid,
1.671 + /// i.e. it is a real node of the graph.
1.672 + ///
1.673 + /// \warning A removed node could become valid again if new nodes are
1.674 + /// added to the graph.
1.675 + bool valid(Node n) const { return Parent::valid(n); }
1.676 + /// Edge validity check
1.677 +
1.678 + /// This function gives back \c true if the given edge is valid,
1.679 + /// i.e. it is a real edge of the graph.
1.680 + ///
1.681 + /// \warning A removed edge could become valid again if new edges are
1.682 + /// added to the graph.
1.683 + bool valid(Edge e) const { return Parent::valid(e); }
1.684 + /// Arc validity check
1.685 +
1.686 + /// This function gives back \c true if the given arc is valid,
1.687 + /// i.e. it is a real arc of the graph.
1.688 + ///
1.689 + /// \warning A removed arc could become valid again if new edges are
1.690 + /// added to the graph.
1.691 + bool valid(Arc a) const { return Parent::valid(a); }
1.692 +
1.693 + /// \brief Change the first node of an edge.
1.694 + ///
1.695 + /// This function changes the first node of the given edge \c e to \c n.
1.696 + ///
1.697 + ///\note \c EdgeIt and \c ArcIt iterators referencing the
1.698 + ///changed edge are invalidated and all other iterators whose
1.699 + ///base node is the changed node are also invalidated.
1.700 + ///
1.701 + ///\warning This functionality cannot be used together with the
1.702 + ///Snapshot feature.
1.703 + void changeU(Edge e, Node n) {
1.704 + Parent::changeU(e,n);
1.705 + }
1.706 + /// \brief Change the second node of an edge.
1.707 + ///
1.708 + /// This function changes the second node of the given edge \c e to \c n.
1.709 + ///
1.710 + ///\note \c EdgeIt iterators referencing the changed edge remain
1.711 + ///valid, but \c ArcIt iterators referencing the changed edge and
1.712 + ///all other iterators whose base node is the changed node are also
1.713 + ///invalidated.
1.714 + ///
1.715 + ///\warning This functionality cannot be used together with the
1.716 + ///Snapshot feature.
1.717 + void changeV(Edge e, Node n) {
1.718 + Parent::changeV(e,n);
1.719 + }
1.720 +
1.721 + /// \brief Contract two nodes.
1.722 + ///
1.723 + /// This function contracts the given two nodes.
1.724 + /// Node \c b is removed, but instead of deleting
1.725 + /// its incident edges, they are joined to node \c a.
1.726 + /// If the last parameter \c r is \c true (this is the default value),
1.727 + /// then the newly created loops are removed.
1.728 + ///
1.729 + /// \note The moved edges are joined to node \c a using changeU()
1.730 + /// or changeV(), thus all edge and arc iterators whose base node is
1.731 + /// \c b are invalidated.
1.732 + /// Moreover all iterators referencing node \c b or the removed
1.733 + /// loops are also invalidated. Other iterators remain valid.
1.734 + ///
1.735 + ///\warning This functionality cannot be used together with the
1.736 + ///Snapshot feature.
1.737 + void contract(Node a, Node b, bool r = true) {
1.738 + for(IncEdgeIt e(*this, b); e!=INVALID;) {
1.739 + IncEdgeIt f = e; ++f;
1.740 + if (r && runningNode(e) == a) {
1.741 + erase(e);
1.742 + } else if (u(e) == b) {
1.743 + changeU(e, a);
1.744 + } else {
1.745 + changeV(e, a);
1.746 + }
1.747 + e = f;
1.748 + }
1.749 + erase(b);
1.750 + }
1.751 +
1.752 + ///Clear the graph.
1.753 +
1.754 + ///This function erases all nodes and arcs from the graph.
1.755 + ///
1.756 + ///\note All iterators of the graph are invalidated, of course.
1.757 + void clear() {
1.758 + Parent::clear();
1.759 + }
1.760 +
1.761 + /// Reserve memory for nodes.
1.762 +
1.763 + /// Using this function, it is possible to avoid superfluous memory
1.764 + /// allocation: if you know that the graph you want to build will
1.765 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.766 + /// then it is worth reserving space for this amount before starting
1.767 + /// to build the graph.
1.768 + /// \sa reserveEdge()
1.769 + void reserveNode(int n) { nodes.reserve(n); };
1.770 +
1.771 + /// Reserve memory for edges.
1.772 +
1.773 + /// Using this function, it is possible to avoid superfluous memory
1.774 + /// allocation: if you know that the graph you want to build will
1.775 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.776 + /// then it is worth reserving space for this amount before starting
1.777 + /// to build the graph.
1.778 + /// \sa reserveNode()
1.779 + void reserveEdge(int m) { arcs.reserve(2 * m); };
1.780 +
1.781 + /// \brief Class to make a snapshot of the graph and restore
1.782 + /// it later.
1.783 + ///
1.784 + /// Class to make a snapshot of the graph and restore it later.
1.785 + ///
1.786 + /// The newly added nodes and edges can be removed
1.787 + /// using the restore() function.
1.788 + ///
1.789 + /// \note After a state is restored, you cannot restore a later state,
1.790 + /// i.e. you cannot add the removed nodes and edges again using
1.791 + /// another Snapshot instance.
1.792 + ///
1.793 + /// \warning Node and edge deletions and other modifications
1.794 + /// (e.g. changing the end-nodes of edges or contracting nodes)
1.795 + /// cannot be restored. These events invalidate the snapshot.
1.796 + /// However, the edges and nodes that were added to the graph after
1.797 + /// making the current snapshot can be removed without invalidating it.
1.798 + class Snapshot {
1.799 + protected:
1.800 +
1.801 + typedef Parent::NodeNotifier NodeNotifier;
1.802 +
1.803 + class NodeObserverProxy : public NodeNotifier::ObserverBase {
1.804 + public:
1.805 +
1.806 + NodeObserverProxy(Snapshot& _snapshot)
1.807 + : snapshot(_snapshot) {}
1.808 +
1.809 + using NodeNotifier::ObserverBase::attach;
1.810 + using NodeNotifier::ObserverBase::detach;
1.811 + using NodeNotifier::ObserverBase::attached;
1.812 +
1.813 + protected:
1.814 +
1.815 + virtual void add(const Node& node) {
1.816 + snapshot.addNode(node);
1.817 + }
1.818 + virtual void add(const std::vector<Node>& nodes) {
1.819 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.820 + snapshot.addNode(nodes[i]);
1.821 + }
1.822 + }
1.823 + virtual void erase(const Node& node) {
1.824 + snapshot.eraseNode(node);
1.825 + }
1.826 + virtual void erase(const std::vector<Node>& nodes) {
1.827 + for (int i = 0; i < int(nodes.size()); ++i) {
1.828 + snapshot.eraseNode(nodes[i]);
1.829 + }
1.830 + }
1.831 + virtual void build() {
1.832 + Node node;
1.833 + std::vector<Node> nodes;
1.834 + for (notifier()->first(node); node != INVALID;
1.835 + notifier()->next(node)) {
1.836 + nodes.push_back(node);
1.837 + }
1.838 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.839 + snapshot.addNode(nodes[i]);
1.840 + }
1.841 + }
1.842 + virtual void clear() {
1.843 + Node node;
1.844 + for (notifier()->first(node); node != INVALID;
1.845 + notifier()->next(node)) {
1.846 + snapshot.eraseNode(node);
1.847 + }
1.848 + }
1.849 +
1.850 + Snapshot& snapshot;
1.851 + };
1.852 +
1.853 + class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1.854 + public:
1.855 +
1.856 + EdgeObserverProxy(Snapshot& _snapshot)
1.857 + : snapshot(_snapshot) {}
1.858 +
1.859 + using EdgeNotifier::ObserverBase::attach;
1.860 + using EdgeNotifier::ObserverBase::detach;
1.861 + using EdgeNotifier::ObserverBase::attached;
1.862 +
1.863 + protected:
1.864 +
1.865 + virtual void add(const Edge& edge) {
1.866 + snapshot.addEdge(edge);
1.867 + }
1.868 + virtual void add(const std::vector<Edge>& edges) {
1.869 + for (int i = edges.size() - 1; i >= 0; --i) {
1.870 + snapshot.addEdge(edges[i]);
1.871 + }
1.872 + }
1.873 + virtual void erase(const Edge& edge) {
1.874 + snapshot.eraseEdge(edge);
1.875 + }
1.876 + virtual void erase(const std::vector<Edge>& edges) {
1.877 + for (int i = 0; i < int(edges.size()); ++i) {
1.878 + snapshot.eraseEdge(edges[i]);
1.879 + }
1.880 + }
1.881 + virtual void build() {
1.882 + Edge edge;
1.883 + std::vector<Edge> edges;
1.884 + for (notifier()->first(edge); edge != INVALID;
1.885 + notifier()->next(edge)) {
1.886 + edges.push_back(edge);
1.887 + }
1.888 + for (int i = edges.size() - 1; i >= 0; --i) {
1.889 + snapshot.addEdge(edges[i]);
1.890 + }
1.891 + }
1.892 + virtual void clear() {
1.893 + Edge edge;
1.894 + for (notifier()->first(edge); edge != INVALID;
1.895 + notifier()->next(edge)) {
1.896 + snapshot.eraseEdge(edge);
1.897 + }
1.898 + }
1.899 +
1.900 + Snapshot& snapshot;
1.901 + };
1.902 +
1.903 + ListGraph *graph;
1.904 +
1.905 + NodeObserverProxy node_observer_proxy;
1.906 + EdgeObserverProxy edge_observer_proxy;
1.907 +
1.908 + std::list<Node> added_nodes;
1.909 + std::list<Edge> added_edges;
1.910 +
1.911 +
1.912 + void addNode(const Node& node) {
1.913 + added_nodes.push_front(node);
1.914 + }
1.915 + void eraseNode(const Node& node) {
1.916 + std::list<Node>::iterator it =
1.917 + std::find(added_nodes.begin(), added_nodes.end(), node);
1.918 + if (it == added_nodes.end()) {
1.919 + clear();
1.920 + edge_observer_proxy.detach();
1.921 + throw NodeNotifier::ImmediateDetach();
1.922 + } else {
1.923 + added_nodes.erase(it);
1.924 + }
1.925 + }
1.926 +
1.927 + void addEdge(const Edge& edge) {
1.928 + added_edges.push_front(edge);
1.929 + }
1.930 + void eraseEdge(const Edge& edge) {
1.931 + std::list<Edge>::iterator it =
1.932 + std::find(added_edges.begin(), added_edges.end(), edge);
1.933 + if (it == added_edges.end()) {
1.934 + clear();
1.935 + node_observer_proxy.detach();
1.936 + throw EdgeNotifier::ImmediateDetach();
1.937 + } else {
1.938 + added_edges.erase(it);
1.939 + }
1.940 + }
1.941 +
1.942 + void attach(ListGraph &_graph) {
1.943 + graph = &_graph;
1.944 + node_observer_proxy.attach(graph->notifier(Node()));
1.945 + edge_observer_proxy.attach(graph->notifier(Edge()));
1.946 + }
1.947 +
1.948 + void detach() {
1.949 + node_observer_proxy.detach();
1.950 + edge_observer_proxy.detach();
1.951 + }
1.952 +
1.953 + bool attached() const {
1.954 + return node_observer_proxy.attached();
1.955 + }
1.956 +
1.957 + void clear() {
1.958 + added_nodes.clear();
1.959 + added_edges.clear();
1.960 + }
1.961 +
1.962 + public:
1.963 +
1.964 + /// \brief Default constructor.
1.965 + ///
1.966 + /// Default constructor.
1.967 + /// You have to call save() to actually make a snapshot.
1.968 + Snapshot()
1.969 + : graph(0), node_observer_proxy(*this),
1.970 + edge_observer_proxy(*this) {}
1.971 +
1.972 + /// \brief Constructor that immediately makes a snapshot.
1.973 + ///
1.974 + /// This constructor immediately makes a snapshot of the given graph.
1.975 + Snapshot(ListGraph &gr)
1.976 + : node_observer_proxy(*this),
1.977 + edge_observer_proxy(*this) {
1.978 + attach(gr);
1.979 + }
1.980 +
1.981 + /// \brief Make a snapshot.
1.982 + ///
1.983 + /// This function makes a snapshot of the given graph.
1.984 + /// It can be called more than once. In case of a repeated
1.985 + /// call, the previous snapshot gets lost.
1.986 + void save(ListGraph &gr) {
1.987 + if (attached()) {
1.988 + detach();
1.989 + clear();
1.990 + }
1.991 + attach(gr);
1.992 + }
1.993 +
1.994 + /// \brief Undo the changes until the last snapshot.
1.995 + ///
1.996 + /// This function undos the changes until the last snapshot
1.997 + /// created by save() or Snapshot(ListGraph&).
1.998 + ///
1.999 + /// \warning This method invalidates the snapshot, i.e. repeated
1.1000 + /// restoring is not supported unless you call save() again.
1.1001 + void restore() {
1.1002 + detach();
1.1003 + for(std::list<Edge>::iterator it = added_edges.begin();
1.1004 + it != added_edges.end(); ++it) {
1.1005 + graph->erase(*it);
1.1006 + }
1.1007 + for(std::list<Node>::iterator it = added_nodes.begin();
1.1008 + it != added_nodes.end(); ++it) {
1.1009 + graph->erase(*it);
1.1010 + }
1.1011 + clear();
1.1012 + }
1.1013 +
1.1014 + /// \brief Returns \c true if the snapshot is valid.
1.1015 + ///
1.1016 + /// This function returns \c true if the snapshot is valid.
1.1017 + bool valid() const {
1.1018 + return attached();
1.1019 + }
1.1020 + };
1.1021 + };
1.1022 +
1.1023 + /// @}
1.1024 +
1.1025 + class ListBpGraphBase {
1.1026 +
1.1027 + protected:
1.1028 +
1.1029 + struct NodeT {
1.1030 + int first_out;
1.1031 + int prev, next;
1.1032 + int partition_prev, partition_next;
1.1033 + int partition_index;
1.1034 + bool red;
1.1035 + };
1.1036 +
1.1037 + struct ArcT {
1.1038 + int target;
1.1039 + int prev_out, next_out;
1.1040 + };
1.1041 +
1.1042 + std::vector<NodeT> nodes;
1.1043 +
1.1044 + int first_node, first_red, first_blue;
1.1045 + int max_red, max_blue;
1.1046 +
1.1047 + int first_free_red, first_free_blue;
1.1048 +
1.1049 + std::vector<ArcT> arcs;
1.1050 +
1.1051 + int first_free_arc;
1.1052 +
1.1053 + public:
1.1054 +
1.1055 + typedef ListBpGraphBase BpGraph;
1.1056 +
1.1057 + class Node {
1.1058 + friend class ListBpGraphBase;
1.1059 + protected:
1.1060 +
1.1061 + int id;
1.1062 + explicit Node(int pid) { id = pid;}
1.1063 +
1.1064 + public:
1.1065 + Node() {}
1.1066 + Node (Invalid) { id = -1; }
1.1067 + bool operator==(const Node& node) const {return id == node.id;}
1.1068 + bool operator!=(const Node& node) const {return id != node.id;}
1.1069 + bool operator<(const Node& node) const {return id < node.id;}
1.1070 + };
1.1071 +
1.1072 + class RedNode : public Node {
1.1073 + friend class ListBpGraphBase;
1.1074 + protected:
1.1075 +
1.1076 + explicit RedNode(int pid) : Node(pid) {}
1.1077 +
1.1078 + public:
1.1079 + RedNode() {}
1.1080 + RedNode(const RedNode& node) : Node(node) {}
1.1081 + RedNode(Invalid) : Node(INVALID){}
1.1082 + };
1.1083 +
1.1084 + class BlueNode : public Node {
1.1085 + friend class ListBpGraphBase;
1.1086 + protected:
1.1087 +
1.1088 + explicit BlueNode(int pid) : Node(pid) {}
1.1089 +
1.1090 + public:
1.1091 + BlueNode() {}
1.1092 + BlueNode(const BlueNode& node) : Node(node) {}
1.1093 + BlueNode(Invalid) : Node(INVALID){}
1.1094 + };
1.1095 +
1.1096 + class Edge {
1.1097 + friend class ListBpGraphBase;
1.1098 + protected:
1.1099 +
1.1100 + int id;
1.1101 + explicit Edge(int pid) { id = pid;}
1.1102 +
1.1103 + public:
1.1104 + Edge() {}
1.1105 + Edge (Invalid) { id = -1; }
1.1106 + bool operator==(const Edge& edge) const {return id == edge.id;}
1.1107 + bool operator!=(const Edge& edge) const {return id != edge.id;}
1.1108 + bool operator<(const Edge& edge) const {return id < edge.id;}
1.1109 + };
1.1110 +
1.1111 + class Arc {
1.1112 + friend class ListBpGraphBase;
1.1113 + protected:
1.1114 +
1.1115 + int id;
1.1116 + explicit Arc(int pid) { id = pid;}
1.1117 +
1.1118 + public:
1.1119 + operator Edge() const {
1.1120 + return id != -1 ? edgeFromId(id / 2) : INVALID;
1.1121 + }
1.1122 +
1.1123 + Arc() {}
1.1124 + Arc (Invalid) { id = -1; }
1.1125 + bool operator==(const Arc& arc) const {return id == arc.id;}
1.1126 + bool operator!=(const Arc& arc) const {return id != arc.id;}
1.1127 + bool operator<(const Arc& arc) const {return id < arc.id;}
1.1128 + };
1.1129 +
1.1130 + ListBpGraphBase()
1.1131 + : nodes(), first_node(-1),
1.1132 + first_red(-1), first_blue(-1),
1.1133 + max_red(-1), max_blue(-1),
1.1134 + first_free_red(-1), first_free_blue(-1),
1.1135 + arcs(), first_free_arc(-1) {}
1.1136 +
1.1137 +
1.1138 + bool red(Node n) const { return nodes[n.id].red; }
1.1139 + bool blue(Node n) const { return !nodes[n.id].red; }
1.1140 +
1.1141 + static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
1.1142 + static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
1.1143 +
1.1144 + int maxNodeId() const { return nodes.size()-1; }
1.1145 + int maxRedId() const { return max_red; }
1.1146 + int maxBlueId() const { return max_blue; }
1.1147 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.1148 + int maxArcId() const { return arcs.size()-1; }
1.1149 +
1.1150 + Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
1.1151 + Node target(Arc e) const { return Node(arcs[e.id].target); }
1.1152 +
1.1153 + RedNode redNode(Edge e) const {
1.1154 + return RedNode(arcs[2 * e.id].target);
1.1155 + }
1.1156 + BlueNode blueNode(Edge e) const {
1.1157 + return BlueNode(arcs[2 * e.id + 1].target);
1.1158 + }
1.1159 +
1.1160 + static bool direction(Arc e) {
1.1161 + return (e.id & 1) == 1;
1.1162 + }
1.1163 +
1.1164 + static Arc direct(Edge e, bool d) {
1.1165 + return Arc(e.id * 2 + (d ? 1 : 0));
1.1166 + }
1.1167 +
1.1168 + void first(Node& node) const {
1.1169 + node.id = first_node;
1.1170 + }
1.1171 +
1.1172 + void next(Node& node) const {
1.1173 + node.id = nodes[node.id].next;
1.1174 + }
1.1175 +
1.1176 + void first(RedNode& node) const {
1.1177 + node.id = first_red;
1.1178 + }
1.1179 +
1.1180 + void next(RedNode& node) const {
1.1181 + node.id = nodes[node.id].partition_next;
1.1182 + }
1.1183 +
1.1184 + void first(BlueNode& node) const {
1.1185 + node.id = first_blue;
1.1186 + }
1.1187 +
1.1188 + void next(BlueNode& node) const {
1.1189 + node.id = nodes[node.id].partition_next;
1.1190 + }
1.1191 +
1.1192 + void first(Arc& e) const {
1.1193 + int n = first_node;
1.1194 + while (n != -1 && nodes[n].first_out == -1) {
1.1195 + n = nodes[n].next;
1.1196 + }
1.1197 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.1198 + }
1.1199 +
1.1200 + void next(Arc& e) const {
1.1201 + if (arcs[e.id].next_out != -1) {
1.1202 + e.id = arcs[e.id].next_out;
1.1203 + } else {
1.1204 + int n = nodes[arcs[e.id ^ 1].target].next;
1.1205 + while(n != -1 && nodes[n].first_out == -1) {
1.1206 + n = nodes[n].next;
1.1207 + }
1.1208 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.1209 + }
1.1210 + }
1.1211 +
1.1212 + void first(Edge& e) const {
1.1213 + int n = first_node;
1.1214 + while (n != -1) {
1.1215 + e.id = nodes[n].first_out;
1.1216 + while ((e.id & 1) != 1) {
1.1217 + e.id = arcs[e.id].next_out;
1.1218 + }
1.1219 + if (e.id != -1) {
1.1220 + e.id /= 2;
1.1221 + return;
1.1222 + }
1.1223 + n = nodes[n].next;
1.1224 + }
1.1225 + e.id = -1;
1.1226 + }
1.1227 +
1.1228 + void next(Edge& e) const {
1.1229 + int n = arcs[e.id * 2].target;
1.1230 + e.id = arcs[(e.id * 2) | 1].next_out;
1.1231 + while ((e.id & 1) != 1) {
1.1232 + e.id = arcs[e.id].next_out;
1.1233 + }
1.1234 + if (e.id != -1) {
1.1235 + e.id /= 2;
1.1236 + return;
1.1237 + }
1.1238 + n = nodes[n].next;
1.1239 + while (n != -1) {
1.1240 + e.id = nodes[n].first_out;
1.1241 + while ((e.id & 1) != 1) {
1.1242 + e.id = arcs[e.id].next_out;
1.1243 + }
1.1244 + if (e.id != -1) {
1.1245 + e.id /= 2;
1.1246 + return;
1.1247 + }
1.1248 + n = nodes[n].next;
1.1249 + }
1.1250 + e.id = -1;
1.1251 + }
1.1252 +
1.1253 + void firstOut(Arc &e, const Node& v) const {
1.1254 + e.id = nodes[v.id].first_out;
1.1255 + }
1.1256 + void nextOut(Arc &e) const {
1.1257 + e.id = arcs[e.id].next_out;
1.1258 + }
1.1259 +
1.1260 + void firstIn(Arc &e, const Node& v) const {
1.1261 + e.id = ((nodes[v.id].first_out) ^ 1);
1.1262 + if (e.id == -2) e.id = -1;
1.1263 + }
1.1264 + void nextIn(Arc &e) const {
1.1265 + e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
1.1266 + if (e.id == -2) e.id = -1;
1.1267 + }
1.1268 +
1.1269 + void firstInc(Edge &e, bool& d, const Node& v) const {
1.1270 + int a = nodes[v.id].first_out;
1.1271 + if (a != -1 ) {
1.1272 + e.id = a / 2;
1.1273 + d = ((a & 1) == 1);
1.1274 + } else {
1.1275 + e.id = -1;
1.1276 + d = true;
1.1277 + }
1.1278 + }
1.1279 + void nextInc(Edge &e, bool& d) const {
1.1280 + int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
1.1281 + if (a != -1 ) {
1.1282 + e.id = a / 2;
1.1283 + d = ((a & 1) == 1);
1.1284 + } else {
1.1285 + e.id = -1;
1.1286 + d = true;
1.1287 + }
1.1288 + }
1.1289 +
1.1290 + static int id(Node v) { return v.id; }
1.1291 + int id(RedNode v) const { return nodes[v.id].partition_index; }
1.1292 + int id(BlueNode v) const { return nodes[v.id].partition_index; }
1.1293 + static int id(Arc e) { return e.id; }
1.1294 + static int id(Edge e) { return e.id; }
1.1295 +
1.1296 + static Node nodeFromId(int id) { return Node(id);}
1.1297 + static Arc arcFromId(int id) { return Arc(id);}
1.1298 + static Edge edgeFromId(int id) { return Edge(id);}
1.1299 +
1.1300 + bool valid(Node n) const {
1.1301 + return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
1.1302 + nodes[n.id].prev != -2;
1.1303 + }
1.1304 +
1.1305 + bool valid(Arc a) const {
1.1306 + return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1.1307 + arcs[a.id].prev_out != -2;
1.1308 + }
1.1309 +
1.1310 + bool valid(Edge e) const {
1.1311 + return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
1.1312 + arcs[2 * e.id].prev_out != -2;
1.1313 + }
1.1314 +
1.1315 + RedNode addRedNode() {
1.1316 + int n;
1.1317 +
1.1318 + if(first_free_red==-1) {
1.1319 + n = nodes.size();
1.1320 + nodes.push_back(NodeT());
1.1321 + nodes[n].partition_index = ++max_red;
1.1322 + nodes[n].red = true;
1.1323 + } else {
1.1324 + n = first_free_red;
1.1325 + first_free_red = nodes[n].next;
1.1326 + }
1.1327 +
1.1328 + nodes[n].next = first_node;
1.1329 + if (first_node != -1) nodes[first_node].prev = n;
1.1330 + first_node = n;
1.1331 + nodes[n].prev = -1;
1.1332 +
1.1333 + nodes[n].partition_next = first_red;
1.1334 + if (first_red != -1) nodes[first_red].partition_prev = n;
1.1335 + first_red = n;
1.1336 + nodes[n].partition_prev = -1;
1.1337 +
1.1338 + nodes[n].first_out = -1;
1.1339 +
1.1340 + return RedNode(n);
1.1341 + }
1.1342 +
1.1343 + BlueNode addBlueNode() {
1.1344 + int n;
1.1345 +
1.1346 + if(first_free_blue==-1) {
1.1347 + n = nodes.size();
1.1348 + nodes.push_back(NodeT());
1.1349 + nodes[n].partition_index = ++max_blue;
1.1350 + nodes[n].red = false;
1.1351 + } else {
1.1352 + n = first_free_blue;
1.1353 + first_free_blue = nodes[n].next;
1.1354 + }
1.1355 +
1.1356 + nodes[n].next = first_node;
1.1357 + if (first_node != -1) nodes[first_node].prev = n;
1.1358 + first_node = n;
1.1359 + nodes[n].prev = -1;
1.1360 +
1.1361 + nodes[n].partition_next = first_blue;
1.1362 + if (first_blue != -1) nodes[first_blue].partition_prev = n;
1.1363 + first_blue = n;
1.1364 + nodes[n].partition_prev = -1;
1.1365 +
1.1366 + nodes[n].first_out = -1;
1.1367 +
1.1368 + return BlueNode(n);
1.1369 + }
1.1370 +
1.1371 + Edge addEdge(Node u, Node v) {
1.1372 + int n;
1.1373 +
1.1374 + if (first_free_arc == -1) {
1.1375 + n = arcs.size();
1.1376 + arcs.push_back(ArcT());
1.1377 + arcs.push_back(ArcT());
1.1378 + } else {
1.1379 + n = first_free_arc;
1.1380 + first_free_arc = arcs[n].next_out;
1.1381 + }
1.1382 +
1.1383 + arcs[n].target = u.id;
1.1384 + arcs[n | 1].target = v.id;
1.1385 +
1.1386 + arcs[n].next_out = nodes[v.id].first_out;
1.1387 + if (nodes[v.id].first_out != -1) {
1.1388 + arcs[nodes[v.id].first_out].prev_out = n;
1.1389 + }
1.1390 + arcs[n].prev_out = -1;
1.1391 + nodes[v.id].first_out = n;
1.1392 +
1.1393 + arcs[n | 1].next_out = nodes[u.id].first_out;
1.1394 + if (nodes[u.id].first_out != -1) {
1.1395 + arcs[nodes[u.id].first_out].prev_out = (n | 1);
1.1396 + }
1.1397 + arcs[n | 1].prev_out = -1;
1.1398 + nodes[u.id].first_out = (n | 1);
1.1399 +
1.1400 + return Edge(n / 2);
1.1401 + }
1.1402 +
1.1403 + void erase(const Node& node) {
1.1404 + int n = node.id;
1.1405 +
1.1406 + if(nodes[n].next != -1) {
1.1407 + nodes[nodes[n].next].prev = nodes[n].prev;
1.1408 + }
1.1409 +
1.1410 + if(nodes[n].prev != -1) {
1.1411 + nodes[nodes[n].prev].next = nodes[n].next;
1.1412 + } else {
1.1413 + first_node = nodes[n].next;
1.1414 + }
1.1415 +
1.1416 + if (nodes[n].partition_next != -1) {
1.1417 + nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
1.1418 + }
1.1419 +
1.1420 + if (nodes[n].partition_prev != -1) {
1.1421 + nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
1.1422 + } else {
1.1423 + if (nodes[n].red) {
1.1424 + first_red = nodes[n].partition_next;
1.1425 + } else {
1.1426 + first_blue = nodes[n].partition_next;
1.1427 + }
1.1428 + }
1.1429 +
1.1430 + if (nodes[n].red) {
1.1431 + nodes[n].next = first_free_red;
1.1432 + first_free_red = n;
1.1433 + } else {
1.1434 + nodes[n].next = first_free_blue;
1.1435 + first_free_blue = n;
1.1436 + }
1.1437 + nodes[n].prev = -2;
1.1438 + }
1.1439 +
1.1440 + void erase(const Edge& edge) {
1.1441 + int n = edge.id * 2;
1.1442 +
1.1443 + if (arcs[n].next_out != -1) {
1.1444 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.1445 + }
1.1446 +
1.1447 + if (arcs[n].prev_out != -1) {
1.1448 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.1449 + } else {
1.1450 + nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1.1451 + }
1.1452 +
1.1453 + if (arcs[n | 1].next_out != -1) {
1.1454 + arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1.1455 + }
1.1456 +
1.1457 + if (arcs[n | 1].prev_out != -1) {
1.1458 + arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1.1459 + } else {
1.1460 + nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1.1461 + }
1.1462 +
1.1463 + arcs[n].next_out = first_free_arc;
1.1464 + first_free_arc = n;
1.1465 + arcs[n].prev_out = -2;
1.1466 + arcs[n | 1].prev_out = -2;
1.1467 +
1.1468 + }
1.1469 +
1.1470 + void clear() {
1.1471 + arcs.clear();
1.1472 + nodes.clear();
1.1473 + first_node = first_free_arc = first_red = first_blue =
1.1474 + max_red = max_blue = first_free_red = first_free_blue = -1;
1.1475 + }
1.1476 +
1.1477 + protected:
1.1478 +
1.1479 + void changeRed(Edge e, RedNode n) {
1.1480 + if(arcs[(2 * e.id) | 1].next_out != -1) {
1.1481 + arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1.1482 + arcs[(2 * e.id) | 1].prev_out;
1.1483 + }
1.1484 + if(arcs[(2 * e.id) | 1].prev_out != -1) {
1.1485 + arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1.1486 + arcs[(2 * e.id) | 1].next_out;
1.1487 + } else {
1.1488 + nodes[arcs[2 * e.id].target].first_out =
1.1489 + arcs[(2 * e.id) | 1].next_out;
1.1490 + }
1.1491 +
1.1492 + if (nodes[n.id].first_out != -1) {
1.1493 + arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1.1494 + }
1.1495 + arcs[2 * e.id].target = n.id;
1.1496 + arcs[(2 * e.id) | 1].prev_out = -1;
1.1497 + arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1.1498 + nodes[n.id].first_out = ((2 * e.id) | 1);
1.1499 + }
1.1500 +
1.1501 + void changeBlue(Edge e, BlueNode n) {
1.1502 + if(arcs[2 * e.id].next_out != -1) {
1.1503 + arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1.1504 + }
1.1505 + if(arcs[2 * e.id].prev_out != -1) {
1.1506 + arcs[arcs[2 * e.id].prev_out].next_out =
1.1507 + arcs[2 * e.id].next_out;
1.1508 + } else {
1.1509 + nodes[arcs[(2 * e.id) | 1].target].first_out =
1.1510 + arcs[2 * e.id].next_out;
1.1511 + }
1.1512 +
1.1513 + if (nodes[n.id].first_out != -1) {
1.1514 + arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1.1515 + }
1.1516 + arcs[(2 * e.id) | 1].target = n.id;
1.1517 + arcs[2 * e.id].prev_out = -1;
1.1518 + arcs[2 * e.id].next_out = nodes[n.id].first_out;
1.1519 + nodes[n.id].first_out = 2 * e.id;
1.1520 + }
1.1521 +
1.1522 + };
1.1523 +
1.1524 + typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
1.1525 +
1.1526 +
1.1527 + /// \addtogroup graphs
1.1528 + /// @{
1.1529 +
1.1530 + ///A general undirected graph structure.
1.1531 +
1.1532 + ///\ref ListBpGraph is a versatile and fast undirected graph
1.1533 + ///implementation based on linked lists that are stored in
1.1534 + ///\c std::vector structures.
1.1535 + ///
1.1536 + ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
1.1537 + ///and it also provides several useful additional functionalities.
1.1538 + ///Most of its member functions and nested classes are documented
1.1539 + ///only in the concept class.
1.1540 + ///
1.1541 + ///This class provides only linear time counting for nodes, edges and arcs.
1.1542 + ///
1.1543 + ///\sa concepts::BpGraph
1.1544 + ///\sa ListDigraph
1.1545 + class ListBpGraph : public ExtendedListBpGraphBase {
1.1546 + typedef ExtendedListBpGraphBase Parent;
1.1547 +
1.1548 + private:
1.1549 + /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
1.1550 + ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase() {};
1.1551 + /// \brief Assignment of a graph to another one is \e not allowed.
1.1552 + /// Use BpGraphCopy instead.
1.1553 + void operator=(const ListBpGraph &) {}
1.1554 + public:
1.1555 + /// Constructor
1.1556 +
1.1557 + /// Constructor.
1.1558 + ///
1.1559 + ListBpGraph() {}
1.1560 +
1.1561 + typedef Parent::OutArcIt IncEdgeIt;
1.1562 +
1.1563 + /// \brief Add a new red node to the graph.
1.1564 + ///
1.1565 + /// This function adds a red new node to the graph.
1.1566 + /// \return The new node.
1.1567 + RedNode addRedNode() { return Parent::addRedNode(); }
1.1568 +
1.1569 + /// \brief Add a new blue node to the graph.
1.1570 + ///
1.1571 + /// This function adds a blue new node to the graph.
1.1572 + /// \return The new node.
1.1573 + BlueNode addBlueNode() { return Parent::addBlueNode(); }
1.1574 +
1.1575 + /// \brief Add a new edge to the graph.
1.1576 + ///
1.1577 + /// This function adds a new edge to the graph between nodes
1.1578 + /// \c u and \c v with inherent orientation from node \c u to
1.1579 + /// node \c v.
1.1580 + /// \return The new edge.
1.1581 + Edge addEdge(RedNode u, BlueNode v) {
1.1582 + return Parent::addEdge(u, v);
1.1583 + }
1.1584 + Edge addEdge(BlueNode v, RedNode u) {
1.1585 + return Parent::addEdge(u, v);
1.1586 + }
1.1587 +
1.1588 + ///\brief Erase a node from the graph.
1.1589 + ///
1.1590 + /// This function erases the given node along with its incident arcs
1.1591 + /// from the graph.
1.1592 + ///
1.1593 + /// \note All iterators referencing the removed node or the incident
1.1594 + /// edges are invalidated, of course.
1.1595 + void erase(Node n) { Parent::erase(n); }
1.1596 +
1.1597 + ///\brief Erase an edge from the graph.
1.1598 + ///
1.1599 + /// This function erases the given edge from the graph.
1.1600 + ///
1.1601 + /// \note All iterators referencing the removed edge are invalidated,
1.1602 + /// of course.
1.1603 + void erase(Edge e) { Parent::erase(e); }
1.1604 + /// Node validity check
1.1605 +
1.1606 + /// This function gives back \c true if the given node is valid,
1.1607 + /// i.e. it is a real node of the graph.
1.1608 + ///
1.1609 + /// \warning A removed node could become valid again if new nodes are
1.1610 + /// added to the graph.
1.1611 + bool valid(Node n) const { return Parent::valid(n); }
1.1612 + /// Edge validity check
1.1613 +
1.1614 + /// This function gives back \c true if the given edge is valid,
1.1615 + /// i.e. it is a real edge of the graph.
1.1616 + ///
1.1617 + /// \warning A removed edge could become valid again if new edges are
1.1618 + /// added to the graph.
1.1619 + bool valid(Edge e) const { return Parent::valid(e); }
1.1620 + /// Arc validity check
1.1621 +
1.1622 + /// This function gives back \c true if the given arc is valid,
1.1623 + /// i.e. it is a real arc of the graph.
1.1624 + ///
1.1625 + /// \warning A removed arc could become valid again if new edges are
1.1626 + /// added to the graph.
1.1627 + bool valid(Arc a) const { return Parent::valid(a); }
1.1628 +
1.1629 + /// \brief Change the red node of an edge.
1.1630 + ///
1.1631 + /// This function changes the red node of the given edge \c e to \c n.
1.1632 + ///
1.1633 + ///\note \c EdgeIt and \c ArcIt iterators referencing the
1.1634 + ///changed edge are invalidated and all other iterators whose
1.1635 + ///base node is the changed node are also invalidated.
1.1636 + ///
1.1637 + ///\warning This functionality cannot be used together with the
1.1638 + ///Snapshot feature.
1.1639 + void changeRed(Edge e, RedNode n) {
1.1640 + Parent::changeRed(e, n);
1.1641 + }
1.1642 + /// \brief Change the blue node of an edge.
1.1643 + ///
1.1644 + /// This function changes the blue node of the given edge \c e to \c n.
1.1645 + ///
1.1646 + ///\note \c EdgeIt iterators referencing the changed edge remain
1.1647 + ///valid, but \c ArcIt iterators referencing the changed edge and
1.1648 + ///all other iterators whose base node is the changed node are also
1.1649 + ///invalidated.
1.1650 + ///
1.1651 + ///\warning This functionality cannot be used together with the
1.1652 + ///Snapshot feature.
1.1653 + void changeBlue(Edge e, BlueNode n) {
1.1654 + Parent::changeBlue(e, n);
1.1655 + }
1.1656 +
1.1657 + ///Clear the graph.
1.1658 +
1.1659 + ///This function erases all nodes and arcs from the graph.
1.1660 + ///
1.1661 + ///\note All iterators of the graph are invalidated, of course.
1.1662 + void clear() {
1.1663 + Parent::clear();
1.1664 + }
1.1665 +
1.1666 + /// Reserve memory for nodes.
1.1667 +
1.1668 + /// Using this function, it is possible to avoid superfluous memory
1.1669 + /// allocation: if you know that the graph you want to build will
1.1670 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.1671 + /// then it is worth reserving space for this amount before starting
1.1672 + /// to build the graph.
1.1673 + /// \sa reserveEdge()
1.1674 + void reserveNode(int n) { nodes.reserve(n); };
1.1675 +
1.1676 + /// Reserve memory for edges.
1.1677 +
1.1678 + /// Using this function, it is possible to avoid superfluous memory
1.1679 + /// allocation: if you know that the graph you want to build will
1.1680 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.1681 + /// then it is worth reserving space for this amount before starting
1.1682 + /// to build the graph.
1.1683 + /// \sa reserveNode()
1.1684 + void reserveEdge(int m) { arcs.reserve(2 * m); };
1.1685 +
1.1686 + /// \brief Class to make a snapshot of the graph and restore
1.1687 + /// it later.
1.1688 + ///
1.1689 + /// Class to make a snapshot of the graph and restore it later.
1.1690 + ///
1.1691 + /// The newly added nodes and edges can be removed
1.1692 + /// using the restore() function.
1.1693 + ///
1.1694 + /// \note After a state is restored, you cannot restore a later state,
1.1695 + /// i.e. you cannot add the removed nodes and edges again using
1.1696 + /// another Snapshot instance.
1.1697 + ///
1.1698 + /// \warning Node and edge deletions and other modifications
1.1699 + /// (e.g. changing the end-nodes of edges or contracting nodes)
1.1700 + /// cannot be restored. These events invalidate the snapshot.
1.1701 + /// However, the edges and nodes that were added to the graph after
1.1702 + /// making the current snapshot can be removed without invalidating it.
1.1703 + class Snapshot {
1.1704 + protected:
1.1705 +
1.1706 + typedef Parent::NodeNotifier NodeNotifier;
1.1707 +
1.1708 + class NodeObserverProxy : public NodeNotifier::ObserverBase {
1.1709 + public:
1.1710 +
1.1711 + NodeObserverProxy(Snapshot& _snapshot)
1.1712 + : snapshot(_snapshot) {}
1.1713 +
1.1714 + using NodeNotifier::ObserverBase::attach;
1.1715 + using NodeNotifier::ObserverBase::detach;
1.1716 + using NodeNotifier::ObserverBase::attached;
1.1717 +
1.1718 + protected:
1.1719 +
1.1720 + virtual void add(const Node& node) {
1.1721 + snapshot.addNode(node);
1.1722 + }
1.1723 + virtual void add(const std::vector<Node>& nodes) {
1.1724 for (int i = nodes.size() - 1; i >= 0; ++i) {
1.1725 snapshot.addNode(nodes[i]);
1.1726 }
1.1727 @@ -616,818 +2333,6 @@
1.1728 Snapshot& snapshot;
1.1729 };
1.1730
1.1731 - class ArcObserverProxy : public ArcNotifier::ObserverBase {
1.1732 - public:
1.1733 -
1.1734 - ArcObserverProxy(Snapshot& _snapshot)
1.1735 - : snapshot(_snapshot) {}
1.1736 -
1.1737 - using ArcNotifier::ObserverBase::attach;
1.1738 - using ArcNotifier::ObserverBase::detach;
1.1739 - using ArcNotifier::ObserverBase::attached;
1.1740 -
1.1741 - protected:
1.1742 -
1.1743 - virtual void add(const Arc& arc) {
1.1744 - snapshot.addArc(arc);
1.1745 - }
1.1746 - virtual void add(const std::vector<Arc>& arcs) {
1.1747 - for (int i = arcs.size() - 1; i >= 0; ++i) {
1.1748 - snapshot.addArc(arcs[i]);
1.1749 - }
1.1750 - }
1.1751 - virtual void erase(const Arc& arc) {
1.1752 - snapshot.eraseArc(arc);
1.1753 - }
1.1754 - virtual void erase(const std::vector<Arc>& arcs) {
1.1755 - for (int i = 0; i < int(arcs.size()); ++i) {
1.1756 - snapshot.eraseArc(arcs[i]);
1.1757 - }
1.1758 - }
1.1759 - virtual void build() {
1.1760 - Arc arc;
1.1761 - std::vector<Arc> arcs;
1.1762 - for (notifier()->first(arc); arc != INVALID;
1.1763 - notifier()->next(arc)) {
1.1764 - arcs.push_back(arc);
1.1765 - }
1.1766 - for (int i = arcs.size() - 1; i >= 0; --i) {
1.1767 - snapshot.addArc(arcs[i]);
1.1768 - }
1.1769 - }
1.1770 - virtual void clear() {
1.1771 - Arc arc;
1.1772 - for (notifier()->first(arc); arc != INVALID;
1.1773 - notifier()->next(arc)) {
1.1774 - snapshot.eraseArc(arc);
1.1775 - }
1.1776 - }
1.1777 -
1.1778 - Snapshot& snapshot;
1.1779 - };
1.1780 -
1.1781 - ListDigraph *digraph;
1.1782 -
1.1783 - NodeObserverProxy node_observer_proxy;
1.1784 - ArcObserverProxy arc_observer_proxy;
1.1785 -
1.1786 - std::list<Node> added_nodes;
1.1787 - std::list<Arc> added_arcs;
1.1788 -
1.1789 -
1.1790 - void addNode(const Node& node) {
1.1791 - added_nodes.push_front(node);
1.1792 - }
1.1793 - void eraseNode(const Node& node) {
1.1794 - std::list<Node>::iterator it =
1.1795 - std::find(added_nodes.begin(), added_nodes.end(), node);
1.1796 - if (it == added_nodes.end()) {
1.1797 - clear();
1.1798 - arc_observer_proxy.detach();
1.1799 - throw NodeNotifier::ImmediateDetach();
1.1800 - } else {
1.1801 - added_nodes.erase(it);
1.1802 - }
1.1803 - }
1.1804 -
1.1805 - void addArc(const Arc& arc) {
1.1806 - added_arcs.push_front(arc);
1.1807 - }
1.1808 - void eraseArc(const Arc& arc) {
1.1809 - std::list<Arc>::iterator it =
1.1810 - std::find(added_arcs.begin(), added_arcs.end(), arc);
1.1811 - if (it == added_arcs.end()) {
1.1812 - clear();
1.1813 - node_observer_proxy.detach();
1.1814 - throw ArcNotifier::ImmediateDetach();
1.1815 - } else {
1.1816 - added_arcs.erase(it);
1.1817 - }
1.1818 - }
1.1819 -
1.1820 - void attach(ListDigraph &_digraph) {
1.1821 - digraph = &_digraph;
1.1822 - node_observer_proxy.attach(digraph->notifier(Node()));
1.1823 - arc_observer_proxy.attach(digraph->notifier(Arc()));
1.1824 - }
1.1825 -
1.1826 - void detach() {
1.1827 - node_observer_proxy.detach();
1.1828 - arc_observer_proxy.detach();
1.1829 - }
1.1830 -
1.1831 - bool attached() const {
1.1832 - return node_observer_proxy.attached();
1.1833 - }
1.1834 -
1.1835 - void clear() {
1.1836 - added_nodes.clear();
1.1837 - added_arcs.clear();
1.1838 - }
1.1839 -
1.1840 - public:
1.1841 -
1.1842 - /// \brief Default constructor.
1.1843 - ///
1.1844 - /// Default constructor.
1.1845 - /// You have to call save() to actually make a snapshot.
1.1846 - Snapshot()
1.1847 - : digraph(0), node_observer_proxy(*this),
1.1848 - arc_observer_proxy(*this) {}
1.1849 -
1.1850 - /// \brief Constructor that immediately makes a snapshot.
1.1851 - ///
1.1852 - /// This constructor immediately makes a snapshot of the given digraph.
1.1853 - Snapshot(ListDigraph &gr)
1.1854 - : node_observer_proxy(*this),
1.1855 - arc_observer_proxy(*this) {
1.1856 - attach(gr);
1.1857 - }
1.1858 -
1.1859 - /// \brief Make a snapshot.
1.1860 - ///
1.1861 - /// This function makes a snapshot of the given digraph.
1.1862 - /// It can be called more than once. In case of a repeated
1.1863 - /// call, the previous snapshot gets lost.
1.1864 - void save(ListDigraph &gr) {
1.1865 - if (attached()) {
1.1866 - detach();
1.1867 - clear();
1.1868 - }
1.1869 - attach(gr);
1.1870 - }
1.1871 -
1.1872 - /// \brief Undo the changes until the last snapshot.
1.1873 - ///
1.1874 - /// This function undos the changes until the last snapshot
1.1875 - /// created by save() or Snapshot(ListDigraph&).
1.1876 - ///
1.1877 - /// \warning This method invalidates the snapshot, i.e. repeated
1.1878 - /// restoring is not supported unless you call save() again.
1.1879 - void restore() {
1.1880 - detach();
1.1881 - for(std::list<Arc>::iterator it = added_arcs.begin();
1.1882 - it != added_arcs.end(); ++it) {
1.1883 - digraph->erase(*it);
1.1884 - }
1.1885 - for(std::list<Node>::iterator it = added_nodes.begin();
1.1886 - it != added_nodes.end(); ++it) {
1.1887 - digraph->erase(*it);
1.1888 - }
1.1889 - clear();
1.1890 - }
1.1891 -
1.1892 - /// \brief Returns \c true if the snapshot is valid.
1.1893 - ///
1.1894 - /// This function returns \c true if the snapshot is valid.
1.1895 - bool valid() const {
1.1896 - return attached();
1.1897 - }
1.1898 - };
1.1899 -
1.1900 - };
1.1901 -
1.1902 - ///@}
1.1903 -
1.1904 - class ListGraphBase {
1.1905 -
1.1906 - protected:
1.1907 -
1.1908 - struct NodeT {
1.1909 - int first_out;
1.1910 - int prev, next;
1.1911 - };
1.1912 -
1.1913 - struct ArcT {
1.1914 - int target;
1.1915 - int prev_out, next_out;
1.1916 - };
1.1917 -
1.1918 - std::vector<NodeT> nodes;
1.1919 -
1.1920 - int first_node;
1.1921 -
1.1922 - int first_free_node;
1.1923 -
1.1924 - std::vector<ArcT> arcs;
1.1925 -
1.1926 - int first_free_arc;
1.1927 -
1.1928 - public:
1.1929 -
1.1930 - typedef ListGraphBase Graph;
1.1931 -
1.1932 - class Node {
1.1933 - friend class ListGraphBase;
1.1934 - protected:
1.1935 -
1.1936 - int id;
1.1937 - explicit Node(int pid) { id = pid;}
1.1938 -
1.1939 - public:
1.1940 - Node() {}
1.1941 - Node (Invalid) { id = -1; }
1.1942 - bool operator==(const Node& node) const {return id == node.id;}
1.1943 - bool operator!=(const Node& node) const {return id != node.id;}
1.1944 - bool operator<(const Node& node) const {return id < node.id;}
1.1945 - };
1.1946 -
1.1947 - class Edge {
1.1948 - friend class ListGraphBase;
1.1949 - protected:
1.1950 -
1.1951 - int id;
1.1952 - explicit Edge(int pid) { id = pid;}
1.1953 -
1.1954 - public:
1.1955 - Edge() {}
1.1956 - Edge (Invalid) { id = -1; }
1.1957 - bool operator==(const Edge& edge) const {return id == edge.id;}
1.1958 - bool operator!=(const Edge& edge) const {return id != edge.id;}
1.1959 - bool operator<(const Edge& edge) const {return id < edge.id;}
1.1960 - };
1.1961 -
1.1962 - class Arc {
1.1963 - friend class ListGraphBase;
1.1964 - protected:
1.1965 -
1.1966 - int id;
1.1967 - explicit Arc(int pid) { id = pid;}
1.1968 -
1.1969 - public:
1.1970 - operator Edge() const {
1.1971 - return id != -1 ? edgeFromId(id / 2) : INVALID;
1.1972 - }
1.1973 -
1.1974 - Arc() {}
1.1975 - Arc (Invalid) { id = -1; }
1.1976 - bool operator==(const Arc& arc) const {return id == arc.id;}
1.1977 - bool operator!=(const Arc& arc) const {return id != arc.id;}
1.1978 - bool operator<(const Arc& arc) const {return id < arc.id;}
1.1979 - };
1.1980 -
1.1981 - ListGraphBase()
1.1982 - : nodes(), first_node(-1),
1.1983 - first_free_node(-1), arcs(), first_free_arc(-1) {}
1.1984 -
1.1985 -
1.1986 - int maxNodeId() const { return nodes.size()-1; }
1.1987 - int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.1988 - int maxArcId() const { return arcs.size()-1; }
1.1989 -
1.1990 - Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
1.1991 - Node target(Arc e) const { return Node(arcs[e.id].target); }
1.1992 -
1.1993 - Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
1.1994 - Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
1.1995 -
1.1996 - static bool direction(Arc e) {
1.1997 - return (e.id & 1) == 1;
1.1998 - }
1.1999 -
1.2000 - static Arc direct(Edge e, bool d) {
1.2001 - return Arc(e.id * 2 + (d ? 1 : 0));
1.2002 - }
1.2003 -
1.2004 - void first(Node& node) const {
1.2005 - node.id = first_node;
1.2006 - }
1.2007 -
1.2008 - void next(Node& node) const {
1.2009 - node.id = nodes[node.id].next;
1.2010 - }
1.2011 -
1.2012 - void first(Arc& e) const {
1.2013 - int n = first_node;
1.2014 - while (n != -1 && nodes[n].first_out == -1) {
1.2015 - n = nodes[n].next;
1.2016 - }
1.2017 - e.id = (n == -1) ? -1 : nodes[n].first_out;
1.2018 - }
1.2019 -
1.2020 - void next(Arc& e) const {
1.2021 - if (arcs[e.id].next_out != -1) {
1.2022 - e.id = arcs[e.id].next_out;
1.2023 - } else {
1.2024 - int n = nodes[arcs[e.id ^ 1].target].next;
1.2025 - while(n != -1 && nodes[n].first_out == -1) {
1.2026 - n = nodes[n].next;
1.2027 - }
1.2028 - e.id = (n == -1) ? -1 : nodes[n].first_out;
1.2029 - }
1.2030 - }
1.2031 -
1.2032 - void first(Edge& e) const {
1.2033 - int n = first_node;
1.2034 - while (n != -1) {
1.2035 - e.id = nodes[n].first_out;
1.2036 - while ((e.id & 1) != 1) {
1.2037 - e.id = arcs[e.id].next_out;
1.2038 - }
1.2039 - if (e.id != -1) {
1.2040 - e.id /= 2;
1.2041 - return;
1.2042 - }
1.2043 - n = nodes[n].next;
1.2044 - }
1.2045 - e.id = -1;
1.2046 - }
1.2047 -
1.2048 - void next(Edge& e) const {
1.2049 - int n = arcs[e.id * 2].target;
1.2050 - e.id = arcs[(e.id * 2) | 1].next_out;
1.2051 - while ((e.id & 1) != 1) {
1.2052 - e.id = arcs[e.id].next_out;
1.2053 - }
1.2054 - if (e.id != -1) {
1.2055 - e.id /= 2;
1.2056 - return;
1.2057 - }
1.2058 - n = nodes[n].next;
1.2059 - while (n != -1) {
1.2060 - e.id = nodes[n].first_out;
1.2061 - while ((e.id & 1) != 1) {
1.2062 - e.id = arcs[e.id].next_out;
1.2063 - }
1.2064 - if (e.id != -1) {
1.2065 - e.id /= 2;
1.2066 - return;
1.2067 - }
1.2068 - n = nodes[n].next;
1.2069 - }
1.2070 - e.id = -1;
1.2071 - }
1.2072 -
1.2073 - void firstOut(Arc &e, const Node& v) const {
1.2074 - e.id = nodes[v.id].first_out;
1.2075 - }
1.2076 - void nextOut(Arc &e) const {
1.2077 - e.id = arcs[e.id].next_out;
1.2078 - }
1.2079 -
1.2080 - void firstIn(Arc &e, const Node& v) const {
1.2081 - e.id = ((nodes[v.id].first_out) ^ 1);
1.2082 - if (e.id == -2) e.id = -1;
1.2083 - }
1.2084 - void nextIn(Arc &e) const {
1.2085 - e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
1.2086 - if (e.id == -2) e.id = -1;
1.2087 - }
1.2088 -
1.2089 - void firstInc(Edge &e, bool& d, const Node& v) const {
1.2090 - int a = nodes[v.id].first_out;
1.2091 - if (a != -1 ) {
1.2092 - e.id = a / 2;
1.2093 - d = ((a & 1) == 1);
1.2094 - } else {
1.2095 - e.id = -1;
1.2096 - d = true;
1.2097 - }
1.2098 - }
1.2099 - void nextInc(Edge &e, bool& d) const {
1.2100 - int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
1.2101 - if (a != -1 ) {
1.2102 - e.id = a / 2;
1.2103 - d = ((a & 1) == 1);
1.2104 - } else {
1.2105 - e.id = -1;
1.2106 - d = true;
1.2107 - }
1.2108 - }
1.2109 -
1.2110 - static int id(Node v) { return v.id; }
1.2111 - static int id(Arc e) { return e.id; }
1.2112 - static int id(Edge e) { return e.id; }
1.2113 -
1.2114 - static Node nodeFromId(int id) { return Node(id);}
1.2115 - static Arc arcFromId(int id) { return Arc(id);}
1.2116 - static Edge edgeFromId(int id) { return Edge(id);}
1.2117 -
1.2118 - bool valid(Node n) const {
1.2119 - return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
1.2120 - nodes[n.id].prev != -2;
1.2121 - }
1.2122 -
1.2123 - bool valid(Arc a) const {
1.2124 - return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1.2125 - arcs[a.id].prev_out != -2;
1.2126 - }
1.2127 -
1.2128 - bool valid(Edge e) const {
1.2129 - return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
1.2130 - arcs[2 * e.id].prev_out != -2;
1.2131 - }
1.2132 -
1.2133 - Node addNode() {
1.2134 - int n;
1.2135 -
1.2136 - if(first_free_node==-1) {
1.2137 - n = nodes.size();
1.2138 - nodes.push_back(NodeT());
1.2139 - } else {
1.2140 - n = first_free_node;
1.2141 - first_free_node = nodes[n].next;
1.2142 - }
1.2143 -
1.2144 - nodes[n].next = first_node;
1.2145 - if (first_node != -1) nodes[first_node].prev = n;
1.2146 - first_node = n;
1.2147 - nodes[n].prev = -1;
1.2148 -
1.2149 - nodes[n].first_out = -1;
1.2150 -
1.2151 - return Node(n);
1.2152 - }
1.2153 -
1.2154 - Edge addEdge(Node u, Node v) {
1.2155 - int n;
1.2156 -
1.2157 - if (first_free_arc == -1) {
1.2158 - n = arcs.size();
1.2159 - arcs.push_back(ArcT());
1.2160 - arcs.push_back(ArcT());
1.2161 - } else {
1.2162 - n = first_free_arc;
1.2163 - first_free_arc = arcs[n].next_out;
1.2164 - }
1.2165 -
1.2166 - arcs[n].target = u.id;
1.2167 - arcs[n | 1].target = v.id;
1.2168 -
1.2169 - arcs[n].next_out = nodes[v.id].first_out;
1.2170 - if (nodes[v.id].first_out != -1) {
1.2171 - arcs[nodes[v.id].first_out].prev_out = n;
1.2172 - }
1.2173 - arcs[n].prev_out = -1;
1.2174 - nodes[v.id].first_out = n;
1.2175 -
1.2176 - arcs[n | 1].next_out = nodes[u.id].first_out;
1.2177 - if (nodes[u.id].first_out != -1) {
1.2178 - arcs[nodes[u.id].first_out].prev_out = (n | 1);
1.2179 - }
1.2180 - arcs[n | 1].prev_out = -1;
1.2181 - nodes[u.id].first_out = (n | 1);
1.2182 -
1.2183 - return Edge(n / 2);
1.2184 - }
1.2185 -
1.2186 - void erase(const Node& node) {
1.2187 - int n = node.id;
1.2188 -
1.2189 - if(nodes[n].next != -1) {
1.2190 - nodes[nodes[n].next].prev = nodes[n].prev;
1.2191 - }
1.2192 -
1.2193 - if(nodes[n].prev != -1) {
1.2194 - nodes[nodes[n].prev].next = nodes[n].next;
1.2195 - } else {
1.2196 - first_node = nodes[n].next;
1.2197 - }
1.2198 -
1.2199 - nodes[n].next = first_free_node;
1.2200 - first_free_node = n;
1.2201 - nodes[n].prev = -2;
1.2202 - }
1.2203 -
1.2204 - void erase(const Edge& edge) {
1.2205 - int n = edge.id * 2;
1.2206 -
1.2207 - if (arcs[n].next_out != -1) {
1.2208 - arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.2209 - }
1.2210 -
1.2211 - if (arcs[n].prev_out != -1) {
1.2212 - arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.2213 - } else {
1.2214 - nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1.2215 - }
1.2216 -
1.2217 - if (arcs[n | 1].next_out != -1) {
1.2218 - arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1.2219 - }
1.2220 -
1.2221 - if (arcs[n | 1].prev_out != -1) {
1.2222 - arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1.2223 - } else {
1.2224 - nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1.2225 - }
1.2226 -
1.2227 - arcs[n].next_out = first_free_arc;
1.2228 - first_free_arc = n;
1.2229 - arcs[n].prev_out = -2;
1.2230 - arcs[n | 1].prev_out = -2;
1.2231 -
1.2232 - }
1.2233 -
1.2234 - void clear() {
1.2235 - arcs.clear();
1.2236 - nodes.clear();
1.2237 - first_node = first_free_node = first_free_arc = -1;
1.2238 - }
1.2239 -
1.2240 - protected:
1.2241 -
1.2242 - void changeV(Edge e, Node n) {
1.2243 - if(arcs[2 * e.id].next_out != -1) {
1.2244 - arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1.2245 - }
1.2246 - if(arcs[2 * e.id].prev_out != -1) {
1.2247 - arcs[arcs[2 * e.id].prev_out].next_out =
1.2248 - arcs[2 * e.id].next_out;
1.2249 - } else {
1.2250 - nodes[arcs[(2 * e.id) | 1].target].first_out =
1.2251 - arcs[2 * e.id].next_out;
1.2252 - }
1.2253 -
1.2254 - if (nodes[n.id].first_out != -1) {
1.2255 - arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1.2256 - }
1.2257 - arcs[(2 * e.id) | 1].target = n.id;
1.2258 - arcs[2 * e.id].prev_out = -1;
1.2259 - arcs[2 * e.id].next_out = nodes[n.id].first_out;
1.2260 - nodes[n.id].first_out = 2 * e.id;
1.2261 - }
1.2262 -
1.2263 - void changeU(Edge e, Node n) {
1.2264 - if(arcs[(2 * e.id) | 1].next_out != -1) {
1.2265 - arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1.2266 - arcs[(2 * e.id) | 1].prev_out;
1.2267 - }
1.2268 - if(arcs[(2 * e.id) | 1].prev_out != -1) {
1.2269 - arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1.2270 - arcs[(2 * e.id) | 1].next_out;
1.2271 - } else {
1.2272 - nodes[arcs[2 * e.id].target].first_out =
1.2273 - arcs[(2 * e.id) | 1].next_out;
1.2274 - }
1.2275 -
1.2276 - if (nodes[n.id].first_out != -1) {
1.2277 - arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1.2278 - }
1.2279 - arcs[2 * e.id].target = n.id;
1.2280 - arcs[(2 * e.id) | 1].prev_out = -1;
1.2281 - arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1.2282 - nodes[n.id].first_out = ((2 * e.id) | 1);
1.2283 - }
1.2284 -
1.2285 - };
1.2286 -
1.2287 - typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
1.2288 -
1.2289 -
1.2290 - /// \addtogroup graphs
1.2291 - /// @{
1.2292 -
1.2293 - ///A general undirected graph structure.
1.2294 -
1.2295 - ///\ref ListGraph is a versatile and fast undirected graph
1.2296 - ///implementation based on linked lists that are stored in
1.2297 - ///\c std::vector structures.
1.2298 - ///
1.2299 - ///This type fully conforms to the \ref concepts::Graph "Graph concept"
1.2300 - ///and it also provides several useful additional functionalities.
1.2301 - ///Most of its member functions and nested classes are documented
1.2302 - ///only in the concept class.
1.2303 - ///
1.2304 - ///This class provides only linear time counting for nodes, edges and arcs.
1.2305 - ///
1.2306 - ///\sa concepts::Graph
1.2307 - ///\sa ListDigraph
1.2308 - class ListGraph : public ExtendedListGraphBase {
1.2309 - typedef ExtendedListGraphBase Parent;
1.2310 -
1.2311 - private:
1.2312 - /// Graphs are \e not copy constructible. Use GraphCopy instead.
1.2313 - ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
1.2314 - /// \brief Assignment of a graph to another one is \e not allowed.
1.2315 - /// Use GraphCopy instead.
1.2316 - void operator=(const ListGraph &) {}
1.2317 - public:
1.2318 - /// Constructor
1.2319 -
1.2320 - /// Constructor.
1.2321 - ///
1.2322 - ListGraph() {}
1.2323 -
1.2324 - typedef Parent::OutArcIt IncEdgeIt;
1.2325 -
1.2326 - /// \brief Add a new node to the graph.
1.2327 - ///
1.2328 - /// This function adds a new node to the graph.
1.2329 - /// \return The new node.
1.2330 - Node addNode() { return Parent::addNode(); }
1.2331 -
1.2332 - /// \brief Add a new edge to the graph.
1.2333 - ///
1.2334 - /// This function adds a new edge to the graph between nodes
1.2335 - /// \c u and \c v with inherent orientation from node \c u to
1.2336 - /// node \c v.
1.2337 - /// \return The new edge.
1.2338 - Edge addEdge(Node u, Node v) {
1.2339 - return Parent::addEdge(u, v);
1.2340 - }
1.2341 -
1.2342 - ///\brief Erase a node from the graph.
1.2343 - ///
1.2344 - /// This function erases the given node along with its incident arcs
1.2345 - /// from the graph.
1.2346 - ///
1.2347 - /// \note All iterators referencing the removed node or the incident
1.2348 - /// edges are invalidated, of course.
1.2349 - void erase(Node n) { Parent::erase(n); }
1.2350 -
1.2351 - ///\brief Erase an edge from the graph.
1.2352 - ///
1.2353 - /// This function erases the given edge from the graph.
1.2354 - ///
1.2355 - /// \note All iterators referencing the removed edge are invalidated,
1.2356 - /// of course.
1.2357 - void erase(Edge e) { Parent::erase(e); }
1.2358 - /// Node validity check
1.2359 -
1.2360 - /// This function gives back \c true if the given node is valid,
1.2361 - /// i.e. it is a real node of the graph.
1.2362 - ///
1.2363 - /// \warning A removed node could become valid again if new nodes are
1.2364 - /// added to the graph.
1.2365 - bool valid(Node n) const { return Parent::valid(n); }
1.2366 - /// Edge validity check
1.2367 -
1.2368 - /// This function gives back \c true if the given edge is valid,
1.2369 - /// i.e. it is a real edge of the graph.
1.2370 - ///
1.2371 - /// \warning A removed edge could become valid again if new edges are
1.2372 - /// added to the graph.
1.2373 - bool valid(Edge e) const { return Parent::valid(e); }
1.2374 - /// Arc validity check
1.2375 -
1.2376 - /// This function gives back \c true if the given arc is valid,
1.2377 - /// i.e. it is a real arc of the graph.
1.2378 - ///
1.2379 - /// \warning A removed arc could become valid again if new edges are
1.2380 - /// added to the graph.
1.2381 - bool valid(Arc a) const { return Parent::valid(a); }
1.2382 -
1.2383 - /// \brief Change the first node of an edge.
1.2384 - ///
1.2385 - /// This function changes the first node of the given edge \c e to \c n.
1.2386 - ///
1.2387 - ///\note \c EdgeIt and \c ArcIt iterators referencing the
1.2388 - ///changed edge are invalidated and all other iterators whose
1.2389 - ///base node is the changed node are also invalidated.
1.2390 - ///
1.2391 - ///\warning This functionality cannot be used together with the
1.2392 - ///Snapshot feature.
1.2393 - void changeU(Edge e, Node n) {
1.2394 - Parent::changeU(e,n);
1.2395 - }
1.2396 - /// \brief Change the second node of an edge.
1.2397 - ///
1.2398 - /// This function changes the second node of the given edge \c e to \c n.
1.2399 - ///
1.2400 - ///\note \c EdgeIt iterators referencing the changed edge remain
1.2401 - ///valid, but \c ArcIt iterators referencing the changed edge and
1.2402 - ///all other iterators whose base node is the changed node are also
1.2403 - ///invalidated.
1.2404 - ///
1.2405 - ///\warning This functionality cannot be used together with the
1.2406 - ///Snapshot feature.
1.2407 - void changeV(Edge e, Node n) {
1.2408 - Parent::changeV(e,n);
1.2409 - }
1.2410 -
1.2411 - /// \brief Contract two nodes.
1.2412 - ///
1.2413 - /// This function contracts the given two nodes.
1.2414 - /// Node \c b is removed, but instead of deleting
1.2415 - /// its incident edges, they are joined to node \c a.
1.2416 - /// If the last parameter \c r is \c true (this is the default value),
1.2417 - /// then the newly created loops are removed.
1.2418 - ///
1.2419 - /// \note The moved edges are joined to node \c a using changeU()
1.2420 - /// or changeV(), thus all edge and arc iterators whose base node is
1.2421 - /// \c b are invalidated.
1.2422 - /// Moreover all iterators referencing node \c b or the removed
1.2423 - /// loops are also invalidated. Other iterators remain valid.
1.2424 - ///
1.2425 - ///\warning This functionality cannot be used together with the
1.2426 - ///Snapshot feature.
1.2427 - void contract(Node a, Node b, bool r = true) {
1.2428 - for(IncEdgeIt e(*this, b); e!=INVALID;) {
1.2429 - IncEdgeIt f = e; ++f;
1.2430 - if (r && runningNode(e) == a) {
1.2431 - erase(e);
1.2432 - } else if (u(e) == b) {
1.2433 - changeU(e, a);
1.2434 - } else {
1.2435 - changeV(e, a);
1.2436 - }
1.2437 - e = f;
1.2438 - }
1.2439 - erase(b);
1.2440 - }
1.2441 -
1.2442 - ///Clear the graph.
1.2443 -
1.2444 - ///This function erases all nodes and arcs from the graph.
1.2445 - ///
1.2446 - ///\note All iterators of the graph are invalidated, of course.
1.2447 - void clear() {
1.2448 - Parent::clear();
1.2449 - }
1.2450 -
1.2451 - /// Reserve memory for nodes.
1.2452 -
1.2453 - /// Using this function, it is possible to avoid superfluous memory
1.2454 - /// allocation: if you know that the graph you want to build will
1.2455 - /// be large (e.g. it will contain millions of nodes and/or edges),
1.2456 - /// then it is worth reserving space for this amount before starting
1.2457 - /// to build the graph.
1.2458 - /// \sa reserveEdge()
1.2459 - void reserveNode(int n) { nodes.reserve(n); };
1.2460 -
1.2461 - /// Reserve memory for edges.
1.2462 -
1.2463 - /// Using this function, it is possible to avoid superfluous memory
1.2464 - /// allocation: if you know that the graph you want to build will
1.2465 - /// be large (e.g. it will contain millions of nodes and/or edges),
1.2466 - /// then it is worth reserving space for this amount before starting
1.2467 - /// to build the graph.
1.2468 - /// \sa reserveNode()
1.2469 - void reserveEdge(int m) { arcs.reserve(2 * m); };
1.2470 -
1.2471 - /// \brief Class to make a snapshot of the graph and restore
1.2472 - /// it later.
1.2473 - ///
1.2474 - /// Class to make a snapshot of the graph and restore it later.
1.2475 - ///
1.2476 - /// The newly added nodes and edges can be removed
1.2477 - /// using the restore() function.
1.2478 - ///
1.2479 - /// \note After a state is restored, you cannot restore a later state,
1.2480 - /// i.e. you cannot add the removed nodes and edges again using
1.2481 - /// another Snapshot instance.
1.2482 - ///
1.2483 - /// \warning Node and edge deletions and other modifications
1.2484 - /// (e.g. changing the end-nodes of edges or contracting nodes)
1.2485 - /// cannot be restored. These events invalidate the snapshot.
1.2486 - /// However, the edges and nodes that were added to the graph after
1.2487 - /// making the current snapshot can be removed without invalidating it.
1.2488 - class Snapshot {
1.2489 - protected:
1.2490 -
1.2491 - typedef Parent::NodeNotifier NodeNotifier;
1.2492 -
1.2493 - class NodeObserverProxy : public NodeNotifier::ObserverBase {
1.2494 - public:
1.2495 -
1.2496 - NodeObserverProxy(Snapshot& _snapshot)
1.2497 - : snapshot(_snapshot) {}
1.2498 -
1.2499 - using NodeNotifier::ObserverBase::attach;
1.2500 - using NodeNotifier::ObserverBase::detach;
1.2501 - using NodeNotifier::ObserverBase::attached;
1.2502 -
1.2503 - protected:
1.2504 -
1.2505 - virtual void add(const Node& node) {
1.2506 - snapshot.addNode(node);
1.2507 - }
1.2508 - virtual void add(const std::vector<Node>& nodes) {
1.2509 - for (int i = nodes.size() - 1; i >= 0; ++i) {
1.2510 - snapshot.addNode(nodes[i]);
1.2511 - }
1.2512 - }
1.2513 - virtual void erase(const Node& node) {
1.2514 - snapshot.eraseNode(node);
1.2515 - }
1.2516 - virtual void erase(const std::vector<Node>& nodes) {
1.2517 - for (int i = 0; i < int(nodes.size()); ++i) {
1.2518 - snapshot.eraseNode(nodes[i]);
1.2519 - }
1.2520 - }
1.2521 - virtual void build() {
1.2522 - Node node;
1.2523 - std::vector<Node> nodes;
1.2524 - for (notifier()->first(node); node != INVALID;
1.2525 - notifier()->next(node)) {
1.2526 - nodes.push_back(node);
1.2527 - }
1.2528 - for (int i = nodes.size() - 1; i >= 0; --i) {
1.2529 - snapshot.addNode(nodes[i]);
1.2530 - }
1.2531 - }
1.2532 - virtual void clear() {
1.2533 - Node node;
1.2534 - for (notifier()->first(node); node != INVALID;
1.2535 - notifier()->next(node)) {
1.2536 - snapshot.eraseNode(node);
1.2537 - }
1.2538 - }
1.2539 -
1.2540 - Snapshot& snapshot;
1.2541 - };
1.2542 -
1.2543 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1.2544 public:
1.2545
1.2546 @@ -1478,911 +2383,6 @@
1.2547 Snapshot& snapshot;
1.2548 };
1.2549
1.2550 - ListGraph *graph;
1.2551 -
1.2552 - NodeObserverProxy node_observer_proxy;
1.2553 - EdgeObserverProxy edge_observer_proxy;
1.2554 -
1.2555 - std::list<Node> added_nodes;
1.2556 - std::list<Edge> added_edges;
1.2557 -
1.2558 -
1.2559 - void addNode(const Node& node) {
1.2560 - added_nodes.push_front(node);
1.2561 - }
1.2562 - void eraseNode(const Node& node) {
1.2563 - std::list<Node>::iterator it =
1.2564 - std::find(added_nodes.begin(), added_nodes.end(), node);
1.2565 - if (it == added_nodes.end()) {
1.2566 - clear();
1.2567 - edge_observer_proxy.detach();
1.2568 - throw NodeNotifier::ImmediateDetach();
1.2569 - } else {
1.2570 - added_nodes.erase(it);
1.2571 - }
1.2572 - }
1.2573 -
1.2574 - void addEdge(const Edge& edge) {
1.2575 - added_edges.push_front(edge);
1.2576 - }
1.2577 - void eraseEdge(const Edge& edge) {
1.2578 - std::list<Edge>::iterator it =
1.2579 - std::find(added_edges.begin(), added_edges.end(), edge);
1.2580 - if (it == added_edges.end()) {
1.2581 - clear();
1.2582 - node_observer_proxy.detach();
1.2583 - throw EdgeNotifier::ImmediateDetach();
1.2584 - } else {
1.2585 - added_edges.erase(it);
1.2586 - }
1.2587 - }
1.2588 -
1.2589 - void attach(ListGraph &_graph) {
1.2590 - graph = &_graph;
1.2591 - node_observer_proxy.attach(graph->notifier(Node()));
1.2592 - edge_observer_proxy.attach(graph->notifier(Edge()));
1.2593 - }
1.2594 -
1.2595 - void detach() {
1.2596 - node_observer_proxy.detach();
1.2597 - edge_observer_proxy.detach();
1.2598 - }
1.2599 -
1.2600 - bool attached() const {
1.2601 - return node_observer_proxy.attached();
1.2602 - }
1.2603 -
1.2604 - void clear() {
1.2605 - added_nodes.clear();
1.2606 - added_edges.clear();
1.2607 - }
1.2608 -
1.2609 - public:
1.2610 -
1.2611 - /// \brief Default constructor.
1.2612 - ///
1.2613 - /// Default constructor.
1.2614 - /// You have to call save() to actually make a snapshot.
1.2615 - Snapshot()
1.2616 - : graph(0), node_observer_proxy(*this),
1.2617 - edge_observer_proxy(*this) {}
1.2618 -
1.2619 - /// \brief Constructor that immediately makes a snapshot.
1.2620 - ///
1.2621 - /// This constructor immediately makes a snapshot of the given graph.
1.2622 - Snapshot(ListGraph &gr)
1.2623 - : node_observer_proxy(*this),
1.2624 - edge_observer_proxy(*this) {
1.2625 - attach(gr);
1.2626 - }
1.2627 -
1.2628 - /// \brief Make a snapshot.
1.2629 - ///
1.2630 - /// This function makes a snapshot of the given graph.
1.2631 - /// It can be called more than once. In case of a repeated
1.2632 - /// call, the previous snapshot gets lost.
1.2633 - void save(ListGraph &gr) {
1.2634 - if (attached()) {
1.2635 - detach();
1.2636 - clear();
1.2637 - }
1.2638 - attach(gr);
1.2639 - }
1.2640 -
1.2641 - /// \brief Undo the changes until the last snapshot.
1.2642 - ///
1.2643 - /// This function undos the changes until the last snapshot
1.2644 - /// created by save() or Snapshot(ListGraph&).
1.2645 - ///
1.2646 - /// \warning This method invalidates the snapshot, i.e. repeated
1.2647 - /// restoring is not supported unless you call save() again.
1.2648 - void restore() {
1.2649 - detach();
1.2650 - for(std::list<Edge>::iterator it = added_edges.begin();
1.2651 - it != added_edges.end(); ++it) {
1.2652 - graph->erase(*it);
1.2653 - }
1.2654 - for(std::list<Node>::iterator it = added_nodes.begin();
1.2655 - it != added_nodes.end(); ++it) {
1.2656 - graph->erase(*it);
1.2657 - }
1.2658 - clear();
1.2659 - }
1.2660 -
1.2661 - /// \brief Returns \c true if the snapshot is valid.
1.2662 - ///
1.2663 - /// This function returns \c true if the snapshot is valid.
1.2664 - bool valid() const {
1.2665 - return attached();
1.2666 - }
1.2667 - };
1.2668 - };
1.2669 -
1.2670 - /// @}
1.2671 -
1.2672 - class ListBpGraphBase {
1.2673 -
1.2674 - protected:
1.2675 -
1.2676 - struct NodeT {
1.2677 - int first_out;
1.2678 - int prev, next;
1.2679 - int partition_prev, partition_next;
1.2680 - int partition_index;
1.2681 - bool red;
1.2682 - };
1.2683 -
1.2684 - struct ArcT {
1.2685 - int target;
1.2686 - int prev_out, next_out;
1.2687 - };
1.2688 -
1.2689 - std::vector<NodeT> nodes;
1.2690 -
1.2691 - int first_node, first_red, first_blue;
1.2692 - int max_red, max_blue;
1.2693 -
1.2694 - int first_free_red, first_free_blue;
1.2695 -
1.2696 - std::vector<ArcT> arcs;
1.2697 -
1.2698 - int first_free_arc;
1.2699 -
1.2700 - public:
1.2701 -
1.2702 - typedef ListBpGraphBase BpGraph;
1.2703 -
1.2704 - class Node {
1.2705 - friend class ListBpGraphBase;
1.2706 - protected:
1.2707 -
1.2708 - int id;
1.2709 - explicit Node(int pid) { id = pid;}
1.2710 -
1.2711 - public:
1.2712 - Node() {}
1.2713 - Node (Invalid) { id = -1; }
1.2714 - bool operator==(const Node& node) const {return id == node.id;}
1.2715 - bool operator!=(const Node& node) const {return id != node.id;}
1.2716 - bool operator<(const Node& node) const {return id < node.id;}
1.2717 - };
1.2718 -
1.2719 - class RedNode : public Node {
1.2720 - friend class ListBpGraphBase;
1.2721 - protected:
1.2722 -
1.2723 - explicit RedNode(int pid) : Node(pid) {}
1.2724 -
1.2725 - public:
1.2726 - RedNode() {}
1.2727 - RedNode(const RedNode& node) : Node(node) {}
1.2728 - RedNode(Invalid) : Node(INVALID){}
1.2729 - };
1.2730 -
1.2731 - class BlueNode : public Node {
1.2732 - friend class ListBpGraphBase;
1.2733 - protected:
1.2734 -
1.2735 - explicit BlueNode(int pid) : Node(pid) {}
1.2736 -
1.2737 - public:
1.2738 - BlueNode() {}
1.2739 - BlueNode(const BlueNode& node) : Node(node) {}
1.2740 - BlueNode(Invalid) : Node(INVALID){}
1.2741 - };
1.2742 -
1.2743 - class Edge {
1.2744 - friend class ListBpGraphBase;
1.2745 - protected:
1.2746 -
1.2747 - int id;
1.2748 - explicit Edge(int pid) { id = pid;}
1.2749 -
1.2750 - public:
1.2751 - Edge() {}
1.2752 - Edge (Invalid) { id = -1; }
1.2753 - bool operator==(const Edge& edge) const {return id == edge.id;}
1.2754 - bool operator!=(const Edge& edge) const {return id != edge.id;}
1.2755 - bool operator<(const Edge& edge) const {return id < edge.id;}
1.2756 - };
1.2757 -
1.2758 - class Arc {
1.2759 - friend class ListBpGraphBase;
1.2760 - protected:
1.2761 -
1.2762 - int id;
1.2763 - explicit Arc(int pid) { id = pid;}
1.2764 -
1.2765 - public:
1.2766 - operator Edge() const {
1.2767 - return id != -1 ? edgeFromId(id / 2) : INVALID;
1.2768 - }
1.2769 -
1.2770 - Arc() {}
1.2771 - Arc (Invalid) { id = -1; }
1.2772 - bool operator==(const Arc& arc) const {return id == arc.id;}
1.2773 - bool operator!=(const Arc& arc) const {return id != arc.id;}
1.2774 - bool operator<(const Arc& arc) const {return id < arc.id;}
1.2775 - };
1.2776 -
1.2777 - ListBpGraphBase()
1.2778 - : nodes(), first_node(-1),
1.2779 - first_red(-1), first_blue(-1),
1.2780 - max_red(-1), max_blue(-1),
1.2781 - first_free_red(-1), first_free_blue(-1),
1.2782 - arcs(), first_free_arc(-1) {}
1.2783 -
1.2784 -
1.2785 - bool red(Node n) const { return nodes[n.id].red; }
1.2786 - bool blue(Node n) const { return !nodes[n.id].red; }
1.2787 -
1.2788 - static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
1.2789 - static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
1.2790 -
1.2791 - int maxNodeId() const { return nodes.size()-1; }
1.2792 - int maxRedId() const { return max_red; }
1.2793 - int maxBlueId() const { return max_blue; }
1.2794 - int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.2795 - int maxArcId() const { return arcs.size()-1; }
1.2796 -
1.2797 - Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
1.2798 - Node target(Arc e) const { return Node(arcs[e.id].target); }
1.2799 -
1.2800 - RedNode redNode(Edge e) const {
1.2801 - return RedNode(arcs[2 * e.id].target);
1.2802 - }
1.2803 - BlueNode blueNode(Edge e) const {
1.2804 - return BlueNode(arcs[2 * e.id + 1].target);
1.2805 - }
1.2806 -
1.2807 - static bool direction(Arc e) {
1.2808 - return (e.id & 1) == 1;
1.2809 - }
1.2810 -
1.2811 - static Arc direct(Edge e, bool d) {
1.2812 - return Arc(e.id * 2 + (d ? 1 : 0));
1.2813 - }
1.2814 -
1.2815 - void first(Node& node) const {
1.2816 - node.id = first_node;
1.2817 - }
1.2818 -
1.2819 - void next(Node& node) const {
1.2820 - node.id = nodes[node.id].next;
1.2821 - }
1.2822 -
1.2823 - void first(RedNode& node) const {
1.2824 - node.id = first_red;
1.2825 - }
1.2826 -
1.2827 - void next(RedNode& node) const {
1.2828 - node.id = nodes[node.id].partition_next;
1.2829 - }
1.2830 -
1.2831 - void first(BlueNode& node) const {
1.2832 - node.id = first_blue;
1.2833 - }
1.2834 -
1.2835 - void next(BlueNode& node) const {
1.2836 - node.id = nodes[node.id].partition_next;
1.2837 - }
1.2838 -
1.2839 - void first(Arc& e) const {
1.2840 - int n = first_node;
1.2841 - while (n != -1 && nodes[n].first_out == -1) {
1.2842 - n = nodes[n].next;
1.2843 - }
1.2844 - e.id = (n == -1) ? -1 : nodes[n].first_out;
1.2845 - }
1.2846 -
1.2847 - void next(Arc& e) const {
1.2848 - if (arcs[e.id].next_out != -1) {
1.2849 - e.id = arcs[e.id].next_out;
1.2850 - } else {
1.2851 - int n = nodes[arcs[e.id ^ 1].target].next;
1.2852 - while(n != -1 && nodes[n].first_out == -1) {
1.2853 - n = nodes[n].next;
1.2854 - }
1.2855 - e.id = (n == -1) ? -1 : nodes[n].first_out;
1.2856 - }
1.2857 - }
1.2858 -
1.2859 - void first(Edge& e) const {
1.2860 - int n = first_node;
1.2861 - while (n != -1) {
1.2862 - e.id = nodes[n].first_out;
1.2863 - while ((e.id & 1) != 1) {
1.2864 - e.id = arcs[e.id].next_out;
1.2865 - }
1.2866 - if (e.id != -1) {
1.2867 - e.id /= 2;
1.2868 - return;
1.2869 - }
1.2870 - n = nodes[n].next;
1.2871 - }
1.2872 - e.id = -1;
1.2873 - }
1.2874 -
1.2875 - void next(Edge& e) const {
1.2876 - int n = arcs[e.id * 2].target;
1.2877 - e.id = arcs[(e.id * 2) | 1].next_out;
1.2878 - while ((e.id & 1) != 1) {
1.2879 - e.id = arcs[e.id].next_out;
1.2880 - }
1.2881 - if (e.id != -1) {
1.2882 - e.id /= 2;
1.2883 - return;
1.2884 - }
1.2885 - n = nodes[n].next;
1.2886 - while (n != -1) {
1.2887 - e.id = nodes[n].first_out;
1.2888 - while ((e.id & 1) != 1) {
1.2889 - e.id = arcs[e.id].next_out;
1.2890 - }
1.2891 - if (e.id != -1) {
1.2892 - e.id /= 2;
1.2893 - return;
1.2894 - }
1.2895 - n = nodes[n].next;
1.2896 - }
1.2897 - e.id = -1;
1.2898 - }
1.2899 -
1.2900 - void firstOut(Arc &e, const Node& v) const {
1.2901 - e.id = nodes[v.id].first_out;
1.2902 - }
1.2903 - void nextOut(Arc &e) const {
1.2904 - e.id = arcs[e.id].next_out;
1.2905 - }
1.2906 -
1.2907 - void firstIn(Arc &e, const Node& v) const {
1.2908 - e.id = ((nodes[v.id].first_out) ^ 1);
1.2909 - if (e.id == -2) e.id = -1;
1.2910 - }
1.2911 - void nextIn(Arc &e) const {
1.2912 - e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
1.2913 - if (e.id == -2) e.id = -1;
1.2914 - }
1.2915 -
1.2916 - void firstInc(Edge &e, bool& d, const Node& v) const {
1.2917 - int a = nodes[v.id].first_out;
1.2918 - if (a != -1 ) {
1.2919 - e.id = a / 2;
1.2920 - d = ((a & 1) == 1);
1.2921 - } else {
1.2922 - e.id = -1;
1.2923 - d = true;
1.2924 - }
1.2925 - }
1.2926 - void nextInc(Edge &e, bool& d) const {
1.2927 - int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
1.2928 - if (a != -1 ) {
1.2929 - e.id = a / 2;
1.2930 - d = ((a & 1) == 1);
1.2931 - } else {
1.2932 - e.id = -1;
1.2933 - d = true;
1.2934 - }
1.2935 - }
1.2936 -
1.2937 - static int id(Node v) { return v.id; }
1.2938 - int id(RedNode v) const { return nodes[v.id].partition_index; }
1.2939 - int id(BlueNode v) const { return nodes[v.id].partition_index; }
1.2940 - static int id(Arc e) { return e.id; }
1.2941 - static int id(Edge e) { return e.id; }
1.2942 -
1.2943 - static Node nodeFromId(int id) { return Node(id);}
1.2944 - static Arc arcFromId(int id) { return Arc(id);}
1.2945 - static Edge edgeFromId(int id) { return Edge(id);}
1.2946 -
1.2947 - bool valid(Node n) const {
1.2948 - return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
1.2949 - nodes[n.id].prev != -2;
1.2950 - }
1.2951 -
1.2952 - bool valid(Arc a) const {
1.2953 - return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1.2954 - arcs[a.id].prev_out != -2;
1.2955 - }
1.2956 -
1.2957 - bool valid(Edge e) const {
1.2958 - return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
1.2959 - arcs[2 * e.id].prev_out != -2;
1.2960 - }
1.2961 -
1.2962 - RedNode addRedNode() {
1.2963 - int n;
1.2964 -
1.2965 - if(first_free_red==-1) {
1.2966 - n = nodes.size();
1.2967 - nodes.push_back(NodeT());
1.2968 - nodes[n].partition_index = ++max_red;
1.2969 - nodes[n].red = true;
1.2970 - } else {
1.2971 - n = first_free_red;
1.2972 - first_free_red = nodes[n].next;
1.2973 - }
1.2974 -
1.2975 - nodes[n].next = first_node;
1.2976 - if (first_node != -1) nodes[first_node].prev = n;
1.2977 - first_node = n;
1.2978 - nodes[n].prev = -1;
1.2979 -
1.2980 - nodes[n].partition_next = first_red;
1.2981 - if (first_red != -1) nodes[first_red].partition_prev = n;
1.2982 - first_red = n;
1.2983 - nodes[n].partition_prev = -1;
1.2984 -
1.2985 - nodes[n].first_out = -1;
1.2986 -
1.2987 - return RedNode(n);
1.2988 - }
1.2989 -
1.2990 - BlueNode addBlueNode() {
1.2991 - int n;
1.2992 -
1.2993 - if(first_free_blue==-1) {
1.2994 - n = nodes.size();
1.2995 - nodes.push_back(NodeT());
1.2996 - nodes[n].partition_index = ++max_blue;
1.2997 - nodes[n].red = false;
1.2998 - } else {
1.2999 - n = first_free_blue;
1.3000 - first_free_blue = nodes[n].next;
1.3001 - }
1.3002 -
1.3003 - nodes[n].next = first_node;
1.3004 - if (first_node != -1) nodes[first_node].prev = n;
1.3005 - first_node = n;
1.3006 - nodes[n].prev = -1;
1.3007 -
1.3008 - nodes[n].partition_next = first_blue;
1.3009 - if (first_blue != -1) nodes[first_blue].partition_prev = n;
1.3010 - first_blue = n;
1.3011 - nodes[n].partition_prev = -1;
1.3012 -
1.3013 - nodes[n].first_out = -1;
1.3014 -
1.3015 - return BlueNode(n);
1.3016 - }
1.3017 -
1.3018 - Edge addEdge(Node u, Node v) {
1.3019 - int n;
1.3020 -
1.3021 - if (first_free_arc == -1) {
1.3022 - n = arcs.size();
1.3023 - arcs.push_back(ArcT());
1.3024 - arcs.push_back(ArcT());
1.3025 - } else {
1.3026 - n = first_free_arc;
1.3027 - first_free_arc = arcs[n].next_out;
1.3028 - }
1.3029 -
1.3030 - arcs[n].target = u.id;
1.3031 - arcs[n | 1].target = v.id;
1.3032 -
1.3033 - arcs[n].next_out = nodes[v.id].first_out;
1.3034 - if (nodes[v.id].first_out != -1) {
1.3035 - arcs[nodes[v.id].first_out].prev_out = n;
1.3036 - }
1.3037 - arcs[n].prev_out = -1;
1.3038 - nodes[v.id].first_out = n;
1.3039 -
1.3040 - arcs[n | 1].next_out = nodes[u.id].first_out;
1.3041 - if (nodes[u.id].first_out != -1) {
1.3042 - arcs[nodes[u.id].first_out].prev_out = (n | 1);
1.3043 - }
1.3044 - arcs[n | 1].prev_out = -1;
1.3045 - nodes[u.id].first_out = (n | 1);
1.3046 -
1.3047 - return Edge(n / 2);
1.3048 - }
1.3049 -
1.3050 - void erase(const Node& node) {
1.3051 - int n = node.id;
1.3052 -
1.3053 - if(nodes[n].next != -1) {
1.3054 - nodes[nodes[n].next].prev = nodes[n].prev;
1.3055 - }
1.3056 -
1.3057 - if(nodes[n].prev != -1) {
1.3058 - nodes[nodes[n].prev].next = nodes[n].next;
1.3059 - } else {
1.3060 - first_node = nodes[n].next;
1.3061 - }
1.3062 -
1.3063 - if (nodes[n].partition_next != -1) {
1.3064 - nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
1.3065 - }
1.3066 -
1.3067 - if (nodes[n].partition_prev != -1) {
1.3068 - nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
1.3069 - } else {
1.3070 - if (nodes[n].red) {
1.3071 - first_red = nodes[n].partition_next;
1.3072 - } else {
1.3073 - first_blue = nodes[n].partition_next;
1.3074 - }
1.3075 - }
1.3076 -
1.3077 - if (nodes[n].red) {
1.3078 - nodes[n].next = first_free_red;
1.3079 - first_free_red = n;
1.3080 - } else {
1.3081 - nodes[n].next = first_free_blue;
1.3082 - first_free_blue = n;
1.3083 - }
1.3084 - nodes[n].prev = -2;
1.3085 - }
1.3086 -
1.3087 - void erase(const Edge& edge) {
1.3088 - int n = edge.id * 2;
1.3089 -
1.3090 - if (arcs[n].next_out != -1) {
1.3091 - arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.3092 - }
1.3093 -
1.3094 - if (arcs[n].prev_out != -1) {
1.3095 - arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.3096 - } else {
1.3097 - nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1.3098 - }
1.3099 -
1.3100 - if (arcs[n | 1].next_out != -1) {
1.3101 - arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1.3102 - }
1.3103 -
1.3104 - if (arcs[n | 1].prev_out != -1) {
1.3105 - arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1.3106 - } else {
1.3107 - nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1.3108 - }
1.3109 -
1.3110 - arcs[n].next_out = first_free_arc;
1.3111 - first_free_arc = n;
1.3112 - arcs[n].prev_out = -2;
1.3113 - arcs[n | 1].prev_out = -2;
1.3114 -
1.3115 - }
1.3116 -
1.3117 - void clear() {
1.3118 - arcs.clear();
1.3119 - nodes.clear();
1.3120 - first_node = first_free_arc = first_red = first_blue =
1.3121 - max_red = max_blue = first_free_red = first_free_blue = -1;
1.3122 - }
1.3123 -
1.3124 - protected:
1.3125 -
1.3126 - void changeRed(Edge e, RedNode n) {
1.3127 - if(arcs[(2 * e.id) | 1].next_out != -1) {
1.3128 - arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1.3129 - arcs[(2 * e.id) | 1].prev_out;
1.3130 - }
1.3131 - if(arcs[(2 * e.id) | 1].prev_out != -1) {
1.3132 - arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1.3133 - arcs[(2 * e.id) | 1].next_out;
1.3134 - } else {
1.3135 - nodes[arcs[2 * e.id].target].first_out =
1.3136 - arcs[(2 * e.id) | 1].next_out;
1.3137 - }
1.3138 -
1.3139 - if (nodes[n.id].first_out != -1) {
1.3140 - arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1.3141 - }
1.3142 - arcs[2 * e.id].target = n.id;
1.3143 - arcs[(2 * e.id) | 1].prev_out = -1;
1.3144 - arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1.3145 - nodes[n.id].first_out = ((2 * e.id) | 1);
1.3146 - }
1.3147 -
1.3148 - void changeBlue(Edge e, BlueNode n) {
1.3149 - if(arcs[2 * e.id].next_out != -1) {
1.3150 - arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1.3151 - }
1.3152 - if(arcs[2 * e.id].prev_out != -1) {
1.3153 - arcs[arcs[2 * e.id].prev_out].next_out =
1.3154 - arcs[2 * e.id].next_out;
1.3155 - } else {
1.3156 - nodes[arcs[(2 * e.id) | 1].target].first_out =
1.3157 - arcs[2 * e.id].next_out;
1.3158 - }
1.3159 -
1.3160 - if (nodes[n.id].first_out != -1) {
1.3161 - arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1.3162 - }
1.3163 - arcs[(2 * e.id) | 1].target = n.id;
1.3164 - arcs[2 * e.id].prev_out = -1;
1.3165 - arcs[2 * e.id].next_out = nodes[n.id].first_out;
1.3166 - nodes[n.id].first_out = 2 * e.id;
1.3167 - }
1.3168 -
1.3169 - };
1.3170 -
1.3171 - typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
1.3172 -
1.3173 -
1.3174 - /// \addtogroup graphs
1.3175 - /// @{
1.3176 -
1.3177 - ///A general undirected graph structure.
1.3178 -
1.3179 - ///\ref ListBpGraph is a versatile and fast undirected graph
1.3180 - ///implementation based on linked lists that are stored in
1.3181 - ///\c std::vector structures.
1.3182 - ///
1.3183 - ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
1.3184 - ///and it also provides several useful additional functionalities.
1.3185 - ///Most of its member functions and nested classes are documented
1.3186 - ///only in the concept class.
1.3187 - ///
1.3188 - ///This class provides only linear time counting for nodes, edges and arcs.
1.3189 - ///
1.3190 - ///\sa concepts::BpGraph
1.3191 - ///\sa ListDigraph
1.3192 - class ListBpGraph : public ExtendedListBpGraphBase {
1.3193 - typedef ExtendedListBpGraphBase Parent;
1.3194 -
1.3195 - private:
1.3196 - /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
1.3197 - ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase() {};
1.3198 - /// \brief Assignment of a graph to another one is \e not allowed.
1.3199 - /// Use BpGraphCopy instead.
1.3200 - void operator=(const ListBpGraph &) {}
1.3201 - public:
1.3202 - /// Constructor
1.3203 -
1.3204 - /// Constructor.
1.3205 - ///
1.3206 - ListBpGraph() {}
1.3207 -
1.3208 - typedef Parent::OutArcIt IncEdgeIt;
1.3209 -
1.3210 - /// \brief Add a new red node to the graph.
1.3211 - ///
1.3212 - /// This function adds a red new node to the graph.
1.3213 - /// \return The new node.
1.3214 - RedNode addRedNode() { return Parent::addRedNode(); }
1.3215 -
1.3216 - /// \brief Add a new blue node to the graph.
1.3217 - ///
1.3218 - /// This function adds a blue new node to the graph.
1.3219 - /// \return The new node.
1.3220 - BlueNode addBlueNode() { return Parent::addBlueNode(); }
1.3221 -
1.3222 - /// \brief Add a new edge to the graph.
1.3223 - ///
1.3224 - /// This function adds a new edge to the graph between nodes
1.3225 - /// \c u and \c v with inherent orientation from node \c u to
1.3226 - /// node \c v.
1.3227 - /// \return The new edge.
1.3228 - Edge addEdge(RedNode u, BlueNode v) {
1.3229 - return Parent::addEdge(u, v);
1.3230 - }
1.3231 - Edge addEdge(BlueNode v, RedNode u) {
1.3232 - return Parent::addEdge(u, v);
1.3233 - }
1.3234 -
1.3235 - ///\brief Erase a node from the graph.
1.3236 - ///
1.3237 - /// This function erases the given node along with its incident arcs
1.3238 - /// from the graph.
1.3239 - ///
1.3240 - /// \note All iterators referencing the removed node or the incident
1.3241 - /// edges are invalidated, of course.
1.3242 - void erase(Node n) { Parent::erase(n); }
1.3243 -
1.3244 - ///\brief Erase an edge from the graph.
1.3245 - ///
1.3246 - /// This function erases the given edge from the graph.
1.3247 - ///
1.3248 - /// \note All iterators referencing the removed edge are invalidated,
1.3249 - /// of course.
1.3250 - void erase(Edge e) { Parent::erase(e); }
1.3251 - /// Node validity check
1.3252 -
1.3253 - /// This function gives back \c true if the given node is valid,
1.3254 - /// i.e. it is a real node of the graph.
1.3255 - ///
1.3256 - /// \warning A removed node could become valid again if new nodes are
1.3257 - /// added to the graph.
1.3258 - bool valid(Node n) const { return Parent::valid(n); }
1.3259 - /// Edge validity check
1.3260 -
1.3261 - /// This function gives back \c true if the given edge is valid,
1.3262 - /// i.e. it is a real edge of the graph.
1.3263 - ///
1.3264 - /// \warning A removed edge could become valid again if new edges are
1.3265 - /// added to the graph.
1.3266 - bool valid(Edge e) const { return Parent::valid(e); }
1.3267 - /// Arc validity check
1.3268 -
1.3269 - /// This function gives back \c true if the given arc is valid,
1.3270 - /// i.e. it is a real arc of the graph.
1.3271 - ///
1.3272 - /// \warning A removed arc could become valid again if new edges are
1.3273 - /// added to the graph.
1.3274 - bool valid(Arc a) const { return Parent::valid(a); }
1.3275 -
1.3276 - /// \brief Change the red node of an edge.
1.3277 - ///
1.3278 - /// This function changes the red node of the given edge \c e to \c n.
1.3279 - ///
1.3280 - ///\note \c EdgeIt and \c ArcIt iterators referencing the
1.3281 - ///changed edge are invalidated and all other iterators whose
1.3282 - ///base node is the changed node are also invalidated.
1.3283 - ///
1.3284 - ///\warning This functionality cannot be used together with the
1.3285 - ///Snapshot feature.
1.3286 - void changeRed(Edge e, RedNode n) {
1.3287 - Parent::changeRed(e, n);
1.3288 - }
1.3289 - /// \brief Change the blue node of an edge.
1.3290 - ///
1.3291 - /// This function changes the blue node of the given edge \c e to \c n.
1.3292 - ///
1.3293 - ///\note \c EdgeIt iterators referencing the changed edge remain
1.3294 - ///valid, but \c ArcIt iterators referencing the changed edge and
1.3295 - ///all other iterators whose base node is the changed node are also
1.3296 - ///invalidated.
1.3297 - ///
1.3298 - ///\warning This functionality cannot be used together with the
1.3299 - ///Snapshot feature.
1.3300 - void changeBlue(Edge e, BlueNode n) {
1.3301 - Parent::changeBlue(e, n);
1.3302 - }
1.3303 -
1.3304 - ///Clear the graph.
1.3305 -
1.3306 - ///This function erases all nodes and arcs from the graph.
1.3307 - ///
1.3308 - ///\note All iterators of the graph are invalidated, of course.
1.3309 - void clear() {
1.3310 - Parent::clear();
1.3311 - }
1.3312 -
1.3313 - /// Reserve memory for nodes.
1.3314 -
1.3315 - /// Using this function, it is possible to avoid superfluous memory
1.3316 - /// allocation: if you know that the graph you want to build will
1.3317 - /// be large (e.g. it will contain millions of nodes and/or edges),
1.3318 - /// then it is worth reserving space for this amount before starting
1.3319 - /// to build the graph.
1.3320 - /// \sa reserveEdge()
1.3321 - void reserveNode(int n) { nodes.reserve(n); };
1.3322 -
1.3323 - /// Reserve memory for edges.
1.3324 -
1.3325 - /// Using this function, it is possible to avoid superfluous memory
1.3326 - /// allocation: if you know that the graph you want to build will
1.3327 - /// be large (e.g. it will contain millions of nodes and/or edges),
1.3328 - /// then it is worth reserving space for this amount before starting
1.3329 - /// to build the graph.
1.3330 - /// \sa reserveNode()
1.3331 - void reserveEdge(int m) { arcs.reserve(2 * m); };
1.3332 -
1.3333 - /// \brief Class to make a snapshot of the graph and restore
1.3334 - /// it later.
1.3335 - ///
1.3336 - /// Class to make a snapshot of the graph and restore it later.
1.3337 - ///
1.3338 - /// The newly added nodes and edges can be removed
1.3339 - /// using the restore() function.
1.3340 - ///
1.3341 - /// \note After a state is restored, you cannot restore a later state,
1.3342 - /// i.e. you cannot add the removed nodes and edges again using
1.3343 - /// another Snapshot instance.
1.3344 - ///
1.3345 - /// \warning Node and edge deletions and other modifications
1.3346 - /// (e.g. changing the end-nodes of edges or contracting nodes)
1.3347 - /// cannot be restored. These events invalidate the snapshot.
1.3348 - /// However, the edges and nodes that were added to the graph after
1.3349 - /// making the current snapshot can be removed without invalidating it.
1.3350 - class Snapshot {
1.3351 - protected:
1.3352 -
1.3353 - typedef Parent::NodeNotifier NodeNotifier;
1.3354 -
1.3355 - class NodeObserverProxy : public NodeNotifier::ObserverBase {
1.3356 - public:
1.3357 -
1.3358 - NodeObserverProxy(Snapshot& _snapshot)
1.3359 - : snapshot(_snapshot) {}
1.3360 -
1.3361 - using NodeNotifier::ObserverBase::attach;
1.3362 - using NodeNotifier::ObserverBase::detach;
1.3363 - using NodeNotifier::ObserverBase::attached;
1.3364 -
1.3365 - protected:
1.3366 -
1.3367 - virtual void add(const Node& node) {
1.3368 - snapshot.addNode(node);
1.3369 - }
1.3370 - virtual void add(const std::vector<Node>& nodes) {
1.3371 - for (int i = nodes.size() - 1; i >= 0; ++i) {
1.3372 - snapshot.addNode(nodes[i]);
1.3373 - }
1.3374 - }
1.3375 - virtual void erase(const Node& node) {
1.3376 - snapshot.eraseNode(node);
1.3377 - }
1.3378 - virtual void erase(const std::vector<Node>& nodes) {
1.3379 - for (int i = 0; i < int(nodes.size()); ++i) {
1.3380 - snapshot.eraseNode(nodes[i]);
1.3381 - }
1.3382 - }
1.3383 - virtual void build() {
1.3384 - Node node;
1.3385 - std::vector<Node> nodes;
1.3386 - for (notifier()->first(node); node != INVALID;
1.3387 - notifier()->next(node)) {
1.3388 - nodes.push_back(node);
1.3389 - }
1.3390 - for (int i = nodes.size() - 1; i >= 0; --i) {
1.3391 - snapshot.addNode(nodes[i]);
1.3392 - }
1.3393 - }
1.3394 - virtual void clear() {
1.3395 - Node node;
1.3396 - for (notifier()->first(node); node != INVALID;
1.3397 - notifier()->next(node)) {
1.3398 - snapshot.eraseNode(node);
1.3399 - }
1.3400 - }
1.3401 -
1.3402 - Snapshot& snapshot;
1.3403 - };
1.3404 -
1.3405 - class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1.3406 - public:
1.3407 -
1.3408 - EdgeObserverProxy(Snapshot& _snapshot)
1.3409 - : snapshot(_snapshot) {}
1.3410 -
1.3411 - using EdgeNotifier::ObserverBase::attach;
1.3412 - using EdgeNotifier::ObserverBase::detach;
1.3413 - using EdgeNotifier::ObserverBase::attached;
1.3414 -
1.3415 - protected:
1.3416 -
1.3417 - virtual void add(const Edge& edge) {
1.3418 - snapshot.addEdge(edge);
1.3419 - }
1.3420 - virtual void add(const std::vector<Edge>& edges) {
1.3421 - for (int i = edges.size() - 1; i >= 0; ++i) {
1.3422 - snapshot.addEdge(edges[i]);
1.3423 - }
1.3424 - }
1.3425 - virtual void erase(const Edge& edge) {
1.3426 - snapshot.eraseEdge(edge);
1.3427 - }
1.3428 - virtual void erase(const std::vector<Edge>& edges) {
1.3429 - for (int i = 0; i < int(edges.size()); ++i) {
1.3430 - snapshot.eraseEdge(edges[i]);
1.3431 - }
1.3432 - }
1.3433 - virtual void build() {
1.3434 - Edge edge;
1.3435 - std::vector<Edge> edges;
1.3436 - for (notifier()->first(edge); edge != INVALID;
1.3437 - notifier()->next(edge)) {
1.3438 - edges.push_back(edge);
1.3439 - }
1.3440 - for (int i = edges.size() - 1; i >= 0; --i) {
1.3441 - snapshot.addEdge(edges[i]);
1.3442 - }
1.3443 - }
1.3444 - virtual void clear() {
1.3445 - Edge edge;
1.3446 - for (notifier()->first(edge); edge != INVALID;
1.3447 - notifier()->next(edge)) {
1.3448 - snapshot.eraseEdge(edge);
1.3449 - }
1.3450 - }
1.3451 -
1.3452 - Snapshot& snapshot;
1.3453 - };
1.3454 -
1.3455 ListBpGraph *graph;
1.3456
1.3457 NodeObserverProxy node_observer_proxy;