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

author	marci
	Mon, 05 Apr 2004 17:56:31 +0000
changeset 309	50f1d2077d50
parent 275	2dd19df03593
permissions	-rw-r--r--