lemon-0.x: comparison src/work/marci/merge_node_graph

equal deleted inserted replaced

-:9744318aa587
+:86da8bcef4fc
 #include <lemon/invalid.h>
 #include <lemon/maps.h>
 #include <lemon/map_defines.h>
 #include <lemon/graph_wrapper.h>
 #include <iostream>
 using std::cout;
 using std::endl;
 #include <boost/type_traits.hpp>
 #include <boost/utility/enable_if.hpp>
 template <class _Graph2>
 class P2 : public GraphWrapperBase<_Graph2> {
 };
-/*! A base class for merging the node-set of two node-disjoint graphs
-into the node-set of one graph.
+/*! A graph wrapper base class
+for merging the node-set of two node-disjoint graphs
+into the node-set of one graph.
+Generic implementation for unrelated _Graph1::Node and _Graph2::Node.
 */
 template <typename _Graph1, typename _Graph2, typename Enable=void>
 class MergeNodeGraphWrapperBase :
 public P1<_Graph1>, public P2<_Graph2> {
 public:
-void printNode() const { std::cout << "generic" << std::endl; }
+static void printNode() { std::cout << "node: generic" << std::endl; }
 typedef _Graph1 Graph1;
 typedef _Graph2 Graph2;
 typedef P1<_Graph1> Parent1;
 typedef P2<_Graph2> Parent2;
 typedef typename Parent1::Node Graph1Node;
 public:
 template <typename _Value> class NodeMap;
 class Node : public Graph1Node, public Graph2Node {
 friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
-template <typename Value> friend class NodeMap;
+template <typename _Value> friend class NodeMap;
 protected:
 bool backward; //true, iff backward
 public:
 Node() { }
 /// \todo =false is needed, or causes problems?
 Node(const Graph1Node& n1,
 	   const Graph2Node& n2, bool _backward) :
 	Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
 Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
 bool operator==(const Node& v) const {
-	return (this->backward==v.backward &&
+	if (backward)
-		static_cast<Graph1Node>(*this)==
+	  return (v.backward &&
-		static_cast<Graph1Node>(v) &&
+		  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
-		static_cast<Graph2Node>(*this)==
+	else
-		static_cast<Graph2Node>(v));
+	  return (!v.backward &&
+		  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
 }
 bool operator!=(const Node& v) const {
-	return (this->backward!=v.backward ||
+	return !(*this==v);
-		static_cast<Graph1Node>(*this)!=
-		static_cast<Graph1Node>(v) ||
-		static_cast<Graph2Node>(*this)!=
-		static_cast<Graph2Node>(v));
 }
 };
 //typedef void Edge;
 class Edge { };
 else
 	return this->Parent2::graph->id(n);
 }
 template <typename _Value>
-class NodeMap : public Parent1::template NodeMap<_Value>,
+class NodeMap {
-		    public Parent2::template NodeMap<_Value> {
+protected:
-typedef typename Parent1::template NodeMap<_Value> ParentMap1;
+typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
-typedef typename Parent2::template NodeMap<_Value> ParentMap2;
+typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
+ParentMap1 forward_map;
+ParentMap2 backward_map;
 public:
 typedef _Value Value;
 typedef Node Key;
 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
-	ParentMap1(gw), ParentMap2(gw) { }
+	forward_map(*(gw.Parent1::graph)),
+	backward_map(*(gw.Parent2::graph)) { }
 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
 	      const _Value& value) :
-	ParentMap1(gw, value), ParentMap2(gw, value) { }
+	forward_map(*(gw.Parent1::graph), value),
+	backward_map(*(gw.Parent2::graph), value) { }
 _Value operator[](const Node& n) const {
 	if (!n.backward)
-	  return ParentMap1::operator[](n);
+	  return forward_map[n];
 	else
-	  return ParentMap2::operator[](n);
+	  return backward_map[n];
 }
 void set(const Node& n, const _Value& value) {
 	if (!n.backward)
-	  ParentMap1::set(n, value);
+	  forward_map.set(n, value);
 	else
-	  ParentMap2::set(n, value);
+	  backward_map.set(n, value);
 }
 //       using ParentMap1::operator[];
 //       using ParentMap2::operator[];
 };
 };
-//not yet working
+/*! A graph wrapper base class
+for merging the node-set of two node-disjoint graphs
+into the node-set of one graph.
+Specialization for the case when _Graph1::Node are the same _Graph2::Node.
+*/
 template <typename _Graph1, typename _Graph2>
 class MergeNodeGraphWrapperBase<
 _Graph1, _Graph2, typename boost::enable_if<
 boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
 public P1<_Graph1>, public P2<_Graph2> {
-public :
+public:
-void printNode() const { std::cout << "same" << std::endl; }
+static void printNode() { std::cout << "node: same" << std::endl; }
 typedef _Graph1 Graph1;
 typedef _Graph2 Graph2;
 typedef P1<_Graph1> Parent1;
 typedef P2<_Graph2> Parent2;
 typedef typename Parent1::Node Graph1Node;
 typedef typename Parent2::Node Graph2Node;
 protected:
 MergeNodeGraphWrapperBase() { }
 public:
-class Node { };
+template <typename _Value> class NodeMap;
+class Node : public Graph1Node {
+friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
+template <typename _Value> friend class NodeMap;
+protected:
+bool backward; //true, iff backward
+public:
+Node() { }
+/// \todo =false is needed, or causes problems?
+/// If \c _backward is false, then we get an edge corresponding to the
+/// original one, otherwise its oppositely directed pair is obtained.
+Node(const Graph1Node& n1,
+	   const Graph2Node& n2, bool _backward) :
+	Graph1Node(!backward ? n1 : n2), backward(_backward) { }
+Node(Invalid i) : Graph1Node(i), backward(true) { }
+bool operator==(const Node& v) const {
+	return (backward==v.backward &&
+		static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
+}
+bool operator!=(const Node& v) const {
+	return !(*this==v);
+}
+};
+//typedef void Edge;
 class Edge { };
-void first() const;
-void next() const;
+void first(Node& i) const {
-};
+Parent1::graph->first(*static_cast<Graph1Node*>(&i));
+i.backward=false;
-//not yet working
+if (*static_cast<Graph1Node*>(&i)==INVALID) {
+	Parent2::graph->first(*static_cast<Graph1Node*>(&i));
+	i.backward=true;
+}
+}
+void next(Node& i) const {
+if (!(i.backward)) {
+	Parent1::graph->next(*static_cast<Graph1Node*>(&i));
+	if (*static_cast<Graph1Node*>(&i)==INVALID) {
+	  Parent2::graph->first(*static_cast<Graph1Node*>(&i));
+	  i.backward=true;
+	}
+} else {
+	Parent2::graph->next(*static_cast<Graph1Node*>(&i));
+}
+}
+int id(const Node& n) const {
+if (!n.backward)
+	return this->Parent1::graph->id(n);
+else
+	return this->Parent2::graph->id(n);
+}
+template <typename _Value>
+class NodeMap {
+protected:
+typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
+typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
+ParentMap1 forward_map;
+ParentMap2 backward_map;
+public:
+typedef _Value Value;
+typedef Node Key;
+NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
+	forward_map(*(gw.Parent1::graph)),
+	backward_map(*(gw.Parent2::graph)) { }
+NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
+	      const _Value& value) :
+	forward_map(*(gw.Parent1::graph), value),
+	backward_map(*(gw.Parent2::graph), value) { }
+_Value operator[](const Node& n) const {
+	if (!n.backward)
+	  return forward_map[n];
+	else
+	  return backward_map[n];
+}
+void set(const Node& n, const _Value& value) {
+	if (!n.backward)
+	  forward_map.set(n, value);
+	else
+	  backward_map.set(n, value);
+}
+//       using ParentMap1::operator[];
+//       using ParentMap2::operator[];
+};
+};
+/*! A graph wrapper base class
+for merging the node-set of two node-disjoint graphs
+into the node-set of one graph.
+Specialization for the case when
+_Graph1::Node are base and derived _Graph2::Node.
+NOT YET IMPLEMENTED
+*/
 template <typename _Graph1, typename _Graph2>
 class MergeNodeGraphWrapperBase<
 _Graph1, _Graph2, typename boost::enable_if<
 boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
 public P1<_Graph1>, public P2<_Graph2> {
 public :
-void printNode() const { std::cout << "2. nagyobb" << std::endl; }
+static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }
 typedef _Graph1 Graph1;
 typedef _Graph2 Graph2;
 typedef P1<_Graph1> Parent1;
 typedef P2<_Graph2> Parent2;
 typedef typename Parent1::Node Graph1Node;
 class MergeNodeGraphWrapperBase<
 _Graph1, _Graph2, typename boost::enable_if<
 boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
 public P1<_Graph1>, public P2<_Graph2> {
 public :
-void printNode() const { std::cout << "1. nagyobb" << std::endl; }
+static void printNode() { std::cout << "node: 1st is derived" << std::endl; }
 typedef _Graph1 Graph1;
 typedef _Graph2 Graph2;
 typedef P1<_Graph1> Parent1;
 typedef P2<_Graph2> Parent2;
 typedef typename Parent1::Node Graph1Node;
 void first() const;
 void next() const;
 };
