lemon-0.x: src/work/marci/merge_node_graph_wrapper.h@28e117c5bddf (annotated)

marci@915	1	/* -- C++ --
alpar@921	2	* src/lemon/merge_node_graph_wrapper.h - Part of LEMON, a generic C++ optimization library
marci@915	3	*
marci@915	4	* Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
marci@915	5	* (Egervary Combinatorial Optimization Research Group, EGRES).
marci@915	6	*
marci@915	7	* Permission to use, modify and distribute this software is granted
marci@915	8	* provided that this copyright notice appears in all copies. For
marci@915	9	* precise terms see the accompanying LICENSE file.
marci@915	10	*
marci@915	11	* This software is provided "AS IS" with no warranty of any kind,
marci@915	12	* express or implied, and with no claim as to its suitability for any
marci@915	13	* purpose.
marci@915	14	*
marci@915	15	*/
marci@915	16
alpar@921	17	#ifndef LEMON_MERGE_NODE_GRAPH_WRAPPER_H
alpar@921	18	#define LEMON_MERGE_NODE_GRAPH_WRAPPER_H
marci@917	19
alpar@921	20	#include <lemon/invalid.h>
alpar@921	21	#include <lemon/maps.h>
alpar@921	22	#include <lemon/map_defines.h>
alpar@921	23	#include <lemon/graph_wrapper.h>
marci@915	24	#include <iostream>
marci@1013	25
marci@1008	26	using std::cout;
marci@1008	27	using std::endl;
marci@915	28
marci@1007	29	#include <boost/type_traits.hpp>
marci@1007	30	#include <boost/utility/enable_if.hpp>
marci@1007	31
alpar@921	32	namespace lemon {
marci@915	33
marci@1007	34	template <class _Graph1>
marci@1007	35	class P1 : public GraphWrapperBase<_Graph1> {
marci@1007	36	};
marci@1007	37
marci@1007	38	template <class _Graph2>
marci@1007	39	class P2 : public GraphWrapperBase<_Graph2> {
marci@1007	40	};
marci@1007	41
marci@1013	42
marci@1013	43	/*! A graph wrapper base class
marci@1013	44	for merging the node-set of two node-disjoint graphs
marci@1013	45	into the node-set of one graph.
marci@1013	46	Generic implementation for unrelated _Graph1::Node and _Graph2::Node.
marci@1009	47	*/
marci@1002	48	template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1002	49	class MergeNodeGraphWrapperBase :
marci@1007	50	public P1<_Graph1>, public P2<_Graph2> {
marci@915	51	public:
marci@1013	52	static void printNode() { std::cout << "node: generic" << std::endl; }
marci@1002	53	typedef _Graph1 Graph1;
marci@1002	54	typedef _Graph2 Graph2;
marci@1007	55	typedef P1<_Graph1> Parent1;
marci@1007	56	typedef P2<_Graph2> Parent2;
marci@1002	57	typedef typename Parent1::Node Graph1Node;
marci@1002	58	typedef typename Parent2::Node Graph2Node;
marci@1002	59	protected:
marci@1002	60	MergeNodeGraphWrapperBase() { }
marci@1002	61	public:
marci@1002	62	template <typename _Value> class NodeMap;
marci@915	63
marci@915	64	class Node : public Graph1Node, public Graph2Node {
marci@1002	65	friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
marci@1013	66	template <typename _Value> friend class NodeMap;
marci@915	67	protected:
marci@915	68	bool backward; //true, iff backward
marci@915	69	public:
marci@915	70	Node() { }
marci@915	71	/// \todo =false is needed, or causes problems?
marci@915	72	/// If \c _backward is false, then we get an edge corresponding to the
marci@915	73	/// original one, otherwise its oppositely directed pair is obtained.
marci@915	74	Node(const Graph1Node& n1,
marci@915	75	const Graph2Node& n2, bool _backward) :
marci@915	76	Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
marci@915	77	Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
marci@915	78	bool operator==(const Node& v) const {
marci@1013	79	if (backward)
marci@1013	80	return (v.backward &&
marci@1013	81	static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
marci@1013	82	else
marci@1013	83	return (!v.backward &&
marci@1013	84	static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
marci@915	85	}
marci@915	86	bool operator!=(const Node& v) const {
marci@1013	87	return !(*this==v);
marci@915	88	}
marci@915	89	};
marci@915	90
marci@1002	91	//typedef void Edge;
marci@1002	92	class Edge { };
marci@1002	93
marci@1002	94	void first(Node& i) const {
marci@1002	95	Parent1::graph->first(static_cast<Graph1Node>(&i));
marci@1002	96	i.backward=false;
marci@1002	97	if (static_cast<Graph1Node>(&i)==INVALID) {
marci@1002	98	Parent2::graph->first(static_cast<Graph2Node>(&i));
marci@1002	99	i.backward=true;
marci@1002	100	}
marci@1002	101	}
marci@1002	102	void next(Node& i) const {
marci@1002	103	if (!(i.backward)) {
marci@1002	104	Parent1::graph->next(static_cast<Graph1Node>(&i));
marci@1002	105	if (static_cast<Graph1Node>(&i)==INVALID) {
marci@1002	106	Parent2::graph->first(static_cast<Graph2Node>(&i));
marci@1002	107	i.backward=true;
marci@915	108	}
marci@1002	109	} else {
marci@1002	110	Parent2::graph->next(static_cast<Graph2Node>(&i));
marci@915	111	}
marci@1002	112	}
marci@915	113
marci@915	114	int id(const Node& n) const {
marci@915	115	if (!n.backward)
marci@915	116	return this->Parent1::graph->id(n);
marci@915	117	else
marci@915	118	return this->Parent2::graph->id(n);
marci@915	119	}
marci@915	120
marci@1002	121	template <typename _Value>
marci@1013	122	class NodeMap {
marci@1013	123	protected:
marci@1013	124	typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
marci@1013	125	typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
marci@1013	126	ParentMap1 forward_map;
marci@1013	127	ParentMap2 backward_map;
marci@917	128	public:
marci@1002	129	typedef _Value Value;
marci@1002	130	typedef Node Key;
marci@1002	131	NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1013	132	forward_map(*(gw.Parent1::graph)),
marci@1013	133	backward_map(*(gw.Parent2::graph)) { }
marci@1002	134	NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1002	135	const _Value& value) :
marci@1013	136	forward_map(*(gw.Parent1::graph), value),
marci@1013	137	backward_map(*(gw.Parent2::graph), value) { }
marci@1002	138	_Value operator[](const Node& n) const {
marci@917	139	if (!n.backward)
marci@1013	140	return forward_map[n];
marci@917	141	else
marci@1013	142	return backward_map[n];
marci@917	143	}
marci@1002	144	void set(const Node& n, const _Value& value) {
marci@917	145	if (!n.backward)
marci@1013	146	forward_map.set(n, value);
marci@917	147	else
marci@1013	148	backward_map.set(n, value);
marci@917	149	}
marci@1009	150	// using ParentMap1::operator[];
marci@1009	151	// using ParentMap2::operator[];
marci@917	152	};
marci@1002	153
marci@1002	154	};
marci@1002	155
marci@1013	156
marci@1013	157	/*! A graph wrapper base class
marci@1013	158	for merging the node-set of two node-disjoint graphs
marci@1013	159	into the node-set of one graph.
marci@1013	160	Specialization for the case when _Graph1::Node are the same _Graph2::Node.
marci@1013	161	*/
marci@1007	162	template <typename _Graph1, typename _Graph2>
marci@1007	163	class MergeNodeGraphWrapperBase<
marci@1007	164	_Graph1, _Graph2, typename boost::enable_if<
marci@1007	165	boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
marci@1007	166	public P1<_Graph1>, public P2<_Graph2> {
marci@1013	167	public:
marci@1013	168	static void printNode() { std::cout << "node: same" << std::endl; }
marci@1007	169	typedef _Graph1 Graph1;
marci@1007	170	typedef _Graph2 Graph2;
marci@1007	171	typedef P1<_Graph1> Parent1;
marci@1007	172	typedef P2<_Graph2> Parent2;
marci@1007	173	typedef typename Parent1::Node Graph1Node;
marci@1007	174	typedef typename Parent2::Node Graph2Node;
marci@1007	175	protected:
marci@1007	176	MergeNodeGraphWrapperBase() { }
marci@1007	177	public:
marci@1013	178	template <typename _Value> class NodeMap;
marci@1013	179
marci@1013	180	class Node : public Graph1Node {
marci@1013	181	friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
marci@1013	182	template <typename _Value> friend class NodeMap;
marci@1013	183	protected:
marci@1013	184	bool backward; //true, iff backward
marci@1013	185	public:
marci@1013	186	Node() { }
marci@1013	187	/// \todo =false is needed, or causes problems?
marci@1013	188	/// If \c _backward is false, then we get an edge corresponding to the
marci@1013	189	/// original one, otherwise its oppositely directed pair is obtained.
marci@1013	190	Node(const Graph1Node& n1,
marci@1013	191	const Graph2Node& n2, bool _backward) :
marci@1013	192	Graph1Node(!backward ? n1 : n2), backward(_backward) { }
marci@1013	193	Node(Invalid i) : Graph1Node(i), backward(true) { }
marci@1013	194	bool operator==(const Node& v) const {
marci@1013	195	return (backward==v.backward &&
marci@1013	196	static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
marci@1013	197	}
marci@1013	198	bool operator!=(const Node& v) const {
marci@1013	199	return !(*this==v);
marci@1013	200	}
marci@1013	201	};
marci@1013	202
marci@1013	203	//typedef void Edge;
marci@1007	204	class Edge { };
marci@1013	205
marci@1013	206	void first(Node& i) const {
marci@1013	207	Parent1::graph->first(static_cast<Graph1Node>(&i));
marci@1013	208	i.backward=false;
marci@1013	209	if (static_cast<Graph1Node>(&i)==INVALID) {
marci@1013	210	Parent2::graph->first(static_cast<Graph1Node>(&i));
marci@1013	211	i.backward=true;
marci@1013	212	}
marci@1013	213	}
marci@1013	214	void next(Node& i) const {
marci@1013	215	if (!(i.backward)) {
marci@1013	216	Parent1::graph->next(static_cast<Graph1Node>(&i));
marci@1013	217	if (static_cast<Graph1Node>(&i)==INVALID) {
marci@1013	218	Parent2::graph->first(static_cast<Graph1Node>(&i));
marci@1013	219	i.backward=true;
marci@1013	220	}
marci@1013	221	} else {
marci@1013	222	Parent2::graph->next(static_cast<Graph1Node>(&i));
marci@1013	223	}
marci@1013	224	}
marci@1013	225
marci@1013	226	int id(const Node& n) const {
marci@1013	227	if (!n.backward)
marci@1013	228	return this->Parent1::graph->id(n);
marci@1013	229	else
marci@1013	230	return this->Parent2::graph->id(n);
marci@1013	231	}
marci@1013	232
marci@1013	233	template <typename _Value>
marci@1013	234	class NodeMap {
marci@1013	235	protected:
marci@1013	236	typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
marci@1013	237	typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
marci@1013	238	ParentMap1 forward_map;
marci@1013	239	ParentMap2 backward_map;
marci@1013	240	public:
marci@1013	241	typedef _Value Value;
marci@1013	242	typedef Node Key;
marci@1013	243	NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1013	244	forward_map(*(gw.Parent1::graph)),
marci@1013	245	backward_map(*(gw.Parent2::graph)) { }
marci@1013	246	NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1013	247	const _Value& value) :
marci@1013	248	forward_map(*(gw.Parent1::graph), value),
marci@1013	249	backward_map(*(gw.Parent2::graph), value) { }
marci@1013	250	_Value operator[](const Node& n) const {
marci@1013	251	if (!n.backward)
marci@1013	252	return forward_map[n];
marci@1013	253	else
marci@1013	254	return backward_map[n];
marci@1013	255	}
marci@1013	256	void set(const Node& n, const _Value& value) {
marci@1013	257	if (!n.backward)
marci@1013	258	forward_map.set(n, value);
marci@1013	259	else
marci@1013	260	backward_map.set(n, value);
marci@1013	261	}
marci@1013	262	// using ParentMap1::operator[];
marci@1013	263	// using ParentMap2::operator[];
marci@1013	264	};
marci@1013	265
marci@1007	266	};
marci@1007	267
marci@1013	268
marci@1013	269	/*! A graph wrapper base class
marci@1013	270	for merging the node-set of two node-disjoint graphs
marci@1013	271	into the node-set of one graph.
marci@1013	272	Specialization for the case when
marci@1016	273	_Graph1::Node is a base class and _Graph2::Node is derived from it.
marci@1013	274	*/
marci@1007	275	template <typename _Graph1, typename _Graph2>
marci@1007	276	class MergeNodeGraphWrapperBase<
marci@1007	277	_Graph1, _Graph2, typename boost::enable_if<
marci@1007	278	boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
marci@1007	279	public P1<_Graph1>, public P2<_Graph2> {
marci@1007	280	public :
marci@1013	281	static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }
marci@1007	282	typedef _Graph1 Graph1;
marci@1007	283	typedef _Graph2 Graph2;
marci@1007	284	typedef P1<_Graph1> Parent1;
marci@1007	285	typedef P2<_Graph2> Parent2;
marci@1007	286	typedef typename Parent1::Node Graph1Node;
marci@1007	287	typedef typename Parent2::Node Graph2Node;
marci@1007	288	protected:
marci@1007	289	MergeNodeGraphWrapperBase() { }
marci@1007	290	public:
marci@1016	291	template <typename _Value> class NodeMap;
marci@1016	292
marci@1016	293	class Node : public Graph2Node {
marci@1016	294	friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
marci@1016	295	template <typename _Value> friend class NodeMap;
marci@1016	296	protected:
marci@1016	297	bool backward; //true, iff backward
marci@1016	298	public:
marci@1016	299	Node() { }
marci@1016	300	/// \todo =false is needed, or causes problems?
marci@1016	301	/// If \c _backward is false, then we get an edge corresponding to the
marci@1016	302	/// original one, otherwise its oppositely directed pair is obtained.
marci@1016	303	Node(const Graph1Node& n1,
marci@1016	304	const Graph2Node& n2, bool _backward) :
marci@1016	305	Graph2Node(n2), backward(_backward) {
marci@1016	306	if (!backward) *this=n1;
marci@1016	307	}
marci@1016	308	Node(Invalid i) : Graph2Node(i), backward(true) { }
marci@1016	309	bool operator==(const Node& v) const {
marci@1016	310	if (backward)
marci@1016	311	return (v.backward &&
marci@1016	312	static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
marci@1016	313	else
marci@1016	314	return (!v.backward &&
marci@1016	315	static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
marci@1016	316	}
marci@1016	317	bool operator!=(const Node& v) const {
marci@1016	318	return !(*this==v);
marci@1016	319	}
marci@1016	320	};
marci@1016	321
marci@1016	322	//typedef void Edge;
marci@1007	323	class Edge { };
marci@1016	324
marci@1016	325	void first(Node& i) const {
marci@1016	326	Parent1::graph->first(static_cast<Graph1Node>(&i));
marci@1016	327	i.backward=false;
marci@1016	328	if (static_cast<Graph1Node>(&i)==INVALID) {
marci@1016	329	Parent2::graph->first(static_cast<Graph2Node>(&i));
marci@1016	330	i.backward=true;
marci@1016	331	}
marci@1016	332	}
marci@1016	333	void next(Node& i) const {
marci@1016	334	if (!(i.backward)) {
marci@1016	335	Parent1::graph->next(static_cast<Graph1Node>(&i));
marci@1016	336	if (static_cast<Graph1Node>(&i)==INVALID) {
marci@1016	337	Parent2::graph->first(static_cast<Graph2Node>(&i));
marci@1016	338	i.backward=true;
marci@1016	339	}
marci@1016	340	} else {
marci@1016	341	Parent2::graph->next(static_cast<Graph2Node>(&i));
marci@1016	342	}
marci@1016	343	}
marci@1016	344
marci@1016	345	int id(const Node& n) const {
marci@1016	346	if (!n.backward)
marci@1016	347	return this->Parent1::graph->id(n);
marci@1016	348	else
marci@1016	349	return this->Parent2::graph->id(n);
marci@1016	350	}
marci@1016	351
marci@1016	352	template <typename _Value>
marci@1016	353	class NodeMap {
marci@1016	354	protected:
marci@1016	355	typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
marci@1016	356	typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
marci@1016	357	ParentMap1 forward_map;
marci@1016	358	ParentMap2 backward_map;
marci@1016	359	public:
marci@1016	360	typedef _Value Value;
marci@1016	361	typedef Node Key;
marci@1016	362	NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1016	363	forward_map(*(gw.Parent1::graph)),
marci@1016	364	backward_map(*(gw.Parent2::graph)) { }
marci@1016	365	NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1016	366	const _Value& value) :
marci@1016	367	forward_map(*(gw.Parent1::graph), value),
marci@1016	368	backward_map(*(gw.Parent2::graph), value) { }
marci@1016	369	_Value operator[](const Node& n) const {
marci@1016	370	if (!n.backward)
marci@1016	371	return forward_map[n];
marci@1016	372	else
marci@1016	373	return backward_map[n];
marci@1016	374	}
marci@1016	375	void set(const Node& n, const _Value& value) {
marci@1016	376	if (!n.backward)
marci@1016	377	forward_map.set(n, value);
marci@1016	378	else
marci@1016	379	backward_map.set(n, value);
marci@1016	380	}
marci@1016	381	// using ParentMap1::operator[];
marci@1016	382	// using ParentMap2::operator[];
marci@1016	383	};
marci@1016	384
marci@1007	385	};
marci@1007	386
marci@1016	387
marci@1016	388	/*! A graph wrapper base class
marci@1016	389	for merging the node-set of two node-disjoint graphs
marci@1016	390	into the node-set of one graph.
marci@1016	391	Specialized implementaton for the case when _Graph1::Node is derived
marci@1016	392	from _Graph2::Node.
marci@1016	393	*/
marci@1007	394	template <typename _Graph1, typename _Graph2>
marci@1007	395	class MergeNodeGraphWrapperBase<
marci@1007	396	_Graph1, _Graph2, typename boost::enable_if<
marci@1007	397	boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
marci@1007	398	public P1<_Graph1>, public P2<_Graph2> {
marci@1007	399	public :
marci@1013	400	static void printNode() { std::cout << "node: 1st is derived" << std::endl; }
marci@1007	401	typedef _Graph1 Graph1;
marci@1007	402	typedef _Graph2 Graph2;
marci@1007	403	typedef P1<_Graph1> Parent1;
marci@1007	404	typedef P2<_Graph2> Parent2;
marci@1007	405	typedef typename Parent1::Node Graph1Node;
marci@1007	406	typedef typename Parent2::Node Graph2Node;
marci@1007	407	protected:
marci@1007	408	MergeNodeGraphWrapperBase() { }
marci@1007	409	public:
marci@1016	410	template <typename _Value> class NodeMap;
marci@1016	411
marci@1016	412	class Node : public Graph1Node {
marci@1016	413	friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
marci@1016	414	template <typename _Value> friend class NodeMap;
marci@1016	415	protected:
marci@1016	416	bool backward; //true, iff backward
marci@1016	417	public:
marci@1016	418	Node() { }
marci@1016	419	/// \todo =false is needed, or causes problems?
marci@1016	420	/// If \c _backward is false, then we get an edge corresponding to the
marci@1016	421	/// original one, otherwise its oppositely directed pair is obtained.
marci@1016	422	Node(const Graph1Node& n1,
marci@1016	423	const Graph2Node& n2, bool _backward) :
marci@1016	424	Graph1Node(n1), backward(_backward) {
marci@1016	425	if (backward) *this=n2;
marci@1016	426	}
marci@1016	427	Node(Invalid i) : Graph1Node(i), backward(true) { }
marci@1016	428	bool operator==(const Node& v) const {
marci@1016	429	if (backward)
marci@1016	430	return (v.backward &&
marci@1016	431	static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
marci@1016	432	else
marci@1016	433	return (!v.backward &&
marci@1016	434	static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
marci@1016	435	}
marci@1016	436	bool operator!=(const Node& v) const {
marci@1016	437	return !(*this==v);
marci@1016	438	}
marci@1016	439	};
marci@1016	440
marci@1016	441	//typedef void Edge;
marci@1007	442	class Edge { };
marci@1016	443
marci@1016	444	void first(Node& i) const {
marci@1016	445	Parent1::graph->first(static_cast<Graph1Node>(&i));
marci@1016	446	i.backward=false;
marci@1016	447	if (static_cast<Graph1Node>(&i)==INVALID) {
marci@1016	448	Parent2::graph->first(static_cast<Graph2Node>(&i));
marci@1016	449	i.backward=true;
marci@1016	450	}
marci@1016	451	}
marci@1016	452	void next(Node& i) const {
marci@1016	453	if (!(i.backward)) {
marci@1016	454	Parent1::graph->next(static_cast<Graph1Node>(&i));
marci@1016	455	if (static_cast<Graph1Node>(&i)==INVALID) {
marci@1016	456	Parent2::graph->first(static_cast<Graph2Node>(&i));
marci@1016	457	i.backward=true;
marci@1016	458	}
marci@1016	459	} else {
marci@1016	460	Parent2::graph->next(static_cast<Graph2Node>(&i));
marci@1016	461	}
marci@1016	462	}
marci@1016	463
marci@1016	464	int id(const Node& n) const {
marci@1016	465	if (!n.backward)
marci@1016	466	return this->Parent1::graph->id(n);
marci@1016	467	else
marci@1016	468	return this->Parent2::graph->id(n);
marci@1016	469	}
marci@1016	470
marci@1016	471	template <typename _Value>
marci@1016	472	class NodeMap {
marci@1016	473	protected:
marci@1016	474	typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
marci@1016	475	typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
marci@1016	476	ParentMap1 forward_map;
marci@1016	477	ParentMap2 backward_map;
marci@1016	478	public:
marci@1016	479	typedef _Value Value;
marci@1016	480	typedef Node Key;
marci@1016	481	NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1016	482	forward_map(*(gw.Parent1::graph)),
marci@1016	483	backward_map(*(gw.Parent2::graph)) { }
marci@1016	484	NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1016	485	const _Value& value) :
marci@1016	486	forward_map(*(gw.Parent1::graph), value),
marci@1016	487	backward_map(*(gw.Parent2::graph), value) { }
marci@1016	488	_Value operator[](const Node& n) const {
marci@1016	489	if (!n.backward)
marci@1016	490	return forward_map[n];
marci@1016	491	else
marci@1016	492	return backward_map[n];
marci@1016	493	}
marci@1016	494	void set(const Node& n, const _Value& value) {
marci@1016	495	if (!n.backward)
marci@1016	496	forward_map.set(n, value);
marci@1016	497	else
marci@1016	498	backward_map.set(n, value);
marci@1016	499	}
marci@1016	500	// using ParentMap1::operator[];
marci@1016	501	// using ParentMap2::operator[];
marci@1016	502	};
marci@1016	503
marci@1007	504	};
marci@1007	505
marci@1002	506
marci@1013	507	/*! A graph wrapper class
marci@1013	508	fors merging the node-set of two node-disjoint graphs
marci@1013	509	into one node-set. It does not satisfy
marci@1013	510	StaticGraph concept as it has no edge-set which
marci@1013	511	works together with the node-set.
marci@1013	512	*/
marci@1009	513	template <typename _Graph1, typename _Graph2>
marci@1002	514	class MergeNodeGraphWrapper : public
marci@1009	515	IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
marci@1002	516	public:
marci@1002	517	typedef _Graph1 Graph1;
marci@1002	518	typedef _Graph2 Graph2;
marci@1002	519	typedef IterableGraphExtender<
marci@1009	520	MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
marci@1002	521	protected:
marci@1002	522	MergeNodeGraphWrapper() { }
marci@1002	523	public:
marci@1002	524	MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
marci@1002	525	Parent::Parent1::setGraph(_graph1);
marci@1002	526	Parent::Parent2::setGraph(_graph2);
marci@1002	527	}
marci@915	528	};
marci@915	529
marci@1009	530
marci@1013	531	/*! A grah wrapper base class
marci@1013	532	for merging the node-sets and edge-sets of
marci@1009	533	two node-disjoint graphs
marci@1009	534	into one graph.
marci@1013	535	Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
marci@1009	536	*/
marci@1009	537	template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1009	538	class MergeEdgeGraphWrapperBase :
marci@1009	539	public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1009	540	public:
marci@1013	541	static void printEdge() { std::cout << "edge: generic" << std::endl; }
marci@1009	542	typedef _Graph1 Graph1;
marci@1009	543	typedef _Graph2 Graph2;
marci@1009	544	typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1009	545	typedef typename Parent::Parent1 Parent1;
marci@1009	546	typedef typename Parent::Parent2 Parent2;
marci@1009	547	// typedef P1<_Graph1> Parent1;
marci@1009	548	// typedef P2<_Graph2> Parent2;
marci@1009	549	typedef typename Parent1::Edge Graph1Edge;
marci@1009	550	typedef typename Parent2::Edge Graph2Edge;
marci@1009	551	protected:
marci@1009	552	MergeEdgeGraphWrapperBase() { }
marci@1009	553	public:
marci@1009	554	template <typename _Value> class EdgeMap;
marci@1009	555
marci@1009	556	typedef typename Parent::Node Node;
marci@1009	557
marci@1009	558	class Edge : public Graph1Edge, public Graph2Edge {
marci@1009	559	friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
marci@1013	560	template <typename _Value> friend class EdgeMap;
marci@1009	561	protected:
marci@1009	562	bool backward; //true, iff backward
marci@1009	563	public:
marci@1009	564	Edge() { }
marci@1009	565	/// \todo =false is needed, or causes problems?
marci@1009	566	/// If \c _backward is false, then we get an edge corresponding to the
marci@1009	567	/// original one, otherwise its oppositely directed pair is obtained.
marci@1009	568	Edge(const Graph1Edge& n1,
marci@1009	569	const Graph2Edge& n2, bool _backward) :
marci@1009	570	Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
marci@1009	571	Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
marci@1009	572	bool operator==(const Edge& v) const {
marci@1013	573	if (backward)
marci@1013	574	return (v.backward &&
marci@1013	575	static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
marci@1013	576	else
marci@1013	577	return (!v.backward &&
marci@1013	578	static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1009	579	}
marci@1009	580	bool operator!=(const Edge& v) const {
marci@1013	581	return !(*this==v);
marci@1009	582	}
marci@1009	583	};
marci@1009	584
marci@1009	585	using Parent::first;
marci@1009	586	void first(Edge& i) const {
marci@1009	587	Parent1::graph->first(static_cast<Graph1Edge>(&i));
marci@1009	588	i.backward=false;
marci@1009	589	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1009	590	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1009	591	i.backward=true;
marci@1009	592	}
marci@1009	593	}
marci@1009	594	void firstIn(Edge& i, const Node& n) const {
marci@1009	595	Parent1::graph->firstIn(static_cast<Graph1Edge>(&i), n);
marci@1009	596	i.backward=false;
marci@1009	597	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1009	598	Parent2::graph->firstIn(static_cast<Graph2Edge>(&i), n);
marci@1009	599	i.backward=true;
marci@1009	600	}
marci@1009	601	}
marci@1009	602	void firstOut(Edge& i, const Node& n) const {
marci@1009	603	Parent1::graph->firstOut(static_cast<Graph1Edge>(&i), n);
marci@1009	604	i.backward=false;
marci@1009	605	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1009	606	Parent2::graph->firstOut(static_cast<Graph2Edge>(&i), n);
marci@1009	607	i.backward=true;
marci@1009	608	}
marci@1009	609	}
marci@1009	610
marci@1009	611	using Parent::next;
marci@1009	612	void next(Edge& i) const {
marci@1009	613	if (!(i.backward)) {
marci@1009	614	Parent1::graph->next(static_cast<Graph1Edge>(&i));
marci@1009	615	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1009	616	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1009	617	i.backward=true;
marci@1009	618	}
marci@1009	619	} else {
marci@1009	620	Parent2::graph->next(static_cast<Graph2Edge>(&i));
marci@1009	621	}
marci@1009	622	}
marci@1009	623	void nextIn(Edge& i) const {
marci@1009	624	if (!(i.backward)) {
marci@1009	625	Parent1::graph->nextIn(static_cast<Graph1Edge>(&i));
marci@1009	626	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1009	627	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1009	628	i.backward=true;
marci@1009	629	}
marci@1009	630	} else {
marci@1009	631	Parent2::graph->nextIn(static_cast<Graph2Edge>(&i));
marci@1009	632	}
marci@1009	633	}
marci@1009	634	void nextOut(Edge& i) const {
marci@1009	635	if (!(i.backward)) {
marci@1009	636	Parent1::graph->nextOut(static_cast<Graph1Edge>(&i));
marci@1009	637	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1009	638	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1009	639	i.backward=true;
marci@1009	640	}
marci@1009	641	} else {
marci@1009	642	Parent2::graph->nextOut(static_cast<Graph2Edge>(&i));
marci@1009	643	}
marci@1009	644	}
marci@1009	645
marci@1009	646	Node source(const Edge& i) const {
marci@1009	647	if (!(i.backward)) {
marci@1009	648	return
marci@1009	649	Node(Parent1::graph->source(i), INVALID, false);
marci@1009	650	} else {
marci@1009	651	return
marci@1009	652	Node(INVALID, Parent2::graph->source(i), true);
marci@1009	653	}
marci@1009	654	}
marci@1009	655
marci@1009	656	Node target(const Edge& i) const {
marci@1009	657	if (!(i.backward)) {
marci@1009	658	return
marci@1009	659	Node(Parent1::graph->target(i), INVALID, false);
marci@1009	660	} else {
marci@1009	661	return
marci@1009	662	Node(INVALID, Parent2::graph->target(i), true);
marci@1009	663	}
marci@1009	664	}
marci@1009	665
marci@1009	666	using Parent::id;
marci@1009	667	int id(const Edge& n) const {
marci@1009	668	if (!n.backward)
marci@1009	669	return this->Parent1::graph->id(n);
marci@1009	670	else
marci@1009	671	return this->Parent2::graph->id(n);
marci@1009	672	}
marci@1009	673
marci@1009	674	template <typename _Value>
marci@1013	675	class EdgeMap {
marci@1013	676	protected:
marci@1013	677	typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
marci@1013	678	typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
marci@1013	679	ParentMap1 forward_map;
marci@1013	680	ParentMap2 backward_map;
marci@1009	681	public:
marci@1009	682	typedef _Value Value;
marci@1009	683	typedef Edge Key;
marci@1009	684	EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1013	685	forward_map(*(gw.Parent1::graph)),
marci@1013	686	backward_map(*(gw.Parent2::graph)) { }
marci@1009	687	EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1009	688	const _Value& value) :
marci@1013	689	forward_map(*(gw.Parent1::graph), value),
marci@1013	690	backward_map(*(gw.Parent2::graph), value) { }
marci@1009	691	_Value operator[](const Edge& n) const {
marci@1009	692	if (!n.backward)
marci@1013	693	return forward_map[n];
marci@1009	694	else
marci@1013	695	return backward_map[n];
marci@1009	696	}
marci@1009	697	void set(const Edge& n, const _Value& value) {
marci@1009	698	if (!n.backward)
marci@1013	699	forward_map.set(n, value);
marci@1009	700	else
marci@1013	701	backward_map.set(n, value);
marci@1009	702	}
marci@1009	703	// using ParentMap1::operator[];
marci@1009	704	// using ParentMap2::operator[];
marci@1009	705	};
marci@1009	706
marci@1009	707	};
marci@1009	708
marci@1009	709
marci@1013	710	/*! A graph wrapper base class
marci@1013	711	for merging the node-sets and edge-sets of
marci@1013	712	two node-disjoint graphs
marci@1013	713	into one graph.
marci@1013	714	Specialization for the case when _Graph1::Edge and _Graph2::Edge
marci@1013	715	are the same.
marci@1013	716	*/
marci@1013	717	template <typename _Graph1, typename _Graph2>
marci@1013	718	class MergeEdgeGraphWrapperBase<
marci@1013	719	_Graph1, _Graph2, typename boost::enable_if<
marci@1016	720	boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
marci@1013	721	public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1013	722	public:
marci@1013	723	static void printEdge() { std::cout << "edge: same" << std::endl; }
marci@1013	724	typedef _Graph1 Graph1;
marci@1013	725	typedef _Graph2 Graph2;
marci@1013	726	typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1013	727	typedef typename Parent::Parent1 Parent1;
marci@1013	728	typedef typename Parent::Parent2 Parent2;
marci@1013	729	// typedef P1<_Graph1> Parent1;
marci@1013	730	// typedef P2<_Graph2> Parent2;
marci@1013	731	typedef typename Parent1::Edge Graph1Edge;
marci@1013	732	typedef typename Parent2::Edge Graph2Edge;
marci@1013	733	protected:
marci@1013	734	MergeEdgeGraphWrapperBase() { }
marci@1013	735	public:
marci@1013	736	template <typename _Value> class EdgeMap;
marci@1013	737
marci@1013	738	typedef typename Parent::Node Node;
marci@1013	739
marci@1013	740	class Edge : public Graph1Edge {
marci@1013	741	friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
marci@1013	742	template <typename _Value> friend class EdgeMap;
marci@1013	743	protected:
marci@1013	744	bool backward; //true, iff backward
marci@1013	745	public:
marci@1013	746	Edge() { }
marci@1013	747	/// \todo =false is needed, or causes problems?
marci@1013	748	/// If \c _backward is false, then we get an edge corresponding to the
marci@1013	749	/// original one, otherwise its oppositely directed pair is obtained.
marci@1013	750	Edge(const Graph1Edge& n1,
marci@1013	751	const Graph2Edge& n2, bool _backward) :
marci@1013	752	Graph1Edge(!backward ? n1 : n2), backward(_backward) { }
marci@1013	753	Edge(Invalid i) : Graph1Edge(i), backward(true) { }
marci@1013	754	bool operator==(const Edge& v) const {
marci@1013	755	return (backward==v.backward &&
marci@1013	756	static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1013	757	}
marci@1013	758	bool operator!=(const Edge& v) const {
marci@1013	759	return !(*this==v);
marci@1013	760	}
marci@1013	761	};
marci@1013	762
marci@1013	763	using Parent::first;
marci@1013	764	void first(Edge& i) const {
marci@1013	765	Parent1::graph->first(static_cast<Graph1Edge>(&i));
marci@1013	766	i.backward=false;
marci@1013	767	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	768	Parent2::graph->first(static_cast<Graph1Edge>(&i));
marci@1013	769	i.backward=true;
marci@1013	770	}
marci@1013	771	}
marci@1013	772	void firstIn(Edge& i, const Node& n) const {
marci@1013	773	Parent1::graph->firstIn(static_cast<Graph1Edge>(&i), n);
marci@1013	774	i.backward=false;
marci@1013	775	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	776	Parent2::graph->firstIn(static_cast<Graph1Edge>(&i), n);
marci@1013	777	i.backward=true;
marci@1013	778	}
marci@1013	779	}
marci@1013	780	void firstOut(Edge& i, const Node& n) const {
marci@1013	781	Parent1::graph->firstOut(static_cast<Graph1Edge>(&i), n);
marci@1013	782	i.backward=false;
marci@1013	783	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	784	Parent2::graph->firstOut(static_cast<Graph1Edge>(&i), n);
marci@1013	785	i.backward=true;
marci@1013	786	}
marci@1013	787	}
marci@1013	788
marci@1013	789	using Parent::next;
marci@1013	790	void next(Edge& i) const {
marci@1013	791	if (!(i.backward)) {
marci@1013	792	Parent1::graph->next(static_cast<Graph1Edge>(&i));
marci@1013	793	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	794	Parent2::graph->first(static_cast<Graph1Edge>(&i));
marci@1013	795	i.backward=true;
marci@1013	796	}
marci@1013	797	} else {
marci@1013	798	Parent2::graph->next(static_cast<Graph1Edge>(&i));
marci@1013	799	}
marci@1013	800	}
marci@1013	801	void nextIn(Edge& i) const {
marci@1013	802	if (!(i.backward)) {
marci@1013	803	Parent1::graph->nextIn(static_cast<Graph1Edge>(&i));
marci@1013	804	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	805	Parent2::graph->first(static_cast<Graph1Edge>(&i));
marci@1013	806	i.backward=true;
marci@1013	807	}
marci@1013	808	} else {
marci@1013	809	Parent2::graph->nextIn(static_cast<Graph1Edge>(&i));
marci@1013	810	}
marci@1013	811	}
marci@1013	812	void nextOut(Edge& i) const {
marci@1013	813	if (!(i.backward)) {
marci@1013	814	Parent1::graph->nextOut(static_cast<Graph1Edge>(&i));
marci@1013	815	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	816	Parent2::graph->first(static_cast<Graph1Edge>(&i));
marci@1013	817	i.backward=true;
marci@1013	818	}
marci@1013	819	} else {
marci@1013	820	Parent2::graph->nextOut(static_cast<Graph1Edge>(&i));
marci@1013	821	}
marci@1013	822	}
marci@1013	823
marci@1013	824	Node source(const Edge& i) const {
marci@1013	825	if (!(i.backward)) {
marci@1013	826	return
marci@1013	827	Node(Parent1::graph->source(i), INVALID, false);
marci@1013	828	} else {
marci@1013	829	return
marci@1013	830	Node(INVALID, Parent2::graph->source(i), true);
marci@1013	831	}
marci@1013	832	}
marci@1013	833
marci@1013	834	Node target(const Edge& i) const {
marci@1013	835	if (!(i.backward)) {
marci@1013	836	return
marci@1013	837	Node(Parent1::graph->target(i), INVALID, false);
marci@1013	838	} else {
marci@1013	839	return
marci@1013	840	Node(INVALID, Parent2::graph->target(i), true);
marci@1013	841	}
marci@1013	842	}
marci@1013	843
marci@1013	844	using Parent::id;
marci@1013	845	int id(const Edge& n) const {
marci@1013	846	if (!n.backward)
marci@1013	847	return this->Parent1::graph->id(n);
marci@1013	848	else
marci@1013	849	return this->Parent2::graph->id(n);
marci@1013	850	}
marci@1013	851
marci@1013	852	template <typename _Value>
marci@1013	853	class EdgeMap {
marci@1013	854	protected:
marci@1013	855	typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
marci@1013	856	typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
marci@1013	857	ParentMap1 forward_map;
marci@1013	858	ParentMap2 backward_map;
marci@1013	859	public:
marci@1013	860	typedef _Value Value;
marci@1013	861	typedef Edge Key;
marci@1013	862	EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1013	863	forward_map(*(gw.Parent1::graph)),
marci@1013	864	backward_map(*(gw.Parent2::graph)) { }
marci@1013	865	EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1013	866	const _Value& value) :
marci@1013	867	forward_map(*(gw.Parent1::graph), value),
marci@1013	868	backward_map(*(gw.Parent2::graph), value) { }
marci@1013	869	_Value operator[](const Edge& n) const {
marci@1013	870	if (!n.backward)
marci@1013	871	return forward_map[n];
marci@1013	872	else
marci@1013	873	return backward_map[n];
marci@1013	874	}
marci@1013	875	void set(const Edge& n, const _Value& value) {
marci@1013	876	if (!n.backward)
marci@1013	877	forward_map.set(n, value);
marci@1013	878	else
marci@1013	879	backward_map.set(n, value);
marci@1013	880	}
marci@1013	881	// using ParentMap1::operator[];
marci@1013	882	// using ParentMap2::operator[];
marci@1013	883	};
marci@1013	884
marci@1013	885	};
marci@1013	886
marci@1013	887
marci@1016	888	/*! A grah wrapper base class
marci@1016	889	for merging the node-sets and edge-sets of
marci@1016	890	two node-disjoint graphs
marci@1016	891	into one graph.
marci@1016	892	Specialized implementation for the case
marci@1016	893	when _Graph1::Edge is a base class and _Graph2::Edge
marci@1016	894	is derived from it.
marci@1016	895	*/
marci@1016	896	template <typename _Graph1, typename _Graph2>
marci@1016	897	class MergeEdgeGraphWrapperBase<
marci@1016	898	_Graph1, _Graph2, typename boost::enable_if<
marci@1016	899	boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
marci@1016	900	public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1016	901	public:
marci@1016	902	static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; }
marci@1016	903	typedef _Graph1 Graph1;
marci@1016	904	typedef _Graph2 Graph2;
marci@1016	905	typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1016	906	typedef typename Parent::Parent1 Parent1;
marci@1016	907	typedef typename Parent::Parent2 Parent2;
marci@1016	908	// typedef P1<_Graph1> Parent1;
marci@1016	909	// typedef P2<_Graph2> Parent2;
marci@1016	910	typedef typename Parent1::Edge Graph1Edge;
marci@1016	911	typedef typename Parent2::Edge Graph2Edge;
marci@1016	912	protected:
marci@1016	913	MergeEdgeGraphWrapperBase() { }
marci@1016	914	public:
marci@1016	915	template <typename _Value> class EdgeMap;
marci@1016	916
marci@1016	917	typedef typename Parent::Node Node;
marci@1016	918
marci@1016	919	class Edge : public Graph2Edge {
marci@1016	920	friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
marci@1016	921	template <typename _Value> friend class EdgeMap;
marci@1016	922	protected:
marci@1016	923	bool backward; //true, iff backward
marci@1016	924	public:
marci@1016	925	Edge() { }
marci@1016	926	/// \todo =false is needed, or causes problems?
marci@1016	927	/// If \c _backward is false, then we get an edge corresponding to the
marci@1016	928	/// original one, otherwise its oppositely directed pair is obtained.
marci@1016	929	Edge(const Graph1Edge& n1,
marci@1016	930	const Graph2Edge& n2, bool _backward) :
marci@1016	931	Graph2Edge(n2), backward(_backward) {
marci@1016	932	if (!backward) *this=n1;
marci@1016	933	}
marci@1016	934	Edge(Invalid i) : Graph2Edge(i), backward(true) { }
marci@1016	935	bool operator==(const Edge& v) const {
marci@1016	936	if (backward)
marci@1016	937	return (v.backward &&
marci@1016	938	static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
marci@1016	939	else
marci@1016	940	return (!v.backward &&
marci@1016	941	static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1016	942	}
marci@1016	943	bool operator!=(const Edge& v) const {
marci@1016	944	return !(*this==v);
marci@1016	945	}
marci@1016	946	};
marci@1016	947
marci@1016	948	using Parent::first;
marci@1016	949	void first(Edge& i) const {
marci@1016	950	Parent1::graph->first(static_cast<Graph1Edge>(&i));
marci@1016	951	i.backward=false;
marci@1016	952	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	953	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1016	954	i.backward=true;
marci@1016	955	}
marci@1016	956	}
marci@1016	957	void firstIn(Edge& i, const Node& n) const {
marci@1016	958	Parent1::graph->firstIn(static_cast<Graph1Edge>(&i), n);
marci@1016	959	i.backward=false;
marci@1016	960	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	961	Parent2::graph->firstIn(static_cast<Graph2Edge>(&i), n);
marci@1016	962	i.backward=true;
marci@1016	963	}
marci@1016	964	}
marci@1016	965	void firstOut(Edge& i, const Node& n) const {
marci@1016	966	Parent1::graph->firstOut(static_cast<Graph1Edge>(&i), n);
marci@1016	967	i.backward=false;
marci@1016	968	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	969	Parent2::graph->firstOut(static_cast<Graph2Edge>(&i), n);
marci@1016	970	i.backward=true;
marci@1016	971	}
marci@1016	972	}
marci@1016	973
marci@1016	974	using Parent::next;
marci@1016	975	void next(Edge& i) const {
marci@1016	976	if (!(i.backward)) {
marci@1016	977	Parent1::graph->next(static_cast<Graph1Edge>(&i));
marci@1016	978	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	979	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1016	980	i.backward=true;
marci@1016	981	}
marci@1016	982	} else {
marci@1016	983	Parent2::graph->next(static_cast<Graph2Edge>(&i));
marci@1016	984	}
marci@1016	985	}
marci@1016	986	void nextIn(Edge& i) const {
marci@1016	987	if (!(i.backward)) {
marci@1016	988	Parent1::graph->nextIn(static_cast<Graph1Edge>(&i));
marci@1016	989	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	990	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1016	991	i.backward=true;
marci@1016	992	}
marci@1016	993	} else {
marci@1016	994	Parent2::graph->nextIn(static_cast<Graph2Edge>(&i));
marci@1016	995	}
marci@1016	996	}
marci@1016	997	void nextOut(Edge& i) const {
marci@1016	998	if (!(i.backward)) {
marci@1016	999	Parent1::graph->nextOut(static_cast<Graph1Edge>(&i));
marci@1016	1000	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	1001	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1016	1002	i.backward=true;
marci@1016	1003	}
marci@1016	1004	} else {
marci@1016	1005	Parent2::graph->nextOut(static_cast<Graph2Edge>(&i));
marci@1016	1006	}
marci@1016	1007	}
marci@1016	1008
marci@1016	1009	Node source(const Edge& i) const {
marci@1016	1010	if (!(i.backward)) {
marci@1016	1011	return
marci@1016	1012	Node(Parent1::graph->source(i), INVALID, false);
marci@1016	1013	} else {
marci@1016	1014	return
marci@1016	1015	Node(INVALID, Parent2::graph->source(i), true);
marci@1016	1016	}
marci@1016	1017	}
marci@1016	1018
marci@1016	1019	Node target(const Edge& i) const {
marci@1016	1020	if (!(i.backward)) {
marci@1016	1021	return
marci@1016	1022	Node(Parent1::graph->target(i), INVALID, false);
marci@1016	1023	} else {
marci@1016	1024	return
marci@1016	1025	Node(INVALID, Parent2::graph->target(i), true);
marci@1016	1026	}
marci@1016	1027	}
marci@1016	1028
marci@1016	1029	using Parent::id;
marci@1016	1030	int id(const Edge& n) const {
marci@1016	1031	if (!n.backward)
marci@1016	1032	return this->Parent1::graph->id(n);
marci@1016	1033	else
marci@1016	1034	return this->Parent2::graph->id(n);
marci@1016	1035	}
marci@1016	1036
marci@1016	1037	template <typename _Value>
marci@1016	1038	class EdgeMap {
marci@1016	1039	protected:
marci@1016	1040	typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
marci@1016	1041	typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
marci@1016	1042	ParentMap1 forward_map;
marci@1016	1043	ParentMap2 backward_map;
marci@1016	1044	public:
marci@1016	1045	typedef _Value Value;
marci@1016	1046	typedef Edge Key;
marci@1016	1047	EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1016	1048	forward_map(*(gw.Parent1::graph)),
marci@1016	1049	backward_map(*(gw.Parent2::graph)) { }
marci@1016	1050	EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1016	1051	const _Value& value) :
marci@1016	1052	forward_map(*(gw.Parent1::graph), value),
marci@1016	1053	backward_map(*(gw.Parent2::graph), value) { }
marci@1016	1054	_Value operator[](const Edge& n) const {
marci@1016	1055	if (!n.backward)
marci@1016	1056	return forward_map[n];
marci@1016	1057	else
marci@1016	1058	return backward_map[n];
marci@1016	1059	}
marci@1016	1060	void set(const Edge& n, const _Value& value) {
marci@1016	1061	if (!n.backward)
marci@1016	1062	forward_map.set(n, value);
marci@1016	1063	else
marci@1016	1064	backward_map.set(n, value);
marci@1016	1065	}
marci@1016	1066	// using ParentMap1::operator[];
marci@1016	1067	// using ParentMap2::operator[];
marci@1016	1068	};
marci@1016	1069
marci@1016	1070	};
marci@1016	1071
marci@1016	1072
marci@1016	1073	/*! A grah wrapper base class
marci@1016	1074	for merging the node-sets and edge-sets of
marci@1016	1075	two node-disjoint graphs
marci@1016	1076	into one graph.
marci@1016	1077	Specialized implementation for the case
marci@1016	1078	when _Graph1::Edge is derived from _Graph2::Edge.
marci@1016	1079	*/
marci@1016	1080	template <typename _Graph1, typename _Graph2>
marci@1016	1081	class MergeEdgeGraphWrapperBase<
marci@1016	1082	_Graph1, _Graph2, typename boost::enable_if<
marci@1016	1083	boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> :
marci@1016	1084	public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1016	1085	public:
marci@1016	1086	static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; }
marci@1016	1087	typedef _Graph1 Graph1;
marci@1016	1088	typedef _Graph2 Graph2;
marci@1016	1089	typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1016	1090	typedef typename Parent::Parent1 Parent1;
marci@1016	1091	typedef typename Parent::Parent2 Parent2;
marci@1016	1092	// typedef P1<_Graph1> Parent1;
marci@1016	1093	// typedef P2<_Graph2> Parent2;
marci@1016	1094	typedef typename Parent1::Edge Graph1Edge;
marci@1016	1095	typedef typename Parent2::Edge Graph2Edge;
marci@1016	1096	protected:
marci@1016	1097	MergeEdgeGraphWrapperBase() { }
marci@1016	1098	public:
marci@1016	1099	template <typename _Value> class EdgeMap;
marci@1016	1100
marci@1016	1101	typedef typename Parent::Node Node;
marci@1016	1102
marci@1016	1103	class Edge : public Graph1Edge {
marci@1016	1104	friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
marci@1016	1105	template <typename _Value> friend class EdgeMap;
marci@1016	1106	protected:
marci@1016	1107	bool backward; //true, iff backward
marci@1016	1108	public:
marci@1016	1109	Edge() { }
marci@1016	1110	/// \todo =false is needed, or causes problems?
marci@1016	1111	/// If \c _backward is false, then we get an edge corresponding to the
marci@1016	1112	/// original one, otherwise its oppositely directed pair is obtained.
marci@1016	1113	Edge(const Graph1Edge& n1,
marci@1016	1114	const Graph2Edge& n2, bool _backward) :
marci@1016	1115	Graph1Edge(n1), backward(_backward) {
marci@1016	1116	if (backward) *this=n2;
marci@1016	1117	}
marci@1016	1118	Edge(Invalid i) : Graph1Edge(i), backward(true) { }
marci@1016	1119	bool operator==(const Edge& v) const {
marci@1016	1120	if (backward)
marci@1016	1121	return (v.backward &&
marci@1016	1122	static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
marci@1016	1123	else
marci@1016	1124	return (!v.backward &&
marci@1016	1125	static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1016	1126	}
marci@1016	1127	bool operator!=(const Edge& v) const {
marci@1016	1128	return !(*this==v);
marci@1016	1129	}
marci@1016	1130	};
marci@1016	1131
marci@1016	1132	using Parent::first;
marci@1016	1133	void first(Edge& i) const {
marci@1016	1134	Parent1::graph->first(static_cast<Graph1Edge>(&i));
marci@1016	1135	i.backward=false;
marci@1016	1136	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	1137	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1016	1138	i.backward=true;
marci@1016	1139	}
marci@1016	1140	}
marci@1016	1141	void firstIn(Edge& i, const Node& n) const {
marci@1016	1142	Parent1::graph->firstIn(static_cast<Graph1Edge>(&i), n);
marci@1016	1143	i.backward=false;
marci@1016	1144	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	1145	Parent2::graph->firstIn(static_cast<Graph2Edge>(&i), n);
marci@1016	1146	i.backward=true;
marci@1016	1147	}
marci@1016	1148	}
marci@1016	1149	void firstOut(Edge& i, const Node& n) const {
marci@1016	1150	Parent1::graph->firstOut(static_cast<Graph1Edge>(&i), n);
marci@1016	1151	i.backward=false;
marci@1016	1152	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	1153	Parent2::graph->firstOut(static_cast<Graph2Edge>(&i), n);
marci@1016	1154	i.backward=true;
marci@1016	1155	}
marci@1016	1156	}
marci@1016	1157
marci@1016	1158	using Parent::next;
marci@1016	1159	void next(Edge& i) const {
marci@1016	1160	if (!(i.backward)) {
marci@1016	1161	Parent1::graph->next(static_cast<Graph1Edge>(&i));
marci@1016	1162	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	1163	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1016	1164	i.backward=true;
marci@1016	1165	}
marci@1016	1166	} else {
marci@1016	1167	Parent2::graph->next(static_cast<Graph2Edge>(&i));
marci@1016	1168	}
marci@1016	1169	}
marci@1016	1170	void nextIn(Edge& i) const {
marci@1016	1171	if (!(i.backward)) {
marci@1016	1172	Parent1::graph->nextIn(static_cast<Graph1Edge>(&i));
marci@1016	1173	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	1174	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1016	1175	i.backward=true;
marci@1016	1176	}
marci@1016	1177	} else {
marci@1016	1178	Parent2::graph->nextIn(static_cast<Graph2Edge>(&i));
marci@1016	1179	}
marci@1016	1180	}
marci@1016	1181	void nextOut(Edge& i) const {
marci@1016	1182	if (!(i.backward)) {
marci@1016	1183	Parent1::graph->nextOut(static_cast<Graph1Edge>(&i));
marci@1016	1184	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1016	1185	Parent2::graph->first(static_cast<Graph2Edge>(&i));
marci@1016	1186	i.backward=true;
marci@1016	1187	}
marci@1016	1188	} else {
marci@1016	1189	Parent2::graph->nextOut(static_cast<Graph2Edge>(&i));
marci@1016	1190	}
marci@1016	1191	}
marci@1016	1192
marci@1016	1193	Node source(const Edge& i) const {
marci@1016	1194	if (!(i.backward)) {
marci@1016	1195	return
marci@1016	1196	Node(Parent1::graph->source(i), INVALID, false);
marci@1016	1197	} else {
marci@1016	1198	return
marci@1016	1199	Node(INVALID, Parent2::graph->source(i), true);
marci@1016	1200	}
marci@1016	1201	}
marci@1016	1202
marci@1016	1203	Node target(const Edge& i) const {
marci@1016	1204	if (!(i.backward)) {
marci@1016	1205	return
marci@1016	1206	Node(Parent1::graph->target(i), INVALID, false);
marci@1016	1207	} else {
marci@1016	1208	return
marci@1016	1209	Node(INVALID, Parent2::graph->target(i), true);
marci@1016	1210	}
marci@1016	1211	}
marci@1016	1212
marci@1016	1213	using Parent::id;
marci@1016	1214	int id(const Edge& n) const {
marci@1016	1215	if (!n.backward)
marci@1016	1216	return this->Parent1::graph->id(n);
marci@1016	1217	else
marci@1016	1218	return this->Parent2::graph->id(n);
marci@1016	1219	}
marci@1016	1220
marci@1016	1221	template <typename _Value>
marci@1016	1222	class EdgeMap {
marci@1016	1223	protected:
marci@1016	1224	typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
marci@1016	1225	typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
marci@1016	1226	ParentMap1 forward_map;
marci@1016	1227	ParentMap2 backward_map;
marci@1016	1228	public:
marci@1016	1229	typedef _Value Value;
marci@1016	1230	typedef Edge Key;
marci@1016	1231	EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1016	1232	forward_map(*(gw.Parent1::graph)),
marci@1016	1233	backward_map(*(gw.Parent2::graph)) { }
marci@1016	1234	EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1016	1235	const _Value& value) :
marci@1016	1236	forward_map(*(gw.Parent1::graph), value),
marci@1016	1237	backward_map(*(gw.Parent2::graph), value) { }
marci@1016	1238	_Value operator[](const Edge& n) const {
marci@1016	1239	if (!n.backward)
marci@1016	1240	return forward_map[n];
marci@1016	1241	else
marci@1016	1242	return backward_map[n];
marci@1016	1243	}
marci@1016	1244	void set(const Edge& n, const _Value& value) {
marci@1016	1245	if (!n.backward)
marci@1016	1246	forward_map.set(n, value);
marci@1016	1247	else
marci@1016	1248	backward_map.set(n, value);
marci@1016	1249	}
marci@1016	1250	// using ParentMap1::operator[];
marci@1016	1251	// using ParentMap2::operator[];
marci@1016	1252	};
marci@1016	1253
marci@1016	1254	};
marci@1016	1255
marci@1016	1256
marci@1013	1257	/*! A graph wrapper class
marci@1013	1258	for merging the node-sets and edge-sets of
marci@1013	1259	two node-disjoint graphs
marci@1013	1260	into one graph.
marci@1013	1261	*/
marci@1009	1262	template <typename _Graph1, typename _Graph2>
marci@1009	1263	class MergeEdgeGraphWrapper : public
marci@1009	1264	IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
marci@1009	1265	public:
marci@1009	1266	typedef _Graph1 Graph1;
marci@1009	1267	typedef _Graph2 Graph2;
marci@1009	1268	typedef IterableGraphExtender<
marci@1009	1269	MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
marci@1009	1270	protected:
marci@1009	1271	MergeEdgeGraphWrapper() { }
marci@1009	1272	public:
marci@1009	1273	MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
marci@1009	1274	Parent::Parent1::setGraph(_graph1);
marci@1009	1275	Parent::Parent2::setGraph(_graph2);
marci@1009	1276	}
marci@1009	1277	};
marci@1009	1278
marci@1008	1279
marci@1013	1280	/*! A graph wrapper base class for the following functionality.
marci@1013	1281	If a bijection is given between the node-sets of two graphs,
marci@1013	1282	then the second one can be considered as a new edge-set
marci@1013	1283	over th first node-set.
marci@1013	1284	*/
marci@1008	1285	template <typename _Graph, typename _EdgeSetGraph>
marci@1008	1286	class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
marci@1008	1287	public:
marci@1008	1288	typedef GraphWrapperBase<_Graph> Parent;
marci@1008	1289	typedef _Graph Graph;
marci@1008	1290	typedef _EdgeSetGraph EdgeSetGraph;
marci@1008	1291	typedef typename _Graph::Node Node;
marci@1008	1292	typedef typename _EdgeSetGraph::Node ENode;
marci@1008	1293	protected:
marci@1008	1294	EdgeSetGraph* edge_set_graph;
marci@1008	1295	typename Graph::NodeMap<ENode>* e_node;
marci@1008	1296	typename EdgeSetGraph::NodeMap<Node>* n_node;
marci@1008	1297	void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) {
marci@1008	1298	edge_set_graph=&_edge_set_graph;
marci@1008	1299	}
marci@1008	1300	/// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
marci@1008	1301	void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
marci@1008	1302	n_node=&_n_node;
marci@1008	1303	}
marci@1008	1304	/// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
marci@1008	1305	void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
marci@1008	1306	e_node=&_e_node;
marci@1008	1307	}
marci@1008	1308	public:
marci@1008	1309	class Edge : public EdgeSetGraph::Edge {
marci@1008	1310	typedef typename EdgeSetGraph::Edge Parent;
marci@1008	1311	public:
marci@1008	1312	Edge() { }
marci@1008	1313	Edge(const Parent& e) : Parent(e) { }
marci@1008	1314	Edge(Invalid i) : Parent(i) { }
marci@1008	1315	};
marci@1008	1316
marci@1008	1317	using Parent::first;
marci@1008	1318	void first(Edge &e) const {
marci@1008	1319	edge_set_graph->first(e);
marci@1008	1320	}
marci@1008	1321	void firstOut(Edge& e, const Node& n) const {
marci@1008	1322	// cout << e_node << endl;
marci@1008	1323	// cout << n_node << endl;
marci@1008	1324	edge_set_graph->firstOut(e, (*e_node)[n]);
marci@1008	1325	}
marci@1008	1326	void firstIn(Edge& e, const Node& n) const {
marci@1008	1327	edge_set_graph->firstIn(e, (*e_node)[n]);
marci@1008	1328	}
marci@1008	1329
marci@1008	1330	using Parent::next;
marci@1008	1331	void next(Edge &e) const {
marci@1008	1332	edge_set_graph->next(e);
marci@1008	1333	}
marci@1008	1334	void nextOut(Edge& e) const {
marci@1008	1335	edge_set_graph->nextOut(e);
marci@1008	1336	}
marci@1008	1337	void nextIn(Edge& e) const {
marci@1008	1338	edge_set_graph->nextIn(e);
marci@1008	1339	}
marci@1008	1340
marci@1008	1341	Node source(const Edge& e) const {
marci@1008	1342	return (*n_node)[edge_set_graph->source(e)];
marci@1008	1343	}
marci@1008	1344	Node target(const Edge& e) const {
marci@1008	1345	return (*n_node)[edge_set_graph->target(e)];
marci@1008	1346	}
marci@1008	1347
marci@1008	1348	int edgeNum() const { return edge_set_graph->edgeNum(); }
marci@1008	1349
marci@1008	1350	Edge addEdge(const Node& u, const Node& v) {
marci@1008	1351	return edge_set_graph->addEdge((e_node)[u], (e_node)[v]);
marci@1008	1352	}
marci@1008	1353
marci@1008	1354	using Parent::erase;
marci@1008	1355	void erase(const Edge& i) const { edge_set_graph->erase(i); }
marci@1008	1356
marci@1008	1357	void clear() const { Parent::clear(); edge_set_graph->clear(); }
marci@1008	1358
marci@1008	1359	bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
marci@1008	1360	bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
marci@1008	1361
marci@1013	1362	int id(const Node& e) const { return Parent::id(e); }
marci@1008	1363	int id(const Edge& e) const { return edge_set_graph->id(e); }
marci@1008	1364
marci@1008	1365	Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
marci@1008	1366
marci@1008	1367	template <typename _Value>
marci@1008	1368	class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
marci@1008	1369	public:
marci@1008	1370	typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
marci@1008	1371	typedef _Value Value;
marci@1008	1372	typedef Edge Key;
marci@1008	1373	EdgeMap(const NewEdgeSetGraphWrapperBase& gw) :
marci@1008	1374	Parent(*(gw.edge_set_graph)) { }
marci@1008	1375	EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) :
marci@1008	1376	Parent(*(gw.edge_set_graph), _value) { }
marci@1008	1377	};
marci@1008	1378
marci@1008	1379	};
marci@1008	1380
marci@1013	1381
marci@1013	1382	/*! A graph wrapper class for the following functionality.
marci@1013	1383	If a bijection is given between the node-sets of two graphs,
marci@1013	1384	then the second one can be considered as a new edge-set
marci@1013	1385	over th first node-set.
marci@1013	1386	*/
marci@1008	1387	template <typename _Graph, typename _EdgeSetGraph>
marci@1008	1388	class NewEdgeSetGraphWrapper :
marci@1008	1389	public IterableGraphExtender<
marci@1008	1390	NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
marci@1008	1391	public:
marci@1008	1392	typedef _Graph Graph;
marci@1008	1393	typedef _EdgeSetGraph EdgeSetGraph;
marci@1008	1394	typedef IterableGraphExtender<
marci@1008	1395	NewEdgeSetGraphWrapper<_Graph, _EdgeSetGraph> > Parent;
marci@1008	1396	protected:
marci@1008	1397	NewEdgeSetGraphWrapper() { }
marci@1008	1398	public:
marci@1008	1399	NewEdgeSetGraphWrapper(_Graph& _graph,
marci@1008	1400	_EdgeSetGraph& _edge_set_graph,
marci@1008	1401	typename _Graph::
marci@1008	1402	NodeMap<typename _EdgeSetGraph::Node>& _e_node,
marci@1008	1403	typename _EdgeSetGraph::
marci@1008	1404	NodeMap<typename _Graph::Node>& _n_node) {
marci@1008	1405	setGraph(_graph);
marci@1008	1406	setEdgeSetGraph(_edge_set_graph);
marci@1008	1407	setNodeMap(_n_node);
marci@1008	1408	setENodeMap(_e_node);
marci@1008	1409	}
marci@1008	1410	};
marci@1008	1411
marci@1013	1412
marci@1013	1413	/*! A graph wrapper base class
marci@1013	1414	for merging graphs of type _Graph1 and _Graph2
marci@1013	1415	which are given on the same node-set
marci@1013	1416	(specially on the node-set of Graph1)
marci@1013	1417	into one graph.
marci@1013	1418	In an other point of view, _Graph1 is extended with
marci@1013	1419	the edge-set of _Graph2.
marci@1013	1420	*/
marci@1013	1421	template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1013	1422	class AugmentingGraphWrapperBase :
marci@1013	1423	public P1<_Graph1> {
marci@1013	1424	public:
marci@1013	1425	void printAugment() const { std::cout << "generic" << std::endl; }
marci@1013	1426	typedef _Graph1 Graph1;
marci@1013	1427	typedef _Graph2 Graph2;
marci@1013	1428	typedef P1<_Graph1> Parent1;
marci@1013	1429	typedef P2<_Graph2> Parent2;
marci@1013	1430	typedef typename Parent1::Edge Graph1Edge;
marci@1013	1431	typedef typename Parent2::Edge Graph2Edge;
marci@1013	1432	protected:
marci@1013	1433	AugmentingGraphWrapperBase() { }
marci@1013	1434	_Graph2* graph2;
marci@1013	1435	void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
marci@1013	1436	public:
marci@1013	1437
marci@1013	1438	template <typename _Value> class EdgeMap;
marci@1013	1439
marci@1013	1440	typedef typename Parent1::Node Node;
marci@1013	1441
marci@1013	1442	class Edge : public Graph1Edge, public Graph2Edge {
marci@1013	1443	friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
marci@1013	1444	template <typename _Value> friend class EdgeMap;
marci@1013	1445	protected:
marci@1013	1446	bool backward; //true, iff backward
marci@1013	1447	public:
marci@1013	1448	Edge() { }
marci@1013	1449	/// \todo =false is needed, or causes problems?
marci@1013	1450	/// If \c _backward is false, then we get an edge corresponding to the
marci@1013	1451	/// original one, otherwise its oppositely directed pair is obtained.
marci@1013	1452	Edge(const Graph1Edge& n1,
marci@1013	1453	const Graph2Edge& n2, bool _backward) :
marci@1013	1454	Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
marci@1013	1455	Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
marci@1013	1456	bool operator==(const Edge& v) const {
marci@1013	1457	if (backward)
marci@1013	1458	return (v.backward &&
marci@1013	1459	static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
marci@1013	1460	else
marci@1013	1461	return (!v.backward &&
marci@1013	1462	static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
marci@1013	1463	}
marci@1013	1464	bool operator!=(const Edge& v) const {
marci@1013	1465	return !(*this==v);
marci@1013	1466	}
marci@1013	1467	};
marci@1013	1468
marci@1013	1469	using Parent1::first;
marci@1013	1470	void first(Edge& i) const {
marci@1013	1471	Parent1::graph->first(static_cast<Graph1Edge>(&i));
marci@1013	1472	i.backward=false;
marci@1013	1473	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	1474	graph2->first(static_cast<Graph2Edge>(&i));
marci@1013	1475	i.backward=true;
marci@1013	1476	}
marci@1013	1477	}
marci@1013	1478	void firstIn(Edge& i, const Node& n) const {
marci@1013	1479	Parent1::graph->firstIn(static_cast<Graph1Edge>(&i), n);
marci@1013	1480	i.backward=false;
marci@1013	1481	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	1482	graph2->firstIn(static_cast<Graph2Edge>(&i), n);
marci@1013	1483	i.backward=true;
marci@1013	1484	}
marci@1013	1485	}
marci@1013	1486	void firstOut(Edge& i, const Node& n) const {
marci@1013	1487	Parent1::graph->firstOut(static_cast<Graph1Edge>(&i), n);
marci@1013	1488	i.backward=false;
marci@1013	1489	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	1490	graph2->firstOut(static_cast<Graph2Edge>(&i), n);
marci@1013	1491	i.backward=true;
marci@1013	1492	}
marci@1013	1493	}
marci@1013	1494
marci@1013	1495	using Parent1::next;
marci@1013	1496	void next(Edge& i) const {
marci@1013	1497	if (!(i.backward)) {
marci@1013	1498	Parent1::graph->next(static_cast<Graph1Edge>(&i));
marci@1013	1499	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	1500	graph2->first(static_cast<Graph2Edge>(&i));
marci@1013	1501	i.backward=true;
marci@1013	1502	}
marci@1013	1503	} else {
marci@1013	1504	graph2->next(static_cast<Graph2Edge>(&i));
marci@1013	1505	}
marci@1013	1506	}
marci@1013	1507	void nextIn(Edge& i) const {
marci@1013	1508	if (!(i.backward)) {
marci@1013	1509	Parent1::graph->nextIn(static_cast<Graph1Edge>(&i));
marci@1013	1510	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	1511	graph2->first(static_cast<Graph2Edge>(&i));
marci@1013	1512	i.backward=true;
marci@1013	1513	}
marci@1013	1514	} else {
marci@1013	1515	graph2->nextIn(static_cast<Graph2Edge>(&i));
marci@1013	1516	}
marci@1013	1517	}
marci@1013	1518	void nextOut(Edge& i) const {
marci@1013	1519	if (!(i.backward)) {
marci@1013	1520	Parent1::graph->nextOut(static_cast<Graph1Edge>(&i));
marci@1013	1521	if (static_cast<Graph1Edge>(&i)==INVALID) {
marci@1013	1522	graph2->first(static_cast<Graph2Edge>(&i));
marci@1013	1523	i.backward=true;
marci@1013	1524	}
marci@1013	1525	} else {
marci@1013	1526	graph2->nextOut(static_cast<Graph2Edge>(&i));
marci@1013	1527	}
marci@1013	1528	}
marci@1013	1529
marci@1013	1530	Node source(const Edge& i) const {
marci@1013	1531	if (!(i.backward)) {
marci@1013	1532	return Parent1::graph->source(i);
marci@1013	1533	} else {
marci@1013	1534	return graph2->source(i);
marci@1013	1535	}
marci@1013	1536	}
marci@1013	1537
marci@1013	1538	Node target(const Edge& i) const {
marci@1013	1539	if (!(i.backward)) {
marci@1013	1540	return Parent1::graph->target(i);
marci@1013	1541	} else {
marci@1013	1542	return graph2->target(i);
marci@1013	1543	}
marci@1013	1544	}
marci@1013	1545
marci@1013	1546	int id(const Node& n) const {
marci@1013	1547	return Parent1::id(n);
marci@1013	1548	};
marci@1013	1549	int id(const Edge& n) const {
marci@1013	1550	if (!n.backward)
marci@1013	1551	return this->Parent1::graph->id(n);
marci@1013	1552	else
marci@1013	1553	return this->graph2->id(n);
marci@1013	1554	}
marci@1013	1555
marci@1013	1556	template <typename _Value>
marci@1013	1557	class EdgeMap {
marci@1013	1558	protected:
marci@1013	1559	typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
marci@1013	1560	typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
marci@1013	1561	ParentMap1 forward_map;
marci@1013	1562	ParentMap2 backward_map;
marci@1013	1563	public:
marci@1013	1564	typedef _Value Value;
marci@1013	1565	typedef Edge Key;
marci@1013	1566	EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) :
marci@1013	1567	forward_map(*(gw.Parent1::graph)),
marci@1013	1568	backward_map(*(gw.graph2)) { }
marci@1013	1569	EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw,
marci@1013	1570	const _Value& value) :
marci@1013	1571	forward_map(*(gw.Parent1::graph), value),
marci@1013	1572	backward_map(*(gw.graph2), value) { }
marci@1013	1573	_Value operator[](const Edge& n) const {
marci@1013	1574	if (!n.backward)
marci@1013	1575	return forward_map[n];
marci@1013	1576	else
marci@1013	1577	return backward_map[n];
marci@1013	1578	}
marci@1013	1579	void set(const Edge& n, const _Value& value) {
marci@1013	1580	if (!n.backward)
marci@1013	1581	forward_map.set(n, value);
marci@1013	1582	else
marci@1013	1583	backward_map.set(n, value);
marci@1013	1584	}
marci@1013	1585	// using ParentMap1::operator[];
marci@1013	1586	// using ParentMap2::operator[];
marci@1013	1587	};
marci@1013	1588
marci@1013	1589	};
marci@1013	1590
marci@1013	1591
marci@1013	1592	/*! A graph wrapper class
marci@1013	1593	for merging two graphs (of type _Graph1 and _Graph2)
marci@1013	1594	with the same node-set
marci@1013	1595	(specially on the node-set of Graph1)
marci@1013	1596	into one graph.
marci@1013	1597	In an other point of view, _Graph1 is extended with
marci@1013	1598	the edge-set of _Graph2.
marci@1013	1599	*/
marci@1013	1600	template <typename _Graph1, typename _Graph2>
marci@1013	1601	class AugmentingGraphWrapper : public
marci@1013	1602	IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
marci@1013	1603	public:
marci@1013	1604	typedef
marci@1013	1605	IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
marci@1013	1606	Parent;
marci@1013	1607	typedef _Graph1 Graph1;
marci@1013	1608	typedef _Graph2 Graph2;
marci@1013	1609	protected:
marci@1013	1610	AugmentingGraphWrapper() { }
marci@1013	1611	public:
marci@1013	1612	AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
marci@1013	1613	setGraph(_graph1);
marci@1013	1614	setGraph2(_graph2);
marci@1013	1615	}
marci@1013	1616	};
marci@1013	1617
alpar@921	1618	} //namespace lemon
marci@915	1619
alpar@921	1620	#endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H

author	ladanyi
	Mon, 29 Nov 2004 16:11:51 +0000
changeset 1024	28e117c5bddf
parent 1013	b3bdd856faf4
child 1025	3b1ad8bc21da
permissions	-rw-r--r--