marci@915: /* -*- C++ -*-
alpar@921: * src/lemon/merge_node_graph_wrapper.h - Part of LEMON, a generic C++ optimization library
marci@915: *
alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
marci@915: * (Egervary Combinatorial Optimization Research Group, EGRES).
marci@915: *
marci@915: * Permission to use, modify and distribute this software is granted
marci@915: * provided that this copyright notice appears in all copies. For
marci@915: * precise terms see the accompanying LICENSE file.
marci@915: *
marci@915: * This software is provided "AS IS" with no warranty of any kind,
marci@915: * express or implied, and with no claim as to its suitability for any
marci@915: * purpose.
marci@915: *
marci@915: */
marci@915:
alpar@921: #ifndef LEMON_MERGE_NODE_GRAPH_WRAPPER_H
alpar@921: #define LEMON_MERGE_NODE_GRAPH_WRAPPER_H
marci@917:
alpar@921: #include <lemon/invalid.h>
alpar@921: #include <lemon/maps.h>
alpar@921: #include <lemon/map_defines.h>
alpar@921: #include <lemon/graph_wrapper.h>
marci@915: #include <iostream>
marci@1013:
marci@1008: using std::cout;
marci@1008: using std::endl;
marci@915:
marci@1007: #include <boost/type_traits.hpp>
marci@1007: #include <boost/utility/enable_if.hpp>
marci@1007:
alpar@921: namespace lemon {
marci@915:
marci@1007: template <class _Graph1>
marci@1007: class P1 : public GraphWrapperBase<_Graph1> {
marci@1007: };
marci@1007:
marci@1007: template <class _Graph2>
marci@1007: class P2 : public GraphWrapperBase<_Graph2> {
marci@1007: };
marci@1007:
marci@1013:
marci@1002: template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1025: class MergeNodeGraphWrapperBaseBase :
marci@1007: public P1<_Graph1>, public P2<_Graph2> {
marci@915: public:
marci@1013: static void printNode() { std::cout << "node: generic" << std::endl; }
marci@1002: typedef _Graph1 Graph1;
marci@1002: typedef _Graph2 Graph2;
marci@1007: typedef P1<_Graph1> Parent1;
marci@1007: typedef P2<_Graph2> Parent2;
marci@1002: typedef typename Parent1::Node Graph1Node;
marci@1002: typedef typename Parent2::Node Graph2Node;
marci@1002: protected:
marci@1025: MergeNodeGraphWrapperBaseBase() { }
marci@1002: public:
marci@915:
marci@915: class Node : public Graph1Node, public Graph2Node {
marci@1025: friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@915: protected:
marci@915: bool backward; //true, iff backward
marci@915: public:
marci@915: Node() { }
marci@915: /// \todo =false is needed, or causes problems?
marci@915: /// If \c _backward is false, then we get an edge corresponding to the
marci@915: /// original one, otherwise its oppositely directed pair is obtained.
marci@915: Node(const Graph1Node& n1,
marci@915: const Graph2Node& n2, bool _backward) :
marci@915: Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
marci@915: Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
marci@915: bool operator==(const Node& v) const {
marci@1013: if (backward)
marci@1013: return (v.backward &&
marci@1013: static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
marci@1013: else
marci@1013: return (!v.backward &&
marci@1013: static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
marci@915: }
marci@915: bool operator!=(const Node& v) const {
marci@1013: return !(*this==v);
marci@915: }
marci@915: };
marci@915:
marci@1025: static bool forward(const Node& n) { return !n.backward; }
marci@1025: static bool backward(const Node& n) { return n.backward; }
marci@1025: static void setForward(Node& n) { n.backward=false; }
marci@1025: static void setBackward(Node& n) { n.backward=true; }
marci@1002: };
marci@1002:
marci@1013:
marci@1007: template <typename _Graph1, typename _Graph2>
marci@1025: class MergeNodeGraphWrapperBaseBase<
marci@1007: _Graph1, _Graph2, typename boost::enable_if<
marci@1007: boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
marci@1007: public P1<_Graph1>, public P2<_Graph2> {
marci@1013: public:
marci@1013: static void printNode() { std::cout << "node: same" << std::endl; }
marci@1007: typedef _Graph1 Graph1;
marci@1007: typedef _Graph2 Graph2;
marci@1007: typedef P1<_Graph1> Parent1;
marci@1007: typedef P2<_Graph2> Parent2;
marci@1007: typedef typename Parent1::Node Graph1Node;
marci@1007: typedef typename Parent2::Node Graph2Node;
marci@1007: protected:
marci@1025: MergeNodeGraphWrapperBaseBase() { }
marci@1007: public:
marci@1013:
marci@1013: class Node : public Graph1Node {
marci@1025: friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1013: protected:
marci@1013: bool backward; //true, iff backward
marci@1013: public:
marci@1013: Node() { }
marci@1013: /// \todo =false is needed, or causes problems?
marci@1013: /// If \c _backward is false, then we get an edge corresponding to the
marci@1013: /// original one, otherwise its oppositely directed pair is obtained.
marci@1013: Node(const Graph1Node& n1,
marci@1013: const Graph2Node& n2, bool _backward) :
marci@1025: Graph1Node(!_backward ? n1 : n2), backward(_backward) { }
marci@1013: Node(Invalid i) : Graph1Node(i), backward(true) { }
marci@1013: bool operator==(const Node& v) const {
marci@1013: return (backward==v.backward &&
marci@1013: static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
marci@1013: }
marci@1013: bool operator!=(const Node& v) const {
marci@1013: return !(*this==v);
marci@1013: }
marci@1013: };
marci@1013:
marci@1025: static bool forward(const Node& n) { return !n.backward; }
marci@1025: static bool backward(const Node& n) { return n.backward; }
marci@1025: static void setForward(Node& n) { n.backward=false; }
marci@1025: static void setBackward(Node& n) { n.backward=true; }
marci@1007: };
marci@1007:
marci@1013:
marci@1007: template <typename _Graph1, typename _Graph2>
marci@1025: class MergeNodeGraphWrapperBaseBase<
marci@1007: _Graph1, _Graph2, typename boost::enable_if<
marci@1007: boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
marci@1007: public P1<_Graph1>, public P2<_Graph2> {
marci@1007: public :
marci@1013: static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }
marci@1007: typedef _Graph1 Graph1;
marci@1007: typedef _Graph2 Graph2;
marci@1007: typedef P1<_Graph1> Parent1;
marci@1007: typedef P2<_Graph2> Parent2;
marci@1007: typedef typename Parent1::Node Graph1Node;
marci@1007: typedef typename Parent2::Node Graph2Node;
marci@1007: protected:
marci@1025: MergeNodeGraphWrapperBaseBase() { }
marci@1007: public:
marci@1016:
marci@1016: class Node : public Graph2Node {
marci@1025: friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1016: protected:
marci@1016: bool backward; //true, iff backward
marci@1016: public:
marci@1016: Node() { }
marci@1016: /// \todo =false is needed, or causes problems?
marci@1016: /// If \c _backward is false, then we get an edge corresponding to the
marci@1016: /// original one, otherwise its oppositely directed pair is obtained.
marci@1016: Node(const Graph1Node& n1,
marci@1016: const Graph2Node& n2, bool _backward) :
marci@1016: Graph2Node(n2), backward(_backward) {
marci@1016: if (!backward) *this=n1;
marci@1016: }
marci@1016: Node(Invalid i) : Graph2Node(i), backward(true) { }
marci@1016: bool operator==(const Node& v) const {
marci@1016: if (backward)
marci@1016: return (v.backward &&
marci@1016: static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
marci@1016: else
marci@1016: return (!v.backward &&
marci@1016: static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
marci@1016: }
marci@1016: bool operator!=(const Node& v) const {
marci@1016: return !(*this==v);
marci@1016: }
marci@1016: };
marci@1016:
marci@1025: static bool forward(const Node& n) { return !n.backward; }
marci@1025: static bool backward(const Node& n) { return n.backward; }
marci@1025: static void setForward(Node& n) { n.backward=false; }
marci@1025: static void setBackward(Node& n) { n.backward=true; }
marci@1025: };
marci@1025:
marci@1016:
marci@1007: template <typename _Graph1, typename _Graph2>
marci@1025: class MergeNodeGraphWrapperBaseBase<
marci@1007: _Graph1, _Graph2, typename boost::enable_if<
marci@1007: boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
marci@1007: public P1<_Graph1>, public P2<_Graph2> {
marci@1007: public :
marci@1013: static void printNode() { std::cout << "node: 1st is derived" << std::endl; }
marci@1007: typedef _Graph1 Graph1;
marci@1007: typedef _Graph2 Graph2;
marci@1007: typedef P1<_Graph1> Parent1;
marci@1007: typedef P2<_Graph2> Parent2;
marci@1007: typedef typename Parent1::Node Graph1Node;
marci@1007: typedef typename Parent2::Node Graph2Node;
marci@1007: protected:
marci@1025: MergeNodeGraphWrapperBaseBase() { }
marci@1007: public:
marci@1016:
marci@1016: class Node : public Graph1Node {
marci@1025: friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1016: protected:
marci@1016: bool backward; //true, iff backward
marci@1016: public:
marci@1016: Node() { }
marci@1016: /// \todo =false is needed, or causes problems?
marci@1016: /// If \c _backward is false, then we get an edge corresponding to the
marci@1016: /// original one, otherwise its oppositely directed pair is obtained.
marci@1016: Node(const Graph1Node& n1,
marci@1016: const Graph2Node& n2, bool _backward) :
marci@1016: Graph1Node(n1), backward(_backward) {
marci@1016: if (backward) *this=n2;
marci@1016: }
marci@1016: Node(Invalid i) : Graph1Node(i), backward(true) { }
marci@1016: bool operator==(const Node& v) const {
marci@1016: if (backward)
marci@1016: return (v.backward &&
marci@1016: static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
marci@1016: else
marci@1016: return (!v.backward &&
marci@1016: static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
marci@1016: }
marci@1016: bool operator!=(const Node& v) const {
marci@1016: return !(*this==v);
marci@1016: }
marci@1016: };
marci@1016:
marci@1025: static bool forward(const Node& n) { return !n.backward; }
marci@1025: static bool backward(const Node& n) { return n.backward; }
marci@1025: static void setForward(Node& n) { n.backward=false; }
marci@1025: static void setBackward(Node& n) { n.backward=true; }
marci@1025: };
marci@1025:
marci@1025:
marci@1025: template <typename _Graph1, typename _Graph2>
marci@1025: class MergeNodeGraphWrapperBase :
marci@1025: public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> {
marci@1025: public:
marci@1025: typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
marci@1025: typedef _Graph1 Graph1;
marci@1025: typedef _Graph2 Graph2;
marci@1025: typedef P1<_Graph1> Parent1;
marci@1025: typedef P2<_Graph2> Parent2;
marci@1025: typedef typename Parent1::Node Graph1Node;
marci@1025: typedef typename Parent2::Node Graph2Node;
marci@1025:
marci@1025: typedef typename Parent::Node Node;
marci@1007: class Edge { };
marci@1016:
marci@1016: void first(Node& i) const {
marci@1016: Parent1::graph->first(*static_cast<Graph1Node*>(&i));
marci@1025: this->setForward(i);
marci@1016: if (*static_cast<Graph1Node*>(&i)==INVALID) {
marci@1016: Parent2::graph->first(*static_cast<Graph2Node*>(&i));
marci@1025: this->setBackward(i);
marci@1016: }
marci@1016: }
marci@1016: void next(Node& i) const {
marci@1025: if (this->forward(i)) {
marci@1016: Parent1::graph->next(*static_cast<Graph1Node*>(&i));
marci@1016: if (*static_cast<Graph1Node*>(&i)==INVALID) {
marci@1016: Parent2::graph->first(*static_cast<Graph2Node*>(&i));
marci@1025: this->setBackward(i);
marci@1016: }
marci@1016: } else {
marci@1016: Parent2::graph->next(*static_cast<Graph2Node*>(&i));
marci@1016: }
marci@1016: }
marci@1016:
marci@1016: int id(const Node& n) const {
marci@1025: if (this->forward(n))
marci@1016: return this->Parent1::graph->id(n);
marci@1016: else
marci@1016: return this->Parent2::graph->id(n);
marci@1016: }
marci@1016:
marci@1016: template <typename _Value>
marci@1016: class NodeMap {
marci@1016: protected:
marci@1016: typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
marci@1016: typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
marci@1016: ParentMap1 forward_map;
marci@1016: ParentMap2 backward_map;
marci@1016: public:
marci@1016: typedef _Value Value;
marci@1016: typedef Node Key;
marci@1016: NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1016: forward_map(*(gw.Parent1::graph)),
marci@1016: backward_map(*(gw.Parent2::graph)) { }
marci@1016: NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1016: const _Value& value) :
marci@1016: forward_map(*(gw.Parent1::graph), value),
marci@1016: backward_map(*(gw.Parent2::graph), value) { }
marci@1016: _Value operator[](const Node& n) const {
marci@1025: if (Parent::forward(n))
marci@1016: return forward_map[n];
marci@1016: else
marci@1016: return backward_map[n];
marci@1016: }
marci@1016: void set(const Node& n, const _Value& value) {
marci@1025: if (Parent::forward(n))
marci@1016: forward_map.set(n, value);
marci@1016: else
marci@1016: backward_map.set(n, value);
marci@1016: }
marci@1016: // using ParentMap1::operator[];
marci@1016: // using ParentMap2::operator[];
marci@1016: };
marci@1016:
marci@1007: };
marci@1007:
marci@1002:
marci@1013: /*! A graph wrapper class
marci@1025: for merging the node-set of two node-disjoint graphs
marci@1025: into the node-set of one graph.
marci@1025: Different implementations are according to the relation of
marci@1025: _Graph1::Node and _Graph2::Node.
marci@1025: If _Graph1::Node and _Graph2::Node are unrelated, then
marci@1025: MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
marci@1025: is derived from both.
marci@1025: If _Graph1::Node and _Graph2::Node are the same type, then
marci@1025: MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
marci@1025: is derived from _Graph1::Node.
marci@1025: If one of _Graph1::Node and _Graph2::Node
marci@1025: is derived from the other one, then
marci@1025: MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
marci@1025: is derived from the derived type.
marci@1025: It does not satisfy
marci@1013: StaticGraph concept as it has no edge-set which
marci@1013: works together with the node-set.
marci@1025: */
marci@1009: template <typename _Graph1, typename _Graph2>
marci@1002: class MergeNodeGraphWrapper : public
marci@1009: IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
marci@1002: public:
marci@1002: typedef _Graph1 Graph1;
marci@1002: typedef _Graph2 Graph2;
marci@1002: typedef IterableGraphExtender<
marci@1009: MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
marci@1002: protected:
marci@1002: MergeNodeGraphWrapper() { }
marci@1002: public:
marci@1002: MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
marci@1002: Parent::Parent1::setGraph(_graph1);
marci@1002: Parent::Parent2::setGraph(_graph2);
marci@1002: }
marci@915: };
marci@915:
marci@1009:
marci@1013: /*! A grah wrapper base class
marci@1013: for merging the node-sets and edge-sets of
marci@1009: two node-disjoint graphs
marci@1009: into one graph.
marci@1013: Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
marci@1009: */
marci@1009: template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1026: class MergeEdgeGraphWrapperBaseBase :
marci@1009: public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1009: public:
marci@1013: static void printEdge() { std::cout << "edge: generic" << std::endl; }
marci@1009: typedef _Graph1 Graph1;
marci@1009: typedef _Graph2 Graph2;
marci@1009: typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1009: typedef typename Parent::Parent1 Parent1;
marci@1009: typedef typename Parent::Parent2 Parent2;
marci@1009: // typedef P1<_Graph1> Parent1;
marci@1009: // typedef P2<_Graph2> Parent2;
marci@1009: typedef typename Parent1::Edge Graph1Edge;
marci@1009: typedef typename Parent2::Edge Graph2Edge;
marci@1009: protected:
marci@1026: MergeEdgeGraphWrapperBaseBase() { }
marci@1009: public:
marci@1009:
marci@1009: class Edge : public Graph1Edge, public Graph2Edge {
marci@1026: friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1009: protected:
marci@1009: bool backward; //true, iff backward
marci@1009: public:
marci@1009: Edge() { }
marci@1009: /// \todo =false is needed, or causes problems?
marci@1009: /// If \c _backward is false, then we get an edge corresponding to the
marci@1009: /// original one, otherwise its oppositely directed pair is obtained.
marci@1009: Edge(const Graph1Edge& n1,
marci@1009: const Graph2Edge& n2, bool _backward) :
marci@1009: Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
marci@1009: Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
marci@1009: bool operator==(const Edge& v) const {
marci@1013: if (backward)
marci@1013: return (v.backward &&
marci@1013: static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
marci@1013: else
marci@1013: return (!v.backward &&
marci@1013: static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1009: }
marci@1009: bool operator!=(const Edge& v) const {
marci@1013: return !(*this==v);
marci@1009: }
marci@1009: };
marci@1009:
marci@1025: using Parent::forward;
marci@1025: using Parent::backward;
marci@1026: using Parent::setForward;
marci@1026: using Parent::setBackward;
marci@1026: static bool forward(const Edge& e) { return !e.backward; }
marci@1026: static bool backward(const Edge& e) { return e.backward; }
marci@1026: static void setForward(Edge& e) { e.backward=false; }
marci@1026: static void setBackward(Edge& e) { e.backward=true; }
marci@1026: };
marci@1025:
marci@1009:
marci@1009:
marci@1013: /*! A graph wrapper base class
marci@1013: for merging the node-sets and edge-sets of
marci@1013: two node-disjoint graphs
marci@1013: into one graph.
marci@1013: Specialization for the case when _Graph1::Edge and _Graph2::Edge
marci@1013: are the same.
marci@1013: */
marci@1013: template <typename _Graph1, typename _Graph2>
marci@1026: class MergeEdgeGraphWrapperBaseBase<
marci@1013: _Graph1, _Graph2, typename boost::enable_if<
marci@1016: boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
marci@1013: public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1013: public:
marci@1013: static void printEdge() { std::cout << "edge: same" << std::endl; }
marci@1013: typedef _Graph1 Graph1;
marci@1013: typedef _Graph2 Graph2;
marci@1013: typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1013: typedef typename Parent::Parent1 Parent1;
marci@1013: typedef typename Parent::Parent2 Parent2;
marci@1013: // typedef P1<_Graph1> Parent1;
marci@1013: // typedef P2<_Graph2> Parent2;
marci@1013: typedef typename Parent1::Edge Graph1Edge;
marci@1013: typedef typename Parent2::Edge Graph2Edge;
marci@1013: protected:
marci@1026: MergeEdgeGraphWrapperBaseBase() { }
marci@1013: public:
marci@1013:
marci@1013: class Edge : public Graph1Edge {
marci@1026: friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1013: protected:
marci@1013: bool backward; //true, iff backward
marci@1013: public:
marci@1013: Edge() { }
marci@1013: /// \todo =false is needed, or causes problems?
marci@1013: /// If \c _backward is false, then we get an edge corresponding to the
marci@1013: /// original one, otherwise its oppositely directed pair is obtained.
marci@1013: Edge(const Graph1Edge& n1,
marci@1013: const Graph2Edge& n2, bool _backward) :
marci@1025: Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }
marci@1013: Edge(Invalid i) : Graph1Edge(i), backward(true) { }
marci@1013: bool operator==(const Edge& v) const {
marci@1013: return (backward==v.backward &&
marci@1013: static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1013: }
marci@1013: bool operator!=(const Edge& v) const {
marci@1013: return !(*this==v);
marci@1013: }
marci@1013: };
marci@1013:
marci@1025: using Parent::forward;
marci@1025: using Parent::backward;
marci@1026: using Parent::setForward;
marci@1026: using Parent::setBackward;
marci@1026: static bool forward(const Edge& e) { return !e.backward; }
marci@1026: static bool backward(const Edge& e) { return e.backward; }
marci@1026: static void setForward(Edge& e) { e.backward=false; }
marci@1026: static void setBackward(Edge& e) { e.backward=true; }
marci@1013: };
marci@1013:
marci@1013:
marci@1016: /*! A grah wrapper base class
marci@1016: for merging the node-sets and edge-sets of
marci@1016: two node-disjoint graphs
marci@1016: into one graph.
marci@1016: Specialized implementation for the case
marci@1016: when _Graph1::Edge is a base class and _Graph2::Edge
marci@1016: is derived from it.
marci@1016: */
marci@1016: template <typename _Graph1, typename _Graph2>
marci@1026: class MergeEdgeGraphWrapperBaseBase<
marci@1016: _Graph1, _Graph2, typename boost::enable_if<
marci@1016: boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
marci@1016: public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1016: public:
marci@1016: static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; }
marci@1016: typedef _Graph1 Graph1;
marci@1016: typedef _Graph2 Graph2;
marci@1016: typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1016: typedef typename Parent::Parent1 Parent1;
marci@1016: typedef typename Parent::Parent2 Parent2;
marci@1016: // typedef P1<_Graph1> Parent1;
marci@1016: // typedef P2<_Graph2> Parent2;
marci@1016: typedef typename Parent1::Edge Graph1Edge;
marci@1016: typedef typename Parent2::Edge Graph2Edge;
marci@1016: protected:
marci@1026: MergeEdgeGraphWrapperBaseBase() { }
marci@1016: public:
marci@1016:
marci@1016: class Edge : public Graph2Edge {
marci@1026: friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1016: protected:
marci@1016: bool backward; //true, iff backward
marci@1016: public:
marci@1016: Edge() { }
marci@1016: /// \todo =false is needed, or causes problems?
marci@1016: /// If \c _backward is false, then we get an edge corresponding to the
marci@1016: /// original one, otherwise its oppositely directed pair is obtained.
marci@1016: Edge(const Graph1Edge& n1,
marci@1016: const Graph2Edge& n2, bool _backward) :
marci@1016: Graph2Edge(n2), backward(_backward) {
marci@1016: if (!backward) *this=n1;
marci@1016: }
marci@1016: Edge(Invalid i) : Graph2Edge(i), backward(true) { }
marci@1016: bool operator==(const Edge& v) const {
marci@1016: if (backward)
marci@1016: return (v.backward &&
marci@1016: static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
marci@1016: else
marci@1016: return (!v.backward &&
marci@1016: static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1016: }
marci@1016: bool operator!=(const Edge& v) const {
marci@1016: return !(*this==v);
marci@1016: }
marci@1016: };
marci@1016:
marci@1025: using Parent::forward;
marci@1025: using Parent::backward;
marci@1026: using Parent::setForward;
marci@1026: using Parent::setBackward;
marci@1026: static bool forward(const Edge& e) { return !e.backward; }
marci@1026: static bool backward(const Edge& e) { return e.backward; }
marci@1026: static void setForward(Edge& e) { e.backward=false; }
marci@1026: static void setBackward(Edge& e) { e.backward=true; }
marci@1016: };
marci@1016:
marci@1016:
marci@1016: /*! A grah wrapper base class
marci@1016: for merging the node-sets and edge-sets of
marci@1016: two node-disjoint graphs
marci@1016: into one graph.
marci@1016: Specialized implementation for the case
marci@1016: when _Graph1::Edge is derived from _Graph2::Edge.
marci@1016: */
marci@1016: template <typename _Graph1, typename _Graph2>
marci@1026: class MergeEdgeGraphWrapperBaseBase<
marci@1016: _Graph1, _Graph2, typename boost::enable_if<
marci@1016: boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> :
marci@1016: public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1016: public:
marci@1016: static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; }
marci@1016: typedef _Graph1 Graph1;
marci@1016: typedef _Graph2 Graph2;
marci@1026: typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
marci@1016: typedef typename Parent::Parent1 Parent1;
marci@1016: typedef typename Parent::Parent2 Parent2;
marci@1016: // typedef P1<_Graph1> Parent1;
marci@1016: // typedef P2<_Graph2> Parent2;
marci@1016: typedef typename Parent1::Edge Graph1Edge;
marci@1016: typedef typename Parent2::Edge Graph2Edge;
marci@1016: protected:
marci@1026: MergeEdgeGraphWrapperBaseBase() { }
marci@1016: public:
marci@1016:
marci@1016: class Edge : public Graph1Edge {
marci@1026: friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1016: protected:
marci@1016: bool backward; //true, iff backward
marci@1016: public:
marci@1016: Edge() { }
marci@1016: /// \todo =false is needed, or causes problems?
marci@1016: /// If \c _backward is false, then we get an edge corresponding to the
marci@1016: /// original one, otherwise its oppositely directed pair is obtained.
marci@1016: Edge(const Graph1Edge& n1,
marci@1016: const Graph2Edge& n2, bool _backward) :
marci@1016: Graph1Edge(n1), backward(_backward) {
marci@1016: if (backward) *this=n2;
marci@1016: }
marci@1016: Edge(Invalid i) : Graph1Edge(i), backward(true) { }
marci@1016: bool operator==(const Edge& v) const {
marci@1016: if (backward)
marci@1016: return (v.backward &&
marci@1016: static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
marci@1016: else
marci@1016: return (!v.backward &&
marci@1016: static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1016: }
marci@1016: bool operator!=(const Edge& v) const {
marci@1016: return !(*this==v);
marci@1016: }
marci@1016: };
marci@1016:
marci@1025: using Parent::forward;
marci@1025: using Parent::backward;
marci@1026: using Parent::setForward;
marci@1026: using Parent::setBackward;
marci@1026: static bool forward(const Edge& e) { return !e.backward; }
marci@1026: static bool backward(const Edge& e) { return e.backward; }
marci@1026: static void setForward(Edge& e) { e.backward=false; }
marci@1026: static void setBackward(Edge& e) { e.backward=true; }
marci@1026: };
marci@1026:
marci@1026:
marci@1026: template <typename _Graph1, typename _Graph2>
marci@1026: class MergeEdgeGraphWrapperBase :
marci@1026: public MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> {
marci@1026: public:
marci@1026: typedef MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
marci@1026: typedef _Graph1 Graph1;
marci@1026: typedef _Graph2 Graph2;
marci@1026: typedef typename Parent::Parent1 Parent1;
marci@1026: typedef typename Parent::Parent2 Parent2;
marci@1026: typedef typename Parent1::Node Graph1Node;
marci@1026: typedef typename Parent2::Node Graph2Node;
marci@1026: typedef typename Parent1::Edge Graph1Edge;
marci@1026: typedef typename Parent2::Edge Graph2Edge;
marci@1026:
marci@1026: typedef typename Parent::Node Node;
marci@1026: typedef typename Parent::Edge Edge;
marci@1025:
marci@1016: using Parent::first;
marci@1016: void first(Edge& i) const {
marci@1016: Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
marci@1026: this->setForward(i);
marci@1016: if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1016: Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
marci@1026: this->setBackward(i);
marci@1016: }
marci@1016: }
marci@1016: void firstIn(Edge& i, const Node& n) const {
marci@1026: if (forward(n)) {
marci@1025: Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
marci@1025: if (*static_cast<Graph1Edge*>(&i)==INVALID)
marci@1025: i=INVALID;
marci@1025: else
marci@1026: this->setForward(i);
marci@1025: } else {
marci@1016: Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
marci@1026: this->setBackward(i);
marci@1016: }
marci@1016: }
marci@1016: void firstOut(Edge& i, const Node& n) const {
marci@1026: if (forward(n)) {
marci@1025: Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
marci@1025: if (*static_cast<Graph1Edge*>(&i)==INVALID)
marci@1025: i=INVALID;
marci@1026: else
marci@1026: this->setForward(i);
marci@1025: } else {
marci@1016: Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
marci@1026: this->setBackward(i);
marci@1016: }
marci@1016: }
marci@1016:
marci@1016: using Parent::next;
marci@1016: void next(Edge& i) const {
marci@1026: if (forward(i)) {
marci@1016: Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
marci@1016: if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1016: Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
marci@1026: this->setBackward(i);
marci@1016: }
marci@1016: } else {
marci@1016: Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
marci@1016: }
marci@1016: }
marci@1016: void nextIn(Edge& i) const {
marci@1026: if (forward(i)) {
marci@1016: Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
marci@1025: if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
marci@1016: } else {
marci@1016: Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
marci@1016: }
marci@1016: }
marci@1016: void nextOut(Edge& i) const {
marci@1026: if (Parent::forward(i)) {
marci@1016: Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
marci@1025: if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
marci@1016: } else {
marci@1016: Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
marci@1016: }
marci@1016: }
marci@1016:
marci@1016: Node source(const Edge& i) const {
marci@1026: if (forward(i)) {
marci@1016: return
marci@1016: Node(Parent1::graph->source(i), INVALID, false);
marci@1016: } else {
marci@1016: return
marci@1016: Node(INVALID, Parent2::graph->source(i), true);
marci@1016: }
marci@1016: }
marci@1016:
marci@1016: Node target(const Edge& i) const {
marci@1026: if (forward(i)) {
marci@1016: return
marci@1016: Node(Parent1::graph->target(i), INVALID, false);
marci@1016: } else {
marci@1016: return
marci@1016: Node(INVALID, Parent2::graph->target(i), true);
marci@1016: }
marci@1016: }
marci@1016:
marci@1016: using Parent::id;
marci@1016: int id(const Edge& n) const {
marci@1026: if (forward(n))
marci@1016: return this->Parent1::graph->id(n);
marci@1016: else
marci@1016: return this->Parent2::graph->id(n);
marci@1016: }
marci@1016:
marci@1016: template <typename _Value>
marci@1016: class EdgeMap {
marci@1016: protected:
marci@1016: typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
marci@1016: typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
marci@1016: ParentMap1 forward_map;
marci@1016: ParentMap2 backward_map;
marci@1016: public:
marci@1016: typedef _Value Value;
marci@1016: typedef Edge Key;
marci@1016: EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1016: forward_map(*(gw.Parent1::graph)),
marci@1016: backward_map(*(gw.Parent2::graph)) { }
marci@1016: EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1016: const _Value& value) :
marci@1016: forward_map(*(gw.Parent1::graph), value),
marci@1016: backward_map(*(gw.Parent2::graph), value) { }
marci@1016: _Value operator[](const Edge& n) const {
marci@1026: if (Parent::forward(n))
marci@1016: return forward_map[n];
marci@1016: else
marci@1016: return backward_map[n];
marci@1016: }
marci@1016: void set(const Edge& n, const _Value& value) {
marci@1026: if (Parent::forward(n))
marci@1016: forward_map.set(n, value);
marci@1016: else
marci@1016: backward_map.set(n, value);
marci@1016: }
marci@1016: // using ParentMap1::operator[];
marci@1016: // using ParentMap2::operator[];
marci@1016: };
marci@1016:
marci@1016: };
marci@1016:
marci@1016:
marci@1026:
marci@1013: /*! A graph wrapper class
marci@1026: for merging two node-disjoint graphs
marci@1026: into one graph.
marci@1026: Different implementations are according to the relation of
marci@1026: _Graph1::Edge and _Graph2::Edge.
marci@1026: If _Graph1::Edge and _Graph2::Edge are unrelated, then
marci@1026: MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
marci@1026: is derived from both.
marci@1026: If _Graph1::Edge and _Graph2::Edge are the same type, then
marci@1026: MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
marci@1026: is derived from _Graph1::Edge.
marci@1026: If one of _Graph1::Edge and _Graph2::Edge
marci@1026: is derived from the other one, then
marci@1026: MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
marci@1026: is derived from the derived type.
marci@1026: It does not satisfy
marci@1026: */
marci@1009: template <typename _Graph1, typename _Graph2>
marci@1009: class MergeEdgeGraphWrapper : public
marci@1009: IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
marci@1009: public:
marci@1009: typedef _Graph1 Graph1;
marci@1009: typedef _Graph2 Graph2;
marci@1009: typedef IterableGraphExtender<
marci@1009: MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
marci@1009: protected:
marci@1009: MergeEdgeGraphWrapper() { }
marci@1009: public:
marci@1009: MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
marci@1009: Parent::Parent1::setGraph(_graph1);
marci@1009: Parent::Parent2::setGraph(_graph2);
marci@1009: }
marci@1009: };
marci@1009:
marci@1008:
marci@1013: /*! A graph wrapper base class for the following functionality.
marci@1013: If a bijection is given between the node-sets of two graphs,
marci@1013: then the second one can be considered as a new edge-set
marci@1013: over th first node-set.
marci@1013: */
marci@1008: template <typename _Graph, typename _EdgeSetGraph>
marci@1008: class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
marci@1008: public:
marci@1008: typedef GraphWrapperBase<_Graph> Parent;
marci@1008: typedef _Graph Graph;
marci@1008: typedef _EdgeSetGraph EdgeSetGraph;
marci@1008: typedef typename _Graph::Node Node;
marci@1008: typedef typename _EdgeSetGraph::Node ENode;
marci@1008: protected:
marci@1008: EdgeSetGraph* edge_set_graph;
marci@1008: typename Graph::NodeMap<ENode>* e_node;
marci@1008: typename EdgeSetGraph::NodeMap<Node>* n_node;
marci@1008: void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) {
marci@1008: edge_set_graph=&_edge_set_graph;
marci@1008: }
marci@1008: /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
marci@1008: void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
marci@1008: n_node=&_n_node;
marci@1008: }
marci@1008: /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
marci@1008: void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
marci@1008: e_node=&_e_node;
marci@1008: }
marci@1008: public:
marci@1008: class Edge : public EdgeSetGraph::Edge {
marci@1008: typedef typename EdgeSetGraph::Edge Parent;
marci@1008: public:
marci@1008: Edge() { }
marci@1008: Edge(const Parent& e) : Parent(e) { }
marci@1008: Edge(Invalid i) : Parent(i) { }
marci@1008: };
marci@1008:
marci@1008: using Parent::first;
marci@1008: void first(Edge &e) const {
marci@1008: edge_set_graph->first(e);
marci@1008: }
marci@1008: void firstOut(Edge& e, const Node& n) const {
marci@1008: // cout << e_node << endl;
marci@1008: // cout << n_node << endl;
marci@1008: edge_set_graph->firstOut(e, (*e_node)[n]);
marci@1008: }
marci@1008: void firstIn(Edge& e, const Node& n) const {
marci@1008: edge_set_graph->firstIn(e, (*e_node)[n]);
marci@1008: }
marci@1008:
marci@1008: using Parent::next;
marci@1008: void next(Edge &e) const {
marci@1008: edge_set_graph->next(e);
marci@1008: }
marci@1008: void nextOut(Edge& e) const {
marci@1008: edge_set_graph->nextOut(e);
marci@1008: }
marci@1008: void nextIn(Edge& e) const {
marci@1008: edge_set_graph->nextIn(e);
marci@1008: }
marci@1008:
marci@1008: Node source(const Edge& e) const {
marci@1008: return (*n_node)[edge_set_graph->source(e)];
marci@1008: }
marci@1008: Node target(const Edge& e) const {
marci@1008: return (*n_node)[edge_set_graph->target(e)];
marci@1008: }
marci@1008:
marci@1008: int edgeNum() const { return edge_set_graph->edgeNum(); }
marci@1008:
marci@1025: // NNode addOldNode() {
marci@1025: // return Parent::addNode();
marci@1025: // }
marci@1025:
marci@1025: // ENode addNewNode() {
marci@1025: // return edge_set_graph->addNode();
marci@1025: // }
marci@1025:
marci@1008: Edge addEdge(const Node& u, const Node& v) {
marci@1008: return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
marci@1008: }
marci@1008:
marci@1008: using Parent::erase;
marci@1008: void erase(const Edge& i) const { edge_set_graph->erase(i); }
marci@1008:
marci@1008: void clear() const { Parent::clear(); edge_set_graph->clear(); }
marci@1008:
marci@1008: bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
marci@1008: bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
marci@1008:
marci@1013: int id(const Node& e) const { return Parent::id(e); }
marci@1008: int id(const Edge& e) const { return edge_set_graph->id(e); }
marci@1008:
marci@1008: Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
marci@1008:
marci@1008: template <typename _Value>
marci@1008: class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
marci@1008: public:
marci@1008: typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
marci@1008: typedef _Value Value;
marci@1008: typedef Edge Key;
marci@1008: EdgeMap(const NewEdgeSetGraphWrapperBase& gw) :
marci@1008: Parent(*(gw.edge_set_graph)) { }
marci@1008: EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) :
marci@1008: Parent(*(gw.edge_set_graph), _value) { }
marci@1008: };
marci@1008:
marci@1008: };
marci@1008:
marci@1013:
marci@1013: /*! A graph wrapper class for the following functionality.
marci@1013: If a bijection is given between the node-sets of two graphs,
marci@1013: then the second one can be considered as a new edge-set
marci@1013: over th first node-set.
marci@1013: */
marci@1008: template <typename _Graph, typename _EdgeSetGraph>
marci@1008: class NewEdgeSetGraphWrapper :
marci@1008: public IterableGraphExtender<
marci@1008: NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
marci@1008: public:
marci@1008: typedef _Graph Graph;
marci@1008: typedef _EdgeSetGraph EdgeSetGraph;
marci@1008: typedef IterableGraphExtender<
marci@1025: NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
marci@1008: protected:
marci@1008: NewEdgeSetGraphWrapper() { }
marci@1008: public:
marci@1008: NewEdgeSetGraphWrapper(_Graph& _graph,
marci@1008: _EdgeSetGraph& _edge_set_graph,
marci@1008: typename _Graph::
marci@1008: NodeMap<typename _EdgeSetGraph::Node>& _e_node,
marci@1008: typename _EdgeSetGraph::
marci@1008: NodeMap<typename _Graph::Node>& _n_node) {
marci@1008: setGraph(_graph);
marci@1008: setEdgeSetGraph(_edge_set_graph);
marci@1008: setNodeMap(_n_node);
marci@1008: setENodeMap(_e_node);
marci@1008: }
marci@1008: };
marci@1008:
marci@1025: /*! A graph wrapper class for the following functionality.
marci@1025: The same as NewEdgeSetGrapWrapper, but the bijection and the graph of
marci@1025: new edges is andled inthe class.
marci@1025: */
marci@1025: template <typename _Graph, typename _EdgeSetGraph>
marci@1025: class NewEdgeSetGraphWrapper2 :
marci@1025: public IterableGraphExtender<
marci@1025: NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
marci@1025: public:
marci@1025: typedef _Graph Graph;
marci@1025: typedef _EdgeSetGraph EdgeSetGraph;
marci@1025: typedef IterableGraphExtender<
marci@1025: NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
marci@1025: protected:
marci@1025: _EdgeSetGraph _edge_set_graph;
marci@1025: typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node;
marci@1025: typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node;
marci@1025: NewEdgeSetGraphWrapper2() { }
marci@1025: public:
marci@1025: typedef typename Graph::Node Node;
marci@1025: // typedef typename Parent::Edge Edge;
marci@1025:
marci@1025: NewEdgeSetGraphWrapper2(_Graph& _graph) :
marci@1025: _edge_set_graph(),
marci@1025: _e_node(_graph), _n_node(_edge_set_graph) {
marci@1025: setGraph(_graph);
marci@1025: setEdgeSetGraph(_edge_set_graph);
marci@1025: setNodeMap(_n_node); setENodeMap(_e_node);
marci@1025: Node n;
marci@1025: for (this->first(n); n!=INVALID; this->next(n)) {
marci@1025: typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
marci@1025: _e_node.set(n, e);
marci@1025: _n_node.set(e, n);
marci@1025: }
marci@1025: }
marci@1025:
marci@1025: // Node addNode() {
marci@1025: // Node n=(*this).Parent::addNode();
marci@1025: // typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
marci@1025: // _e_node.set(n, e);
marci@1025: // _n_node.set(e, n);
marci@1025: // return n;
marci@1025: // }
marci@1025:
marci@1025: };
marci@1013:
marci@1013: /*! A graph wrapper base class
marci@1013: for merging graphs of type _Graph1 and _Graph2
marci@1013: which are given on the same node-set
marci@1013: (specially on the node-set of Graph1)
marci@1013: into one graph.
marci@1013: In an other point of view, _Graph1 is extended with
marci@1013: the edge-set of _Graph2.
marci@1025: \warning we need specialize dimplementations
marci@1025: \todo we need specialize dimplementations
marci@1025: \bug we need specialize dimplementations
marci@1013: */
marci@1013: template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1013: class AugmentingGraphWrapperBase :
marci@1013: public P1<_Graph1> {
marci@1013: public:
marci@1013: void printAugment() const { std::cout << "generic" << std::endl; }
marci@1013: typedef _Graph1 Graph1;
marci@1013: typedef _Graph2 Graph2;
marci@1013: typedef P1<_Graph1> Parent1;
marci@1013: typedef P2<_Graph2> Parent2;
marci@1013: typedef typename Parent1::Edge Graph1Edge;
marci@1013: typedef typename Parent2::Edge Graph2Edge;
marci@1013: protected:
marci@1013: AugmentingGraphWrapperBase() { }
marci@1013: _Graph2* graph2;
marci@1013: void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
marci@1013: public:
marci@1013:
marci@1013: template <typename _Value> class EdgeMap;
marci@1013:
marci@1013: typedef typename Parent1::Node Node;
marci@1013:
marci@1013: class Edge : public Graph1Edge, public Graph2Edge {
marci@1013: friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
marci@1013: template <typename _Value> friend class EdgeMap;
marci@1013: protected:
marci@1013: bool backward; //true, iff backward
marci@1013: public:
marci@1013: Edge() { }
marci@1013: /// \todo =false is needed, or causes problems?
marci@1013: /// If \c _backward is false, then we get an edge corresponding to the
marci@1013: /// original one, otherwise its oppositely directed pair is obtained.
marci@1013: Edge(const Graph1Edge& n1,
marci@1013: const Graph2Edge& n2, bool _backward) :
marci@1013: Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
marci@1013: Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
marci@1013: bool operator==(const Edge& v) const {
marci@1013: if (backward)
marci@1013: return (v.backward &&
marci@1013: static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
marci@1013: else
marci@1013: return (!v.backward &&
marci@1013: static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1013: }
marci@1013: bool operator!=(const Edge& v) const {
marci@1013: return !(*this==v);
marci@1013: }
marci@1013: };
marci@1013:
marci@1013: using Parent1::first;
marci@1013: void first(Edge& i) const {
marci@1013: Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
marci@1013: i.backward=false;
marci@1013: if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1013: graph2->first(*static_cast<Graph2Edge*>(&i));
marci@1013: i.backward=true;
marci@1013: }
marci@1013: }
marci@1013: void firstIn(Edge& i, const Node& n) const {
marci@1013: Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
marci@1013: i.backward=false;
marci@1013: if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1013: graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
marci@1013: i.backward=true;
marci@1013: }
marci@1013: }
marci@1013: void firstOut(Edge& i, const Node& n) const {
marci@1013: Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
marci@1013: i.backward=false;
marci@1013: if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1013: graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
marci@1013: i.backward=true;
marci@1013: }
marci@1013: }
marci@1013:
marci@1013: using Parent1::next;
marci@1013: void next(Edge& i) const {
marci@1013: if (!(i.backward)) {
marci@1013: Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
marci@1013: if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1013: graph2->first(*static_cast<Graph2Edge*>(&i));
marci@1013: i.backward=true;
marci@1013: }
marci@1013: } else {
marci@1013: graph2->next(*static_cast<Graph2Edge*>(&i));
marci@1013: }
marci@1013: }
marci@1013: void nextIn(Edge& i) const {
marci@1013: if (!(i.backward)) {
marci@1025: Node n=target(i);
marci@1013: Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
marci@1013: if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1025: graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
marci@1013: i.backward=true;
marci@1013: }
marci@1013: } else {
marci@1013: graph2->nextIn(*static_cast<Graph2Edge*>(&i));
marci@1013: }
marci@1013: }
marci@1013: void nextOut(Edge& i) const {
marci@1013: if (!(i.backward)) {
marci@1025: Node n=source(i);
marci@1013: Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
marci@1013: if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1025: graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
marci@1013: i.backward=true;
marci@1013: }
marci@1013: } else {
marci@1013: graph2->nextOut(*static_cast<Graph2Edge*>(&i));
marci@1013: }
marci@1013: }
marci@1013:
marci@1013: Node source(const Edge& i) const {
marci@1013: if (!(i.backward)) {
marci@1013: return Parent1::graph->source(i);
marci@1013: } else {
marci@1013: return graph2->source(i);
marci@1013: }
marci@1013: }
marci@1013:
marci@1013: Node target(const Edge& i) const {
marci@1013: if (!(i.backward)) {
marci@1013: return Parent1::graph->target(i);
marci@1013: } else {
marci@1013: return graph2->target(i);
marci@1013: }
marci@1013: }
marci@1013:
marci@1013: int id(const Node& n) const {
marci@1013: return Parent1::id(n);
marci@1013: };
marci@1013: int id(const Edge& n) const {
marci@1013: if (!n.backward)
marci@1013: return this->Parent1::graph->id(n);
marci@1013: else
marci@1013: return this->graph2->id(n);
marci@1013: }
marci@1013:
marci@1013: template <typename _Value>
marci@1013: class EdgeMap {
marci@1013: protected:
marci@1013: typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
marci@1013: typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
marci@1013: ParentMap1 forward_map;
marci@1013: ParentMap2 backward_map;
marci@1013: public:
marci@1013: typedef _Value Value;
marci@1013: typedef Edge Key;
marci@1013: EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1013: forward_map(*(gw.Parent1::graph)),
marci@1013: backward_map(*(gw.graph2)) { }
marci@1013: EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1013: const _Value& value) :
marci@1013: forward_map(*(gw.Parent1::graph), value),
marci@1013: backward_map(*(gw.graph2), value) { }
marci@1013: _Value operator[](const Edge& n) const {
marci@1013: if (!n.backward)
marci@1013: return forward_map[n];
marci@1013: else
marci@1013: return backward_map[n];
marci@1013: }
marci@1013: void set(const Edge& n, const _Value& value) {
marci@1013: if (!n.backward)
marci@1013: forward_map.set(n, value);
marci@1013: else
marci@1013: backward_map.set(n, value);
marci@1013: }
marci@1013: // using ParentMap1::operator[];
marci@1013: // using ParentMap2::operator[];
marci@1013: };
marci@1013:
marci@1013: };
marci@1013:
marci@1013:
marci@1013: /*! A graph wrapper class
marci@1013: for merging two graphs (of type _Graph1 and _Graph2)
marci@1013: with the same node-set
marci@1013: (specially on the node-set of Graph1)
marci@1013: into one graph.
marci@1013: In an other point of view, _Graph1 is extended with
marci@1013: the edge-set of _Graph2.
marci@1013: */
marci@1013: template <typename _Graph1, typename _Graph2>
marci@1013: class AugmentingGraphWrapper : public
marci@1013: IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
marci@1013: public:
marci@1013: typedef
marci@1013: IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
marci@1013: Parent;
marci@1013: typedef _Graph1 Graph1;
marci@1013: typedef _Graph2 Graph2;
marci@1013: protected:
marci@1013: AugmentingGraphWrapper() { }
marci@1013: public:
marci@1013: AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
marci@1013: setGraph(_graph1);
marci@1013: setGraph2(_graph2);
marci@1013: }
marci@1013: };
marci@1013:
alpar@921: } //namespace lemon
marci@915:
alpar@921: #endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H