lemon-0.x: src/work/marci/graph_wrapper.h@7bec4e8fb7dd (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@317	465
marci@317	466	Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@317	467	Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@317	468	Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@317	469	Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@317	470
marci@311	471	// template<typename I> I& next(I &i) const {
marci@311	472	// graph->next(i);
marci@311	473	// // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
marci@311	474	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@311	475	// return i;
marci@311	476	// }
marci@263	477
marci@263	478	template< typename It > It first() const {
marci@263	479	It e; this->first(e); return e; }
marci@263	480
marci@263	481	template< typename It > It first(const Node& v) const {
marci@263	482	It e; this->first(e, v); return e; }
marci@263	483	};
marci@155	484
marci@317	485	// //Subgraph on the same node-set and partial edge-set
marci@317	486	// template<typename Graph, typename NodeFilterMap,
marci@317	487	// typename EdgeFilterMap>
marci@317	488	// class SubGraphWrapper : public GraphWrapper<Graph> {
marci@317	489	// protected:
marci@317	490	// NodeFilterMap* node_filter_map;
marci@317	491	// EdgeFilterMap* edge_filter_map;
marci@317	492	// public:
marci@317	493	// // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
marci@317	494	// SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
marci@317	495	// EdgeFilterMap& _edge_filter_map) :
marci@317	496	// GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
marci@317	497	// edge_filter_map(&_edge_filter_map) { }
marci@317	498
marci@317	499
marci@317	500	// typedef typename Graph::Node Node;
marci@317	501	// class NodeIt : public Graph::NodeIt {
marci@317	502	// // typedef typename Graph::NodeIt GraphNodeIt;
marci@317	503	// public:
marci@317	504	// NodeIt() { }
marci@317	505	// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
marci@317	506	// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
marci@317	507	// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
marci@317	508	// Graph::NodeIt(*(_G.graph)) {
marci@317	509	// while (_G.graph->valid((this)/.GraphNodeIt*/) &&
marci@317	510	// !((_G.node_filter_map))[(this)/.GraphNodeIt/])
marci@317	511	// _G.graph->next((this)/.GraphNodeIt*/);
marci@317	512	// }
marci@317	513	// };
marci@317	514	// typedef typename Graph::Edge Edge;
marci@317	515	// class OutEdgeIt : public Graph::OutEdgeIt {
marci@317	516	// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	517	// public:
marci@317	518	// OutEdgeIt() { }
marci@317	519	// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
marci@317	520	// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
marci@317	521	// OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
marci@317	522	// _G, const Node& n) :
marci@317	523	// Graph::OutEdgeIt(*(_G.graph), n) {
marci@317	524	// while (_G.graph->valid((this)/.GraphOutEdgeIt*/) &&
marci@317	525	// !((_G.edge_filter_map))[(this)/.GraphOutEdgeIt/])
marci@317	526	// _G.graph->next((this)/.GraphOutEdgeIt*/);
marci@317	527	// }
marci@317	528	// };
marci@317	529	// class InEdgeIt : public Graph::InEdgeIt {
marci@317	530	// // typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	531	// public:
marci@317	532	// InEdgeIt() { }
marci@317	533	// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
marci@317	534	// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
marci@317	535	// InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
marci@317	536	// const Node& n) :
marci@317	537	// Graph::InEdgeIt(*(_G.graph), n) {
marci@317	538	// while (_G.graph->valid((this)/.GraphInEdgeIt*/) &&
marci@317	539	// !((_G.edge_filter_map))[(this)/.GraphInEdgeIt/])
marci@317	540	// _G.graph->next((this)/.GraphInEdgeIt*/);
marci@317	541	// }
marci@317	542	// };
marci@317	543	// // //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@317	544	// class EdgeIt : public Graph::EdgeIt {
marci@317	545	// // typedef typename Graph::EdgeIt GraphEdgeIt;
marci@317	546	// public:
marci@317	547	// EdgeIt() { }
marci@317	548	// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
marci@317	549	// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
marci@317	550	// EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
marci@317	551	// Graph::EdgeIt(*(_G.graph)) {
marci@317	552	// while (_G.graph->valid((this)/.GraphEdgeIt*/) &&
marci@317	553	// !((_G.edge_filter_map))[(this)/.GraphEdgeIt/])
marci@317	554	// _G.graph->next((this)/.GraphEdgeIt*/);
marci@317	555	// }
marci@317	556	// };
marci@317	557
marci@317	558	// NodeIt& first(NodeIt& i) const {
marci@317	559	// i=NodeIt(*this);
marci@317	560	// return i;
marci@317	561	// }
marci@317	562	// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
marci@317	563	// i=OutEdgeIt(*this, n);
marci@317	564	// return i;
marci@317	565	// }
marci@317	566	// InEdgeIt& first(InEdgeIt& i, const Node& n) const {
marci@317	567	// i=InEdgeIt(*this, n);
marci@317	568	// return i;
marci@317	569	// }
marci@317	570	// EdgeIt& first(EdgeIt& i) const {
marci@317	571	// i=EdgeIt(*this);
marci@317	572	// return i;
marci@317	573	// }
marci@317	574
marci@317	575	// // template<typename I> I& first(I& i) const {
marci@317	576	// // graph->first(i);
marci@317	577	// // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
marci@317	578	// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	579	// // return i;
marci@317	580	// // }
marci@317	581	// // template<typename I, typename P> I& first(I& i, const P& p) const {
marci@317	582	// // graph->first(i, p);
marci@317	583	// // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
marci@317	584	// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	585	// // return i;
marci@317	586	// // }
marci@317	587
marci@317	588	// NodeIt& next(NodeIt& i) const {
marci@317	589	// graph->next(i);
marci@317	590	// while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
marci@317	591	// return i;
marci@317	592	// }
marci@317	593	// OutEdgeIt& next(OutEdgeIt& i) const {
marci@317	594	// graph->next(i);
marci@317	595	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	596	// return i;
marci@317	597	// }
marci@317	598	// InEdgeIt& next(InEdgeIt& i) const {
marci@317	599	// graph->next(i);
marci@317	600	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	601	// return i;
marci@317	602	// }
marci@317	603	// EdgeIt& next(EdgeIt& i) const {
marci@317	604	// graph->next(i);
marci@317	605	// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	606	// return i;
marci@317	607	// }
marci@317	608
marci@317	609	// // template<typename I> I& next(I &i) const {
marci@317	610	// // graph->next(i);
marci@317	611	// // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
marci@317	612	// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
marci@317	613	// // return i;
marci@317	614	// // }
marci@317	615
marci@317	616	// template< typename It > It first() const {
marci@317	617	// It e; this->first(e); return e; }
marci@317	618
marci@317	619	// template< typename It > It first(const Node& v) const {
marci@317	620	// It e; this->first(e, v); return e; }
marci@317	621	// };
marci@317	622
marci@303	623	template<typename Graph>
marci@303	624	class UndirGraphWrapper : public GraphWrapper<Graph> {
marci@317	625	// protected:
marci@317	626	// typedef typename Graph::Edge GraphEdge;
marci@317	627	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	628	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@303	629	public:
marci@303	630	typedef typename GraphWrapper<Graph>::Node Node;
marci@303	631	typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@317	632	typedef typename GraphWrapper<Graph>::Edge Edge;
marci@317	633	typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
marci@236	634
marci@303	635	// UndirGraphWrapper() : GraphWrapper<Graph>() { }
marci@303	636	UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
marci@158	637
marci@317	638
marci@317	639	// class Edge {
marci@317	640	// friend class UndirGraphWrapper<Graph>;
marci@317	641	// protected:
marci@317	642	// bool out_or_in; //true iff out
marci@317	643	// GraphOutEdgeIt out;
marci@317	644	// GraphInEdgeIt in;
marci@317	645	// public:
marci@317	646	// Edge() : out_or_in(), out(), in() { }
marci@317	647	// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
marci@317	648	// operator GraphEdge() const {
marci@317	649	// if (out_or_in) return(out); else return(in);
marci@317	650	// }
marci@317	651	// //FIXME
marci@317	652	// //2 edges are equal if they "refer" to the same physical edge
marci@317	653	// //is it good?
marci@317	654	// friend bool operator==(const Edge& u, const Edge& v) {
marci@317	655	// if (v.out_or_in)
marci@317	656	// if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
marci@317	657	// //return (u.out_or_in && u.out==v.out);
marci@317	658	// else
marci@317	659	// if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
marci@317	660	// //return (!u.out_or_in && u.in==v.in);
marci@317	661	// }
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	// };
marci@317	671
marci@317	672	class OutEdgeIt {
marci@303	673	friend class UndirGraphWrapper<Graph>;
marci@158	674	bool out_or_in; //true iff out
marci@317	675	typename Graph::OutEdgeIt out;
marci@317	676	typename Graph::InEdgeIt in;
marci@158	677	public:
marci@317	678	OutEdgeIt() { }
marci@317	679	OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@317	680	OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
marci@317	681	out_or_in=true; _G.graph->first(out, _n);
marci@317	682	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
marci@174	683	}
marci@317	684	operator Edge() const {
marci@317	685	if (out_or_in) return Edge(out); else return Edge(in);
marci@158	686	}
marci@158	687	};
marci@317	688	// class OutEdgeIt : public Edge {
marci@317	689	// friend class UndirGraphWrapper<Graph>;
marci@317	690	// public:
marci@317	691	// OutEdgeIt() : Edge() { }
marci@317	692	// OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@317	693	// OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
marci@317	694	// : Edge() {
marci@317	695	// out_or_in=true; _G.graph->first(out, n);
marci@317	696	// if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
marci@317	697	// }
marci@317	698	// };
marci@158	699
marci@317	700	//FIXME InEdgeIt
marci@238	701	typedef OutEdgeIt InEdgeIt;
marci@238	702
marci@317	703	// class EdgeIt : public Edge {
marci@317	704	// friend class UndirGraphWrapper<Graph>;
marci@317	705	// protected:
marci@317	706	// NodeIt v;
marci@317	707	// public:
marci@317	708	// EdgeIt() : Edge() { }
marci@317	709	// EdgeIt(const Invalid& i) : Edge(i) { }
marci@317	710	// EdgeIt(const UndirGraphWrapper<Graph>& _G)
marci@317	711	// : Edge() {
marci@317	712	// out_or_in=true;
marci@317	713	// //Node v;
marci@317	714	// _G.first(v);
marci@317	715	// if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
marci@317	716	// while (_G.valid(v) && !_G.graph->valid(out)) {
marci@317	717	// _G.graph->next(v);
marci@317	718	// if (_G.valid(v)) _G.graph->first(out);
marci@317	719	// }
marci@317	720	// }
marci@317	721	// };
marci@238	722
marci@317	723	NodeIt& first(NodeIt& i) const {
marci@317	724	i=NodeIt(*this); return i;
marci@158	725	}
marci@317	726	OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	727	i=OutEdgeIt(*this, p); return i;
marci@317	728	}
marci@317	729	//FIXME
marci@317	730	// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	731	// i=InEdgeIt(*this, p); return i;
marci@317	732	// }
marci@317	733	EdgeIt& first(EdgeIt& i) const {
marci@317	734	i=EdgeIt(*this); return i;
marci@238	735	}
marci@238	736
marci@303	737	template<typename I> I& first(I& i) const { graph->first(i); return i; }
marci@238	738	template<typename I, typename P> I& first(I& i, const P& p) const {
marci@303	739	graph->first(i, p); return i; }
marci@238	740
marci@317	741	NodeIt& next(NodeIt& n) const {
marci@317	742	GraphWrapper<Graph>::next(n);
marci@317	743	return n;
marci@317	744	}
marci@158	745	OutEdgeIt& next(OutEdgeIt& e) const {
marci@158	746	if (e.out_or_in) {
marci@317	747	typename Graph::Node n=graph->tail(e.out);
marci@303	748	graph->next(e.out);
marci@303	749	if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
marci@158	750	} else {
marci@303	751	graph->next(e.in);
marci@158	752	}
marci@158	753	return e;
marci@158	754	}
marci@317	755	//FIXME InEdgeIt
marci@238	756	EdgeIt& next(EdgeIt& e) const {
marci@317	757	GraphWrapper<Graph>::next(n);
marci@317	758	// graph->next(e.e);
marci@238	759	return e;
marci@238	760	}
marci@158	761
marci@317	762	// template<typename I> I& next(I &i) const { graph->next(i); return i; }
marci@158	763	template< typename It > It first() const {
marci@303	764	It e; this->first(e); return e; }
marci@158	765
marci@174	766	template< typename It > It first(const Node& v) const {
marci@303	767	It e; this->first(e, v); return e; }
marci@158	768
marci@238	769	// Node head(const Edge& e) const { return gw.head(e); }
marci@238	770	// Node tail(const Edge& e) const { return gw.tail(e); }
marci@158	771
marci@238	772	// template<typename I> bool valid(const I& i) const
marci@238	773	// { return gw.valid(i); }
marci@158	774
marci@238	775	// int nodeNum() const { return gw.nodeNum(); }
marci@238	776	// int edgeNum() const { return gw.edgeNum(); }
marci@158	777
marci@174	778	// template<typename I> Node aNode(const I& e) const {
marci@158	779	// return graph->aNode(e); }
marci@174	780	// template<typename I> Node bNode(const I& e) const {
marci@158	781	// return graph->bNode(e); }
marci@238	782
marci@238	783	Node aNode(const OutEdgeIt& e) const {
marci@303	784	if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
marci@238	785	Node bNode(const OutEdgeIt& e) const {
marci@303	786	if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
marci@158	787
marci@238	788	// Node addNode() const { return gw.addNode(); }
marci@238	789
marci@231	790	// FIXME: ez igy nem jo, mert nem
marci@231	791	// Edge addEdge(const Node& tail, const Node& head) const {
marci@231	792	// return graph->addEdge(tail, head); }
marci@158	793
marci@238	794	// template<typename I> void erase(const I& i) const { gw.erase(i); }
marci@158	795
marci@238	796	// void clear() const { gw.clear(); }
marci@158	797
marci@303	798	// template<typename T> class NodeMap : public Graph::NodeMap<T> {
marci@238	799	// public:
marci@303	800	// NodeMap(const UndirGraphWrapper<Graph>& _G) :
marci@303	801	// Graph::NodeMap<T>(_G.gw) { }
marci@303	802	// NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
marci@303	803	// Graph::NodeMap<T>(_G.gw, a) { }
marci@238	804	// };
marci@168	805
marci@238	806	// template<typename T> class EdgeMap :
marci@303	807	// public GraphWrapperSkeleton<Graph>::EdgeMap<T> {
marci@238	808	// public:
marci@303	809	// EdgeMap(const UndirGraphWrapper<Graph>& _G) :
marci@303	810	// GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }
marci@303	811	// EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
marci@303	812	// Graph::EdgeMap<T>(_G.gw, a) { }
marci@238	813	// };
marci@238	814	};
marci@158	815
marci@158	816
marci@158	817
marci@236	818
marci@236	819
marci@155	820	// template<typename Graph>
marci@155	821	// class SymGraphWrapper
marci@155	822	// {
marci@155	823	// Graph* graph;
marci@76	824
marci@155	825	// public:
marci@303	826	// typedef Graph ParentGraph;
marci@155	827
marci@174	828	// typedef typename Graph::Node Node;
marci@174	829	// typedef typename Graph::Edge Edge;
marci@174	830
marci@155	831	// typedef typename Graph::NodeIt NodeIt;
marci@155	832
marci@155	833	// //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
marci@155	834	// //iranyitatlant, ami van
marci@155	835	// //mert csak 1 dolgot lehet be typedef-elni
marci@155	836	// typedef typename Graph::OutEdgeIt SymEdgeIt;
marci@155	837	// //typedef typename Graph::InEdgeIt SymEdgeIt;
marci@155	838	// //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@174	839	// typedef typename Graph::EdgeIt EdgeIt;
marci@155	840
marci@155	841	// int nodeNum() const { return graph->nodeNum(); }
marci@155	842	// int edgeNum() const { return graph->edgeNum(); }
marci@155	843
marci@212	844	// template<typename I> I& first(I& i) const { return graph->first(i); }
marci@212	845	// template<typename I, typename P> I& first(I& i, const P& p) const {
marci@212	846	// return graph->first(i, p); }
marci@155	847	// //template<typename I> I next(const I i); { return graph->goNext(i); }
marci@155	848	// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
marci@155	849
marci@155	850	// template< typename It > It first() const {
marci@212	851	// It e; first(e); return e; }
marci@155	852
marci@174	853	// template< typename It > It first(Node v) const {
marci@212	854	// It e; first(e, v); return e; }
marci@155	855
marci@174	856	// Node head(const Edge& e) const { return graph->head(e); }
marci@174	857	// Node tail(const Edge& e) const { return graph->tail(e); }
marci@155	858
marci@174	859	// template<typename I> Node aNode(const I& e) const {
marci@155	860	// return graph->aNode(e); }
marci@174	861	// template<typename I> Node bNode(const I& e) const {
marci@155	862	// return graph->bNode(e); }
marci@155	863
marci@155	864	// //template<typename I> bool valid(const I i);
marci@155	865	// //{ return graph->valid(i); }
marci@155	866
marci@155	867	// //template<typename I> void setInvalid(const I &i);
marci@155	868	// //{ return graph->setInvalid(i); }
marci@155	869
marci@174	870	// Node addNode() { return graph->addNode(); }
marci@174	871	// Edge addEdge(const Node& tail, const Node& head) {
marci@155	872	// return graph->addEdge(tail, head); }
marci@155	873
marci@155	874	// template<typename I> void erase(const I& i) { graph->erase(i); }
marci@155	875
marci@155	876	// void clear() { graph->clear(); }
marci@155	877
marci@155	878	// template<typename T> class NodeMap : public Graph::NodeMap<T> { };
marci@155	879	// template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
marci@155	880
marci@155	881	// void setGraph(Graph& _graph) { graph = &_graph; }
marci@155	882	// Graph& getGraph() { return (*graph); }
marci@155	883
marci@155	884	// //SymGraphWrapper() : graph(0) { }
marci@155	885	// SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
marci@155	886	// };
marci@155	887
marci@155	888
marci@317	889
marci@317	890
marci@303	891	template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@311	892	class ResGraphWrapper : public GraphWrapper<Graph> {
marci@199	893	protected:
marci@317	894	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	895	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	896	// typedef typename Graph::Edge GraphEdge;
marci@155	897	FlowMap* flow;
marci@155	898	const CapacityMap* capacity;
marci@155	899	public:
marci@168	900
marci@303	901	ResGraphWrapper(Graph& _graph, FlowMap& _flow,
marci@266	902	const CapacityMap& _capacity) :
marci@303	903	GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
marci@168	904
marci@174	905	class Edge;
marci@155	906	class OutEdgeIt;
marci@174	907	friend class Edge;
marci@155	908	friend class OutEdgeIt;
marci@76	909
marci@311	910	typedef typename GraphWrapper<Graph>::Node Node;
marci@311	911	typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@317	912	class Edge : public Graph::Edge {
marci@303	913	friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@155	914	protected:
marci@317	915	bool forward; //true, iff forward
marci@317	916	// typename Graph::Edge e;
marci@155	917	public:
marci@317	918	Edge() { }
marci@317	919	Edge(const typename Graph::Edge& _e, bool _forward) :
marci@317	920	Graph::Edge(_e), forward(_forward) { }
marci@317	921	Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
marci@317	922	//the unique invalid iterator
marci@174	923	friend bool operator==(const Edge& u, const Edge& v) {
marci@317	924	return (v.forward==u.forward &&
marci@317	925	static_cast<typename Graph::Edge>(u)==
marci@317	926	static_cast<typename Graph::Edge>(v));
marci@174	927	}
marci@174	928	friend bool operator!=(const Edge& u, const Edge& v) {
marci@317	929	return (v.forward!=u.forward \|\|
marci@317	930	static_cast<typename Graph::Edge>(u)!=
marci@317	931	static_cast<typename Graph::Edge>(v));
marci@174	932	}
marci@155	933	};
marci@317	934	// class Edge {
marci@317	935	// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	936	// protected:
marci@317	937	// bool out_or_in; //true, iff out
marci@317	938	// GraphOutEdgeIt out;
marci@317	939	// GraphInEdgeIt in;
marci@317	940	// public:
marci@317	941	// Edge() : out_or_in(true) { }
marci@317	942	// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
marci@317	943	// // bool valid() const {
marci@317	944	// // return out_or_in && out.valid() \|\| in.valid(); }
marci@317	945	// friend bool operator==(const Edge& u, const Edge& v) {
marci@317	946	// if (v.out_or_in)
marci@317	947	// return (u.out_or_in && u.out==v.out);
marci@317	948	// else
marci@317	949	// return (!u.out_or_in && u.in==v.in);
marci@317	950	// }
marci@317	951	// friend bool operator!=(const Edge& u, const Edge& v) {
marci@317	952	// if (v.out_or_in)
marci@317	953	// return (!u.out_or_in \|\| u.out!=v.out);
marci@317	954	// else
marci@317	955	// return (u.out_or_in \|\| u.in!=v.in);
marci@317	956	// }
marci@317	957	// operator GraphEdge() const {
marci@317	958	// if (out_or_in) return(out); else return(in);
marci@317	959	// }
marci@317	960	// };
marci@317	961	class OutEdgeIt {
marci@303	962	friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	963	protected:
marci@317	964	typename Graph::OutEdgeIt out;
marci@317	965	typename Graph::InEdgeIt in;
marci@317	966	bool forward;
marci@155	967	public:
marci@155	968	OutEdgeIt() { }
marci@168	969	//FIXME
marci@317	970	// OutEdgeIt(const Edge& e) : Edge(e) { }
marci@317	971	OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
marci@317	972	//the unique invalid iterator
marci@317	973	OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
marci@317	974	forward=true;
marci@303	975	resG.graph->first(out, v);
marci@317	976	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
marci@303	977	if (!resG.graph->valid(out)) {
marci@317	978	forward=false;
marci@303	979	resG.graph->first(in, v);
marci@317	980	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
marci@155	981	}
marci@155	982	}
marci@317	983	operator Edge() const {
marci@317	984	// Edge e;
marci@317	985	// e.forward=this->forward;
marci@317	986	// if (this->forward) e=out; else e=in;
marci@317	987	// return e;
marci@317	988	if (this->forward)
marci@317	989	return Edge(out, this->forward);
marci@317	990	else
marci@317	991	return Edge(in, this->forward);
marci@317	992	}
marci@317	993	};
marci@317	994	// class OutEdgeIt : public Edge {
marci@317	995	// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	996	// public:
marci@317	997	// OutEdgeIt() { }
marci@317	998	// //FIXME
marci@317	999	// OutEdgeIt(const Edge& e) : Edge(e) { }
marci@317	1000	// OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@317	1001	// OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
marci@317	1002	// resG.graph->first(out, v);
marci@317	1003	// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1004	// if (!resG.graph->valid(out)) {
marci@317	1005	// out_or_in=0;
marci@317	1006	// resG.graph->first(in, v);
marci@317	1007	// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1008	// }
marci@317	1009	// }
marci@168	1010	// public:
marci@168	1011	// OutEdgeIt& operator++() {
marci@168	1012	// if (out_or_in) {
marci@174	1013	// Node v=/resG->/G->aNode(out);
marci@168	1014	// ++out;
marci@269	1015	// while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@168	1016	// if (!out.valid()) {
marci@168	1017	// out_or_in=0;
marci@212	1018	// G->first(in, v);
marci@269	1019	// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1020	// }
marci@168	1021	// } else {
marci@168	1022	// ++in;
marci@269	1023	// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1024	// }
marci@168	1025	// return *this;
marci@168	1026	// }
marci@317	1027	// };
marci@155	1028
marci@263	1029	//FIXME This is just for having InEdgeIt
marci@311	1030	// class InEdgeIt : public Edge { };
marci@263	1031
marci@317	1032	class InEdgeIt {
marci@303	1033	friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	1034	protected:
marci@317	1035	typename Graph::OutEdgeIt out;
marci@317	1036	typename Graph::InEdgeIt in;
marci@317	1037	bool forward;
marci@317	1038	public:
marci@317	1039	InEdgeIt() { }
marci@317	1040	//FIXME
marci@317	1041	// OutEdgeIt(const Edge& e) : Edge(e) { }
marci@317	1042	InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
marci@317	1043	//the unique invalid iterator
marci@317	1044	InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
marci@317	1045	forward=true;
marci@317	1046	resG.graph->first(in, v);
marci@317	1047	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
marci@317	1048	if (!resG.graph->valid(in)) {
marci@317	1049	forward=false;
marci@317	1050	resG.graph->first(out, v);
marci@317	1051	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
marci@317	1052	}
marci@317	1053	}
marci@317	1054	operator Edge() const {
marci@317	1055	// Edge e;
marci@317	1056	// e.forward=this->forward;
marci@317	1057	// if (this->forward) e=out; else e=in;
marci@317	1058	// return e;
marci@317	1059	if (this->forward)
marci@317	1060	return Edge(in, this->forward);
marci@317	1061	else
marci@317	1062	return Edge(out, this->forward);
marci@317	1063	}
marci@317	1064	};
marci@317	1065
marci@317	1066	class EdgeIt {
marci@317	1067	friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	1068	protected:
marci@317	1069	typename Graph::EdgeIt e;
marci@317	1070	bool forward;
marci@155	1071	public:
marci@174	1072	EdgeIt() { }
marci@317	1073	EdgeIt(const Invalid& i) : e(i), forward(false) { }
marci@317	1074	EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) {
marci@317	1075	forward=true;
marci@317	1076	resG.graph->first(e);
marci@317	1077	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
marci@317	1078	if (!resG.graph->valid(e)) {
marci@317	1079	forward=false;
marci@317	1080	resG.graph->first(e);
marci@317	1081	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
marci@155	1082	}
marci@155	1083	}
marci@317	1084	operator Edge() const {
marci@317	1085	return Edge(e, this->forward);
marci@317	1086	}
marci@317	1087	};
marci@317	1088	// class EdgeIt : public Edge {
marci@317	1089	// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	1090	// NodeIt v;
marci@317	1091	// public:
marci@317	1092	// EdgeIt() { }
marci@317	1093	// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
marci@317	1094	// EdgeIt(const Invalid& i) : Edge(i) { }
marci@317	1095	// EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
marci@317	1096	// resG.graph->first(v);
marci@317	1097	// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
marci@317	1098	// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1099	// while (resG.graph->valid(v) && !resG.graph->valid(out)) {
marci@317	1100	// resG.graph->next(v);
marci@317	1101	// if (resG.graph->valid(v)) resG.graph->first(out, v);
marci@317	1102	// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1103	// }
marci@317	1104	// if (!resG.graph->valid(out)) {
marci@317	1105	// out_or_in=0;
marci@317	1106	// resG.graph->first(v);
marci@317	1107	// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
marci@317	1108	// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1109	// while (resG.graph->valid(v) && !resG.graph->valid(in)) {
marci@317	1110	// resG.graph->next(v);
marci@317	1111	// if (resG.graph->valid(v)) resG.graph->first(in, v);
marci@317	1112	// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1113	// }
marci@317	1114	// }
marci@317	1115	// }
marci@174	1116	// EdgeIt& operator++() {
marci@168	1117	// if (out_or_in) {
marci@168	1118	// ++out;
marci@269	1119	// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@168	1120	// while (v.valid() && !out.valid()) {
marci@168	1121	// ++v;
marci@212	1122	// if (v.valid()) G->first(out, v);
marci@269	1123	// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@168	1124	// }
marci@168	1125	// if (!out.valid()) {
marci@168	1126	// out_or_in=0;
marci@212	1127	// G->first(v);
marci@303	1128	// if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
marci@269	1129	// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1130	// while (v.valid() && !in.valid()) {
marci@168	1131	// ++v;
marci@212	1132	// if (v.valid()) G->first(in, v);
marci@269	1133	// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@168	1134	// }
marci@168	1135	// }
marci@168	1136	// } else {
marci@168	1137	// ++in;
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	// return *this;
marci@168	1146	// }
marci@317	1147	// };
marci@155	1148
marci@311	1149	NodeIt& first(NodeIt& i) const {
marci@317	1150	i=NodeIt(*this); return i;
marci@155	1151	}
marci@311	1152	OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	1153	i=OutEdgeIt(*this, p); return i;
marci@311	1154	}
marci@317	1155	// FIXME not tested
marci@317	1156	InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	1157	i=InEdgeIt(*this, p); return i;
marci@317	1158	}
marci@317	1159	EdgeIt& first(EdgeIt& i) const {
marci@317	1160	i=EdgeIt(*this); return i;
marci@155	1161	}
marci@155	1162
marci@317	1163	NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
marci@155	1164	OutEdgeIt& next(OutEdgeIt& e) const {
marci@317	1165	if (e.forward) {
marci@303	1166	Node v=graph->aNode(e.out);
marci@303	1167	graph->next(e.out);
marci@317	1168	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
marci@303	1169	if (!graph->valid(e.out)) {
marci@317	1170	e.forward=false;
marci@303	1171	graph->first(e.in, v);
marci@317	1172	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
marci@155	1173	}
marci@155	1174	} else {
marci@303	1175	graph->next(e.in);
marci@317	1176	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
marci@155	1177	}
marci@155	1178	return e;
marci@155	1179	}
marci@317	1180	// FIXME Not tested
marci@317	1181	InEdgeIt& next(InEdgeIt& e) const {
marci@317	1182	if (e.forward) {
marci@317	1183	Node v=graph->aNode(e.in);
marci@317	1184	graph->next(e.in);
marci@317	1185	while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
marci@317	1186	if (!graph->valid(e.in)) {
marci@317	1187	e.forward=false;
marci@317	1188	graph->first(e.out, v);
marci@317	1189	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
marci@317	1190	}
marci@317	1191	} else {
marci@303	1192	graph->next(e.out);
marci@317	1193	while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
marci@317	1194	}
marci@317	1195	return e;
marci@317	1196	}
marci@317	1197	EdgeIt& next(EdgeIt& e) const {
marci@317	1198	if (e.forward) {
marci@317	1199	graph->next(e.e);
marci@317	1200	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
marci@317	1201	if (!graph->valid(e.e)) {
marci@317	1202	e.forward=false;
marci@317	1203	graph->first(e.e);
marci@317	1204	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
marci@155	1205	}
marci@317	1206	} else {
marci@317	1207	graph->next(e.e);
marci@317	1208	while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
marci@155	1209	}
marci@317	1210	return e;
marci@317	1211	}
marci@317	1212	// EdgeIt& next(EdgeIt& e) const {
marci@317	1213	// if (e.out_or_in) {
marci@317	1214	// graph->next(e.out);
marci@317	1215	// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1216	// while (graph->valid(e.v) && !graph->valid(e.out)) {
marci@317	1217	// graph->next(e.v);
marci@317	1218	// if (graph->valid(e.v)) graph->first(e.out, e.v);
marci@317	1219	// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1220	// }
marci@317	1221	// if (!graph->valid(e.out)) {
marci@317	1222	// e.out_or_in=0;
marci@317	1223	// graph->first(e.v);
marci@317	1224	// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
marci@317	1225	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1226	// while (graph->valid(e.v) && !graph->valid(e.in)) {
marci@317	1227	// graph->next(e.v);
marci@317	1228	// if (graph->valid(e.v)) graph->first(e.in, e.v);
marci@317	1229	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1230	// }
marci@317	1231	// }
marci@317	1232	// } else {
marci@317	1233	// graph->next(e.in);
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	// return e;
marci@317	1242	// }
marci@76	1243
marci@76	1244
marci@155	1245	template< typename It >
marci@155	1246	It first() const {
marci@155	1247	It e;
marci@212	1248	first(e);
marci@155	1249	return e;
marci@155	1250	}
marci@76	1251
marci@155	1252	template< typename It >
marci@174	1253	It first(Node v) const {
marci@155	1254	It e;
marci@212	1255	first(e, v);
marci@155	1256	return e;
marci@155	1257	}
marci@76	1258
marci@174	1259	Node tail(Edge e) const {
marci@317	1260	return ((e.forward) ? graph->tail(e) : graph->head(e)); }
marci@174	1261	Node head(Edge e) const {
marci@317	1262	return ((e.forward) ? graph->head(e) : graph->tail(e)); }
marci@76	1263
marci@174	1264	Node aNode(OutEdgeIt e) const {
marci@317	1265	return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
marci@174	1266	Node bNode(OutEdgeIt e) const {
marci@317	1267	return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
marci@76	1268
marci@303	1269	int nodeNum() const { return graph->nodeNum(); }
marci@263	1270	//FIXME
marci@303	1271	//int edgeNum() const { return graph->edgeNum(); }
marci@263	1272
marci@263	1273
marci@317	1274	// int id(Node v) const { return graph->id(v); }
marci@155	1275
marci@317	1276	bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
marci@174	1277	bool valid(Edge e) const {
marci@317	1278	return graph->valid(e);
marci@317	1279	//return e.forward ? graph->valid(e.out) : graph->valid(e.in);
marci@317	1280	}
marci@155	1281
marci@174	1282	void augment(const Edge& e, Number a) const {
marci@317	1283	if (e.forward)
marci@303	1284	// flow->set(e.out, flow->get(e.out)+a);
marci@317	1285	flow->set(e, (*flow)[e]+a);
marci@168	1286	else
marci@303	1287	// flow->set(e.in, flow->get(e.in)-a);
marci@317	1288	flow->set(e, (*flow)[e]-a);
marci@168	1289	}
marci@168	1290
marci@269	1291	Number resCap(const Edge& e) const {
marci@317	1292	if (e.forward)
marci@303	1293	// return (capacity->get(e.out)-flow->get(e.out));
marci@317	1294	return ((capacity)[e]-(flow)[e]);
marci@168	1295	else
marci@303	1296	// return (flow->get(e.in));
marci@317	1297	return ((*flow)[e]);
marci@168	1298	}
marci@168	1299
marci@317	1300	// Number resCap(typename Graph::OutEdgeIt out) const {
marci@317	1301	// // return (capacity->get(out)-flow->get(out));
marci@317	1302	// return ((capacity)[out]-(flow)[out]);
marci@317	1303	// }
marci@168	1304
marci@317	1305	// Number resCap(typename Graph::InEdgeIt in) const {
marci@317	1306	// // return (flow->get(in));
marci@317	1307	// return ((*flow)[in]);
marci@317	1308	// }
marci@168	1309
marci@303	1310	// template<typename T> class NodeMap : public Graph::NodeMap<T> {
marci@266	1311	// public:
marci@303	1312	// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
marci@303	1313	// : Graph::NodeMap<T>(_G.gw) { }
marci@303	1314	// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
marci@303	1315	// T a) : Graph::NodeMap<T>(_G.gw, a) { }
marci@266	1316	// };
marci@155	1317
marci@155	1318	// template <typename T>
marci@155	1319	// class NodeMap {
marci@155	1320	// typename Graph::NodeMap<T> node_map;
marci@155	1321	// public:
marci@174	1322	// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
marci@174	1323	// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
marci@174	1324	// void set(Node nit, T a) { node_map.set(nit, a); }
marci@174	1325	// T get(Node nit) const { return node_map.get(nit); }
marci@155	1326	// };
marci@155	1327
marci@155	1328	template <typename T>
marci@155	1329	class EdgeMap {
marci@303	1330	typename Graph::EdgeMap<T> forward_map, backward_map;
marci@155	1331	public:
marci@303	1332	EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map((_G.graph)), backward_map((_G.graph)) { }
marci@303	1333	EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map((_G.graph), a), backward_map((_G.graph), a) { }
marci@174	1334	void set(Edge e, T a) {
marci@317	1335	if (e.forward)
marci@155	1336	forward_map.set(e.out, a);
marci@155	1337	else
marci@155	1338	backward_map.set(e.in, a);
marci@155	1339	}
marci@303	1340	T operator[](Edge e) const {
marci@317	1341	if (e.forward)
marci@303	1342	return forward_map[e.out];
marci@155	1343	else
marci@303	1344	return backward_map[e.in];
marci@155	1345	}
marci@303	1346	// T get(Edge e) const {
marci@303	1347	// if (e.out_or_in)
marci@303	1348	// return forward_map.get(e.out);
marci@303	1349	// else
marci@303	1350	// return backward_map.get(e.in);
marci@303	1351	// }
marci@155	1352	};
marci@168	1353	};
marci@168	1354
marci@317	1355
marci@317	1356
marci@317	1357	// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@317	1358	// class ResGraphWrapper : public GraphWrapper<Graph> {
marci@317	1359	// protected:
marci@317	1360	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	1361	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	1362	// typedef typename Graph::Edge GraphEdge;
marci@317	1363	// FlowMap* flow;
marci@317	1364	// const CapacityMap* capacity;
marci@317	1365	// public:
marci@317	1366
marci@317	1367	// ResGraphWrapper(Graph& _graph, FlowMap& _flow,
marci@317	1368	// const CapacityMap& _capacity) :
marci@317	1369	// GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
marci@317	1370
marci@317	1371	// class Edge;
marci@317	1372	// class OutEdgeIt;
marci@317	1373	// friend class Edge;
marci@317	1374	// friend class OutEdgeIt;
marci@317	1375
marci@317	1376	// typedef typename GraphWrapper<Graph>::Node Node;
marci@317	1377	// typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@317	1378	// class Edge {
marci@317	1379	// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	1380	// protected:
marci@317	1381	// bool out_or_in; //true, iff out
marci@317	1382	// GraphOutEdgeIt out;
marci@317	1383	// GraphInEdgeIt in;
marci@317	1384	// public:
marci@317	1385	// Edge() : out_or_in(true) { }
marci@317	1386	// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
marci@317	1387	// // bool valid() const {
marci@317	1388	// // return out_or_in && out.valid() \|\| in.valid(); }
marci@317	1389	// friend bool operator==(const Edge& u, const Edge& v) {
marci@317	1390	// if (v.out_or_in)
marci@317	1391	// return (u.out_or_in && u.out==v.out);
marci@317	1392	// else
marci@317	1393	// return (!u.out_or_in && u.in==v.in);
marci@317	1394	// }
marci@317	1395	// friend bool operator!=(const Edge& u, const Edge& v) {
marci@317	1396	// if (v.out_or_in)
marci@317	1397	// return (!u.out_or_in \|\| u.out!=v.out);
marci@317	1398	// else
marci@317	1399	// return (u.out_or_in \|\| u.in!=v.in);
marci@317	1400	// }
marci@317	1401	// operator GraphEdge() const {
marci@317	1402	// if (out_or_in) return(out); else return(in);
marci@317	1403	// }
marci@317	1404	// };
marci@317	1405	// class OutEdgeIt : public Edge {
marci@317	1406	// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	1407	// public:
marci@317	1408	// OutEdgeIt() { }
marci@317	1409	// //FIXME
marci@317	1410	// OutEdgeIt(const Edge& e) : Edge(e) { }
marci@317	1411	// OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@317	1412	// OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
marci@317	1413	// resG.graph->first(out, v);
marci@317	1414	// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1415	// if (!resG.graph->valid(out)) {
marci@317	1416	// out_or_in=0;
marci@317	1417	// resG.graph->first(in, v);
marci@317	1418	// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1419	// }
marci@317	1420	// }
marci@317	1421	// // public:
marci@317	1422	// // OutEdgeIt& operator++() {
marci@317	1423	// // if (out_or_in) {
marci@317	1424	// // Node v=/resG->/G->aNode(out);
marci@317	1425	// // ++out;
marci@317	1426	// // while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@317	1427	// // if (!out.valid()) {
marci@317	1428	// // out_or_in=0;
marci@317	1429	// // G->first(in, v);
marci@317	1430	// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1431	// // }
marci@317	1432	// // } else {
marci@317	1433	// // ++in;
marci@317	1434	// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1435	// // }
marci@317	1436	// // return *this;
marci@317	1437	// // }
marci@317	1438	// };
marci@317	1439
marci@317	1440	// //FIXME This is just for having InEdgeIt
marci@317	1441	// // class InEdgeIt : public Edge { };
marci@317	1442
marci@317	1443	// class EdgeIt : public Edge {
marci@317	1444	// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
marci@317	1445	// NodeIt v;
marci@317	1446	// public:
marci@317	1447	// EdgeIt() { }
marci@317	1448	// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
marci@317	1449	// EdgeIt(const Invalid& i) : Edge(i) { }
marci@317	1450	// EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
marci@317	1451	// resG.graph->first(v);
marci@317	1452	// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
marci@317	1453	// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1454	// while (resG.graph->valid(v) && !resG.graph->valid(out)) {
marci@317	1455	// resG.graph->next(v);
marci@317	1456	// if (resG.graph->valid(v)) resG.graph->first(out, v);
marci@317	1457	// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
marci@317	1458	// }
marci@317	1459	// if (!resG.graph->valid(out)) {
marci@317	1460	// out_or_in=0;
marci@317	1461	// resG.graph->first(v);
marci@317	1462	// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
marci@317	1463	// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1464	// while (resG.graph->valid(v) && !resG.graph->valid(in)) {
marci@317	1465	// resG.graph->next(v);
marci@317	1466	// if (resG.graph->valid(v)) resG.graph->first(in, v);
marci@317	1467	// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
marci@317	1468	// }
marci@317	1469	// }
marci@317	1470	// }
marci@317	1471	// // EdgeIt& operator++() {
marci@317	1472	// // if (out_or_in) {
marci@317	1473	// // ++out;
marci@317	1474	// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@317	1475	// // while (v.valid() && !out.valid()) {
marci@317	1476	// // ++v;
marci@317	1477	// // if (v.valid()) G->first(out, v);
marci@317	1478	// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
marci@317	1479	// // }
marci@317	1480	// // if (!out.valid()) {
marci@317	1481	// // out_or_in=0;
marci@317	1482	// // G->first(v);
marci@317	1483	// // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
marci@317	1484	// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1485	// // while (v.valid() && !in.valid()) {
marci@317	1486	// // ++v;
marci@317	1487	// // if (v.valid()) G->first(in, v);
marci@317	1488	// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
marci@317	1489	// // }
marci@317	1490	// // }
marci@317	1491	// // } else {
marci@317	1492	// // ++in;
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	// // return *this;
marci@317	1501	// // }
marci@317	1502	// };
marci@317	1503
marci@317	1504	// NodeIt& first(NodeIt& i) const {
marci@317	1505	// i=NodeIt(*this);
marci@317	1506	// return i;
marci@317	1507	// }
marci@317	1508	// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	1509	// i=OutEdgeIt(*this, p);
marci@317	1510	// return i;
marci@317	1511	// }
marci@317	1512	// //FIXME Not yet implemented
marci@317	1513	// //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	1514	// //i=InEdgeIt(*this, p);
marci@317	1515	// // return i;
marci@317	1516	// //}
marci@317	1517	// EdgeIt& first(EdgeIt& e) const {
marci@317	1518	// e=EdgeIt(*this);
marci@317	1519	// return e;
marci@317	1520	// }
marci@317	1521
marci@317	1522	// NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
marci@317	1523	// OutEdgeIt& next(OutEdgeIt& e) const {
marci@317	1524	// if (e.out_or_in) {
marci@317	1525	// Node v=graph->aNode(e.out);
marci@317	1526	// graph->next(e.out);
marci@317	1527	// while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1528	// if (!graph->valid(e.out)) {
marci@317	1529	// e.out_or_in=0;
marci@317	1530	// graph->first(e.in, v);
marci@317	1531	// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1532	// }
marci@317	1533	// } else {
marci@317	1534	// graph->next(e.in);
marci@317	1535	// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1536	// }
marci@317	1537	// return e;
marci@317	1538	// }
marci@317	1539	// //FIXME Not yet implemented
marci@317	1540	// //InEdgeIt& next(InEdgeIt& e) const {
marci@317	1541	// // return e;
marci@317	1542	// //}
marci@317	1543	// EdgeIt& next(EdgeIt& e) const {
marci@317	1544	// if (e.out_or_in) {
marci@317	1545	// graph->next(e.out);
marci@317	1546	// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1547	// while (graph->valid(e.v) && !graph->valid(e.out)) {
marci@317	1548	// graph->next(e.v);
marci@317	1549	// if (graph->valid(e.v)) graph->first(e.out, e.v);
marci@317	1550	// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
marci@317	1551	// }
marci@317	1552	// if (!graph->valid(e.out)) {
marci@317	1553	// e.out_or_in=0;
marci@317	1554	// graph->first(e.v);
marci@317	1555	// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
marci@317	1556	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1557	// while (graph->valid(e.v) && !graph->valid(e.in)) {
marci@317	1558	// graph->next(e.v);
marci@317	1559	// if (graph->valid(e.v)) graph->first(e.in, e.v);
marci@317	1560	// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
marci@317	1561	// }
marci@317	1562	// }
marci@317	1563	// } else {
marci@317	1564	// graph->next(e.in);
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	// return e;
marci@317	1573	// }
marci@317	1574
marci@317	1575
marci@317	1576	// template< typename It >
marci@317	1577	// It first() const {
marci@317	1578	// It e;
marci@317	1579	// first(e);
marci@317	1580	// return e;
marci@317	1581	// }
marci@317	1582
marci@317	1583	// template< typename It >
marci@317	1584	// It first(Node v) const {
marci@317	1585	// It e;
marci@317	1586	// first(e, v);
marci@317	1587	// return e;
marci@317	1588	// }
marci@317	1589
marci@317	1590	// Node tail(Edge e) const {
marci@317	1591	// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
marci@317	1592	// Node head(Edge e) const {
marci@317	1593	// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
marci@317	1594
marci@317	1595	// Node aNode(OutEdgeIt e) const {
marci@317	1596	// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
marci@317	1597	// Node bNode(OutEdgeIt e) const {
marci@317	1598	// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
marci@317	1599
marci@317	1600	// int nodeNum() const { return graph->nodeNum(); }
marci@317	1601	// //FIXME
marci@317	1602	// //int edgeNum() const { return graph->edgeNum(); }
marci@317	1603
marci@317	1604
marci@317	1605	// int id(Node v) const { return graph->id(v); }
marci@317	1606
marci@317	1607	// bool valid(Node n) const { return graph->valid(n); }
marci@317	1608	// bool valid(Edge e) const {
marci@317	1609	// return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
marci@317	1610
marci@317	1611	// void augment(const Edge& e, Number a) const {
marci@317	1612	// if (e.out_or_in)
marci@317	1613	// // flow->set(e.out, flow->get(e.out)+a);
marci@317	1614	// flow->set(e.out, (*flow)[e.out]+a);
marci@317	1615	// else
marci@317	1616	// // flow->set(e.in, flow->get(e.in)-a);
marci@317	1617	// flow->set(e.in, (*flow)[e.in]-a);
marci@317	1618	// }
marci@317	1619
marci@317	1620	// Number resCap(const Edge& e) const {
marci@317	1621	// if (e.out_or_in)
marci@317	1622	// // return (capacity->get(e.out)-flow->get(e.out));
marci@317	1623	// return ((capacity)[e.out]-(flow)[e.out]);
marci@317	1624	// else
marci@317	1625	// // return (flow->get(e.in));
marci@317	1626	// return ((*flow)[e.in]);
marci@317	1627	// }
marci@317	1628
marci@317	1629	// Number resCap(GraphOutEdgeIt out) const {
marci@317	1630	// // return (capacity->get(out)-flow->get(out));
marci@317	1631	// return ((capacity)[out]-(flow)[out]);
marci@317	1632	// }
marci@317	1633
marci@317	1634	// Number resCap(GraphInEdgeIt in) const {
marci@317	1635	// // return (flow->get(in));
marci@317	1636	// return ((*flow)[in]);
marci@317	1637	// }
marci@317	1638
marci@317	1639	// // template<typename T> class NodeMap : public Graph::NodeMap<T> {
marci@317	1640	// // public:
marci@317	1641	// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
marci@317	1642	// // : Graph::NodeMap<T>(_G.gw) { }
marci@317	1643	// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
marci@317	1644	// // T a) : Graph::NodeMap<T>(_G.gw, a) { }
marci@317	1645	// // };
marci@317	1646
marci@317	1647	// // template <typename T>
marci@317	1648	// // class NodeMap {
marci@317	1649	// // typename Graph::NodeMap<T> node_map;
marci@317	1650	// // public:
marci@317	1651	// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
marci@317	1652	// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
marci@317	1653	// // void set(Node nit, T a) { node_map.set(nit, a); }
marci@317	1654	// // T get(Node nit) const { return node_map.get(nit); }
marci@317	1655	// // };
marci@317	1656
marci@317	1657	// template <typename T>
marci@317	1658	// class EdgeMap {
marci@317	1659	// typename Graph::EdgeMap<T> forward_map, backward_map;
marci@317	1660	// public:
marci@317	1661	// EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map((_G.graph)), backward_map((_G.graph)) { }
marci@317	1662	// EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map((_G.graph), a), backward_map((_G.graph), a) { }
marci@317	1663	// void set(Edge e, T a) {
marci@317	1664	// if (e.out_or_in)
marci@317	1665	// forward_map.set(e.out, a);
marci@317	1666	// else
marci@317	1667	// backward_map.set(e.in, a);
marci@317	1668	// }
marci@317	1669	// T operator[](Edge e) const {
marci@317	1670	// if (e.out_or_in)
marci@317	1671	// return forward_map[e.out];
marci@317	1672	// else
marci@317	1673	// return backward_map[e.in];
marci@317	1674	// }
marci@317	1675	// // T get(Edge e) const {
marci@317	1676	// // if (e.out_or_in)
marci@317	1677	// // return forward_map.get(e.out);
marci@317	1678	// // else
marci@317	1679	// // return backward_map.get(e.in);
marci@317	1680	// // }
marci@317	1681	// };
marci@317	1682	// };
marci@317	1683
marci@317	1684
marci@303	1685	//ErasingFirstGraphWrapper for blocking flows
marci@303	1686	template<typename Graph, typename FirstOutEdgesMap>
marci@303	1687	class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
marci@269	1688	protected:
marci@269	1689	FirstOutEdgesMap* first_out_edges;
marci@269	1690	public:
marci@303	1691	ErasingFirstGraphWrapper(Graph& _graph,
marci@303	1692	FirstOutEdgesMap& _first_out_edges) :
marci@303	1693	GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
marci@269	1694
marci@317	1695	typedef typename GraphWrapper<Graph>::Node Node;
marci@317	1696	class NodeIt {
marci@317	1697	friend class GraphWrapper<Graph>;
marci@317	1698	friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@317	1699	typename Graph::NodeIt n;
marci@317	1700	public:
marci@311	1701	NodeIt() { }
marci@317	1702	NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
marci@317	1703	NodeIt(const Invalid& i) : n(i) { }
marci@311	1704	NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
marci@317	1705	n(*(_G.graph)) { }
marci@317	1706	operator Node() const { return Node(typename Graph::Node(n)); }
marci@311	1707	};
marci@317	1708	typedef typename GraphWrapper<Graph>::Edge Edge;
marci@317	1709	class OutEdgeIt {
marci@317	1710	friend class GraphWrapper<Graph>;
marci@317	1711	friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@317	1712	// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@317	1713	typename Graph::OutEdgeIt e;
marci@311	1714	public:
marci@311	1715	OutEdgeIt() { }
marci@317	1716	OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
marci@317	1717	OutEdgeIt(const Invalid& i) : e(i) { }
marci@311	1718	OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
marci@317	1719	const Node& _n) :
marci@317	1720	e((*_G.first_out_edges)[_n]) { }
marci@317	1721	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@311	1722	};
marci@317	1723	class InEdgeIt {
marci@317	1724	friend class GraphWrapper<Graph>;
marci@317	1725	friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@317	1726	// typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@317	1727	typename Graph::InEdgeIt e;
marci@311	1728	public:
marci@311	1729	InEdgeIt() { }
marci@317	1730	InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
marci@317	1731	InEdgeIt(const Invalid& i) : e(i) { }
marci@311	1732	InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
marci@317	1733	const Node& _n) :
marci@317	1734	e(*(_G.graph), typename Graph::Node(_n)) { }
marci@317	1735	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@311	1736	};
marci@311	1737	//typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@317	1738	class EdgeIt {
marci@317	1739	friend class GraphWrapper<Graph>;
marci@317	1740	friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@317	1741	// typedef typename Graph::EdgeIt GraphEdgeIt;
marci@317	1742	typename Graph::EdgeIt e;
marci@311	1743	public:
marci@311	1744	EdgeIt() { }
marci@317	1745	EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
marci@317	1746	EdgeIt(const Invalid& i) : e(i) { }
marci@311	1747	EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
marci@317	1748	e(*(_G.graph)) { }
marci@317	1749	operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@311	1750	};
marci@311	1751
marci@317	1752	NodeIt& first(NodeIt& i) const {
marci@317	1753	i=NodeIt(*this); return i;
marci@269	1754	}
marci@317	1755	OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
marci@317	1756	i=OutEdgeIt(*this, p); return i;
marci@269	1757	}
marci@317	1758	InEdgeIt& first(InEdgeIt& i, const Node& p) const {
marci@317	1759	i=InEdgeIt(*this, p); return i;
marci@311	1760	}
marci@317	1761	EdgeIt& first(EdgeIt& i) const {
marci@317	1762	i=EdgeIt(*this); return i;
marci@311	1763	}
marci@311	1764
marci@311	1765	// template<typename I> I& first(I& i) const {
marci@311	1766	// graph->first(i);
marci@311	1767	// return i;
marci@311	1768	// }
marci@311	1769	// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
marci@311	1770	// // e=first_out_edges->get(n);
marci@311	1771	// e=(*first_out_edges)[n];
marci@311	1772	// return e;
marci@311	1773	// }
marci@311	1774	// template<typename I, typename P> I& first(I& i, const P& p) const {
marci@311	1775	// graph->first(i, p);
marci@311	1776	// return i;
marci@311	1777	// }
marci@269	1778
marci@317	1779	NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
marci@317	1780	OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
marci@317	1781	InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
marci@317	1782	EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
marci@317	1783
marci@317	1784	Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@317	1785	Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@317	1786	Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@317	1787	Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@311	1788
marci@311	1789	// template<typename I> I& next(I &i) const {
marci@311	1790	// graph->next(i);
marci@311	1791	// return i;
marci@311	1792	// }
marci@269	1793
marci@269	1794	template< typename It > It first() const {
marci@269	1795	It e; this->first(e); return e; }
marci@269	1796
marci@269	1797	template< typename It > It first(const Node& v) const {
marci@269	1798	It e; this->first(e, v); return e; }
marci@269	1799
marci@269	1800	void erase(const OutEdgeIt& e) const {
marci@269	1801	OutEdgeIt f=e;
marci@269	1802	this->next(f);
marci@317	1803	first_out_edges->set(this->tail(e), f.e);
marci@269	1804	}
marci@269	1805	};
marci@269	1806
marci@317	1807	// //ErasingFirstGraphWrapper for blocking flows
marci@317	1808	// template<typename Graph, typename FirstOutEdgesMap>
marci@317	1809	// class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
marci@317	1810	// protected:
marci@317	1811	// FirstOutEdgesMap* first_out_edges;
marci@317	1812	// public:
marci@317	1813	// ErasingFirstGraphWrapper(Graph& _graph,
marci@317	1814	// FirstOutEdgesMap& _first_out_edges) :
marci@317	1815	// GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
marci@317	1816
marci@317	1817	// typedef typename Graph::Node Node;
marci@317	1818	// class NodeIt : public Graph::NodeIt {
marci@317	1819	// public:
marci@317	1820	// NodeIt() { }
marci@317	1821	// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
marci@317	1822	// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
marci@317	1823	// NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
marci@317	1824	// Graph::NodeIt(*(_G.graph)) { }
marci@317	1825	// };
marci@317	1826	// typedef typename Graph::Edge Edge;
marci@317	1827	// class OutEdgeIt : public Graph::OutEdgeIt {
marci@317	1828	// public:
marci@317	1829	// OutEdgeIt() { }
marci@317	1830	// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
marci@317	1831	// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
marci@317	1832	// OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
marci@317	1833	// const Node& n) :
marci@317	1834	// Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
marci@317	1835	// };
marci@317	1836	// class InEdgeIt : public Graph::InEdgeIt {
marci@317	1837	// public:
marci@317	1838	// InEdgeIt() { }
marci@317	1839	// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
marci@317	1840	// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
marci@317	1841	// InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
marci@317	1842	// const Node& n) :
marci@317	1843	// Graph::InEdgeIt(*(_G.graph), n) { }
marci@317	1844	// };
marci@317	1845	// //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@317	1846	// class EdgeIt : public Graph::EdgeIt {
marci@317	1847	// public:
marci@317	1848	// EdgeIt() { }
marci@317	1849	// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
marci@317	1850	// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
marci@317	1851	// EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
marci@317	1852	// Graph::EdgeIt(*(_G.graph)) { }
marci@317	1853	// };
marci@317	1854
marci@317	1855	// NodeIt& first(NodeIt& i) const {
marci@317	1856	// i=NodeIt(*this);
marci@317	1857	// return i;
marci@317	1858	// }
marci@317	1859	// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
marci@317	1860	// i=OutEdgeIt(*this, n);
marci@317	1861	// // i=(*first_out_edges)[n];
marci@317	1862	// return i;
marci@317	1863	// }
marci@317	1864	// InEdgeIt& first(InEdgeIt& i, const Node& n) const {
marci@317	1865	// i=InEdgeIt(*this, n);
marci@317	1866	// return i;
marci@317	1867	// }
marci@317	1868	// EdgeIt& first(EdgeIt& i) const {
marci@317	1869	// i=EdgeIt(*this);
marci@317	1870	// return i;
marci@317	1871	// }
marci@317	1872
marci@317	1873	// // template<typename I> I& first(I& i) const {
marci@317	1874	// // graph->first(i);
marci@317	1875	// // return i;
marci@317	1876	// // }
marci@317	1877	// // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
marci@317	1878	// // // e=first_out_edges->get(n);
marci@317	1879	// // e=(*first_out_edges)[n];
marci@317	1880	// // return e;
marci@317	1881	// // }
marci@317	1882	// // template<typename I, typename P> I& first(I& i, const P& p) const {
marci@317	1883	// // graph->first(i, p);
marci@317	1884	// // return i;
marci@317	1885	// // }
marci@317	1886
marci@317	1887	// NodeIt& next(NodeIt& i) const {
marci@317	1888	// graph->next(i);
marci@317	1889	// return i;
marci@317	1890	// }
marci@317	1891	// OutEdgeIt& next(OutEdgeIt& i) const {
marci@317	1892	// graph->next(i);
marci@317	1893	// return i;
marci@317	1894	// }
marci@317	1895	// InEdgeIt& next(InEdgeIt& i) const {
marci@317	1896	// graph->next(i);
marci@317	1897	// return i;
marci@317	1898	// }
marci@317	1899	// EdgeIt& next(EdgeIt& i) const {
marci@317	1900	// graph->next(i);
marci@317	1901	// return i;
marci@317	1902	// }
marci@317	1903
marci@317	1904	// // template<typename I> I& next(I &i) const {
marci@317	1905	// // graph->next(i);
marci@317	1906	// // return i;
marci@317	1907	// // }
marci@317	1908
marci@317	1909	// template< typename It > It first() const {
marci@317	1910	// It e; this->first(e); return e; }
marci@317	1911
marci@317	1912	// template< typename It > It first(const Node& v) const {
marci@317	1913	// It e; this->first(e, v); return e; }
marci@317	1914
marci@317	1915	// void erase(const OutEdgeIt& e) const {
marci@317	1916	// OutEdgeIt f=e;
marci@317	1917	// this->next(f);
marci@317	1918	// first_out_edges->set(this->tail(e), f);
marci@317	1919	// }
marci@317	1920	// };
marci@317	1921
marci@317	1922
marci@148	1923	// // FIXME: comparison should be made better!!!
marci@148	1924	// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
marci@148	1925	// class ResGraphWrapper
marci@148	1926	// {
marci@148	1927	// Graph* graph;
marci@76	1928
marci@148	1929	// public:
marci@303	1930	// typedef Graph ParentGraph;
marci@76	1931
marci@174	1932	// typedef typename Graph::Node Node;
marci@174	1933	// typedef typename Graph::Edge Edge;
marci@174	1934
marci@148	1935	// typedef typename Graph::NodeIt NodeIt;
marci@76	1936
marci@148	1937	// class OutEdgeIt {
marci@148	1938	// public:
marci@174	1939	// //Graph::Node n;
marci@148	1940	// bool out_or_in;
marci@148	1941	// typename Graph::OutEdgeIt o;
marci@148	1942	// typename Graph::InEdgeIt i;
marci@148	1943	// };
marci@148	1944	// class InEdgeIt {
marci@148	1945	// public:
marci@174	1946	// //Graph::Node n;
marci@148	1947	// bool out_or_in;
marci@148	1948	// typename Graph::OutEdgeIt o;
marci@148	1949	// typename Graph::InEdgeIt i;
marci@148	1950	// };
marci@148	1951	// typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@174	1952	// typedef typename Graph::EdgeIt EdgeIt;
marci@76	1953
marci@259	1954	// int nodeNum() const { return gw.nodeNum(); }
marci@259	1955	// int edgeNum() const { return gw.edgeNum(); }
marci@76	1956
marci@259	1957	// Node& first(Node& n) const { return gw.first(n); }
marci@76	1958
marci@174	1959	// // Edge and SymEdge is missing!!!!
marci@174	1960	// // Edge <-> In/OutEdgeIt conversion is missing!!!!
marci@76	1961
marci@148	1962	// //FIXME
marci@212	1963	// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
marci@148	1964	// {
marci@148	1965	// e.n=n;
marci@259	1966	// gw.first(e.o,n);
marci@259	1967	// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
marci@259	1968	// gw.goNext(e.o);
marci@259	1969	// if(!gw.valid(e.o)) {
marci@259	1970	// gw.first(e.i,n);
marci@259	1971	// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
marci@259	1972	// gw.goNext(e.i);
marci@148	1973	// }
marci@148	1974	// return e;
marci@148	1975	// }
marci@148	1976	// /*
marci@148	1977	// OutEdgeIt &goNext(OutEdgeIt &e)
marci@148	1978	// {
marci@259	1979	// if(gw.valid(e.o)) {
marci@259	1980	// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
marci@259	1981	// gw.goNext(e.o);
marci@259	1982	// if(gw.valid(e.o)) return e;
marci@259	1983	// else gw.first(e.i,e.n);
marci@148	1984	// }
marci@148	1985	// else {
marci@259	1986	// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
marci@259	1987	// gw.goNext(e.i);
marci@148	1988	// return e;
marci@148	1989	// }
marci@148	1990	// }
marci@148	1991	// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
marci@148	1992	// */
marci@259	1993	// //bool valid(const OutEdgeIt e) { return gw.valid(e.o)\|\|gw.valid(e.i);}
marci@76	1994
marci@148	1995	// //FIXME
marci@212	1996	// InEdgeIt& first(InEdgeIt& e, const Node& n) const
marci@148	1997	// {
marci@148	1998	// e.n=n;
marci@259	1999	// gw.first(e.i,n);
marci@259	2000	// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
marci@259	2001	// gw.goNext(e.i);
marci@259	2002	// if(!gw.valid(e.i)) {
marci@259	2003	// gw.first(e.o,n);
marci@259	2004	// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
marci@259	2005	// gw.goNext(e.o);
marci@148	2006	// }
marci@148	2007	// return e;
marci@148	2008	// }
marci@148	2009	// /*
marci@148	2010	// InEdgeIt &goNext(InEdgeIt &e)
marci@148	2011	// {
marci@259	2012	// if(gw.valid(e.i)) {
marci@259	2013	// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
marci@259	2014	// gw.goNext(e.i);
marci@259	2015	// if(gw.valid(e.i)) return e;
marci@259	2016	// else gw.first(e.o,e.n);
marci@148	2017	// }
marci@148	2018	// else {
marci@259	2019	// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
marci@259	2020	// gw.goNext(e.o);
marci@148	2021	// return e;
marci@148	2022	// }
marci@148	2023	// }
marci@148	2024	// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
marci@148	2025	// */
marci@259	2026	// //bool valid(const InEdgeIt e) { return gw.valid(e.i)\|\|gw.valid(e.o);}
marci@76	2027
marci@259	2028	// //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
marci@259	2029	// //template<typename I> I next(const I i); { return gw.goNext(i); }
marci@76	2030
marci@148	2031	// template< typename It > It first() const {
marci@212	2032	// It e; first(e); return e; }
marci@76	2033
marci@174	2034	// template< typename It > It first(Node v) const {
marci@212	2035	// It e; first(e, v); return e; }
marci@76	2036
marci@259	2037	// Node head(const Edge& e) const { return gw.head(e); }
marci@259	2038	// Node tail(const Edge& e) const { return gw.tail(e); }
marci@76	2039
marci@174	2040	// template<typename I> Node aNode(const I& e) const {
marci@259	2041	// return gw.aNode(e); }
marci@174	2042	// template<typename I> Node bNode(const I& e) const {
marci@259	2043	// return gw.bNode(e); }
marci@76	2044
marci@148	2045	// //template<typename I> bool valid(const I i);
marci@259	2046	// //{ return gw.valid(i); }
marci@76	2047
marci@148	2048	// //template<typename I> void setInvalid(const I &i);
marci@259	2049	// //{ return gw.setInvalid(i); }
marci@76	2050
marci@259	2051	// Node addNode() { return gw.addNode(); }
marci@174	2052	// Edge addEdge(const Node& tail, const Node& head) {
marci@259	2053	// return gw.addEdge(tail, head); }
marci@76	2054
marci@259	2055	// template<typename I> void erase(const I& i) { gw.erase(i); }
marci@76	2056
marci@259	2057	// void clear() { gw.clear(); }
marci@76	2058
marci@148	2059	// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
marci@148	2060	// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
marci@76	2061
marci@148	2062	// void setGraph(Graph& _graph) { graph = &_graph; }
marci@148	2063	// Graph& getGraph() { return (*graph); }
marci@76	2064
marci@148	2065	// //ResGraphWrapper() : graph(0) { }
marci@148	2066	// ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
marci@148	2067	// };
marci@76	2068
alpar@105	2069	} //namespace hugo
marci@76	2070
marci@259	2071	#endif //HUGO_GRAPH_WRAPPER_H
marci@76	2072

author	marci
	Wed, 14 Apr 2004 11:26:12 +0000
changeset 318	7bec4e8fb7dd
parent 317	6e6db1c49bc1
child 323	58bc28afea63
permissions	-rw-r--r--