lemon-0.x: src/hugo/graph_wrapper.h@4297098d9677 (annotated)

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

author	alpar
	Mon, 30 Aug 2004 12:01:47 +0000
changeset 774	4297098d9677
parent 739	3bb5553ec41b
child 775	e46a1f0623a0
permissions	-rw-r--r--