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

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

author	marci
	Wed, 14 Apr 2004 13:57:48 +0000
changeset 323	58bc28afea63
parent 318	7bec4e8fb7dd
child 330	7ac0d4e8a31c
permissions	-rw-r--r--