lemon-0.x: src/work/marci/graph_wrapper.h@7ac0d4e8a31c (annotated)

marci@174	1	// -- c++ --
marci@259	2	#ifndef HUGO_GRAPH_WRAPPER_H
marci@259	3	#define HUGO_GRAPH_WRAPPER_H
marci@76	4
marci@174	5	#include <invalid.h>
marci@174	6
alpar@105	7	namespace hugo {
marci@76	8
marci@303	9	template<typename Graph>
marci@303	10	class GraphWrapper {
marci@212	11	protected:
marci@303	12	Graph* graph;
marci@212	13
marci@212	14	public:
marci@311	15	typedef Graph BaseGraph;
marci@303	16	typedef Graph ParentGraph;
marci@212	17
marci@303	18	// GraphWrapper() : graph(0) { }
marci@303	19	GraphWrapper(Graph& _graph) : graph(&_graph) { }
marci@303	20	// void setGraph(Graph& _graph) { graph=&_graph; }
marci@303	21	// Graph& getGraph() const { return *graph; }
marci@303	22
marci@317	23	// typedef typename Graph::Node Node;
marci@317	24	class Node : public Graph::Node {
marci@317	25	friend class GraphWrapper<Graph>;
marci@265	26	public:
marci@317	27	Node() { }
marci@317	28	Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
marci@317	29	Node(const Invalid& i) : Graph::Node(i) { }
marci@317	30	};
marci@317	31	class NodeIt {
marci@317	32	friend class GraphWrapper<Graph>;
marci@317	33	typename Graph::NodeIt n;
marci@317	34	public:
marci@265	35	NodeIt() { }
marci@317	36	NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
marci@317	37	NodeIt(const Invalid& i) : n(i) { }
marci@317	38	NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
marci@317	39	operator Node() const { return Node(typename Graph::Node(n)); }
marci@265	40	};
marci@317	41	// typedef typename Graph::Edge Edge;
marci@317	42	class Edge : public Graph::Edge {
marci@317	43	friend class GraphWrapper<Graph>;
marci@317	44	public:
marci@317	45	Edge() { }
marci@317	46	Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
marci@317	47	Edge(const Invalid& i) : Graph::Edge(i) { }
marci@317	48	};
marci@317	49	class OutEdgeIt {
marci@317	50	friend class GraphWrapper<Graph>;
marci@317	51	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	52	typename Graph::OutEdgeIt e;
marci@265	53	public:
marci@265	54	OutEdgeIt() { }
marci@317	55	OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
marci@317	56	OutEdgeIt(const Invalid& i) : e(i) { }
marci@317	57	OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
marci@317	58	e(*(_G.graph), typename Graph::Node(_n)) { }
marci@317	59	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@265	60	};
marci@317	61	class InEdgeIt {
marci@317	62	friend class GraphWrapper<Graph>;
marci@317	63	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	64	typename Graph::InEdgeIt e;
marci@265	65	public:
marci@265	66	InEdgeIt() { }
marci@317	67	InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
marci@317	68	InEdgeIt(const Invalid& i) : e(i) { }
marci@317	69	InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
marci@317	70	e(*(_G.graph), typename Graph::Node(_n)) { }
marci@317	71	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@265	72	};
marci@303	73	//typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@317	74	class EdgeIt {
marci@317	75	friend class GraphWrapper<Graph>;
marci@317	76	// typedef typename Graph::EdgeIt GraphEdgeIt;
marci@317	77	typename Graph::EdgeIt e;
marci@265	78	public:
marci@265	79	EdgeIt() { }
marci@317	80	EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
marci@317	81	EdgeIt(const Invalid& i) : e(i) { }
marci@317	82	EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
marci@317	83	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@265	84	};
marci@303	85
marci@303	86	NodeIt& first(NodeIt& i) const {
marci@317	87	i=NodeIt(*this); return i;
marci@265	88	}
marci@303	89	OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	90	i=OutEdgeIt(*this, p); return i;
marci@303	91	}
marci@303	92	InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	93	i=InEdgeIt(*this, p); return i;
marci@303	94	}
marci@311	95	EdgeIt& first(EdgeIt& i) const {
marci@317	96	i=EdgeIt(*this); return i;
marci@311	97	}
marci@312	98	// template<typename I> I& first(I& i) const {
marci@312	99	// i=I(*this);
marci@312	100	// return i;
marci@312	101	// }
marci@303	102	// template<typename I, typename P> I& first(I& i, const P& p) const {
marci@303	103	// i=I(*this, p);
marci@303	104	// return i;
marci@303	105	// }
marci@212	106
marci@317	107	NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
marci@317	108	OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
marci@317	109	InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
marci@317	110	EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
marci@312	111	// template<typename I> I& next(I &i) const { graph->next(i); return i; }
marci@212	112	template< typename It > It first() const {
marci@212	113	It e; this->first(e); return e; }
marci@212	114
marci@212	115	template< typename It > It first(const Node& v) const {
marci@212	116	It e; this->first(e, v); return e; }
marci@212	117
marci@317	118	Node head(const Edge& e) const {
marci@317	119	return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
marci@317	120	Node tail(const Edge& e) const {
marci@317	121	return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
marci@212	122
marci@317	123	bool valid(const Node& n) const {
marci@317	124	return graph->valid(static_cast<typename Graph::Node>(n)); }
marci@317	125	bool valid(const Edge& e) const {
marci@317	126	return graph->valid(static_cast<typename Graph::Edge>(e)); }
marci@317	127	// template<typename I> bool valid(const I& i) const {
marci@317	128	// return graph->valid(i); }
marci@212	129
marci@212	130	//template<typename I> void setInvalid(const I &i);
marci@212	131	//{ return graph->setInvalid(i); }
marci@212	132
marci@303	133	int nodeNum() const { return graph->nodeNum(); }
marci@303	134	int edgeNum() const { return graph->edgeNum(); }
marci@212	135
marci@317	136	Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@317	137	Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@317	138	Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@317	139	Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@317	140	// template<typename I> Node aNode(const I& e) const {
marci@317	141	// return Node(graph->aNode(e.e)); }
marci@317	142	// template<typename I> Node bNode(const I& e) const {
marci@317	143	// return Node(graph->bNode(e.e)); }
marci@212	144
marci@317	145	Node addNode() const { return Node(graph->addNode()); }
marci@212	146	Edge addEdge(const Node& tail, const Node& head) const {
marci@317	147	return Edge(graph->addEdge(tail, head)); }
marci@317	148
marci@317	149	void erase(const Node& i) const { graph->erase(i); }
marci@317	150	void erase(const Edge& i) const { graph->erase(i); }
marci@317	151	// template<typename I> void erase(const I& i) const { graph->erase(i); }
marci@212	152
marci@303	153	void clear() const { graph->clear(); }
marci@212	154
marci@303	155	template<typename T> class NodeMap : public Graph::NodeMap<T> {
marci@212	156	public:
marci@303	157	NodeMap(const GraphWrapper<Graph>& _G) :
marci@303	158	Graph::NodeMap<T>(*(_G.graph)) { }
marci@303	159	NodeMap(const GraphWrapper<Graph>& _G, T a) :
marci@303	160	Graph::NodeMap<T>(*(_G.graph), a) { }
marci@212	161	};
marci@212	162
marci@303	163	template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
marci@212	164	public:
marci@303	165	EdgeMap(const GraphWrapper<Graph>& _G) :
marci@303	166	Graph::EdgeMap<T>(*(_G.graph)) { }
marci@303	167	EdgeMap(const GraphWrapper<Graph>& _G, T a) :
marci@303	168	Graph::EdgeMap<T>(*(_G.graph), a) { }
marci@212	169	};
marci@212	170	};
marci@212	171
marci@303	172
marci@230	173	// template<typename Graph>
marci@230	174	// class RevGraphWrapper
marci@230	175	// {
marci@230	176	// protected:
marci@230	177	// Graph* graph;
marci@230	178
marci@230	179	// public:
marci@303	180	// typedef Graph ParentGraph;
marci@230	181
marci@230	182	// typedef typename Graph::Node Node;
marci@230	183	// typedef typename Graph::NodeIt NodeIt;
marci@230	184
marci@230	185	// typedef typename Graph::Edge Edge;
marci@230	186	// typedef typename Graph::OutEdgeIt InEdgeIt;
marci@230	187	// typedef typename Graph::InEdgeIt OutEdgeIt;
marci@230	188	// //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@230	189	// typedef typename Graph::EdgeIt EdgeIt;
marci@230	190
marci@230	191	// //RevGraphWrapper() : graph(0) { }
marci@230	192	// RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
marci@230	193
marci@230	194	// void setGraph(Graph& _graph) { graph = &_graph; }
marci@230	195	// Graph& getGraph() const { return (*graph); }
marci@230	196
marci@230	197	// template<typename I> I& first(I& i) const { return graph->first(i); }
marci@230	198	// template<typename I, typename P> I& first(I& i, const P& p) const {
marci@230	199	// return graph->first(i, p); }
marci@230	200
marci@230	201	// template<typename I> I& next(I &i) const { return graph->next(i); }
marci@230	202
marci@230	203	// template< typename It > It first() const {
marci@230	204	// It e; first(e); return e; }
marci@230	205
marci@230	206	// template< typename It > It first(const Node& v) const {
marci@230	207	// It e; first(e, v); return e; }
marci@230	208
marci@230	209	// Node head(const Edge& e) const { return graph->tail(e); }
marci@230	210	// Node tail(const Edge& e) const { return graph->head(e); }
marci@230	211
marci@230	212	// template<typename I> bool valid(const I& i) const
marci@230	213	// { return graph->valid(i); }
marci@230	214
marci@230	215	// //template<typename I> void setInvalid(const I &i);
marci@230	216	// //{ return graph->setInvalid(i); }
marci@230	217
marci@230	218	// template<typename I> Node aNode(const I& e) const {
marci@230	219	// return graph->aNode(e); }
marci@230	220	// template<typename I> Node bNode(const I& e) const {
marci@230	221	// return graph->bNode(e); }
marci@230	222
marci@230	223	// Node addNode() const { return graph->addNode(); }
marci@230	224	// Edge addEdge(const Node& tail, const Node& head) const {
marci@230	225	// return graph->addEdge(tail, head); }
marci@230	226
marci@230	227	// int nodeNum() const { return graph->nodeNum(); }
marci@230	228	// int edgeNum() const { return graph->edgeNum(); }
marci@230	229
marci@230	230	// template<typename I> void erase(const I& i) const { graph->erase(i); }
marci@230	231
marci@230	232	// void clear() const { graph->clear(); }
marci@230	233
marci@230	234	// template<typename T> class NodeMap : public Graph::NodeMap<T> {
marci@230	235	// public:
marci@230	236	// NodeMap(const RevGraphWrapper<Graph>& _G) :
marci@230	237	// Graph::NodeMap<T>(_G.getGraph()) { }
marci@230	238	// NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
marci@230	239	// Graph::NodeMap<T>(_G.getGraph(), a) { }
marci@230	240	// };
marci@230	241
marci@230	242	// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
marci@230	243	// public:
marci@230	244	// EdgeMap(const RevGraphWrapper<Graph>& _G) :
marci@230	245	// Graph::EdgeMap<T>(_G.getGraph()) { }
marci@230	246	// EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
marci@230	247	// Graph::EdgeMap<T>(_G.getGraph(), a) { }
marci@230	248	// };
marci@230	249	// };
marci@230	250
marci@235	251
marci@303	252	template<typename Graph>
marci@303	253	class RevGraphWrapper : public GraphWrapper<Graph> {
marci@230	254	public:
marci@303	255	typedef typename GraphWrapper<Graph>::Node Node;
marci@303	256	typedef typename GraphWrapper<Graph>::Edge Edge;
marci@279	257	//FIXME
marci@303	258	//If Graph::OutEdgeIt is not defined
marci@279	259	//and we do not want to use RevGraphWrapper::InEdgeIt,
marci@279	260	//this won't work, because of typedef
marci@279	261	//OR
marci@279	262	//graphs have to define their non-existing iterators to void
marci@279	263	//Unfortunately all the typedefs are instantiated in templates,
marci@279	264	//unlike other stuff
marci@303	265	typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
marci@303	266	typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
marci@237	267
marci@303	268	// RevGraphWrapper() : GraphWrapper<Graph>() { }
marci@303	269	RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
marci@238	270
marci@237	271	Node head(const Edge& e) const
marci@303	272	{ return GraphWrapper<Graph>::tail(e); }
marci@237	273	Node tail(const Edge& e) const
marci@303	274	{ return GraphWrapper<Graph>::head(e); }
marci@76	275	};
marci@76	276
marci@263	277	//Subgraph on the same node-set and partial edge-set
marci@311	278	template<typename Graph, typename NodeFilterMap,
marci@311	279	typename EdgeFilterMap>
marci@303	280	class SubGraphWrapper : public GraphWrapper<Graph> {
marci@263	281	protected:
marci@311	282	NodeFilterMap* node_filter_map;
marci@311	283	EdgeFilterMap* edge_filter_map;
marci@263	284	public:
marci@311	285	// SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
marci@311	286	SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
marci@311	287	EdgeFilterMap& _edge_filter_map) :
marci@311	288	GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
marci@311	289	edge_filter_map(&_edge_filter_map) { }
marci@263	290
marci@317	291	typedef typename GraphWrapper<Graph>::Node Node;
marci@317	292	class NodeIt {
marci@317	293	friend class GraphWrapper<Graph>;
marci@317	294	friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@317	295	typename Graph::NodeIt n;
marci@317	296	public:
marci@311	297	NodeIt() { }
marci@317	298	NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
marci@317	299	NodeIt(const Invalid& i) : n(i) { }
marci@311	300	NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
marci@317	301	n(*(_G.graph)) {
marci@317	302	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
marci@317	303	_G.graph->next(n);
marci@311	304	}
marci@317	305	operator Node() const { return Node(typename Graph::Node(n)); }
marci@311	306	};
marci@317	307	// class NodeIt : public Graph::NodeIt {
marci@317	308	// // typedef typename Graph::NodeIt GraphNodeIt;
marci@317	309	// public:
marci@317	310	// NodeIt() { }
marci@317	311	// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
marci@317	312	// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
marci@317	313	// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
marci@317	314	// Graph::NodeIt(*(_G.graph)) {
marci@317	315	// while (_G.graph->valid((this)/.GraphNodeIt*/) &&
marci@317	316	// !((_G.node_filter_map))[(this)/.GraphNodeIt/])
marci@317	317	// _G.graph->next((this)/.GraphNodeIt*/);
marci@317	318	// }
marci@317	319	// };
marci@317	320	typedef typename GraphWrapper<Graph>::Edge Edge;
marci@317	321	class OutEdgeIt {
marci@317	322	friend class GraphWrapper<Graph>;
marci@317	323	friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@311	324	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	325	typename Graph::OutEdgeIt e;
marci@311	326	public:
marci@311	327	OutEdgeIt() { }
marci@317	328	OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
marci@317	329	OutEdgeIt(const Invalid& i) : e(i) { }
marci@317	330	OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
marci@317	331	const Node& _n) :
marci@317	332	e(*(_G.graph), typename Graph::Node(_n)) {
marci@317	333	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
marci@317	334	_G.graph->next(e);
marci@311	335	}
marci@317	336	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@311	337	};
marci@317	338	class InEdgeIt {
marci@317	339	friend class GraphWrapper<Graph>;
marci@317	340	friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@311	341	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	342	typename Graph::InEdgeIt e;
marci@311	343	public:
marci@311	344	InEdgeIt() { }
marci@317	345	InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
marci@317	346	InEdgeIt(const Invalid& i) : e(i) { }
marci@311	347	InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
marci@317	348	const Node& _n) :
marci@317	349	e(*(_G.graph), typename Graph::Node(_n)) {
marci@317	350	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
marci@317	351	_G.graph->next(e);
marci@311	352	}
marci@317	353	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@311	354	};
marci@317	355	//typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@317	356	class EdgeIt {
marci@317	357	friend class GraphWrapper<Graph>;
marci@317	358	friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@311	359	// typedef typename Graph::EdgeIt GraphEdgeIt;
marci@317	360	typename Graph::EdgeIt e;
marci@311	361	public:
marci@311	362	EdgeIt() { }
marci@317	363	EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
marci@317	364	EdgeIt(const Invalid& i) : e(i) { }
marci@311	365	EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
marci@317	366	e(*(_G.graph)) {
marci@317	367	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
marci@317	368	_G.graph->next(e);
marci@311	369	}
marci@317	370	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@311	371	};
marci@317	372	// operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@317	373	// };
marci@317	374	// class OutEdgeIt : public Graph::OutEdgeIt {
marci@317	375	// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	376	// public:
marci@317	377	// OutEdgeIt() { }
marci@317	378	// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
marci@317	379	// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
marci@317	380	// OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
marci@317	381	// _G, const Node& n) :
marci@317	382	// Graph::OutEdgeIt(*(_G.graph), n) {
marci@317	383	// while (_G.graph->valid((this)/.GraphOutEdgeIt*/) &&
marci@317	384	// !((_G.edge_filter_map))[(this)/.GraphOutEdgeIt/])
marci@317	385	// _G.graph->next((this)/.GraphOutEdgeIt*/);
marci@317	386	// }
marci@317	387	// };
marci@317	388	// class InEdgeIt : public Graph::InEdgeIt {
marci@317	389	// // typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	390	// public:
marci@317	391	// InEdgeIt() { }
marci@317	392	// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
marci@317	393	// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
marci@317	394	// InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
marci@317	395	// const Node& n) :
marci@317	396	// Graph::InEdgeIt(*(_G.graph), n) {
marci@317	397	// while (_G.graph->valid((this)/.GraphInEdgeIt*/) &&
marci@317	398	// !((_G.edge_filter_map))[(this)/.GraphInEdgeIt/])
marci@317	399	// _G.graph->next((this)/.GraphInEdgeIt*/);
marci@317	400	// }
marci@317	401	// };
marci@317	402	// // //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@317	403	// class EdgeIt : public Graph::EdgeIt {
marci@317	404	// // typedef typename Graph::EdgeIt GraphEdgeIt;
marci@317	405	// public:
marci@317	406	// EdgeIt() { }
marci@317	407	// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
marci@317	408	// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
marci@317	409	// EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
marci@317	410	// Graph::EdgeIt(*(_G.graph)) {
marci@317	411	// while (_G.graph->valid((this)/.GraphEdgeIt*/) &&
marci@317	412	// !((_G.edge_filter_map))[(this)/.GraphEdgeIt/])
marci@317	413	// _G.graph->next((this)/.GraphEdgeIt*/);
marci@317	414	// }
marci@317	415	// };
marci@311	416
marci@317	417
marci@317	418	NodeIt& first(NodeIt& i) const {
marci@317	419	i=NodeIt(*this); return i;
marci@263	420	}
marci@317	421	OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	422	i=OutEdgeIt(*this, p); return i;
marci@311	423	}
marci@317	424	InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	425	i=InEdgeIt(*this, p); return i;
marci@311	426	}
marci@317	427	EdgeIt& first(EdgeIt& i) const {
marci@317	428	i=EdgeIt(*this); return i;
marci@263	429	}
marci@263	430
marci@311	431	// template<typename I> I& first(I& i) const {
marci@311	432	// graph->first(i);
marci@311	433	// //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
marci@311	434	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@311	435	// return i;
marci@311	436	// }
marci@311	437	// template<typename I, typename P> I& first(I& i, const P& p) const {
marci@311	438	// graph->first(i, p);
marci@311	439	// // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
marci@311	440	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@311	441	// return i;
marci@311	442	// }
marci@311	443
marci@311	444	NodeIt& next(NodeIt& i) const {
marci@317	445	graph->next(i.n);
marci@317	446	while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
marci@311	447	return i;
marci@311	448	}
marci@311	449	OutEdgeIt& next(OutEdgeIt& i) const {
marci@317	450	graph->next(i.e);
marci@317	451	while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
marci@311	452	return i;
marci@311	453	}
marci@311	454	InEdgeIt& next(InEdgeIt& i) const {
marci@317	455	graph->next(i.e);
marci@317	456	while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
marci@311	457	return i;
marci@311	458	}
marci@311	459	EdgeIt& next(EdgeIt& i) const {
marci@317	460	graph->next(i.e);
marci@317	461	while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
marci@311	462	return i;
marci@311	463	}
marci@311	464
marci@311	465	// template<typename I> I& next(I &i) const {
marci@311	466	// graph->next(i);
marci@311	467	// // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
marci@311	468	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@311	469	// return i;
marci@323	470	// }
marci@323	471
marci@323	472	Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@323	473	Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@323	474	Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@323	475	Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@323	476
marci@323	477	void hide(const Node& n) const { node_filter_map->set(n, false); }
marci@323	478	void hide(const Edge& e) const { edge_filter_map->set(e, false); }
marci@323	479
marci@323	480	void unHide(const Node& n) const { node_filter_map->set(n, true); }
marci@323	481	void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
marci@323	482
marci@323	483	bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
marci@323	484	bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
marci@323	485
marci@263	486	template< typename It > It first() const {
marci@263	487	It e; this->first(e); return e; }
marci@263	488
marci@263	489	template< typename It > It first(const Node& v) const {
marci@263	490	It e; this->first(e, v); return e; }
marci@263	491	};
marci@155	492
marci@317	493	// //Subgraph on the same node-set and partial edge-set
marci@317	494	// template<typename Graph, typename NodeFilterMap,
marci@317	495	// typename EdgeFilterMap>
marci@317	496	// class SubGraphWrapper : public GraphWrapper<Graph> {
marci@317	497	// protected:
marci@317	498	// NodeFilterMap* node_filter_map;
marci@317	499	// EdgeFilterMap* edge_filter_map;
marci@317	500	// public:
marci@317	501	// // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
marci@317	502	// SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
marci@317	503	// EdgeFilterMap& _edge_filter_map) :
marci@317	504	// GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
marci@317	505	// edge_filter_map(&_edge_filter_map) { }
marci@317	506
marci@317	507
marci@317	508	// typedef typename Graph::Node Node;
marci@317	509	// class NodeIt : public Graph::NodeIt {
marci@317	510	// // typedef typename Graph::NodeIt GraphNodeIt;
marci@317	511	// public:
marci@317	512	// NodeIt() { }
marci@317	513	// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
marci@317	514	// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
marci@317	515	// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
marci@317	516	// Graph::NodeIt(*(_G.graph)) {
marci@317	517	// while (_G.graph->valid((this)/.GraphNodeIt*/) &&
marci@317	518	// !((_G.node_filter_map))[(this)/.GraphNodeIt/])
marci@317	519	// _G.graph->next((this)/.GraphNodeIt*/);
marci@317	520	// }
marci@317	521	// };
marci@317	522	// typedef typename Graph::Edge Edge;
marci@317	523	// class OutEdgeIt : public Graph::OutEdgeIt {
marci@317	524	// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	525	// public:
marci@317	526	// OutEdgeIt() { }
marci@317	527	// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
marci@317	528	// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
marci@317	529	// OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
marci@317	530	// _G, const Node& n) :
marci@317	531	// Graph::OutEdgeIt(*(_G.graph), n) {
marci@317	532	// while (_G.graph->valid((this)/.GraphOutEdgeIt*/) &&
marci@317	533	// !((_G.edge_filter_map))[(this)/.GraphOutEdgeIt/])
marci@317	534	// _G.graph->next((this)/.GraphOutEdgeIt*/);
marci@317	535	// }
marci@317	536	// };
marci@317	537	// class InEdgeIt : public Graph::InEdgeIt {
marci@317	538	// // typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	539	// public:
marci@317	540	// InEdgeIt() { }
marci@317	541	// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
marci@317	542	// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
marci@317	543	// InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
marci@317	544	// const Node& n) :
marci@317	545	// Graph::InEdgeIt(*(_G.graph), n) {
marci@317	546	// while (_G.graph->valid((this)/.GraphInEdgeIt*/) &&
marci@317	547	// !((_G.edge_filter_map))[(this)/.GraphInEdgeIt/])
marci@317	548	// _G.graph->next((this)/.GraphInEdgeIt*/);
marci@317	549	// }
marci@317	550	// };
marci@317	551	// // //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@317	552	// class EdgeIt : public Graph::EdgeIt {
marci@317	553	// // typedef typename Graph::EdgeIt GraphEdgeIt;
marci@317	554	// public:
marci@317	555	// EdgeIt() { }
marci@317	556	// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
marci@317	557	// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
marci@317	558	// EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
marci@317	559	// Graph::EdgeIt(*(_G.graph)) {
marci@317	560	// while (_G.graph->valid((this)/.GraphEdgeIt*/) &&
marci@317	561	// !((_G.edge_filter_map))[(this)/.GraphEdgeIt/])
marci@317	562	// _G.graph->next((this)/.GraphEdgeIt*/);
marci@317	563	// }
marci@317	564	// };
marci@317	565
marci@317	566	// NodeIt& first(NodeIt& i) const {
marci@317	567	// i=NodeIt(*this);
marci@317	568	// return i;
marci@317	569	// }
marci@317	570	// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
marci@317	571	// i=OutEdgeIt(*this, n);
marci@317	572	// return i;
marci@317	573	// }
marci@317	574	// InEdgeIt& first(InEdgeIt& i, const Node& n) const {
marci@317	575	// i=InEdgeIt(*this, n);
marci@317	576	// return i;
marci@317	577	// }
marci@317	578	// EdgeIt& first(EdgeIt& i) const {
marci@317	579	// i=EdgeIt(*this);
marci@317	580	// return i;
marci@317	581	// }
marci@317	582
marci@317	583	// // template<typename I> I& first(I& i) const {
marci@317	584	// // graph->first(i);
marci@317	585	// // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
marci@317	586	// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	587	// // return i;
marci@317	588	// // }
marci@317	589	// // template<typename I, typename P> I& first(I& i, const P& p) const {
marci@317	590	// // graph->first(i, p);
marci@317	591	// // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
marci@317	592	// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	593	// // return i;
marci@317	594	// // }
marci@317	595
marci@317	596	// NodeIt& next(NodeIt& i) const {
marci@317	597	// graph->next(i);
marci@317	598	// while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
marci@317	599	// return i;
marci@317	600	// }
marci@317	601	// OutEdgeIt& next(OutEdgeIt& i) const {
marci@317	602	// graph->next(i);
marci@317	603	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	604	// return i;
marci@317	605	// }
marci@317	606	// InEdgeIt& next(InEdgeIt& i) const {
marci@317	607	// graph->next(i);
marci@317	608	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	609	// return i;
marci@317	610	// }
marci@317	611	// EdgeIt& next(EdgeIt& i) const {
marci@317	612	// graph->next(i);
marci@317	613	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	614	// return i;
marci@317	615	// }
marci@317	616
marci@317	617	// // template<typename I> I& next(I &i) const {
marci@317	618	// // graph->next(i);
marci@317	619	// // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
marci@317	620	// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	621	// // return i;
marci@317	622	// // }
marci@317	623
marci@317	624	// template< typename It > It first() const {
marci@317	625	// It e; this->first(e); return e; }
marci@317	626
marci@317	627	// template< typename It > It first(const Node& v) const {
marci@317	628	// It e; this->first(e, v); return e; }
marci@317	629	// };
marci@317	630
marci@303	631	template<typename Graph>
marci@303	632	class UndirGraphWrapper : public GraphWrapper<Graph> {
marci@317	633	// protected:
marci@317	634	// typedef typename Graph::Edge GraphEdge;
marci@317	635	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	636	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@303	637	public:
marci@303	638	typedef typename GraphWrapper<Graph>::Node Node;
marci@303	639	typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@317	640	typedef typename GraphWrapper<Graph>::Edge Edge;
marci@317	641	typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
marci@236	642
marci@303	643	// UndirGraphWrapper() : GraphWrapper<Graph>() { }
marci@303	644	UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
marci@158	645
marci@317	646
marci@317	647	// class Edge {
marci@317	648	// friend class UndirGraphWrapper<Graph>;
marci@317	649	// protected:
marci@317	650	// bool out_or_in; //true iff out
marci@317	651	// GraphOutEdgeIt out;
marci@317	652	// GraphInEdgeIt in;
marci@317	653	// public:
marci@317	654	// Edge() : out_or_in(), out(), in() { }
marci@317	655	// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
marci@317	656	// operator GraphEdge() const {
marci@317	657	// if (out_or_in) return(out); else return(in);
marci@317	658	// }
marci@317	659	// //FIXME
marci@317	660	// //2 edges are equal if they "refer" to the same physical edge
marci@317	661	// //is it good?
marci@317	662	// friend bool operator==(const Edge& u, const Edge& v) {
marci@317	663	// if (v.out_or_in)
marci@317	664	// if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
marci@317	665	// //return (u.out_or_in && u.out==v.out);
marci@317	666	// else
marci@317	667	// if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
marci@317	668	// //return (!u.out_or_in && u.in==v.in);
marci@317	669	// }
marci@317	670	// friend bool operator!=(const Edge& u, const Edge& v) {
marci@317	671	// if (v.out_or_in)
marci@317	672	// if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
marci@317	673	// //return (!u.out_or_in \|\| u.out!=v.out);
marci@317	674	// else
marci@317	675	// if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
marci@317	676	// //return (u.out_or_in \|\| u.in!=v.in);
marci@317	677	// }
marci@317	678	// };
marci@317	679
marci@317	680	class OutEdgeIt {
marci@303	681	friend class UndirGraphWrapper<Graph>;
marci@158	682	bool out_or_in; //true iff out
marci@317	683	typename Graph::OutEdgeIt out;
marci@317	684	typename Graph::InEdgeIt in;
marci@158	685	public:
marci@317	686	OutEdgeIt() { }
marci@317	687	OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@317	688	OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
marci@317	689	out_or_in=true; _G.graph->first(out, _n);
marci@317	690	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
marci@174	691	}
marci@317	692	operator Edge() const {
marci@317	693	if (out_or_in) return Edge(out); else return Edge(in);
marci@158	694	}
marci@158	695	};
marci@317	696	// class OutEdgeIt : public Edge {
marci@317	697	// friend class UndirGraphWrapper<Graph>;
marci@317	698	// public:
marci@317	699	// OutEdgeIt() : Edge() { }
marci@317	700	// OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@317	701	// OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
marci@317	702	// : Edge() {
marci@317	703	// out_or_in=true; _G.graph->first(out, n);
marci@317	704	// if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
marci@317	705	// }
marci@317	706	// };
marci@158	707
marci@317	708	//FIXME InEdgeIt
marci@238	709	typedef OutEdgeIt InEdgeIt;
marci@238	710
marci@317	711	// class EdgeIt : public Edge {
marci@317	712	// friend class UndirGraphWrapper<Graph>;
marci@317	713	// protected:
marci@317	714	// NodeIt v;
marci@317	715	// public:
marci@317	716	// EdgeIt() : Edge() { }
marci@317	717	// EdgeIt(const Invalid& i) : Edge(i) { }
marci@317	718	// EdgeIt(const UndirGraphWrapper<Graph>& _G)
marci@317	719	// : Edge() {
marci@317	720	// out_or_in=true;
marci@317	721	// //Node v;
marci@317	722	// _G.first(v);
marci@317	723	// if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
marci@317	724	// while (_G.valid(v) && !_G.graph->valid(out)) {
marci@317	725	// _G.graph->next(v);
marci@317	726	// if (_G.valid(v)) _G.graph->first(out);
marci@317	727	// }
marci@317	728	// }
marci@317	729	// };
marci@238	730
marci@317	731	NodeIt& first(NodeIt& i) const {
marci@317	732	i=NodeIt(*this); return i;
marci@158	733	}
marci@317	734	OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	735	i=OutEdgeIt(*this, p); return i;
marci@317	736	}
marci@317	737	//FIXME
marci@317	738	// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	739	// i=InEdgeIt(*this, p); return i;
marci@317	740	// }
marci@317	741	EdgeIt& first(EdgeIt& i) const {
marci@317	742	i=EdgeIt(*this); return i;
marci@238	743	}
marci@238	744
marci@303	745	template<typename I> I& first(I& i) const { graph->first(i); return i; }
marci@238	746	template<typename I, typename P> I& first(I& i, const P& p) const {
marci@303	747	graph->first(i, p); return i; }
marci@238	748
marci@317	749	NodeIt& next(NodeIt& n) const {
marci@317	750	GraphWrapper<Graph>::next(n);
marci@317	751	return n;
marci@317	752	}
marci@158	753	OutEdgeIt& next(OutEdgeIt& e) const {
marci@158	754	if (e.out_or_in) {
marci@317	755	typename Graph::Node n=graph->tail(e.out);
marci@303	756	graph->next(e.out);
marci@303	757	if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
marci@158	758	} else {
marci@303	759	graph->next(e.in);
marci@158	760	}
marci@158	761	return e;
marci@158	762	}
marci@317	763	//FIXME InEdgeIt
marci@238	764	EdgeIt& next(EdgeIt& e) const {
marci@317	765	GraphWrapper<Graph>::next(n);
marci@317	766	// graph->next(e.e);
marci@238	767	return e;
marci@238	768	}
marci@158	769
marci@317	770	// template<typename I> I& next(I &i) const { graph->next(i); return i; }
marci@158	771	template< typename It > It first() const {
marci@303	772	It e; this->first(e); return e; }
marci@158	773
marci@174	774	template< typename It > It first(const Node& v) const {
marci@303	775	It e; this->first(e, v); return e; }
marci@158	776
marci@238	777	// Node head(const Edge& e) const { return gw.head(e); }
marci@238	778	// Node tail(const Edge& e) const { return gw.tail(e); }
marci@158	779
marci@238	780	// template<typename I> bool valid(const I& i) const
marci@238	781	// { return gw.valid(i); }
marci@158	782
marci@238	783	// int nodeNum() const { return gw.nodeNum(); }
marci@238	784	// int edgeNum() const { return gw.edgeNum(); }
marci@158	785
marci@174	786	// template<typename I> Node aNode(const I& e) const {
marci@158	787	// return graph->aNode(e); }
marci@174	788	// template<typename I> Node bNode(const I& e) const {
marci@158	789	// return graph->bNode(e); }
marci@238	790
marci@238	791	Node aNode(const OutEdgeIt& e) const {
marci@303	792	if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
marci@238	793	Node bNode(const OutEdgeIt& e) const {
marci@303	794	if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
marci@158	795
marci@238	796	// Node addNode() const { return gw.addNode(); }
marci@238	797
marci@231	798	// FIXME: ez igy nem jo, mert nem
marci@231	799	// Edge addEdge(const Node& tail, const Node& head) const {
marci@231	800	// return graph->addEdge(tail, head); }
marci@158	801
marci@238	802	// template<typename I> void erase(const I& i) const { gw.erase(i); }
marci@158	803
marci@238	804	// void clear() const { gw.clear(); }
marci@158	805
marci@303	806	// template<typename T> class NodeMap : public Graph::NodeMap<T> {
marci@238	807	// public:
marci@303	808	// NodeMap(const UndirGraphWrapper<Graph>& _G) :
marci@303	809	// Graph::NodeMap<T>(_G.gw) { }
marci@303	810	// NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
marci@303	811	// Graph::NodeMap<T>(_G.gw, a) { }
marci@238	812	// };
marci@168	813
marci@238	814	// template<typename T> class EdgeMap :
marci@303	815	// public GraphWrapperSkeleton<Graph>::EdgeMap<T> {
marci@238	816	// public:
marci@303	817	// EdgeMap(const UndirGraphWrapper<Graph>& _G) :
marci@303	818	// GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }
marci@303	819	// EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
marci@303	820	// Graph::EdgeMap<T>(_G.gw, a) { }
marci@238	821	// };
marci@238	822	};
marci@158	823
marci@158	824
marci@158	825
marci@236	826
marci@236	827
marci@155	828	// template<typename Graph>
marci@155	829	// class SymGraphWrapper
marci@155	830	// {
marci@155	831	// Graph* graph;
marci@76	832
marci@155	833	// public:
marci@303	834	// typedef Graph ParentGraph;
marci@155	835
marci@174	836	// typedef typename Graph::Node Node;
marci@174	837	// typedef typename Graph::Edge Edge;
marci@174	838
marci@155	839	// typedef typename Graph::NodeIt NodeIt;
marci@155	840
marci@155	841	// //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
marci@155	842	// //iranyitatlant, ami van
marci@155	843	// //mert csak 1 dolgot lehet be typedef-elni
marci@155	844	// typedef typename Graph::OutEdgeIt SymEdgeIt;
marci@155	845	// //typedef typename Graph::InEdgeIt SymEdgeIt;
marci@155	846	// //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@174	847	// typedef typename Graph::EdgeIt EdgeIt;
marci@155	848
marci@155	849	// int nodeNum() const { return graph->nodeNum(); }
marci@155	850	// int edgeNum() const { return graph->edgeNum(); }
marci@155	851
marci@212	852	// template<typename I> I& first(I& i) const { return graph->first(i); }
marci@212	853	// template<typename I, typename P> I& first(I& i, const P& p) const {
marci@212	854	// return graph->first(i, p); }
marci@155	855	// //template<typename I> I next(const I i); { return graph->goNext(i); }
marci@155	856	// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
marci@155	857
marci@155	858	// template< typename It > It first() const {
marci@212	859	// It e; first(e); return e; }
marci@155	860
marci@174	861	// template< typename It > It first(Node v) const {
marci@212	862	// It e; first(e, v); return e; }
marci@155	863
marci@174	864	// Node head(const Edge& e) const { return graph->head(e); }
marci@174	865	// Node tail(const Edge& e) const { return graph->tail(e); }
marci@155	866
marci@174	867	// template<typename I> Node aNode(const I& e) const {
marci@155	868	// return graph->aNode(e); }
marci@174	869	// template<typename I> Node bNode(const I& e) const {
marci@155	870	// return graph->bNode(e); }
marci@155	871
marci@155	872	// //template<typename I> bool valid(const I i);
marci@155	873	// //{ return graph->valid(i); }
marci@155	874
marci@155	875	// //template<typename I> void setInvalid(const I &i);
marci@155	876	// //{ return graph->setInvalid(i); }
marci@155	877
marci@174	878	// Node addNode() { return graph->addNode(); }
marci@174	879	// Edge addEdge(const Node& tail, const Node& head) {
marci@155	880	// return graph->addEdge(tail, head); }
marci@155	881
marci@155	882	// template<typename I> void erase(const I& i) { graph->erase(i); }
marci@155	883
marci@155	884	// void clear() { graph->clear(); }
marci@155	885
marci@155	886	// template<typename T> class NodeMap : public Graph::NodeMap<T> { };
marci@155	887	// template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
marci@155	888
marci@155	889	// void setGraph(Graph& _graph) { graph = &_graph; }
marci@155	890	// Graph& getGraph() { return (*graph); }
marci@155	891
marci@155	892	// //SymGraphWrapper() : graph(0) { }
marci@155	893	// SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
marci@155	894	// };
marci@155	895
marci@155	896
marci@317	897
marci@317	898
marci@330	899	template<typename Graph, typename Number,
marci@330	900	typename CapacityMap, typename FlowMap>
marci@311	901	class ResGraphWrapper : public GraphWrapper<Graph> {
marci@199	902	protected:
marci@317	903	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	904	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	905	// typedef typename Graph::Edge GraphEdge;
marci@330	906	const CapacityMap* capacity;
marci@155	907	FlowMap* flow;
marci@155	908	public:
marci@168	909
marci@330	910	ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
marci@330	911	FlowMap& _flow) :
marci@330	912	GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
marci@168	913
marci@174	914	class Edge;
marci@155	915	class OutEdgeIt;
marci@174	916	friend class Edge;
marci@155	917	friend class OutEdgeIt;
marci@76	918
marci@311	919	typedef typename GraphWrapper<Graph>::Node Node;
marci@311	920	typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@317	921	class Edge : public Graph::Edge {
marci@330	922	friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
marci@155	923	protected:
marci@317	924	bool forward; //true, iff forward
marci@317	925	// typename Graph::Edge e;
marci@155	926	public:
marci@317	927	Edge() { }
marci@317	928	Edge(const typename Graph::Edge& _e, bool _forward) :
marci@317	929	Graph::Edge(_e), forward(_forward) { }
marci@317	930	Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
marci@317	931	//the unique invalid iterator
marci@174	932	friend bool operator==(const Edge& u, const Edge& v) {
marci@317	933	return (v.forward==u.forward &&
marci@317	934	static_cast<typename Graph::Edge>(u)==
marci@317	935	static_cast<typename Graph::Edge>(v));
marci@174	936	}
marci@174	937	friend bool operator!=(const Edge& u, const Edge& v) {
marci@317	938	return (v.forward!=u.forward \|\|
marci@317	939	static_cast<typename Graph::Edge>(u)!=
marci@317	940	static_cast<typename Graph::Edge>(v));
marci@174	941	}
marci@155	942	};
marci@317	943	// class Edge {
marci@330	944	// friend class ResGraphWrapper<Graph, Number,lksd FlowMap, CapacityMap>;
marci@317	945	// protected:
marci@317	946	// bool out_or_in; //true, iff out
marci@317	947	// GraphOutEdgeIt out;
marci@317	948	// GraphInEdgeIt in;
marci@317	949	// public:
marci@317	950	// Edge() : out_or_in(true) { }
marci@317	951	// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
marci@317	952	// // bool valid() const {
marci@317	953	// // return out_or_in && out.valid() \|\| in.valid(); }
marci@317	954	// friend bool operator==(const Edge& u, const Edge& v) {
marci@317	955	// if (v.out_or_in)
marci@317	956	// return (u.out_or_in && u.out==v.out);
marci@317	957	// else
marci@317	958	// return (!u.out_or_in && u.in==v.in);
marci@317	959	// }
marci@317	960	// friend bool operator!=(const Edge& u, const Edge& v) {
marci@317	961	// if (v.out_or_in)
marci@317	962	// return (!u.out_or_in \|\| u.out!=v.out);
marci@317	963	// else
marci@317	964	// return (u.out_or_in \|\| u.in!=v.in);
marci@317	965	// }
marci@317	966	// operator GraphEdge() const {
marci@317	967	// if (out_or_in) return(out); else return(in);
marci@317	968	// }
marci@317	969	// };
marci@317	970	class OutEdgeIt {
marci@330	971	friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
marci@317	972	protected:
marci@317	973	typename Graph::OutEdgeIt out;
marci@317	974	typename Graph::InEdgeIt in;
marci@317	975	bool forward;
marci@155	976	public:
marci@155	977	OutEdgeIt() { }
marci@168	978	//FIXME
marci@317	979	// OutEdgeIt(const Edge& e) : Edge(e) { }
marci@317	980	OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
marci@317	981	//the unique invalid iterator
marci@330	982	OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
marci@317	983	forward=true;
marci@303	984	resG.graph->first(out, v);
marci@317	985	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
marci@303	986	if (!resG.graph->valid(out)) {
marci@317	987	forward=false;
marci@303	988	resG.graph->first(in, v);
marci@317	989	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
marci@155	990	}
marci@155	991	}
marci@317	992	operator Edge() const {
marci@317	993	// Edge e;
marci@317	994	// e.forward=this->forward;
marci@317	995	// if (this->forward) e=out; else e=in;
marci@317	996	// return e;
marci@317	997	if (this->forward)
marci@317	998	return Edge(out, this->forward);
marci@317	999	else
marci@317	1000	return Edge(in, this->forward);
marci@317	1001	}
marci@317	1002	};
marci@317	1003	// class OutEdgeIt : public Edge {
marci@330	1004	// friend class ResGraphWrapper<Graph, Number, FkklowMap, CapacityMap>;
marci@317	1005	// public:
marci@317	1006	// OutEdgeIt() { }
marci@317	1007	// //FIXME
marci@317	1008	// OutEdgeIt(const Edge& e) : Edge(e) { }
marci@317	1009	// OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@330	1010	// OutEdgeIt(const ResGraphWrapper<Graph, Number, FdfvlowMap, CapacityMap>& resG, Node v) : Edge() {
marci@317	1011	// resG.graph->first(out, v);
marci@317	1012	// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1013	// if (!resG.graph->valid(out)) {
marci@317	1014	// out_or_in=0;
marci@317	1015	// resG.graph->first(in, v);
marci@317	1016	// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1017	// }
marci@317	1018	// }
marci@168	1019	// public:
marci@168	1020	// OutEdgeIt& operator++() {
marci@168	1021	// if (out_or_in) {
marci@174	1022	// Node v=/resG->/G->aNode(out);
marci@168	1023	// ++out;
marci@269	1024	// while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@168	1025	// if (!out.valid()) {
marci@168	1026	// out_or_in=0;
marci@212	1027	// G->first(in, v);
marci@269	1028	// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1029	// }
marci@168	1030	// } else {
marci@168	1031	// ++in;
marci@269	1032	// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1033	// }
marci@168	1034	// return *this;
marci@168	1035	// }
marci@317	1036	// };
marci@155	1037
marci@263	1038	//FIXME This is just for having InEdgeIt
marci@311	1039	// class InEdgeIt : public Edge { };
marci@263	1040
marci@317	1041	class InEdgeIt {
marci@330	1042	friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
marci@317	1043	protected:
marci@317	1044	typename Graph::OutEdgeIt out;
marci@317	1045	typename Graph::InEdgeIt in;
marci@317	1046	bool forward;
marci@317	1047	public:
marci@317	1048	InEdgeIt() { }
marci@317	1049	//FIXME
marci@317	1050	// OutEdgeIt(const Edge& e) : Edge(e) { }
marci@317	1051	InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
marci@317	1052	//the unique invalid iterator
marci@330	1053	InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
marci@317	1054	forward=true;
marci@317	1055	resG.graph->first(in, v);
marci@317	1056	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
marci@317	1057	if (!resG.graph->valid(in)) {
marci@317	1058	forward=false;
marci@317	1059	resG.graph->first(out, v);
marci@317	1060	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
marci@317	1061	}
marci@317	1062	}
marci@317	1063	operator Edge() const {
marci@317	1064	// Edge e;
marci@317	1065	// e.forward=this->forward;
marci@317	1066	// if (this->forward) e=out; else e=in;
marci@317	1067	// return e;
marci@317	1068	if (this->forward)
marci@317	1069	return Edge(in, this->forward);
marci@317	1070	else
marci@317	1071	return Edge(out, this->forward);
marci@317	1072	}
marci@317	1073	};
marci@317	1074
marci@317	1075	class EdgeIt {
marci@330	1076	friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
marci@317	1077	protected:
marci@317	1078	typename Graph::EdgeIt e;
marci@317	1079	bool forward;
marci@155	1080	public:
marci@174	1081	EdgeIt() { }
marci@317	1082	EdgeIt(const Invalid& i) : e(i), forward(false) { }
marci@330	1083	EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
marci@317	1084	forward=true;
marci@317	1085	resG.graph->first(e);
marci@317	1086	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
marci@317	1087	if (!resG.graph->valid(e)) {
marci@317	1088	forward=false;
marci@317	1089	resG.graph->first(e);
marci@317	1090	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
marci@155	1091	}
marci@155	1092	}
marci@317	1093	operator Edge() const {
marci@317	1094	return Edge(e, this->forward);
marci@317	1095	}
marci@317	1096	};
marci@317	1097	// class EdgeIt : public Edge {
marci@330	1098	// friend class ResGraphWrapper<Graph, Number, FflowMap, CapacityMap>;
marci@317	1099	// NodeIt v;
marci@317	1100	// public:
marci@317	1101	// EdgeIt() { }
marci@317	1102	// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
marci@317	1103	// EdgeIt(const Invalid& i) : Edge(i) { }
marci@330	1104	// EdgeIt(const ResGraphWrapper<Graph, Number, FlfowMap, CapacityMap>& resG) : Edge() {
marci@317	1105	// resG.graph->first(v);
marci@317	1106	// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
marci@317	1107	// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1108	// while (resG.graph->valid(v) && !resG.graph->valid(out)) {
marci@317	1109	// resG.graph->next(v);
marci@317	1110	// if (resG.graph->valid(v)) resG.graph->first(out, v);
marci@317	1111	// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1112	// }
marci@317	1113	// if (!resG.graph->valid(out)) {
marci@317	1114	// out_or_in=0;
marci@317	1115	// resG.graph->first(v);
marci@317	1116	// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
marci@317	1117	// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1118	// while (resG.graph->valid(v) && !resG.graph->valid(in)) {
marci@317	1119	// resG.graph->next(v);
marci@317	1120	// if (resG.graph->valid(v)) resG.graph->first(in, v);
marci@317	1121	// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1122	// }
marci@317	1123	// }
marci@317	1124	// }
marci@174	1125	// EdgeIt& operator++() {
marci@168	1126	// if (out_or_in) {
marci@168	1127	// ++out;
marci@269	1128	// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@168	1129	// while (v.valid() && !out.valid()) {
marci@168	1130	// ++v;
marci@212	1131	// if (v.valid()) G->first(out, v);
marci@269	1132	// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@168	1133	// }
marci@168	1134	// if (!out.valid()) {
marci@168	1135	// out_or_in=0;
marci@212	1136	// G->first(v);
marci@303	1137	// if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
marci@269	1138	// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1139	// while (v.valid() && !in.valid()) {
marci@168	1140	// ++v;
marci@212	1141	// if (v.valid()) G->first(in, v);
marci@269	1142	// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1143	// }
marci@168	1144	// }
marci@168	1145	// } else {
marci@168	1146	// ++in;
marci@269	1147	// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1148	// while (v.valid() && !in.valid()) {
marci@168	1149	// ++v;
marci@212	1150	// if (v.valid()) G->first(in, v);
marci@269	1151	// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1152	// }
marci@168	1153	// }
marci@168	1154	// return *this;
marci@168	1155	// }
marci@317	1156	// };
marci@155	1157
marci@311	1158	NodeIt& first(NodeIt& i) const {
marci@317	1159	i=NodeIt(*this); return i;
marci@155	1160	}
marci@311	1161	OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	1162	i=OutEdgeIt(*this, p); return i;
marci@311	1163	}
marci@317	1164	// FIXME not tested
marci@317	1165	InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	1166	i=InEdgeIt(*this, p); return i;
marci@317	1167	}
marci@317	1168	EdgeIt& first(EdgeIt& i) const {
marci@317	1169	i=EdgeIt(*this); return i;
marci@155	1170	}
marci@155	1171
marci@317	1172	NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
marci@155	1173	OutEdgeIt& next(OutEdgeIt& e) const {
marci@317	1174	if (e.forward) {
marci@303	1175	Node v=graph->aNode(e.out);
marci@303	1176	graph->next(e.out);
marci@317	1177	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
marci@303	1178	if (!graph->valid(e.out)) {
marci@317	1179	e.forward=false;
marci@303	1180	graph->first(e.in, v);
marci@317	1181	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
marci@155	1182	}
marci@155	1183	} else {
marci@303	1184	graph->next(e.in);
marci@317	1185	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
marci@155	1186	}
marci@155	1187	return e;
marci@155	1188	}
marci@317	1189	// FIXME Not tested
marci@317	1190	InEdgeIt& next(InEdgeIt& e) const {
marci@317	1191	if (e.forward) {
marci@317	1192	Node v=graph->aNode(e.in);
marci@317	1193	graph->next(e.in);
marci@317	1194	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
marci@317	1195	if (!graph->valid(e.in)) {
marci@317	1196	e.forward=false;
marci@317	1197	graph->first(e.out, v);
marci@317	1198	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
marci@317	1199	}
marci@317	1200	} else {
marci@303	1201	graph->next(e.out);
marci@317	1202	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
marci@317	1203	}
marci@317	1204	return e;
marci@317	1205	}
marci@317	1206	EdgeIt& next(EdgeIt& e) const {
marci@317	1207	if (e.forward) {
marci@317	1208	graph->next(e.e);
marci@317	1209	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
marci@317	1210	if (!graph->valid(e.e)) {
marci@317	1211	e.forward=false;
marci@317	1212	graph->first(e.e);
marci@317	1213	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
marci@155	1214	}
marci@317	1215	} else {
marci@317	1216	graph->next(e.e);
marci@317	1217	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
marci@155	1218	}
marci@317	1219	return e;
marci@317	1220	}
marci@317	1221	// EdgeIt& next(EdgeIt& e) const {
marci@317	1222	// if (e.out_or_in) {
marci@317	1223	// graph->next(e.out);
marci@317	1224	// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1225	// while (graph->valid(e.v) && !graph->valid(e.out)) {
marci@317	1226	// graph->next(e.v);
marci@317	1227	// if (graph->valid(e.v)) graph->first(e.out, e.v);
marci@317	1228	// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1229	// }
marci@317	1230	// if (!graph->valid(e.out)) {
marci@317	1231	// e.out_or_in=0;
marci@317	1232	// graph->first(e.v);
marci@317	1233	// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
marci@317	1234	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1235	// while (graph->valid(e.v) && !graph->valid(e.in)) {
marci@317	1236	// graph->next(e.v);
marci@317	1237	// if (graph->valid(e.v)) graph->first(e.in, e.v);
marci@317	1238	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1239	// }
marci@317	1240	// }
marci@317	1241	// } else {
marci@317	1242	// graph->next(e.in);
marci@317	1243	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1244	// while (graph->valid(e.v) && !graph->valid(e.in)) {
marci@317	1245	// graph->next(e.v);
marci@317	1246	// if (graph->valid(e.v)) graph->first(e.in, e.v);
marci@317	1247	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1248	// }
marci@317	1249	// }
marci@317	1250	// return e;
marci@317	1251	// }
marci@76	1252
marci@76	1253
marci@155	1254	template< typename It >
marci@155	1255	It first() const {
marci@155	1256	It e;
marci@212	1257	first(e);
marci@155	1258	return e;
marci@155	1259	}
marci@76	1260
marci@155	1261	template< typename It >
marci@174	1262	It first(Node v) const {
marci@155	1263	It e;
marci@212	1264	first(e, v);
marci@155	1265	return e;
marci@155	1266	}
marci@76	1267
marci@174	1268	Node tail(Edge e) const {
marci@317	1269	return ((e.forward) ? graph->tail(e) : graph->head(e)); }
marci@174	1270	Node head(Edge e) const {
marci@317	1271	return ((e.forward) ? graph->head(e) : graph->tail(e)); }
marci@76	1272
marci@174	1273	Node aNode(OutEdgeIt e) const {
marci@317	1274	return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
marci@174	1275	Node bNode(OutEdgeIt e) const {
marci@317	1276	return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
marci@76	1277
marci@303	1278	int nodeNum() const { return graph->nodeNum(); }
marci@263	1279	//FIXME
marci@303	1280	//int edgeNum() const { return graph->edgeNum(); }
marci@263	1281
marci@263	1282
marci@317	1283	// int id(Node v) const { return graph->id(v); }
marci@155	1284
marci@317	1285	bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
marci@174	1286	bool valid(Edge e) const {
marci@317	1287	return graph->valid(e);
marci@317	1288	//return e.forward ? graph->valid(e.out) : graph->valid(e.in);
marci@317	1289	}
marci@155	1290
marci@174	1291	void augment(const Edge& e, Number a) const {
marci@317	1292	if (e.forward)
marci@303	1293	// flow->set(e.out, flow->get(e.out)+a);
marci@317	1294	flow->set(e, (*flow)[e]+a);
marci@168	1295	else
marci@303	1296	// flow->set(e.in, flow->get(e.in)-a);
marci@317	1297	flow->set(e, (*flow)[e]-a);
marci@168	1298	}
marci@168	1299
marci@269	1300	Number resCap(const Edge& e) const {
marci@317	1301	if (e.forward)
marci@303	1302	// return (capacity->get(e.out)-flow->get(e.out));
marci@317	1303	return ((capacity)[e]-(flow)[e]);
marci@168	1304	else
marci@303	1305	// return (flow->get(e.in));
marci@317	1306	return ((*flow)[e]);
marci@168	1307	}
marci@168	1308
marci@317	1309	// Number resCap(typename Graph::OutEdgeIt out) const {
marci@317	1310	// // return (capacity->get(out)-flow->get(out));
marci@317	1311	// return ((capacity)[out]-(flow)[out]);
marci@317	1312	// }
marci@168	1313
marci@317	1314	// Number resCap(typename Graph::InEdgeIt in) const {
marci@317	1315	// // return (flow->get(in));
marci@317	1316	// return ((*flow)[in]);
marci@317	1317	// }
marci@168	1318
marci@303	1319	// template<typename T> class NodeMap : public Graph::NodeMap<T> {
marci@266	1320	// public:
marci@330	1321	// NodeMap(const ResGraphWrapper<Graph, Number, FlovwMap, CapacityMap>& _G)
marci@303	1322	// : Graph::NodeMap<T>(_G.gw) { }
marci@330	1323	// NodeMap(const ResGraphWrapper<Graph, Number, FlowvMap, CapacityMap>& _G,
marci@303	1324	// T a) : Graph::NodeMap<T>(_G.gw, a) { }
marci@266	1325	// };
marci@155	1326
marci@155	1327	// template <typename T>
marci@155	1328	// class NodeMap {
marci@155	1329	// typename Graph::NodeMap<T> node_map;
marci@155	1330	// public:
marci@174	1331	// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
marci@174	1332	// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
marci@174	1333	// void set(Node nit, T a) { node_map.set(nit, a); }
marci@174	1334	// T get(Node nit) const { return node_map.get(nit); }
marci@155	1335	// };
marci@155	1336
marci@155	1337	template <typename T>
marci@155	1338	class EdgeMap {
marci@303	1339	typename Graph::EdgeMap<T> forward_map, backward_map;
marci@155	1340	public:
marci@330	1341	EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map((_G.graph)), backward_map((_G.graph)) { }
marci@330	1342	EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map((_G.graph), a), backward_map((_G.graph), a) { }
marci@174	1343	void set(Edge e, T a) {
marci@317	1344	if (e.forward)
marci@155	1345	forward_map.set(e.out, a);
marci@155	1346	else
marci@155	1347	backward_map.set(e.in, a);
marci@155	1348	}
marci@303	1349	T operator[](Edge e) const {
marci@317	1350	if (e.forward)
marci@303	1351	return forward_map[e.out];
marci@155	1352	else
marci@303	1353	return backward_map[e.in];
marci@155	1354	}
marci@303	1355	// T get(Edge e) const {
marci@303	1356	// if (e.out_or_in)
marci@303	1357	// return forward_map.get(e.out);
marci@303	1358	// else
marci@303	1359	// return backward_map.get(e.in);
marci@303	1360	// }
marci@155	1361	};
marci@168	1362	};
marci@168	1363
marci@317	1364
marci@317	1365
marci@317	1366	// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@317	1367	// class ResGraphWrapper : public GraphWrapper<Graph> {
marci@317	1368	// protected:
marci@317	1369	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	1370	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	1371	// typedef typename Graph::Edge GraphEdge;
marci@317	1372	// FlowMap* flow;
marci@317	1373	// const CapacityMap* capacity;
marci@317	1374	// public:
marci@317	1375
marci@317	1376	// ResGraphWrapper(Graph& _graph, FlowMap& _flow,
marci@317	1377	// const CapacityMap& _capacity) :
marci@317	1378	// GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
marci@317	1379
marci@317	1380	// class Edge;
marci@317	1381	// class OutEdgeIt;
marci@317	1382	// friend class Edge;
marci@317	1383	// friend class OutEdgeIt;
marci@317	1384
marci@317	1385	// typedef typename GraphWrapper<Graph>::Node Node;
marci@317	1386	// typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@317	1387	// class Edge {
marci@317	1388	// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	1389	// protected:
marci@317	1390	// bool out_or_in; //true, iff out
marci@317	1391	// GraphOutEdgeIt out;
marci@317	1392	// GraphInEdgeIt in;
marci@317	1393	// public:
marci@317	1394	// Edge() : out_or_in(true) { }
marci@317	1395	// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
marci@317	1396	// // bool valid() const {
marci@317	1397	// // return out_or_in && out.valid() \|\| in.valid(); }
marci@317	1398	// friend bool operator==(const Edge& u, const Edge& v) {
marci@317	1399	// if (v.out_or_in)
marci@317	1400	// return (u.out_or_in && u.out==v.out);
marci@317	1401	// else
marci@317	1402	// return (!u.out_or_in && u.in==v.in);
marci@317	1403	// }
marci@317	1404	// friend bool operator!=(const Edge& u, const Edge& v) {
marci@317	1405	// if (v.out_or_in)
marci@317	1406	// return (!u.out_or_in \|\| u.out!=v.out);
marci@317	1407	// else
marci@317	1408	// return (u.out_or_in \|\| u.in!=v.in);
marci@317	1409	// }
marci@317	1410	// operator GraphEdge() const {
marci@317	1411	// if (out_or_in) return(out); else return(in);
marci@317	1412	// }
marci@317	1413	// };
marci@317	1414	// class OutEdgeIt : public Edge {
marci@317	1415	// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	1416	// public:
marci@317	1417	// OutEdgeIt() { }
marci@317	1418	// //FIXME
marci@317	1419	// OutEdgeIt(const Edge& e) : Edge(e) { }
marci@317	1420	// OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@317	1421	// OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
marci@317	1422	// resG.graph->first(out, v);
marci@317	1423	// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1424	// if (!resG.graph->valid(out)) {
marci@317	1425	// out_or_in=0;
marci@317	1426	// resG.graph->first(in, v);
marci@317	1427	// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1428	// }
marci@317	1429	// }
marci@317	1430	// // public:
marci@317	1431	// // OutEdgeIt& operator++() {
marci@317	1432	// // if (out_or_in) {
marci@317	1433	// // Node v=/resG->/G->aNode(out);
marci@317	1434	// // ++out;
marci@317	1435	// // while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@317	1436	// // if (!out.valid()) {
marci@317	1437	// // out_or_in=0;
marci@317	1438	// // G->first(in, v);
marci@317	1439	// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1440	// // }
marci@317	1441	// // } else {
marci@317	1442	// // ++in;
marci@317	1443	// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1444	// // }
marci@317	1445	// // return *this;
marci@317	1446	// // }
marci@317	1447	// };
marci@317	1448
marci@317	1449	// //FIXME This is just for having InEdgeIt
marci@317	1450	// // class InEdgeIt : public Edge { };
marci@317	1451
marci@317	1452	// class EdgeIt : public Edge {
marci@317	1453	// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	1454	// NodeIt v;
marci@317	1455	// public:
marci@317	1456	// EdgeIt() { }
marci@317	1457	// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
marci@317	1458	// EdgeIt(const Invalid& i) : Edge(i) { }
marci@317	1459	// EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
marci@317	1460	// resG.graph->first(v);
marci@317	1461	// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
marci@317	1462	// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1463	// while (resG.graph->valid(v) && !resG.graph->valid(out)) {
marci@317	1464	// resG.graph->next(v);
marci@317	1465	// if (resG.graph->valid(v)) resG.graph->first(out, v);
marci@317	1466	// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1467	// }
marci@317	1468	// if (!resG.graph->valid(out)) {
marci@317	1469	// out_or_in=0;
marci@317	1470	// resG.graph->first(v);
marci@317	1471	// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
marci@317	1472	// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1473	// while (resG.graph->valid(v) && !resG.graph->valid(in)) {
marci@317	1474	// resG.graph->next(v);
marci@317	1475	// if (resG.graph->valid(v)) resG.graph->first(in, v);
marci@317	1476	// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1477	// }
marci@317	1478	// }
marci@317	1479	// }
marci@317	1480	// // EdgeIt& operator++() {
marci@317	1481	// // if (out_or_in) {
marci@317	1482	// // ++out;
marci@317	1483	// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@317	1484	// // while (v.valid() && !out.valid()) {
marci@317	1485	// // ++v;
marci@317	1486	// // if (v.valid()) G->first(out, v);
marci@317	1487	// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@317	1488	// // }
marci@317	1489	// // if (!out.valid()) {
marci@317	1490	// // out_or_in=0;
marci@317	1491	// // G->first(v);
marci@317	1492	// // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
marci@317	1493	// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1494	// // while (v.valid() && !in.valid()) {
marci@317	1495	// // ++v;
marci@317	1496	// // if (v.valid()) G->first(in, v);
marci@317	1497	// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1498	// // }
marci@317	1499	// // }
marci@317	1500	// // } else {
marci@317	1501	// // ++in;
marci@317	1502	// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1503	// // while (v.valid() && !in.valid()) {
marci@317	1504	// // ++v;
marci@317	1505	// // if (v.valid()) G->first(in, v);
marci@317	1506	// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1507	// // }
marci@317	1508	// // }
marci@317	1509	// // return *this;
marci@317	1510	// // }
marci@317	1511	// };
marci@317	1512
marci@317	1513	// NodeIt& first(NodeIt& i) const {
marci@317	1514	// i=NodeIt(*this);
marci@317	1515	// return i;
marci@317	1516	// }
marci@317	1517	// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	1518	// i=OutEdgeIt(*this, p);
marci@317	1519	// return i;
marci@317	1520	// }
marci@317	1521	// //FIXME Not yet implemented
marci@317	1522	// //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	1523	// //i=InEdgeIt(*this, p);
marci@317	1524	// // return i;
marci@317	1525	// //}
marci@317	1526	// EdgeIt& first(EdgeIt& e) const {
marci@317	1527	// e=EdgeIt(*this);
marci@317	1528	// return e;
marci@317	1529	// }
marci@317	1530
marci@317	1531	// NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
marci@317	1532	// OutEdgeIt& next(OutEdgeIt& e) const {
marci@317	1533	// if (e.out_or_in) {
marci@317	1534	// Node v=graph->aNode(e.out);
marci@317	1535	// graph->next(e.out);
marci@317	1536	// while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1537	// if (!graph->valid(e.out)) {
marci@317	1538	// e.out_or_in=0;
marci@317	1539	// graph->first(e.in, v);
marci@317	1540	// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1541	// }
marci@317	1542	// } else {
marci@317	1543	// graph->next(e.in);
marci@317	1544	// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1545	// }
marci@317	1546	// return e;
marci@317	1547	// }
marci@317	1548	// //FIXME Not yet implemented
marci@317	1549	// //InEdgeIt& next(InEdgeIt& e) const {
marci@317	1550	// // return e;
marci@317	1551	// //}
marci@317	1552	// EdgeIt& next(EdgeIt& e) const {
marci@317	1553	// if (e.out_or_in) {
marci@317	1554	// graph->next(e.out);
marci@317	1555	// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1556	// while (graph->valid(e.v) && !graph->valid(e.out)) {
marci@317	1557	// graph->next(e.v);
marci@317	1558	// if (graph->valid(e.v)) graph->first(e.out, e.v);
marci@317	1559	// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1560	// }
marci@317	1561	// if (!graph->valid(e.out)) {
marci@317	1562	// e.out_or_in=0;
marci@317	1563	// graph->first(e.v);
marci@317	1564	// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
marci@317	1565	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1566	// while (graph->valid(e.v) && !graph->valid(e.in)) {
marci@317	1567	// graph->next(e.v);
marci@317	1568	// if (graph->valid(e.v)) graph->first(e.in, e.v);
marci@317	1569	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1570	// }
marci@317	1571	// }
marci@317	1572	// } else {
marci@317	1573	// graph->next(e.in);
marci@317	1574	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1575	// while (graph->valid(e.v) && !graph->valid(e.in)) {
marci@317	1576	// graph->next(e.v);
marci@317	1577	// if (graph->valid(e.v)) graph->first(e.in, e.v);
marci@317	1578	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1579	// }
marci@317	1580	// }
marci@317	1581	// return e;
marci@317	1582	// }
marci@317	1583
marci@317	1584
marci@317	1585	// template< typename It >
marci@317	1586	// It first() const {
marci@317	1587	// It e;
marci@317	1588	// first(e);
marci@317	1589	// return e;
marci@317	1590	// }
marci@317	1591
marci@317	1592	// template< typename It >
marci@317	1593	// It first(Node v) const {
marci@317	1594	// It e;
marci@317	1595	// first(e, v);
marci@317	1596	// return e;
marci@317	1597	// }
marci@317	1598
marci@317	1599	// Node tail(Edge e) const {
marci@317	1600	// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
marci@317	1601	// Node head(Edge e) const {
marci@317	1602	// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
marci@317	1603
marci@317	1604	// Node aNode(OutEdgeIt e) const {
marci@317	1605	// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
marci@317	1606	// Node bNode(OutEdgeIt e) const {
marci@317	1607	// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
marci@317	1608
marci@317	1609	// int nodeNum() const { return graph->nodeNum(); }
marci@317	1610	// //FIXME
marci@317	1611	// //int edgeNum() const { return graph->edgeNum(); }
marci@317	1612
marci@317	1613
marci@317	1614	// int id(Node v) const { return graph->id(v); }
marci@317	1615
marci@317	1616	// bool valid(Node n) const { return graph->valid(n); }
marci@317	1617	// bool valid(Edge e) const {
marci@317	1618	// return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
marci@317	1619
marci@317	1620	// void augment(const Edge& e, Number a) const {
marci@317	1621	// if (e.out_or_in)
marci@317	1622	// // flow->set(e.out, flow->get(e.out)+a);
marci@317	1623	// flow->set(e.out, (*flow)[e.out]+a);
marci@317	1624	// else
marci@317	1625	// // flow->set(e.in, flow->get(e.in)-a);
marci@317	1626	// flow->set(e.in, (*flow)[e.in]-a);
marci@317	1627	// }
marci@317	1628
marci@317	1629	// Number resCap(const Edge& e) const {
marci@317	1630	// if (e.out_or_in)
marci@317	1631	// // return (capacity->get(e.out)-flow->get(e.out));
marci@317	1632	// return ((capacity)[e.out]-(flow)[e.out]);
marci@317	1633	// else
marci@317	1634	// // return (flow->get(e.in));
marci@317	1635	// return ((*flow)[e.in]);
marci@317	1636	// }
marci@317	1637
marci@317	1638	// Number resCap(GraphOutEdgeIt out) const {
marci@317	1639	// // return (capacity->get(out)-flow->get(out));
marci@317	1640	// return ((capacity)[out]-(flow)[out]);
marci@317	1641	// }
marci@317	1642
marci@317	1643	// Number resCap(GraphInEdgeIt in) const {
marci@317	1644	// // return (flow->get(in));
marci@317	1645	// return ((*flow)[in]);
marci@317	1646	// }
marci@317	1647
marci@317	1648	// // template<typename T> class NodeMap : public Graph::NodeMap<T> {
marci@317	1649	// // public:
marci@317	1650	// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
marci@317	1651	// // : Graph::NodeMap<T>(_G.gw) { }
marci@317	1652	// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
marci@317	1653	// // T a) : Graph::NodeMap<T>(_G.gw, a) { }
marci@317	1654	// // };
marci@317	1655
marci@317	1656	// // template <typename T>
marci@317	1657	// // class NodeMap {
marci@317	1658	// // typename Graph::NodeMap<T> node_map;
marci@317	1659	// // public:
marci@317	1660	// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
marci@317	1661	// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
marci@317	1662	// // void set(Node nit, T a) { node_map.set(nit, a); }
marci@317	1663	// // T get(Node nit) const { return node_map.get(nit); }
marci@317	1664	// // };
marci@317	1665
marci@317	1666	// template <typename T>
marci@317	1667	// class EdgeMap {
marci@317	1668	// typename Graph::EdgeMap<T> forward_map, backward_map;
marci@317	1669	// public:
marci@317	1670	// EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map((_G.graph)), backward_map((_G.graph)) { }
marci@317	1671	// EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map((_G.graph), a), backward_map((_G.graph), a) { }
marci@317	1672	// void set(Edge e, T a) {
marci@317	1673	// if (e.out_or_in)
marci@317	1674	// forward_map.set(e.out, a);
marci@317	1675	// else
marci@317	1676	// backward_map.set(e.in, a);
marci@317	1677	// }
marci@317	1678	// T operator[](Edge e) const {
marci@317	1679	// if (e.out_or_in)
marci@317	1680	// return forward_map[e.out];
marci@317	1681	// else
marci@317	1682	// return backward_map[e.in];
marci@317	1683	// }
marci@317	1684	// // T get(Edge e) const {
marci@317	1685	// // if (e.out_or_in)
marci@317	1686	// // return forward_map.get(e.out);
marci@317	1687	// // else
marci@317	1688	// // return backward_map.get(e.in);
marci@317	1689	// // }
marci@317	1690	// };
marci@317	1691	// };
marci@317	1692
marci@317	1693
marci@303	1694	//ErasingFirstGraphWrapper for blocking flows
marci@303	1695	template<typename Graph, typename FirstOutEdgesMap>
marci@303	1696	class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
marci@269	1697	protected:
marci@269	1698	FirstOutEdgesMap* first_out_edges;
marci@269	1699	public:
marci@303	1700	ErasingFirstGraphWrapper(Graph& _graph,
marci@303	1701	FirstOutEdgesMap& _first_out_edges) :
marci@303	1702	GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
marci@269	1703
marci@317	1704	typedef typename GraphWrapper<Graph>::Node Node;
marci@317	1705	class NodeIt {
marci@317	1706	friend class GraphWrapper<Graph>;
marci@317	1707	friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@317	1708	typename Graph::NodeIt n;
marci@317	1709	public:
marci@311	1710	NodeIt() { }
marci@317	1711	NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
marci@317	1712	NodeIt(const Invalid& i) : n(i) { }
marci@311	1713	NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
marci@317	1714	n(*(_G.graph)) { }
marci@317	1715	operator Node() const { return Node(typename Graph::Node(n)); }
marci@311	1716	};
marci@317	1717	typedef typename GraphWrapper<Graph>::Edge Edge;
marci@317	1718	class OutEdgeIt {
marci@317	1719	friend class GraphWrapper<Graph>;
marci@317	1720	friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@317	1721	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	1722	typename Graph::OutEdgeIt e;
marci@311	1723	public:
marci@311	1724	OutEdgeIt() { }
marci@317	1725	OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
marci@317	1726	OutEdgeIt(const Invalid& i) : e(i) { }
marci@311	1727	OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
marci@317	1728	const Node& _n) :
marci@317	1729	e((*_G.first_out_edges)[_n]) { }
marci@317	1730	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@311	1731	};
marci@317	1732	class InEdgeIt {
marci@317	1733	friend class GraphWrapper<Graph>;
marci@317	1734	friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@317	1735	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	1736	typename Graph::InEdgeIt e;
marci@311	1737	public:
marci@311	1738	InEdgeIt() { }
marci@317	1739	InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
marci@317	1740	InEdgeIt(const Invalid& i) : e(i) { }
marci@311	1741	InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
marci@317	1742	const Node& _n) :
marci@317	1743	e(*(_G.graph), typename Graph::Node(_n)) { }
marci@317	1744	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@311	1745	};
marci@311	1746	//typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@317	1747	class EdgeIt {
marci@317	1748	friend class GraphWrapper<Graph>;
marci@317	1749	friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@317	1750	// typedef typename Graph::EdgeIt GraphEdgeIt;
marci@317	1751	typename Graph::EdgeIt e;
marci@311	1752	public:
marci@311	1753	EdgeIt() { }
marci@317	1754	EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
marci@317	1755	EdgeIt(const Invalid& i) : e(i) { }
marci@311	1756	EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
marci@317	1757	e(*(_G.graph)) { }
marci@317	1758	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@311	1759	};
marci@311	1760
marci@317	1761	NodeIt& first(NodeIt& i) const {
marci@317	1762	i=NodeIt(*this); return i;
marci@269	1763	}
marci@317	1764	OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	1765	i=OutEdgeIt(*this, p); return i;
marci@269	1766	}
marci@317	1767	InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	1768	i=InEdgeIt(*this, p); return i;
marci@311	1769	}
marci@317	1770	EdgeIt& first(EdgeIt& i) const {
marci@317	1771	i=EdgeIt(*this); return i;
marci@311	1772	}
marci@311	1773
marci@311	1774	// template<typename I> I& first(I& i) const {
marci@311	1775	// graph->first(i);
marci@311	1776	// return i;
marci@311	1777	// }
marci@311	1778	// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
marci@311	1779	// // e=first_out_edges->get(n);
marci@311	1780	// e=(*first_out_edges)[n];
marci@311	1781	// return e;
marci@311	1782	// }
marci@311	1783	// template<typename I, typename P> I& first(I& i, const P& p) const {
marci@311	1784	// graph->first(i, p);
marci@311	1785	// return i;
marci@311	1786	// }
marci@269	1787
marci@317	1788	NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
marci@317	1789	OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
marci@317	1790	InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
marci@317	1791	EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
marci@317	1792
marci@317	1793	Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@317	1794	Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@317	1795	Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@317	1796	Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@311	1797
marci@311	1798	// template<typename I> I& next(I &i) const {
marci@311	1799	// graph->next(i);
marci@311	1800	// return i;
marci@311	1801	// }
marci@269	1802
marci@269	1803	template< typename It > It first() const {
marci@269	1804	It e; this->first(e); return e; }
marci@269	1805
marci@269	1806	template< typename It > It first(const Node& v) const {
marci@269	1807	It e; this->first(e, v); return e; }
marci@269	1808
marci@269	1809	void erase(const OutEdgeIt& e) const {
marci@269	1810	OutEdgeIt f=e;
marci@269	1811	this->next(f);
marci@317	1812	first_out_edges->set(this->tail(e), f.e);
marci@269	1813	}
marci@269	1814	};
marci@269	1815
marci@317	1816	// //ErasingFirstGraphWrapper for blocking flows
marci@317	1817	// template<typename Graph, typename FirstOutEdgesMap>
marci@317	1818	// class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
marci@317	1819	// protected:
marci@317	1820	// FirstOutEdgesMap* first_out_edges;
marci@317	1821	// public:
marci@317	1822	// ErasingFirstGraphWrapper(Graph& _graph,
marci@317	1823	// FirstOutEdgesMap& _first_out_edges) :
marci@317	1824	// GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
marci@317	1825
marci@317	1826	// typedef typename Graph::Node Node;
marci@317	1827	// class NodeIt : public Graph::NodeIt {
marci@317	1828	// public:
marci@317	1829	// NodeIt() { }
marci@317	1830	// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
marci@317	1831	// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
marci@317	1832	// NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
marci@317	1833	// Graph::NodeIt(*(_G.graph)) { }
marci@317	1834	// };
marci@317	1835	// typedef typename Graph::Edge Edge;
marci@317	1836	// class OutEdgeIt : public Graph::OutEdgeIt {
marci@317	1837	// public:
marci@317	1838	// OutEdgeIt() { }
marci@317	1839	// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
marci@317	1840	// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
marci@317	1841	// OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
marci@317	1842	// const Node& n) :
marci@317	1843	// Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
marci@317	1844	// };
marci@317	1845	// class InEdgeIt : public Graph::InEdgeIt {
marci@317	1846	// public:
marci@317	1847	// InEdgeIt() { }
marci@317	1848	// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
marci@317	1849	// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
marci@317	1850	// InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
marci@317	1851	// const Node& n) :
marci@317	1852	// Graph::InEdgeIt(*(_G.graph), n) { }
marci@317	1853	// };
marci@317	1854	// //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@317	1855	// class EdgeIt : public Graph::EdgeIt {
marci@317	1856	// public:
marci@317	1857	// EdgeIt() { }
marci@317	1858	// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
marci@317	1859	// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
marci@317	1860	// EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
marci@317	1861	// Graph::EdgeIt(*(_G.graph)) { }
marci@317	1862	// };
marci@317	1863
marci@317	1864	// NodeIt& first(NodeIt& i) const {
marci@317	1865	// i=NodeIt(*this);
marci@317	1866	// return i;
marci@317	1867	// }
marci@317	1868	// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
marci@317	1869	// i=OutEdgeIt(*this, n);
marci@317	1870	// // i=(*first_out_edges)[n];
marci@317	1871	// return i;
marci@317	1872	// }
marci@317	1873	// InEdgeIt& first(InEdgeIt& i, const Node& n) const {
marci@317	1874	// i=InEdgeIt(*this, n);
marci@317	1875	// return i;
marci@317	1876	// }
marci@317	1877	// EdgeIt& first(EdgeIt& i) const {
marci@317	1878	// i=EdgeIt(*this);
marci@317	1879	// return i;
marci@317	1880	// }
marci@317	1881
marci@317	1882	// // template<typename I> I& first(I& i) const {
marci@317	1883	// // graph->first(i);
marci@317	1884	// // return i;
marci@317	1885	// // }
marci@317	1886	// // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
marci@317	1887	// // // e=first_out_edges->get(n);
marci@317	1888	// // e=(*first_out_edges)[n];
marci@317	1889	// // return e;
marci@317	1890	// // }
marci@317	1891	// // template<typename I, typename P> I& first(I& i, const P& p) const {
marci@317	1892	// // graph->first(i, p);
marci@317	1893	// // return i;
marci@317	1894	// // }
marci@317	1895
marci@317	1896	// NodeIt& next(NodeIt& i) const {
marci@317	1897	// graph->next(i);
marci@317	1898	// return i;
marci@317	1899	// }
marci@317	1900	// OutEdgeIt& next(OutEdgeIt& i) const {
marci@317	1901	// graph->next(i);
marci@317	1902	// return i;
marci@317	1903	// }
marci@317	1904	// InEdgeIt& next(InEdgeIt& i) const {
marci@317	1905	// graph->next(i);
marci@317	1906	// return i;
marci@317	1907	// }
marci@317	1908	// EdgeIt& next(EdgeIt& i) const {
marci@317	1909	// graph->next(i);
marci@317	1910	// return i;
marci@317	1911	// }
marci@317	1912
marci@317	1913	// // template<typename I> I& next(I &i) const {
marci@317	1914	// // graph->next(i);
marci@317	1915	// // return i;
marci@317	1916	// // }
marci@317	1917
marci@317	1918	// template< typename It > It first() const {
marci@317	1919	// It e; this->first(e); return e; }
marci@317	1920
marci@317	1921	// template< typename It > It first(const Node& v) const {
marci@317	1922	// It e; this->first(e, v); return e; }
marci@317	1923
marci@317	1924	// void erase(const OutEdgeIt& e) const {
marci@317	1925	// OutEdgeIt f=e;
marci@317	1926	// this->next(f);
marci@317	1927	// first_out_edges->set(this->tail(e), f);
marci@317	1928	// }
marci@317	1929	// };
marci@317	1930
marci@317	1931
marci@148	1932	// // FIXME: comparison should be made better!!!
marci@148	1933	// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
marci@148	1934	// class ResGraphWrapper
marci@148	1935	// {
marci@148	1936	// Graph* graph;
marci@76	1937
marci@148	1938	// public:
marci@303	1939	// typedef Graph ParentGraph;
marci@76	1940
marci@174	1941	// typedef typename Graph::Node Node;
marci@174	1942	// typedef typename Graph::Edge Edge;
marci@174	1943
marci@148	1944	// typedef typename Graph::NodeIt NodeIt;
marci@76	1945
marci@148	1946	// class OutEdgeIt {
marci@148	1947	// public:
marci@174	1948	// //Graph::Node n;
marci@148	1949	// bool out_or_in;
marci@148	1950	// typename Graph::OutEdgeIt o;
marci@148	1951	// typename Graph::InEdgeIt i;
marci@148	1952	// };
marci@148	1953	// class InEdgeIt {
marci@148	1954	// public:
marci@174	1955	// //Graph::Node n;
marci@148	1956	// bool out_or_in;
marci@148	1957	// typename Graph::OutEdgeIt o;
marci@148	1958	// typename Graph::InEdgeIt i;
marci@148	1959	// };
marci@148	1960	// typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@174	1961	// typedef typename Graph::EdgeIt EdgeIt;
marci@76	1962
marci@259	1963	// int nodeNum() const { return gw.nodeNum(); }
marci@259	1964	// int edgeNum() const { return gw.edgeNum(); }
marci@76	1965
marci@259	1966	// Node& first(Node& n) const { return gw.first(n); }
marci@76	1967
marci@174	1968	// // Edge and SymEdge is missing!!!!
marci@174	1969	// // Edge <-> In/OutEdgeIt conversion is missing!!!!
marci@76	1970
marci@148	1971	// //FIXME
marci@212	1972	// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
marci@148	1973	// {
marci@148	1974	// e.n=n;
marci@259	1975	// gw.first(e.o,n);
marci@259	1976	// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
marci@259	1977	// gw.goNext(e.o);
marci@259	1978	// if(!gw.valid(e.o)) {
marci@259	1979	// gw.first(e.i,n);
marci@259	1980	// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
marci@259	1981	// gw.goNext(e.i);
marci@148	1982	// }
marci@148	1983	// return e;
marci@148	1984	// }
marci@148	1985	// /*
marci@148	1986	// OutEdgeIt &goNext(OutEdgeIt &e)
marci@148	1987	// {
marci@259	1988	// if(gw.valid(e.o)) {
marci@259	1989	// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
marci@259	1990	// gw.goNext(e.o);
marci@259	1991	// if(gw.valid(e.o)) return e;
marci@259	1992	// else gw.first(e.i,e.n);
marci@148	1993	// }
marci@148	1994	// else {
marci@259	1995	// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
marci@259	1996	// gw.goNext(e.i);
marci@148	1997	// return e;
marci@148	1998	// }
marci@148	1999	// }
marci@148	2000	// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
marci@148	2001	// */
marci@259	2002	// //bool valid(const OutEdgeIt e) { return gw.valid(e.o)\|\|gw.valid(e.i);}
marci@76	2003
marci@148	2004	// //FIXME
marci@212	2005	// InEdgeIt& first(InEdgeIt& e, const Node& n) const
marci@148	2006	// {
marci@148	2007	// e.n=n;
marci@259	2008	// gw.first(e.i,n);
marci@259	2009	// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
marci@259	2010	// gw.goNext(e.i);
marci@259	2011	// if(!gw.valid(e.i)) {
marci@259	2012	// gw.first(e.o,n);
marci@259	2013	// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
marci@259	2014	// gw.goNext(e.o);
marci@148	2015	// }
marci@148	2016	// return e;
marci@148	2017	// }
marci@148	2018	// /*
marci@148	2019	// InEdgeIt &goNext(InEdgeIt &e)
marci@148	2020	// {
marci@259	2021	// if(gw.valid(e.i)) {
marci@259	2022	// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
marci@259	2023	// gw.goNext(e.i);
marci@259	2024	// if(gw.valid(e.i)) return e;
marci@259	2025	// else gw.first(e.o,e.n);
marci@148	2026	// }
marci@148	2027	// else {
marci@259	2028	// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
marci@259	2029	// gw.goNext(e.o);
marci@148	2030	// return e;
marci@148	2031	// }
marci@148	2032	// }
marci@148	2033	// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
marci@148	2034	// */
marci@259	2035	// //bool valid(const InEdgeIt e) { return gw.valid(e.i)\|\|gw.valid(e.o);}
marci@76	2036
marci@259	2037	// //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
marci@259	2038	// //template<typename I> I next(const I i); { return gw.goNext(i); }
marci@76	2039
marci@148	2040	// template< typename It > It first() const {
marci@212	2041	// It e; first(e); return e; }
marci@76	2042
marci@174	2043	// template< typename It > It first(Node v) const {
marci@212	2044	// It e; first(e, v); return e; }
marci@76	2045
marci@259	2046	// Node head(const Edge& e) const { return gw.head(e); }
marci@259	2047	// Node tail(const Edge& e) const { return gw.tail(e); }
marci@76	2048
marci@174	2049	// template<typename I> Node aNode(const I& e) const {
marci@259	2050	// return gw.aNode(e); }
marci@174	2051	// template<typename I> Node bNode(const I& e) const {
marci@259	2052	// return gw.bNode(e); }
marci@76	2053
marci@148	2054	// //template<typename I> bool valid(const I i);
marci@259	2055	// //{ return gw.valid(i); }
marci@76	2056
marci@148	2057	// //template<typename I> void setInvalid(const I &i);
marci@259	2058	// //{ return gw.setInvalid(i); }
marci@76	2059
marci@259	2060	// Node addNode() { return gw.addNode(); }
marci@174	2061	// Edge addEdge(const Node& tail, const Node& head) {
marci@259	2062	// return gw.addEdge(tail, head); }
marci@76	2063
marci@259	2064	// template<typename I> void erase(const I& i) { gw.erase(i); }
marci@76	2065
marci@259	2066	// void clear() { gw.clear(); }
marci@76	2067
marci@148	2068	// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
marci@148	2069	// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
marci@76	2070
marci@148	2071	// void setGraph(Graph& _graph) { graph = &_graph; }
marci@148	2072	// Graph& getGraph() { return (*graph); }
marci@76	2073
marci@148	2074	// //ResGraphWrapper() : graph(0) { }
marci@148	2075	// ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
marci@148	2076	// };
marci@76	2077
alpar@105	2078	} //namespace hugo
marci@76	2079
marci@259	2080	#endif //HUGO_GRAPH_WRAPPER_H
marci@76	2081

author	marci
	Thu, 15 Apr 2004 14:41:20 +0000
changeset 330	7ac0d4e8a31c
parent 323	58bc28afea63
child 335	999eb3cd7b49
permissions	-rw-r--r--