lemon-0.x: lemon/graph_adaptor.h@6936f130bba2 (annotated)

alpar@906	1	/* -- C++ --
alpar@906	2	*
alpar@1956	3	* This file is a part of LEMON, a generic C++ optimization library
alpar@1956	4	*
alpar@1956	5	* Copyright (C) 2003-2006
alpar@1956	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906	8	*
alpar@906	9	* Permission to use, modify and distribute this software is granted
alpar@906	10	* provided that this copyright notice appears in all copies. For
alpar@906	11	* precise terms see the accompanying LICENSE file.
alpar@906	12	*
alpar@906	13	* This software is provided "AS IS" with no warranty of any kind,
alpar@906	14	* express or implied, and with no claim as to its suitability for any
alpar@906	15	* purpose.
alpar@906	16	*
alpar@906	17	*/
alpar@906	18
alpar@1401	19	#ifndef LEMON_GRAPH_ADAPTOR_H
alpar@1401	20	#define LEMON_GRAPH_ADAPTOR_H
marci@556	21
deba@2037	22	///\ingroup graph_adaptors
deba@2037	23	///\file
deba@2037	24	///\brief Several graph adaptors.
marci@556	25	///
deba@2037	26	///This file contains several useful graph adaptor functions.
marci@556	27	///
deba@2037	28	///\author Marton Makai and Balazs Dezso
marci@556	29
deba@1993	30	#include <lemon/bits/invalid.h>
alpar@921	31	#include <lemon/maps.h>
deba@1979	32
deba@1999	33	#include <lemon/bits/base_extender.h>
deba@1979	34	#include <lemon/bits/graph_adaptor_extender.h>
deba@1791	35	#include <lemon/bits/graph_extender.h>
deba@1979	36
deba@2034	37	#include <lemon/tolerance.h>
deba@2034	38
alpar@774	39	#include <iostream>
marci@556	40
alpar@921	41	namespace lemon {
marci@556	42
klao@1951	43	///\brief Base type for the Graph Adaptors
klao@1951	44	///\ingroup graph_adaptors
klao@1951	45	///
klao@1951	46	///Base type for the Graph Adaptors
klao@1951	47	///
klao@1951	48	///This is the base type for most of LEMON graph adaptors.
klao@1951	49	///This class implements a trivial graph adaptor i.e. it only wraps the
klao@1951	50	///functions and types of the graph. The purpose of this class is to
klao@1951	51	///make easier implementing graph adaptors. E.g. if an adaptor is
klao@1951	52	///considered which differs from the wrapped graph only in some of its
klao@1951	53	///functions or types, then it can be derived from GraphAdaptor,
klao@1951	54	///and only the
klao@1951	55	///differences should be implemented.
klao@1951	56	///
klao@1951	57	///author Marton Makai
marci@970	58	template<typename _Graph>
alpar@1401	59	class GraphAdaptorBase {
marci@970	60	public:
marci@970	61	typedef _Graph Graph;
deba@2031	62	typedef GraphAdaptorBase Adaptor;
marci@970	63	typedef Graph ParentGraph;
marci@970	64
marci@556	65	protected:
marci@556	66	Graph* graph;
alpar@1401	67	GraphAdaptorBase() : graph(0) { }
marci@556	68	void setGraph(Graph& _graph) { graph=&_graph; }
marci@556	69
marci@556	70	public:
alpar@1401	71	GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
deba@2034	72
alpar@774	73	typedef typename Graph::Node Node;
alpar@774	74	typedef typename Graph::Edge Edge;
marci@556	75
marci@970	76	void first(Node& i) const { graph->first(i); }
marci@970	77	void first(Edge& i) const { graph->first(i); }
marci@970	78	void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
marci@970	79	void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
marci@556	80
marci@970	81	void next(Node& i) const { graph->next(i); }
marci@970	82	void next(Edge& i) const { graph->next(i); }
marci@970	83	void nextIn(Edge& i) const { graph->nextIn(i); }
marci@970	84	void nextOut(Edge& i) const { graph->nextOut(i); }
marci@970	85
alpar@986	86	Node source(const Edge& e) const { return graph->source(e); }
alpar@986	87	Node target(const Edge& e) const { return graph->target(e); }
marci@556	88
deba@1697	89	typedef NodeNumTagIndicator<Graph> NodeNumTag;
marci@556	90	int nodeNum() const { return graph->nodeNum(); }
deba@1697	91
deba@1697	92	typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
marci@556	93	int edgeNum() const { return graph->edgeNum(); }
deba@1697	94
deba@1697	95	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1697	96	Edge findEdge(const Node& source, const Node& target,
deba@1697	97	const Edge& prev = INVALID) {
deba@1697	98	return graph->findEdge(source, target, prev);
deba@1697	99	}
marci@556	100
deba@1697	101	Node addNode() const {
deba@1697	102	return Node(graph->addNode());
deba@1697	103	}
deba@1697	104
alpar@986	105	Edge addEdge(const Node& source, const Node& target) const {
deba@1697	106	return Edge(graph->addEdge(source, target));
deba@1697	107	}
marci@556	108
marci@556	109	void erase(const Node& i) const { graph->erase(i); }
marci@556	110	void erase(const Edge& i) const { graph->erase(i); }
marci@556	111
marci@556	112	void clear() const { graph->clear(); }
marci@556	113
marci@739	114	int id(const Node& v) const { return graph->id(v); }
marci@739	115	int id(const Edge& e) const { return graph->id(e); }
deba@1991	116
deba@2031	117	Node fromNodeId(int id) const {
deba@2031	118	return graph->fromNodeId(id);
deba@2031	119	}
deba@2031	120
deba@2031	121	Edge fromEdgeId(int id) const {
deba@2031	122	return graph->fromEdgeId(id);
deba@2031	123	}
deba@2031	124
deba@1991	125	int maxNodeId() const {
deba@1991	126	return graph->maxNodeId();
deba@1991	127	}
deba@1991	128
deba@1991	129	int maxEdgeId() const {
deba@1991	130	return graph->maxEdgeId();
deba@1991	131	}
deba@1991	132
deba@1991	133	typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@1991	134
deba@1991	135	NodeNotifier& getNotifier(Node) const {
deba@1991	136	return graph->getNotifier(Node());
deba@1991	137	}
deba@1991	138
deba@1991	139	typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@1991	140
deba@1991	141	EdgeNotifier& getNotifier(Edge) const {
deba@1991	142	return graph->getNotifier(Edge());
deba@1991	143	}
marci@650	144
marci@970	145	template <typename _Value>
deba@2031	146	class NodeMap : public Graph::template NodeMap<_Value> {
marci@970	147	public:
deba@2031	148
deba@2031	149	typedef typename Graph::template NodeMap<_Value> Parent;
deba@2031	150
deba@2031	151	explicit NodeMap(const Adaptor& ga)
deba@2031	152	: Parent(*ga.graph) {}
deba@2031	153
deba@2031	154	NodeMap(const Adaptor& ga, const _Value& value)
deba@1991	155	: Parent(*ga.graph, value) { }
deba@2031	156
deba@2031	157	NodeMap& operator=(const NodeMap& cmap) {
deba@2031	158	return operator=<NodeMap>(cmap);
deba@2031	159	}
deba@2031	160
deba@2031	161	template <typename CMap>
deba@2031	162	NodeMap& operator=(const CMap& cmap) {
deba@2031	163	Parent::operator=(cmap);
deba@2031	164	return *this;
deba@2031	165	}
deba@2031	166
marci@970	167	};
marci@556	168
marci@970	169	template <typename _Value>
deba@2031	170	class EdgeMap : public Graph::template EdgeMap<_Value> {
marci@970	171	public:
deba@2031	172
deba@2031	173	typedef typename Graph::template EdgeMap<_Value> Parent;
deba@2031	174
deba@2031	175	explicit EdgeMap(const Adaptor& ga)
deba@2031	176	: Parent(*ga.graph) {}
deba@2031	177
deba@2031	178	EdgeMap(const Adaptor& ga, const _Value& value)
deba@2031	179	: Parent(*ga.graph, value) {}
deba@2031	180
deba@2031	181	EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031	182	return operator=<EdgeMap>(cmap);
deba@2031	183	}
deba@2031	184
deba@2031	185	template <typename CMap>
deba@2031	186	EdgeMap& operator=(const CMap& cmap) {
deba@2031	187	Parent::operator=(cmap);
deba@2031	188	return *this;
deba@2031	189	}
deba@2031	190
marci@970	191	};
deba@877	192
marci@556	193	};
marci@556	194
marci@970	195	template <typename _Graph>
alpar@1401	196	class GraphAdaptor :
deba@1979	197	public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
marci@970	198	public:
marci@970	199	typedef _Graph Graph;
deba@1979	200	typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
marci@970	201	protected:
alpar@1401	202	GraphAdaptor() : Parent() { }
marci@569	203
marci@970	204	public:
deba@1755	205	explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
marci@970	206	};
marci@569	207
deba@1991	208	/// \brief Just gives back a graph adaptor
deba@1991	209	///
deba@1991	210	/// Just gives back a graph adaptor which
deba@1991	211	/// should be provide original graph
deba@1991	212	template<typename Graph>
deba@1991	213	GraphAdaptor<const Graph>
deba@1991	214	graphAdaptor(const Graph& graph) {
deba@1991	215	return GraphAdaptor<const Graph>(graph);
deba@1991	216	}
deba@1991	217
deba@1991	218
marci@997	219	template <typename _Graph>
alpar@1401	220	class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@997	221	public:
marci@997	222	typedef _Graph Graph;
alpar@1401	223	typedef GraphAdaptorBase<_Graph> Parent;
marci@997	224	protected:
alpar@1401	225	RevGraphAdaptorBase() : Parent() { }
marci@997	226	public:
marci@997	227	typedef typename Parent::Node Node;
marci@997	228	typedef typename Parent::Edge Edge;
marci@997	229
marci@997	230	void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
marci@997	231	void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
marci@997	232
marci@997	233	void nextIn(Edge& i) const { Parent::nextOut(i); }
marci@997	234	void nextOut(Edge& i) const { Parent::nextIn(i); }
marci@997	235
marci@997	236	Node source(const Edge& e) const { return Parent::target(e); }
marci@997	237	Node target(const Edge& e) const { return Parent::source(e); }
deba@1991	238
deba@1991	239	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1991	240	Edge findEdge(const Node& source, const Node& target,
deba@1991	241	const Edge& prev = INVALID) {
deba@1991	242	return Parent::findEdge(target, source, prev);
deba@1991	243	}
deba@1991	244
marci@997	245	};
marci@997	246
marci@997	247
alpar@1949	248	///\brief A graph adaptor which reverses the orientation of the edges.
alpar@1949	249	///\ingroup graph_adaptors
alpar@1949	250	///
alpar@1949	251	/// If \c g is defined as
alpar@1946	252	///\code
marci@923	253	/// ListGraph g;
alpar@1946	254	///\endcode
alpar@1949	255	/// then
alpar@1946	256	///\code
deba@1991	257	/// RevGraphAdaptor<ListGraph> ga(g);
alpar@1946	258	///\endcode
alpar@1949	259	///implements the graph obtained from \c g by
alpar@1949	260	/// reversing the orientation of its edges.
alpar@1946	261
marci@997	262	template<typename _Graph>
alpar@1401	263	class RevGraphAdaptor :
deba@1979	264	public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
marci@650	265	public:
marci@997	266	typedef _Graph Graph;
deba@1979	267	typedef GraphAdaptorExtender<
alpar@1401	268	RevGraphAdaptorBase<_Graph> > Parent;
marci@556	269	protected:
alpar@1401	270	RevGraphAdaptor() { }
marci@556	271	public:
deba@1755	272	explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
marci@997	273	};
marci@556	274
deba@1991	275	/// \brief Just gives back a reverse graph adaptor
deba@1991	276	///
deba@1991	277	/// Just gives back a reverse graph adaptor
deba@1991	278	template<typename Graph>
deba@1991	279	RevGraphAdaptor<const Graph>
deba@1991	280	revGraphAdaptor(const Graph& graph) {
deba@1991	281	return RevGraphAdaptor<const Graph>(graph);
deba@1991	282	}
deba@1991	283
deba@1681	284	template <typename _Graph, typename NodeFilterMap,
deba@1681	285	typename EdgeFilterMap, bool checked = true>
alpar@1401	286	class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@992	287	public:
marci@992	288	typedef _Graph Graph;
deba@2031	289	typedef SubGraphAdaptorBase Adaptor;
alpar@1401	290	typedef GraphAdaptorBase<_Graph> Parent;
marci@992	291	protected:
marci@992	292	NodeFilterMap* node_filter_map;
marci@992	293	EdgeFilterMap* edge_filter_map;
alpar@1401	294	SubGraphAdaptorBase() : Parent(),
marci@992	295	node_filter_map(0), edge_filter_map(0) { }
marci@775	296
marci@992	297	void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
marci@992	298	node_filter_map=&_node_filter_map;
marci@992	299	}
marci@992	300	void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
marci@992	301	edge_filter_map=&_edge_filter_map;
marci@992	302	}
marci@992	303
marci@992	304	public:
marci@992	305
marci@992	306	typedef typename Parent::Node Node;
marci@992	307	typedef typename Parent::Edge Edge;
marci@992	308
marci@992	309	void first(Node& i) const {
marci@992	310	Parent::first(i);
marci@992	311	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
marci@992	312	}
deba@1681	313
deba@1681	314	void first(Edge& i) const {
deba@1681	315	Parent::first(i);
deba@1681	316	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	317	\|\| !(*node_filter_map)[Parent::source(i)]
deba@1681	318	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
deba@1681	319	}
deba@1681	320
deba@1681	321	void firstIn(Edge& i, const Node& n) const {
deba@1681	322	Parent::firstIn(i, n);
deba@1681	323	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	324	\|\| !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
deba@1681	325	}
deba@1681	326
deba@1681	327	void firstOut(Edge& i, const Node& n) const {
deba@1681	328	Parent::firstOut(i, n);
deba@1681	329	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	330	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
deba@1681	331	}
deba@1681	332
deba@1681	333	void next(Node& i) const {
deba@1681	334	Parent::next(i);
deba@1681	335	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
deba@1681	336	}
deba@1681	337
deba@1681	338	void next(Edge& i) const {
deba@1681	339	Parent::next(i);
deba@1681	340	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	341	\|\| !(*node_filter_map)[Parent::source(i)]
deba@1681	342	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
deba@1681	343	}
deba@1681	344
deba@1681	345	void nextIn(Edge& i) const {
deba@1681	346	Parent::nextIn(i);
deba@1681	347	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	348	\|\| !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
deba@1681	349	}
deba@1681	350
deba@1681	351	void nextOut(Edge& i) const {
deba@1681	352	Parent::nextOut(i);
deba@1681	353	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	354	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
deba@1681	355	}
deba@1681	356
klao@1951	357	///\e
alpar@1949	358
klao@1951	359	/// This function hides \c n in the graph, i.e. the iteration
klao@1951	360	/// jumps over it. This is done by simply setting the value of \c n
klao@1951	361	/// to be false in the corresponding node-map.
deba@1681	362	void hide(const Node& n) const { node_filter_map->set(n, false); }
deba@1681	363
klao@1951	364	///\e
alpar@1949	365
klao@1951	366	/// This function hides \c e in the graph, i.e. the iteration
klao@1951	367	/// jumps over it. This is done by simply setting the value of \c e
klao@1951	368	/// to be false in the corresponding edge-map.
deba@1681	369	void hide(const Edge& e) const { edge_filter_map->set(e, false); }
deba@1681	370
klao@1951	371	///\e
alpar@1949	372
klao@1951	373	/// The value of \c n is set to be true in the node-map which stores
klao@1951	374	/// hide information. If \c n was hidden previuosly, then it is shown
klao@1951	375	/// again
deba@1681	376	void unHide(const Node& n) const { node_filter_map->set(n, true); }
deba@1681	377
klao@1951	378	///\e
alpar@1949	379
klao@1951	380	/// The value of \c e is set to be true in the edge-map which stores
klao@1951	381	/// hide information. If \c e was hidden previuosly, then it is shown
klao@1951	382	/// again
deba@1681	383	void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
deba@1681	384
klao@1951	385	/// Returns true if \c n is hidden.
alpar@1949	386
klao@1951	387	///\e
klao@1951	388	///
deba@1681	389	bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
deba@1681	390
klao@1951	391	/// Returns true if \c n is hidden.
alpar@1949	392
klao@1951	393	///\e
klao@1951	394	///
deba@1681	395	bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
deba@1681	396
deba@1697	397	typedef False NodeNumTag;
deba@1697	398	typedef False EdgeNumTag;
deba@1991	399
deba@1991	400	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1991	401	Edge findEdge(const Node& source, const Node& target,
deba@1991	402	const Edge& prev = INVALID) {
deba@1991	403	if (!(node_filter_map)[source] \|\| !(node_filter_map)[target]) {
deba@1991	404	return INVALID;
deba@1991	405	}
deba@1991	406	Edge edge = Parent::findEdge(source, target, prev);
deba@1991	407	while (edge != INVALID && !(*edge_filter_map)[edge]) {
deba@1991	408	edge = Parent::findEdge(source, target, edge);
deba@1991	409	}
deba@1991	410	return edge;
deba@1991	411	}
deba@2031	412
deba@2031	413	template <typename _Value>
deba@2031	414	class NodeMap
deba@2031	415	: public SubMapExtender<Adaptor,
deba@2031	416	typename Parent::template NodeMap<_Value> >
deba@2031	417	{
deba@2031	418	public:
deba@2031	419	typedef Adaptor Graph;
deba@2031	420	typedef SubMapExtender<Adaptor, typename Parent::
deba@2031	421	template NodeMap<_Value> > Parent;
deba@2031	422
deba@2031	423	NodeMap(const Graph& graph)
deba@2031	424	: Parent(graph) {}
deba@2031	425	NodeMap(const Graph& graph, const _Value& value)
deba@2031	426	: Parent(graph, value) {}
deba@2031	427
deba@2031	428	NodeMap& operator=(const NodeMap& cmap) {
deba@2031	429	return operator=<NodeMap>(cmap);
deba@2031	430	}
deba@2031	431
deba@2031	432	template <typename CMap>
deba@2031	433	NodeMap& operator=(const CMap& cmap) {
deba@2031	434	Parent::operator=(cmap);
deba@2031	435	return *this;
deba@2031	436	}
deba@2031	437	};
deba@2031	438
deba@2031	439	template <typename _Value>
deba@2031	440	class EdgeMap
deba@2031	441	: public SubMapExtender<Adaptor,
deba@2031	442	typename Parent::template EdgeMap<_Value> >
deba@2031	443	{
deba@2031	444	public:
deba@2031	445	typedef Adaptor Graph;
deba@2031	446	typedef SubMapExtender<Adaptor, typename Parent::
deba@2031	447	template EdgeMap<_Value> > Parent;
deba@2031	448
deba@2031	449	EdgeMap(const Graph& graph)
deba@2031	450	: Parent(graph) {}
deba@2031	451	EdgeMap(const Graph& graph, const _Value& value)
deba@2031	452	: Parent(graph, value) {}
deba@2031	453
deba@2031	454	EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031	455	return operator=<EdgeMap>(cmap);
deba@2031	456	}
deba@2031	457
deba@2031	458	template <typename CMap>
deba@2031	459	EdgeMap& operator=(const CMap& cmap) {
deba@2031	460	Parent::operator=(cmap);
deba@2031	461	return *this;
deba@2031	462	}
deba@2031	463	};
deba@2031	464
deba@1681	465	};
deba@1681	466
deba@1681	467	template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1681	468	class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
deba@1681	469	: public GraphAdaptorBase<_Graph> {
deba@1681	470	public:
deba@1681	471	typedef _Graph Graph;
deba@2031	472	typedef SubGraphAdaptorBase Adaptor;
deba@1681	473	typedef GraphAdaptorBase<_Graph> Parent;
deba@1681	474	protected:
deba@1681	475	NodeFilterMap* node_filter_map;
deba@1681	476	EdgeFilterMap* edge_filter_map;
deba@1681	477	SubGraphAdaptorBase() : Parent(),
deba@1681	478	node_filter_map(0), edge_filter_map(0) { }
deba@1681	479
deba@1681	480	void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
deba@1681	481	node_filter_map=&_node_filter_map;
deba@1681	482	}
deba@1681	483	void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
deba@1681	484	edge_filter_map=&_edge_filter_map;
deba@1681	485	}
deba@1681	486
deba@1681	487	public:
deba@1681	488
deba@1681	489	typedef typename Parent::Node Node;
deba@1681	490	typedef typename Parent::Edge Edge;
deba@1681	491
deba@1681	492	void first(Node& i) const {
deba@1681	493	Parent::first(i);
deba@1681	494	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
deba@1681	495	}
deba@1681	496
marci@992	497	void first(Edge& i) const {
marci@992	498	Parent::first(i);
marci@992	499	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
marci@992	500	}
deba@1681	501
marci@992	502	void firstIn(Edge& i, const Node& n) const {
marci@992	503	Parent::firstIn(i, n);
marci@992	504	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
marci@992	505	}
deba@1681	506
marci@992	507	void firstOut(Edge& i, const Node& n) const {
marci@992	508	Parent::firstOut(i, n);
marci@992	509	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
marci@992	510	}
marci@992	511
marci@992	512	void next(Node& i) const {
marci@992	513	Parent::next(i);
marci@992	514	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
marci@992	515	}
marci@992	516	void next(Edge& i) const {
marci@992	517	Parent::next(i);
marci@992	518	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
marci@992	519	}
marci@992	520	void nextIn(Edge& i) const {
marci@992	521	Parent::nextIn(i);
marci@992	522	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
marci@992	523	}
deba@1681	524
marci@992	525	void nextOut(Edge& i) const {
marci@992	526	Parent::nextOut(i);
marci@992	527	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
marci@992	528	}
marci@992	529
klao@1951	530	///\e
alpar@1949	531
klao@1951	532	/// This function hides \c n in the graph, i.e. the iteration
klao@1951	533	/// jumps over it. This is done by simply setting the value of \c n
klao@1951	534	/// to be false in the corresponding node-map.
marci@992	535	void hide(const Node& n) const { node_filter_map->set(n, false); }
marci@992	536
klao@1951	537	///\e
alpar@1949	538
klao@1951	539	/// This function hides \c e in the graph, i.e. the iteration
klao@1951	540	/// jumps over it. This is done by simply setting the value of \c e
klao@1951	541	/// to be false in the corresponding edge-map.
marci@992	542	void hide(const Edge& e) const { edge_filter_map->set(e, false); }
marci@992	543
klao@1951	544	///\e
alpar@1949	545
klao@1951	546	/// The value of \c n is set to be true in the node-map which stores
klao@1951	547	/// hide information. If \c n was hidden previuosly, then it is shown
klao@1951	548	/// again
marci@992	549	void unHide(const Node& n) const { node_filter_map->set(n, true); }
marci@992	550
klao@1951	551	///\e
alpar@1949	552
klao@1951	553	/// The value of \c e is set to be true in the edge-map which stores
klao@1951	554	/// hide information. If \c e was hidden previuosly, then it is shown
klao@1951	555	/// again
marci@992	556	void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
marci@992	557
klao@1951	558	/// Returns true if \c n is hidden.
alpar@1949	559
klao@1951	560	///\e
klao@1951	561	///
marci@992	562	bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
marci@992	563
klao@1951	564	/// Returns true if \c n is hidden.
alpar@1949	565
klao@1951	566	///\e
klao@1951	567	///
marci@992	568	bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
marci@992	569
deba@1697	570	typedef False NodeNumTag;
deba@1697	571	typedef False EdgeNumTag;
deba@1991	572
deba@1991	573	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1991	574	Edge findEdge(const Node& source, const Node& target,
deba@1991	575	const Edge& prev = INVALID) {
deba@1991	576	if (!(node_filter_map)[source] \|\| !(node_filter_map)[target]) {
deba@1991	577	return INVALID;
deba@1991	578	}
deba@1991	579	Edge edge = Parent::findEdge(source, target, prev);
deba@1991	580	while (edge != INVALID && !(*edge_filter_map)[edge]) {
deba@1991	581	edge = Parent::findEdge(source, target, edge);
deba@1991	582	}
deba@1991	583	return edge;
deba@1991	584	}
deba@2031	585
deba@2031	586	template <typename _Value>
deba@2031	587	class NodeMap
deba@2031	588	: public SubMapExtender<Adaptor,
deba@2031	589	typename Parent::template NodeMap<_Value> >
deba@2031	590	{
deba@2031	591	public:
deba@2031	592	typedef Adaptor Graph;
deba@2031	593	typedef SubMapExtender<Adaptor, typename Parent::
deba@2031	594	template NodeMap<_Value> > Parent;
deba@2031	595
deba@2031	596	NodeMap(const Graph& graph)
deba@2031	597	: Parent(graph) {}
deba@2031	598	NodeMap(const Graph& graph, const _Value& value)
deba@2031	599	: Parent(graph, value) {}
deba@2031	600
deba@2031	601	NodeMap& operator=(const NodeMap& cmap) {
deba@2031	602	return operator=<NodeMap>(cmap);
deba@2031	603	}
deba@2031	604
deba@2031	605	template <typename CMap>
deba@2031	606	NodeMap& operator=(const CMap& cmap) {
deba@2031	607	Parent::operator=(cmap);
deba@2031	608	return *this;
deba@2031	609	}
deba@2031	610	};
deba@2031	611
deba@2031	612	template <typename _Value>
deba@2031	613	class EdgeMap
deba@2031	614	: public SubMapExtender<Adaptor,
deba@2031	615	typename Parent::template EdgeMap<_Value> >
deba@2031	616	{
deba@2031	617	public:
deba@2031	618	typedef Adaptor Graph;
deba@2031	619	typedef SubMapExtender<Adaptor, typename Parent::
deba@2031	620	template EdgeMap<_Value> > Parent;
deba@2031	621
deba@2031	622	EdgeMap(const Graph& graph)
deba@2031	623	: Parent(graph) {}
deba@2031	624	EdgeMap(const Graph& graph, const _Value& value)
deba@2031	625	: Parent(graph, value) {}
deba@2031	626
deba@2031	627	EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031	628	return operator=<EdgeMap>(cmap);
deba@2031	629	}
deba@2031	630
deba@2031	631	template <typename CMap>
deba@2031	632	EdgeMap& operator=(const CMap& cmap) {
deba@2031	633	Parent::operator=(cmap);
deba@2031	634	return *this;
deba@2031	635	}
deba@2031	636	};
deba@2031	637
marci@992	638	};
marci@775	639
klao@1951	640	/// \brief A graph adaptor for hiding nodes and edges from a graph.
klao@1951	641	/// \ingroup graph_adaptors
klao@1951	642	///
klao@1951	643	/// SubGraphAdaptor shows the graph with filtered node-set and
klao@1951	644	/// edge-set. If the \c checked parameter is true then it filters the edgeset
klao@1951	645	/// to do not get invalid edges without source or target.
klao@1952	646	/// Let \f$ G=(V, A) \f$ be a directed graph
klao@1951	647	/// and suppose that the graph instance \c g of type ListGraph
klao@1952	648	/// implements \f$ G \f$.
klao@1952	649	/// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
klao@1951	650	/// on the node-set and edge-set.
klao@1951	651	/// SubGraphAdaptor<...>::NodeIt iterates
klao@1952	652	/// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
klao@1951	653	/// SubGraphAdaptor<...>::EdgeIt iterates
klao@1952	654	/// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
klao@1951	655	/// SubGraphAdaptor<...>::OutEdgeIt and
klao@1951	656	/// SubGraphAdaptor<...>::InEdgeIt iterates
klao@1951	657	/// only on edges leaving and entering a specific node which have true value.
klao@1951	658	///
klao@1951	659	/// If the \c checked template parameter is false then we have to note that
klao@1951	660	/// the node-iterator cares only the filter on the node-set, and the
klao@1951	661	/// edge-iterator cares only the filter on the edge-set.
klao@1951	662	/// This way the edge-map
klao@1951	663	/// should filter all edges which's source or target is filtered by the
klao@1951	664	/// node-filter.
alpar@1957	665	///\code
klao@1951	666	/// typedef ListGraph Graph;
klao@1951	667	/// Graph g;
klao@1951	668	/// typedef Graph::Node Node;
klao@1951	669	/// typedef Graph::Edge Edge;
klao@1951	670	/// Node u=g.addNode(); //node of id 0
klao@1951	671	/// Node v=g.addNode(); //node of id 1
klao@1951	672	/// Node e=g.addEdge(u, v); //edge of id 0
klao@1951	673	/// Node f=g.addEdge(v, u); //edge of id 1
klao@1951	674	/// Graph::NodeMap<bool> nm(g, true);
klao@1951	675	/// nm.set(u, false);
klao@1951	676	/// Graph::EdgeMap<bool> em(g, true);
klao@1951	677	/// em.set(e, false);
deba@1991	678	/// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
deba@1991	679	/// SubGA ga(g, nm, em);
deba@1991	680	/// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
klao@1951	681	/// std::cout << ":-)" << std::endl;
deba@1991	682	/// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
alpar@1957	683	///\endcode
klao@1951	684	/// The output of the above code is the following.
alpar@1957	685	///\code
klao@1951	686	/// 1
klao@1951	687	/// :-)
klao@1951	688	/// 1
alpar@1957	689	///\endcode
deba@1991	690	/// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
klao@1951	691	/// \c Graph::Node that is why \c g.id(n) can be applied.
klao@1951	692	///
klao@1951	693	/// For other examples see also the documentation of NodeSubGraphAdaptor and
klao@1951	694	/// EdgeSubGraphAdaptor.
klao@1951	695	///
klao@1951	696	/// \author Marton Makai
marci@1242	697
marci@992	698	template<typename _Graph, typename NodeFilterMap,
deba@1681	699	typename EdgeFilterMap, bool checked = true>
alpar@1401	700	class SubGraphAdaptor :
deba@1979	701	public GraphAdaptorExtender<
deba@1681	702	SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
marci@650	703	public:
marci@992	704	typedef _Graph Graph;
deba@2031	705	typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
deba@2031	706	EdgeFilterMap, checked> >
deba@2031	707	Parent;
deba@2031	708
marci@556	709	protected:
alpar@1401	710	SubGraphAdaptor() { }
marci@992	711	public:
deba@2031	712
alpar@1401	713	SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
marci@992	714	EdgeFilterMap& _edge_filter_map) {
marci@992	715	setGraph(_graph);
marci@992	716	setNodeFilterMap(_node_filter_map);
marci@992	717	setEdgeFilterMap(_edge_filter_map);
marci@992	718	}
deba@2031	719
marci@992	720	};
marci@556	721
deba@1991	722	/// \brief Just gives back a sub graph adaptor
deba@1991	723	///
deba@1991	724	/// Just gives back a sub graph adaptor
deba@1991	725	template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991	726	SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
deba@1991	727	subGraphAdaptor(const Graph& graph,
deba@1991	728	NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991	729	return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
deba@1991	730	(graph, nfm, efm);
deba@1991	731	}
deba@1991	732
deba@1991	733	template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991	734	SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
deba@1991	735	subGraphAdaptor(const Graph& graph,
deba@1991	736	NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991	737	return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
deba@1991	738	(graph, nfm, efm);
deba@1991	739	}
deba@1991	740
deba@1991	741	template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991	742	SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
deba@1991	743	subGraphAdaptor(const Graph& graph,
deba@1991	744	NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991	745	return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
deba@1991	746	(graph, nfm, efm);
deba@1991	747	}
deba@1991	748
deba@1991	749	template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991	750	SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
deba@1991	751	subGraphAdaptor(const Graph& graph,
deba@1991	752	NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991	753	return SubGraphAdaptor<const Graph, const NodeFilterMap,
deba@1991	754	const EdgeFilterMap>(graph, nfm, efm);
deba@1991	755	}
deba@1991	756
marci@556	757
marci@569	758
klao@1951	759	///\brief An adaptor for hiding nodes from a graph.
klao@1951	760	///\ingroup graph_adaptors
klao@1951	761	///
klao@1951	762	///An adaptor for hiding nodes from a graph.
klao@1951	763	///This adaptor specializes SubGraphAdaptor in the way that only
klao@1951	764	///the node-set
klao@1951	765	///can be filtered. In usual case the checked parameter is true, we get the
klao@1951	766	///induced subgraph. But if the checked parameter is false then we can only
klao@1951	767	///filter only isolated nodes.
klao@1951	768	///\author Marton Makai
deba@1681	769	template<typename Graph, typename NodeFilterMap, bool checked = true>
alpar@1401	770	class NodeSubGraphAdaptor :
alpar@1401	771	public SubGraphAdaptor<Graph, NodeFilterMap,
deba@1681	772	ConstMap<typename Graph::Edge,bool>, checked> {
marci@933	773	public:
deba@2031	774
alpar@1401	775	typedef SubGraphAdaptor<Graph, NodeFilterMap,
deba@2031	776	ConstMap<typename Graph::Edge,bool>, checked >
deba@2031	777	Parent;
deba@2031	778
marci@933	779	protected:
marci@933	780	ConstMap<typename Graph::Edge, bool> const_true_map;
deba@1991	781
deba@1991	782	NodeSubGraphAdaptor() : const_true_map(true) {
deba@1991	783	Parent::setEdgeFilterMap(const_true_map);
deba@1991	784	}
deba@1991	785
marci@933	786	public:
deba@2031	787
alpar@1401	788	NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
marci@933	789	Parent(), const_true_map(true) {
marci@933	790	Parent::setGraph(_graph);
marci@933	791	Parent::setNodeFilterMap(_node_filter_map);
marci@933	792	Parent::setEdgeFilterMap(const_true_map);
marci@933	793	}
deba@2031	794
marci@933	795	};
marci@933	796
marci@933	797
deba@1991	798	/// \brief Just gives back a node sub graph adaptor
deba@1991	799	///
deba@1991	800	/// Just gives back a node sub graph adaptor
deba@1991	801	template<typename Graph, typename NodeFilterMap>
deba@1991	802	NodeSubGraphAdaptor<const Graph, NodeFilterMap>
deba@1991	803	nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
deba@1991	804	return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
deba@1991	805	}
deba@1991	806
deba@1991	807	template<typename Graph, typename NodeFilterMap>
deba@1991	808	NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
deba@1991	809	nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
deba@1991	810	return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
deba@1991	811	}
deba@1991	812
klao@1951	813	///\brief An adaptor for hiding edges from a graph.
klao@1951	814	///
klao@1951	815	///An adaptor for hiding edges from a graph.
klao@1951	816	///This adaptor specializes SubGraphAdaptor in the way that
klao@1951	817	///only the edge-set
klao@1951	818	///can be filtered. The usefulness of this adaptor is demonstrated in the
klao@1951	819	///problem of searching a maximum number of edge-disjoint shortest paths
klao@1951	820	///between
klao@1951	821	///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
klao@1951	822	///non-negative edge-lengths. Note that
klao@1951	823	///the comprehension of the presented solution
klao@1951	824	///need's some elementary knowledge from combinatorial optimization.
klao@1951	825	///
klao@1951	826	///If a single shortest path is to be
klao@1951	827	///searched between \c s and \c t, then this can be done easily by
klao@1951	828	///applying the Dijkstra algorithm. What happens, if a maximum number of
klao@1951	829	///edge-disjoint shortest paths is to be computed. It can be proved that an
klao@1951	830	///edge can be in a shortest path if and only
klao@1951	831	///if it is tight with respect to
klao@1951	832	///the potential function computed by Dijkstra.
klao@1951	833	///Moreover, any path containing
klao@1951	834	///only such edges is a shortest one.
klao@1951	835	///Thus we have to compute a maximum number
klao@1951	836	///of edge-disjoint paths between \c s and \c t in
klao@1951	837	///the graph which has edge-set
klao@1951	838	///all the tight edges. The computation will be demonstrated
klao@1951	839	///on the following
klao@1951	840	///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
klao@1951	841	///The full source code is available in \ref sub_graph_adaptor_demo.cc.
klao@1951	842	///If you are interested in more demo programs, you can use
klao@1951	843	///\ref dim_to_dot.cc to generate .dot files from dimacs files.
klao@1951	844	///The .dot file of the following figure was generated by
klao@1951	845	///the demo program \ref dim_to_dot.cc.
klao@1951	846	///
klao@1951	847	///\dot
klao@1951	848	///digraph lemon_dot_example {
klao@1951	849	///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
klao@1951	850	///n0 [ label="0 (s)" ];
klao@1951	851	///n1 [ label="1" ];
klao@1951	852	///n2 [ label="2" ];
klao@1951	853	///n3 [ label="3" ];
klao@1951	854	///n4 [ label="4" ];
klao@1951	855	///n5 [ label="5" ];
klao@1951	856	///n6 [ label="6 (t)" ];
klao@1951	857	///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
klao@1951	858	///n5 -> n6 [ label="9, length:4" ];
klao@1951	859	///n4 -> n6 [ label="8, length:2" ];
klao@1951	860	///n3 -> n5 [ label="7, length:1" ];
klao@1951	861	///n2 -> n5 [ label="6, length:3" ];
klao@1951	862	///n2 -> n6 [ label="5, length:5" ];
klao@1951	863	///n2 -> n4 [ label="4, length:2" ];
klao@1951	864	///n1 -> n4 [ label="3, length:3" ];
klao@1951	865	///n0 -> n3 [ label="2, length:1" ];
klao@1951	866	///n0 -> n2 [ label="1, length:2" ];
klao@1951	867	///n0 -> n1 [ label="0, length:3" ];
klao@1951	868	///}
klao@1951	869	///\enddot
klao@1951	870	///
klao@1951	871	///\code
klao@1951	872	///Graph g;
klao@1951	873	///Node s, t;
klao@1951	874	///LengthMap length(g);
klao@1951	875	///
klao@1951	876	///readDimacs(std::cin, g, length, s, t);
klao@1951	877	///
klao@1951	878	///cout << "edges with lengths (of form id, source--length->target): " << endl;
klao@1951	879	///for(EdgeIt e(g); e!=INVALID; ++e)
klao@1951	880	/// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
klao@1951	881	/// << length[e] << "->" << g.id(g.target(e)) << endl;
klao@1951	882	///
klao@1951	883	///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
klao@1951	884	///\endcode
klao@1951	885	///Next, the potential function is computed with Dijkstra.
klao@1951	886	///\code
klao@1951	887	///typedef Dijkstra<Graph, LengthMap> Dijkstra;
klao@1951	888	///Dijkstra dijkstra(g, length);
klao@1951	889	///dijkstra.run(s);
klao@1951	890	///\endcode
klao@1951	891	///Next, we consrtruct a map which filters the edge-set to the tight edges.
klao@1951	892	///\code
klao@1951	893	///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
klao@1951	894	/// TightEdgeFilter;
klao@1951	895	///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
klao@1951	896	///
deba@1991	897	///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
deba@1991	898	///SubGA ga(g, tight_edge_filter);
klao@1951	899	///\endcode
klao@1951	900	///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
klao@1951	901	///with a max flow algorithm Preflow.
klao@1951	902	///\code
klao@1951	903	///ConstMap<Edge, int> const_1_map(1);
klao@1951	904	///Graph::EdgeMap<int> flow(g, 0);
klao@1951	905	///
deba@1991	906	///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
deba@1991	907	/// preflow(ga, s, t, const_1_map, flow);
klao@1951	908	///preflow.run();
klao@1951	909	///\endcode
klao@1951	910	///Last, the output is:
klao@1951	911	///\code
klao@1951	912	///cout << "maximum number of edge-disjoint shortest path: "
klao@1951	913	/// << preflow.flowValue() << endl;
klao@1951	914	///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
klao@1951	915	/// << endl;
klao@1951	916	///for(EdgeIt e(g); e!=INVALID; ++e)
klao@1951	917	/// if (flow[e])
klao@1951	918	/// cout << " " << g.id(g.source(e)) << "--"
klao@1951	919	/// << length[e] << "->" << g.id(g.target(e)) << endl;
klao@1951	920	///\endcode
klao@1951	921	///The program has the following (expected :-)) output:
klao@1951	922	///\code
klao@1951	923	///edges with lengths (of form id, source--length->target):
klao@1951	924	/// 9, 5--4->6
klao@1951	925	/// 8, 4--2->6
klao@1951	926	/// 7, 3--1->5
klao@1951	927	/// 6, 2--3->5
klao@1951	928	/// 5, 2--5->6
klao@1951	929	/// 4, 2--2->4
klao@1951	930	/// 3, 1--3->4
klao@1951	931	/// 2, 0--1->3
klao@1951	932	/// 1, 0--2->2
klao@1951	933	/// 0, 0--3->1
klao@1951	934	///s: 0 t: 6
klao@1951	935	///maximum number of edge-disjoint shortest path: 2
klao@1951	936	///edges of the maximum number of edge-disjoint shortest s-t paths:
klao@1951	937	/// 9, 5--4->6
klao@1951	938	/// 8, 4--2->6
klao@1951	939	/// 7, 3--1->5
klao@1951	940	/// 4, 2--2->4
klao@1951	941	/// 2, 0--1->3
klao@1951	942	/// 1, 0--2->2
klao@1951	943	///\endcode
klao@1951	944	///
klao@1951	945	///\author Marton Makai
marci@932	946	template<typename Graph, typename EdgeFilterMap>
alpar@1401	947	class EdgeSubGraphAdaptor :
alpar@1401	948	public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
deba@1681	949	EdgeFilterMap, false> {
marci@932	950	public:
alpar@1401	951	typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
deba@1685	952	EdgeFilterMap, false> Parent;
marci@932	953	protected:
marci@932	954	ConstMap<typename Graph::Node, bool> const_true_map;
deba@1991	955
deba@1991	956	EdgeSubGraphAdaptor() : const_true_map(true) {
deba@1991	957	Parent::setNodeFilterMap(const_true_map);
deba@1991	958	}
deba@1991	959
marci@932	960	public:
deba@2031	961
alpar@1401	962	EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
marci@932	963	Parent(), const_true_map(true) {
marci@932	964	Parent::setGraph(_graph);
marci@932	965	Parent::setNodeFilterMap(const_true_map);
marci@932	966	Parent::setEdgeFilterMap(_edge_filter_map);
marci@932	967	}
deba@2031	968
marci@932	969	};
marci@932	970
deba@1991	971	/// \brief Just gives back an edge sub graph adaptor
deba@1991	972	///
deba@1991	973	/// Just gives back an edge sub graph adaptor
deba@1991	974	template<typename Graph, typename EdgeFilterMap>
deba@1991	975	EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
deba@1991	976	edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
deba@1991	977	return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
deba@1991	978	}
deba@1991	979
deba@1991	980	template<typename Graph, typename EdgeFilterMap>
deba@1991	981	EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
deba@1991	982	edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
deba@1991	983	return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
deba@1991	984	}
deba@1991	985
deba@1991	986	template <typename _Graph, typename Enable = void>
deba@1980	987	class UndirGraphAdaptorBase :
deba@1979	988	public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
marci@1383	989	public:
marci@1383	990	typedef _Graph Graph;
deba@2031	991	typedef UndirGraphAdaptorBase Adaptor;
deba@1979	992	typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
deba@1991	993
marci@1383	994	protected:
deba@1991	995
deba@1991	996	UndirGraphAdaptorBase() : Parent() {}
deba@1991	997
marci@1383	998	public:
deba@1991	999
klao@1909	1000	typedef typename Parent::UEdge UEdge;
marci@1383	1001	typedef typename Parent::Edge Edge;
deba@1991	1002
deba@2031	1003	private:
marci@1383	1004
deba@1991	1005	template <typename _Value>
deba@2031	1006	class EdgeMapBase {
deba@1991	1007	private:
deba@1991	1008
deba@1991	1009	typedef typename _Graph::template EdgeMap<_Value> MapImpl;
deba@1991	1010
marci@1383	1011	public:
deba@1991	1012
deba@1991	1013	typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
deba@1991	1014
deba@1991	1015	typedef _Value Value;
marci@1383	1016	typedef Edge Key;
marci@1383	1017
deba@2031	1018	EdgeMapBase(const Adaptor& adaptor) :
deba@2031	1019	forward_map(adaptor.graph), backward_map(adaptor.graph) {}
marci@569	1020
deba@2031	1021	EdgeMapBase(const Adaptor& adaptor, const Value& v)
deba@2031	1022	: forward_map(adaptor.graph, v), backward_map(adaptor.graph, v) {}
marci@1383	1023
deba@1991	1024	void set(const Edge& e, const Value& a) {
deba@1991	1025	if (Parent::direction(e)) {
marci@1383	1026	forward_map.set(e, a);
deba@1991	1027	} else {
deba@1991	1028	backward_map.set(e, a);
deba@1991	1029	}
marci@1383	1030	}
marci@556	1031
deba@1991	1032	typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
deba@1991	1033	if (Parent::direction(e)) {
marci@1383	1034	return forward_map[e];
deba@1991	1035	} else {
marci@1383	1036	return backward_map[e];
deba@1991	1037	}
marci@556	1038	}
deba@1991	1039
deba@1991	1040	typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
deba@1991	1041	if (Parent::direction(e)) {
deba@1991	1042	return forward_map[e];
deba@1991	1043	} else {
deba@1991	1044	return backward_map[e];
deba@1991	1045	}
deba@1991	1046	}
deba@1991	1047
deba@1991	1048	protected:
deba@1991	1049
deba@1991	1050	MapImpl forward_map, backward_map;
deba@1991	1051
marci@556	1052	};
deba@2031	1053
deba@2031	1054	public:
deba@2031	1055
deba@2031	1056	template <typename _Value>
deba@2031	1057	class EdgeMap
deba@2031	1058	: public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
deba@2031	1059	{
deba@2031	1060	public:
deba@2031	1061	typedef Adaptor Graph;
deba@2031	1062	typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
deba@2031	1063
deba@2031	1064	EdgeMap(const Graph& graph)
deba@2031	1065	: Parent(graph) {}
deba@2031	1066	EdgeMap(const Graph& graph, const _Value& value)
deba@2031	1067	: Parent(graph, value) {}
deba@2031	1068
deba@2031	1069	EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031	1070	return operator=<EdgeMap>(cmap);
deba@2031	1071	}
deba@2031	1072
deba@2031	1073	template <typename CMap>
deba@2031	1074	EdgeMap& operator=(const CMap& cmap) {
deba@2031	1075	Parent::operator=(cmap);
deba@2031	1076	return *this;
deba@2031	1077	}
deba@2031	1078	};
marci@1383	1079
deba@1991	1080	template <typename _Value>
deba@2031	1081	class UEdgeMap : public Graph::template EdgeMap<_Value> {
marci@1383	1082	public:
deba@2031	1083
deba@2031	1084	typedef typename Graph::template EdgeMap<_Value> Parent;
deba@2031	1085
deba@2031	1086	explicit UEdgeMap(const Adaptor& ga)
deba@2031	1087	: Parent(*ga.graph) {}
deba@1991	1088
deba@2031	1089	UEdgeMap(const Adaptor& ga, const _Value& value)
deba@2031	1090	: Parent(*ga.graph, value) {}
deba@1991	1091
deba@2031	1092	UEdgeMap& operator=(const UEdgeMap& cmap) {
deba@2031	1093	return operator=<UEdgeMap>(cmap);
deba@2031	1094	}
deba@1991	1095
deba@2031	1096	template <typename CMap>
deba@2031	1097	UEdgeMap& operator=(const CMap& cmap) {
deba@2031	1098	Parent::operator=(cmap);
deba@2031	1099	return *this;
deba@2031	1100	}
deba@2031	1101
deba@1991	1102	};
deba@1991	1103
deba@1991	1104	};
marci@556	1105
deba@1991	1106	template <typename _Graph>
deba@1991	1107	class UndirGraphAdaptorBase<
deba@1991	1108	_Graph, typename enable_if<
deba@1991	1109	typename _Graph::EdgeNotifier::Notifier>::type >
deba@1991	1110	: public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
deba@1991	1111	public:
deba@1991	1112
deba@1991	1113	typedef _Graph Graph;
deba@2031	1114	typedef UndirGraphAdaptorBase Adaptor;
deba@1991	1115	typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
deba@1991	1116
deba@1991	1117	protected:
deba@1991	1118
deba@1991	1119	UndirGraphAdaptorBase()
deba@1999	1120	: edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}
deba@1991	1121
deba@1991	1122	void setGraph(_Graph& graph) {
deba@1991	1123	Parent::setGraph(graph);
deba@1991	1124	edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge()));
deba@1991	1125	}
deba@1991	1126
deba@1991	1127	public:
deba@1991	1128
deba@1991	1129	~UndirGraphAdaptorBase() {
deba@1999	1130	edge_notifier.clear();
deba@1999	1131	}
deba@1999	1132
deba@1999	1133	int maxId(typename Parent::Edge) const {
deba@1999	1134	return Parent::maxEdgeId();
deba@1991	1135	}
deba@1991	1136
deba@1991	1137
deba@1991	1138	typedef typename Parent::UEdge UEdge;
deba@1991	1139	typedef typename Parent::Edge Edge;
deba@1991	1140
deba@1991	1141	typedef typename Parent::EdgeNotifier UEdgeNotifier;
deba@1991	1142
deba@1991	1143	using Parent::getNotifier;
deba@1991	1144
deba@1999	1145	typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
deba@1991	1146	EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
deba@1991	1147
deba@1991	1148	protected:
deba@1991	1149
deba@1991	1150	class NotifierProxy : public UEdgeNotifier::ObserverBase {
deba@1991	1151	public:
deba@1991	1152
deba@1991	1153	typedef typename UEdgeNotifier::ObserverBase Parent;
deba@1991	1154	typedef UndirGraphAdaptorBase AdaptorBase;
marci@1383	1155
deba@1991	1156	NotifierProxy(EdgeNotifier& _edge_notifier)
deba@1991	1157	: Parent(), edge_notifier(_edge_notifier) {
marci@1383	1158	}
marci@556	1159
deba@1991	1160	virtual ~NotifierProxy() {
deba@1991	1161	if (Parent::attached()) {
deba@1991	1162	Parent::detach();
deba@1991	1163	}
marci@1383	1164	}
deba@1991	1165
deba@1991	1166	void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
deba@1991	1167	Parent::attach(_uedge_notifier);
deba@1991	1168	}
deba@1991	1169
deba@1991	1170
deba@1991	1171	protected:
deba@1991	1172
deba@1991	1173	virtual void add(const UEdge& uedge) {
deba@1991	1174	std::vector<Edge> edges;
deba@1991	1175	edges.push_back(AdaptorBase::Parent::direct(uedge, true));
deba@1991	1176	edges.push_back(AdaptorBase::Parent::direct(uedge, false));
deba@1991	1177	edge_notifier.add(edges);
deba@1991	1178	}
deba@1991	1179	virtual void add(const std::vector<UEdge>& uedges) {
deba@1991	1180	std::vector<Edge> edges;
deba@1991	1181	for (int i = 0; i < (int)uedges.size(); ++i) {
deba@1991	1182	edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
deba@1991	1183	edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
deba@1991	1184	}
deba@1991	1185	edge_notifier.add(edges);
deba@1991	1186	}
deba@1991	1187	virtual void erase(const UEdge& uedge) {
deba@1991	1188	std::vector<Edge> edges;
deba@1991	1189	edges.push_back(AdaptorBase::Parent::direct(uedge, true));
deba@1991	1190	edges.push_back(AdaptorBase::Parent::direct(uedge, false));
deba@1991	1191	edge_notifier.erase(edges);
deba@1991	1192	}
deba@1991	1193	virtual void erase(const std::vector<UEdge>& uedges) {
deba@1991	1194	std::vector<Edge> edges;
deba@1991	1195	for (int i = 0; i < (int)uedges.size(); ++i) {
deba@1991	1196	edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
deba@1991	1197	edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
deba@1991	1198	}
deba@1991	1199	edge_notifier.erase(edges);
deba@1991	1200	}
deba@1991	1201	virtual void build() {
deba@1991	1202	edge_notifier.build();
deba@1991	1203	}
deba@1991	1204	virtual void clear() {
deba@1991	1205	edge_notifier.clear();
deba@1991	1206	}
deba@1991	1207
deba@1991	1208	EdgeNotifier& edge_notifier;
deba@1991	1209	};
deba@1991	1210
deba@1991	1211
deba@1991	1212	mutable EdgeNotifier edge_notifier;
deba@1991	1213	NotifierProxy edge_notifier_proxy;
deba@1991	1214
deba@2031	1215	private:
deba@1991	1216
deba@1991	1217	template <typename _Value>
deba@2031	1218	class EdgeMapBase {
deba@1991	1219	private:
deba@1991	1220
deba@1991	1221	typedef typename _Graph::template EdgeMap<_Value> MapImpl;
deba@1991	1222
deba@1991	1223	public:
deba@1991	1224
deba@1991	1225	typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
deba@1991	1226
deba@1991	1227	typedef _Value Value;
deba@1991	1228	typedef Edge Key;
deba@1991	1229
deba@2031	1230	EdgeMapBase(const Adaptor& adaptor) :
deba@2031	1231	forward_map(adaptor.graph), backward_map(adaptor.graph) {}
deba@1991	1232
deba@2031	1233	EdgeMapBase(const Adaptor& adaptor, const Value& v)
deba@2031	1234	: forward_map(adaptor.graph, v), backward_map(adaptor.graph, v) {}
deba@1991	1235
deba@1991	1236	void set(const Edge& e, const Value& a) {
deba@1991	1237	if (Parent::direction(e)) {
deba@1991	1238	forward_map.set(e, a);
deba@1991	1239	} else {
deba@1991	1240	backward_map.set(e, a);
deba@1991	1241	}
deba@1991	1242	}
deba@1991	1243
deba@2031	1244	typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
deba@1991	1245	if (Parent::direction(e)) {
deba@1991	1246	return forward_map[e];
deba@1991	1247	} else {
deba@1991	1248	return backward_map[e];
deba@1991	1249	}
deba@1991	1250	}
deba@1991	1251
deba@2031	1252	typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
deba@1991	1253	if (Parent::direction(e)) {
deba@1991	1254	return forward_map[e];
deba@1991	1255	} else {
deba@1991	1256	return backward_map[e];
deba@1991	1257	}
deba@1991	1258	}
deba@1991	1259
deba@1991	1260	protected:
deba@1991	1261
deba@1991	1262	MapImpl forward_map, backward_map;
deba@1991	1263
deba@1991	1264	};
deba@2031	1265
deba@2031	1266	public:
deba@2031	1267
deba@2031	1268	template <typename _Value>
deba@2031	1269	class EdgeMap
deba@2031	1270	: public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
deba@2031	1271	{
deba@2031	1272	public:
deba@2031	1273	typedef Adaptor Graph;
deba@2031	1274	typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
deba@2031	1275
deba@2031	1276	EdgeMap(const Graph& graph)
deba@2031	1277	: Parent(graph) {}
deba@2031	1278	EdgeMap(const Graph& graph, const _Value& value)
deba@2031	1279	: Parent(graph, value) {}
deba@2031	1280
deba@2031	1281	EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031	1282	return operator=<EdgeMap>(cmap);
deba@2031	1283	}
deba@2031	1284
deba@2031	1285	template <typename CMap>
deba@2031	1286	EdgeMap& operator=(const CMap& cmap) {
deba@2031	1287	Parent::operator=(cmap);
deba@2031	1288	return *this;
deba@2031	1289	}
deba@2031	1290	};
deba@1991	1291
deba@1991	1292	template <typename _Value>
deba@2031	1293	class UEdgeMap : public Graph::template EdgeMap<_Value> {
deba@1991	1294	public:
deba@2031	1295
deba@2031	1296	typedef typename Graph::template EdgeMap<_Value> Parent;
deba@2031	1297
deba@2031	1298	explicit UEdgeMap(const Adaptor& ga)
deba@2031	1299	: Parent(*ga.graph) {}
deba@1991	1300
deba@2031	1301	UEdgeMap(const Adaptor& ga, const _Value& value)
deba@2031	1302	: Parent(*ga.graph, value) {}
deba@1991	1303
deba@2031	1304	UEdgeMap& operator=(const UEdgeMap& cmap) {
deba@2031	1305	return operator=<UEdgeMap>(cmap);
deba@2031	1306	}
deba@1991	1307
deba@2031	1308	template <typename CMap>
deba@2031	1309	UEdgeMap& operator=(const CMap& cmap) {
deba@2031	1310	Parent::operator=(cmap);
deba@2031	1311	return *this;
deba@2031	1312	}
deba@2031	1313
marci@1383	1314	};
marci@1383	1315
marci@1383	1316	};
marci@1383	1317
klao@1951	1318	///\brief An undirected graph is made from a directed graph by an adaptor
klao@1951	1319	///\ingroup graph_adaptors
klao@1951	1320	///
klao@1951	1321	/// Undocumented, untested!!!
klao@1951	1322	/// If somebody knows nice demo application, let's polulate it.
klao@1951	1323	///
klao@1951	1324	/// \author Marton Makai
marci@1383	1325	template<typename _Graph>
deba@1980	1326	class UndirGraphAdaptor :
deba@1979	1327	public UGraphAdaptorExtender<
deba@1980	1328	UndirGraphAdaptorBase<_Graph> > {
marci@1383	1329	public:
marci@1383	1330	typedef _Graph Graph;
deba@1979	1331	typedef UGraphAdaptorExtender<
deba@1980	1332	UndirGraphAdaptorBase<_Graph> > Parent;
marci@1383	1333	protected:
deba@1980	1334	UndirGraphAdaptor() { }
marci@1383	1335	public:
deba@1980	1336	UndirGraphAdaptor(_Graph& _graph) {
marci@1383	1337	setGraph(_graph);
marci@556	1338	}
marci@556	1339
deba@1991	1340	template <typename _ForwardMap, typename _BackwardMap>
deba@1991	1341	class CombinedEdgeMap {
deba@1991	1342	public:
deba@1991	1343
deba@1991	1344	typedef _ForwardMap ForwardMap;
deba@1991	1345	typedef _BackwardMap BackwardMap;
marci@992	1346
deba@1991	1347	typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
marci@992	1348
deba@1991	1349	typedef typename ForwardMap::Value Value;
deba@1991	1350	typedef typename Parent::Edge Key;
deba@1991	1351
deba@1991	1352	CombinedEdgeMap() : forward_map(0), backward_map(0) {}
marci@992	1353
deba@1991	1354	CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
deba@1991	1355	: forward_map(&_forward_map), backward_map(&_backward_map) {}
marci@992	1356
deba@1991	1357	void set(const Key& e, const Value& a) {
deba@1991	1358	if (Parent::direction(e)) {
deba@1991	1359	forward_map->set(e, a);
deba@1991	1360	} else {
deba@1991	1361	backward_map->set(e, a);
deba@1991	1362	}
marci@992	1363	}
marci@992	1364
deba@1991	1365	typename MapTraits<ForwardMap>::ConstReturnValue
deba@1991	1366	operator[](const Key& e) const {
deba@1991	1367	if (Parent::direction(e)) {
deba@1991	1368	return (*forward_map)[e];
deba@1991	1369	} else {
deba@1991	1370	return (*backward_map)[e];
deba@1991	1371	}
marci@992	1372	}
marci@992	1373
deba@1991	1374	typename MapTraits<ForwardMap>::ReturnValue
deba@1991	1375	operator[](const Key& e) {
deba@1991	1376	if (Parent::direction(e)) {
deba@1991	1377	return (*forward_map)[e];
deba@1991	1378	} else {
deba@1991	1379	return (*backward_map)[e];
deba@1991	1380	}
marci@992	1381	}
deba@1991	1382
deba@1991	1383	void setForwardMap(ForwardMap& _forward_map) {
deba@1991	1384	forward_map = &_forward_map;
deba@1991	1385	}
deba@1991	1386
deba@1991	1387	void setBackwardMap(BackwardMap& _backward_map) {
deba@1991	1388	backward_map = &_backward_map;
deba@1991	1389	}
deba@1991	1390
deba@1991	1391	protected:
deba@1991	1392
deba@1991	1393	ForwardMap* forward_map;
deba@1991	1394	BackwardMap* backward_map;
deba@1991	1395
marci@992	1396	};
marci@992	1397
marci@992	1398	};
marci@569	1399
deba@1991	1400	/// \brief Just gives back an undir graph adaptor
klao@1951	1401	///
deba@1991	1402	/// Just gives back an undir graph adaptor
marci@650	1403	template<typename Graph>
deba@1991	1404	UndirGraphAdaptor<const Graph>
deba@1991	1405	undirGraphAdaptor(const Graph& graph) {
deba@1991	1406	return UndirGraphAdaptor<const Graph>(graph);
deba@1991	1407	}
marci@650	1408
deba@2034	1409	template<typename Graph, typename Number,
deba@2034	1410	typename CapacityMap, typename FlowMap,
deba@2034	1411	typename Tolerance = Tolerance<Number> >
marci@658	1412	class ResForwardFilter {
marci@650	1413	const CapacityMap* capacity;
marci@650	1414	const FlowMap* flow;
deba@2034	1415	Tolerance tolerance;
marci@650	1416	public:
deba@1991	1417	typedef typename Graph::Edge Key;
deba@1991	1418	typedef bool Value;
deba@1991	1419
deba@2034	1420	ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
deba@2034	1421	const Tolerance& _tolerance = Tolerance())
deba@2034	1422	: capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
deba@2034	1423
deba@2034	1424	ResForwardFilter(const Tolerance& _tolerance)
deba@2034	1425	: capacity(0), flow(0), tolerance(_tolerance) { }
deba@2034	1426
deba@1991	1427	void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
deba@1991	1428	void setFlow(const FlowMap& _flow) { flow = &_flow; }
deba@2034	1429
marci@650	1430	bool operator[](const typename Graph::Edge& e) const {
deba@2034	1431	return tolerance.less((flow)[e], (capacity)[e]);
marci@650	1432	}
marci@650	1433	};
marci@650	1434
marci@650	1435	template<typename Graph, typename Number,
deba@2034	1436	typename CapacityMap, typename FlowMap,
deba@2034	1437	typename Tolerance = Tolerance<Number> >
marci@658	1438	class ResBackwardFilter {
marci@650	1439	const CapacityMap* capacity;
marci@650	1440	const FlowMap* flow;
deba@2034	1441	Tolerance tolerance;
marci@650	1442	public:
deba@1991	1443	typedef typename Graph::Edge Key;
deba@1991	1444	typedef bool Value;
deba@1991	1445
deba@2034	1446	ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
deba@2034	1447	const Tolerance& _tolerance = Tolerance())
deba@2034	1448	: capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
deba@2034	1449	ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
deba@2034	1450	: capacity(0), flow(0), tolerance(_tolerance) { }
deba@1991	1451	void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
deba@1991	1452	void setFlow(const FlowMap& _flow) { flow = &_flow; }
marci@650	1453	bool operator[](const typename Graph::Edge& e) const {
deba@2034	1454	return tolerance.less(0, Number((*flow)[e]));
marci@650	1455	}
marci@650	1456	};
marci@650	1457
marci@653	1458
klao@1951	1459	///\brief An adaptor for composing the residual
klao@1951	1460	///graph for directed flow and circulation problems.
deba@2037	1461	///
klao@1951	1462	///\ingroup graph_adaptors
klao@1951	1463	///
deba@2042	1464	///An adaptor for composing the residual graph for directed flow and
deba@2042	1465	///circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
deba@2042	1466	///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
deba@2042	1467	///be functions on the edge-set.
deba@2042	1468	///
deba@2042	1469	///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
deba@2042	1470	///for a flow and \f$ c \f$ for a capacity function. Suppose that a
deba@2042	1471	///graph instange \c g of type \c ListGraph implements \f$ G \f$.
deba@2042	1472	///
deba@2042	1473	///\code
deba@2042	1474	/// ListGraph g;
deba@2042	1475	///\endcode
deba@2042	1476	///
deba@2042	1477	///Then RevGraphAdaptor implements the graph structure with node-set
deba@2042	1478	/// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
deba@2042	1479	///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
deba@2042	1480	/// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
deba@2042	1481	///residual graph. When we take the union
deba@2042	1482	/// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
deba@2042	1483	///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
deba@2042	1484	///then in the adaptor it appears twice. The following code shows how
deba@2042	1485	///such an instance can be constructed.
deba@2042	1486	///
deba@2042	1487	///\code
deba@2042	1488	/// typedef ListGraph Graph;
deba@2042	1489	/// Graph::EdgeMap<int> f(g);
deba@2042	1490	/// Graph::EdgeMap<int> c(g);
deba@2042	1491	/// ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
deba@2042	1492	///\endcode
deba@2042	1493	///\author Marton Makai
deba@2042	1494	///
marci@650	1495	template<typename Graph, typename Number,
deba@2034	1496	typename CapacityMap, typename FlowMap,
deba@2034	1497	typename Tolerance = Tolerance<Number> >
alpar@1401	1498	class ResGraphAdaptor :
deba@1991	1499	public EdgeSubGraphAdaptor<
deba@2034	1500	UndirGraphAdaptor<const Graph>,
deba@2034	1501	typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
deba@2034	1502	ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>,
deba@2034	1503	ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
marci@650	1504	public:
deba@1991	1505
deba@2034	1506	typedef UndirGraphAdaptor<const Graph> UGraph;
deba@1991	1507
deba@2034	1508	typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
deba@1991	1509	ForwardFilter;
deba@1991	1510
deba@2034	1511	typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
deba@1991	1512	BackwardFilter;
deba@1991	1513
deba@1991	1514	typedef typename UGraph::
deba@1991	1515	template CombinedEdgeMap<ForwardFilter, BackwardFilter>
deba@1991	1516	EdgeFilter;
deba@1991	1517
deba@1991	1518	typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
deba@1991	1519
marci@650	1520	protected:
deba@1991	1521
marci@650	1522	const CapacityMap* capacity;
marci@650	1523	FlowMap* flow;
deba@1991	1524
deba@1991	1525	UGraph ugraph;
deba@1991	1526	ForwardFilter forward_filter;
deba@1991	1527	BackwardFilter backward_filter;
deba@1991	1528	EdgeFilter edge_filter;
deba@1991	1529
marci@658	1530	void setCapacityMap(const CapacityMap& _capacity) {
marci@658	1531	capacity=&_capacity;
marci@658	1532	forward_filter.setCapacity(_capacity);
marci@658	1533	backward_filter.setCapacity(_capacity);
marci@658	1534	}
deba@1991	1535
marci@658	1536	void setFlowMap(FlowMap& _flow) {
marci@658	1537	flow=&_flow;
marci@658	1538	forward_filter.setFlow(_flow);
marci@658	1539	backward_filter.setFlow(_flow);
marci@658	1540	}
deba@1991	1541
marci@650	1542	public:
deba@1991	1543
deba@2034	1544	/// \brief Constructor of the residual graph.
deba@2034	1545	///
deba@2034	1546	/// Constructor of the residual graph. The parameters are the graph type,
deba@2034	1547	/// the flow map, the capacity map and a tolerance object.
deba@2034	1548	ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
deba@2034	1549	FlowMap& _flow, const Tolerance& _tolerance = Tolerance())
deba@2034	1550	: Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
deba@2034	1551	forward_filter(_capacity, _flow, _tolerance),
deba@2034	1552	backward_filter(_capacity, _flow, _tolerance),
deba@2034	1553	edge_filter(forward_filter, backward_filter)
deba@2034	1554	{
deba@1991	1555	Parent::setGraph(ugraph);
deba@1991	1556	Parent::setEdgeFilterMap(edge_filter);
marci@650	1557	}
marci@650	1558
marci@660	1559	typedef typename Parent::Edge Edge;
marci@660	1560
deba@2034	1561	/// \brief Gives back the residual capacity of the edge.
deba@2034	1562	///
deba@2034	1563	/// Gives back the residual capacity of the edge.
deba@2034	1564	Number rescap(const Edge& edge) const {
deba@2034	1565	if (UGraph::direction(edge)) {
deba@2034	1566	return (capacity)[edge]-(flow)[edge];
deba@2034	1567	} else {
deba@2034	1568	return (*flow)[edge];
deba@2034	1569	}
deba@2034	1570	}
deba@2034	1571
deba@2034	1572	/// \brief Augment on the given edge in the residual graph.
deba@2034	1573	///
deba@2034	1574	/// Augment on the given edge in the residual graph. It increase
deba@2034	1575	/// or decrease the flow on the original edge depend on the direction
deba@2034	1576	/// of the residual edge.
marci@660	1577	void augment(const Edge& e, Number a) const {
deba@1991	1578	if (UGraph::direction(e)) {
deba@2034	1579	flow->set(e, (*flow)[e] + a);
deba@1991	1580	} else {
deba@2034	1581	flow->set(e, (*flow)[e] - a);
deba@1991	1582	}
marci@650	1583	}
marci@650	1584
deba@2034	1585	/// \brief Returns the direction of the edge.
deba@2034	1586	///
deba@2034	1587	/// Returns true when the edge is same oriented as the original edge.
deba@1991	1588	static bool forward(const Edge& e) {
deba@1991	1589	return UGraph::direction(e);
deba@1991	1590	}
deba@1991	1591
deba@2034	1592	/// \brief Returns the direction of the edge.
deba@2034	1593	///
deba@2034	1594	/// Returns true when the edge is opposite oriented as the original edge.
deba@1991	1595	static bool backward(const Edge& e) {
deba@1991	1596	return !UGraph::direction(e);
deba@1991	1597	}
deba@1991	1598
deba@2034	1599	/// \brief Gives back the forward oriented residual edge.
deba@2034	1600	///
deba@2034	1601	/// Gives back the forward oriented residual edge.
deba@1991	1602	static Edge forward(const typename Graph::Edge& e) {
deba@1991	1603	return UGraph::direct(e, true);
deba@1991	1604	}
deba@1991	1605
deba@2034	1606	/// \brief Gives back the backward oriented residual edge.
deba@2034	1607	///
deba@2034	1608	/// Gives back the backward oriented residual edge.
deba@1991	1609	static Edge backward(const typename Graph::Edge& e) {
deba@1991	1610	return UGraph::direct(e, false);
deba@1991	1611	}
deba@1991	1612
klao@1951	1613	/// \brief Residual capacity map.
klao@1951	1614	///
klao@1951	1615	/// In generic residual graphs the residual capacity can be obtained
klao@1951	1616	/// as a map.
marci@660	1617	class ResCap {
marci@660	1618	protected:
deba@1991	1619	const ResGraphAdaptor* res_graph;
marci@660	1620	public:
alpar@987	1621	typedef Number Value;
alpar@987	1622	typedef Edge Key;
deba@1991	1623	ResCap(const ResGraphAdaptor& _res_graph)
deba@1991	1624	: res_graph(&_res_graph) {}
deba@1991	1625
deba@2034	1626	Number operator[](const Edge& e) const {
deba@2034	1627	return res_graph->rescap(e);
marci@660	1628	}
deba@1991	1629
marci@660	1630	};
marci@660	1631
marci@650	1632	};
marci@650	1633
marci@650	1634
marci@998	1635
marci@998	1636	template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401	1637	class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@998	1638	public:
marci@998	1639	typedef _Graph Graph;
alpar@1401	1640	typedef GraphAdaptorBase<_Graph> Parent;
marci@998	1641	protected:
marci@998	1642	FirstOutEdgesMap* first_out_edges;
alpar@1401	1643	ErasingFirstGraphAdaptorBase() : Parent(),
marci@998	1644	first_out_edges(0) { }
marci@998	1645
marci@998	1646	void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
marci@998	1647	first_out_edges=&_first_out_edges;
marci@998	1648	}
marci@998	1649
marci@998	1650	public:
marci@998	1651
marci@998	1652	typedef typename Parent::Node Node;
marci@998	1653	typedef typename Parent::Edge Edge;
marci@998	1654
marci@998	1655	void firstOut(Edge& i, const Node& n) const {
marci@998	1656	i=(*first_out_edges)[n];
marci@998	1657	}
marci@998	1658
marci@998	1659	void erase(const Edge& e) const {
marci@998	1660	Node n=source(e);
marci@998	1661	Edge f=e;
marci@998	1662	Parent::nextOut(f);
marci@998	1663	first_out_edges->set(n, f);
marci@998	1664	}
marci@998	1665	};
marci@998	1666
marci@998	1667
klao@1951	1668	///\brief For blocking flows.
klao@1951	1669	///\ingroup graph_adaptors
klao@1951	1670	///
klao@1951	1671	///This graph adaptor is used for on-the-fly
klao@1951	1672	///Dinits blocking flow computations.
klao@1951	1673	///For each node, an out-edge is stored which is used when the
klao@1951	1674	///\code
klao@1951	1675	///OutEdgeIt& first(OutEdgeIt&, const Node&)
klao@1951	1676	///\endcode
klao@1951	1677	///is called.
klao@1951	1678	///
klao@1951	1679	///\author Marton Makai
klao@1951	1680	///
marci@998	1681	template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401	1682	class ErasingFirstGraphAdaptor :
deba@1979	1683	public GraphAdaptorExtender<
alpar@1401	1684	ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
marci@650	1685	public:
marci@998	1686	typedef _Graph Graph;
deba@1979	1687	typedef GraphAdaptorExtender<
alpar@1401	1688	ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
alpar@1401	1689	ErasingFirstGraphAdaptor(Graph& _graph,
marci@998	1690	FirstOutEdgesMap& _first_out_edges) {
marci@998	1691	setGraph(_graph);
marci@998	1692	setFirstOutEdgesMap(_first_out_edges);
marci@998	1693	}
marci@1019	1694
marci@998	1695	};
marci@556	1696
deba@1989	1697	// template <typename _Graph>
deba@1989	1698	// class SplitGraphAdaptorBase
deba@1989	1699	// : public GraphAdaptorBase<_Graph> {
deba@1989	1700	// public:
deba@1989	1701	// typedef GraphAdaptorBase<_Graph> Parent;
deba@1697	1702
deba@1989	1703	// class Node;
deba@1989	1704	// class Edge;
deba@1989	1705	// template <typename T> class NodeMap;
deba@1989	1706	// template <typename T> class EdgeMap;
deba@1697	1707
deba@1697	1708
deba@1989	1709	// class Node : public Parent::Node {
deba@1989	1710	// friend class SplitGraphAdaptorBase;
deba@1989	1711	// template <typename T> friend class NodeMap;
deba@1989	1712	// typedef typename Parent::Node NodeParent;
deba@1989	1713	// private:
deba@1697	1714
deba@1989	1715	// bool entry;
deba@1989	1716	// Node(typename Parent::Node _node, bool _entry)
deba@1989	1717	// : Parent::Node(_node), entry(_entry) {}
deba@1697	1718
deba@1989	1719	// public:
deba@1989	1720	// Node() {}
deba@1989	1721	// Node(Invalid) : NodeParent(INVALID), entry(true) {}
deba@1697	1722
deba@1989	1723	// bool operator==(const Node& node) const {
deba@1989	1724	// return NodeParent::operator==(node) && entry == node.entry;
deba@1989	1725	// }
deba@1697	1726
deba@1989	1727	// bool operator!=(const Node& node) const {
deba@1989	1728	// return !(*this == node);
deba@1989	1729	// }
deba@1697	1730
deba@1989	1731	// bool operator<(const Node& node) const {
deba@1989	1732	// return NodeParent::operator<(node) \|\|
deba@1989	1733	// (NodeParent::operator==(node) && entry < node.entry);
deba@1989	1734	// }
deba@1989	1735	// };
deba@1697	1736
deba@1989	1737	// /// \todo May we want VARIANT/union type
deba@1989	1738	// class Edge : public Parent::Edge {
deba@1989	1739	// friend class SplitGraphAdaptorBase;
deba@1989	1740	// template <typename T> friend class EdgeMap;
deba@1989	1741	// private:
deba@1989	1742	// typedef typename Parent::Edge EdgeParent;
deba@1989	1743	// typedef typename Parent::Node NodeParent;
deba@1989	1744	// NodeParent bind;
deba@1697	1745
deba@1989	1746	// Edge(const EdgeParent& edge, const NodeParent& node)
deba@1989	1747	// : EdgeParent(edge), bind(node) {}
deba@1989	1748	// public:
deba@1989	1749	// Edge() {}
deba@1989	1750	// Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
deba@1697	1751
deba@1989	1752	// bool operator==(const Edge& edge) const {
deba@1989	1753	// return EdgeParent::operator==(edge) && bind == edge.bind;
deba@1989	1754	// }
deba@1697	1755
deba@1989	1756	// bool operator!=(const Edge& edge) const {
deba@1989	1757	// return !(*this == edge);
deba@1989	1758	// }
deba@1697	1759
deba@1989	1760	// bool operator<(const Edge& edge) const {
deba@1989	1761	// return EdgeParent::operator<(edge) \|\|
deba@1989	1762	// (EdgeParent::operator==(edge) && bind < edge.bind);
deba@1989	1763	// }
deba@1989	1764	// };
deba@1697	1765
deba@1989	1766	// void first(Node& node) const {
deba@1989	1767	// Parent::first(node);
deba@1989	1768	// node.entry = true;
deba@1989	1769	// }
deba@1697	1770
deba@1989	1771	// void next(Node& node) const {
deba@1989	1772	// if (node.entry) {
deba@1989	1773	// node.entry = false;
deba@1989	1774	// } else {
deba@1989	1775	// node.entry = true;
deba@1989	1776	// Parent::next(node);
deba@1989	1777	// }
deba@1989	1778	// }
deba@1697	1779
deba@1989	1780	// void first(Edge& edge) const {
deba@1989	1781	// Parent::first(edge);
deba@1989	1782	// if ((typename Parent::Edge&)edge == INVALID) {
deba@1989	1783	// Parent::first(edge.bind);
deba@1989	1784	// } else {
deba@1989	1785	// edge.bind = INVALID;
deba@1989	1786	// }
deba@1989	1787	// }
deba@1697	1788
deba@1989	1789	// void next(Edge& edge) const {
deba@1989	1790	// if ((typename Parent::Edge&)edge != INVALID) {
deba@1989	1791	// Parent::next(edge);
deba@1989	1792	// if ((typename Parent::Edge&)edge == INVALID) {
deba@1989	1793	// Parent::first(edge.bind);
deba@1989	1794	// }
deba@1989	1795	// } else {
deba@1989	1796	// Parent::next(edge.bind);
deba@1989	1797	// }
deba@1989	1798	// }
deba@1697	1799
deba@1989	1800	// void firstIn(Edge& edge, const Node& node) const {
deba@1989	1801	// if (node.entry) {
deba@1989	1802	// Parent::firstIn(edge, node);
deba@1989	1803	// edge.bind = INVALID;
deba@1989	1804	// } else {
deba@1989	1805	// (typename Parent::Edge&)edge = INVALID;
deba@1989	1806	// edge.bind = node;
deba@1989	1807	// }
deba@1989	1808	// }
deba@1697	1809
deba@1989	1810	// void nextIn(Edge& edge) const {
deba@1989	1811	// if ((typename Parent::Edge&)edge != INVALID) {
deba@1989	1812	// Parent::nextIn(edge);
deba@1989	1813	// } else {
deba@1989	1814	// edge.bind = INVALID;
deba@1989	1815	// }
deba@1989	1816	// }
deba@1697	1817
deba@1989	1818	// void firstOut(Edge& edge, const Node& node) const {
deba@1989	1819	// if (!node.entry) {
deba@1989	1820	// Parent::firstOut(edge, node);
deba@1989	1821	// edge.bind = INVALID;
deba@1989	1822	// } else {
deba@1989	1823	// (typename Parent::Edge&)edge = INVALID;
deba@1989	1824	// edge.bind = node;
deba@1989	1825	// }
deba@1989	1826	// }
deba@1697	1827
deba@1989	1828	// void nextOut(Edge& edge) const {
deba@1989	1829	// if ((typename Parent::Edge&)edge != INVALID) {
deba@1989	1830	// Parent::nextOut(edge);
deba@1989	1831	// } else {
deba@1989	1832	// edge.bind = INVALID;
deba@1989	1833	// }
deba@1989	1834	// }
deba@1697	1835
deba@1989	1836	// Node source(const Edge& edge) const {
deba@1989	1837	// if ((typename Parent::Edge&)edge != INVALID) {
deba@1989	1838	// return Node(Parent::source(edge), false);
deba@1989	1839	// } else {
deba@1989	1840	// return Node(edge.bind, true);
deba@1989	1841	// }
deba@1989	1842	// }
deba@1697	1843
deba@1989	1844	// Node target(const Edge& edge) const {
deba@1989	1845	// if ((typename Parent::Edge&)edge != INVALID) {
deba@1989	1846	// return Node(Parent::target(edge), true);
deba@1989	1847	// } else {
deba@1989	1848	// return Node(edge.bind, false);
deba@1989	1849	// }
deba@1989	1850	// }
deba@1697	1851
deba@1989	1852	// static bool entryNode(const Node& node) {
deba@1989	1853	// return node.entry;
deba@1989	1854	// }
deba@1697	1855
deba@1989	1856	// static bool exitNode(const Node& node) {
deba@1989	1857	// return !node.entry;
deba@1989	1858	// }
deba@1697	1859
deba@1989	1860	// static Node getEntry(const typename Parent::Node& node) {
deba@1989	1861	// return Node(node, true);
deba@1989	1862	// }
deba@1697	1863
deba@1989	1864	// static Node getExit(const typename Parent::Node& node) {
deba@1989	1865	// return Node(node, false);
deba@1989	1866	// }
deba@1697	1867
deba@1989	1868	// static bool originalEdge(const Edge& edge) {
deba@1989	1869	// return (typename Parent::Edge&)edge != INVALID;
deba@1989	1870	// }
deba@1697	1871
deba@1989	1872	// static bool bindingEdge(const Edge& edge) {
deba@1989	1873	// return edge.bind != INVALID;
deba@1989	1874	// }
deba@1697	1875
deba@1989	1876	// static Node getBindedNode(const Edge& edge) {
deba@1989	1877	// return edge.bind;
deba@1989	1878	// }
deba@1697	1879
deba@1989	1880	// int nodeNum() const {
deba@1989	1881	// return Parent::nodeNum() * 2;
deba@1989	1882	// }
deba@1697	1883
deba@1989	1884	// typedef True EdgeNumTag;
deba@1697	1885
deba@1989	1886	// int edgeNum() const {
deba@1989	1887	// return countEdges() + Parent::nodeNum();
deba@1989	1888	// }
deba@1697	1889
deba@1989	1890	// Edge findEdge(const Node& source, const Node& target,
deba@1989	1891	// const Edge& prev = INVALID) const {
deba@1989	1892	// if (exitNode(source) && entryNode(target)) {
deba@1989	1893	// return Parent::findEdge(source, target, prev);
deba@1989	1894	// } else {
deba@1989	1895	// if (prev == INVALID && entryNode(source) && exitNode(target) &&
deba@1989	1896	// (typename Parent::Node&)source == (typename Parent::Node&)target) {
deba@1989	1897	// return Edge(INVALID, source);
deba@1989	1898	// } else {
deba@1989	1899	// return INVALID;
deba@1989	1900	// }
deba@1989	1901	// }
deba@1989	1902	// }
deba@1697	1903
deba@1989	1904	// template <typename T>
deba@1989	1905	// class NodeMap : public MapBase<Node, T> {
deba@1989	1906	// typedef typename Parent::template NodeMap<T> NodeImpl;
deba@1989	1907	// public:
deba@1989	1908	// NodeMap(const SplitGraphAdaptorBase& _graph)
deba@1989	1909	// : entry(_graph), exit(_graph) {}
deba@1989	1910	// NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
deba@1989	1911	// : entry(_graph, t), exit(_graph, t) {}
deba@1697	1912
deba@1989	1913	// void set(const Node& key, const T& val) {
deba@1989	1914	// if (key.entry) { entry.set(key, val); }
deba@1989	1915	// else {exit.set(key, val); }
deba@1989	1916	// }
deba@1697	1917
deba@1989	1918	// typename MapTraits<NodeImpl>::ReturnValue
deba@1989	1919	// operator[](const Node& key) {
deba@1989	1920	// if (key.entry) { return entry[key]; }
deba@1989	1921	// else { return exit[key]; }
deba@1989	1922	// }
deba@1697	1923
deba@1989	1924	// typename MapTraits<NodeImpl>::ConstReturnValue
deba@1989	1925	// operator[](const Node& key) const {
deba@1989	1926	// if (key.entry) { return entry[key]; }
deba@1989	1927	// else { return exit[key]; }
deba@1989	1928	// }
deba@1697	1929
deba@1989	1930	// private:
deba@1989	1931	// NodeImpl entry, exit;
deba@1989	1932	// };
deba@1697	1933
deba@1989	1934	// template <typename T>
deba@1989	1935	// class EdgeMap : public MapBase<Edge, T> {
deba@1989	1936	// typedef typename Parent::template NodeMap<T> NodeImpl;
deba@1989	1937	// typedef typename Parent::template EdgeMap<T> EdgeImpl;
deba@1989	1938	// public:
deba@1989	1939	// EdgeMap(const SplitGraphAdaptorBase& _graph)
deba@1989	1940	// : bind(_graph), orig(_graph) {}
deba@1989	1941	// EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
deba@1989	1942	// : bind(_graph, t), orig(_graph, t) {}
deba@1697	1943
deba@1989	1944	// void set(const Edge& key, const T& val) {
deba@1989	1945	// if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
deba@1989	1946	// else {bind.set(key.bind, val); }
deba@1989	1947	// }
deba@1697	1948
deba@1989	1949	// typename MapTraits<EdgeImpl>::ReturnValue
deba@1989	1950	// operator[](const Edge& key) {
deba@1989	1951	// if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
deba@1989	1952	// else {return bind[key.bind]; }
deba@1989	1953	// }
deba@1697	1954
deba@1989	1955	// typename MapTraits<EdgeImpl>::ConstReturnValue
deba@1989	1956	// operator[](const Edge& key) const {
deba@1989	1957	// if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
deba@1989	1958	// else {return bind[key.bind]; }
deba@1989	1959	// }
deba@1697	1960
deba@1989	1961	// private:
deba@1989	1962	// typename Parent::template NodeMap<T> bind;
deba@1989	1963	// typename Parent::template EdgeMap<T> orig;
deba@1989	1964	// };
deba@1697	1965
deba@1989	1966	// template <typename EntryMap, typename ExitMap>
deba@1989	1967	// class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
deba@1989	1968	// public:
deba@1989	1969	// typedef MapBase<Node, typename EntryMap::Value> Parent;
deba@1697	1970
deba@1989	1971	// typedef typename Parent::Key Key;
deba@1989	1972	// typedef typename Parent::Value Value;
deba@1697	1973
deba@1989	1974	// CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
deba@1989	1975	// : entryMap(_entryMap), exitMap(_exitMap) {}
deba@1697	1976
deba@1989	1977	// Value& operator[](const Key& key) {
deba@1989	1978	// if (key.entry) {
deba@1989	1979	// return entryMap[key];
deba@1989	1980	// } else {
deba@1989	1981	// return exitMap[key];
deba@1989	1982	// }
deba@1989	1983	// }
deba@1697	1984
deba@1989	1985	// Value operator[](const Key& key) const {
deba@1989	1986	// if (key.entry) {
deba@1989	1987	// return entryMap[key];
deba@1989	1988	// } else {
deba@1989	1989	// return exitMap[key];
deba@1989	1990	// }
deba@1989	1991	// }
deba@1697	1992
deba@1989	1993	// void set(const Key& key, const Value& value) {
deba@1989	1994	// if (key.entry) {
deba@1989	1995	// entryMap.set(key, value);
deba@1989	1996	// } else {
deba@1989	1997	// exitMap.set(key, value);
deba@1989	1998	// }
deba@1989	1999	// }
deba@1697	2000
deba@1989	2001	// private:
deba@1697	2002
deba@1989	2003	// EntryMap& entryMap;
deba@1989	2004	// ExitMap& exitMap;
deba@1697	2005
deba@1989	2006	// };
deba@1697	2007
deba@1989	2008	// template <typename EdgeMap, typename NodeMap>
deba@1989	2009	// class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
deba@1989	2010	// public:
deba@1989	2011	// typedef MapBase<Edge, typename EdgeMap::Value> Parent;
deba@1697	2012
deba@1989	2013	// typedef typename Parent::Key Key;
deba@1989	2014	// typedef typename Parent::Value Value;
deba@1697	2015
deba@1989	2016	// CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
deba@1989	2017	// : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
deba@1697	2018
deba@1989	2019	// void set(const Edge& edge, const Value& val) {
deba@1989	2020	// if (SplitGraphAdaptorBase::originalEdge(edge)) {
deba@1989	2021	// edgeMap.set(edge, val);
deba@1989	2022	// } else {
deba@1989	2023	// nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
deba@1989	2024	// }
deba@1989	2025	// }
deba@1697	2026
deba@1989	2027	// Value operator[](const Key& edge) const {
deba@1989	2028	// if (SplitGraphAdaptorBase::originalEdge(edge)) {
deba@1989	2029	// return edgeMap[edge];
deba@1989	2030	// } else {
deba@1989	2031	// return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
deba@1989	2032	// }
deba@1989	2033	// }
deba@1697	2034
deba@1989	2035	// Value& operator[](const Key& edge) {
deba@1989	2036	// if (SplitGraphAdaptorBase::originalEdge(edge)) {
deba@1989	2037	// return edgeMap[edge];
deba@1989	2038	// } else {
deba@1989	2039	// return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
deba@1989	2040	// }
deba@1989	2041	// }
deba@1697	2042
deba@1989	2043	// private:
deba@1989	2044	// EdgeMap& edgeMap;
deba@1989	2045	// NodeMap& nodeMap;
deba@1989	2046	// };
deba@1697	2047
deba@1989	2048	// };
deba@1697	2049
deba@1989	2050	// template <typename _Graph>
deba@1989	2051	// class SplitGraphAdaptor
deba@1989	2052	// : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
deba@1989	2053	// public:
deba@1989	2054	// typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
deba@1697	2055
deba@1989	2056	// SplitGraphAdaptor(_Graph& graph) {
deba@1989	2057	// Parent::setGraph(graph);
deba@1989	2058	// }
deba@1697	2059
deba@1697	2060
deba@1989	2061	// };
deba@1697	2062
alpar@921	2063	} //namespace lemon
marci@556	2064
alpar@1401	2065	#endif //LEMON_GRAPH_ADAPTOR_H
marci@556	2066

author	ladanyi
	Tue, 02 May 2006 18:23:42 +0000
changeset 2068	6936f130bba2
parent 2037	32e4bebee616
child 2079	7fe378247fea
permissions	-rw-r--r--