1.1 --- a/lemon/bits/graph_extender.h Mon Jul 16 16:21:40 2018 +0200
1.2 +++ b/lemon/bits/graph_extender.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2013
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -746,6 +746,587 @@
1.13
1.14 };
1.15
1.16 + // \ingroup _graphbits
1.17 + //
1.18 + // \brief Extender for the BpGraphs
1.19 + template <typename Base>
1.20 + class BpGraphExtender : public Base {
1.21 + typedef Base Parent;
1.22 +
1.23 + public:
1.24 +
1.25 + typedef BpGraphExtender BpGraph;
1.26 +
1.27 + typedef True UndirectedTag;
1.28 +
1.29 + typedef typename Parent::Node Node;
1.30 + typedef typename Parent::RedNode RedNode;
1.31 + typedef typename Parent::BlueNode BlueNode;
1.32 + typedef typename Parent::Arc Arc;
1.33 + typedef typename Parent::Edge Edge;
1.34 +
1.35 + // BpGraph extension
1.36 +
1.37 + using Parent::first;
1.38 + using Parent::next;
1.39 + using Parent::id;
1.40 +
1.41 + int maxId(Node) const {
1.42 + return Parent::maxNodeId();
1.43 + }
1.44 +
1.45 + int maxId(RedNode) const {
1.46 + return Parent::maxRedId();
1.47 + }
1.48 +
1.49 + int maxId(BlueNode) const {
1.50 + return Parent::maxBlueId();
1.51 + }
1.52 +
1.53 + int maxId(Arc) const {
1.54 + return Parent::maxArcId();
1.55 + }
1.56 +
1.57 + int maxId(Edge) const {
1.58 + return Parent::maxEdgeId();
1.59 + }
1.60 +
1.61 + static Node fromId(int id, Node) {
1.62 + return Parent::nodeFromId(id);
1.63 + }
1.64 +
1.65 + static Arc fromId(int id, Arc) {
1.66 + return Parent::arcFromId(id);
1.67 + }
1.68 +
1.69 + static Edge fromId(int id, Edge) {
1.70 + return Parent::edgeFromId(id);
1.71 + }
1.72 +
1.73 + Node u(Edge e) const { return this->redNode(e); }
1.74 + Node v(Edge e) const { return this->blueNode(e); }
1.75 +
1.76 + Node oppositeNode(const Node &n, const Edge &e) const {
1.77 + if( n == u(e))
1.78 + return v(e);
1.79 + else if( n == v(e))
1.80 + return u(e);
1.81 + else
1.82 + return INVALID;
1.83 + }
1.84 +
1.85 + Arc oppositeArc(const Arc &arc) const {
1.86 + return Parent::direct(arc, !Parent::direction(arc));
1.87 + }
1.88 +
1.89 + using Parent::direct;
1.90 + Arc direct(const Edge &edge, const Node &node) const {
1.91 + return Parent::direct(edge, Parent::redNode(edge) == node);
1.92 + }
1.93 +
1.94 + RedNode asRedNode(const Node& node) const {
1.95 + if (node == INVALID || Parent::blue(node)) {
1.96 + return INVALID;
1.97 + } else {
1.98 + return Parent::asRedNodeUnsafe(node);
1.99 + }
1.100 + }
1.101 +
1.102 + BlueNode asBlueNode(const Node& node) const {
1.103 + if (node == INVALID || Parent::red(node)) {
1.104 + return INVALID;
1.105 + } else {
1.106 + return Parent::asBlueNodeUnsafe(node);
1.107 + }
1.108 + }
1.109 +
1.110 + // Alterable extension
1.111 +
1.112 + typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
1.113 + typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
1.114 + typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
1.115 + typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
1.116 + typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
1.117 +
1.118 +
1.119 + protected:
1.120 +
1.121 + mutable NodeNotifier node_notifier;
1.122 + mutable RedNodeNotifier red_node_notifier;
1.123 + mutable BlueNodeNotifier blue_node_notifier;
1.124 + mutable ArcNotifier arc_notifier;
1.125 + mutable EdgeNotifier edge_notifier;
1.126 +
1.127 + public:
1.128 +
1.129 + NodeNotifier& notifier(Node) const {
1.130 + return node_notifier;
1.131 + }
1.132 +
1.133 + RedNodeNotifier& notifier(RedNode) const {
1.134 + return red_node_notifier;
1.135 + }
1.136 +
1.137 + BlueNodeNotifier& notifier(BlueNode) const {
1.138 + return blue_node_notifier;
1.139 + }
1.140 +
1.141 + ArcNotifier& notifier(Arc) const {
1.142 + return arc_notifier;
1.143 + }
1.144 +
1.145 + EdgeNotifier& notifier(Edge) const {
1.146 + return edge_notifier;
1.147 + }
1.148 +
1.149 +
1.150 +
1.151 + class NodeIt : public Node {
1.152 + const BpGraph* _graph;
1.153 + public:
1.154 +
1.155 + NodeIt() {}
1.156 +
1.157 + NodeIt(Invalid i) : Node(i) { }
1.158 +
1.159 + explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
1.160 + _graph->first(static_cast<Node&>(*this));
1.161 + }
1.162 +
1.163 + NodeIt(const BpGraph& graph, const Node& node)
1.164 + : Node(node), _graph(&graph) {}
1.165 +
1.166 + NodeIt& operator++() {
1.167 + _graph->next(*this);
1.168 + return *this;
1.169 + }
1.170 +
1.171 + };
1.172 +
1.173 + class RedNodeIt : public RedNode {
1.174 + const BpGraph* _graph;
1.175 + public:
1.176 +
1.177 + RedNodeIt() {}
1.178 +
1.179 + RedNodeIt(Invalid i) : RedNode(i) { }
1.180 +
1.181 + explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
1.182 + _graph->first(static_cast<RedNode&>(*this));
1.183 + }
1.184 +
1.185 + RedNodeIt(const BpGraph& graph, const RedNode& node)
1.186 + : RedNode(node), _graph(&graph) {}
1.187 +
1.188 + RedNodeIt& operator++() {
1.189 + _graph->next(static_cast<RedNode&>(*this));
1.190 + return *this;
1.191 + }
1.192 +
1.193 + };
1.194 +
1.195 + class BlueNodeIt : public BlueNode {
1.196 + const BpGraph* _graph;
1.197 + public:
1.198 +
1.199 + BlueNodeIt() {}
1.200 +
1.201 + BlueNodeIt(Invalid i) : BlueNode(i) { }
1.202 +
1.203 + explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
1.204 + _graph->first(static_cast<BlueNode&>(*this));
1.205 + }
1.206 +
1.207 + BlueNodeIt(const BpGraph& graph, const BlueNode& node)
1.208 + : BlueNode(node), _graph(&graph) {}
1.209 +
1.210 + BlueNodeIt& operator++() {
1.211 + _graph->next(static_cast<BlueNode&>(*this));
1.212 + return *this;
1.213 + }
1.214 +
1.215 + };
1.216 +
1.217 +
1.218 + class ArcIt : public Arc {
1.219 + const BpGraph* _graph;
1.220 + public:
1.221 +
1.222 + ArcIt() { }
1.223 +
1.224 + ArcIt(Invalid i) : Arc(i) { }
1.225 +
1.226 + explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
1.227 + _graph->first(static_cast<Arc&>(*this));
1.228 + }
1.229 +
1.230 + ArcIt(const BpGraph& graph, const Arc& arc) :
1.231 + Arc(arc), _graph(&graph) { }
1.232 +
1.233 + ArcIt& operator++() {
1.234 + _graph->next(*this);
1.235 + return *this;
1.236 + }
1.237 +
1.238 + };
1.239 +
1.240 +
1.241 + class OutArcIt : public Arc {
1.242 + const BpGraph* _graph;
1.243 + public:
1.244 +
1.245 + OutArcIt() { }
1.246 +
1.247 + OutArcIt(Invalid i) : Arc(i) { }
1.248 +
1.249 + OutArcIt(const BpGraph& graph, const Node& node)
1.250 + : _graph(&graph) {
1.251 + _graph->firstOut(*this, node);
1.252 + }
1.253 +
1.254 + OutArcIt(const BpGraph& graph, const Arc& arc)
1.255 + : Arc(arc), _graph(&graph) {}
1.256 +
1.257 + OutArcIt& operator++() {
1.258 + _graph->nextOut(*this);
1.259 + return *this;
1.260 + }
1.261 +
1.262 + };
1.263 +
1.264 +
1.265 + class InArcIt : public Arc {
1.266 + const BpGraph* _graph;
1.267 + public:
1.268 +
1.269 + InArcIt() { }
1.270 +
1.271 + InArcIt(Invalid i) : Arc(i) { }
1.272 +
1.273 + InArcIt(const BpGraph& graph, const Node& node)
1.274 + : _graph(&graph) {
1.275 + _graph->firstIn(*this, node);
1.276 + }
1.277 +
1.278 + InArcIt(const BpGraph& graph, const Arc& arc) :
1.279 + Arc(arc), _graph(&graph) {}
1.280 +
1.281 + InArcIt& operator++() {
1.282 + _graph->nextIn(*this);
1.283 + return *this;
1.284 + }
1.285 +
1.286 + };
1.287 +
1.288 +
1.289 + class EdgeIt : public Parent::Edge {
1.290 + const BpGraph* _graph;
1.291 + public:
1.292 +
1.293 + EdgeIt() { }
1.294 +
1.295 + EdgeIt(Invalid i) : Edge(i) { }
1.296 +
1.297 + explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
1.298 + _graph->first(static_cast<Edge&>(*this));
1.299 + }
1.300 +
1.301 + EdgeIt(const BpGraph& graph, const Edge& edge) :
1.302 + Edge(edge), _graph(&graph) { }
1.303 +
1.304 + EdgeIt& operator++() {
1.305 + _graph->next(*this);
1.306 + return *this;
1.307 + }
1.308 +
1.309 + };
1.310 +
1.311 + class IncEdgeIt : public Parent::Edge {
1.312 + friend class BpGraphExtender;
1.313 + const BpGraph* _graph;
1.314 + bool _direction;
1.315 + public:
1.316 +
1.317 + IncEdgeIt() { }
1.318 +
1.319 + IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
1.320 +
1.321 + IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
1.322 + _graph->firstInc(*this, _direction, node);
1.323 + }
1.324 +
1.325 + IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
1.326 + : _graph(&graph), Edge(edge) {
1.327 + _direction = (_graph->source(edge) == node);
1.328 + }
1.329 +
1.330 + IncEdgeIt& operator++() {
1.331 + _graph->nextInc(*this, _direction);
1.332 + return *this;
1.333 + }
1.334 + };
1.335 +
1.336 + // \brief Base node of the iterator
1.337 + //
1.338 + // Returns the base node (ie. the source in this case) of the iterator
1.339 + Node baseNode(const OutArcIt &arc) const {
1.340 + return Parent::source(static_cast<const Arc&>(arc));
1.341 + }
1.342 + // \brief Running node of the iterator
1.343 + //
1.344 + // Returns the running node (ie. the target in this case) of the
1.345 + // iterator
1.346 + Node runningNode(const OutArcIt &arc) const {
1.347 + return Parent::target(static_cast<const Arc&>(arc));
1.348 + }
1.349 +
1.350 + // \brief Base node of the iterator
1.351 + //
1.352 + // Returns the base node (ie. the target in this case) of the iterator
1.353 + Node baseNode(const InArcIt &arc) const {
1.354 + return Parent::target(static_cast<const Arc&>(arc));
1.355 + }
1.356 + // \brief Running node of the iterator
1.357 + //
1.358 + // Returns the running node (ie. the source in this case) of the
1.359 + // iterator
1.360 + Node runningNode(const InArcIt &arc) const {
1.361 + return Parent::source(static_cast<const Arc&>(arc));
1.362 + }
1.363 +
1.364 + // Base node of the iterator
1.365 + //
1.366 + // Returns the base node of the iterator
1.367 + Node baseNode(const IncEdgeIt &edge) const {
1.368 + return edge._direction ? this->u(edge) : this->v(edge);
1.369 + }
1.370 + // Running node of the iterator
1.371 + //
1.372 + // Returns the running node of the iterator
1.373 + Node runningNode(const IncEdgeIt &edge) const {
1.374 + return edge._direction ? this->v(edge) : this->u(edge);
1.375 + }
1.376 +
1.377 + // Mappable extension
1.378 +
1.379 + template <typename _Value>
1.380 + class NodeMap
1.381 + : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
1.382 + typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
1.383 +
1.384 + public:
1.385 + explicit NodeMap(const BpGraph& bpgraph)
1.386 + : Parent(bpgraph) {}
1.387 + NodeMap(const BpGraph& bpgraph, const _Value& value)
1.388 + : Parent(bpgraph, value) {}
1.389 +
1.390 + private:
1.391 + NodeMap& operator=(const NodeMap& cmap) {
1.392 + return operator=<NodeMap>(cmap);
1.393 + }
1.394 +
1.395 + template <typename CMap>
1.396 + NodeMap& operator=(const CMap& cmap) {
1.397 + Parent::operator=(cmap);
1.398 + return *this;
1.399 + }
1.400 +
1.401 + };
1.402 +
1.403 + template <typename _Value>
1.404 + class RedNodeMap
1.405 + : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
1.406 + typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
1.407 +
1.408 + public:
1.409 + explicit RedNodeMap(const BpGraph& bpgraph)
1.410 + : Parent(bpgraph) {}
1.411 + RedNodeMap(const BpGraph& bpgraph, const _Value& value)
1.412 + : Parent(bpgraph, value) {}
1.413 +
1.414 + private:
1.415 + RedNodeMap& operator=(const RedNodeMap& cmap) {
1.416 + return operator=<RedNodeMap>(cmap);
1.417 + }
1.418 +
1.419 + template <typename CMap>
1.420 + RedNodeMap& operator=(const CMap& cmap) {
1.421 + Parent::operator=(cmap);
1.422 + return *this;
1.423 + }
1.424 +
1.425 + };
1.426 +
1.427 + template <typename _Value>
1.428 + class BlueNodeMap
1.429 + : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
1.430 + typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
1.431 +
1.432 + public:
1.433 + explicit BlueNodeMap(const BpGraph& bpgraph)
1.434 + : Parent(bpgraph) {}
1.435 + BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
1.436 + : Parent(bpgraph, value) {}
1.437 +
1.438 + private:
1.439 + BlueNodeMap& operator=(const BlueNodeMap& cmap) {
1.440 + return operator=<BlueNodeMap>(cmap);
1.441 + }
1.442 +
1.443 + template <typename CMap>
1.444 + BlueNodeMap& operator=(const CMap& cmap) {
1.445 + Parent::operator=(cmap);
1.446 + return *this;
1.447 + }
1.448 +
1.449 + };
1.450 +
1.451 + template <typename _Value>
1.452 + class ArcMap
1.453 + : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
1.454 + typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
1.455 +
1.456 + public:
1.457 + explicit ArcMap(const BpGraph& graph)
1.458 + : Parent(graph) {}
1.459 + ArcMap(const BpGraph& graph, const _Value& value)
1.460 + : Parent(graph, value) {}
1.461 +
1.462 + private:
1.463 + ArcMap& operator=(const ArcMap& cmap) {
1.464 + return operator=<ArcMap>(cmap);
1.465 + }
1.466 +
1.467 + template <typename CMap>
1.468 + ArcMap& operator=(const CMap& cmap) {
1.469 + Parent::operator=(cmap);
1.470 + return *this;
1.471 + }
1.472 + };
1.473 +
1.474 +
1.475 + template <typename _Value>
1.476 + class EdgeMap
1.477 + : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
1.478 + typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
1.479 +
1.480 + public:
1.481 + explicit EdgeMap(const BpGraph& graph)
1.482 + : Parent(graph) {}
1.483 +
1.484 + EdgeMap(const BpGraph& graph, const _Value& value)
1.485 + : Parent(graph, value) {}
1.486 +
1.487 + private:
1.488 + EdgeMap& operator=(const EdgeMap& cmap) {
1.489 + return operator=<EdgeMap>(cmap);
1.490 + }
1.491 +
1.492 + template <typename CMap>
1.493 + EdgeMap& operator=(const CMap& cmap) {
1.494 + Parent::operator=(cmap);
1.495 + return *this;
1.496 + }
1.497 +
1.498 + };
1.499 +
1.500 + // Alteration extension
1.501 +
1.502 + RedNode addRedNode() {
1.503 + RedNode node = Parent::addRedNode();
1.504 + notifier(RedNode()).add(node);
1.505 + notifier(Node()).add(node);
1.506 + return node;
1.507 + }
1.508 +
1.509 + BlueNode addBlueNode() {
1.510 + BlueNode node = Parent::addBlueNode();
1.511 + notifier(BlueNode()).add(node);
1.512 + notifier(Node()).add(node);
1.513 + return node;
1.514 + }
1.515 +
1.516 + Edge addEdge(const RedNode& from, const BlueNode& to) {
1.517 + Edge edge = Parent::addEdge(from, to);
1.518 + notifier(Edge()).add(edge);
1.519 + std::vector<Arc> av;
1.520 + av.push_back(Parent::direct(edge, true));
1.521 + av.push_back(Parent::direct(edge, false));
1.522 + notifier(Arc()).add(av);
1.523 + return edge;
1.524 + }
1.525 +
1.526 + void clear() {
1.527 + notifier(Arc()).clear();
1.528 + notifier(Edge()).clear();
1.529 + notifier(Node()).clear();
1.530 + notifier(BlueNode()).clear();
1.531 + notifier(RedNode()).clear();
1.532 + Parent::clear();
1.533 + }
1.534 +
1.535 + template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
1.536 + void build(const BpGraph& graph, NodeRefMap& nodeRef,
1.537 + EdgeRefMap& edgeRef) {
1.538 + Parent::build(graph, nodeRef, edgeRef);
1.539 + notifier(RedNode()).build();
1.540 + notifier(BlueNode()).build();
1.541 + notifier(Node()).build();
1.542 + notifier(Edge()).build();
1.543 + notifier(Arc()).build();
1.544 + }
1.545 +
1.546 + void erase(const Node& node) {
1.547 + Arc arc;
1.548 + Parent::firstOut(arc, node);
1.549 + while (arc != INVALID ) {
1.550 + erase(arc);
1.551 + Parent::firstOut(arc, node);
1.552 + }
1.553 +
1.554 + Parent::firstIn(arc, node);
1.555 + while (arc != INVALID ) {
1.556 + erase(arc);
1.557 + Parent::firstIn(arc, node);
1.558 + }
1.559 +
1.560 + if (Parent::red(node)) {
1.561 + notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
1.562 + } else {
1.563 + notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
1.564 + }
1.565 +
1.566 + notifier(Node()).erase(node);
1.567 + Parent::erase(node);
1.568 + }
1.569 +
1.570 + void erase(const Edge& edge) {
1.571 + std::vector<Arc> av;
1.572 + av.push_back(Parent::direct(edge, true));
1.573 + av.push_back(Parent::direct(edge, false));
1.574 + notifier(Arc()).erase(av);
1.575 + notifier(Edge()).erase(edge);
1.576 + Parent::erase(edge);
1.577 + }
1.578 +
1.579 + BpGraphExtender() {
1.580 + red_node_notifier.setContainer(*this);
1.581 + blue_node_notifier.setContainer(*this);
1.582 + node_notifier.setContainer(*this);
1.583 + arc_notifier.setContainer(*this);
1.584 + edge_notifier.setContainer(*this);
1.585 + }
1.586 +
1.587 + ~BpGraphExtender() {
1.588 + edge_notifier.clear();
1.589 + arc_notifier.clear();
1.590 + node_notifier.clear();
1.591 + blue_node_notifier.clear();
1.592 + red_node_notifier.clear();
1.593 + }
1.594 +
1.595 + };
1.596 +
1.597 }
1.598
1.599 #endif