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

author	marci
	Fri, 16 Apr 2004 08:26:00 +0000
changeset 335	999eb3cd7b49
parent 330	7ac0d4e8a31c
child 338	e8725f30dd98
permissions	-rw-r--r--