1.1 --- a/src/work/marci/merge_node_graph_wrapper.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1189 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/merge_node_graph_wrapper.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef LEMON_MERGE_NODE_GRAPH_WRAPPER_H
1.21 -#define LEMON_MERGE_NODE_GRAPH_WRAPPER_H
1.22 -
1.23 -#include <lemon/invalid.h>
1.24 -#include <lemon/maps.h>
1.25 -#include <lemon/map_defines.h>
1.26 -#include <lemon/graph_wrapper.h>
1.27 -#include <iostream>
1.28 -
1.29 -using std::cout;
1.30 -using std::endl;
1.31 -
1.32 -#include <boost/type_traits.hpp>
1.33 -#include <boost/utility/enable_if.hpp>
1.34 -
1.35 -namespace lemon {
1.36 -
1.37 - template <class _Graph1>
1.38 - class P1 : public GraphWrapperBase<_Graph1> {
1.39 - };
1.40 -
1.41 - template <class _Graph2>
1.42 - class P2 : public GraphWrapperBase<_Graph2> {
1.43 - };
1.44 -
1.45 -
1.46 - template <typename _Graph1, typename _Graph2, typename Enable=void>
1.47 - class MergeNodeGraphWrapperBaseBase :
1.48 - public P1<_Graph1>, public P2<_Graph2> {
1.49 - public:
1.50 - static void printNode() { std::cout << "node: generic" << std::endl; }
1.51 - typedef _Graph1 Graph1;
1.52 - typedef _Graph2 Graph2;
1.53 - typedef P1<_Graph1> Parent1;
1.54 - typedef P2<_Graph2> Parent2;
1.55 - typedef typename Parent1::Node Graph1Node;
1.56 - typedef typename Parent2::Node Graph2Node;
1.57 - protected:
1.58 - MergeNodeGraphWrapperBaseBase() { }
1.59 - public:
1.60 -
1.61 - class Node : public Graph1Node, public Graph2Node {
1.62 - friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
1.63 - protected:
1.64 - bool backward; //true, iff backward
1.65 - public:
1.66 - Node() { }
1.67 - /// \todo =false is needed, or causes problems?
1.68 - /// If \c _backward is false, then we get an edge corresponding to the
1.69 - /// original one, otherwise its oppositely directed pair is obtained.
1.70 - Node(const Graph1Node& n1,
1.71 - const Graph2Node& n2, bool _backward) :
1.72 - Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
1.73 - Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
1.74 - bool operator==(const Node& v) const {
1.75 - if (backward)
1.76 - return (v.backward &&
1.77 - static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
1.78 - else
1.79 - return (!v.backward &&
1.80 - static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
1.81 - }
1.82 - bool operator!=(const Node& v) const {
1.83 - return !(*this==v);
1.84 - }
1.85 - };
1.86 -
1.87 - static bool forward(const Node& n) { return !n.backward; }
1.88 - static bool backward(const Node& n) { return n.backward; }
1.89 - static void setForward(Node& n) { n.backward=false; }
1.90 - static void setBackward(Node& n) { n.backward=true; }
1.91 - };
1.92 -
1.93 -
1.94 - template <typename _Graph1, typename _Graph2>
1.95 - class MergeNodeGraphWrapperBaseBase<
1.96 - _Graph1, _Graph2, typename boost::enable_if<
1.97 - boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
1.98 - public P1<_Graph1>, public P2<_Graph2> {
1.99 - public:
1.100 - static void printNode() { std::cout << "node: same" << std::endl; }
1.101 - typedef _Graph1 Graph1;
1.102 - typedef _Graph2 Graph2;
1.103 - typedef P1<_Graph1> Parent1;
1.104 - typedef P2<_Graph2> Parent2;
1.105 - typedef typename Parent1::Node Graph1Node;
1.106 - typedef typename Parent2::Node Graph2Node;
1.107 - protected:
1.108 - MergeNodeGraphWrapperBaseBase() { }
1.109 - public:
1.110 -
1.111 - class Node : public Graph1Node {
1.112 - friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
1.113 - protected:
1.114 - bool backward; //true, iff backward
1.115 - public:
1.116 - Node() { }
1.117 - /// \todo =false is needed, or causes problems?
1.118 - /// If \c _backward is false, then we get an edge corresponding to the
1.119 - /// original one, otherwise its oppositely directed pair is obtained.
1.120 - Node(const Graph1Node& n1,
1.121 - const Graph2Node& n2, bool _backward) :
1.122 - Graph1Node(!_backward ? n1 : n2), backward(_backward) { }
1.123 - Node(Invalid i) : Graph1Node(i), backward(true) { }
1.124 - bool operator==(const Node& v) const {
1.125 - return (backward==v.backward &&
1.126 - static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
1.127 - }
1.128 - bool operator!=(const Node& v) const {
1.129 - return !(*this==v);
1.130 - }
1.131 - };
1.132 -
1.133 - static bool forward(const Node& n) { return !n.backward; }
1.134 - static bool backward(const Node& n) { return n.backward; }
1.135 - static void setForward(Node& n) { n.backward=false; }
1.136 - static void setBackward(Node& n) { n.backward=true; }
1.137 - };
1.138 -
1.139 -
1.140 - template <typename _Graph1, typename _Graph2>
1.141 - class MergeNodeGraphWrapperBaseBase<
1.142 - _Graph1, _Graph2, typename boost::enable_if<
1.143 - boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
1.144 - public P1<_Graph1>, public P2<_Graph2> {
1.145 - public :
1.146 - static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }
1.147 - typedef _Graph1 Graph1;
1.148 - typedef _Graph2 Graph2;
1.149 - typedef P1<_Graph1> Parent1;
1.150 - typedef P2<_Graph2> Parent2;
1.151 - typedef typename Parent1::Node Graph1Node;
1.152 - typedef typename Parent2::Node Graph2Node;
1.153 - protected:
1.154 - MergeNodeGraphWrapperBaseBase() { }
1.155 - public:
1.156 -
1.157 - class Node : public Graph2Node {
1.158 - friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
1.159 - protected:
1.160 - bool backward; //true, iff backward
1.161 - public:
1.162 - Node() { }
1.163 - /// \todo =false is needed, or causes problems?
1.164 - /// If \c _backward is false, then we get an edge corresponding to the
1.165 - /// original one, otherwise its oppositely directed pair is obtained.
1.166 - Node(const Graph1Node& n1,
1.167 - const Graph2Node& n2, bool _backward) :
1.168 - Graph2Node(n2), backward(_backward) {
1.169 - if (!backward) *this=n1;
1.170 - }
1.171 - Node(Invalid i) : Graph2Node(i), backward(true) { }
1.172 - bool operator==(const Node& v) const {
1.173 - if (backward)
1.174 - return (v.backward &&
1.175 - static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
1.176 - else
1.177 - return (!v.backward &&
1.178 - static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
1.179 - }
1.180 - bool operator!=(const Node& v) const {
1.181 - return !(*this==v);
1.182 - }
1.183 - };
1.184 -
1.185 - static bool forward(const Node& n) { return !n.backward; }
1.186 - static bool backward(const Node& n) { return n.backward; }
1.187 - static void setForward(Node& n) { n.backward=false; }
1.188 - static void setBackward(Node& n) { n.backward=true; }
1.189 - };
1.190 -
1.191 -
1.192 - template <typename _Graph1, typename _Graph2>
1.193 - class MergeNodeGraphWrapperBaseBase<
1.194 - _Graph1, _Graph2, typename boost::enable_if<
1.195 - boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
1.196 - public P1<_Graph1>, public P2<_Graph2> {
1.197 - public :
1.198 - static void printNode() { std::cout << "node: 1st is derived" << std::endl; }
1.199 - typedef _Graph1 Graph1;
1.200 - typedef _Graph2 Graph2;
1.201 - typedef P1<_Graph1> Parent1;
1.202 - typedef P2<_Graph2> Parent2;
1.203 - typedef typename Parent1::Node Graph1Node;
1.204 - typedef typename Parent2::Node Graph2Node;
1.205 - protected:
1.206 - MergeNodeGraphWrapperBaseBase() { }
1.207 - public:
1.208 -
1.209 - class Node : public Graph1Node {
1.210 - friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
1.211 - protected:
1.212 - bool backward; //true, iff backward
1.213 - public:
1.214 - Node() { }
1.215 - /// \todo =false is needed, or causes problems?
1.216 - /// If \c _backward is false, then we get an edge corresponding to the
1.217 - /// original one, otherwise its oppositely directed pair is obtained.
1.218 - Node(const Graph1Node& n1,
1.219 - const Graph2Node& n2, bool _backward) :
1.220 - Graph1Node(n1), backward(_backward) {
1.221 - if (backward) *this=n2;
1.222 - }
1.223 - Node(Invalid i) : Graph1Node(i), backward(true) { }
1.224 - bool operator==(const Node& v) const {
1.225 - if (backward)
1.226 - return (v.backward &&
1.227 - static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
1.228 - else
1.229 - return (!v.backward &&
1.230 - static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
1.231 - }
1.232 - bool operator!=(const Node& v) const {
1.233 - return !(*this==v);
1.234 - }
1.235 - };
1.236 -
1.237 - static bool forward(const Node& n) { return !n.backward; }
1.238 - static bool backward(const Node& n) { return n.backward; }
1.239 - static void setForward(Node& n) { n.backward=false; }
1.240 - static void setBackward(Node& n) { n.backward=true; }
1.241 - };
1.242 -
1.243 -
1.244 - template <typename _Graph1, typename _Graph2>
1.245 - class MergeNodeGraphWrapperBase :
1.246 - public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> {
1.247 - public:
1.248 - typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
1.249 - typedef _Graph1 Graph1;
1.250 - typedef _Graph2 Graph2;
1.251 - typedef P1<_Graph1> Parent1;
1.252 - typedef P2<_Graph2> Parent2;
1.253 - typedef typename Parent1::Node Graph1Node;
1.254 - typedef typename Parent2::Node Graph2Node;
1.255 -
1.256 - typedef typename Parent::Node Node;
1.257 - class Edge { };
1.258 -
1.259 - void first(Node& i) const {
1.260 - Parent1::graph->first(*static_cast<Graph1Node*>(&i));
1.261 - this->setForward(i);
1.262 - if (*static_cast<Graph1Node*>(&i)==INVALID) {
1.263 - Parent2::graph->first(*static_cast<Graph2Node*>(&i));
1.264 - this->setBackward(i);
1.265 - }
1.266 - }
1.267 - void next(Node& i) const {
1.268 - if (this->forward(i)) {
1.269 - Parent1::graph->next(*static_cast<Graph1Node*>(&i));
1.270 - if (*static_cast<Graph1Node*>(&i)==INVALID) {
1.271 - Parent2::graph->first(*static_cast<Graph2Node*>(&i));
1.272 - this->setBackward(i);
1.273 - }
1.274 - } else {
1.275 - Parent2::graph->next(*static_cast<Graph2Node*>(&i));
1.276 - }
1.277 - }
1.278 -
1.279 - int id(const Node& n) const {
1.280 - if (this->forward(n))
1.281 - return this->Parent1::graph->id(n);
1.282 - else
1.283 - return this->Parent2::graph->id(n);
1.284 - }
1.285 -
1.286 - template <typename _Value>
1.287 - class NodeMap {
1.288 - protected:
1.289 - typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
1.290 - typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
1.291 - ParentMap1 forward_map;
1.292 - ParentMap2 backward_map;
1.293 - public:
1.294 - typedef _Value Value;
1.295 - typedef Node Key;
1.296 - NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
1.297 - forward_map(*(gw.Parent1::graph)),
1.298 - backward_map(*(gw.Parent2::graph)) { }
1.299 - NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
1.300 - const _Value& value) :
1.301 - forward_map(*(gw.Parent1::graph), value),
1.302 - backward_map(*(gw.Parent2::graph), value) { }
1.303 - _Value operator[](const Node& n) const {
1.304 - if (Parent::forward(n))
1.305 - return forward_map[n];
1.306 - else
1.307 - return backward_map[n];
1.308 - }
1.309 - void set(const Node& n, const _Value& value) {
1.310 - if (Parent::forward(n))
1.311 - forward_map.set(n, value);
1.312 - else
1.313 - backward_map.set(n, value);
1.314 - }
1.315 -// using ParentMap1::operator[];
1.316 -// using ParentMap2::operator[];
1.317 - };
1.318 -
1.319 - };
1.320 -
1.321 -
1.322 - /*! A graph wrapper class
1.323 - for merging the node-set of two node-disjoint graphs
1.324 - into the node-set of one graph.
1.325 - Different implementations are according to the relation of
1.326 - _Graph1::Node and _Graph2::Node.
1.327 - If _Graph1::Node and _Graph2::Node are unrelated, then
1.328 - MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
1.329 - is derived from both.
1.330 - If _Graph1::Node and _Graph2::Node are the same type, then
1.331 - MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
1.332 - is derived from _Graph1::Node.
1.333 - If one of _Graph1::Node and _Graph2::Node
1.334 - is derived from the other one, then
1.335 - MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
1.336 - is derived from the derived type.
1.337 - It does not satisfy
1.338 - StaticGraph concept as it has no edge-set which
1.339 - works together with the node-set.
1.340 - */
1.341 - template <typename _Graph1, typename _Graph2>
1.342 - class MergeNodeGraphWrapper : public
1.343 - IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
1.344 - public:
1.345 - typedef _Graph1 Graph1;
1.346 - typedef _Graph2 Graph2;
1.347 - typedef IterableGraphExtender<
1.348 - MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
1.349 - protected:
1.350 - MergeNodeGraphWrapper() { }
1.351 - public:
1.352 - MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
1.353 - Parent::Parent1::setGraph(_graph1);
1.354 - Parent::Parent2::setGraph(_graph2);
1.355 - }
1.356 - };
1.357 -
1.358 -
1.359 - /*! A grah wrapper base class
1.360 - for merging the node-sets and edge-sets of
1.361 - two node-disjoint graphs
1.362 - into one graph.
1.363 - Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
1.364 - */
1.365 - template <typename _Graph1, typename _Graph2, typename Enable=void>
1.366 - class MergeEdgeGraphWrapperBaseBase :
1.367 - public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
1.368 - public:
1.369 - static void printEdge() { std::cout << "edge: generic" << std::endl; }
1.370 - typedef _Graph1 Graph1;
1.371 - typedef _Graph2 Graph2;
1.372 - typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
1.373 - typedef typename Parent::Parent1 Parent1;
1.374 - typedef typename Parent::Parent2 Parent2;
1.375 -// typedef P1<_Graph1> Parent1;
1.376 -// typedef P2<_Graph2> Parent2;
1.377 - typedef typename Parent1::Edge Graph1Edge;
1.378 - typedef typename Parent2::Edge Graph2Edge;
1.379 - protected:
1.380 - MergeEdgeGraphWrapperBaseBase() { }
1.381 - public:
1.382 -
1.383 - class Edge : public Graph1Edge, public Graph2Edge {
1.384 - friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
1.385 - protected:
1.386 - bool backward; //true, iff backward
1.387 - public:
1.388 - Edge() { }
1.389 - /// \todo =false is needed, or causes problems?
1.390 - /// If \c _backward is false, then we get an edge corresponding to the
1.391 - /// original one, otherwise its oppositely directed pair is obtained.
1.392 - Edge(const Graph1Edge& n1,
1.393 - const Graph2Edge& n2, bool _backward) :
1.394 - Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
1.395 - Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
1.396 - bool operator==(const Edge& v) const {
1.397 - if (backward)
1.398 - return (v.backward &&
1.399 - static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
1.400 - else
1.401 - return (!v.backward &&
1.402 - static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
1.403 - }
1.404 - bool operator!=(const Edge& v) const {
1.405 - return !(*this==v);
1.406 - }
1.407 - };
1.408 -
1.409 - using Parent::forward;
1.410 - using Parent::backward;
1.411 - using Parent::setForward;
1.412 - using Parent::setBackward;
1.413 - static bool forward(const Edge& e) { return !e.backward; }
1.414 - static bool backward(const Edge& e) { return e.backward; }
1.415 - static void setForward(Edge& e) { e.backward=false; }
1.416 - static void setBackward(Edge& e) { e.backward=true; }
1.417 - };
1.418 -
1.419 -
1.420 -
1.421 - /*! A graph wrapper base class
1.422 - for merging the node-sets and edge-sets of
1.423 - two node-disjoint graphs
1.424 - into one graph.
1.425 - Specialization for the case when _Graph1::Edge and _Graph2::Edge
1.426 - are the same.
1.427 - */
1.428 - template <typename _Graph1, typename _Graph2>
1.429 - class MergeEdgeGraphWrapperBaseBase<
1.430 - _Graph1, _Graph2, typename boost::enable_if<
1.431 - boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
1.432 - public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
1.433 - public:
1.434 - static void printEdge() { std::cout << "edge: same" << std::endl; }
1.435 - typedef _Graph1 Graph1;
1.436 - typedef _Graph2 Graph2;
1.437 - typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
1.438 - typedef typename Parent::Parent1 Parent1;
1.439 - typedef typename Parent::Parent2 Parent2;
1.440 -// typedef P1<_Graph1> Parent1;
1.441 -// typedef P2<_Graph2> Parent2;
1.442 - typedef typename Parent1::Edge Graph1Edge;
1.443 - typedef typename Parent2::Edge Graph2Edge;
1.444 - protected:
1.445 - MergeEdgeGraphWrapperBaseBase() { }
1.446 - public:
1.447 -
1.448 - class Edge : public Graph1Edge {
1.449 - friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
1.450 - protected:
1.451 - bool backward; //true, iff backward
1.452 - public:
1.453 - Edge() { }
1.454 - /// \todo =false is needed, or causes problems?
1.455 - /// If \c _backward is false, then we get an edge corresponding to the
1.456 - /// original one, otherwise its oppositely directed pair is obtained.
1.457 - Edge(const Graph1Edge& n1,
1.458 - const Graph2Edge& n2, bool _backward) :
1.459 - Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }
1.460 - Edge(Invalid i) : Graph1Edge(i), backward(true) { }
1.461 - bool operator==(const Edge& v) const {
1.462 - return (backward==v.backward &&
1.463 - static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
1.464 - }
1.465 - bool operator!=(const Edge& v) const {
1.466 - return !(*this==v);
1.467 - }
1.468 - };
1.469 -
1.470 - using Parent::forward;
1.471 - using Parent::backward;
1.472 - using Parent::setForward;
1.473 - using Parent::setBackward;
1.474 - static bool forward(const Edge& e) { return !e.backward; }
1.475 - static bool backward(const Edge& e) { return e.backward; }
1.476 - static void setForward(Edge& e) { e.backward=false; }
1.477 - static void setBackward(Edge& e) { e.backward=true; }
1.478 - };
1.479 -
1.480 -
1.481 - /*! A grah wrapper base class
1.482 - for merging the node-sets and edge-sets of
1.483 - two node-disjoint graphs
1.484 - into one graph.
1.485 - Specialized implementation for the case
1.486 - when _Graph1::Edge is a base class and _Graph2::Edge
1.487 - is derived from it.
1.488 - */
1.489 - template <typename _Graph1, typename _Graph2>
1.490 - class MergeEdgeGraphWrapperBaseBase<
1.491 - _Graph1, _Graph2, typename boost::enable_if<
1.492 - boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
1.493 - public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
1.494 - public:
1.495 - static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; }
1.496 - typedef _Graph1 Graph1;
1.497 - typedef _Graph2 Graph2;
1.498 - typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
1.499 - typedef typename Parent::Parent1 Parent1;
1.500 - typedef typename Parent::Parent2 Parent2;
1.501 -// typedef P1<_Graph1> Parent1;
1.502 -// typedef P2<_Graph2> Parent2;
1.503 - typedef typename Parent1::Edge Graph1Edge;
1.504 - typedef typename Parent2::Edge Graph2Edge;
1.505 - protected:
1.506 - MergeEdgeGraphWrapperBaseBase() { }
1.507 - public:
1.508 -
1.509 - class Edge : public Graph2Edge {
1.510 - friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
1.511 - protected:
1.512 - bool backward; //true, iff backward
1.513 - public:
1.514 - Edge() { }
1.515 - /// \todo =false is needed, or causes problems?
1.516 - /// If \c _backward is false, then we get an edge corresponding to the
1.517 - /// original one, otherwise its oppositely directed pair is obtained.
1.518 - Edge(const Graph1Edge& n1,
1.519 - const Graph2Edge& n2, bool _backward) :
1.520 - Graph2Edge(n2), backward(_backward) {
1.521 - if (!backward) *this=n1;
1.522 - }
1.523 - Edge(Invalid i) : Graph2Edge(i), backward(true) { }
1.524 - bool operator==(const Edge& v) const {
1.525 - if (backward)
1.526 - return (v.backward &&
1.527 - static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
1.528 - else
1.529 - return (!v.backward &&
1.530 - static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
1.531 - }
1.532 - bool operator!=(const Edge& v) const {
1.533 - return !(*this==v);
1.534 - }
1.535 - };
1.536 -
1.537 - using Parent::forward;
1.538 - using Parent::backward;
1.539 - using Parent::setForward;
1.540 - using Parent::setBackward;
1.541 - static bool forward(const Edge& e) { return !e.backward; }
1.542 - static bool backward(const Edge& e) { return e.backward; }
1.543 - static void setForward(Edge& e) { e.backward=false; }
1.544 - static void setBackward(Edge& e) { e.backward=true; }
1.545 - };
1.546 -
1.547 -
1.548 - /*! A grah wrapper base class
1.549 - for merging the node-sets and edge-sets of
1.550 - two node-disjoint graphs
1.551 - into one graph.
1.552 - Specialized implementation for the case
1.553 - when _Graph1::Edge is derived from _Graph2::Edge.
1.554 - */
1.555 - template <typename _Graph1, typename _Graph2>
1.556 - class MergeEdgeGraphWrapperBaseBase<
1.557 - _Graph1, _Graph2, typename boost::enable_if<
1.558 - boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> :
1.559 - public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
1.560 - public:
1.561 - static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; }
1.562 - typedef _Graph1 Graph1;
1.563 - typedef _Graph2 Graph2;
1.564 - typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
1.565 - typedef typename Parent::Parent1 Parent1;
1.566 - typedef typename Parent::Parent2 Parent2;
1.567 -// typedef P1<_Graph1> Parent1;
1.568 -// typedef P2<_Graph2> Parent2;
1.569 - typedef typename Parent1::Edge Graph1Edge;
1.570 - typedef typename Parent2::Edge Graph2Edge;
1.571 - protected:
1.572 - MergeEdgeGraphWrapperBaseBase() { }
1.573 - public:
1.574 -
1.575 - class Edge : public Graph1Edge {
1.576 - friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
1.577 - protected:
1.578 - bool backward; //true, iff backward
1.579 - public:
1.580 - Edge() { }
1.581 - /// \todo =false is needed, or causes problems?
1.582 - /// If \c _backward is false, then we get an edge corresponding to the
1.583 - /// original one, otherwise its oppositely directed pair is obtained.
1.584 - Edge(const Graph1Edge& n1,
1.585 - const Graph2Edge& n2, bool _backward) :
1.586 - Graph1Edge(n1), backward(_backward) {
1.587 - if (backward) *this=n2;
1.588 - }
1.589 - Edge(Invalid i) : Graph1Edge(i), backward(true) { }
1.590 - bool operator==(const Edge& v) const {
1.591 - if (backward)
1.592 - return (v.backward &&
1.593 - static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
1.594 - else
1.595 - return (!v.backward &&
1.596 - static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
1.597 - }
1.598 - bool operator!=(const Edge& v) const {
1.599 - return !(*this==v);
1.600 - }
1.601 - };
1.602 -
1.603 - using Parent::forward;
1.604 - using Parent::backward;
1.605 - using Parent::setForward;
1.606 - using Parent::setBackward;
1.607 - static bool forward(const Edge& e) { return !e.backward; }
1.608 - static bool backward(const Edge& e) { return e.backward; }
1.609 - static void setForward(Edge& e) { e.backward=false; }
1.610 - static void setBackward(Edge& e) { e.backward=true; }
1.611 - };
1.612 -
1.613 -
1.614 - template <typename _Graph1, typename _Graph2>
1.615 - class MergeEdgeGraphWrapperBase :
1.616 - public MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> {
1.617 - public:
1.618 - typedef MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
1.619 - typedef _Graph1 Graph1;
1.620 - typedef _Graph2 Graph2;
1.621 - typedef typename Parent::Parent1 Parent1;
1.622 - typedef typename Parent::Parent2 Parent2;
1.623 - typedef typename Parent1::Node Graph1Node;
1.624 - typedef typename Parent2::Node Graph2Node;
1.625 - typedef typename Parent1::Edge Graph1Edge;
1.626 - typedef typename Parent2::Edge Graph2Edge;
1.627 -
1.628 - typedef typename Parent::Node Node;
1.629 - typedef typename Parent::Edge Edge;
1.630 -
1.631 - using Parent::first;
1.632 - void first(Edge& i) const {
1.633 - Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
1.634 - this->setForward(i);
1.635 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.636 - Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
1.637 - this->setBackward(i);
1.638 - }
1.639 - }
1.640 - void firstIn(Edge& i, const Node& n) const {
1.641 - if (forward(n)) {
1.642 - Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
1.643 - if (*static_cast<Graph1Edge*>(&i)==INVALID)
1.644 - i=INVALID;
1.645 - else
1.646 - this->setForward(i);
1.647 - } else {
1.648 - Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
1.649 - this->setBackward(i);
1.650 - }
1.651 - }
1.652 - void firstOut(Edge& i, const Node& n) const {
1.653 - if (forward(n)) {
1.654 - Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
1.655 - if (*static_cast<Graph1Edge*>(&i)==INVALID)
1.656 - i=INVALID;
1.657 - else
1.658 - this->setForward(i);
1.659 - } else {
1.660 - Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
1.661 - this->setBackward(i);
1.662 - }
1.663 - }
1.664 -
1.665 - using Parent::next;
1.666 - void next(Edge& i) const {
1.667 - if (forward(i)) {
1.668 - Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
1.669 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.670 - Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
1.671 - this->setBackward(i);
1.672 - }
1.673 - } else {
1.674 - Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
1.675 - }
1.676 - }
1.677 - void nextIn(Edge& i) const {
1.678 - if (forward(i)) {
1.679 - Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
1.680 - if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
1.681 - } else {
1.682 - Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
1.683 - }
1.684 - }
1.685 - void nextOut(Edge& i) const {
1.686 - if (Parent::forward(i)) {
1.687 - Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
1.688 - if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
1.689 - } else {
1.690 - Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
1.691 - }
1.692 - }
1.693 -
1.694 - Node source(const Edge& i) const {
1.695 - if (forward(i)) {
1.696 - return
1.697 - Node(Parent1::graph->source(i), INVALID, false);
1.698 - } else {
1.699 - return
1.700 - Node(INVALID, Parent2::graph->source(i), true);
1.701 - }
1.702 - }
1.703 -
1.704 - Node target(const Edge& i) const {
1.705 - if (forward(i)) {
1.706 - return
1.707 - Node(Parent1::graph->target(i), INVALID, false);
1.708 - } else {
1.709 - return
1.710 - Node(INVALID, Parent2::graph->target(i), true);
1.711 - }
1.712 - }
1.713 -
1.714 - using Parent::id;
1.715 - int id(const Edge& n) const {
1.716 - if (forward(n))
1.717 - return this->Parent1::graph->id(n);
1.718 - else
1.719 - return this->Parent2::graph->id(n);
1.720 - }
1.721 -
1.722 - template <typename _Value>
1.723 - class EdgeMap {
1.724 - protected:
1.725 - typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
1.726 - typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
1.727 - ParentMap1 forward_map;
1.728 - ParentMap2 backward_map;
1.729 - public:
1.730 - typedef _Value Value;
1.731 - typedef Edge Key;
1.732 - EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
1.733 - forward_map(*(gw.Parent1::graph)),
1.734 - backward_map(*(gw.Parent2::graph)) { }
1.735 - EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
1.736 - const _Value& value) :
1.737 - forward_map(*(gw.Parent1::graph), value),
1.738 - backward_map(*(gw.Parent2::graph), value) { }
1.739 - _Value operator[](const Edge& n) const {
1.740 - if (Parent::forward(n))
1.741 - return forward_map[n];
1.742 - else
1.743 - return backward_map[n];
1.744 - }
1.745 - void set(const Edge& n, const _Value& value) {
1.746 - if (Parent::forward(n))
1.747 - forward_map.set(n, value);
1.748 - else
1.749 - backward_map.set(n, value);
1.750 - }
1.751 -// using ParentMap1::operator[];
1.752 -// using ParentMap2::operator[];
1.753 - };
1.754 -
1.755 - };
1.756 -
1.757 -
1.758 -
1.759 - /*! A graph wrapper class
1.760 - for merging two node-disjoint graphs
1.761 - into one graph.
1.762 - Different implementations are according to the relation of
1.763 - _Graph1::Edge and _Graph2::Edge.
1.764 - If _Graph1::Edge and _Graph2::Edge are unrelated, then
1.765 - MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
1.766 - is derived from both.
1.767 - If _Graph1::Edge and _Graph2::Edge are the same type, then
1.768 - MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
1.769 - is derived from _Graph1::Edge.
1.770 - If one of _Graph1::Edge and _Graph2::Edge
1.771 - is derived from the other one, then
1.772 - MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
1.773 - is derived from the derived type.
1.774 - It does not satisfy
1.775 - */
1.776 - template <typename _Graph1, typename _Graph2>
1.777 - class MergeEdgeGraphWrapper : public
1.778 - IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
1.779 - public:
1.780 - typedef _Graph1 Graph1;
1.781 - typedef _Graph2 Graph2;
1.782 - typedef IterableGraphExtender<
1.783 - MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
1.784 - protected:
1.785 - MergeEdgeGraphWrapper() { }
1.786 - public:
1.787 - MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
1.788 - Parent::Parent1::setGraph(_graph1);
1.789 - Parent::Parent2::setGraph(_graph2);
1.790 - }
1.791 - };
1.792 -
1.793 -
1.794 - /*! A graph wrapper base class for the following functionality.
1.795 - If a bijection is given between the node-sets of two graphs,
1.796 - then the second one can be considered as a new edge-set
1.797 - over th first node-set.
1.798 - */
1.799 - template <typename _Graph, typename _EdgeSetGraph>
1.800 - class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
1.801 - public:
1.802 - typedef GraphWrapperBase<_Graph> Parent;
1.803 - typedef _Graph Graph;
1.804 - typedef _EdgeSetGraph EdgeSetGraph;
1.805 - typedef typename _Graph::Node Node;
1.806 - typedef typename _EdgeSetGraph::Node ENode;
1.807 - protected:
1.808 - EdgeSetGraph* edge_set_graph;
1.809 - typename Graph::NodeMap<ENode>* e_node;
1.810 - typename EdgeSetGraph::NodeMap<Node>* n_node;
1.811 - void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) {
1.812 - edge_set_graph=&_edge_set_graph;
1.813 - }
1.814 - /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
1.815 - void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
1.816 - n_node=&_n_node;
1.817 - }
1.818 - /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
1.819 - void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
1.820 - e_node=&_e_node;
1.821 - }
1.822 - public:
1.823 - class Edge : public EdgeSetGraph::Edge {
1.824 - typedef typename EdgeSetGraph::Edge Parent;
1.825 - public:
1.826 - Edge() { }
1.827 - Edge(const Parent& e) : Parent(e) { }
1.828 - Edge(Invalid i) : Parent(i) { }
1.829 - };
1.830 -
1.831 - using Parent::first;
1.832 - void first(Edge &e) const {
1.833 - edge_set_graph->first(e);
1.834 - }
1.835 - void firstOut(Edge& e, const Node& n) const {
1.836 -// cout << e_node << endl;
1.837 -// cout << n_node << endl;
1.838 - edge_set_graph->firstOut(e, (*e_node)[n]);
1.839 - }
1.840 - void firstIn(Edge& e, const Node& n) const {
1.841 - edge_set_graph->firstIn(e, (*e_node)[n]);
1.842 - }
1.843 -
1.844 - using Parent::next;
1.845 - void next(Edge &e) const {
1.846 - edge_set_graph->next(e);
1.847 - }
1.848 - void nextOut(Edge& e) const {
1.849 - edge_set_graph->nextOut(e);
1.850 - }
1.851 - void nextIn(Edge& e) const {
1.852 - edge_set_graph->nextIn(e);
1.853 - }
1.854 -
1.855 - Node source(const Edge& e) const {
1.856 - return (*n_node)[edge_set_graph->source(e)];
1.857 - }
1.858 - Node target(const Edge& e) const {
1.859 - return (*n_node)[edge_set_graph->target(e)];
1.860 - }
1.861 -
1.862 - int edgeNum() const { return edge_set_graph->edgeNum(); }
1.863 -
1.864 -// NNode addOldNode() {
1.865 -// return Parent::addNode();
1.866 -// }
1.867 -
1.868 -// ENode addNewNode() {
1.869 -// return edge_set_graph->addNode();
1.870 -// }
1.871 -
1.872 - Edge addEdge(const Node& u, const Node& v) {
1.873 - return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
1.874 - }
1.875 -
1.876 - using Parent::erase;
1.877 - void erase(const Edge& i) const { edge_set_graph->erase(i); }
1.878 -
1.879 - void clear() const { Parent::clear(); edge_set_graph->clear(); }
1.880 -
1.881 - bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
1.882 - bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
1.883 -
1.884 - int id(const Node& e) const { return Parent::id(e); }
1.885 - int id(const Edge& e) const { return edge_set_graph->id(e); }
1.886 -
1.887 - Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
1.888 -
1.889 - template <typename _Value>
1.890 - class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
1.891 - public:
1.892 - typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
1.893 - typedef _Value Value;
1.894 - typedef Edge Key;
1.895 - EdgeMap(const NewEdgeSetGraphWrapperBase& gw) :
1.896 - Parent(*(gw.edge_set_graph)) { }
1.897 - EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) :
1.898 - Parent(*(gw.edge_set_graph), _value) { }
1.899 - };
1.900 -
1.901 - };
1.902 -
1.903 -
1.904 - /*! A graph wrapper class for the following functionality.
1.905 - If a bijection is given between the node-sets of two graphs,
1.906 - then the second one can be considered as a new edge-set
1.907 - over th first node-set.
1.908 - */
1.909 - template <typename _Graph, typename _EdgeSetGraph>
1.910 - class NewEdgeSetGraphWrapper :
1.911 - public IterableGraphExtender<
1.912 - NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
1.913 - public:
1.914 - typedef _Graph Graph;
1.915 - typedef _EdgeSetGraph EdgeSetGraph;
1.916 - typedef IterableGraphExtender<
1.917 - NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
1.918 - protected:
1.919 - NewEdgeSetGraphWrapper() { }
1.920 - public:
1.921 - NewEdgeSetGraphWrapper(_Graph& _graph,
1.922 - _EdgeSetGraph& _edge_set_graph,
1.923 - typename _Graph::
1.924 - NodeMap<typename _EdgeSetGraph::Node>& _e_node,
1.925 - typename _EdgeSetGraph::
1.926 - NodeMap<typename _Graph::Node>& _n_node) {
1.927 - setGraph(_graph);
1.928 - setEdgeSetGraph(_edge_set_graph);
1.929 - setNodeMap(_n_node);
1.930 - setENodeMap(_e_node);
1.931 - }
1.932 - };
1.933 -
1.934 - /*! A graph wrapper class for the following functionality.
1.935 - The same as NewEdgeSetGrapWrapper, but the bijection and the graph of
1.936 - new edges is andled inthe class.
1.937 - */
1.938 - template <typename _Graph, typename _EdgeSetGraph>
1.939 - class NewEdgeSetGraphWrapper2 :
1.940 - public IterableGraphExtender<
1.941 - NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
1.942 - public:
1.943 - typedef _Graph Graph;
1.944 - typedef _EdgeSetGraph EdgeSetGraph;
1.945 - typedef IterableGraphExtender<
1.946 - NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
1.947 - protected:
1.948 - _EdgeSetGraph _edge_set_graph;
1.949 - typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node;
1.950 - typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node;
1.951 - NewEdgeSetGraphWrapper2() { }
1.952 - public:
1.953 - typedef typename Graph::Node Node;
1.954 - // typedef typename Parent::Edge Edge;
1.955 -
1.956 - NewEdgeSetGraphWrapper2(_Graph& _graph) :
1.957 - _edge_set_graph(),
1.958 - _e_node(_graph), _n_node(_edge_set_graph) {
1.959 - setGraph(_graph);
1.960 - setEdgeSetGraph(_edge_set_graph);
1.961 - setNodeMap(_n_node); setENodeMap(_e_node);
1.962 - Node n;
1.963 - for (this->first(n); n!=INVALID; this->next(n)) {
1.964 - typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
1.965 - _e_node.set(n, e);
1.966 - _n_node.set(e, n);
1.967 - }
1.968 - }
1.969 -
1.970 -// Node addNode() {
1.971 -// Node n=(*this).Parent::addNode();
1.972 -// typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
1.973 -// _e_node.set(n, e);
1.974 -// _n_node.set(e, n);
1.975 -// return n;
1.976 -// }
1.977 -
1.978 - };
1.979 -
1.980 - /*! A graph wrapper base class
1.981 - for merging graphs of type _Graph1 and _Graph2
1.982 - which are given on the same node-set
1.983 - (specially on the node-set of Graph1)
1.984 - into one graph.
1.985 - In an other point of view, _Graph1 is extended with
1.986 - the edge-set of _Graph2.
1.987 - \warning we need specialize dimplementations
1.988 - \todo we need specialize dimplementations
1.989 - \bug we need specialize dimplementations
1.990 - */
1.991 - template <typename _Graph1, typename _Graph2, typename Enable=void>
1.992 - class AugmentingGraphWrapperBase :
1.993 - public P1<_Graph1> {
1.994 - public:
1.995 - void printAugment() const { std::cout << "generic" << std::endl; }
1.996 - typedef _Graph1 Graph1;
1.997 - typedef _Graph2 Graph2;
1.998 - typedef P1<_Graph1> Parent1;
1.999 - typedef P2<_Graph2> Parent2;
1.1000 - typedef typename Parent1::Edge Graph1Edge;
1.1001 - typedef typename Parent2::Edge Graph2Edge;
1.1002 - protected:
1.1003 - AugmentingGraphWrapperBase() { }
1.1004 - _Graph2* graph2;
1.1005 - void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
1.1006 - public:
1.1007 -
1.1008 - template <typename _Value> class EdgeMap;
1.1009 -
1.1010 - typedef typename Parent1::Node Node;
1.1011 -
1.1012 - class Edge : public Graph1Edge, public Graph2Edge {
1.1013 - friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
1.1014 - template <typename _Value> friend class EdgeMap;
1.1015 - protected:
1.1016 - bool backward; //true, iff backward
1.1017 - public:
1.1018 - Edge() { }
1.1019 - /// \todo =false is needed, or causes problems?
1.1020 - /// If \c _backward is false, then we get an edge corresponding to the
1.1021 - /// original one, otherwise its oppositely directed pair is obtained.
1.1022 - Edge(const Graph1Edge& n1,
1.1023 - const Graph2Edge& n2, bool _backward) :
1.1024 - Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
1.1025 - Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
1.1026 - bool operator==(const Edge& v) const {
1.1027 - if (backward)
1.1028 - return (v.backward &&
1.1029 - static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
1.1030 - else
1.1031 - return (!v.backward &&
1.1032 - static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
1.1033 - }
1.1034 - bool operator!=(const Edge& v) const {
1.1035 - return !(*this==v);
1.1036 - }
1.1037 - };
1.1038 -
1.1039 - using Parent1::first;
1.1040 - void first(Edge& i) const {
1.1041 - Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
1.1042 - i.backward=false;
1.1043 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.1044 - graph2->first(*static_cast<Graph2Edge*>(&i));
1.1045 - i.backward=true;
1.1046 - }
1.1047 - }
1.1048 - void firstIn(Edge& i, const Node& n) const {
1.1049 - Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
1.1050 - i.backward=false;
1.1051 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.1052 - graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
1.1053 - i.backward=true;
1.1054 - }
1.1055 - }
1.1056 - void firstOut(Edge& i, const Node& n) const {
1.1057 - Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
1.1058 - i.backward=false;
1.1059 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.1060 - graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
1.1061 - i.backward=true;
1.1062 - }
1.1063 - }
1.1064 -
1.1065 - using Parent1::next;
1.1066 - void next(Edge& i) const {
1.1067 - if (!(i.backward)) {
1.1068 - Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
1.1069 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.1070 - graph2->first(*static_cast<Graph2Edge*>(&i));
1.1071 - i.backward=true;
1.1072 - }
1.1073 - } else {
1.1074 - graph2->next(*static_cast<Graph2Edge*>(&i));
1.1075 - }
1.1076 - }
1.1077 - void nextIn(Edge& i) const {
1.1078 - if (!(i.backward)) {
1.1079 - Node n=target(i);
1.1080 - Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
1.1081 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.1082 - graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
1.1083 - i.backward=true;
1.1084 - }
1.1085 - } else {
1.1086 - graph2->nextIn(*static_cast<Graph2Edge*>(&i));
1.1087 - }
1.1088 - }
1.1089 - void nextOut(Edge& i) const {
1.1090 - if (!(i.backward)) {
1.1091 - Node n=source(i);
1.1092 - Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
1.1093 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1.1094 - graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
1.1095 - i.backward=true;
1.1096 - }
1.1097 - } else {
1.1098 - graph2->nextOut(*static_cast<Graph2Edge*>(&i));
1.1099 - }
1.1100 - }
1.1101 -
1.1102 - Node source(const Edge& i) const {
1.1103 - if (!(i.backward)) {
1.1104 - return Parent1::graph->source(i);
1.1105 - } else {
1.1106 - return graph2->source(i);
1.1107 - }
1.1108 - }
1.1109 -
1.1110 - Node target(const Edge& i) const {
1.1111 - if (!(i.backward)) {
1.1112 - return Parent1::graph->target(i);
1.1113 - } else {
1.1114 - return graph2->target(i);
1.1115 - }
1.1116 - }
1.1117 -
1.1118 - int id(const Node& n) const {
1.1119 - return Parent1::id(n);
1.1120 - };
1.1121 - int id(const Edge& n) const {
1.1122 - if (!n.backward)
1.1123 - return this->Parent1::graph->id(n);
1.1124 - else
1.1125 - return this->graph2->id(n);
1.1126 - }
1.1127 -
1.1128 - template <typename _Value>
1.1129 - class EdgeMap {
1.1130 - protected:
1.1131 - typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
1.1132 - typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
1.1133 - ParentMap1 forward_map;
1.1134 - ParentMap2 backward_map;
1.1135 - public:
1.1136 - typedef _Value Value;
1.1137 - typedef Edge Key;
1.1138 - EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) :
1.1139 - forward_map(*(gw.Parent1::graph)),
1.1140 - backward_map(*(gw.graph2)) { }
1.1141 - EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw,
1.1142 - const _Value& value) :
1.1143 - forward_map(*(gw.Parent1::graph), value),
1.1144 - backward_map(*(gw.graph2), value) { }
1.1145 - _Value operator[](const Edge& n) const {
1.1146 - if (!n.backward)
1.1147 - return forward_map[n];
1.1148 - else
1.1149 - return backward_map[n];
1.1150 - }
1.1151 - void set(const Edge& n, const _Value& value) {
1.1152 - if (!n.backward)
1.1153 - forward_map.set(n, value);
1.1154 - else
1.1155 - backward_map.set(n, value);
1.1156 - }
1.1157 -// using ParentMap1::operator[];
1.1158 -// using ParentMap2::operator[];
1.1159 - };
1.1160 -
1.1161 - };
1.1162 -
1.1163 -
1.1164 - /*! A graph wrapper class
1.1165 - for merging two graphs (of type _Graph1 and _Graph2)
1.1166 - with the same node-set
1.1167 - (specially on the node-set of Graph1)
1.1168 - into one graph.
1.1169 - In an other point of view, _Graph1 is extended with
1.1170 - the edge-set of _Graph2.
1.1171 - */
1.1172 - template <typename _Graph1, typename _Graph2>
1.1173 - class AugmentingGraphWrapper : public
1.1174 - IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
1.1175 - public:
1.1176 - typedef
1.1177 - IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
1.1178 - Parent;
1.1179 - typedef _Graph1 Graph1;
1.1180 - typedef _Graph2 Graph2;
1.1181 - protected:
1.1182 - AugmentingGraphWrapper() { }
1.1183 - public:
1.1184 - AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
1.1185 - setGraph(_graph1);
1.1186 - setGraph2(_graph2);
1.1187 - }
1.1188 - };
1.1189 -
1.1190 -} //namespace lemon
1.1191 -
1.1192 -#endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H