lemon-0.x: lemon/graph_adaptor.h@49c8d69c0640 (annotated)

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

author	alpar
	Thu, 09 Nov 2006 00:19:53 +0000
changeset 2297	49c8d69c0640
parent 2260	4274224f8a7d
child 2340	03c71d754990
permissions	-rw-r--r--