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

author	kpeter
	Tue, 05 Feb 2008 11:03:55 +0000
changeset 2560	635e7985be46
parent 2529	93de38566e6c
child 2617	5222a3c470ed
permissions	-rw-r--r--