lemon-0.x: lemon/graph_adaptor.h@94a7deb46c07 (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
deba@2079	39	#include <algorithm>
marci@556	40
alpar@921	41	namespace lemon {
marci@556	42
klao@1951	43	///\brief Base type for the Graph Adaptors
klao@1951	44	///
klao@1951	45	///Base type for the Graph Adaptors
klao@1951	46	///
klao@1951	47	///This is the base type for most of LEMON graph adaptors.
klao@1951	48	///This class implements a trivial graph adaptor i.e. it only wraps the
klao@1951	49	///functions and types of the graph. The purpose of this class is to
klao@1951	50	///make easier implementing graph adaptors. E.g. if an adaptor is
klao@1951	51	///considered which differs from the wrapped graph only in some of its
klao@1951	52	///functions or types, then it can be derived from GraphAdaptor,
klao@1951	53	///and only the
klao@1951	54	///differences should be implemented.
klao@1951	55	///
klao@1951	56	///author Marton Makai
marci@970	57	template<typename _Graph>
alpar@1401	58	class GraphAdaptorBase {
marci@970	59	public:
marci@970	60	typedef _Graph Graph;
deba@2031	61	typedef GraphAdaptorBase Adaptor;
marci@970	62	typedef Graph ParentGraph;
marci@970	63
marci@556	64	protected:
marci@556	65	Graph* graph;
alpar@1401	66	GraphAdaptorBase() : graph(0) { }
marci@556	67	void setGraph(Graph& _graph) { graph=&_graph; }
marci@556	68
marci@556	69	public:
alpar@1401	70	GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
deba@2034	71
alpar@774	72	typedef typename Graph::Node Node;
alpar@774	73	typedef typename Graph::Edge Edge;
marci@556	74
marci@970	75	void first(Node& i) const { graph->first(i); }
marci@970	76	void first(Edge& i) const { graph->first(i); }
marci@970	77	void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
marci@970	78	void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
marci@556	79
marci@970	80	void next(Node& i) const { graph->next(i); }
marci@970	81	void next(Edge& i) const { graph->next(i); }
marci@970	82	void nextIn(Edge& i) const { graph->nextIn(i); }
marci@970	83	void nextOut(Edge& i) const { graph->nextOut(i); }
marci@970	84
alpar@986	85	Node source(const Edge& e) const { return graph->source(e); }
alpar@986	86	Node target(const Edge& e) const { return graph->target(e); }
marci@556	87
deba@1697	88	typedef NodeNumTagIndicator<Graph> NodeNumTag;
marci@556	89	int nodeNum() const { return graph->nodeNum(); }
deba@1697	90
deba@1697	91	typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
marci@556	92	int edgeNum() const { return graph->edgeNum(); }
deba@1697	93
deba@1697	94	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1697	95	Edge findEdge(const Node& source, const Node& target,
deba@1697	96	const Edge& prev = INVALID) {
deba@1697	97	return graph->findEdge(source, target, prev);
deba@1697	98	}
marci@556	99
deba@1697	100	Node addNode() const {
deba@1697	101	return Node(graph->addNode());
deba@1697	102	}
deba@1697	103
alpar@986	104	Edge addEdge(const Node& source, const Node& target) const {
deba@1697	105	return Edge(graph->addEdge(source, target));
deba@1697	106	}
marci@556	107
marci@556	108	void erase(const Node& i) const { graph->erase(i); }
marci@556	109	void erase(const Edge& i) const { graph->erase(i); }
marci@556	110
marci@556	111	void clear() const { graph->clear(); }
marci@556	112
marci@739	113	int id(const Node& v) const { return graph->id(v); }
marci@739	114	int id(const Edge& e) const { return graph->id(e); }
deba@1991	115
deba@2031	116	Node fromNodeId(int id) const {
deba@2031	117	return graph->fromNodeId(id);
deba@2031	118	}
deba@2031	119
deba@2031	120	Edge fromEdgeId(int id) const {
deba@2031	121	return graph->fromEdgeId(id);
deba@2031	122	}
deba@2031	123
deba@1991	124	int maxNodeId() const {
deba@1991	125	return graph->maxNodeId();
deba@1991	126	}
deba@1991	127
deba@1991	128	int maxEdgeId() const {
deba@1991	129	return graph->maxEdgeId();
deba@1991	130	}
deba@1991	131
deba@1991	132	typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@1991	133
deba@1991	134	NodeNotifier& getNotifier(Node) const {
deba@1991	135	return graph->getNotifier(Node());
deba@1991	136	}
deba@1991	137
deba@1991	138	typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@1991	139
deba@1991	140	EdgeNotifier& getNotifier(Edge) const {
deba@1991	141	return graph->getNotifier(Edge());
deba@1991	142	}
marci@650	143
marci@970	144	template <typename _Value>
deba@2031	145	class NodeMap : public Graph::template NodeMap<_Value> {
marci@970	146	public:
deba@2031	147
deba@2031	148	typedef typename Graph::template NodeMap<_Value> Parent;
deba@2031	149
deba@2031	150	explicit NodeMap(const Adaptor& ga)
deba@2031	151	: Parent(*ga.graph) {}
deba@2031	152
deba@2031	153	NodeMap(const Adaptor& ga, const _Value& value)
deba@1991	154	: Parent(*ga.graph, value) { }
deba@2031	155
deba@2031	156	NodeMap& operator=(const NodeMap& cmap) {
deba@2031	157	return operator=<NodeMap>(cmap);
deba@2031	158	}
deba@2031	159
deba@2031	160	template <typename CMap>
deba@2031	161	NodeMap& operator=(const CMap& cmap) {
deba@2031	162	Parent::operator=(cmap);
deba@2031	163	return *this;
deba@2031	164	}
deba@2031	165
marci@970	166	};
marci@556	167
marci@970	168	template <typename _Value>
deba@2031	169	class EdgeMap : public Graph::template EdgeMap<_Value> {
marci@970	170	public:
deba@2031	171
deba@2031	172	typedef typename Graph::template EdgeMap<_Value> Parent;
deba@2031	173
deba@2031	174	explicit EdgeMap(const Adaptor& ga)
deba@2031	175	: Parent(*ga.graph) {}
deba@2031	176
deba@2031	177	EdgeMap(const Adaptor& ga, const _Value& value)
deba@2031	178	: Parent(*ga.graph, value) {}
deba@2031	179
deba@2031	180	EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031	181	return operator=<EdgeMap>(cmap);
deba@2031	182	}
deba@2031	183
deba@2031	184	template <typename CMap>
deba@2031	185	EdgeMap& operator=(const CMap& cmap) {
deba@2031	186	Parent::operator=(cmap);
deba@2031	187	return *this;
deba@2031	188	}
deba@2031	189
marci@970	190	};
deba@877	191
marci@556	192	};
marci@556	193
deba@2081	194	///\ingroup graph_adaptors
deba@2081	195	///
deba@2081	196	///\brief Trivial Graph Adaptor
deba@2081	197	///
deba@2081	198	/// This class is an adaptor which does not change the adapted graph.
deba@2081	199	/// It can be used only to test the graph adaptors.
marci@970	200	template <typename _Graph>
alpar@1401	201	class GraphAdaptor :
deba@1979	202	public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
marci@970	203	public:
marci@970	204	typedef _Graph Graph;
deba@1979	205	typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
marci@970	206	protected:
alpar@1401	207	GraphAdaptor() : Parent() { }
marci@569	208
marci@970	209	public:
deba@1755	210	explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
marci@970	211	};
marci@569	212
deba@1991	213	/// \brief Just gives back a graph adaptor
deba@1991	214	///
deba@1991	215	/// Just gives back a graph adaptor which
deba@1991	216	/// should be provide original graph
deba@1991	217	template<typename Graph>
deba@1991	218	GraphAdaptor<const Graph>
deba@1991	219	graphAdaptor(const Graph& graph) {
deba@1991	220	return GraphAdaptor<const Graph>(graph);
deba@1991	221	}
deba@1991	222
deba@1991	223
marci@997	224	template <typename _Graph>
alpar@1401	225	class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@997	226	public:
marci@997	227	typedef _Graph Graph;
alpar@1401	228	typedef GraphAdaptorBase<_Graph> Parent;
marci@997	229	protected:
alpar@1401	230	RevGraphAdaptorBase() : Parent() { }
marci@997	231	public:
marci@997	232	typedef typename Parent::Node Node;
marci@997	233	typedef typename Parent::Edge Edge;
marci@997	234
marci@997	235	void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
marci@997	236	void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
marci@997	237
marci@997	238	void nextIn(Edge& i) const { Parent::nextOut(i); }
marci@997	239	void nextOut(Edge& i) const { Parent::nextIn(i); }
marci@997	240
marci@997	241	Node source(const Edge& e) const { return Parent::target(e); }
marci@997	242	Node target(const Edge& e) const { return Parent::source(e); }
deba@1991	243
deba@1991	244	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1991	245	Edge findEdge(const Node& source, const Node& target,
deba@1991	246	const Edge& prev = INVALID) {
deba@1991	247	return Parent::findEdge(target, source, prev);
deba@1991	248	}
deba@1991	249
marci@997	250	};
marci@997	251
marci@997	252
deba@2081	253	///\ingroup graph_adaptors
deba@2081	254	///
alpar@1949	255	///\brief A graph adaptor which reverses the orientation of the edges.
alpar@1949	256	///
alpar@1949	257	/// If \c g is defined as
alpar@1946	258	///\code
marci@923	259	/// ListGraph g;
alpar@1946	260	///\endcode
alpar@1949	261	/// then
alpar@1946	262	///\code
deba@1991	263	/// RevGraphAdaptor<ListGraph> ga(g);
alpar@1946	264	///\endcode
deba@2079	265	/// implements the graph obtained from \c g by
alpar@1949	266	/// reversing the orientation of its edges.
marci@997	267	template<typename _Graph>
alpar@1401	268	class RevGraphAdaptor :
deba@1979	269	public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
marci@650	270	public:
marci@997	271	typedef _Graph Graph;
deba@1979	272	typedef GraphAdaptorExtender<
alpar@1401	273	RevGraphAdaptorBase<_Graph> > Parent;
marci@556	274	protected:
alpar@1401	275	RevGraphAdaptor() { }
marci@556	276	public:
deba@1755	277	explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
marci@997	278	};
marci@556	279
deba@1991	280	/// \brief Just gives back a reverse graph adaptor
deba@1991	281	///
deba@1991	282	/// Just gives back a reverse graph adaptor
deba@1991	283	template<typename Graph>
deba@1991	284	RevGraphAdaptor<const Graph>
deba@1991	285	revGraphAdaptor(const Graph& graph) {
deba@1991	286	return RevGraphAdaptor<const Graph>(graph);
deba@1991	287	}
deba@1991	288
deba@1681	289	template <typename _Graph, typename NodeFilterMap,
deba@1681	290	typename EdgeFilterMap, bool checked = true>
alpar@1401	291	class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@992	292	public:
marci@992	293	typedef _Graph Graph;
deba@2031	294	typedef SubGraphAdaptorBase Adaptor;
alpar@1401	295	typedef GraphAdaptorBase<_Graph> Parent;
marci@992	296	protected:
marci@992	297	NodeFilterMap* node_filter_map;
marci@992	298	EdgeFilterMap* edge_filter_map;
alpar@1401	299	SubGraphAdaptorBase() : Parent(),
marci@992	300	node_filter_map(0), edge_filter_map(0) { }
marci@775	301
marci@992	302	void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
marci@992	303	node_filter_map=&_node_filter_map;
marci@992	304	}
marci@992	305	void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
marci@992	306	edge_filter_map=&_edge_filter_map;
marci@992	307	}
marci@992	308
marci@992	309	public:
marci@992	310
marci@992	311	typedef typename Parent::Node Node;
marci@992	312	typedef typename Parent::Edge Edge;
marci@992	313
marci@992	314	void first(Node& i) const {
marci@992	315	Parent::first(i);
marci@992	316	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
marci@992	317	}
deba@1681	318
deba@1681	319	void first(Edge& i) const {
deba@1681	320	Parent::first(i);
deba@1681	321	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	322	\|\| !(*node_filter_map)[Parent::source(i)]
deba@1681	323	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
deba@1681	324	}
deba@1681	325
deba@1681	326	void firstIn(Edge& i, const Node& n) const {
deba@1681	327	Parent::firstIn(i, n);
deba@1681	328	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	329	\|\| !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
deba@1681	330	}
deba@1681	331
deba@1681	332	void firstOut(Edge& i, const Node& n) const {
deba@1681	333	Parent::firstOut(i, n);
deba@1681	334	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	335	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
deba@1681	336	}
deba@1681	337
deba@1681	338	void next(Node& i) const {
deba@1681	339	Parent::next(i);
deba@1681	340	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
deba@1681	341	}
deba@1681	342
deba@1681	343	void next(Edge& i) const {
deba@1681	344	Parent::next(i);
deba@1681	345	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	346	\|\| !(*node_filter_map)[Parent::source(i)]
deba@1681	347	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
deba@1681	348	}
deba@1681	349
deba@1681	350	void nextIn(Edge& i) const {
deba@1681	351	Parent::nextIn(i);
deba@1681	352	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	353	\|\| !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
deba@1681	354	}
deba@1681	355
deba@1681	356	void nextOut(Edge& i) const {
deba@1681	357	Parent::nextOut(i);
deba@1681	358	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	359	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
deba@1681	360	}
deba@1681	361
klao@1951	362	///\e
alpar@1949	363
klao@1951	364	/// This function hides \c n in the graph, i.e. the iteration
klao@1951	365	/// jumps over it. This is done by simply setting the value of \c n
klao@1951	366	/// to be false in the corresponding node-map.
deba@1681	367	void hide(const Node& n) const { node_filter_map->set(n, false); }
deba@1681	368
klao@1951	369	///\e
alpar@1949	370
klao@1951	371	/// This function hides \c e in the graph, i.e. the iteration
klao@1951	372	/// jumps over it. This is done by simply setting the value of \c e
klao@1951	373	/// to be false in the corresponding edge-map.
deba@1681	374	void hide(const Edge& e) const { edge_filter_map->set(e, false); }
deba@1681	375
klao@1951	376	///\e
alpar@1949	377
klao@1951	378	/// The value of \c n is set to be true in the node-map which stores
klao@1951	379	/// hide information. If \c n was hidden previuosly, then it is shown
klao@1951	380	/// again
deba@1681	381	void unHide(const Node& n) const { node_filter_map->set(n, true); }
deba@1681	382
klao@1951	383	///\e
alpar@1949	384
klao@1951	385	/// The value of \c e is set to be true in the edge-map which stores
klao@1951	386	/// hide information. If \c e was hidden previuosly, then it is shown
klao@1951	387	/// again
deba@1681	388	void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
deba@1681	389
klao@1951	390	/// Returns true if \c n is hidden.
alpar@1949	391
klao@1951	392	///\e
klao@1951	393	///
deba@1681	394	bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
deba@1681	395
klao@1951	396	/// Returns true if \c n is hidden.
alpar@1949	397
klao@1951	398	///\e
klao@1951	399	///
deba@1681	400	bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
deba@1681	401
deba@1697	402	typedef False NodeNumTag;
deba@1697	403	typedef False EdgeNumTag;
deba@1991	404
deba@1991	405	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1991	406	Edge findEdge(const Node& source, const Node& target,
deba@1991	407	const Edge& prev = INVALID) {
deba@1991	408	if (!(node_filter_map)[source] \|\| !(node_filter_map)[target]) {
deba@1991	409	return INVALID;
deba@1991	410	}
deba@1991	411	Edge edge = Parent::findEdge(source, target, prev);
deba@1991	412	while (edge != INVALID && !(*edge_filter_map)[edge]) {
deba@1991	413	edge = Parent::findEdge(source, target, edge);
deba@1991	414	}
deba@1991	415	return edge;
deba@1991	416	}
deba@2031	417
deba@2031	418	template <typename _Value>
deba@2031	419	class NodeMap
deba@2031	420	: public SubMapExtender<Adaptor,
deba@2031	421	typename Parent::template NodeMap<_Value> >
deba@2031	422	{
deba@2031	423	public:
deba@2031	424	typedef Adaptor Graph;
deba@2031	425	typedef SubMapExtender<Adaptor, typename Parent::
deba@2031	426	template NodeMap<_Value> > Parent;
deba@2031	427
deba@2031	428	NodeMap(const Graph& graph)
deba@2031	429	: Parent(graph) {}
deba@2031	430	NodeMap(const Graph& graph, const _Value& value)
deba@2031	431	: Parent(graph, value) {}
deba@2031	432
deba@2031	433	NodeMap& operator=(const NodeMap& cmap) {
deba@2031	434	return operator=<NodeMap>(cmap);
deba@2031	435	}
deba@2031	436
deba@2031	437	template <typename CMap>
deba@2031	438	NodeMap& operator=(const CMap& cmap) {
deba@2031	439	Parent::operator=(cmap);
deba@2031	440	return *this;
deba@2031	441	}
deba@2031	442	};
deba@2031	443
deba@2031	444	template <typename _Value>
deba@2031	445	class EdgeMap
deba@2031	446	: public SubMapExtender<Adaptor,
deba@2031	447	typename Parent::template EdgeMap<_Value> >
deba@2031	448	{
deba@2031	449	public:
deba@2031	450	typedef Adaptor Graph;
deba@2031	451	typedef SubMapExtender<Adaptor, typename Parent::
deba@2031	452	template EdgeMap<_Value> > Parent;
deba@2031	453
deba@2031	454	EdgeMap(const Graph& graph)
deba@2031	455	: Parent(graph) {}
deba@2031	456	EdgeMap(const Graph& graph, const _Value& value)
deba@2031	457	: Parent(graph, value) {}
deba@2031	458
deba@2031	459	EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031	460	return operator=<EdgeMap>(cmap);
deba@2031	461	}
deba@2031	462
deba@2031	463	template <typename CMap>
deba@2031	464	EdgeMap& operator=(const CMap& cmap) {
deba@2031	465	Parent::operator=(cmap);
deba@2031	466	return *this;
deba@2031	467	}
deba@2031	468	};
deba@2031	469
deba@1681	470	};
deba@1681	471
deba@1681	472	template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1681	473	class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
deba@1681	474	: public GraphAdaptorBase<_Graph> {
deba@1681	475	public:
deba@1681	476	typedef _Graph Graph;
deba@2031	477	typedef SubGraphAdaptorBase Adaptor;
deba@1681	478	typedef GraphAdaptorBase<_Graph> Parent;
deba@1681	479	protected:
deba@1681	480	NodeFilterMap* node_filter_map;
deba@1681	481	EdgeFilterMap* edge_filter_map;
deba@1681	482	SubGraphAdaptorBase() : Parent(),
deba@1681	483	node_filter_map(0), edge_filter_map(0) { }
deba@1681	484
deba@1681	485	void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
deba@1681	486	node_filter_map=&_node_filter_map;
deba@1681	487	}
deba@1681	488	void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
deba@1681	489	edge_filter_map=&_edge_filter_map;
deba@1681	490	}
deba@1681	491
deba@1681	492	public:
deba@1681	493
deba@1681	494	typedef typename Parent::Node Node;
deba@1681	495	typedef typename Parent::Edge Edge;
deba@1681	496
deba@1681	497	void first(Node& i) const {
deba@1681	498	Parent::first(i);
deba@1681	499	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
deba@1681	500	}
deba@1681	501
marci@992	502	void first(Edge& i) const {
marci@992	503	Parent::first(i);
marci@992	504	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
marci@992	505	}
deba@1681	506
marci@992	507	void firstIn(Edge& i, const Node& n) const {
marci@992	508	Parent::firstIn(i, n);
marci@992	509	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
marci@992	510	}
deba@1681	511
marci@992	512	void firstOut(Edge& i, const Node& n) const {
marci@992	513	Parent::firstOut(i, n);
marci@992	514	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
marci@992	515	}
marci@992	516
marci@992	517	void next(Node& i) const {
marci@992	518	Parent::next(i);
marci@992	519	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
marci@992	520	}
marci@992	521	void next(Edge& i) const {
marci@992	522	Parent::next(i);
marci@992	523	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
marci@992	524	}
marci@992	525	void nextIn(Edge& i) const {
marci@992	526	Parent::nextIn(i);
marci@992	527	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
marci@992	528	}
deba@1681	529
marci@992	530	void nextOut(Edge& i) const {
marci@992	531	Parent::nextOut(i);
marci@992	532	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
marci@992	533	}
marci@992	534
klao@1951	535	///\e
alpar@1949	536
klao@1951	537	/// This function hides \c n in the graph, i.e. the iteration
klao@1951	538	/// jumps over it. This is done by simply setting the value of \c n
klao@1951	539	/// to be false in the corresponding node-map.
marci@992	540	void hide(const Node& n) const { node_filter_map->set(n, false); }
marci@992	541
klao@1951	542	///\e
alpar@1949	543
klao@1951	544	/// This function hides \c e in the graph, i.e. the iteration
klao@1951	545	/// jumps over it. This is done by simply setting the value of \c e
klao@1951	546	/// to be false in the corresponding edge-map.
marci@992	547	void hide(const Edge& e) const { edge_filter_map->set(e, false); }
marci@992	548
klao@1951	549	///\e
alpar@1949	550
klao@1951	551	/// The value of \c n is set to be true in the node-map which stores
klao@1951	552	/// hide information. If \c n was hidden previuosly, then it is shown
klao@1951	553	/// again
marci@992	554	void unHide(const Node& n) const { node_filter_map->set(n, true); }
marci@992	555
klao@1951	556	///\e
alpar@1949	557
klao@1951	558	/// The value of \c e is set to be true in the edge-map which stores
klao@1951	559	/// hide information. If \c e was hidden previuosly, then it is shown
klao@1951	560	/// again
marci@992	561	void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
marci@992	562
klao@1951	563	/// Returns true if \c n is hidden.
alpar@1949	564
klao@1951	565	///\e
klao@1951	566	///
marci@992	567	bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
marci@992	568
klao@1951	569	/// Returns true if \c n is hidden.
alpar@1949	570
klao@1951	571	///\e
klao@1951	572	///
marci@992	573	bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
marci@992	574
deba@1697	575	typedef False NodeNumTag;
deba@1697	576	typedef False EdgeNumTag;
deba@1991	577
deba@1991	578	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1991	579	Edge findEdge(const Node& source, const Node& target,
deba@1991	580	const Edge& prev = INVALID) {
deba@1991	581	if (!(node_filter_map)[source] \|\| !(node_filter_map)[target]) {
deba@1991	582	return INVALID;
deba@1991	583	}
deba@1991	584	Edge edge = Parent::findEdge(source, target, prev);
deba@1991	585	while (edge != INVALID && !(*edge_filter_map)[edge]) {
deba@1991	586	edge = Parent::findEdge(source, target, edge);
deba@1991	587	}
deba@1991	588	return edge;
deba@1991	589	}
deba@2031	590
deba@2031	591	template <typename _Value>
deba@2031	592	class NodeMap
deba@2031	593	: public SubMapExtender<Adaptor,
deba@2031	594	typename Parent::template NodeMap<_Value> >
deba@2031	595	{
deba@2031	596	public:
deba@2031	597	typedef Adaptor Graph;
deba@2031	598	typedef SubMapExtender<Adaptor, typename Parent::
deba@2031	599	template NodeMap<_Value> > Parent;
deba@2031	600
deba@2031	601	NodeMap(const Graph& graph)
deba@2031	602	: Parent(graph) {}
deba@2031	603	NodeMap(const Graph& graph, const _Value& value)
deba@2031	604	: Parent(graph, value) {}
deba@2031	605
deba@2031	606	NodeMap& operator=(const NodeMap& cmap) {
deba@2031	607	return operator=<NodeMap>(cmap);
deba@2031	608	}
deba@2031	609
deba@2031	610	template <typename CMap>
deba@2031	611	NodeMap& operator=(const CMap& cmap) {
deba@2031	612	Parent::operator=(cmap);
deba@2031	613	return *this;
deba@2031	614	}
deba@2031	615	};
deba@2031	616
deba@2031	617	template <typename _Value>
deba@2031	618	class EdgeMap
deba@2031	619	: public SubMapExtender<Adaptor,
deba@2031	620	typename Parent::template EdgeMap<_Value> >
deba@2031	621	{
deba@2031	622	public:
deba@2031	623	typedef Adaptor Graph;
deba@2031	624	typedef SubMapExtender<Adaptor, typename Parent::
deba@2031	625	template EdgeMap<_Value> > Parent;
deba@2031	626
deba@2031	627	EdgeMap(const Graph& graph)
deba@2031	628	: Parent(graph) {}
deba@2031	629	EdgeMap(const Graph& graph, const _Value& value)
deba@2031	630	: Parent(graph, value) {}
deba@2031	631
deba@2031	632	EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031	633	return operator=<EdgeMap>(cmap);
deba@2031	634	}
deba@2031	635
deba@2031	636	template <typename CMap>
deba@2031	637	EdgeMap& operator=(const CMap& cmap) {
deba@2031	638	Parent::operator=(cmap);
deba@2031	639	return *this;
deba@2031	640	}
deba@2031	641	};
deba@2031	642
marci@992	643	};
marci@775	644
deba@2081	645	/// \ingroup graph_adaptors
deba@2081	646	///
klao@1951	647	/// \brief A graph adaptor for hiding nodes and edges from a graph.
klao@1951	648	///
klao@1951	649	/// SubGraphAdaptor shows the graph with filtered node-set and
klao@1951	650	/// edge-set. If the \c checked parameter is true then it filters the edgeset
klao@1951	651	/// to do not get invalid edges without source or target.
klao@1952	652	/// Let \f$ G=(V, A) \f$ be a directed graph
klao@1951	653	/// and suppose that the graph instance \c g of type ListGraph
klao@1952	654	/// implements \f$ G \f$.
klao@1952	655	/// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
klao@1951	656	/// on the node-set and edge-set.
klao@1951	657	/// SubGraphAdaptor<...>::NodeIt iterates
klao@1952	658	/// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
klao@1951	659	/// SubGraphAdaptor<...>::EdgeIt iterates
klao@1952	660	/// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
klao@1951	661	/// SubGraphAdaptor<...>::OutEdgeIt and
klao@1951	662	/// SubGraphAdaptor<...>::InEdgeIt iterates
klao@1951	663	/// only on edges leaving and entering a specific node which have true value.
klao@1951	664	///
klao@1951	665	/// If the \c checked template parameter is false then we have to note that
klao@1951	666	/// the node-iterator cares only the filter on the node-set, and the
klao@1951	667	/// edge-iterator cares only the filter on the edge-set.
klao@1951	668	/// This way the edge-map
klao@1951	669	/// should filter all edges which's source or target is filtered by the
klao@1951	670	/// node-filter.
alpar@1957	671	///\code
klao@1951	672	/// typedef ListGraph Graph;
klao@1951	673	/// Graph g;
klao@1951	674	/// typedef Graph::Node Node;
klao@1951	675	/// typedef Graph::Edge Edge;
klao@1951	676	/// Node u=g.addNode(); //node of id 0
klao@1951	677	/// Node v=g.addNode(); //node of id 1
klao@1951	678	/// Node e=g.addEdge(u, v); //edge of id 0
klao@1951	679	/// Node f=g.addEdge(v, u); //edge of id 1
klao@1951	680	/// Graph::NodeMap<bool> nm(g, true);
klao@1951	681	/// nm.set(u, false);
klao@1951	682	/// Graph::EdgeMap<bool> em(g, true);
klao@1951	683	/// em.set(e, false);
deba@1991	684	/// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
deba@1991	685	/// SubGA ga(g, nm, em);
deba@1991	686	/// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
klao@1951	687	/// std::cout << ":-)" << std::endl;
deba@1991	688	/// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
alpar@1957	689	///\endcode
klao@1951	690	/// The output of the above code is the following.
alpar@1957	691	///\code
klao@1951	692	/// 1
klao@1951	693	/// :-)
klao@1951	694	/// 1
alpar@1957	695	///\endcode
deba@1991	696	/// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
klao@1951	697	/// \c Graph::Node that is why \c g.id(n) can be applied.
klao@1951	698	///
klao@1951	699	/// For other examples see also the documentation of NodeSubGraphAdaptor and
klao@1951	700	/// EdgeSubGraphAdaptor.
klao@1951	701	///
klao@1951	702	/// \author Marton Makai
marci@1242	703
marci@992	704	template<typename _Graph, typename NodeFilterMap,
deba@1681	705	typename EdgeFilterMap, bool checked = true>
alpar@1401	706	class SubGraphAdaptor :
deba@1979	707	public GraphAdaptorExtender<
deba@1681	708	SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
marci@650	709	public:
marci@992	710	typedef _Graph Graph;
deba@2031	711	typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
deba@2031	712	EdgeFilterMap, checked> >
deba@2031	713	Parent;
deba@2031	714
marci@556	715	protected:
alpar@1401	716	SubGraphAdaptor() { }
marci@992	717	public:
deba@2031	718
alpar@1401	719	SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
marci@992	720	EdgeFilterMap& _edge_filter_map) {
marci@992	721	setGraph(_graph);
marci@992	722	setNodeFilterMap(_node_filter_map);
marci@992	723	setEdgeFilterMap(_edge_filter_map);
marci@992	724	}
deba@2031	725
marci@992	726	};
marci@556	727
deba@1991	728	/// \brief Just gives back a sub graph adaptor
deba@1991	729	///
deba@1991	730	/// Just gives back a sub graph adaptor
deba@1991	731	template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991	732	SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
deba@1991	733	subGraphAdaptor(const Graph& graph,
deba@1991	734	NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991	735	return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
deba@1991	736	(graph, nfm, efm);
deba@1991	737	}
deba@1991	738
deba@1991	739	template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991	740	SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
deba@1991	741	subGraphAdaptor(const Graph& graph,
deba@1991	742	NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991	743	return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
deba@1991	744	(graph, nfm, efm);
deba@1991	745	}
deba@1991	746
deba@1991	747	template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991	748	SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
deba@1991	749	subGraphAdaptor(const Graph& graph,
deba@1991	750	NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991	751	return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
deba@1991	752	(graph, nfm, efm);
deba@1991	753	}
deba@1991	754
deba@1991	755	template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991	756	SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
deba@1991	757	subGraphAdaptor(const Graph& graph,
deba@1991	758	NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991	759	return SubGraphAdaptor<const Graph, const NodeFilterMap,
deba@1991	760	const EdgeFilterMap>(graph, nfm, efm);
deba@1991	761	}
deba@1991	762
marci@556	763
marci@569	764
deba@2081	765	///\ingroup graph_adaptors
deba@2081	766	///
klao@1951	767	///\brief An adaptor for hiding nodes from a graph.
klao@1951	768	///
klao@1951	769	///An adaptor for hiding nodes from a graph.
klao@1951	770	///This adaptor specializes SubGraphAdaptor in the way that only
klao@1951	771	///the node-set
klao@1951	772	///can be filtered. In usual case the checked parameter is true, we get the
klao@1951	773	///induced subgraph. But if the checked parameter is false then we can only
klao@1951	774	///filter only isolated nodes.
klao@1951	775	///\author Marton Makai
deba@1681	776	template<typename Graph, typename NodeFilterMap, bool checked = true>
alpar@1401	777	class NodeSubGraphAdaptor :
alpar@1401	778	public SubGraphAdaptor<Graph, NodeFilterMap,
deba@1681	779	ConstMap<typename Graph::Edge,bool>, checked> {
marci@933	780	public:
deba@2031	781
alpar@1401	782	typedef SubGraphAdaptor<Graph, NodeFilterMap,
deba@2031	783	ConstMap<typename Graph::Edge,bool>, checked >
deba@2031	784	Parent;
deba@2031	785
marci@933	786	protected:
marci@933	787	ConstMap<typename Graph::Edge, bool> const_true_map;
deba@1991	788
deba@1991	789	NodeSubGraphAdaptor() : const_true_map(true) {
deba@1991	790	Parent::setEdgeFilterMap(const_true_map);
deba@1991	791	}
deba@1991	792
marci@933	793	public:
deba@2031	794
alpar@1401	795	NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
marci@933	796	Parent(), const_true_map(true) {
marci@933	797	Parent::setGraph(_graph);
marci@933	798	Parent::setNodeFilterMap(_node_filter_map);
marci@933	799	Parent::setEdgeFilterMap(const_true_map);
marci@933	800	}
deba@2031	801
marci@933	802	};
marci@933	803
marci@933	804
deba@1991	805	/// \brief Just gives back a node sub graph adaptor
deba@1991	806	///
deba@1991	807	/// Just gives back a node sub graph adaptor
deba@1991	808	template<typename Graph, typename NodeFilterMap>
deba@1991	809	NodeSubGraphAdaptor<const Graph, NodeFilterMap>
deba@1991	810	nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
deba@1991	811	return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
deba@1991	812	}
deba@1991	813
deba@1991	814	template<typename Graph, typename NodeFilterMap>
deba@1991	815	NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
deba@1991	816	nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
deba@1991	817	return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
deba@1991	818	}
deba@1991	819
deba@2081	820	///\ingroup graph_adaptors
deba@2081	821	///
klao@1951	822	///\brief An adaptor for hiding edges from a graph.
klao@1951	823	///
klao@1951	824	///An adaptor for hiding edges from a graph.
klao@1951	825	///This adaptor specializes SubGraphAdaptor in the way that
klao@1951	826	///only the edge-set
klao@1951	827	///can be filtered. The usefulness of this adaptor is demonstrated in the
klao@1951	828	///problem of searching a maximum number of edge-disjoint shortest paths
klao@1951	829	///between
klao@1951	830	///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
klao@1951	831	///non-negative edge-lengths. Note that
klao@1951	832	///the comprehension of the presented solution
klao@1951	833	///need's some elementary knowledge from combinatorial optimization.
klao@1951	834	///
klao@1951	835	///If a single shortest path is to be
klao@1951	836	///searched between \c s and \c t, then this can be done easily by
klao@1951	837	///applying the Dijkstra algorithm. What happens, if a maximum number of
klao@1951	838	///edge-disjoint shortest paths is to be computed. It can be proved that an
klao@1951	839	///edge can be in a shortest path if and only
klao@1951	840	///if it is tight with respect to
klao@1951	841	///the potential function computed by Dijkstra.
klao@1951	842	///Moreover, any path containing
klao@1951	843	///only such edges is a shortest one.
klao@1951	844	///Thus we have to compute a maximum number
klao@1951	845	///of edge-disjoint paths between \c s and \c t in
klao@1951	846	///the graph which has edge-set
klao@1951	847	///all the tight edges. The computation will be demonstrated
klao@1951	848	///on the following
klao@1951	849	///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
klao@1951	850	///The full source code is available in \ref sub_graph_adaptor_demo.cc.
klao@1951	851	///If you are interested in more demo programs, you can use
klao@1951	852	///\ref dim_to_dot.cc to generate .dot files from dimacs files.
klao@1951	853	///The .dot file of the following figure was generated by
klao@1951	854	///the demo program \ref dim_to_dot.cc.
klao@1951	855	///
klao@1951	856	///\dot
klao@1951	857	///digraph lemon_dot_example {
klao@1951	858	///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
klao@1951	859	///n0 [ label="0 (s)" ];
klao@1951	860	///n1 [ label="1" ];
klao@1951	861	///n2 [ label="2" ];
klao@1951	862	///n3 [ label="3" ];
klao@1951	863	///n4 [ label="4" ];
klao@1951	864	///n5 [ label="5" ];
klao@1951	865	///n6 [ label="6 (t)" ];
klao@1951	866	///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
klao@1951	867	///n5 -> n6 [ label="9, length:4" ];
klao@1951	868	///n4 -> n6 [ label="8, length:2" ];
klao@1951	869	///n3 -> n5 [ label="7, length:1" ];
klao@1951	870	///n2 -> n5 [ label="6, length:3" ];
klao@1951	871	///n2 -> n6 [ label="5, length:5" ];
klao@1951	872	///n2 -> n4 [ label="4, length:2" ];
klao@1951	873	///n1 -> n4 [ label="3, length:3" ];
klao@1951	874	///n0 -> n3 [ label="2, length:1" ];
klao@1951	875	///n0 -> n2 [ label="1, length:2" ];
klao@1951	876	///n0 -> n1 [ label="0, length:3" ];
klao@1951	877	///}
klao@1951	878	///\enddot
klao@1951	879	///
klao@1951	880	///\code
klao@1951	881	///Graph g;
klao@1951	882	///Node s, t;
klao@1951	883	///LengthMap length(g);
klao@1951	884	///
klao@1951	885	///readDimacs(std::cin, g, length, s, t);
klao@1951	886	///
klao@1951	887	///cout << "edges with lengths (of form id, source--length->target): " << endl;
klao@1951	888	///for(EdgeIt e(g); e!=INVALID; ++e)
klao@1951	889	/// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
klao@1951	890	/// << length[e] << "->" << g.id(g.target(e)) << endl;
klao@1951	891	///
klao@1951	892	///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
klao@1951	893	///\endcode
klao@1951	894	///Next, the potential function is computed with Dijkstra.
klao@1951	895	///\code
klao@1951	896	///typedef Dijkstra<Graph, LengthMap> Dijkstra;
klao@1951	897	///Dijkstra dijkstra(g, length);
klao@1951	898	///dijkstra.run(s);
klao@1951	899	///\endcode
klao@1951	900	///Next, we consrtruct a map which filters the edge-set to the tight edges.
klao@1951	901	///\code
klao@1951	902	///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
klao@1951	903	/// TightEdgeFilter;
klao@1951	904	///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
klao@1951	905	///
deba@1991	906	///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
deba@1991	907	///SubGA ga(g, tight_edge_filter);
klao@1951	908	///\endcode
klao@1951	909	///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
klao@1951	910	///with a max flow algorithm Preflow.
klao@1951	911	///\code
klao@1951	912	///ConstMap<Edge, int> const_1_map(1);
klao@1951	913	///Graph::EdgeMap<int> flow(g, 0);
klao@1951	914	///
deba@1991	915	///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
deba@1991	916	/// preflow(ga, s, t, const_1_map, flow);
klao@1951	917	///preflow.run();
klao@1951	918	///\endcode
klao@1951	919	///Last, the output is:
klao@1951	920	///\code
klao@1951	921	///cout << "maximum number of edge-disjoint shortest path: "
klao@1951	922	/// << preflow.flowValue() << endl;
klao@1951	923	///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
klao@1951	924	/// << endl;
klao@1951	925	///for(EdgeIt e(g); e!=INVALID; ++e)
klao@1951	926	/// if (flow[e])
klao@1951	927	/// cout << " " << g.id(g.source(e)) << "--"
klao@1951	928	/// << length[e] << "->" << g.id(g.target(e)) << endl;
klao@1951	929	///\endcode
klao@1951	930	///The program has the following (expected :-)) output:
klao@1951	931	///\code
klao@1951	932	///edges with lengths (of form id, source--length->target):
klao@1951	933	/// 9, 5--4->6
klao@1951	934	/// 8, 4--2->6
klao@1951	935	/// 7, 3--1->5
klao@1951	936	/// 6, 2--3->5
klao@1951	937	/// 5, 2--5->6
klao@1951	938	/// 4, 2--2->4
klao@1951	939	/// 3, 1--3->4
klao@1951	940	/// 2, 0--1->3
klao@1951	941	/// 1, 0--2->2
klao@1951	942	/// 0, 0--3->1
klao@1951	943	///s: 0 t: 6
klao@1951	944	///maximum number of edge-disjoint shortest path: 2
klao@1951	945	///edges of the maximum number of edge-disjoint shortest s-t paths:
klao@1951	946	/// 9, 5--4->6
klao@1951	947	/// 8, 4--2->6
klao@1951	948	/// 7, 3--1->5
klao@1951	949	/// 4, 2--2->4
klao@1951	950	/// 2, 0--1->3
klao@1951	951	/// 1, 0--2->2
klao@1951	952	///\endcode
klao@1951	953	///
klao@1951	954	///\author Marton Makai
marci@932	955	template<typename Graph, typename EdgeFilterMap>
alpar@1401	956	class EdgeSubGraphAdaptor :
alpar@1401	957	public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
deba@1681	958	EdgeFilterMap, false> {
marci@932	959	public:
alpar@1401	960	typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
deba@1685	961	EdgeFilterMap, false> Parent;
marci@932	962	protected:
marci@932	963	ConstMap<typename Graph::Node, bool> const_true_map;
deba@1991	964
deba@1991	965	EdgeSubGraphAdaptor() : const_true_map(true) {
deba@1991	966	Parent::setNodeFilterMap(const_true_map);
deba@1991	967	}
deba@1991	968
marci@932	969	public:
deba@2031	970
alpar@1401	971	EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
marci@932	972	Parent(), const_true_map(true) {
marci@932	973	Parent::setGraph(_graph);
marci@932	974	Parent::setNodeFilterMap(const_true_map);
marci@932	975	Parent::setEdgeFilterMap(_edge_filter_map);
marci@932	976	}
deba@2031	977
marci@932	978	};
marci@932	979
deba@1991	980	/// \brief Just gives back an edge sub graph adaptor
deba@1991	981	///
deba@1991	982	/// Just gives back an edge sub graph adaptor
deba@1991	983	template<typename Graph, typename EdgeFilterMap>
deba@1991	984	EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
deba@1991	985	edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
deba@1991	986	return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
deba@1991	987	}
deba@1991	988
deba@1991	989	template<typename Graph, typename EdgeFilterMap>
deba@1991	990	EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
deba@1991	991	edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
deba@1991	992	return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
deba@1991	993	}
deba@1991	994
deba@2079	995	template <typename _Graph>
deba@1980	996	class UndirGraphAdaptorBase :
deba@2079	997	public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
marci@1383	998	public:
marci@1383	999	typedef _Graph Graph;
deba@2031	1000	typedef UndirGraphAdaptorBase Adaptor;
deba@2079	1001	typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
deba@1991	1002
marci@1383	1003	protected:
deba@1991	1004
deba@1991	1005	UndirGraphAdaptorBase() : Parent() {}
deba@1991	1006
marci@1383	1007	public:
deba@1991	1008
klao@1909	1009	typedef typename Parent::UEdge UEdge;
marci@1383	1010	typedef typename Parent::Edge Edge;
deba@1991	1011
deba@2031	1012	private:
marci@1383	1013
deba@1991	1014	template <typename _Value>
deba@2031	1015	class EdgeMapBase {
deba@1991	1016	private:
deba@1991	1017
deba@1991	1018	typedef typename _Graph::template EdgeMap<_Value> MapImpl;
deba@1991	1019
marci@1383	1020	public:
deba@1991	1021
deba@1991	1022	typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
deba@1991	1023
deba@1991	1024	typedef _Value Value;
marci@1383	1025	typedef Edge Key;
marci@1383	1026
deba@2031	1027	EdgeMapBase(const Adaptor& adaptor) :
deba@2031	1028	forward_map(adaptor.graph), backward_map(adaptor.graph) {}
marci@569	1029
deba@2031	1030	EdgeMapBase(const Adaptor& adaptor, const Value& v)
deba@2031	1031	: forward_map(adaptor.graph, v), backward_map(adaptor.graph, v) {}
marci@1383	1032
deba@1991	1033	void set(const Edge& e, const Value& a) {
deba@1991	1034	if (Parent::direction(e)) {
marci@1383	1035	forward_map.set(e, a);
deba@1991	1036	} else {
deba@1991	1037	backward_map.set(e, a);
deba@1991	1038	}
marci@1383	1039	}
marci@556	1040
deba@1991	1041	typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
deba@1991	1042	if (Parent::direction(e)) {
marci@1383	1043	return forward_map[e];
deba@1991	1044	} else {
marci@1383	1045	return backward_map[e];
deba@1991	1046	}
marci@556	1047	}
deba@1991	1048
deba@1991	1049	typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
deba@1991	1050	if (Parent::direction(e)) {
deba@1991	1051	return forward_map[e];
deba@1991	1052	} else {
deba@1991	1053	return backward_map[e];
deba@1991	1054	}
deba@1991	1055	}
deba@1991	1056
deba@1991	1057	protected:
deba@1991	1058
deba@1991	1059	MapImpl forward_map, backward_map;
deba@1991	1060
marci@556	1061	};
deba@2031	1062
deba@2031	1063	public:
deba@2031	1064
deba@2031	1065	template <typename _Value>
deba@2031	1066	class EdgeMap
deba@2031	1067	: public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
deba@2031	1068	{
deba@2031	1069	public:
deba@2031	1070	typedef Adaptor Graph;
deba@2031	1071	typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
deba@2031	1072
deba@2031	1073	EdgeMap(const Graph& graph)
deba@2031	1074	: Parent(graph) {}
deba@2031	1075	EdgeMap(const Graph& graph, const _Value& value)
deba@2031	1076	: Parent(graph, value) {}
deba@2031	1077
deba@2031	1078	EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031	1079	return operator=<EdgeMap>(cmap);
deba@2031	1080	}
deba@2031	1081
deba@2031	1082	template <typename CMap>
deba@2031	1083	EdgeMap& operator=(const CMap& cmap) {
deba@2031	1084	Parent::operator=(cmap);
deba@2031	1085	return *this;
deba@2031	1086	}
deba@2031	1087	};
marci@1383	1088
deba@1991	1089	template <typename _Value>
deba@2031	1090	class UEdgeMap : public Graph::template EdgeMap<_Value> {
marci@1383	1091	public:
deba@2031	1092
deba@2031	1093	typedef typename Graph::template EdgeMap<_Value> Parent;
deba@2031	1094
deba@2031	1095	explicit UEdgeMap(const Adaptor& ga)
deba@2031	1096	: Parent(*ga.graph) {}
deba@1991	1097
deba@2031	1098	UEdgeMap(const Adaptor& ga, const _Value& value)
deba@2031	1099	: Parent(*ga.graph, value) {}
deba@1991	1100
deba@2031	1101	UEdgeMap& operator=(const UEdgeMap& cmap) {
deba@2031	1102	return operator=<UEdgeMap>(cmap);
deba@2031	1103	}
deba@1991	1104
deba@2031	1105	template <typename CMap>
deba@2031	1106	UEdgeMap& operator=(const CMap& cmap) {
deba@2031	1107	Parent::operator=(cmap);
deba@2031	1108	return *this;
deba@2031	1109	}
deba@2031	1110
deba@1991	1111	};
deba@1991	1112
deba@1991	1113	};
marci@556	1114
deba@2079	1115	template <typename _Graph, typename Enable = void>
deba@2079	1116	class AlterableUndirGraphAdaptor
deba@2079	1117	: public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
deba@2079	1118	public:
deba@2079	1119	typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
deba@2079	1120
deba@2079	1121	protected:
deba@2079	1122
deba@2079	1123	AlterableUndirGraphAdaptor() : Parent() {}
deba@2079	1124
deba@1991	1125	public:
deba@1991	1126
deba@2079	1127	typedef typename Parent::EdgeNotifier UEdgeNotifier;
deba@2079	1128	typedef InvalidType EdgeNotifier;
deba@2079	1129
deba@2079	1130	};
deba@2079	1131
deba@2079	1132	template <typename _Graph>
deba@2079	1133	class AlterableUndirGraphAdaptor<
deba@2079	1134	_Graph,
deba@2079	1135	typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type >
deba@2079	1136	: public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
deba@2079	1137	public:
deba@2079	1138
deba@2079	1139	typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
deba@1991	1140	typedef _Graph Graph;
deba@2079	1141	typedef typename _Graph::Edge GraphEdge;
deba@2079	1142
deba@1991	1143	protected:
deba@1991	1144
deba@2079	1145	AlterableUndirGraphAdaptor()
deba@2079	1146	: Parent(), edge_notifier(this), edge_notifier_proxy(this) {}
deba@1991	1147
deba@1991	1148	void setGraph(_Graph& graph) {
deba@1991	1149	Parent::setGraph(graph);
deba@2079	1150	edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
deba@1991	1151	}
deba@1991	1152
deba@1991	1153	public:
deba@1991	1154
deba@2079	1155	~AlterableUndirGraphAdaptor() {
deba@1999	1156	edge_notifier.clear();
deba@1999	1157	}
deba@1999	1158
deba@1991	1159	typedef typename Parent::UEdge UEdge;
deba@1991	1160	typedef typename Parent::Edge Edge;
deba@1991	1161
deba@1991	1162	typedef typename Parent::EdgeNotifier UEdgeNotifier;
deba@1991	1163
deba@1991	1164	using Parent::getNotifier;
deba@1991	1165
deba@2079	1166	typedef AlterationNotifier<AlterableUndirGraphAdaptor,
deba@2079	1167	Edge> EdgeNotifier;
deba@1991	1168	EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
deba@1991	1169
deba@1991	1170	protected:
deba@1991	1171
deba@2079	1172	class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
deba@1991	1173	public:
deba@1991	1174
deba@2079	1175	typedef typename Graph::EdgeNotifier::ObserverBase Parent;
deba@2079	1176	typedef AlterableUndirGraphAdaptor AdaptorBase;
marci@1383	1177
deba@2079	1178	NotifierProxy(const AdaptorBase& _adaptor)
deba@2079	1179	: Parent(), adaptor(&_adaptor) {
marci@1383	1180	}
marci@556	1181
deba@1991	1182	virtual ~NotifierProxy() {
deba@1991	1183	if (Parent::attached()) {
deba@1991	1184	Parent::detach();
deba@1991	1185	}
marci@1383	1186	}
deba@1991	1187
deba@2079	1188	void setNotifier(typename Graph::EdgeNotifier& notifier) {
deba@2079	1189	Parent::attach(notifier);
deba@1991	1190	}
deba@1991	1191
deba@1991	1192
deba@1991	1193	protected:
deba@1991	1194
deba@2079	1195	virtual void add(const GraphEdge& ge) {
deba@1991	1196	std::vector<Edge> edges;
deba@2079	1197	edges.push_back(AdaptorBase::Parent::direct(ge, true));
deba@2079	1198	edges.push_back(AdaptorBase::Parent::direct(ge, false));
deba@2079	1199	adaptor->getNotifier(Edge()).add(edges);
deba@1991	1200	}
deba@2079	1201	virtual void add(const std::vector<GraphEdge>& ge) {
deba@1991	1202	std::vector<Edge> edges;
deba@2079	1203	for (int i = 0; i < (int)ge.size(); ++i) {
deba@2079	1204	edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
deba@2079	1205	edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
deba@1991	1206	}
deba@2079	1207	adaptor->getNotifier(Edge()).add(edges);
deba@1991	1208	}
deba@2079	1209	virtual void erase(const GraphEdge& ge) {
deba@1991	1210	std::vector<Edge> edges;
deba@2079	1211	edges.push_back(AdaptorBase::Parent::direct(ge, true));
deba@2079	1212	edges.push_back(AdaptorBase::Parent::direct(ge, false));
deba@2079	1213	adaptor->getNotifier(Edge()).erase(edges);
deba@1991	1214	}
deba@2079	1215	virtual void erase(const std::vector<GraphEdge>& ge) {
deba@1991	1216	std::vector<Edge> edges;
deba@2079	1217	for (int i = 0; i < (int)ge.size(); ++i) {
deba@2079	1218	edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
deba@2079	1219	edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
deba@1991	1220	}
deba@2079	1221	adaptor->getNotifier(Edge()).erase(edges);
deba@1991	1222	}
deba@1991	1223	virtual void build() {
deba@2079	1224	adaptor->getNotifier(Edge()).build();
deba@1991	1225	}
deba@1991	1226	virtual void clear() {
deba@2079	1227	adaptor->getNotifier(Edge()).clear();
deba@1991	1228	}
deba@1991	1229
deba@2079	1230	const AdaptorBase* adaptor;
deba@1991	1231	};
deba@1991	1232
deba@1991	1233
deba@1991	1234	mutable EdgeNotifier edge_notifier;
deba@1991	1235	NotifierProxy edge_notifier_proxy;
deba@1991	1236
marci@1383	1237	};
marci@1383	1238
deba@2079	1239
deba@2081	1240	///\ingroup graph_adaptors
deba@2081	1241	///
deba@2079	1242	/// \brief An undirected graph is made from a directed graph by an adaptor
klao@1951	1243	///
klao@1951	1244	/// Undocumented, untested!!!
klao@1951	1245	/// If somebody knows nice demo application, let's polulate it.
klao@1951	1246	///
klao@1951	1247	/// \author Marton Makai
marci@1383	1248	template<typename _Graph>
deba@2079	1249	class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
marci@1383	1250	public:
marci@1383	1251	typedef _Graph Graph;
deba@2079	1252	typedef AlterableUndirGraphAdaptor<_Graph> Parent;
marci@1383	1253	protected:
deba@1980	1254	UndirGraphAdaptor() { }
marci@1383	1255	public:
deba@1980	1256	UndirGraphAdaptor(_Graph& _graph) {
marci@1383	1257	setGraph(_graph);
marci@556	1258	}
marci@556	1259
deba@1991	1260	template <typename _ForwardMap, typename _BackwardMap>
deba@1991	1261	class CombinedEdgeMap {
deba@1991	1262	public:
deba@1991	1263
deba@1991	1264	typedef _ForwardMap ForwardMap;
deba@1991	1265	typedef _BackwardMap BackwardMap;
marci@992	1266
deba@1991	1267	typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
marci@992	1268
deba@1991	1269	typedef typename ForwardMap::Value Value;
deba@1991	1270	typedef typename Parent::Edge Key;
deba@1991	1271
deba@1991	1272	CombinedEdgeMap() : forward_map(0), backward_map(0) {}
marci@992	1273
deba@1991	1274	CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
deba@1991	1275	: forward_map(&_forward_map), backward_map(&_backward_map) {}
marci@992	1276
deba@1991	1277	void set(const Key& e, const Value& a) {
deba@1991	1278	if (Parent::direction(e)) {
deba@1991	1279	forward_map->set(e, a);
deba@1991	1280	} else {
deba@1991	1281	backward_map->set(e, a);
deba@1991	1282	}
marci@992	1283	}
marci@992	1284
deba@1991	1285	typename MapTraits<ForwardMap>::ConstReturnValue
deba@1991	1286	operator[](const Key& e) const {
deba@1991	1287	if (Parent::direction(e)) {
deba@1991	1288	return (*forward_map)[e];
deba@1991	1289	} else {
deba@1991	1290	return (*backward_map)[e];
deba@1991	1291	}
marci@992	1292	}
marci@992	1293
deba@1991	1294	typename MapTraits<ForwardMap>::ReturnValue
deba@1991	1295	operator[](const Key& e) {
deba@1991	1296	if (Parent::direction(e)) {
deba@1991	1297	return (*forward_map)[e];
deba@1991	1298	} else {
deba@1991	1299	return (*backward_map)[e];
deba@1991	1300	}
marci@992	1301	}
deba@1991	1302
deba@1991	1303	void setForwardMap(ForwardMap& _forward_map) {
deba@1991	1304	forward_map = &_forward_map;
deba@1991	1305	}
deba@1991	1306
deba@1991	1307	void setBackwardMap(BackwardMap& _backward_map) {
deba@1991	1308	backward_map = &_backward_map;
deba@1991	1309	}
deba@1991	1310
deba@1991	1311	protected:
deba@1991	1312
deba@1991	1313	ForwardMap* forward_map;
deba@1991	1314	BackwardMap* backward_map;
deba@1991	1315
marci@992	1316	};
marci@992	1317
marci@992	1318	};
marci@569	1319
deba@1991	1320	/// \brief Just gives back an undir graph adaptor
klao@1951	1321	///
deba@1991	1322	/// Just gives back an undir graph adaptor
marci@650	1323	template<typename Graph>
deba@1991	1324	UndirGraphAdaptor<const Graph>
deba@1991	1325	undirGraphAdaptor(const Graph& graph) {
deba@1991	1326	return UndirGraphAdaptor<const Graph>(graph);
deba@1991	1327	}
marci@650	1328
deba@2034	1329	template<typename Graph, typename Number,
deba@2034	1330	typename CapacityMap, typename FlowMap,
deba@2034	1331	typename Tolerance = Tolerance<Number> >
marci@658	1332	class ResForwardFilter {
marci@650	1333	const CapacityMap* capacity;
marci@650	1334	const FlowMap* flow;
deba@2034	1335	Tolerance tolerance;
marci@650	1336	public:
deba@1991	1337	typedef typename Graph::Edge Key;
deba@1991	1338	typedef bool Value;
deba@1991	1339
deba@2034	1340	ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
deba@2034	1341	const Tolerance& _tolerance = Tolerance())
deba@2034	1342	: capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
deba@2034	1343
deba@2034	1344	ResForwardFilter(const Tolerance& _tolerance)
deba@2034	1345	: capacity(0), flow(0), tolerance(_tolerance) { }
deba@2034	1346
deba@1991	1347	void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
deba@1991	1348	void setFlow(const FlowMap& _flow) { flow = &_flow; }
deba@2034	1349
marci@650	1350	bool operator[](const typename Graph::Edge& e) const {
deba@2034	1351	return tolerance.less((flow)[e], (capacity)[e]);
marci@650	1352	}
marci@650	1353	};
marci@650	1354
marci@650	1355	template<typename Graph, typename Number,
deba@2034	1356	typename CapacityMap, typename FlowMap,
deba@2034	1357	typename Tolerance = Tolerance<Number> >
marci@658	1358	class ResBackwardFilter {
marci@650	1359	const CapacityMap* capacity;
marci@650	1360	const FlowMap* flow;
deba@2034	1361	Tolerance tolerance;
marci@650	1362	public:
deba@1991	1363	typedef typename Graph::Edge Key;
deba@1991	1364	typedef bool Value;
deba@1991	1365
deba@2034	1366	ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
deba@2034	1367	const Tolerance& _tolerance = Tolerance())
deba@2034	1368	: capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
deba@2034	1369	ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
deba@2034	1370	: capacity(0), flow(0), tolerance(_tolerance) { }
deba@1991	1371	void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
deba@1991	1372	void setFlow(const FlowMap& _flow) { flow = &_flow; }
marci@650	1373	bool operator[](const typename Graph::Edge& e) const {
deba@2034	1374	return tolerance.less(0, Number((*flow)[e]));
marci@650	1375	}
marci@650	1376	};
marci@650	1377
marci@653	1378
deba@2081	1379	///\ingroup graph_adaptors
deba@2081	1380	///
klao@1951	1381	///\brief An adaptor for composing the residual
klao@1951	1382	///graph for directed flow and circulation problems.
deba@2037	1383	///
deba@2042	1384	///An adaptor for composing the residual graph for directed flow and
deba@2042	1385	///circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
deba@2042	1386	///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
deba@2042	1387	///be functions on the edge-set.
deba@2042	1388	///
deba@2042	1389	///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
deba@2042	1390	///for a flow and \f$ c \f$ for a capacity function. Suppose that a
deba@2042	1391	///graph instange \c g of type \c ListGraph implements \f$ G \f$.
deba@2042	1392	///
deba@2042	1393	///\code
deba@2042	1394	/// ListGraph g;
deba@2042	1395	///\endcode
deba@2042	1396	///
deba@2042	1397	///Then RevGraphAdaptor implements the graph structure with node-set
deba@2042	1398	/// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
deba@2042	1399	///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
deba@2042	1400	/// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
deba@2042	1401	///residual graph. When we take the union
deba@2042	1402	/// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
deba@2042	1403	///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
deba@2042	1404	///then in the adaptor it appears twice. The following code shows how
deba@2042	1405	///such an instance can be constructed.
deba@2042	1406	///
deba@2042	1407	///\code
deba@2042	1408	/// typedef ListGraph Graph;
deba@2042	1409	/// Graph::EdgeMap<int> f(g);
deba@2042	1410	/// Graph::EdgeMap<int> c(g);
deba@2042	1411	/// ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
deba@2042	1412	///\endcode
deba@2042	1413	///\author Marton Makai
deba@2042	1414	///
marci@650	1415	template<typename Graph, typename Number,
deba@2034	1416	typename CapacityMap, typename FlowMap,
deba@2034	1417	typename Tolerance = Tolerance<Number> >
alpar@1401	1418	class ResGraphAdaptor :
deba@1991	1419	public EdgeSubGraphAdaptor<
deba@2034	1420	UndirGraphAdaptor<const Graph>,
deba@2034	1421	typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
deba@2034	1422	ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>,
deba@2034	1423	ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
marci@650	1424	public:
deba@1991	1425
deba@2034	1426	typedef UndirGraphAdaptor<const Graph> UGraph;
deba@1991	1427
deba@2034	1428	typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
deba@1991	1429	ForwardFilter;
deba@1991	1430
deba@2034	1431	typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
deba@1991	1432	BackwardFilter;
deba@1991	1433
deba@1991	1434	typedef typename UGraph::
deba@1991	1435	template CombinedEdgeMap<ForwardFilter, BackwardFilter>
deba@1991	1436	EdgeFilter;
deba@1991	1437
deba@1991	1438	typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
deba@1991	1439
marci@650	1440	protected:
deba@1991	1441
marci@650	1442	const CapacityMap* capacity;
marci@650	1443	FlowMap* flow;
deba@1991	1444
deba@1991	1445	UGraph ugraph;
deba@1991	1446	ForwardFilter forward_filter;
deba@1991	1447	BackwardFilter backward_filter;
deba@1991	1448	EdgeFilter edge_filter;
deba@1991	1449
marci@658	1450	void setCapacityMap(const CapacityMap& _capacity) {
marci@658	1451	capacity=&_capacity;
marci@658	1452	forward_filter.setCapacity(_capacity);
marci@658	1453	backward_filter.setCapacity(_capacity);
marci@658	1454	}
deba@1991	1455
marci@658	1456	void setFlowMap(FlowMap& _flow) {
marci@658	1457	flow=&_flow;
marci@658	1458	forward_filter.setFlow(_flow);
marci@658	1459	backward_filter.setFlow(_flow);
marci@658	1460	}
deba@1991	1461
marci@650	1462	public:
deba@1991	1463
deba@2034	1464	/// \brief Constructor of the residual graph.
deba@2034	1465	///
deba@2034	1466	/// Constructor of the residual graph. The parameters are the graph type,
deba@2034	1467	/// the flow map, the capacity map and a tolerance object.
deba@2034	1468	ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
deba@2034	1469	FlowMap& _flow, const Tolerance& _tolerance = Tolerance())
deba@2034	1470	: Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
deba@2034	1471	forward_filter(_capacity, _flow, _tolerance),
deba@2034	1472	backward_filter(_capacity, _flow, _tolerance),
deba@2034	1473	edge_filter(forward_filter, backward_filter)
deba@2034	1474	{
deba@1991	1475	Parent::setGraph(ugraph);
deba@1991	1476	Parent::setEdgeFilterMap(edge_filter);
marci@650	1477	}
marci@650	1478
marci@660	1479	typedef typename Parent::Edge Edge;
marci@660	1480
deba@2034	1481	/// \brief Gives back the residual capacity of the edge.
deba@2034	1482	///
deba@2034	1483	/// Gives back the residual capacity of the edge.
deba@2034	1484	Number rescap(const Edge& edge) const {
deba@2034	1485	if (UGraph::direction(edge)) {
deba@2034	1486	return (capacity)[edge]-(flow)[edge];
deba@2034	1487	} else {
deba@2034	1488	return (*flow)[edge];
deba@2034	1489	}
deba@2034	1490	}
deba@2034	1491
deba@2034	1492	/// \brief Augment on the given edge in the residual graph.
deba@2034	1493	///
deba@2034	1494	/// Augment on the given edge in the residual graph. It increase
deba@2034	1495	/// or decrease the flow on the original edge depend on the direction
deba@2034	1496	/// of the residual edge.
marci@660	1497	void augment(const Edge& e, Number a) const {
deba@1991	1498	if (UGraph::direction(e)) {
deba@2034	1499	flow->set(e, (*flow)[e] + a);
deba@1991	1500	} else {
deba@2034	1501	flow->set(e, (*flow)[e] - a);
deba@1991	1502	}
marci@650	1503	}
marci@650	1504
deba@2034	1505	/// \brief Returns the direction of the edge.
deba@2034	1506	///
deba@2034	1507	/// Returns true when the edge is same oriented as the original edge.
deba@1991	1508	static bool forward(const Edge& e) {
deba@1991	1509	return UGraph::direction(e);
deba@1991	1510	}
deba@1991	1511
deba@2034	1512	/// \brief Returns the direction of the edge.
deba@2034	1513	///
deba@2034	1514	/// Returns true when the edge is opposite oriented as the original edge.
deba@1991	1515	static bool backward(const Edge& e) {
deba@1991	1516	return !UGraph::direction(e);
deba@1991	1517	}
deba@1991	1518
deba@2034	1519	/// \brief Gives back the forward oriented residual edge.
deba@2034	1520	///
deba@2034	1521	/// Gives back the forward oriented residual edge.
deba@1991	1522	static Edge forward(const typename Graph::Edge& e) {
deba@1991	1523	return UGraph::direct(e, true);
deba@1991	1524	}
deba@1991	1525
deba@2034	1526	/// \brief Gives back the backward oriented residual edge.
deba@2034	1527	///
deba@2034	1528	/// Gives back the backward oriented residual edge.
deba@1991	1529	static Edge backward(const typename Graph::Edge& e) {
deba@1991	1530	return UGraph::direct(e, false);
deba@1991	1531	}
deba@1991	1532
klao@1951	1533	/// \brief Residual capacity map.
klao@1951	1534	///
klao@1951	1535	/// In generic residual graphs the residual capacity can be obtained
klao@1951	1536	/// as a map.
marci@660	1537	class ResCap {
marci@660	1538	protected:
deba@1991	1539	const ResGraphAdaptor* res_graph;
marci@660	1540	public:
alpar@987	1541	typedef Number Value;
alpar@987	1542	typedef Edge Key;
deba@1991	1543	ResCap(const ResGraphAdaptor& _res_graph)
deba@1991	1544	: res_graph(&_res_graph) {}
deba@1991	1545
deba@2034	1546	Number operator[](const Edge& e) const {
deba@2034	1547	return res_graph->rescap(e);
marci@660	1548	}
deba@1991	1549
marci@660	1550	};
marci@660	1551
marci@650	1552	};
marci@650	1553
marci@650	1554
marci@998	1555
marci@998	1556	template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401	1557	class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@998	1558	public:
marci@998	1559	typedef _Graph Graph;
alpar@1401	1560	typedef GraphAdaptorBase<_Graph> Parent;
marci@998	1561	protected:
marci@998	1562	FirstOutEdgesMap* first_out_edges;
alpar@1401	1563	ErasingFirstGraphAdaptorBase() : Parent(),
marci@998	1564	first_out_edges(0) { }
marci@998	1565
marci@998	1566	void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
marci@998	1567	first_out_edges=&_first_out_edges;
marci@998	1568	}
marci@998	1569
marci@998	1570	public:
marci@998	1571
marci@998	1572	typedef typename Parent::Node Node;
marci@998	1573	typedef typename Parent::Edge Edge;
marci@998	1574
marci@998	1575	void firstOut(Edge& i, const Node& n) const {
marci@998	1576	i=(*first_out_edges)[n];
marci@998	1577	}
marci@998	1578
marci@998	1579	void erase(const Edge& e) const {
marci@998	1580	Node n=source(e);
marci@998	1581	Edge f=e;
marci@998	1582	Parent::nextOut(f);
marci@998	1583	first_out_edges->set(n, f);
marci@998	1584	}
marci@998	1585	};
marci@998	1586
marci@998	1587
deba@2081	1588	///\ingroup graph_adaptors
deba@2081	1589	///
klao@1951	1590	///\brief For blocking flows.
klao@1951	1591	///
klao@1951	1592	///This graph adaptor is used for on-the-fly
klao@1951	1593	///Dinits blocking flow computations.
klao@1951	1594	///For each node, an out-edge is stored which is used when the
klao@1951	1595	///\code
klao@1951	1596	///OutEdgeIt& first(OutEdgeIt&, const Node&)
klao@1951	1597	///\endcode
klao@1951	1598	///is called.
klao@1951	1599	///
klao@1951	1600	///\author Marton Makai
klao@1951	1601	///
marci@998	1602	template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401	1603	class ErasingFirstGraphAdaptor :
deba@1979	1604	public GraphAdaptorExtender<
alpar@1401	1605	ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
marci@650	1606	public:
marci@998	1607	typedef _Graph Graph;
deba@1979	1608	typedef GraphAdaptorExtender<
alpar@1401	1609	ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
alpar@1401	1610	ErasingFirstGraphAdaptor(Graph& _graph,
marci@998	1611	FirstOutEdgesMap& _first_out_edges) {
marci@998	1612	setGraph(_graph);
marci@998	1613	setFirstOutEdgesMap(_first_out_edges);
marci@998	1614	}
marci@1019	1615
marci@998	1616	};
marci@556	1617
deba@2079	1618	/// \brief Base class for split graph adaptor
deba@2079	1619	///
deba@2079	1620	/// Base class of split graph adaptor. In most case you do not need to
deba@2079	1621	/// use it directly but the documented member functions of this class can
deba@2079	1622	/// be used with the SplitGraphAdaptor class.
deba@2079	1623	/// \sa SplitGraphAdaptor
deba@2079	1624	template <typename _Graph>
deba@2079	1625	class SplitGraphAdaptorBase
deba@2079	1626	: public GraphAdaptorBase<const _Graph> {
deba@2079	1627	public:
deba@1697	1628
deba@2079	1629	typedef _Graph Graph;
deba@2079	1630
deba@2079	1631	typedef GraphAdaptorBase<const _Graph> Parent;
deba@2079	1632
deba@2079	1633	typedef typename Graph::Node GraphNode;
deba@2079	1634	typedef typename Graph::Edge GraphEdge;
deba@2079	1635
deba@2079	1636	class Node;
deba@2079	1637	class Edge;
deba@2079	1638
deba@2079	1639	template <typename T> class NodeMap;
deba@2079	1640	template <typename T> class EdgeMap;
deba@1697	1641
deba@1697	1642
deba@2079	1643	class Node : public GraphNode {
deba@2079	1644	friend class SplitGraphAdaptorBase;
deba@2079	1645	template <typename T> friend class NodeMap;
deba@2079	1646	private:
deba@1697	1647
deba@2079	1648	bool in_node;
deba@2079	1649	Node(GraphNode _node, bool _in_node)
deba@2079	1650	: GraphNode(_node), in_node(_in_node) {}
deba@1697	1651
deba@2079	1652	public:
deba@1697	1653
deba@2079	1654	Node() {}
deba@2079	1655	Node(Invalid) : GraphNode(INVALID), in_node(true) {}
deba@2079	1656
deba@2079	1657	bool operator==(const Node& node) const {
deba@2079	1658	return GraphNode::operator==(node) && in_node == node.in_node;
deba@2079	1659	}
deba@1697	1660
deba@2079	1661	bool operator!=(const Node& node) const {
deba@2079	1662	return !(*this == node);
deba@2079	1663	}
deba@1697	1664
deba@2079	1665	bool operator<(const Node& node) const {
deba@2079	1666	return GraphNode::operator<(node) \|\|
deba@2079	1667	(GraphNode::operator==(node) && in_node < node.in_node);
deba@2079	1668	}
deba@2079	1669	};
deba@1697	1670
deba@2079	1671	class Edge {
deba@2079	1672	friend class SplitGraphAdaptorBase;
deba@2079	1673	template <typename T> friend class EdgeMap;
deba@2079	1674	private:
deba@2079	1675	typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
deba@1697	1676
deba@2079	1677	explicit Edge(const GraphEdge& edge) : item(edge) {}
deba@2079	1678	explicit Edge(const GraphNode& node) : item(node) {}
deba@2079	1679
deba@2079	1680	EdgeImpl item;
deba@1697	1681
deba@2079	1682	public:
deba@2079	1683	Edge() {}
deba@2079	1684	Edge(Invalid) : item(GraphEdge(INVALID)) {}
deba@2079	1685
deba@2079	1686	bool operator==(const Edge& edge) const {
deba@2079	1687	if (item.firstState()) {
deba@2079	1688	if (edge.item.firstState()) {
deba@2079	1689	return item.first() == edge.item.first();
deba@2079	1690	}
deba@2079	1691	} else {
deba@2079	1692	if (edge.item.secondState()) {
deba@2079	1693	return item.second() == edge.item.second();
deba@2079	1694	}
deba@2079	1695	}
deba@2079	1696	return false;
deba@2079	1697	}
deba@1697	1698
deba@2079	1699	bool operator!=(const Edge& edge) const {
deba@2079	1700	return !(*this == edge);
deba@2079	1701	}
deba@1697	1702
deba@2079	1703	bool operator<(const Edge& edge) const {
deba@2079	1704	if (item.firstState()) {
deba@2079	1705	if (edge.item.firstState()) {
deba@2079	1706	return item.first() < edge.item.first();
deba@2079	1707	}
deba@2079	1708	return false;
deba@2079	1709	} else {
deba@2079	1710	if (edge.item.secondState()) {
deba@2079	1711	return item.second() < edge.item.second();
deba@2079	1712	}
deba@2079	1713	return true;
deba@2079	1714	}
deba@2079	1715	}
deba@1697	1716
deba@2079	1717	operator GraphEdge() const { return item.first(); }
deba@2079	1718	operator GraphNode() const { return item.second(); }
deba@1697	1719
deba@2079	1720	};
deba@1697	1721
deba@2079	1722	void first(Node& node) const {
deba@2079	1723	Parent::first(node);
deba@2079	1724	node.in_node = true;
deba@2079	1725	}
deba@1697	1726
deba@2079	1727	void next(Node& node) const {
deba@2079	1728	if (node.in_node) {
deba@2079	1729	node.in_node = false;
deba@2079	1730	} else {
deba@2079	1731	node.in_node = true;
deba@2079	1732	Parent::next(node);
deba@2079	1733	}
deba@2079	1734	}
deba@1697	1735
deba@2079	1736	void first(Edge& edge) const {
deba@2079	1737	edge.item.setSecond();
deba@2079	1738	Parent::first(edge.item.second());
deba@2079	1739	if (edge.item.second() == INVALID) {
deba@2079	1740	edge.item.setFirst();
deba@2079	1741	Parent::first(edge.item.first());
deba@2079	1742	}
deba@2079	1743	}
deba@1697	1744
deba@2079	1745	void next(Edge& edge) const {
deba@2079	1746	if (edge.item.secondState()) {
deba@2079	1747	Parent::next(edge.item.second());
deba@2079	1748	if (edge.item.second() == INVALID) {
deba@2079	1749	edge.item.setFirst();
deba@2079	1750	Parent::first(edge.item.first());
deba@2079	1751	}
deba@2079	1752	} else {
deba@2079	1753	Parent::next(edge.item.first());
deba@2079	1754	}
deba@2079	1755	}
deba@1697	1756
deba@2079	1757	void firstOut(Edge& edge, const Node& node) const {
deba@2079	1758	if (node.in_node) {
deba@2079	1759	edge.item.setSecond(node);
deba@2079	1760	} else {
deba@2079	1761	edge.item.setFirst();
deba@2079	1762	Parent::firstOut(edge.item.first(), node);
deba@2079	1763	}
deba@2079	1764	}
deba@1697	1765
deba@2079	1766	void nextOut(Edge& edge) const {
deba@2079	1767	if (!edge.item.firstState()) {
deba@2079	1768	edge.item.setFirst(INVALID);
deba@2079	1769	} else {
deba@2079	1770	Parent::nextOut(edge.item.first());
deba@2079	1771	}
deba@2079	1772	}
deba@1697	1773
deba@2079	1774	void firstIn(Edge& edge, const Node& node) const {
deba@2079	1775	if (!node.in_node) {
deba@2079	1776	edge.item.setSecond(node);
deba@2079	1777	} else {
deba@2079	1778	edge.item.setFirst();
deba@2079	1779	Parent::firstIn(edge.item.first(), node);
deba@2079	1780	}
deba@2079	1781	}
deba@1697	1782
deba@2079	1783	void nextIn(Edge& edge) const {
deba@2079	1784	if (!edge.item.firstState()) {
deba@2079	1785	edge.item.setFirst(INVALID);
deba@2079	1786	} else {
deba@2079	1787	Parent::nextIn(edge.item.first());
deba@2079	1788	}
deba@2079	1789	}
deba@1697	1790
deba@2079	1791	Node source(const Edge& edge) const {
deba@2079	1792	if (edge.item.firstState()) {
deba@2079	1793	return Node(Parent::source(edge.item.first()), false);
deba@2079	1794	} else {
deba@2079	1795	return Node(edge.item.second(), true);
deba@2079	1796	}
deba@2079	1797	}
deba@1697	1798
deba@2079	1799	Node target(const Edge& edge) const {
deba@2079	1800	if (edge.item.firstState()) {
deba@2079	1801	return Node(Parent::target(edge.item.first()), true);
deba@2079	1802	} else {
deba@2079	1803	return Node(edge.item.second(), false);
deba@2079	1804	}
deba@2079	1805	}
deba@1697	1806
deba@2079	1807	int id(const Node& node) const {
deba@2079	1808	return (Parent::id(node) << 1) \| (node.in_node ? 0 : 1);
deba@2079	1809	}
deba@2079	1810	Node nodeFromId(int id) const {
deba@2079	1811	return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
deba@2079	1812	}
deba@2079	1813	int maxNodeId() const {
deba@2079	1814	return 2 * Parent::maxNodeId() + 1;
deba@2079	1815	}
deba@1697	1816
deba@2079	1817	int id(const Edge& edge) const {
deba@2079	1818	if (edge.item.firstState()) {
deba@2079	1819	return Parent::id(edge.item.first()) << 1;
deba@2079	1820	} else {
deba@2079	1821	return (Parent::id(edge.item.second()) << 1) \| 1;
deba@2079	1822	}
deba@2079	1823	}
deba@2079	1824	Edge edgeFromId(int id) const {
deba@2079	1825	if ((id & 1) == 0) {
deba@2079	1826	return Edge(Parent::edgeFromId(id >> 1));
deba@2079	1827	} else {
deba@2079	1828	return Edge(Parent::nodeFromId(id >> 1));
deba@2079	1829	}
deba@2079	1830	}
deba@2079	1831	int maxEdgeId() const {
deba@2079	1832	return std::max(Parent::maxNodeId() << 1,
deba@2079	1833	(Parent::maxEdgeId() << 1) \| 1);
deba@2079	1834	}
deba@1697	1835
deba@2079	1836	/// \brief Returns true when the node is in-node.
deba@2079	1837	///
deba@2079	1838	/// Returns true when the node is in-node.
deba@2079	1839	static bool inNode(const Node& node) {
deba@2079	1840	return node.in_node;
deba@2079	1841	}
deba@1697	1842
deba@2079	1843	/// \brief Returns true when the node is out-node.
deba@2079	1844	///
deba@2079	1845	/// Returns true when the node is out-node.
deba@2079	1846	static bool outNode(const Node& node) {
deba@2079	1847	return !node.in_node;
deba@2079	1848	}
deba@1697	1849
deba@2079	1850	/// \brief Returns true when the edge is edge in the original graph.
deba@2079	1851	///
deba@2079	1852	/// Returns true when the edge is edge in the original graph.
deba@2079	1853	static bool origEdge(const Edge& edge) {
deba@2079	1854	return edge.item.firstState();
deba@2079	1855	}
deba@1697	1856
deba@2079	1857	/// \brief Returns true when the edge binds an in-node and an out-node.
deba@2079	1858	///
deba@2079	1859	/// Returns true when the edge binds an in-node and an out-node.
deba@2079	1860	static bool bindEdge(const Edge& edge) {
deba@2079	1861	return edge.item.secondState();
deba@2079	1862	}
deba@1697	1863
deba@2079	1864	/// \brief Gives back the in-node created from the \c node.
deba@2079	1865	///
deba@2079	1866	/// Gives back the in-node created from the \c node.
deba@2079	1867	static Node inNode(const GraphNode& node) {
deba@2079	1868	return Node(node, true);
deba@2079	1869	}
deba@2079	1870
deba@2079	1871	/// \brief Gives back the out-node created from the \c node.
deba@2079	1872	///
deba@2079	1873	/// Gives back the out-node created from the \c node.
deba@2079	1874	static Node outNode(const GraphNode& node) {
deba@2079	1875	return Node(node, false);
deba@2079	1876	}
deba@2079	1877
deba@2079	1878	/// \brief Gives back the edge binds the two part of the node.
deba@2079	1879	///
deba@2079	1880	/// Gives back the edge binds the two part of the node.
deba@2079	1881	static Edge edge(const GraphNode& node) {
deba@2079	1882	return Edge(node);
deba@2079	1883	}
deba@2079	1884
deba@2079	1885	/// \brief Gives back the edge of the original edge.
deba@2079	1886	///
deba@2079	1887	/// Gives back the edge of the original edge.
deba@2079	1888	static Edge edge(const GraphEdge& edge) {
deba@2079	1889	return Edge(edge);
deba@2079	1890	}
deba@2079	1891
deba@2079	1892	typedef True NodeNumTag;
deba@2079	1893
deba@2079	1894	int nodeNum() const {
deba@2079	1895	return 2 * countNodes(*Parent::graph);
deba@2079	1896	}
deba@2079	1897
deba@2079	1898	typedef True EdgeNumTag;
deba@1697	1899
deba@2079	1900	int edgeNum() const {
deba@2079	1901	return countEdges(Parent::graph) + countNodes(Parent::graph);
deba@2079	1902	}
deba@1697	1903
deba@2079	1904	typedef True FindEdgeTag;
deba@2079	1905
deba@2079	1906	Edge findEdge(const Node& source, const Node& target,
deba@2079	1907	const Edge& prev = INVALID) const {
deba@2079	1908	if (inNode(source)) {
deba@2079	1909	if (outNode(target)) {
deba@2079	1910	if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
deba@2079	1911	return Edge(source);
deba@2079	1912	}
deba@2079	1913	}
deba@2079	1914	} else {
deba@2079	1915	if (inNode(target)) {
deba@2079	1916	return Edge(findEdge(*Parent::graph, source, target, prev));
deba@2079	1917	}
deba@2079	1918	}
deba@2079	1919	return INVALID;
deba@2079	1920	}
deba@1697	1921
deba@2079	1922	template <typename T>
deba@2079	1923	class NodeMap : public MapBase<Node, T> {
deba@2079	1924	typedef typename Parent::template NodeMap<T> NodeImpl;
deba@2079	1925	public:
deba@2079	1926	NodeMap(const SplitGraphAdaptorBase& _graph)
deba@2079	1927	: inNodeMap(_graph), outNodeMap(_graph) {}
deba@2079	1928	NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
deba@2079	1929	: inNodeMap(_graph, t), outNodeMap(_graph, t) {}
deba@1697	1930
deba@2079	1931	void set(const Node& key, const T& val) {
deba@2079	1932	if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
deba@2079	1933	else {outNodeMap.set(key, val); }
deba@2079	1934	}
deba@1697	1935
deba@2079	1936	typename MapTraits<NodeImpl>::ReturnValue
deba@2079	1937	operator[](const Node& key) {
deba@2079	1938	if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
deba@2079	1939	else { return outNodeMap[key]; }
deba@2079	1940	}
deba@1697	1941
deba@2079	1942	typename MapTraits<NodeImpl>::ConstReturnValue
deba@2079	1943	operator[](const Node& key) const {
deba@2079	1944	if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
deba@2079	1945	else { return outNodeMap[key]; }
deba@2079	1946	}
deba@1697	1947
deba@2079	1948	private:
deba@2079	1949	NodeImpl inNodeMap, outNodeMap;
deba@2079	1950	};
deba@1697	1951
deba@2079	1952	template <typename T>
deba@2079	1953	class EdgeMap : public MapBase<Edge, T> {
deba@2079	1954	typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
deba@2079	1955	typedef typename Parent::template NodeMap<T> NodeMapImpl;
deba@2079	1956	public:
deba@2079	1957
deba@2079	1958	EdgeMap(const SplitGraphAdaptorBase& _graph)
deba@2079	1959	: edge_map(_graph), node_map(_graph) {}
deba@2079	1960	EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
deba@2079	1961	: edge_map(_graph, t), node_map(_graph, t) {}
deba@1697	1962
deba@2079	1963	void set(const Edge& key, const T& val) {
deba@2079	1964	if (SplitGraphAdaptorBase::origEdge(key)) {
deba@2079	1965	edge_map.set(key.item.first(), val);
deba@2079	1966	} else {
deba@2079	1967	node_map.set(key.item.second(), val);
deba@2079	1968	}
deba@2079	1969	}
deba@1697	1970
deba@2079	1971	typename MapTraits<EdgeMapImpl>::ReturnValue
deba@2079	1972	operator[](const Edge& key) {
deba@2079	1973	if (SplitGraphAdaptorBase::origEdge(key)) {
deba@2079	1974	return edge_map[key.item.first()];
deba@2079	1975	} else {
deba@2079	1976	return node_map[key.item.second()];
deba@2079	1977	}
deba@2079	1978	}
deba@1697	1979
deba@2079	1980	typename MapTraits<EdgeMapImpl>::ConstReturnValue
deba@2079	1981	operator[](const Edge& key) const {
deba@2079	1982	if (SplitGraphAdaptorBase::origEdge(key)) {
deba@2079	1983	return edge_map[key.item.first()];
deba@2079	1984	} else {
deba@2079	1985	return node_map[key.item.second()];
deba@2079	1986	}
deba@2079	1987	}
deba@1697	1988
deba@2079	1989	private:
deba@2079	1990	typename Parent::template EdgeMap<T> edge_map;
deba@2079	1991	typename Parent::template NodeMap<T> node_map;
deba@2079	1992	};
deba@1697	1993
deba@1697	1994
deba@2079	1995	};
deba@1697	1996
deba@2079	1997	template <typename _Graph, typename NodeEnable = void,
deba@2079	1998	typename EdgeEnable = void>
deba@2079	1999	class AlterableSplitGraphAdaptor
deba@2079	2000	: public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
deba@2079	2001	public:
deba@1697	2002
deba@2079	2003	typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
deba@2079	2004	typedef _Graph Graph;
deba@1697	2005
deba@2079	2006	typedef typename Graph::Node GraphNode;
deba@2079	2007	typedef typename Graph::Node GraphEdge;
deba@1697	2008
deba@2079	2009	protected:
deba@2079	2010
deba@2079	2011	AlterableSplitGraphAdaptor() : Parent() {}
deba@2079	2012
deba@2079	2013	public:
deba@2079	2014
deba@2079	2015	typedef InvalidType NodeNotifier;
deba@2079	2016	typedef InvalidType EdgeNotifier;
deba@2079	2017
deba@2079	2018	};
deba@2079	2019
deba@2079	2020	template <typename _Graph, typename EdgeEnable>
deba@2079	2021	class AlterableSplitGraphAdaptor<
deba@2079	2022	_Graph,
deba@2079	2023	typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
deba@2079	2024	EdgeEnable>
deba@2079	2025	: public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
deba@2079	2026	public:
deba@2079	2027
deba@2079	2028	typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
deba@2079	2029	typedef _Graph Graph;
deba@2079	2030
deba@2079	2031	typedef typename Graph::Node GraphNode;
deba@2079	2032	typedef typename Graph::Edge GraphEdge;
deba@2079	2033
deba@2079	2034	typedef typename Parent::Node Node;
deba@2079	2035	typedef typename Parent::Edge Edge;
deba@2079	2036
deba@2079	2037	protected:
deba@2079	2038
deba@2079	2039	AlterableSplitGraphAdaptor()
deba@2079	2040	: Parent(), node_notifier(this), node_notifier_proxy(this) {}
deba@2079	2041
deba@2079	2042	void setGraph(_Graph& graph) {
deba@2079	2043	Parent::setGraph(graph);
deba@2079	2044	node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
deba@2079	2045	}
deba@2079	2046
deba@2079	2047	public:
deba@2079	2048
deba@2079	2049	~AlterableSplitGraphAdaptor() {
deba@2079	2050	node_notifier.clear();
deba@2079	2051	}
deba@2079	2052
deba@2079	2053	typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
deba@2079	2054	typedef InvalidType EdgeNotifier;
deba@2079	2055
deba@2079	2056	NodeNotifier& getNotifier(Node) const { return node_notifier; }
deba@2079	2057
deba@2079	2058	protected:
deba@2079	2059
deba@2079	2060	class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
deba@2079	2061	public:
deba@2079	2062
deba@2079	2063	typedef typename Graph::NodeNotifier::ObserverBase Parent;
deba@2079	2064	typedef AlterableSplitGraphAdaptor AdaptorBase;
deba@1697	2065
deba@2079	2066	NodeNotifierProxy(const AdaptorBase& _adaptor)
deba@2079	2067	: Parent(), adaptor(&_adaptor) {
deba@2079	2068	}
deba@2079	2069
deba@2079	2070	virtual ~NodeNotifierProxy() {
deba@2079	2071	if (Parent::attached()) {
deba@2079	2072	Parent::detach();
deba@2079	2073	}
deba@2079	2074	}
deba@2079	2075
deba@2079	2076	void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
deba@2079	2077	Parent::attach(graph_notifier);
deba@2079	2078	}
deba@2079	2079
deba@1697	2080
deba@2079	2081	protected:
deba@2079	2082
deba@2079	2083	virtual void add(const GraphNode& gn) {
deba@2079	2084	std::vector<Node> nodes;
deba@2079	2085	nodes.push_back(AdaptorBase::Parent::inNode(gn));
deba@2079	2086	nodes.push_back(AdaptorBase::Parent::outNode(gn));
deba@2079	2087	adaptor->getNotifier(Node()).add(nodes);
deba@2079	2088	}
deba@2079	2089
deba@2079	2090	virtual void add(const std::vector<GraphNode>& gn) {
deba@2079	2091	std::vector<Node> nodes;
deba@2079	2092	for (int i = 0; i < (int)gn.size(); ++i) {
deba@2079	2093	nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
deba@2079	2094	nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
deba@2079	2095	}
deba@2079	2096	adaptor->getNotifier(Node()).add(nodes);
deba@2079	2097	}
deba@2079	2098
deba@2079	2099	virtual void erase(const GraphNode& gn) {
deba@2079	2100	std::vector<Node> nodes;
deba@2079	2101	nodes.push_back(AdaptorBase::Parent::inNode(gn));
deba@2079	2102	nodes.push_back(AdaptorBase::Parent::outNode(gn));
deba@2079	2103	adaptor->getNotifier(Node()).erase(nodes);
deba@2079	2104	}
deba@2079	2105
deba@2079	2106	virtual void erase(const std::vector<GraphNode>& gn) {
deba@2079	2107	std::vector<Node> nodes;
deba@2079	2108	for (int i = 0; i < (int)gn.size(); ++i) {
deba@2079	2109	nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
deba@2079	2110	nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
deba@2079	2111	}
deba@2079	2112	adaptor->getNotifier(Node()).erase(nodes);
deba@2079	2113	}
deba@2079	2114	virtual void build() {
deba@2079	2115	adaptor->getNotifier(Node()).build();
deba@2079	2116	}
deba@2079	2117	virtual void clear() {
deba@2079	2118	adaptor->getNotifier(Node()).clear();
deba@2079	2119	}
deba@2079	2120
deba@2079	2121	const AdaptorBase* adaptor;
deba@2079	2122	};
deba@2079	2123
deba@2079	2124
deba@2079	2125	mutable NodeNotifier node_notifier;
deba@2079	2126
deba@2079	2127	NodeNotifierProxy node_notifier_proxy;
deba@2079	2128
deba@2079	2129	};
deba@2079	2130
deba@2079	2131	template <typename _Graph>
deba@2079	2132	class AlterableSplitGraphAdaptor<
deba@2079	2133	_Graph,
deba@2079	2134	typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
deba@2079	2135	typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
deba@2079	2136	: public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
deba@2079	2137	public:
deba@2079	2138
deba@2079	2139	typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
deba@2079	2140	typedef _Graph Graph;
deba@2079	2141
deba@2079	2142	typedef typename Graph::Node GraphNode;
deba@2079	2143	typedef typename Graph::Edge GraphEdge;
deba@2079	2144
deba@2079	2145	typedef typename Parent::Node Node;
deba@2079	2146	typedef typename Parent::Edge Edge;
deba@2079	2147
deba@2079	2148	protected:
deba@2079	2149
deba@2079	2150	AlterableSplitGraphAdaptor()
deba@2079	2151	: Parent(), node_notifier(this), edge_notifier(this),
deba@2079	2152	node_notifier_proxy(this), edge_notifier_proxy(this) {}
deba@2079	2153
deba@2079	2154	void setGraph(_Graph& graph) {
deba@2079	2155	Parent::setGraph(graph);
deba@2079	2156	node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
deba@2079	2157	edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
deba@2079	2158	}
deba@2079	2159
deba@2079	2160	public:
deba@2079	2161
deba@2079	2162	~AlterableSplitGraphAdaptor() {
deba@2079	2163	node_notifier.clear();
deba@2079	2164	edge_notifier.clear();
deba@2079	2165	}
deba@2079	2166
deba@2079	2167	typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
deba@2079	2168	typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
deba@2079	2169
deba@2079	2170	NodeNotifier& getNotifier(Node) const { return node_notifier; }
deba@2079	2171	EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
deba@2079	2172
deba@2079	2173	protected:
deba@2079	2174
deba@2079	2175	class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
deba@2079	2176	public:
deba@1697	2177
deba@2079	2178	typedef typename Graph::NodeNotifier::ObserverBase Parent;
deba@2079	2179	typedef AlterableSplitGraphAdaptor AdaptorBase;
deba@2079	2180
deba@2079	2181	NodeNotifierProxy(const AdaptorBase& _adaptor)
deba@2079	2182	: Parent(), adaptor(&_adaptor) {
deba@2079	2183	}
deba@1697	2184
deba@2079	2185	virtual ~NodeNotifierProxy() {
deba@2079	2186	if (Parent::attached()) {
deba@2079	2187	Parent::detach();
deba@2079	2188	}
deba@2079	2189	}
deba@1697	2190
deba@2079	2191	void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
deba@2079	2192	Parent::attach(graph_notifier);
deba@2079	2193	}
deba@1697	2194
deba@2079	2195
deba@2079	2196	protected:
deba@1697	2197
deba@2079	2198	virtual void add(const GraphNode& gn) {
deba@2079	2199	std::vector<Node> nodes;
deba@2079	2200	nodes.push_back(AdaptorBase::Parent::inNode(gn));
deba@2079	2201	nodes.push_back(AdaptorBase::Parent::outNode(gn));
deba@2079	2202	adaptor->getNotifier(Node()).add(nodes);
deba@2079	2203	adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
deba@2079	2204	}
deba@2079	2205	virtual void add(const std::vector<GraphNode>& gn) {
deba@2079	2206	std::vector<Node> nodes;
deba@2079	2207	std::vector<Edge> edges;
deba@2079	2208	for (int i = 0; i < (int)gn.size(); ++i) {
deba@2079	2209	edges.push_back(AdaptorBase::Parent::edge(gn[i]));
deba@2079	2210	nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
deba@2079	2211	nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
deba@2079	2212	}
deba@2079	2213	adaptor->getNotifier(Node()).add(nodes);
deba@2079	2214	adaptor->getNotifier(Edge()).add(edges);
deba@2079	2215	}
deba@2079	2216	virtual void erase(const GraphNode& gn) {
deba@2079	2217	adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
deba@2079	2218	std::vector<Node> nodes;
deba@2079	2219	nodes.push_back(AdaptorBase::Parent::inNode(gn));
deba@2079	2220	nodes.push_back(AdaptorBase::Parent::outNode(gn));
deba@2079	2221	adaptor->getNotifier(Node()).erase(nodes);
deba@2079	2222	}
deba@2079	2223	virtual void erase(const std::vector<GraphNode>& gn) {
deba@2079	2224	std::vector<Node> nodes;
deba@2079	2225	std::vector<Edge> edges;
deba@2079	2226	for (int i = 0; i < (int)gn.size(); ++i) {
deba@2079	2227	edges.push_back(AdaptorBase::Parent::edge(gn[i]));
deba@2079	2228	nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
deba@2079	2229	nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
deba@2079	2230	}
deba@2079	2231	adaptor->getNotifier(Edge()).erase(edges);
deba@2079	2232	adaptor->getNotifier(Node()).erase(nodes);
deba@2079	2233	}
deba@2079	2234	virtual void build() {
deba@2079	2235	std::vector<Edge> edges;
deba@2079	2236	const typename Parent::Notifier* notifier = Parent::getNotifier();
deba@2079	2237	GraphNode it;
deba@2079	2238	for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@2079	2239	edges.push_back(AdaptorBase::Parent::edge(it));
deba@2079	2240	}
deba@2079	2241	adaptor->getNotifier(Node()).build();
deba@2079	2242	adaptor->getNotifier(Edge()).add(edges);
deba@2079	2243	}
deba@2079	2244	virtual void clear() {
deba@2079	2245	std::vector<Edge> edges;
deba@2079	2246	const typename Parent::Notifier* notifier = Parent::getNotifier();
deba@2079	2247	GraphNode it;
deba@2079	2248	for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@2079	2249	edges.push_back(AdaptorBase::Parent::edge(it));
deba@2079	2250	}
deba@2079	2251	adaptor->getNotifier(Edge()).erase(edges);
deba@2079	2252	adaptor->getNotifier(Node()).clear();
deba@2079	2253	}
deba@1697	2254
deba@2079	2255	const AdaptorBase* adaptor;
deba@2079	2256	};
deba@1697	2257
deba@2079	2258	class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
deba@2079	2259	public:
deba@2079	2260
deba@2079	2261	typedef typename Graph::EdgeNotifier::ObserverBase Parent;
deba@2079	2262	typedef AlterableSplitGraphAdaptor AdaptorBase;
deba@1697	2263
deba@2079	2264	EdgeNotifierProxy(const AdaptorBase& _adaptor)
deba@2079	2265	: Parent(), adaptor(&_adaptor) {
deba@2079	2266	}
deba@1697	2267
deba@2079	2268	virtual ~EdgeNotifierProxy() {
deba@2079	2269	if (Parent::attached()) {
deba@2079	2270	Parent::detach();
deba@2079	2271	}
deba@2079	2272	}
deba@1697	2273
deba@2079	2274	void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
deba@2079	2275	Parent::attach(graph_notifier);
deba@2079	2276	}
deba@1697	2277
deba@2079	2278
deba@2079	2279	protected:
deba@1697	2280
deba@2079	2281	virtual void add(const GraphEdge& ge) {
deba@2079	2282	adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
deba@2079	2283	}
deba@2079	2284	virtual void add(const std::vector<GraphEdge>& ge) {
deba@2079	2285	std::vector<Edge> edges;
deba@2079	2286	for (int i = 0; i < (int)ge.size(); ++i) {
deba@2079	2287	edges.push_back(AdaptorBase::edge(ge[i]));
deba@2079	2288	}
deba@2079	2289	adaptor->getNotifier(Edge()).add(edges);
deba@2079	2290	}
deba@2079	2291	virtual void erase(const GraphEdge& ge) {
deba@2079	2292	adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
deba@2079	2293	}
deba@2079	2294	virtual void erase(const std::vector<GraphEdge>& ge) {
deba@2079	2295	std::vector<Edge> edges;
deba@2079	2296	for (int i = 0; i < (int)ge.size(); ++i) {
deba@2079	2297	edges.push_back(AdaptorBase::edge(ge[i]));
deba@2079	2298	}
deba@2079	2299	adaptor->getNotifier(Edge()).erase(edges);
deba@2079	2300	}
deba@2079	2301	virtual void build() {
deba@2079	2302	std::vector<Edge> edges;
deba@2079	2303	const typename Parent::Notifier* notifier = Parent::getNotifier();
deba@2079	2304	GraphEdge it;
deba@2079	2305	for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@2079	2306	edges.push_back(AdaptorBase::Parent::edge(it));
deba@2079	2307	}
deba@2079	2308	adaptor->getNotifier(Edge()).add(edges);
deba@2079	2309	}
deba@2079	2310	virtual void clear() {
deba@2079	2311	std::vector<Edge> edges;
deba@2079	2312	const typename Parent::Notifier* notifier = Parent::getNotifier();
deba@2079	2313	GraphEdge it;
deba@2079	2314	for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@2079	2315	edges.push_back(AdaptorBase::Parent::edge(it));
deba@2079	2316	}
deba@2079	2317	adaptor->getNotifier(Edge()).erase(edges);
deba@2079	2318	}
deba@1697	2319
deba@2079	2320	const AdaptorBase* adaptor;
deba@2079	2321	};
deba@2079	2322
deba@2079	2323
deba@2079	2324	mutable NodeNotifier node_notifier;
deba@2079	2325	mutable EdgeNotifier edge_notifier;
deba@2079	2326
deba@2079	2327	NodeNotifierProxy node_notifier_proxy;
deba@2079	2328	EdgeNotifierProxy edge_notifier_proxy;
deba@2079	2329
deba@2079	2330	};
deba@2079	2331
deba@2079	2332	/// \ingroup graph_adaptors
deba@2079	2333	///
deba@2081	2334	/// \brief Split graph adaptor class
deba@2079	2335	///
deba@2079	2336	/// This is an graph adaptor which splits all node into an in-node
deba@2079	2337	/// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
deba@2079	2338	/// node in the graph with two node, \f$ u_{in} \f$ node and
deba@2079	2339	/// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
deba@2079	2340	/// original graph the new target of the edge will be \f$ u_{in} \f$ and
deba@2079	2341	/// similarly the source of the original \f$ (u, v) \f$ edge will be
deba@2079	2342	/// \f$ u_{out} \f$. The adaptor will add for each node in the
deba@2079	2343	/// original graph an additional edge which will connect
deba@2079	2344	/// \f$ (u_{in}, u_{out}) \f$.
deba@2079	2345	///
deba@2079	2346	/// The aim of this class is to run algorithm with node costs if the
deba@2079	2347	/// algorithm can use directly just edge costs. In this case we should use
deba@2079	2348	/// a \c SplitGraphAdaptor and set the node cost of the graph to the
deba@2079	2349	/// bind edge in the adapted graph.
deba@2079	2350	///
deba@2079	2351	/// By example a maximum flow algoritm can compute how many edge
deba@2079	2352	/// disjoint paths are in the graph. But we would like to know how
deba@2079	2353	/// many node disjoint paths are in the graph. First we have to
deba@2079	2354	/// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
deba@2079	2355	/// algorithm on the adapted graph. The bottleneck of the flow will
deba@2079	2356	/// be the bind edges which bounds the flow with the count of the
deba@2079	2357	/// node disjoint paths.
deba@2079	2358	///
deba@2079	2359	///\code
deba@2079	2360	///
deba@2079	2361	/// typedef SplitGraphAdaptor<SmartGraph> SGraph;
deba@2079	2362	///
deba@2079	2363	/// SGraph sgraph(graph);
deba@2079	2364	///
deba@2079	2365	/// typedef ConstMap<SGraph::Edge, int> SCapacity;
deba@2079	2366	/// SCapacity scapacity(1);
deba@2079	2367	///
deba@2079	2368	/// SGraph::EdgeMap<int> sflow(sgraph);
deba@2079	2369	///
deba@2079	2370	/// Preflow<SGraph, int, SCapacity>
deba@2079	2371	/// spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target),
deba@2079	2372	/// scapacity, sflow);
deba@2079	2373	///
deba@2079	2374	/// spreflow.run();
deba@2079	2375	///
deba@2079	2376	///\endcode
deba@2079	2377	///
deba@2079	2378	/// The result of the mamixum flow on the original graph
deba@2079	2379	/// shows the next figure:
deba@2079	2380	///
deba@2079	2381	/// \image html edge_disjoint.png
deba@2079	2382	/// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
deba@2079	2383	///
deba@2079	2384	/// And the maximum flow on the adapted graph:
deba@2079	2385	///
deba@2079	2386	/// \image html node_disjoint.png
deba@2079	2387	/// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
deba@2079	2388	///
deba@2079	2389	/// The second solution contains just 3 disjoint paths while the first 4.
deba@2081	2390	/// The full code can be found in the \ref disjoint_paths.cc demo file.
deba@2079	2391	///
deba@2079	2392	/// This graph adaptor is fully conform to the
deba@2079	2393	/// \ref concept::StaticGraph "StaticGraph" concept and
deba@2079	2394	/// contains some additional member functions and types. The
deba@2079	2395	/// documentation of some member functions may be found just in the
deba@2079	2396	/// SplitGraphAdaptorBase class.
deba@2079	2397	///
deba@2079	2398	/// \sa SplitGraphAdaptorBase
deba@2079	2399	template <typename _Graph>
deba@2079	2400	class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
deba@2079	2401	public:
deba@2079	2402	typedef AlterableSplitGraphAdaptor<_Graph> Parent;
deba@2079	2403
deba@2079	2404	typedef typename Parent::Node Node;
deba@2079	2405	typedef typename Parent::Edge Edge;
deba@2079	2406
deba@2079	2407	/// \brief Constructor of the adaptor.
deba@2079	2408	///
deba@2079	2409	/// Constructor of the adaptor.
deba@2079	2410	SplitGraphAdaptor(_Graph& graph) {
deba@2079	2411	Parent::setGraph(graph);
deba@2079	2412	}
deba@2079	2413
deba@2079	2414	/// \brief NodeMap combined from two original NodeMap
deba@2079	2415	///
deba@2079	2416	/// This class adapt two of the original graph NodeMap to
deba@2079	2417	/// get a node map on the adapted graph.
deba@2079	2418	template <typename InNodeMap, typename OutNodeMap>
deba@2079	2419	class CombinedNodeMap {
deba@2079	2420	public:
deba@2079	2421
deba@2079	2422	typedef Node Key;
deba@2079	2423	typedef typename InNodeMap::Value Value;
deba@2079	2424
deba@2079	2425	/// \brief Constructor
deba@2079	2426	///
deba@2079	2427	/// Constructor.
deba@2079	2428	CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
deba@2079	2429	: inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
deba@2079	2430
deba@2079	2431	/// \brief The subscript operator.
deba@2079	2432	///
deba@2079	2433	/// The subscript operator.
deba@2079	2434	Value& operator[](const Key& key) {
deba@2079	2435	if (Parent::inNode(key)) {
deba@2079	2436	return inNodeMap[key];
deba@2079	2437	} else {
deba@2079	2438	return outNodeMap[key];
deba@2079	2439	}
deba@2079	2440	}
deba@2079	2441
deba@2079	2442	/// \brief The const subscript operator.
deba@2079	2443	///
deba@2079	2444	/// The const subscript operator.
deba@2079	2445	Value operator[](const Key& key) const {
deba@2079	2446	if (Parent::inNode(key)) {
deba@2079	2447	return inNodeMap[key];
deba@2079	2448	} else {
deba@2079	2449	return outNodeMap[key];
deba@2079	2450	}
deba@2079	2451	}
deba@2079	2452
deba@2079	2453	/// \brief The setter function of the map.
deba@2079	2454	///
deba@2079	2455	/// The setter function of the map.
deba@2079	2456	void set(const Key& key, const Value& value) {
deba@2079	2457	if (Parent::inNode(key)) {
deba@2079	2458	inNodeMap.set(key, value);
deba@2079	2459	} else {
deba@2079	2460	outNodeMap.set(key, value);
deba@2079	2461	}
deba@2079	2462	}
deba@2079	2463
deba@2079	2464	private:
deba@2079	2465
deba@2079	2466	InNodeMap& inNodeMap;
deba@2079	2467	OutNodeMap& outNodeMap;
deba@2079	2468
deba@2079	2469	};
deba@2079	2470
deba@2079	2471
deba@2079	2472	/// \brief Just gives back a combined node map.
deba@2079	2473	///
deba@2079	2474	/// Just gives back a combined node map.
deba@2079	2475	template <typename InNodeMap, typename OutNodeMap>
deba@2079	2476	static CombinedNodeMap<InNodeMap, OutNodeMap>
deba@2079	2477	combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
deba@2079	2478	return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
deba@2079	2479	}
deba@2079	2480
deba@2079	2481	template <typename InNodeMap, typename OutNodeMap>
deba@2079	2482	static CombinedNodeMap<const InNodeMap, OutNodeMap>
deba@2079	2483	combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
deba@2079	2484	return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
deba@2079	2485	}
deba@2079	2486
deba@2079	2487	template <typename InNodeMap, typename OutNodeMap>
deba@2079	2488	static CombinedNodeMap<InNodeMap, const OutNodeMap>
deba@2079	2489	combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
deba@2079	2490	return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
deba@2079	2491	}
deba@2079	2492
deba@2079	2493	template <typename InNodeMap, typename OutNodeMap>
deba@2079	2494	static CombinedNodeMap<const InNodeMap, const OutNodeMap>
deba@2079	2495	combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
deba@2079	2496	return CombinedNodeMap<const InNodeMap,
deba@2079	2497	const OutNodeMap>(in_map, out_map);
deba@2079	2498	}
deba@2079	2499
deba@2079	2500	/// \brief EdgeMap combined from an original EdgeMap and NodeMap
deba@2079	2501	///
deba@2079	2502	/// This class adapt an original graph EdgeMap and NodeMap to
deba@2079	2503	/// get an edge map on the adapted graph.
deba@2079	2504	template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079	2505	class CombinedEdgeMap
deba@2079	2506	: public MapBase<Edge, typename GraphEdgeMap::Value> {
deba@2079	2507	public:
deba@2079	2508	typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
deba@2079	2509
deba@2079	2510	typedef typename Parent::Key Key;
deba@2079	2511	typedef typename Parent::Value Value;
deba@2079	2512
deba@2079	2513	/// \brief Constructor
deba@2079	2514	///
deba@2079	2515	/// Constructor.
deba@2079	2516	CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
deba@2079	2517	: edge_map(_edge_map), node_map(_node_map) {}
deba@2079	2518
deba@2079	2519	/// \brief The subscript operator.
deba@2079	2520	///
deba@2079	2521	/// The subscript operator.
deba@2079	2522	void set(const Edge& edge, const Value& val) {
deba@2079	2523	if (Parent::origEdge(edge)) {
deba@2079	2524	edge_map.set(edge, val);
deba@2079	2525	} else {
deba@2079	2526	node_map.set(edge, val);
deba@2079	2527	}
deba@2079	2528	}
deba@2079	2529
deba@2079	2530	/// \brief The const subscript operator.
deba@2079	2531	///
deba@2079	2532	/// The const subscript operator.
deba@2079	2533	Value operator[](const Key& edge) const {
deba@2079	2534	if (Parent::origEdge(edge)) {
deba@2079	2535	return edge_map[edge];
deba@2079	2536	} else {
deba@2079	2537	return node_map[edge];
deba@2079	2538	}
deba@2079	2539	}
deba@2079	2540
deba@2079	2541	/// \brief The const subscript operator.
deba@2079	2542	///
deba@2079	2543	/// The const subscript operator.
deba@2079	2544	Value& operator[](const Key& edge) {
deba@2079	2545	if (Parent::origEdge(edge)) {
deba@2079	2546	return edge_map[edge];
deba@2079	2547	} else {
deba@2079	2548	return node_map[edge];
deba@2079	2549	}
deba@2079	2550	}
deba@2079	2551
deba@2079	2552	private:
deba@2079	2553	GraphEdgeMap& edge_map;
deba@2079	2554	GraphNodeMap& node_map;
deba@2079	2555	};
deba@2079	2556
deba@2079	2557	/// \brief Just gives back a combined edge map.
deba@2079	2558	///
deba@2079	2559	/// Just gives back a combined edge map.
deba@2079	2560	template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079	2561	static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
deba@2079	2562	combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
deba@2079	2563	return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
deba@2079	2564	}
deba@2079	2565
deba@2079	2566	template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079	2567	static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
deba@2079	2568	combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
deba@2079	2569	return CombinedEdgeMap<const GraphEdgeMap,
deba@2079	2570	GraphNodeMap>(edge_map, node_map);
deba@2079	2571	}
deba@2079	2572
deba@2079	2573	template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079	2574	static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
deba@2079	2575	combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
deba@2079	2576	return CombinedEdgeMap<GraphEdgeMap,
deba@2079	2577	const GraphNodeMap>(edge_map, node_map);
deba@2079	2578	}
deba@2079	2579
deba@2079	2580	template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079	2581	static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
deba@2079	2582	combinedEdgeMap(const GraphEdgeMap& edge_map,
deba@2079	2583	const GraphNodeMap& node_map) {
deba@2079	2584	return CombinedEdgeMap<const GraphEdgeMap,
deba@2079	2585	const GraphNodeMap>(edge_map, node_map);
deba@2079	2586	}
deba@2079	2587
deba@2079	2588	};
deba@2079	2589
deba@1697	2590
alpar@921	2591	} //namespace lemon
marci@556	2592
alpar@1401	2593	#endif //LEMON_GRAPH_ADAPTOR_H
marci@556	2594

author	deba
	Fri, 12 May 2006 15:29:42 +0000
changeset 2081	94a7deb46c07
parent 2079	7fe378247fea
child 2084	59769591eb60
permissions	-rw-r--r--