+/*! A graph wrapper class
+fors merging the node-set of two node-disjoint graphs
+into one node-set. It does not satisfy
+StaticGraph concept as it has no edge-set which
+works together with the node-set.
+*/
 template <typename _Graph1, typename _Graph2>
 class MergeNodeGraphWrapper : public
 IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
 public:
 typedef _Graph1 Graph1;
 Parent::Parent2::setGraph(_graph2);
 }
 };
-/*! A base class for merging the node-sets and edge-sets of
+/*! A grah wrapper base class
+for merging the node-sets and edge-sets of
 two node-disjoint graphs
 into one graph.
+Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
 */
 template <typename _Graph1, typename _Graph2, typename Enable=void>
 class MergeEdgeGraphWrapperBase :
 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
 public:
-void printEdge() const { std::cout << "generic" << std::endl; }
+static void printEdge() { std::cout << "edge: generic" << std::endl; }
 typedef _Graph1 Graph1;
 typedef _Graph2 Graph2;
 typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
 typedef typename Parent::Parent1 Parent1;
 typedef typename Parent::Parent2 Parent2;
 typedef typename Parent::Node Node;
 class Edge : public Graph1Edge, public Graph2Edge {
 friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
-template <typename Value> friend class EdgeMap;
+template <typename _Value> friend class EdgeMap;
 protected:
 bool backward; //true, iff backward
 public:
 Edge() { }
 /// \todo =false is needed, or causes problems?
 Edge(const Graph1Edge& n1,
 	   const Graph2Edge& n2, bool _backward) :
 	Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
 Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
 bool operator==(const Edge& v) const {
-	return (this->backward==v.backward &&
+	if (backward)
-		static_cast<Graph1Edge>(*this)==
+	  return (v.backward &&
-		static_cast<Graph1Edge>(v) &&
+		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
-		static_cast<Graph2Edge>(*this)==
+	else
-		static_cast<Graph2Edge>(v));
+	  return (!v.backward &&
+		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
 }
 bool operator!=(const Edge& v) const {
-	return (this->backward!=v.backward ||
+	return !(*this==v);
-		static_cast<Graph1Edge>(*this)!=
-		static_cast<Graph1Edge>(v) ||
-		static_cast<Graph2Edge>(*this)!=
-		static_cast<Graph2Edge>(v));
 }
 };
 using Parent::first;
 void first(Edge& i) const {
 else
 	return this->Parent2::graph->id(n);
 }
 template <typename _Value>
-class EdgeMap : public Parent1::template EdgeMap<_Value>,
+class EdgeMap {
-		    public Parent2::template EdgeMap<_Value> {
+protected:
-typedef typename Parent1::template EdgeMap<_Value> ParentMap1;
+typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
-typedef typename Parent2::template EdgeMap<_Value> ParentMap2;
+typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
+ParentMap1 forward_map;
+ParentMap2 backward_map;
 public:
 typedef _Value Value;
 typedef Edge Key;
 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
-	ParentMap1(gw), ParentMap2(gw) { }
+	forward_map(*(gw.Parent1::graph)),
+	backward_map(*(gw.Parent2::graph)) { }
 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
 	      const _Value& value) :
-	ParentMap1(gw, value), ParentMap2(gw, value) { }
+	forward_map(*(gw.Parent1::graph), value),
+	backward_map(*(gw.Parent2::graph), value) { }
 _Value operator[](const Edge& n) const {
 	if (!n.backward)
-	  return ParentMap1::operator[](n);
+	  return forward_map[n];
 	else
-	  return ParentMap2::operator[](n);
+	  return backward_map[n];
 }
 void set(const Edge& n, const _Value& value) {
 	if (!n.backward)
-	  ParentMap1::set(n, value);
+	  forward_map.set(n, value);
 	else
-	  ParentMap2::set(n, value);
+	  backward_map.set(n, value);
 }
 //       using ParentMap1::operator[];
 //       using ParentMap2::operator[];
 };
 };
+/*! A graph wrapper base class
+for merging the node-sets and edge-sets of
+two node-disjoint graphs
+into one graph.
+Specialization for the case when _Graph1::Edge and _Graph2::Edge
+are the same.
+*/
+template <typename _Graph1, typename _Graph2>
+class MergeEdgeGraphWrapperBase<
+_Graph1, _Graph2, typename boost::enable_if<
+boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
+public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
+public:
+static void printEdge() { std::cout << "edge: same" << std::endl; }
+typedef _Graph1 Graph1;
+typedef _Graph2 Graph2;
+typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
+typedef typename Parent::Parent1 Parent1;
+typedef typename Parent::Parent2 Parent2;
+//     typedef P1<_Graph1> Parent1;
+//     typedef P2<_Graph2> Parent2;
+typedef typename Parent1::Edge Graph1Edge;
+typedef typename Parent2::Edge Graph2Edge;
+protected:
+MergeEdgeGraphWrapperBase() { }
+public:
+template <typename _Value> class EdgeMap;
+typedef typename Parent::Node Node;
+class Edge : public Graph1Edge {
+friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
+template <typename _Value> friend class EdgeMap;
+protected:
+bool backward; //true, iff backward
+public:
+Edge() { }
+/// \todo =false is needed, or causes problems?
+/// If \c _backward is false, then we get an edge corresponding to the
+/// original one, otherwise its oppositely directed pair is obtained.
+Edge(const Graph1Edge& n1,
+	   const Graph2Edge& n2, bool _backward) :
+	Graph1Edge(!backward ? n1 : n2), backward(_backward) { }
+Edge(Invalid i) : Graph1Edge(i), backward(true) { }
+bool operator==(const Edge& v) const {
+	return (backward==v.backward &&
+		static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
+}
+bool operator!=(const Edge& v) const {
+	return !(*this==v);
+}
+};
+using Parent::first;
+void first(Edge& i) const {
+Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
+i.backward=false;
+if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
+	i.backward=true;
+}
+}
+void firstIn(Edge& i, const Node& n) const {
+Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
+i.backward=false;
+if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
+	i.backward=true;
+}
+}
+void firstOut(Edge& i, const Node& n) const {
+Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
+i.backward=false;
+if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
+	i.backward=true;
+}
+}
+using Parent::next;
+void next(Edge& i) const {
+if (!(i.backward)) {
+	Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	  Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
+	  i.backward=true;
+	}
+} else {
+	Parent2::graph->next(*static_cast<Graph1Edge*>(&i));
+}
+}
+void nextIn(Edge& i) const {
+if (!(i.backward)) {
+	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	  Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
+	  i.backward=true;
+	}
+} else {
+	Parent2::graph->nextIn(*static_cast<Graph1Edge*>(&i));
+}
+}
+void nextOut(Edge& i) const {
+if (!(i.backward)) {
+	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	  Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
+	  i.backward=true;
+	}
+} else {
+	Parent2::graph->nextOut(*static_cast<Graph1Edge*>(&i));
+}
+}
+Node source(const Edge& i) const {
+if (!(i.backward)) {
+	return
+	  Node(Parent1::graph->source(i), INVALID, false);
+} else {
+	return
+	  Node(INVALID, Parent2::graph->source(i), true);
+}
+}
+Node target(const Edge& i) const {
+if (!(i.backward)) {
+	return
+	  Node(Parent1::graph->target(i), INVALID, false);
+} else {
+	return
+	  Node(INVALID, Parent2::graph->target(i), true);
+}
+}
+using Parent::id;
+int id(const Edge& n) const {
+if (!n.backward)
+	return this->Parent1::graph->id(n);
+else
+	return this->Parent2::graph->id(n);
+}
+template <typename _Value>
+class EdgeMap {
+protected:
+typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
+typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
+ParentMap1 forward_map;
+ParentMap2 backward_map;
+public:
+typedef _Value Value;
+typedef Edge Key;
+EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
+	forward_map(*(gw.Parent1::graph)),
+	backward_map(*(gw.Parent2::graph)) { }
+EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
+	      const _Value& value) :
+	forward_map(*(gw.Parent1::graph), value),
+	backward_map(*(gw.Parent2::graph), value) { }
+_Value operator[](const Edge& n) const {
+	if (!n.backward)
+	  return forward_map[n];
+	else
+	  return backward_map[n];
+}
+void set(const Edge& n, const _Value& value) {
+	if (!n.backward)
+	  forward_map.set(n, value);
+	else
+	  backward_map.set(n, value);
+}
+//       using ParentMap1::operator[];
+//       using ParentMap2::operator[];
+};
+};
+/*! A graph wrapper class
+for merging the node-sets and edge-sets of
+two node-disjoint graphs
+into one graph.
+*/
 template <typename _Graph1, typename _Graph2>
 class MergeEdgeGraphWrapper : public
 IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
 public:
 typedef _Graph1 Graph1;
 Parent::Parent2::setGraph(_graph2);
 }
 };
+/*! A graph wrapper base class for the following functionality.
+If a bijection is given between the node-sets of two graphs,
+then the second one can be considered as a new edge-set
+over th first node-set.
+*/
 template <typename _Graph, typename _EdgeSetGraph>
 class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
 public:
 typedef GraphWrapperBase<_Graph> Parent;
 typedef _Graph Graph;
 void clear() const { Parent::clear(); edge_set_graph->clear(); }
 bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
 bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
-using Parent::id;
+int id(const Node& e) const { return Parent::id(e); }
 int id(const Edge& e) const { return edge_set_graph->id(e); }
 Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
 template <typename _Value>
 	Parent(*(gw.edge_set_graph), _value) { }
 };
 };
+/*! A graph wrapper class for the following functionality.
+If a bijection is given between the node-sets of two graphs,
+then the second one can be considered as a new edge-set
+over th first node-set.
+*/
 template <typename _Graph, typename _EdgeSetGraph>
 class NewEdgeSetGraphWrapper :
 public IterableGraphExtender<
 NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
 public:
 setNodeMap(_n_node);
 setENodeMap(_e_node);
 }
 };
+/*! A graph wrapper base class
+for merging graphs of type _Graph1 and _Graph2
+which are given on the same node-set
+(specially on the node-set of Graph1)
+into one graph.
+In an other point of view, _Graph1 is extended with
+the edge-set of _Graph2.
+*/
+template <typename _Graph1, typename _Graph2, typename Enable=void>
+class AugmentingGraphWrapperBase :
+public P1<_Graph1> {
+public:
+void printAugment() const { std::cout << "generic" << std::endl; }
+typedef _Graph1 Graph1;
+typedef _Graph2 Graph2;
+typedef P1<_Graph1> Parent1;
+typedef P2<_Graph2> Parent2;
+typedef typename Parent1::Edge Graph1Edge;
+typedef typename Parent2::Edge Graph2Edge;
+protected:
+AugmentingGraphWrapperBase() { }
+_Graph2* graph2;
+void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
+public:
+template <typename _Value> class EdgeMap;
+typedef typename Parent1::Node Node;
+class Edge : public Graph1Edge, public Graph2Edge {
+friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
+template <typename _Value> friend class EdgeMap;
+protected:
+bool backward; //true, iff backward
+public:
+Edge() { }
+/// \todo =false is needed, or causes problems?
+/// If \c _backward is false, then we get an edge corresponding to the
+/// original one, otherwise its oppositely directed pair is obtained.
+Edge(const Graph1Edge& n1,
+	   const Graph2Edge& n2, bool _backward) :
+	Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
+Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
+bool operator==(const Edge& v) const {
+	if (backward)
+	  return (v.backward &&
+		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
+	else
+	  return (!v.backward &&
+		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
+}
+bool operator!=(const Edge& v) const {
+	return !(*this==v);
+}
+};
+using Parent1::first;
+void first(Edge& i) const {
+Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
+i.backward=false;
+if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	graph2->first(*static_cast<Graph2Edge*>(&i));
+	i.backward=true;
+}
+}
+void firstIn(Edge& i, const Node& n) const {
+Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
+i.backward=false;
+if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
+	i.backward=true;
+}
+}
+void firstOut(Edge& i, const Node& n) const {
+Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
+i.backward=false;
+if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
+	i.backward=true;
+}
+}
+using Parent1::next;
+void next(Edge& i) const {
+if (!(i.backward)) {
+	Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	  graph2->first(*static_cast<Graph2Edge*>(&i));
+	  i.backward=true;
+	}
+} else {
+	graph2->next(*static_cast<Graph2Edge*>(&i));
+}
+}
+void nextIn(Edge& i) const {
+if (!(i.backward)) {
+	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	  graph2->first(*static_cast<Graph2Edge*>(&i));
+	  i.backward=true;
+	}
+} else {
+	graph2->nextIn(*static_cast<Graph2Edge*>(&i));
+}
+}
+void nextOut(Edge& i) const {
+if (!(i.backward)) {
+	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+	  graph2->first(*static_cast<Graph2Edge*>(&i));
+	  i.backward=true;
+	}
+} else {
+	graph2->nextOut(*static_cast<Graph2Edge*>(&i));
+}
+}
+Node source(const Edge& i) const {
+if (!(i.backward)) {
+	return Parent1::graph->source(i);
+} else {
+	return graph2->source(i);
+}
+}
+Node target(const Edge& i) const {
+if (!(i.backward)) {
+	return Parent1::graph->target(i);
+} else {
+	return graph2->target(i);
+}
+}
+int id(const Node& n) const {
+return Parent1::id(n);
+};
+int id(const Edge& n) const {
+if (!n.backward)
+	return this->Parent1::graph->id(n);
+else
+	return this->graph2->id(n);
+}
+template <typename _Value>
+class EdgeMap {
+protected:
+typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
+typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
+ParentMap1 forward_map;
+ParentMap2 backward_map;
+public:
+typedef _Value Value;
+typedef Edge Key;
+EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) :
+	forward_map(*(gw.Parent1::graph)),
+	backward_map(*(gw.graph2)) { }
+EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw,
+	      const _Value& value) :
+	forward_map(*(gw.Parent1::graph), value),
+	backward_map(*(gw.graph2), value) { }
+_Value operator[](const Edge& n) const {
+	if (!n.backward)
+	  return forward_map[n];
+	else
+	  return backward_map[n];
+}
+void set(const Edge& n, const _Value& value) {
+	if (!n.backward)
+	  forward_map.set(n, value);
+	else
+	  backward_map.set(n, value);
+}
+//       using ParentMap1::operator[];
+//       using ParentMap2::operator[];
+};
+};
+/*! A graph wrapper class
+for merging two graphs (of type _Graph1 and _Graph2)
+with the same node-set
+(specially on the node-set of Graph1)
+into one graph.
+In an other point of view, _Graph1 is extended with
+the edge-set of _Graph2.
+*/
+template <typename _Graph1, typename _Graph2>
+class AugmentingGraphWrapper : public
+IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
+public:
+typedef
+IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
+Parent;
+typedef _Graph1 Graph1;
+typedef _Graph2 Graph2;
+protected:
+AugmentingGraphWrapper() { }
+public:
+AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
+setGraph(_graph1);
+setGraph2(_graph2);
+}
+};
 } //namespace lemon
 #endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H

changeset 1014	aae850a2394d
parent 1009	8cb323dbae93
child 1016	18d009b23e42