lemon-1.1: lemon/adaptors.h@e9a568cc86e3 (annotated)

deba@416	1	/* -- mode: C++; indent-tabs-mode: nil; --
deba@414	2	*
deba@416	3	* This file is a part of LEMON, a generic C++ optimization library.
deba@414	4	*
deba@414	5	* Copyright (C) 2003-2008
deba@414	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@414	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@414	8	*
deba@414	9	* Permission to use, modify and distribute this software is granted
deba@414	10	* provided that this copyright notice appears in all copies. For
deba@414	11	* precise terms see the accompanying LICENSE file.
deba@414	12	*
deba@414	13	* This software is provided "AS IS" with no warranty of any kind,
deba@414	14	* express or implied, and with no claim as to its suitability for any
deba@414	15	* purpose.
deba@414	16	*
deba@414	17	*/
deba@414	18
deba@416	19	#ifndef LEMON_ADAPTORS_H
deba@416	20	#define LEMON_ADAPTORS_H
deba@416	21
deba@416	22	/// \ingroup graph_adaptors
deba@416	23	/// \file
deba@416	24	/// \brief Several graph adaptors
deba@414	25	///
deba@416	26	/// This file contains several useful adaptors for digraphs and graphs.
deba@414	27
deba@414	28	#include <lemon/core.h>
deba@414	29	#include <lemon/maps.h>
deba@414	30	#include <lemon/bits/variant.h>
deba@414	31
deba@414	32	#include <lemon/bits/graph_adaptor_extender.h>
deba@414	33	#include <lemon/tolerance.h>
deba@414	34
deba@414	35	#include <algorithm>
deba@414	36
deba@414	37	namespace lemon {
deba@414	38
deba@414	39	template<typename _Digraph>
deba@414	40	class DigraphAdaptorBase {
deba@414	41	public:
deba@414	42	typedef _Digraph Digraph;
deba@414	43	typedef DigraphAdaptorBase Adaptor;
deba@414	44	typedef Digraph ParentDigraph;
deba@414	45
deba@414	46	protected:
deba@414	47	Digraph* _digraph;
deba@414	48	DigraphAdaptorBase() : _digraph(0) { }
deba@414	49	void setDigraph(Digraph& digraph) { _digraph = &digraph; }
deba@414	50
deba@414	51	public:
deba@414	52	DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
deba@414	53
deba@414	54	typedef typename Digraph::Node Node;
deba@414	55	typedef typename Digraph::Arc Arc;
deba@416	56
deba@414	57	void first(Node& i) const { _digraph->first(i); }
deba@414	58	void first(Arc& i) const { _digraph->first(i); }
deba@414	59	void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
deba@414	60	void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
deba@414	61
deba@414	62	void next(Node& i) const { _digraph->next(i); }
deba@414	63	void next(Arc& i) const { _digraph->next(i); }
deba@414	64	void nextIn(Arc& i) const { _digraph->nextIn(i); }
deba@414	65	void nextOut(Arc& i) const { _digraph->nextOut(i); }
deba@414	66
deba@414	67	Node source(const Arc& a) const { return _digraph->source(a); }
deba@414	68	Node target(const Arc& a) const { return _digraph->target(a); }
deba@414	69
deba@414	70	typedef NodeNumTagIndicator<Digraph> NodeNumTag;
deba@414	71	int nodeNum() const { return _digraph->nodeNum(); }
deba@416	72
deba@414	73	typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
deba@414	74	int arcNum() const { return _digraph->arcNum(); }
deba@414	75
deba@414	76	typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@414	77	Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
deba@414	78	return _digraph->findArc(u, v, prev);
deba@414	79	}
deba@416	80
deba@414	81	Node addNode() { return _digraph->addNode(); }
deba@414	82	Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
deba@414	83
deba@414	84	void erase(const Node& n) const { _digraph->erase(n); }
deba@414	85	void erase(const Arc& a) const { _digraph->erase(a); }
deba@416	86
deba@414	87	void clear() const { _digraph->clear(); }
deba@416	88
deba@414	89	int id(const Node& n) const { return _digraph->id(n); }
deba@414	90	int id(const Arc& a) const { return _digraph->id(a); }
deba@414	91
deba@414	92	Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
deba@414	93	Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
deba@414	94
deba@414	95	int maxNodeId() const { return _digraph->maxNodeId(); }
deba@414	96	int maxArcId() const { return _digraph->maxArcId(); }
deba@414	97
deba@414	98	typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
deba@416	99	NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
deba@414	100
deba@414	101	typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
deba@416	102	ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
deba@416	103
deba@414	104	template <typename _Value>
deba@414	105	class NodeMap : public Digraph::template NodeMap<_Value> {
deba@414	106	public:
deba@414	107
deba@414	108	typedef typename Digraph::template NodeMap<_Value> Parent;
deba@414	109
deba@416	110	explicit NodeMap(const Adaptor& adaptor)
deba@416	111	: Parent(*adaptor._digraph) {}
deba@414	112
deba@414	113	NodeMap(const Adaptor& adaptor, const _Value& value)
deba@416	114	: Parent(*adaptor._digraph, value) { }
deba@414	115
deba@414	116	private:
deba@414	117	NodeMap& operator=(const NodeMap& cmap) {
deba@414	118	return operator=<NodeMap>(cmap);
deba@414	119	}
deba@414	120
deba@414	121	template <typename CMap>
deba@414	122	NodeMap& operator=(const CMap& cmap) {
deba@414	123	Parent::operator=(cmap);
deba@414	124	return *this;
deba@414	125	}
deba@416	126
deba@414	127	};
deba@414	128
deba@414	129	template <typename _Value>
deba@414	130	class ArcMap : public Digraph::template ArcMap<_Value> {
deba@414	131	public:
deba@416	132
deba@414	133	typedef typename Digraph::template ArcMap<_Value> Parent;
deba@416	134
deba@416	135	explicit ArcMap(const Adaptor& adaptor)
deba@416	136	: Parent(*adaptor._digraph) {}
deba@414	137
deba@414	138	ArcMap(const Adaptor& adaptor, const _Value& value)
deba@416	139	: Parent(*adaptor._digraph, value) {}
deba@414	140
deba@414	141	private:
deba@414	142	ArcMap& operator=(const ArcMap& cmap) {
deba@414	143	return operator=<ArcMap>(cmap);
deba@414	144	}
deba@414	145
deba@414	146	template <typename CMap>
deba@414	147	ArcMap& operator=(const CMap& cmap) {
deba@414	148	Parent::operator=(cmap);
deba@414	149	return *this;
deba@414	150	}
deba@414	151
deba@414	152	};
deba@414	153
deba@414	154	};
deba@414	155
deba@416	156	template<typename _Graph>
deba@416	157	class GraphAdaptorBase {
deba@416	158	public:
deba@416	159	typedef _Graph Graph;
deba@416	160	typedef Graph ParentGraph;
deba@416	161
deba@416	162	protected:
deba@416	163	Graph* _graph;
deba@416	164
deba@416	165	GraphAdaptorBase() : _graph(0) {}
deba@416	166
deba@416	167	void setGraph(Graph& graph) { _graph = &graph; }
deba@416	168
deba@416	169	public:
deba@416	170	GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
deba@416	171
deba@416	172	typedef typename Graph::Node Node;
deba@416	173	typedef typename Graph::Arc Arc;
deba@416	174	typedef typename Graph::Edge Edge;
deba@416	175
deba@416	176	void first(Node& i) const { _graph->first(i); }
deba@416	177	void first(Arc& i) const { _graph->first(i); }
deba@416	178	void first(Edge& i) const { _graph->first(i); }
deba@416	179	void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
deba@416	180	void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
deba@416	181	void firstInc(Edge &i, bool &d, const Node &n) const {
deba@416	182	_graph->firstInc(i, d, n);
deba@416	183	}
deba@416	184
deba@416	185	void next(Node& i) const { _graph->next(i); }
deba@416	186	void next(Arc& i) const { _graph->next(i); }
deba@416	187	void next(Edge& i) const { _graph->next(i); }
deba@416	188	void nextIn(Arc& i) const { _graph->nextIn(i); }
deba@416	189	void nextOut(Arc& i) const { _graph->nextOut(i); }
deba@416	190	void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
deba@416	191
deba@416	192	Node u(const Edge& e) const { return _graph->u(e); }
deba@416	193	Node v(const Edge& e) const { return _graph->v(e); }
deba@416	194
deba@416	195	Node source(const Arc& a) const { return _graph->source(a); }
deba@416	196	Node target(const Arc& a) const { return _graph->target(a); }
deba@416	197
deba@416	198	typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@416	199	int nodeNum() const { return _graph->nodeNum(); }
deba@416	200
deba@416	201	typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@416	202	int arcNum() const { return _graph->arcNum(); }
deba@416	203	int edgeNum() const { return _graph->edgeNum(); }
deba@416	204
deba@416	205	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416	206	Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
deba@416	207	return _graph->findArc(u, v, prev);
deba@416	208	}
deba@416	209	Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
deba@416	210	return _graph->findEdge(u, v, prev);
deba@416	211	}
deba@416	212
deba@416	213	Node addNode() { return _graph->addNode(); }
deba@416	214	Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
deba@416	215
deba@416	216	void erase(const Node& i) { _graph->erase(i); }
deba@416	217	void erase(const Edge& i) { _graph->erase(i); }
deba@416	218
deba@416	219	void clear() { _graph->clear(); }
deba@416	220
deba@416	221	bool direction(const Arc& a) const { return _graph->direction(a); }
deba@416	222	Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
deba@416	223
deba@416	224	int id(const Node& v) const { return _graph->id(v); }
deba@416	225	int id(const Arc& a) const { return _graph->id(a); }
deba@416	226	int id(const Edge& e) const { return _graph->id(e); }
deba@416	227
deba@416	228	Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
deba@416	229	Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
deba@416	230	Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
deba@416	231
deba@416	232	int maxNodeId() const { return _graph->maxNodeId(); }
deba@416	233	int maxArcId() const { return _graph->maxArcId(); }
deba@416	234	int maxEdgeId() const { return _graph->maxEdgeId(); }
deba@416	235
deba@416	236	typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@416	237	NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
deba@416	238
deba@416	239	typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
deba@416	240	ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
deba@416	241
deba@416	242	typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@416	243	EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
deba@416	244
deba@416	245	template <typename _Value>
deba@416	246	class NodeMap : public Graph::template NodeMap<_Value> {
deba@416	247	public:
deba@416	248	typedef typename Graph::template NodeMap<_Value> Parent;
deba@416	249	explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
deba@416	250	: Parent(*adapter._graph) {}
deba@416	251	NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
deba@416	252	: Parent(*adapter._graph, value) {}
deba@416	253
deba@416	254	private:
deba@416	255	NodeMap& operator=(const NodeMap& cmap) {
deba@416	256	return operator=<NodeMap>(cmap);
deba@416	257	}
deba@416	258
deba@416	259	template <typename CMap>
deba@416	260	NodeMap& operator=(const CMap& cmap) {
deba@416	261	Parent::operator=(cmap);
deba@416	262	return *this;
deba@416	263	}
deba@416	264
deba@416	265	};
deba@416	266
deba@416	267	template <typename _Value>
deba@416	268	class ArcMap : public Graph::template ArcMap<_Value> {
deba@416	269	public:
deba@416	270	typedef typename Graph::template ArcMap<_Value> Parent;
deba@416	271	explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
deba@416	272	: Parent(*adapter._graph) {}
deba@416	273	ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
deba@416	274	: Parent(*adapter._graph, value) {}
deba@416	275
deba@416	276	private:
deba@416	277	ArcMap& operator=(const ArcMap& cmap) {
deba@416	278	return operator=<ArcMap>(cmap);
deba@416	279	}
deba@416	280
deba@416	281	template <typename CMap>
deba@416	282	ArcMap& operator=(const CMap& cmap) {
deba@416	283	Parent::operator=(cmap);
deba@416	284	return *this;
deba@416	285	}
deba@416	286	};
deba@416	287
deba@416	288	template <typename _Value>
deba@416	289	class EdgeMap : public Graph::template EdgeMap<_Value> {
deba@416	290	public:
deba@416	291	typedef typename Graph::template EdgeMap<_Value> Parent;
deba@416	292	explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
deba@416	293	: Parent(*adapter._graph) {}
deba@416	294	EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
deba@416	295	: Parent(*adapter._graph, value) {}
deba@416	296
deba@416	297	private:
deba@416	298	EdgeMap& operator=(const EdgeMap& cmap) {
deba@416	299	return operator=<EdgeMap>(cmap);
deba@416	300	}
deba@416	301
deba@416	302	template <typename CMap>
deba@416	303	EdgeMap& operator=(const CMap& cmap) {
deba@416	304	Parent::operator=(cmap);
deba@416	305	return *this;
deba@416	306	}
deba@416	307	};
deba@416	308
deba@416	309	};
deba@414	310
deba@414	311	template <typename _Digraph>
deba@416	312	class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
deba@414	313	public:
deba@414	314	typedef _Digraph Digraph;
deba@414	315	typedef DigraphAdaptorBase<_Digraph> Parent;
deba@414	316	protected:
deba@416	317	ReverseDigraphBase() : Parent() { }
deba@414	318	public:
deba@414	319	typedef typename Parent::Node Node;
deba@414	320	typedef typename Parent::Arc Arc;
deba@414	321
deba@414	322	void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
deba@414	323	void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
deba@414	324
deba@414	325	void nextIn(Arc& a) const { Parent::nextOut(a); }
deba@414	326	void nextOut(Arc& a) const { Parent::nextIn(a); }
deba@414	327
deba@414	328	Node source(const Arc& a) const { return Parent::target(a); }
deba@414	329	Node target(const Arc& a) const { return Parent::source(a); }
deba@414	330
deba@416	331	Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
deba@416	332
deba@414	333	typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@416	334	Arc findArc(const Node& u, const Node& v,
deba@416	335	const Arc& prev = INVALID) {
deba@414	336	return Parent::findArc(v, u, prev);
deba@414	337	}
deba@414	338
deba@414	339	};
deba@416	340
deba@416	341	/// \ingroup graph_adaptors
deba@414	342	///
deba@416	343	/// \brief A digraph adaptor which reverses the orientation of the arcs.
deba@414	344	///
deba@416	345	/// ReverseDigraph reverses the arcs in the adapted digraph. The
deba@416	346	/// SubDigraph is conform to the \ref concepts::Digraph
deba@416	347	/// "Digraph concept".
deba@414	348	///
deba@416	349	/// \tparam _Digraph It must be conform to the \ref concepts::Digraph
deba@416	350	/// "Digraph concept". The type can be specified to be const.
deba@414	351	template<typename _Digraph>
deba@416	352	class ReverseDigraph :
deba@416	353	public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
deba@414	354	public:
deba@414	355	typedef _Digraph Digraph;
deba@414	356	typedef DigraphAdaptorExtender<
deba@416	357	ReverseDigraphBase<_Digraph> > Parent;
deba@414	358	protected:
deba@416	359	ReverseDigraph() { }
deba@414	360	public:
deba@415	361
deba@415	362	/// \brief Constructor
deba@415	363	///
deba@416	364	/// Creates a reverse digraph adaptor for the given digraph
deba@416	365	explicit ReverseDigraph(Digraph& digraph) {
deba@416	366	Parent::setDigraph(digraph);
deba@414	367	}
deba@414	368	};
deba@414	369
deba@414	370	/// \brief Just gives back a reverse digraph adaptor
deba@414	371	///
deba@414	372	/// Just gives back a reverse digraph adaptor
deba@414	373	template<typename Digraph>
deba@416	374	ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
deba@416	375	return ReverseDigraph<const Digraph>(digraph);
deba@414	376	}
deba@414	377
deba@416	378	template <typename _Digraph, typename _NodeFilterMap,
deba@416	379	typename _ArcFilterMap, bool _checked = true>
deba@416	380	class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
deba@414	381	public:
deba@414	382	typedef _Digraph Digraph;
deba@414	383	typedef _NodeFilterMap NodeFilterMap;
deba@414	384	typedef _ArcFilterMap ArcFilterMap;
deba@414	385
deba@416	386	typedef SubDigraphBase Adaptor;
deba@414	387	typedef DigraphAdaptorBase<_Digraph> Parent;
deba@414	388	protected:
deba@414	389	NodeFilterMap* _node_filter;
deba@414	390	ArcFilterMap* _arc_filter;
deba@416	391	SubDigraphBase()
deba@414	392	: Parent(), _node_filter(0), _arc_filter(0) { }
deba@414	393
deba@414	394	void setNodeFilterMap(NodeFilterMap& node_filter) {
deba@414	395	_node_filter = &node_filter;
deba@414	396	}
deba@414	397	void setArcFilterMap(ArcFilterMap& arc_filter) {
deba@414	398	_arc_filter = &arc_filter;
deba@414	399	}
deba@414	400
deba@414	401	public:
deba@414	402
deba@414	403	typedef typename Parent::Node Node;
deba@414	404	typedef typename Parent::Arc Arc;
deba@414	405
deba@416	406	void first(Node& i) const {
deba@416	407	Parent::first(i);
deba@416	408	while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
deba@414	409	}
deba@414	410
deba@416	411	void first(Arc& i) const {
deba@416	412	Parent::first(i);
deba@416	413	while (i != INVALID && (!(*_arc_filter)[i]
deba@416	414	\|\| !(*_node_filter)[Parent::source(i)]
deba@416	415	\|\| !(*_node_filter)[Parent::target(i)]))
deba@416	416	Parent::next(i);
deba@414	417	}
deba@414	418
deba@416	419	void firstIn(Arc& i, const Node& n) const {
deba@416	420	Parent::firstIn(i, n);
deba@416	421	while (i != INVALID && (!(*_arc_filter)[i]
deba@416	422	\|\| !(*_node_filter)[Parent::source(i)]))
deba@416	423	Parent::nextIn(i);
deba@414	424	}
deba@414	425
deba@416	426	void firstOut(Arc& i, const Node& n) const {
deba@416	427	Parent::firstOut(i, n);
deba@416	428	while (i != INVALID && (!(*_arc_filter)[i]
deba@416	429	\|\| !(*_node_filter)[Parent::target(i)]))
deba@416	430	Parent::nextOut(i);
deba@414	431	}
deba@414	432
deba@416	433	void next(Node& i) const {
deba@416	434	Parent::next(i);
deba@416	435	while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
deba@414	436	}
deba@414	437
deba@416	438	void next(Arc& i) const {
deba@416	439	Parent::next(i);
deba@416	440	while (i != INVALID && (!(*_arc_filter)[i]
deba@416	441	\|\| !(*_node_filter)[Parent::source(i)]
deba@416	442	\|\| !(*_node_filter)[Parent::target(i)]))
deba@416	443	Parent::next(i);
deba@414	444	}
deba@414	445
deba@416	446	void nextIn(Arc& i) const {
deba@416	447	Parent::nextIn(i);
deba@416	448	while (i != INVALID && (!(*_arc_filter)[i]
deba@416	449	\|\| !(*_node_filter)[Parent::source(i)]))
deba@416	450	Parent::nextIn(i);
deba@414	451	}
deba@414	452
deba@416	453	void nextOut(Arc& i) const {
deba@416	454	Parent::nextOut(i);
deba@416	455	while (i != INVALID && (!(*_arc_filter)[i]
deba@416	456	\|\| !(*_node_filter)[Parent::target(i)]))
deba@416	457	Parent::nextOut(i);
deba@414	458	}
deba@414	459
deba@414	460	void hide(const Node& n) const { _node_filter->set(n, false); }
deba@414	461	void hide(const Arc& a) const { _arc_filter->set(a, false); }
deba@414	462
deba@415	463	void unHide(const Node& n) const { _node_filter->set(n, true); }
deba@414	464	void unHide(const Arc& a) const { _arc_filter->set(a, true); }
deba@414	465
deba@414	466	bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
deba@414	467	bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
deba@414	468
deba@414	469	typedef False NodeNumTag;
deba@414	470	typedef False EdgeNumTag;
deba@414	471
deba@414	472	typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@416	473	Arc findArc(const Node& source, const Node& target,
deba@416	474	const Arc& prev = INVALID) {
deba@414	475	if (!(_node_filter)[source] \|\| !(_node_filter)[target]) {
deba@414	476	return INVALID;
deba@414	477	}
deba@414	478	Arc arc = Parent::findArc(source, target, prev);
deba@414	479	while (arc != INVALID && !(*_arc_filter)[arc]) {
deba@414	480	arc = Parent::findArc(source, target, arc);
deba@414	481	}
deba@414	482	return arc;
deba@414	483	}
deba@414	484
deba@414	485	template <typename _Value>
deba@416	486	class NodeMap : public SubMapExtender<Adaptor,
deba@416	487	typename Parent::template NodeMap<_Value> > {
deba@414	488	public:
deba@414	489	typedef _Value Value;
deba@414	490	typedef SubMapExtender<Adaptor, typename Parent::
deba@414	491	template NodeMap<Value> > MapParent;
deba@416	492
deba@416	493	NodeMap(const Adaptor& adaptor)
deba@416	494	: MapParent(adaptor) {}
deba@416	495	NodeMap(const Adaptor& adaptor, const Value& value)
deba@416	496	: MapParent(adaptor, value) {}
deba@416	497
deba@414	498	private:
deba@414	499	NodeMap& operator=(const NodeMap& cmap) {
deba@416	500	return operator=<NodeMap>(cmap);
deba@414	501	}
deba@416	502
deba@414	503	template <typename CMap>
deba@414	504	NodeMap& operator=(const CMap& cmap) {
deba@414	505	MapParent::operator=(cmap);
deba@416	506	return *this;
deba@414	507	}
deba@414	508	};
deba@414	509
deba@414	510	template <typename _Value>
deba@416	511	class ArcMap : public SubMapExtender<Adaptor,
deba@416	512	typename Parent::template ArcMap<_Value> > {
deba@414	513	public:
deba@414	514	typedef _Value Value;
deba@414	515	typedef SubMapExtender<Adaptor, typename Parent::
deba@414	516	template ArcMap<Value> > MapParent;
deba@416	517
deba@416	518	ArcMap(const Adaptor& adaptor)
deba@416	519	: MapParent(adaptor) {}
deba@416	520	ArcMap(const Adaptor& adaptor, const Value& value)
deba@416	521	: MapParent(adaptor, value) {}
deba@416	522
deba@414	523	private:
deba@414	524	ArcMap& operator=(const ArcMap& cmap) {
deba@416	525	return operator=<ArcMap>(cmap);
deba@414	526	}
deba@416	527
deba@414	528	template <typename CMap>
deba@414	529	ArcMap& operator=(const CMap& cmap) {
deba@414	530	MapParent::operator=(cmap);
deba@416	531	return *this;
deba@414	532	}
deba@414	533	};
deba@414	534
deba@414	535	};
deba@414	536
deba@414	537	template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
deba@416	538	class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
deba@414	539	: public DigraphAdaptorBase<_Digraph> {
deba@414	540	public:
deba@414	541	typedef _Digraph Digraph;
deba@414	542	typedef _NodeFilterMap NodeFilterMap;
deba@414	543	typedef _ArcFilterMap ArcFilterMap;
deba@414	544
deba@416	545	typedef SubDigraphBase Adaptor;
deba@414	546	typedef DigraphAdaptorBase<Digraph> Parent;
deba@414	547	protected:
deba@414	548	NodeFilterMap* _node_filter;
deba@414	549	ArcFilterMap* _arc_filter;
deba@416	550	SubDigraphBase()
deba@414	551	: Parent(), _node_filter(0), _arc_filter(0) { }
deba@414	552
deba@414	553	void setNodeFilterMap(NodeFilterMap& node_filter) {
deba@414	554	_node_filter = &node_filter;
deba@414	555	}
deba@414	556	void setArcFilterMap(ArcFilterMap& arc_filter) {
deba@414	557	_arc_filter = &arc_filter;
deba@414	558	}
deba@414	559
deba@414	560	public:
deba@414	561
deba@414	562	typedef typename Parent::Node Node;
deba@414	563	typedef typename Parent::Arc Arc;
deba@414	564
deba@416	565	void first(Node& i) const {
deba@416	566	Parent::first(i);
deba@416	567	while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
deba@414	568	}
deba@414	569
deba@416	570	void first(Arc& i) const {
deba@416	571	Parent::first(i);
deba@416	572	while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
deba@414	573	}
deba@414	574
deba@416	575	void firstIn(Arc& i, const Node& n) const {
deba@416	576	Parent::firstIn(i, n);
deba@416	577	while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
deba@414	578	}
deba@414	579
deba@416	580	void firstOut(Arc& i, const Node& n) const {
deba@416	581	Parent::firstOut(i, n);
deba@416	582	while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
deba@414	583	}
deba@414	584
deba@416	585	void next(Node& i) const {
deba@416	586	Parent::next(i);
deba@416	587	while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
deba@414	588	}
deba@416	589	void next(Arc& i) const {
deba@416	590	Parent::next(i);
deba@416	591	while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
deba@414	592	}
deba@416	593	void nextIn(Arc& i) const {
deba@416	594	Parent::nextIn(i);
deba@416	595	while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
deba@414	596	}
deba@414	597
deba@416	598	void nextOut(Arc& i) const {
deba@416	599	Parent::nextOut(i);
deba@416	600	while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
deba@414	601	}
deba@414	602
deba@414	603	void hide(const Node& n) const { _node_filter->set(n, false); }
deba@414	604	void hide(const Arc& e) const { _arc_filter->set(e, false); }
deba@414	605
deba@415	606	void unHide(const Node& n) const { _node_filter->set(n, true); }
deba@414	607	void unHide(const Arc& e) const { _arc_filter->set(e, true); }
deba@414	608
deba@414	609	bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
deba@414	610	bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
deba@414	611
deba@414	612	typedef False NodeNumTag;
deba@414	613	typedef False EdgeNumTag;
deba@414	614
deba@414	615	typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@416	616	Arc findArc(const Node& source, const Node& target,
deba@416	617	const Arc& prev = INVALID) {
deba@414	618	if (!(_node_filter)[source] \|\| !(_node_filter)[target]) {
deba@414	619	return INVALID;
deba@414	620	}
deba@414	621	Arc arc = Parent::findArc(source, target, prev);
deba@414	622	while (arc != INVALID && !(*_arc_filter)[arc]) {
deba@414	623	arc = Parent::findArc(source, target, arc);
deba@414	624	}
deba@414	625	return arc;
deba@414	626	}
deba@414	627
deba@414	628	template <typename _Value>
deba@416	629	class NodeMap : public SubMapExtender<Adaptor,
deba@416	630	typename Parent::template NodeMap<_Value> > {
deba@414	631	public:
deba@414	632	typedef _Value Value;
deba@414	633	typedef SubMapExtender<Adaptor, typename Parent::
deba@414	634	template NodeMap<Value> > MapParent;
deba@416	635
deba@416	636	NodeMap(const Adaptor& adaptor)
deba@416	637	: MapParent(adaptor) {}
deba@416	638	NodeMap(const Adaptor& adaptor, const Value& value)
deba@416	639	: MapParent(adaptor, value) {}
deba@416	640
deba@414	641	private:
deba@414	642	NodeMap& operator=(const NodeMap& cmap) {
deba@416	643	return operator=<NodeMap>(cmap);
deba@414	644	}
deba@416	645
deba@414	646	template <typename CMap>
deba@414	647	NodeMap& operator=(const CMap& cmap) {
deba@414	648	MapParent::operator=(cmap);
deba@416	649	return *this;
deba@414	650	}
deba@414	651	};
deba@414	652
deba@414	653	template <typename _Value>
deba@416	654	class ArcMap : public SubMapExtender<Adaptor,
deba@416	655	typename Parent::template ArcMap<_Value> > {
deba@414	656	public:
deba@414	657	typedef _Value Value;
deba@414	658	typedef SubMapExtender<Adaptor, typename Parent::
deba@414	659	template ArcMap<Value> > MapParent;
deba@416	660
deba@416	661	ArcMap(const Adaptor& adaptor)
deba@416	662	: MapParent(adaptor) {}
deba@416	663	ArcMap(const Adaptor& adaptor, const Value& value)
deba@416	664	: MapParent(adaptor, value) {}
deba@416	665
deba@414	666	private:
deba@414	667	ArcMap& operator=(const ArcMap& cmap) {
deba@416	668	return operator=<ArcMap>(cmap);
deba@414	669	}
deba@416	670
deba@414	671	template <typename CMap>
deba@414	672	ArcMap& operator=(const CMap& cmap) {
deba@414	673	MapParent::operator=(cmap);
deba@416	674	return *this;
deba@414	675	}
deba@414	676	};
deba@414	677
deba@414	678	};
deba@414	679
deba@414	680	/// \ingroup graph_adaptors
deba@414	681	///
deba@416	682	/// \brief An adaptor for hiding nodes and arcs in a digraph
deba@416	683	///
deba@416	684	/// SubDigraph hides nodes and arcs in a digraph. A bool node map
deba@416	685	/// and a bool arc map must be specified, which define the filters
deba@416	686	/// for nodes and arcs. Just the nodes and arcs with true value are
deba@416	687	/// shown in the subdigraph. The SubDigraph is conform to the \ref
deba@416	688	/// concepts::Digraph "Digraph concept". If the \c _checked parameter
deba@416	689	/// is true, then the arcs incident to filtered nodes are also
deba@416	690	/// filtered out.
deba@416	691	///
deba@416	692	/// \tparam _Digraph It must be conform to the \ref
deba@416	693	/// concepts::Digraph "Digraph concept". The type can be specified
deba@416	694	/// to const.
deba@416	695	/// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
deba@416	696	/// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
deba@416	697	/// \tparam _checked If the parameter is false then the arc filtering
deba@416	698	/// is not checked with respect to node filter. Otherwise, each arc
deba@416	699	/// is automatically filtered, which is incident to a filtered node.
deba@416	700	///
deba@416	701	/// \see FilterNodes
deba@416	702	/// \see FilterArcs
deba@416	703	template<typename _Digraph,
deba@416	704	typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
deba@416	705	typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
deba@416	706	bool _checked = true>
deba@416	707	class SubDigraph
deba@416	708	: public DigraphAdaptorExtender<
deba@416	709	SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
deba@414	710	public:
deba@414	711	typedef _Digraph Digraph;
deba@414	712	typedef _NodeFilterMap NodeFilterMap;
deba@414	713	typedef _ArcFilterMap ArcFilterMap;
deba@414	714
deba@414	715	typedef DigraphAdaptorExtender<
deba@416	716	SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
deba@414	717	Parent;
deba@414	718
deba@415	719	typedef typename Parent::Node Node;
deba@415	720	typedef typename Parent::Arc Arc;
deba@415	721
deba@414	722	protected:
deba@416	723	SubDigraph() { }
deba@414	724	public:
deba@414	725
deba@415	726	/// \brief Constructor
deba@415	727	///
deba@416	728	/// Creates a subdigraph for the given digraph with
deba@415	729	/// given node and arc map filters.
deba@416	730	SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
deba@416	731	ArcFilterMap& arc_filter) {
deba@414	732	setDigraph(digraph);
deba@414	733	setNodeFilterMap(node_filter);
deba@414	734	setArcFilterMap(arc_filter);
deba@414	735	}
deba@414	736
deba@415	737	/// \brief Hides the node of the graph
deba@415	738	///
deba@416	739	/// This function hides \c n in the digraph, i.e. the iteration
deba@416	740	/// jumps over it. This is done by simply setting the value of \c n
deba@415	741	/// to be false in the corresponding node-map.
deba@415	742	void hide(const Node& n) const { Parent::hide(n); }
deba@415	743
deba@415	744	/// \brief Hides the arc of the graph
deba@415	745	///
deba@416	746	/// This function hides \c a in the digraph, i.e. the iteration
deba@415	747	/// jumps over it. This is done by simply setting the value of \c a
deba@415	748	/// to be false in the corresponding arc-map.
deba@415	749	void hide(const Arc& a) const { Parent::hide(a); }
deba@415	750
deba@415	751	/// \brief Unhides the node of the graph
deba@415	752	///
deba@416	753	/// The value of \c n is set to be true in the node-map which stores
deba@416	754	/// hide information. If \c n was hidden previuosly, then it is shown
deba@415	755	/// again
deba@415	756	void unHide(const Node& n) const { Parent::unHide(n); }
deba@415	757
deba@415	758	/// \brief Unhides the arc of the graph
deba@415	759	///
deba@416	760	/// The value of \c a is set to be true in the arc-map which stores
deba@416	761	/// hide information. If \c a was hidden previuosly, then it is shown
deba@415	762	/// again
deba@415	763	void unHide(const Arc& a) const { Parent::unHide(a); }
deba@415	764
deba@415	765	/// \brief Returns true if \c n is hidden.
deba@415	766	///
deba@415	767	/// Returns true if \c n is hidden.
deba@415	768	///
deba@415	769	bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@415	770
deba@415	771	/// \brief Returns true if \c a is hidden.
deba@415	772	///
deba@415	773	/// Returns true if \c a is hidden.
deba@415	774	///
deba@415	775	bool hidden(const Arc& a) const { return Parent::hidden(a); }
deba@415	776
deba@414	777	};
deba@414	778
deba@416	779	/// \brief Just gives back a subdigraph
deba@414	780	///
deba@416	781	/// Just gives back a subdigraph
deba@414	782	template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
deba@416	783	SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
deba@416	784	subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
deba@416	785	return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
deba@414	786	(digraph, nfm, afm);
deba@414	787	}
deba@414	788
deba@414	789	template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
deba@416	790	SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
deba@416	791	subDigraph(const Digraph& digraph,
deba@416	792	const NodeFilterMap& nfm, ArcFilterMap& afm) {
deba@416	793	return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
deba@414	794	(digraph, nfm, afm);
deba@414	795	}
deba@414	796
deba@414	797	template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
deba@416	798	SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
deba@416	799	subDigraph(const Digraph& digraph,
deba@416	800	NodeFilterMap& nfm, const ArcFilterMap& afm) {
deba@416	801	return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
deba@414	802	(digraph, nfm, afm);
deba@414	803	}
deba@414	804
deba@414	805	template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
deba@416	806	SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
deba@416	807	subDigraph(const Digraph& digraph,
deba@416	808	const NodeFilterMap& nfm, const ArcFilterMap& afm) {
deba@416	809	return SubDigraph<const Digraph, const NodeFilterMap,
deba@414	810	const ArcFilterMap>(digraph, nfm, afm);
deba@414	811	}
deba@414	812
deba@414	813
deba@416	814	template <typename _Graph, typename NodeFilterMap,
deba@416	815	typename EdgeFilterMap, bool _checked = true>
deba@416	816	class SubGraphBase : public GraphAdaptorBase<_Graph> {
deba@416	817	public:
deba@416	818	typedef _Graph Graph;
deba@416	819	typedef SubGraphBase Adaptor;
deba@416	820	typedef GraphAdaptorBase<_Graph> Parent;
deba@416	821	protected:
deba@416	822
deba@416	823	NodeFilterMap* _node_filter_map;
deba@416	824	EdgeFilterMap* _edge_filter_map;
deba@416	825
deba@416	826	SubGraphBase()
deba@416	827	: Parent(), _node_filter_map(0), _edge_filter_map(0) { }
deba@416	828
deba@416	829	void setNodeFilterMap(NodeFilterMap& node_filter_map) {
deba@416	830	_node_filter_map=&node_filter_map;
deba@416	831	}
deba@416	832	void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
deba@416	833	_edge_filter_map=&edge_filter_map;
deba@416	834	}
deba@416	835
deba@416	836	public:
deba@416	837
deba@416	838	typedef typename Parent::Node Node;
deba@416	839	typedef typename Parent::Arc Arc;
deba@416	840	typedef typename Parent::Edge Edge;
deba@416	841
deba@416	842	void first(Node& i) const {
deba@416	843	Parent::first(i);
deba@416	844	while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416	845	}
deba@416	846
deba@416	847	void first(Arc& i) const {
deba@416	848	Parent::first(i);
deba@416	849	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	850	\|\| !(*_node_filter_map)[Parent::source(i)]
deba@416	851	\|\| !(*_node_filter_map)[Parent::target(i)]))
deba@416	852	Parent::next(i);
deba@416	853	}
deba@416	854
deba@416	855	void first(Edge& i) const {
deba@416	856	Parent::first(i);
deba@416	857	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	858	\|\| !(*_node_filter_map)[Parent::u(i)]
deba@416	859	\|\| !(*_node_filter_map)[Parent::v(i)]))
deba@416	860	Parent::next(i);
deba@416	861	}
deba@416	862
deba@416	863	void firstIn(Arc& i, const Node& n) const {
deba@416	864	Parent::firstIn(i, n);
deba@416	865	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	866	\|\| !(*_node_filter_map)[Parent::source(i)]))
deba@416	867	Parent::nextIn(i);
deba@416	868	}
deba@416	869
deba@416	870	void firstOut(Arc& i, const Node& n) const {
deba@416	871	Parent::firstOut(i, n);
deba@416	872	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	873	\|\| !(*_node_filter_map)[Parent::target(i)]))
deba@416	874	Parent::nextOut(i);
deba@416	875	}
deba@416	876
deba@416	877	void firstInc(Edge& i, bool& d, const Node& n) const {
deba@416	878	Parent::firstInc(i, d, n);
deba@416	879	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	880	\|\| !(*_node_filter_map)[Parent::u(i)]
deba@416	881	\|\| !(*_node_filter_map)[Parent::v(i)]))
deba@416	882	Parent::nextInc(i, d);
deba@416	883	}
deba@416	884
deba@416	885	void next(Node& i) const {
deba@416	886	Parent::next(i);
deba@416	887	while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416	888	}
deba@416	889
deba@416	890	void next(Arc& i) const {
deba@416	891	Parent::next(i);
deba@416	892	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	893	\|\| !(*_node_filter_map)[Parent::source(i)]
deba@416	894	\|\| !(*_node_filter_map)[Parent::target(i)]))
deba@416	895	Parent::next(i);
deba@416	896	}
deba@416	897
deba@416	898	void next(Edge& i) const {
deba@416	899	Parent::next(i);
deba@416	900	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	901	\|\| !(*_node_filter_map)[Parent::u(i)]
deba@416	902	\|\| !(*_node_filter_map)[Parent::v(i)]))
deba@416	903	Parent::next(i);
deba@416	904	}
deba@416	905
deba@416	906	void nextIn(Arc& i) const {
deba@416	907	Parent::nextIn(i);
deba@416	908	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	909	\|\| !(*_node_filter_map)[Parent::source(i)]))
deba@416	910	Parent::nextIn(i);
deba@416	911	}
deba@416	912
deba@416	913	void nextOut(Arc& i) const {
deba@416	914	Parent::nextOut(i);
deba@416	915	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	916	\|\| !(*_node_filter_map)[Parent::target(i)]))
deba@416	917	Parent::nextOut(i);
deba@416	918	}
deba@416	919
deba@416	920	void nextInc(Edge& i, bool& d) const {
deba@416	921	Parent::nextInc(i, d);
deba@416	922	while (i!=INVALID && (!(*_edge_filter_map)[i]
deba@416	923	\|\| !(*_node_filter_map)[Parent::u(i)]
deba@416	924	\|\| !(*_node_filter_map)[Parent::v(i)]))
deba@416	925	Parent::nextInc(i, d);
deba@416	926	}
deba@416	927
deba@416	928	void hide(const Node& n) const { _node_filter_map->set(n, false); }
deba@416	929	void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
deba@416	930
deba@416	931	void unHide(const Node& n) const { _node_filter_map->set(n, true); }
deba@416	932	void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
deba@416	933
deba@416	934	bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
deba@416	935	bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
deba@416	936
deba@416	937	typedef False NodeNumTag;
deba@416	938	typedef False EdgeNumTag;
deba@416	939
deba@416	940	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416	941	Arc findArc(const Node& u, const Node& v,
deba@416	942	const Arc& prev = INVALID) {
deba@416	943	if (!(_node_filter_map)[u] \|\| !(_node_filter_map)[v]) {
deba@416	944	return INVALID;
deba@416	945	}
deba@416	946	Arc arc = Parent::findArc(u, v, prev);
deba@416	947	while (arc != INVALID && !(*_edge_filter_map)[arc]) {
deba@416	948	arc = Parent::findArc(u, v, arc);
deba@416	949	}
deba@416	950	return arc;
deba@416	951	}
deba@416	952	Edge findEdge(const Node& u, const Node& v,
deba@416	953	const Edge& prev = INVALID) {
deba@416	954	if (!(_node_filter_map)[u] \|\| !(_node_filter_map)[v]) {
deba@416	955	return INVALID;
deba@416	956	}
deba@416	957	Edge edge = Parent::findEdge(u, v, prev);
deba@416	958	while (edge != INVALID && !(*_edge_filter_map)[edge]) {
deba@416	959	edge = Parent::findEdge(u, v, edge);
deba@416	960	}
deba@416	961	return edge;
deba@416	962	}
deba@416	963
deba@416	964	template <typename _Value>
deba@416	965	class NodeMap : public SubMapExtender<Adaptor,
deba@416	966	typename Parent::template NodeMap<_Value> > {
deba@416	967	public:
deba@416	968	typedef _Value Value;
deba@416	969	typedef SubMapExtender<Adaptor, typename Parent::
deba@416	970	template NodeMap<Value> > MapParent;
deba@416	971
deba@416	972	NodeMap(const Adaptor& adaptor)
deba@416	973	: MapParent(adaptor) {}
deba@416	974	NodeMap(const Adaptor& adaptor, const Value& value)
deba@416	975	: MapParent(adaptor, value) {}
deba@416	976
deba@416	977	private:
deba@416	978	NodeMap& operator=(const NodeMap& cmap) {
deba@416	979	return operator=<NodeMap>(cmap);
deba@416	980	}
deba@416	981
deba@416	982	template <typename CMap>
deba@416	983	NodeMap& operator=(const CMap& cmap) {
deba@416	984	MapParent::operator=(cmap);
deba@416	985	return *this;
deba@416	986	}
deba@416	987	};
deba@416	988
deba@416	989	template <typename _Value>
deba@416	990	class ArcMap : public SubMapExtender<Adaptor,
deba@416	991	typename Parent::template ArcMap<_Value> > {
deba@416	992	public:
deba@416	993	typedef _Value Value;
deba@416	994	typedef SubMapExtender<Adaptor, typename Parent::
deba@416	995	template ArcMap<Value> > MapParent;
deba@416	996
deba@416	997	ArcMap(const Adaptor& adaptor)
deba@416	998	: MapParent(adaptor) {}
deba@416	999	ArcMap(const Adaptor& adaptor, const Value& value)
deba@416	1000	: MapParent(adaptor, value) {}
deba@416	1001
deba@416	1002	private:
deba@416	1003	ArcMap& operator=(const ArcMap& cmap) {
deba@416	1004	return operator=<ArcMap>(cmap);
deba@416	1005	}
deba@416	1006
deba@416	1007	template <typename CMap>
deba@416	1008	ArcMap& operator=(const CMap& cmap) {
deba@416	1009	MapParent::operator=(cmap);
deba@416	1010	return *this;
deba@416	1011	}
deba@416	1012	};
deba@416	1013
deba@416	1014	template <typename _Value>
deba@416	1015	class EdgeMap : public SubMapExtender<Adaptor,
deba@416	1016	typename Parent::template EdgeMap<_Value> > {
deba@416	1017	public:
deba@416	1018	typedef _Value Value;
deba@416	1019	typedef SubMapExtender<Adaptor, typename Parent::
deba@416	1020	template EdgeMap<Value> > MapParent;
deba@416	1021
deba@416	1022	EdgeMap(const Adaptor& adaptor)
deba@416	1023	: MapParent(adaptor) {}
deba@416	1024
deba@416	1025	EdgeMap(const Adaptor& adaptor, const Value& value)
deba@416	1026	: MapParent(adaptor, value) {}
deba@416	1027
deba@416	1028	private:
deba@416	1029	EdgeMap& operator=(const EdgeMap& cmap) {
deba@416	1030	return operator=<EdgeMap>(cmap);
deba@416	1031	}
deba@416	1032
deba@416	1033	template <typename CMap>
deba@416	1034	EdgeMap& operator=(const CMap& cmap) {
deba@416	1035	MapParent::operator=(cmap);
deba@416	1036	return *this;
deba@416	1037	}
deba@416	1038	};
deba@416	1039
deba@416	1040	};
deba@416	1041
deba@416	1042	template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@416	1043	class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
deba@416	1044	: public GraphAdaptorBase<_Graph> {
deba@416	1045	public:
deba@416	1046	typedef _Graph Graph;
deba@416	1047	typedef SubGraphBase Adaptor;
deba@416	1048	typedef GraphAdaptorBase<_Graph> Parent;
deba@416	1049	protected:
deba@416	1050	NodeFilterMap* _node_filter_map;
deba@416	1051	EdgeFilterMap* _edge_filter_map;
deba@416	1052	SubGraphBase() : Parent(),
deba@416	1053	_node_filter_map(0), _edge_filter_map(0) { }
deba@416	1054
deba@416	1055	void setNodeFilterMap(NodeFilterMap& node_filter_map) {
deba@416	1056	_node_filter_map=&node_filter_map;
deba@416	1057	}
deba@416	1058	void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
deba@416	1059	_edge_filter_map=&edge_filter_map;
deba@416	1060	}
deba@416	1061
deba@416	1062	public:
deba@416	1063
deba@416	1064	typedef typename Parent::Node Node;
deba@416	1065	typedef typename Parent::Arc Arc;
deba@416	1066	typedef typename Parent::Edge Edge;
deba@416	1067
deba@416	1068	void first(Node& i) const {
deba@416	1069	Parent::first(i);
deba@416	1070	while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416	1071	}
deba@416	1072
deba@416	1073	void first(Arc& i) const {
deba@416	1074	Parent::first(i);
deba@416	1075	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416	1076	}
deba@416	1077
deba@416	1078	void first(Edge& i) const {
deba@416	1079	Parent::first(i);
deba@416	1080	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416	1081	}
deba@416	1082
deba@416	1083	void firstIn(Arc& i, const Node& n) const {
deba@416	1084	Parent::firstIn(i, n);
deba@416	1085	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
deba@416	1086	}
deba@416	1087
deba@416	1088	void firstOut(Arc& i, const Node& n) const {
deba@416	1089	Parent::firstOut(i, n);
deba@416	1090	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
deba@416	1091	}
deba@416	1092
deba@416	1093	void firstInc(Edge& i, bool& d, const Node& n) const {
deba@416	1094	Parent::firstInc(i, d, n);
deba@416	1095	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
deba@416	1096	}
deba@416	1097
deba@416	1098	void next(Node& i) const {
deba@416	1099	Parent::next(i);
deba@416	1100	while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
deba@416	1101	}
deba@416	1102	void next(Arc& i) const {
deba@416	1103	Parent::next(i);
deba@416	1104	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416	1105	}
deba@416	1106	void next(Edge& i) const {
deba@416	1107	Parent::next(i);
deba@416	1108	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
deba@416	1109	}
deba@416	1110	void nextIn(Arc& i) const {
deba@416	1111	Parent::nextIn(i);
deba@416	1112	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
deba@416	1113	}
deba@416	1114
deba@416	1115	void nextOut(Arc& i) const {
deba@416	1116	Parent::nextOut(i);
deba@416	1117	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
deba@416	1118	}
deba@416	1119	void nextInc(Edge& i, bool& d) const {
deba@416	1120	Parent::nextInc(i, d);
deba@416	1121	while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
deba@416	1122	}
deba@416	1123
deba@416	1124	void hide(const Node& n) const { _node_filter_map->set(n, false); }
deba@416	1125	void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
deba@416	1126
deba@416	1127	void unHide(const Node& n) const { _node_filter_map->set(n, true); }
deba@416	1128	void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
deba@416	1129
deba@416	1130	bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
deba@416	1131	bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
deba@416	1132
deba@416	1133	typedef False NodeNumTag;
deba@416	1134	typedef False EdgeNumTag;
deba@416	1135
deba@416	1136	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416	1137	Arc findArc(const Node& u, const Node& v,
deba@416	1138	const Arc& prev = INVALID) {
deba@416	1139	Arc arc = Parent::findArc(u, v, prev);
deba@416	1140	while (arc != INVALID && !(*_edge_filter_map)[arc]) {
deba@416	1141	arc = Parent::findArc(u, v, arc);
deba@416	1142	}
deba@416	1143	return arc;
deba@416	1144	}
deba@416	1145	Edge findEdge(const Node& u, const Node& v,
deba@416	1146	const Edge& prev = INVALID) {
deba@416	1147	Edge edge = Parent::findEdge(u, v, prev);
deba@416	1148	while (edge != INVALID && !(*_edge_filter_map)[edge]) {
deba@416	1149	edge = Parent::findEdge(u, v, edge);
deba@416	1150	}
deba@416	1151	return edge;
deba@416	1152	}
deba@416	1153
deba@416	1154	template <typename _Value>
deba@416	1155	class NodeMap : public SubMapExtender<Adaptor,
deba@416	1156	typename Parent::template NodeMap<_Value> > {
deba@416	1157	public:
deba@416	1158	typedef _Value Value;
deba@416	1159	typedef SubMapExtender<Adaptor, typename Parent::
deba@416	1160	template NodeMap<Value> > MapParent;
deba@416	1161
deba@416	1162	NodeMap(const Adaptor& adaptor)
deba@416	1163	: MapParent(adaptor) {}
deba@416	1164	NodeMap(const Adaptor& adaptor, const Value& value)
deba@416	1165	: MapParent(adaptor, value) {}
deba@416	1166
deba@416	1167	private:
deba@416	1168	NodeMap& operator=(const NodeMap& cmap) {
deba@416	1169	return operator=<NodeMap>(cmap);
deba@416	1170	}
deba@416	1171
deba@416	1172	template <typename CMap>
deba@416	1173	NodeMap& operator=(const CMap& cmap) {
deba@416	1174	MapParent::operator=(cmap);
deba@416	1175	return *this;
deba@416	1176	}
deba@416	1177	};
deba@416	1178
deba@416	1179	template <typename _Value>
deba@416	1180	class ArcMap : public SubMapExtender<Adaptor,
deba@416	1181	typename Parent::template ArcMap<_Value> > {
deba@416	1182	public:
deba@416	1183	typedef _Value Value;
deba@416	1184	typedef SubMapExtender<Adaptor, typename Parent::
deba@416	1185	template ArcMap<Value> > MapParent;
deba@416	1186
deba@416	1187	ArcMap(const Adaptor& adaptor)
deba@416	1188	: MapParent(adaptor) {}
deba@416	1189	ArcMap(const Adaptor& adaptor, const Value& value)
deba@416	1190	: MapParent(adaptor, value) {}
deba@416	1191
deba@416	1192	private:
deba@416	1193	ArcMap& operator=(const ArcMap& cmap) {
deba@416	1194	return operator=<ArcMap>(cmap);
deba@416	1195	}
deba@416	1196
deba@416	1197	template <typename CMap>
deba@416	1198	ArcMap& operator=(const CMap& cmap) {
deba@416	1199	MapParent::operator=(cmap);
deba@416	1200	return *this;
deba@416	1201	}
deba@416	1202	};
deba@416	1203
deba@416	1204	template <typename _Value>
deba@416	1205	class EdgeMap : public SubMapExtender<Adaptor,
deba@416	1206	typename Parent::template EdgeMap<_Value> > {
deba@416	1207	public:
deba@416	1208	typedef _Value Value;
deba@416	1209	typedef SubMapExtender<Adaptor, typename Parent::
deba@416	1210	template EdgeMap<Value> > MapParent;
deba@416	1211
deba@416	1212	EdgeMap(const Adaptor& adaptor)
deba@416	1213	: MapParent(adaptor) {}
deba@416	1214
deba@416	1215	EdgeMap(const Adaptor& adaptor, const _Value& value)
deba@416	1216	: MapParent(adaptor, value) {}
deba@416	1217
deba@416	1218	private:
deba@416	1219	EdgeMap& operator=(const EdgeMap& cmap) {
deba@416	1220	return operator=<EdgeMap>(cmap);
deba@416	1221	}
deba@416	1222
deba@416	1223	template <typename CMap>
deba@416	1224	EdgeMap& operator=(const CMap& cmap) {
deba@416	1225	MapParent::operator=(cmap);
deba@416	1226	return *this;
deba@416	1227	}
deba@416	1228	};
deba@416	1229
deba@416	1230	};
deba@416	1231
deba@416	1232	/// \ingroup graph_adaptors
deba@414	1233	///
deba@416	1234	/// \brief A graph adaptor for hiding nodes and edges in an
deba@416	1235	/// undirected graph.
deba@414	1236	///
deba@416	1237	/// SubGraph hides nodes and edges in a graph. A bool node map and a
deba@416	1238	/// bool edge map must be specified, which define the filters for
deba@416	1239	/// nodes and edges. Just the nodes and edges with true value are
deba@416	1240	/// shown in the subgraph. The SubGraph is conform to the \ref
deba@416	1241	/// concepts::Graph "Graph concept". If the \c _checked parameter is
deba@416	1242	/// true, then the edges incident to filtered nodes are also
deba@416	1243	/// filtered out.
deba@416	1244	///
deba@416	1245	/// \tparam _Graph It must be conform to the \ref
deba@416	1246	/// concepts::Graph "Graph concept". The type can be specified
deba@416	1247	/// to const.
deba@416	1248	/// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
deba@416	1249	/// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
deba@416	1250	/// \tparam _checked If the parameter is false then the edge filtering
deba@416	1251	/// is not checked with respect to node filter. Otherwise, each edge
deba@416	1252	/// is automatically filtered, which is incident to a filtered node.
deba@416	1253	///
deba@416	1254	/// \see FilterNodes
deba@416	1255	/// \see FilterEdges
deba@416	1256	template<typename _Graph, typename NodeFilterMap,
deba@416	1257	typename EdgeFilterMap, bool _checked = true>
deba@416	1258	class SubGraph
deba@416	1259	: public GraphAdaptorExtender<
deba@416	1260	SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
deba@414	1261	public:
deba@416	1262	typedef _Graph Graph;
deba@416	1263	typedef GraphAdaptorExtender<
deba@416	1264	SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
deba@414	1265
deba@415	1266	typedef typename Parent::Node Node;
deba@416	1267	typedef typename Parent::Edge Edge;
deba@415	1268
deba@414	1269	protected:
deba@416	1270	SubGraph() { }
deba@414	1271	public:
deba@414	1272
deba@415	1273	/// \brief Constructor
deba@415	1274	///
deba@416	1275	/// Creates a subgraph for the given graph with given node and
deba@416	1276	/// edge map filters.
deba@416	1277	SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
deba@416	1278	EdgeFilterMap& edge_filter_map) {
deba@416	1279	setGraph(_graph);
deba@416	1280	setNodeFilterMap(node_filter_map);
deba@416	1281	setEdgeFilterMap(edge_filter_map);
deba@414	1282	}
deba@414	1283
deba@415	1284	/// \brief Hides the node of the graph
deba@415	1285	///
deba@416	1286	/// This function hides \c n in the graph, i.e. the iteration
deba@416	1287	/// jumps over it. This is done by simply setting the value of \c n
deba@415	1288	/// to be false in the corresponding node-map.
deba@415	1289	void hide(const Node& n) const { Parent::hide(n); }
deba@415	1290
deba@416	1291	/// \brief Hides the edge of the graph
deba@416	1292	///
deba@416	1293	/// This function hides \c e in the graph, i.e. the iteration
deba@416	1294	/// jumps over it. This is done by simply setting the value of \c e
deba@416	1295	/// to be false in the corresponding edge-map.
deba@416	1296	void hide(const Edge& e) const { Parent::hide(e); }
deba@416	1297
deba@415	1298	/// \brief Unhides the node of the graph
deba@415	1299	///
deba@416	1300	/// The value of \c n is set to be true in the node-map which stores
deba@416	1301	/// hide information. If \c n was hidden previuosly, then it is shown
deba@415	1302	/// again
deba@415	1303	void unHide(const Node& n) const { Parent::unHide(n); }
deba@415	1304
deba@416	1305	/// \brief Unhides the edge of the graph
deba@416	1306	///
deba@416	1307	/// The value of \c e is set to be true in the edge-map which stores
deba@416	1308	/// hide information. If \c e was hidden previuosly, then it is shown
deba@416	1309	/// again
deba@416	1310	void unHide(const Edge& e) const { Parent::unHide(e); }
deba@416	1311
deba@415	1312	/// \brief Returns true if \c n is hidden.
deba@415	1313	///
deba@415	1314	/// Returns true if \c n is hidden.
deba@415	1315	///
deba@415	1316	bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@415	1317
deba@416	1318	/// \brief Returns true if \c e is hidden.
deba@416	1319	///
deba@416	1320	/// Returns true if \c e is hidden.
deba@416	1321	///
deba@416	1322	bool hidden(const Edge& e) const { return Parent::hidden(e); }
deba@414	1323	};
deba@414	1324
deba@416	1325	/// \brief Just gives back a subgraph
deba@414	1326	///
deba@416	1327	/// Just gives back a subgraph
deba@416	1328	template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416	1329	SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
deba@416	1330	subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@416	1331	return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
deba@416	1332	}
deba@416	1333
deba@416	1334	template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416	1335	SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
deba@416	1336	subGraph(const Graph& graph,
deba@416	1337	const NodeFilterMap& nfm, ArcFilterMap& efm) {
deba@416	1338	return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
deba@416	1339	(graph, nfm, efm);
deba@416	1340	}
deba@416	1341
deba@416	1342	template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416	1343	SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
deba@416	1344	subGraph(const Graph& graph,
deba@416	1345	NodeFilterMap& nfm, const ArcFilterMap& efm) {
deba@416	1346	return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
deba@416	1347	(graph, nfm, efm);
deba@416	1348	}
deba@416	1349
deba@416	1350	template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
deba@416	1351	SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
deba@416	1352	subGraph(const Graph& graph,
deba@416	1353	const NodeFilterMap& nfm, const ArcFilterMap& efm) {
deba@416	1354	return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
deba@416	1355	(graph, nfm, efm);
deba@416	1356	}
deba@416	1357
deba@416	1358	/// \ingroup graph_adaptors
deba@416	1359	///
deba@416	1360	/// \brief An adaptor for hiding nodes from a digraph or a graph.
deba@416	1361	///
deba@416	1362	/// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
deba@416	1363	/// node map must be specified, which defines the filters for
deba@416	1364	/// nodes. Just the unfiltered nodes and the arcs or edges incident
deba@416	1365	/// to unfiltered nodes are shown in the subdigraph or subgraph. The
deba@416	1366	/// FilterNodes is conform to the \ref concepts::Digraph
deba@416	1367	/// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
deba@416	1368	/// on the \c _Digraph template parameter. If the \c _checked
deba@416	1369	/// parameter is true, then the arc or edges incident to filtered nodes
deba@416	1370	/// are also filtered out.
deba@416	1371	///
deba@416	1372	/// \tparam _Digraph It must be conform to the \ref
deba@416	1373	/// concepts::Digraph "Digraph concept" or \ref concepts::Graph
deba@416	1374	/// "Graph concept". The type can be specified to be const.
deba@416	1375	/// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
deba@416	1376	/// \tparam _checked If the parameter is false then the arc or edge
deba@416	1377	/// filtering is not checked with respect to node filter. In this
deba@416	1378	/// case just isolated nodes can be filtered out from the
deba@416	1379	/// graph.
deba@416	1380	#ifdef DOXYGEN
deba@416	1381	template<typename _Digraph,
deba@416	1382	typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
deba@416	1383	bool _checked = true>
deba@416	1384	#else
deba@416	1385	template<typename _Digraph,
deba@416	1386	typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
deba@416	1387	bool _checked = true,
deba@416	1388	typename Enable = void>
deba@416	1389	#endif
deba@416	1390	class FilterNodes
deba@416	1391	: public SubDigraph<_Digraph, _NodeFilterMap,
deba@416	1392	ConstMap<typename _Digraph::Arc, bool>, _checked> {
deba@416	1393	public:
deba@416	1394
deba@416	1395	typedef _Digraph Digraph;
deba@416	1396	typedef _NodeFilterMap NodeFilterMap;
deba@416	1397
deba@416	1398	typedef SubDigraph<Digraph, NodeFilterMap,
deba@416	1399	ConstMap<typename Digraph::Arc, bool>, _checked>
deba@416	1400	Parent;
deba@416	1401
deba@416	1402	typedef typename Parent::Node Node;
deba@416	1403
deba@416	1404	protected:
deba@416	1405	ConstMap<typename Digraph::Arc, bool> const_true_map;
deba@416	1406
deba@416	1407	FilterNodes() : const_true_map(true) {
deba@416	1408	Parent::setArcFilterMap(const_true_map);
deba@416	1409	}
deba@416	1410
deba@416	1411	public:
deba@416	1412
deba@416	1413	/// \brief Constructor
deba@416	1414	///
deba@416	1415	/// Creates an adaptor for the given digraph or graph with
deba@416	1416	/// given node filter map.
deba@416	1417	FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
deba@416	1418	Parent(), const_true_map(true) {
deba@416	1419	Parent::setDigraph(_digraph);
deba@416	1420	Parent::setNodeFilterMap(node_filter);
deba@416	1421	Parent::setArcFilterMap(const_true_map);
deba@416	1422	}
deba@416	1423
deba@416	1424	/// \brief Hides the node of the graph
deba@416	1425	///
deba@416	1426	/// This function hides \c n in the digraph or graph, i.e. the iteration
deba@416	1427	/// jumps over it. This is done by simply setting the value of \c n
deba@416	1428	/// to be false in the corresponding node map.
deba@416	1429	void hide(const Node& n) const { Parent::hide(n); }
deba@416	1430
deba@416	1431	/// \brief Unhides the node of the graph
deba@416	1432	///
deba@416	1433	/// The value of \c n is set to be true in the node-map which stores
deba@416	1434	/// hide information. If \c n was hidden previuosly, then it is shown
deba@416	1435	/// again
deba@416	1436	void unHide(const Node& n) const { Parent::unHide(n); }
deba@416	1437
deba@416	1438	/// \brief Returns true if \c n is hidden.
deba@416	1439	///
deba@416	1440	/// Returns true if \c n is hidden.
deba@416	1441	///
deba@416	1442	bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@416	1443
deba@416	1444	};
deba@416	1445
deba@416	1446	template<typename _Graph, typename _NodeFilterMap, bool _checked>
deba@416	1447	class FilterNodes<_Graph, _NodeFilterMap, _checked,
deba@416	1448	typename enable_if<UndirectedTagIndicator<_Graph> >::type>
deba@416	1449	: public SubGraph<_Graph, _NodeFilterMap,
deba@416	1450	ConstMap<typename _Graph::Edge, bool>, _checked> {
deba@416	1451	public:
deba@416	1452	typedef _Graph Graph;
deba@416	1453	typedef _NodeFilterMap NodeFilterMap;
deba@416	1454	typedef SubGraph<Graph, NodeFilterMap,
deba@416	1455	ConstMap<typename Graph::Edge, bool> > Parent;
deba@416	1456
deba@416	1457	typedef typename Parent::Node Node;
deba@416	1458	protected:
deba@416	1459	ConstMap<typename Graph::Edge, bool> const_true_map;
deba@416	1460
deba@416	1461	FilterNodes() : const_true_map(true) {
deba@416	1462	Parent::setEdgeFilterMap(const_true_map);
deba@416	1463	}
deba@416	1464
deba@416	1465	public:
deba@416	1466
deba@416	1467	FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
deba@416	1468	Parent(), const_true_map(true) {
deba@416	1469	Parent::setGraph(_graph);
deba@416	1470	Parent::setNodeFilterMap(node_filter_map);
deba@416	1471	Parent::setEdgeFilterMap(const_true_map);
deba@416	1472	}
deba@416	1473
deba@416	1474	void hide(const Node& n) const { Parent::hide(n); }
deba@416	1475	void unHide(const Node& n) const { Parent::unHide(n); }
deba@416	1476	bool hidden(const Node& n) const { return Parent::hidden(n); }
deba@416	1477
deba@416	1478	};
deba@416	1479
deba@416	1480
deba@416	1481	/// \brief Just gives back a FilterNodes adaptor
deba@416	1482	///
deba@416	1483	/// Just gives back a FilterNodes adaptor
deba@414	1484	template<typename Digraph, typename NodeFilterMap>
deba@416	1485	FilterNodes<const Digraph, NodeFilterMap>
deba@416	1486	filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
deba@416	1487	return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
deba@414	1488	}
deba@414	1489
deba@414	1490	template<typename Digraph, typename NodeFilterMap>
deba@416	1491	FilterNodes<const Digraph, const NodeFilterMap>
deba@416	1492	filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
deba@416	1493	return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
deba@414	1494	}
deba@414	1495
deba@416	1496	/// \ingroup graph_adaptors
deba@414	1497	///
deba@416	1498	/// \brief An adaptor for hiding arcs from a digraph.
deba@414	1499	///
deba@416	1500	/// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
deba@416	1501	/// be specified, which defines the filters for arcs. Just the
deba@416	1502	/// unfiltered arcs are shown in the subdigraph. The FilterArcs is
deba@416	1503	/// conform to the \ref concepts::Digraph "Digraph concept".
deba@414	1504	///
deba@416	1505	/// \tparam _Digraph It must be conform to the \ref concepts::Digraph
deba@416	1506	/// "Digraph concept". The type can be specified to be const.
deba@416	1507	/// \tparam _ArcFilterMap A bool valued arc map of the the adapted
deba@416	1508	/// graph.
deba@414	1509	template<typename _Digraph, typename _ArcFilterMap>
deba@416	1510	class FilterArcs :
deba@416	1511	public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
deba@416	1512	_ArcFilterMap, false> {
deba@414	1513	public:
deba@414	1514	typedef _Digraph Digraph;
deba@414	1515	typedef _ArcFilterMap ArcFilterMap;
deba@414	1516
deba@416	1517	typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
deba@416	1518	ArcFilterMap, false> Parent;
deba@415	1519
deba@415	1520	typedef typename Parent::Arc Arc;
deba@415	1521
deba@414	1522	protected:
deba@414	1523	ConstMap<typename Digraph::Node, bool> const_true_map;
deba@414	1524
deba@416	1525	FilterArcs() : const_true_map(true) {
deba@414	1526	Parent::setNodeFilterMap(const_true_map);
deba@414	1527	}
deba@414	1528
deba@414	1529	public:
deba@414	1530
deba@415	1531	/// \brief Constructor
deba@415	1532	///
deba@416	1533	/// Creates a FilterArcs adaptor for the given graph with
deba@415	1534	/// given arc map filter.
deba@416	1535	FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
deba@416	1536	: Parent(), const_true_map(true) {
deba@414	1537	Parent::setDigraph(digraph);
deba@414	1538	Parent::setNodeFilterMap(const_true_map);
deba@414	1539	Parent::setArcFilterMap(arc_filter);
deba@414	1540	}
deba@414	1541
deba@415	1542	/// \brief Hides the arc of the graph
deba@415	1543	///
deba@416	1544	/// This function hides \c a in the graph, i.e. the iteration
deba@415	1545	/// jumps over it. This is done by simply setting the value of \c a
deba@416	1546	/// to be false in the corresponding arc map.
deba@415	1547	void hide(const Arc& a) const { Parent::hide(a); }
deba@415	1548
deba@415	1549	/// \brief Unhides the arc of the graph
deba@415	1550	///
deba@416	1551	/// The value of \c a is set to be true in the arc-map which stores
deba@416	1552	/// hide information. If \c a was hidden previuosly, then it is shown
deba@415	1553	/// again
deba@415	1554	void unHide(const Arc& a) const { Parent::unHide(a); }
deba@415	1555
deba@415	1556	/// \brief Returns true if \c a is hidden.
deba@415	1557	///
deba@415	1558	/// Returns true if \c a is hidden.
deba@415	1559	///
deba@415	1560	bool hidden(const Arc& a) const { return Parent::hidden(a); }
deba@415	1561
deba@414	1562	};
deba@414	1563
deba@416	1564	/// \brief Just gives back an FilterArcs adaptor
deba@414	1565	///
deba@416	1566	/// Just gives back an FilterArcs adaptor
deba@414	1567	template<typename Digraph, typename ArcFilterMap>
deba@416	1568	FilterArcs<const Digraph, ArcFilterMap>
deba@416	1569	filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
deba@416	1570	return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
deba@414	1571	}
deba@414	1572
deba@414	1573	template<typename Digraph, typename ArcFilterMap>
deba@416	1574	FilterArcs<const Digraph, const ArcFilterMap>
deba@416	1575	filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
deba@416	1576	return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
deba@414	1577	}
deba@414	1578
deba@416	1579	/// \ingroup graph_adaptors
deba@416	1580	///
deba@416	1581	/// \brief An adaptor for hiding edges from a graph.
deba@416	1582	///
deba@416	1583	/// FilterEdges adaptor hides edges in a digraph. A bool edge map must
deba@416	1584	/// be specified, which defines the filters for edges. Just the
deba@416	1585	/// unfiltered edges are shown in the subdigraph. The FilterEdges is
deba@416	1586	/// conform to the \ref concepts::Graph "Graph concept".
deba@416	1587	///
deba@416	1588	/// \tparam _Graph It must be conform to the \ref concepts::Graph
deba@416	1589	/// "Graph concept". The type can be specified to be const.
deba@416	1590	/// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
deba@416	1591	/// graph.
deba@416	1592	template<typename _Graph, typename _EdgeFilterMap>
deba@416	1593	class FilterEdges :
deba@416	1594	public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
deba@416	1595	_EdgeFilterMap, false> {
deba@416	1596	public:
deba@416	1597	typedef _Graph Graph;
deba@416	1598	typedef _EdgeFilterMap EdgeFilterMap;
deba@416	1599	typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
deba@416	1600	EdgeFilterMap, false> Parent;
deba@416	1601	typedef typename Parent::Edge Edge;
deba@416	1602	protected:
deba@416	1603	ConstMap<typename Graph::Node, bool> const_true_map;
deba@416	1604
deba@416	1605	FilterEdges() : const_true_map(true) {
deba@416	1606	Parent::setNodeFilterMap(const_true_map);
deba@416	1607	}
deba@416	1608
deba@416	1609	public:
deba@416	1610
deba@416	1611	/// \brief Constructor
deba@416	1612	///
deba@416	1613	/// Creates a FilterEdges adaptor for the given graph with
deba@416	1614	/// given edge map filters.
deba@416	1615	FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
deba@416	1616	Parent(), const_true_map(true) {
deba@416	1617	Parent::setGraph(_graph);
deba@416	1618	Parent::setNodeFilterMap(const_true_map);
deba@416	1619	Parent::setEdgeFilterMap(edge_filter_map);
deba@416	1620	}
deba@416	1621
deba@416	1622	/// \brief Hides the edge of the graph
deba@416	1623	///
deba@416	1624	/// This function hides \c e in the graph, i.e. the iteration
deba@416	1625	/// jumps over it. This is done by simply setting the value of \c e
deba@416	1626	/// to be false in the corresponding edge-map.
deba@416	1627	void hide(const Edge& e) const { Parent::hide(e); }
deba@416	1628
deba@416	1629	/// \brief Unhides the edge of the graph
deba@416	1630	///
deba@416	1631	/// The value of \c e is set to be true in the edge-map which stores
deba@416	1632	/// hide information. If \c e was hidden previuosly, then it is shown
deba@416	1633	/// again
deba@416	1634	void unHide(const Edge& e) const { Parent::unHide(e); }
deba@416	1635
deba@416	1636	/// \brief Returns true if \c e is hidden.
deba@416	1637	///
deba@416	1638	/// Returns true if \c e is hidden.
deba@416	1639	///
deba@416	1640	bool hidden(const Edge& e) const { return Parent::hidden(e); }
deba@416	1641
deba@416	1642	};
deba@416	1643
deba@416	1644	/// \brief Just gives back a FilterEdges adaptor
deba@416	1645	///
deba@416	1646	/// Just gives back a FilterEdges adaptor
deba@416	1647	template<typename Graph, typename EdgeFilterMap>
deba@416	1648	FilterEdges<const Graph, EdgeFilterMap>
deba@416	1649	filterEdges(const Graph& graph, EdgeFilterMap& efm) {
deba@416	1650	return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
deba@416	1651	}
deba@416	1652
deba@416	1653	template<typename Graph, typename EdgeFilterMap>
deba@416	1654	FilterEdges<const Graph, const EdgeFilterMap>
deba@416	1655	filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
deba@416	1656	return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
deba@416	1657	}
deba@416	1658
deba@414	1659	template <typename _Digraph>
deba@416	1660	class UndirectorBase {
deba@414	1661	public:
deba@414	1662	typedef _Digraph Digraph;
deba@416	1663	typedef UndirectorBase Adaptor;
deba@414	1664
deba@414	1665	typedef True UndirectedTag;
deba@414	1666
deba@414	1667	typedef typename Digraph::Arc Edge;
deba@414	1668	typedef typename Digraph::Node Node;
deba@414	1669
deba@414	1670	class Arc : public Edge {
deba@416	1671	friend class UndirectorBase;
deba@414	1672	protected:
deba@414	1673	bool _forward;
deba@414	1674
deba@414	1675	Arc(const Edge& edge, bool forward) :
deba@414	1676	Edge(edge), _forward(forward) {}
deba@414	1677
deba@414	1678	public:
deba@414	1679	Arc() {}
deba@414	1680
deba@414	1681	Arc(Invalid) : Edge(INVALID), _forward(true) {}
deba@414	1682
deba@414	1683	bool operator==(const Arc &other) const {
deba@416	1684	return _forward == other._forward &&
deba@416	1685	static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
deba@414	1686	}
deba@414	1687	bool operator!=(const Arc &other) const {
deba@416	1688	return _forward != other._forward \|\|
deba@416	1689	static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
deba@414	1690	}
deba@414	1691	bool operator<(const Arc &other) const {
deba@416	1692	return _forward < other._forward \|\|
deba@416	1693	(_forward == other._forward &&
deba@416	1694	static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
deba@414	1695	}
deba@414	1696	};
deba@414	1697
deba@414	1698
deba@414	1699
deba@414	1700	void first(Node& n) const {
deba@414	1701	_digraph->first(n);
deba@414	1702	}
deba@414	1703
deba@414	1704	void next(Node& n) const {
deba@414	1705	_digraph->next(n);
deba@414	1706	}
deba@414	1707
deba@414	1708	void first(Arc& a) const {
deba@414	1709	_digraph->first(a);
deba@414	1710	a._forward = true;
deba@414	1711	}
deba@414	1712
deba@414	1713	void next(Arc& a) const {
deba@414	1714	if (a._forward) {
deba@416	1715	a._forward = false;
deba@414	1716	} else {
deba@416	1717	_digraph->next(a);
deba@416	1718	a._forward = true;
deba@414	1719	}
deba@414	1720	}
deba@414	1721
deba@414	1722	void first(Edge& e) const {
deba@414	1723	_digraph->first(e);
deba@414	1724	}
deba@414	1725
deba@414	1726	void next(Edge& e) const {
deba@414	1727	_digraph->next(e);
deba@414	1728	}
deba@414	1729
deba@414	1730	void firstOut(Arc& a, const Node& n) const {
deba@414	1731	_digraph->firstIn(a, n);
deba@414	1732	if( static_cast<const Edge&>(a) != INVALID ) {
deba@416	1733	a._forward = false;
deba@414	1734	} else {
deba@416	1735	_digraph->firstOut(a, n);
deba@416	1736	a._forward = true;
deba@414	1737	}
deba@414	1738	}
deba@414	1739	void nextOut(Arc &a) const {
deba@414	1740	if (!a._forward) {
deba@416	1741	Node n = _digraph->target(a);
deba@416	1742	_digraph->nextIn(a);
deba@416	1743	if (static_cast<const Edge&>(a) == INVALID ) {
deba@416	1744	_digraph->firstOut(a, n);
deba@416	1745	a._forward = true;
deba@416	1746	}
deba@414	1747	}
deba@414	1748	else {
deba@416	1749	_digraph->nextOut(a);
deba@414	1750	}
deba@414	1751	}
deba@414	1752
deba@414	1753	void firstIn(Arc &a, const Node &n) const {
deba@414	1754	_digraph->firstOut(a, n);
deba@414	1755	if (static_cast<const Edge&>(a) != INVALID ) {
deba@416	1756	a._forward = false;
deba@414	1757	} else {
deba@416	1758	_digraph->firstIn(a, n);
deba@416	1759	a._forward = true;
deba@414	1760	}
deba@414	1761	}
deba@414	1762	void nextIn(Arc &a) const {
deba@414	1763	if (!a._forward) {
deba@416	1764	Node n = _digraph->source(a);
deba@416	1765	_digraph->nextOut(a);
deba@416	1766	if( static_cast<const Edge&>(a) == INVALID ) {
deba@416	1767	_digraph->firstIn(a, n);
deba@416	1768	a._forward = true;
deba@416	1769	}
deba@414	1770	}
deba@414	1771	else {
deba@416	1772	_digraph->nextIn(a);
deba@414	1773	}
deba@414	1774	}
deba@414	1775
deba@414	1776	void firstInc(Edge &e, bool &d, const Node &n) const {
deba@414	1777	d = true;
deba@414	1778	_digraph->firstOut(e, n);
deba@414	1779	if (e != INVALID) return;
deba@414	1780	d = false;
deba@414	1781	_digraph->firstIn(e, n);
deba@414	1782	}
deba@414	1783
deba@414	1784	void nextInc(Edge &e, bool &d) const {
deba@414	1785	if (d) {
deba@416	1786	Node s = _digraph->source(e);
deba@416	1787	_digraph->nextOut(e);
deba@416	1788	if (e != INVALID) return;
deba@416	1789	d = false;
deba@416	1790	_digraph->firstIn(e, s);
deba@414	1791	} else {
deba@416	1792	_digraph->nextIn(e);
deba@414	1793	}
deba@414	1794	}
deba@414	1795
deba@414	1796	Node u(const Edge& e) const {
deba@414	1797	return _digraph->source(e);
deba@414	1798	}
deba@414	1799
deba@414	1800	Node v(const Edge& e) const {
deba@414	1801	return _digraph->target(e);
deba@414	1802	}
deba@414	1803
deba@414	1804	Node source(const Arc &a) const {
deba@414	1805	return a._forward ? _digraph->source(a) : _digraph->target(a);
deba@414	1806	}
deba@414	1807
deba@414	1808	Node target(const Arc &a) const {
deba@414	1809	return a._forward ? _digraph->target(a) : _digraph->source(a);
deba@414	1810	}
deba@414	1811
deba@414	1812	static Arc direct(const Edge &e, bool d) {
deba@414	1813	return Arc(e, d);
deba@414	1814	}
deba@414	1815	Arc direct(const Edge &e, const Node& n) const {
deba@414	1816	return Arc(e, _digraph->source(e) == n);
deba@414	1817	}
deba@414	1818
deba@414	1819	static bool direction(const Arc &a) { return a._forward; }
deba@414	1820
deba@414	1821	Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
deba@414	1822	Arc arcFromId(int ix) const {
deba@414	1823	return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
deba@414	1824	}
deba@414	1825	Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
deba@414	1826
deba@414	1827	int id(const Node &n) const { return _digraph->id(n); }
deba@414	1828	int id(const Arc &a) const {
deba@414	1829	return (_digraph->id(a) << 1) \| (a._forward ? 1 : 0);
deba@414	1830	}
deba@414	1831	int id(const Edge &e) const { return _digraph->id(e); }
deba@414	1832
deba@414	1833	int maxNodeId() const { return _digraph->maxNodeId(); }
deba@414	1834	int maxArcId() const { return (_digraph->maxArcId() << 1) \| 1; }
deba@414	1835	int maxEdgeId() const { return _digraph->maxArcId(); }
deba@414	1836
deba@414	1837	Node addNode() { return _digraph->addNode(); }
deba@416	1838	Edge addEdge(const Node& u, const Node& v) {
deba@416	1839	return _digraph->addArc(u, v);
deba@414	1840	}
deba@414	1841
deba@414	1842	void erase(const Node& i) { _digraph->erase(i); }
deba@414	1843	void erase(const Edge& i) { _digraph->erase(i); }
deba@416	1844
deba@414	1845	void clear() { _digraph->clear(); }
deba@414	1846
deba@414	1847	typedef NodeNumTagIndicator<Digraph> NodeNumTag;
deba@414	1848	int nodeNum() const { return 2 * _digraph->arcNum(); }
deba@414	1849	typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
deba@414	1850	int arcNum() const { return 2 * _digraph->arcNum(); }
deba@414	1851	int edgeNum() const { return _digraph->arcNum(); }
deba@414	1852
deba@414	1853	typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
deba@414	1854	Arc findArc(Node s, Node t, Arc p = INVALID) const {
deba@414	1855	if (p == INVALID) {
deba@416	1856	Edge arc = _digraph->findArc(s, t);
deba@416	1857	if (arc != INVALID) return direct(arc, true);
deba@416	1858	arc = _digraph->findArc(t, s);
deba@416	1859	if (arc != INVALID) return direct(arc, false);
deba@414	1860	} else if (direction(p)) {
deba@416	1861	Edge arc = _digraph->findArc(s, t, p);
deba@416	1862	if (arc != INVALID) return direct(arc, true);
deba@416	1863	arc = _digraph->findArc(t, s);
deba@416	1864	if (arc != INVALID) return direct(arc, false);
deba@414	1865	} else {
deba@416	1866	Edge arc = _digraph->findArc(t, s, p);
deba@416	1867	if (arc != INVALID) return direct(arc, false);
deba@414	1868	}
deba@414	1869	return INVALID;
deba@414	1870	}
deba@414	1871
deba@414	1872	Edge findEdge(Node s, Node t, Edge p = INVALID) const {
deba@414	1873	if (s != t) {
deba@414	1874	if (p == INVALID) {
deba@414	1875	Edge arc = _digraph->findArc(s, t);
deba@414	1876	if (arc != INVALID) return arc;
deba@414	1877	arc = _digraph->findArc(t, s);
deba@414	1878	if (arc != INVALID) return arc;
deba@414	1879	} else if (_digraph->s(p) == s) {
deba@414	1880	Edge arc = _digraph->findArc(s, t, p);
deba@414	1881	if (arc != INVALID) return arc;
deba@414	1882	arc = _digraph->findArc(t, s);
deba@416	1883	if (arc != INVALID) return arc;
deba@414	1884	} else {
deba@414	1885	Edge arc = _digraph->findArc(t, s, p);
deba@416	1886	if (arc != INVALID) return arc;
deba@414	1887	}
deba@414	1888	} else {
deba@414	1889	return _digraph->findArc(s, t, p);
deba@414	1890	}
deba@414	1891	return INVALID;
deba@414	1892	}
deba@414	1893
deba@414	1894	private:
deba@416	1895
deba@414	1896	template <typename _Value>
deba@414	1897	class ArcMapBase {
deba@414	1898	private:
deba@416	1899
deba@414	1900	typedef typename Digraph::template ArcMap<_Value> MapImpl;
deba@416	1901
deba@414	1902	public:
deba@414	1903
deba@414	1904	typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
deba@414	1905
deba@414	1906	typedef _Value Value;
deba@414	1907	typedef Arc Key;
deba@416	1908
deba@414	1909	ArcMapBase(const Adaptor& adaptor) :
deba@416	1910	_forward(adaptor._digraph), _backward(adaptor._digraph) {}
deba@416	1911
deba@416	1912	ArcMapBase(const Adaptor& adaptor, const Value& v)
deba@414	1913	: _forward(adaptor._digraph, v), _backward(adaptor._digraph, v) {}
deba@416	1914
deba@416	1915	void set(const Arc& a, const Value& v) {
deba@416	1916	if (direction(a)) {
deba@416	1917	_forward.set(a, v);
deba@416	1918	} else {
deba@416	1919	_backward.set(a, v);
deba@414	1920	}
deba@414	1921	}
deba@414	1922
deba@416	1923	typename MapTraits<MapImpl>::ConstReturnValue
deba@416	1924	operator[](const Arc& a) const {
deba@416	1925	if (direction(a)) {
deba@416	1926	return _forward[a];
deba@416	1927	} else {
deba@416	1928	return _backward[a];
deba@414	1929	}
deba@414	1930	}
deba@414	1931
deba@416	1932	typename MapTraits<MapImpl>::ReturnValue
deba@416	1933	operator[](const Arc& a) {
deba@416	1934	if (direction(a)) {
deba@416	1935	return _forward[a];
deba@416	1936	} else {
deba@416	1937	return _backward[a];
deba@416	1938	}
deba@416	1939	}
deba@416	1940
deba@414	1941	protected:
deba@414	1942
deba@416	1943	MapImpl _forward, _backward;
deba@414	1944
deba@414	1945	};
deba@414	1946
deba@414	1947	public:
deba@414	1948
deba@414	1949	template <typename _Value>
deba@414	1950	class NodeMap : public Digraph::template NodeMap<_Value> {
deba@414	1951	public:
deba@414	1952
deba@414	1953	typedef _Value Value;
deba@414	1954	typedef typename Digraph::template NodeMap<Value> Parent;
deba@414	1955
deba@416	1956	explicit NodeMap(const Adaptor& adaptor)
deba@416	1957	: Parent(*adaptor._digraph) {}
deba@414	1958
deba@414	1959	NodeMap(const Adaptor& adaptor, const _Value& value)
deba@416	1960	: Parent(*adaptor._digraph, value) { }
deba@414	1961
deba@414	1962	private:
deba@414	1963	NodeMap& operator=(const NodeMap& cmap) {
deba@414	1964	return operator=<NodeMap>(cmap);
deba@414	1965	}
deba@414	1966
deba@414	1967	template <typename CMap>
deba@414	1968	NodeMap& operator=(const CMap& cmap) {
deba@414	1969	Parent::operator=(cmap);
deba@414	1970	return *this;
deba@414	1971	}
deba@416	1972
deba@414	1973	};
deba@414	1974
deba@414	1975	template <typename _Value>
deba@416	1976	class ArcMap
deba@416	1977	: public SubMapExtender<Adaptor, ArcMapBase<_Value> >
deba@414	1978	{
deba@414	1979	public:
deba@414	1980	typedef _Value Value;
deba@414	1981	typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
deba@416	1982
deba@416	1983	ArcMap(const Adaptor& adaptor)
deba@416	1984	: Parent(adaptor) {}
deba@416	1985
deba@416	1986	ArcMap(const Adaptor& adaptor, const Value& value)
deba@416	1987	: Parent(adaptor, value) {}
deba@416	1988
deba@414	1989	private:
deba@414	1990	ArcMap& operator=(const ArcMap& cmap) {
deba@416	1991	return operator=<ArcMap>(cmap);
deba@414	1992	}
deba@416	1993
deba@414	1994	template <typename CMap>
deba@414	1995	ArcMap& operator=(const CMap& cmap) {
deba@414	1996	Parent::operator=(cmap);
deba@416	1997	return *this;
deba@414	1998	}
deba@414	1999	};
deba@416	2000
deba@414	2001	template <typename _Value>
deba@414	2002	class EdgeMap : public Digraph::template ArcMap<_Value> {
deba@414	2003	public:
deba@416	2004
deba@414	2005	typedef _Value Value;
deba@414	2006	typedef typename Digraph::template ArcMap<Value> Parent;
deba@416	2007
deba@416	2008	explicit EdgeMap(const Adaptor& adaptor)
deba@416	2009	: Parent(*adaptor._digraph) {}
deba@414	2010
deba@414	2011	EdgeMap(const Adaptor& adaptor, const Value& value)
deba@416	2012	: Parent(*adaptor._digraph, value) {}
deba@414	2013
deba@414	2014	private:
deba@414	2015	EdgeMap& operator=(const EdgeMap& cmap) {
deba@414	2016	return operator=<EdgeMap>(cmap);
deba@414	2017	}
deba@414	2018
deba@414	2019	template <typename CMap>
deba@414	2020	EdgeMap& operator=(const CMap& cmap) {
deba@414	2021	Parent::operator=(cmap);
deba@414	2022	return *this;
deba@414	2023	}
deba@414	2024
deba@414	2025	};
deba@414	2026
deba@414	2027	typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
deba@416	2028	NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
deba@414	2029
deba@414	2030	protected:
deba@414	2031
deba@416	2032	UndirectorBase() : _digraph(0) {}
deba@414	2033
deba@414	2034	Digraph* _digraph;
deba@414	2035
deba@414	2036	void setDigraph(Digraph& digraph) {
deba@414	2037	_digraph = &digraph;
deba@414	2038	}
deba@416	2039
deba@414	2040	};
deba@414	2041
deba@416	2042	/// \ingroup graph_adaptors
deba@414	2043	///
deba@416	2044	/// \brief Undirect the graph
deba@414	2045	///
deba@414	2046	/// This adaptor makes an undirected graph from a directed
deba@416	2047	/// graph. All arcs of the underlying digraph will be showed in the
deba@416	2048	/// adaptor as an edge. The Orienter adaptor is conform to the \ref
deba@416	2049	/// concepts::Graph "Graph concept".
deba@414	2050	///
deba@416	2051	/// \tparam _Digraph It must be conform to the \ref
deba@416	2052	/// concepts::Digraph "Digraph concept". The type can be specified
deba@416	2053	/// to const.
deba@414	2054	template<typename _Digraph>
deba@416	2055	class Undirector
deba@416	2056	: public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
deba@414	2057	public:
deba@414	2058	typedef _Digraph Digraph;
deba@416	2059	typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
deba@414	2060	protected:
deba@416	2061	Undirector() { }
deba@414	2062	public:
deba@414	2063
deba@414	2064	/// \brief Constructor
deba@414	2065	///
deba@416	2066	/// Creates a undirected graph from the given digraph
deba@416	2067	Undirector(_Digraph& digraph) {
deba@416	2068	setDigraph(digraph);
deba@414	2069	}
deba@414	2070
deba@414	2071	/// \brief ArcMap combined from two original ArcMap
deba@414	2072	///
deba@414	2073	/// This class adapts two original digraph ArcMap to
deba@416	2074	/// get an arc map on the undirected graph.
deba@414	2075	template <typename _ForwardMap, typename _BackwardMap>
deba@414	2076	class CombinedArcMap {
deba@414	2077	public:
deba@416	2078
deba@414	2079	typedef _ForwardMap ForwardMap;
deba@414	2080	typedef _BackwardMap BackwardMap;
deba@414	2081
deba@414	2082	typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
deba@414	2083
deba@414	2084	typedef typename ForwardMap::Value Value;
deba@414	2085	typedef typename Parent::Arc Key;
deba@414	2086
deba@416	2087	/// \brief Constructor
deba@414	2088	///
deba@416	2089	/// Constructor
deba@416	2090	CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
deba@414	2091	: _forward(&forward), _backward(&backward) {}
deba@416	2092
deba@414	2093
deba@414	2094	/// \brief Sets the value associated with a key.
deba@414	2095	///
deba@414	2096	/// Sets the value associated with a key.
deba@416	2097	void set(const Key& e, const Value& a) {
deba@416	2098	if (Parent::direction(e)) {
deba@416	2099	_forward->set(e, a);
deba@416	2100	} else {
deba@416	2101	_backward->set(e, a);
deba@416	2102	}
deba@414	2103	}
deba@414	2104
deba@414	2105	/// \brief Returns the value associated with a key.
deba@414	2106	///
deba@414	2107	/// Returns the value associated with a key.
deba@416	2108	typename MapTraits<ForwardMap>::ConstReturnValue
deba@416	2109	operator[](const Key& e) const {
deba@416	2110	if (Parent::direction(e)) {
deba@416	2111	return (*_forward)[e];
deba@416	2112	} else {
deba@416	2113	return (*_backward)[e];
deba@414	2114	}
deba@414	2115	}
deba@414	2116
deba@414	2117	/// \brief Returns the value associated with a key.
deba@414	2118	///
deba@414	2119	/// Returns the value associated with a key.
deba@416	2120	typename MapTraits<ForwardMap>::ReturnValue
deba@416	2121	operator[](const Key& e) {
deba@416	2122	if (Parent::direction(e)) {
deba@416	2123	return (*_forward)[e];
deba@416	2124	} else {
deba@416	2125	return (*_backward)[e];
deba@414	2126	}
deba@414	2127	}
deba@414	2128
deba@416	2129	protected:
deba@416	2130
deba@416	2131	ForwardMap* _forward;
deba@416	2132	BackwardMap* _backward;
deba@416	2133
deba@416	2134	};
deba@416	2135
deba@416	2136	/// \brief Just gives back a combined arc map
deba@416	2137	///
deba@416	2138	/// Just gives back a combined arc map
deba@416	2139	template <typename ForwardMap, typename BackwardMap>
deba@416	2140	static CombinedArcMap<ForwardMap, BackwardMap>
deba@416	2141	combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
deba@416	2142	return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
deba@416	2143	}
deba@416	2144
deba@416	2145	template <typename ForwardMap, typename BackwardMap>
deba@416	2146	static CombinedArcMap<const ForwardMap, BackwardMap>
deba@416	2147	combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
deba@416	2148	return CombinedArcMap<const ForwardMap,
deba@416	2149	BackwardMap>(forward, backward);
deba@416	2150	}
deba@416	2151
deba@416	2152	template <typename ForwardMap, typename BackwardMap>
deba@416	2153	static CombinedArcMap<ForwardMap, const BackwardMap>
deba@416	2154	combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
deba@416	2155	return CombinedArcMap<ForwardMap,
deba@416	2156	const BackwardMap>(forward, backward);
deba@416	2157	}
deba@416	2158
deba@416	2159	template <typename ForwardMap, typename BackwardMap>
deba@416	2160	static CombinedArcMap<const ForwardMap, const BackwardMap>
deba@416	2161	combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
deba@416	2162	return CombinedArcMap<const ForwardMap,
deba@416	2163	const BackwardMap>(forward, backward);
deba@416	2164	}
deba@416	2165
deba@416	2166	};
deba@416	2167
deba@416	2168	/// \brief Just gives back an undirected view of the given digraph
deba@416	2169	///
deba@416	2170	/// Just gives back an undirected view of the given digraph
deba@416	2171	template<typename Digraph>
deba@416	2172	Undirector<const Digraph>
deba@416	2173	undirector(const Digraph& digraph) {
deba@416	2174	return Undirector<const Digraph>(digraph);
deba@416	2175	}
deba@416	2176
deba@416	2177	template <typename _Graph, typename _DirectionMap>
deba@416	2178	class OrienterBase {
deba@416	2179	public:
deba@416	2180
deba@416	2181	typedef _Graph Graph;
deba@416	2182	typedef _DirectionMap DirectionMap;
deba@416	2183
deba@416	2184	typedef typename Graph::Node Node;
deba@416	2185	typedef typename Graph::Edge Arc;
deba@416	2186
deba@416	2187	void reverseArc(const Arc& arc) {
deba@416	2188	_direction->set(arc, !(*_direction)[arc]);
deba@416	2189	}
deba@416	2190
deba@416	2191	void first(Node& i) const { _graph->first(i); }
deba@416	2192	void first(Arc& i) const { _graph->first(i); }
deba@416	2193	void firstIn(Arc& i, const Node& n) const {
deba@416	2194	bool d;
deba@416	2195	_graph->firstInc(i, d, n);
deba@416	2196	while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2197	}
deba@416	2198	void firstOut(Arc& i, const Node& n ) const {
deba@416	2199	bool d;
deba@416	2200	_graph->firstInc(i, d, n);
deba@416	2201	while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2202	}
deba@416	2203
deba@416	2204	void next(Node& i) const { _graph->next(i); }
deba@416	2205	void next(Arc& i) const { _graph->next(i); }
deba@416	2206	void nextIn(Arc& i) const {
deba@416	2207	bool d = !(*_direction)[i];
deba@416	2208	_graph->nextInc(i, d);
deba@416	2209	while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2210	}
deba@416	2211	void nextOut(Arc& i) const {
deba@416	2212	bool d = (*_direction)[i];
deba@416	2213	_graph->nextInc(i, d);
deba@416	2214	while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2215	}
deba@416	2216
deba@416	2217	Node source(const Arc& e) const {
deba@416	2218	return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
deba@416	2219	}
deba@416	2220	Node target(const Arc& e) const {
deba@416	2221	return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
deba@416	2222	}
deba@416	2223
deba@416	2224	typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@416	2225	int nodeNum() const { return _graph->nodeNum(); }
deba@416	2226
deba@416	2227	typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@416	2228	int arcNum() const { return _graph->edgeNum(); }
deba@416	2229
deba@416	2230	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@416	2231	Arc findArc(const Node& u, const Node& v,
deba@416	2232	const Arc& prev = INVALID) {
deba@416	2233	Arc arc = prev;
deba@416	2234	bool d = arc == INVALID ? true : (*_direction)[arc];
deba@416	2235	if (d) {
deba@416	2236	arc = _graph->findEdge(u, v, arc);
deba@416	2237	while (arc != INVALID && !(*_direction)[arc]) {
deba@416	2238	_graph->findEdge(u, v, arc);
deba@416	2239	}
deba@416	2240	if (arc != INVALID) return arc;
deba@414	2241	}
deba@416	2242	_graph->findEdge(v, u, arc);
deba@416	2243	while (arc != INVALID && (*_direction)[arc]) {
deba@416	2244	_graph->findEdge(u, v, arc);
deba@414	2245	}
deba@416	2246	return arc;
deba@416	2247	}
deba@416	2248
deba@416	2249	Node addNode() {
deba@416	2250	return Node(_graph->addNode());
deba@416	2251	}
deba@416	2252
deba@416	2253	Arc addArc(const Node& u, const Node& v) {
deba@416	2254	Arc arc = _graph->addArc(u, v);
deba@416	2255	_direction->set(arc, _graph->source(arc) == u);
deba@416	2256	return arc;
deba@416	2257	}
deba@416	2258
deba@416	2259	void erase(const Node& i) { _graph->erase(i); }
deba@416	2260	void erase(const Arc& i) { _graph->erase(i); }
deba@416	2261
deba@416	2262	void clear() { _graph->clear(); }
deba@416	2263
deba@416	2264	int id(const Node& v) const { return _graph->id(v); }
deba@416	2265	int id(const Arc& e) const { return _graph->id(e); }
deba@416	2266
deba@416	2267	Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
deba@416	2268	Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
deba@416	2269
deba@416	2270	int maxNodeId() const { return _graph->maxNodeId(); }
deba@416	2271	int maxArcId() const { return _graph->maxEdgeId(); }
deba@416	2272
deba@416	2273	typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@416	2274	NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
deba@416	2275
deba@416	2276	typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
deba@416	2277	ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
deba@416	2278
deba@416	2279	template <typename _Value>
deba@416	2280	class NodeMap : public _Graph::template NodeMap<_Value> {
deba@416	2281	public:
deba@416	2282
deba@416	2283	typedef typename _Graph::template NodeMap<_Value> Parent;
deba@416	2284
deba@416	2285	explicit NodeMap(const OrienterBase& adapter)
deba@416	2286	: Parent(*adapter._graph) {}
deba@416	2287
deba@416	2288	NodeMap(const OrienterBase& adapter, const _Value& value)
deba@416	2289	: Parent(*adapter._graph, value) {}
deba@416	2290
deba@416	2291	private:
deba@416	2292	NodeMap& operator=(const NodeMap& cmap) {
deba@416	2293	return operator=<NodeMap>(cmap);
deba@416	2294	}
deba@416	2295
deba@416	2296	template <typename CMap>
deba@416	2297	NodeMap& operator=(const CMap& cmap) {
deba@416	2298	Parent::operator=(cmap);
deba@416	2299	return *this;
deba@416	2300	}
deba@414	2301
deba@414	2302	};
deba@414	2303
deba@416	2304	template <typename _Value>
deba@416	2305	class ArcMap : public _Graph::template EdgeMap<_Value> {
deba@416	2306	public:
deba@416	2307
deba@416	2308	typedef typename Graph::template EdgeMap<_Value> Parent;
deba@416	2309
deba@416	2310	explicit ArcMap(const OrienterBase& adapter)
deba@416	2311	: Parent(*adapter._graph) { }
deba@416	2312
deba@416	2313	ArcMap(const OrienterBase& adapter, const _Value& value)
deba@416	2314	: Parent(*adapter._graph, value) { }
deba@416	2315
deba@416	2316	private:
deba@416	2317	ArcMap& operator=(const ArcMap& cmap) {
deba@416	2318	return operator=<ArcMap>(cmap);
deba@416	2319	}
deba@416	2320
deba@416	2321	template <typename CMap>
deba@416	2322	ArcMap& operator=(const CMap& cmap) {
deba@416	2323	Parent::operator=(cmap);
deba@416	2324	return *this;
deba@416	2325	}
deba@416	2326	};
deba@416	2327
deba@416	2328
deba@416	2329
deba@416	2330	protected:
deba@416	2331	Graph* _graph;
deba@416	2332	DirectionMap* _direction;
deba@416	2333
deba@416	2334	void setDirectionMap(DirectionMap& direction) {
deba@416	2335	_direction = &direction;
deba@416	2336	}
deba@416	2337
deba@416	2338	void setGraph(Graph& graph) {
deba@416	2339	_graph = &graph;
deba@416	2340	}
deba@416	2341
deba@414	2342	};
deba@414	2343
deba@416	2344	/// \ingroup graph_adaptors
deba@414	2345	///
deba@416	2346	/// \brief Orients the edges of the graph to get a digraph
deba@416	2347	///
deba@416	2348	/// This adaptor orients each edge in the undirected graph. The
deba@416	2349	/// direction of the arcs stored in an edge node map. The arcs can
deba@416	2350	/// be easily reverted by the \c reverseArc() member function in the
deba@416	2351	/// adaptor. The Orienter adaptor is conform to the \ref
deba@416	2352	/// concepts::Digraph "Digraph concept".
deba@416	2353	///
deba@416	2354	/// \tparam _Graph It must be conform to the \ref concepts::Graph
deba@416	2355	/// "Graph concept". The type can be specified to be const.
deba@416	2356	/// \tparam _DirectionMap A bool valued edge map of the the adapted
deba@416	2357	/// graph.
deba@416	2358	///
deba@416	2359	/// \sa orienter
deba@416	2360	template<typename _Graph,
deba@416	2361	typename DirectionMap = typename _Graph::template EdgeMap<bool> >
deba@416	2362	class Orienter :
deba@416	2363	public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
deba@416	2364	public:
deba@416	2365	typedef _Graph Graph;
deba@416	2366	typedef DigraphAdaptorExtender<
deba@416	2367	OrienterBase<_Graph, DirectionMap> > Parent;
deba@416	2368	typedef typename Parent::Arc Arc;
deba@416	2369	protected:
deba@416	2370	Orienter() { }
deba@416	2371	public:
deba@416	2372
deba@416	2373	/// \brief Constructor of the adaptor
deba@416	2374	///
deba@416	2375	/// Constructor of the adaptor
deba@416	2376	Orienter(Graph& graph, DirectionMap& direction) {
deba@416	2377	setGraph(graph);
deba@416	2378	setDirectionMap(direction);
deba@416	2379	}
deba@416	2380
deba@416	2381	/// \brief Reverse arc
deba@416	2382	///
deba@416	2383	/// It reverse the given arc. It simply negate the direction in the map.
deba@416	2384	void reverseArc(const Arc& a) {
deba@416	2385	Parent::reverseArc(a);
deba@416	2386	}
deba@416	2387	};
deba@416	2388
deba@416	2389	/// \brief Just gives back a Orienter
deba@416	2390	///
deba@416	2391	/// Just gives back a Orienter
deba@416	2392	template<typename Graph, typename DirectionMap>
deba@416	2393	Orienter<const Graph, DirectionMap>
deba@416	2394	orienter(const Graph& graph, DirectionMap& dm) {
deba@416	2395	return Orienter<const Graph, DirectionMap>(graph, dm);
deba@414	2396	}
deba@414	2397
deba@416	2398	template<typename Graph, typename DirectionMap>
deba@416	2399	Orienter<const Graph, const DirectionMap>
deba@416	2400	orienter(const Graph& graph, const DirectionMap& dm) {
deba@416	2401	return Orienter<const Graph, const DirectionMap>(graph, dm);
deba@416	2402	}
deba@416	2403
deba@416	2404	namespace _adaptor_bits {
deba@416	2405
deba@416	2406	template<typename _Digraph,
deba@416	2407	typename _CapacityMap = typename _Digraph::template ArcMap<int>,
deba@416	2408	typename _FlowMap = _CapacityMap,
deba@416	2409	typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@416	2410	class ResForwardFilter {
deba@416	2411	public:
deba@416	2412
deba@416	2413	typedef _Digraph Digraph;
deba@416	2414	typedef _CapacityMap CapacityMap;
deba@416	2415	typedef _FlowMap FlowMap;
deba@416	2416	typedef _Tolerance Tolerance;
deba@416	2417
deba@416	2418	typedef typename Digraph::Arc Key;
deba@416	2419	typedef bool Value;
deba@416	2420
deba@416	2421	private:
deba@416	2422
deba@416	2423	const CapacityMap* _capacity;
deba@416	2424	const FlowMap* _flow;
deba@416	2425	Tolerance _tolerance;
deba@416	2426	public:
deba@416	2427
deba@416	2428	ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
deba@416	2429	const Tolerance& tolerance = Tolerance())
deba@416	2430	: _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416	2431
deba@416	2432	bool operator[](const typename Digraph::Arc& a) const {
deba@416	2433	return _tolerance.positive((_capacity)[a] - (_flow)[a]);
deba@416	2434	}
deba@416	2435	};
deba@416	2436
deba@416	2437	template<typename _Digraph,
deba@416	2438	typename _CapacityMap = typename _Digraph::template ArcMap<int>,
deba@416	2439	typename _FlowMap = _CapacityMap,
deba@416	2440	typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@416	2441	class ResBackwardFilter {
deba@416	2442	public:
deba@416	2443
deba@416	2444	typedef _Digraph Digraph;
deba@416	2445	typedef _CapacityMap CapacityMap;
deba@416	2446	typedef _FlowMap FlowMap;
deba@416	2447	typedef _Tolerance Tolerance;
deba@416	2448
deba@416	2449	typedef typename Digraph::Arc Key;
deba@416	2450	typedef bool Value;
deba@416	2451
deba@416	2452	private:
deba@416	2453
deba@416	2454	const CapacityMap* _capacity;
deba@416	2455	const FlowMap* _flow;
deba@416	2456	Tolerance _tolerance;
deba@416	2457
deba@416	2458	public:
deba@416	2459
deba@416	2460	ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
deba@416	2461	const Tolerance& tolerance = Tolerance())
deba@416	2462	: _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416	2463
deba@416	2464	bool operator[](const typename Digraph::Arc& a) const {
deba@416	2465	return _tolerance.positive((*_flow)[a]);
deba@416	2466	}
deba@416	2467	};
deba@416	2468
deba@416	2469	}
deba@416	2470
deba@416	2471	/// \ingroup graph_adaptors
deba@416	2472	///
deba@416	2473	/// \brief An adaptor for composing the residual graph for directed
deba@416	2474	/// flow and circulation problems.
deba@416	2475	///
deba@416	2476	/// An adaptor for composing the residual graph for directed flow and
deba@416	2477	/// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
deba@416	2478	/// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
deba@416	2479	/// be functions on the arc-set.
deba@416	2480	///
deba@416	2481	/// Then Residual implements the digraph structure with
deba@416	2482	/// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
deba@416	2483	/// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
deba@416	2484	/// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
deba@416	2485	/// called residual graph. When we take the union
deba@416	2486	/// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
deba@416	2487	/// i.e. if an arc is in both \f$ A_{forward} \f$ and
deba@416	2488	/// \f$ A_{backward} \f$, then in the adaptor it appears in both
deba@416	2489	/// orientation.
deba@416	2490	///
deba@416	2491	/// \tparam _Digraph It must be conform to the \ref concepts::Digraph
deba@416	2492	/// "Digraph concept". The type is implicitly const.
deba@416	2493	/// \tparam _CapacityMap An arc map of some numeric type, it defines
deba@416	2494	/// the capacities in the flow problem. The map is implicitly const.
deba@416	2495	/// \tparam _FlowMap An arc map of some numeric type, it defines
deba@416	2496	/// the capacities in the flow problem.
deba@416	2497	/// \tparam _Tolerance Handler for inexact computation.
deba@416	2498	template<typename _Digraph,
deba@416	2499	typename _CapacityMap = typename _Digraph::template ArcMap<int>,
deba@416	2500	typename _FlowMap = _CapacityMap,
deba@414	2501	typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@416	2502	class Residual :
deba@416	2503	public FilterArcs<
deba@416	2504	Undirector<const _Digraph>,
deba@416	2505	typename Undirector<const _Digraph>::template CombinedArcMap<
deba@416	2506	_adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
deba@416	2507	_FlowMap, _Tolerance>,
deba@416	2508	_adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
deba@416	2509	_FlowMap, _Tolerance> > >
deba@416	2510	{
deba@414	2511	public:
deba@414	2512
deba@414	2513	typedef _Digraph Digraph;
deba@414	2514	typedef _CapacityMap CapacityMap;
deba@414	2515	typedef _FlowMap FlowMap;
deba@414	2516	typedef _Tolerance Tolerance;
deba@414	2517
deba@414	2518	typedef typename CapacityMap::Value Value;
deba@416	2519	typedef Residual Adaptor;
deba@414	2520
deba@414	2521	protected:
deba@414	2522
deba@416	2523	typedef Undirector<const Digraph> Undirected;
deba@416	2524
deba@416	2525	typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
deba@416	2526	FlowMap, Tolerance> ForwardFilter;
deba@416	2527
deba@416	2528	typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
deba@416	2529	FlowMap, Tolerance> BackwardFilter;
deba@416	2530
deba@416	2531	typedef typename Undirected::
deba@414	2532	template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
deba@414	2533
deba@416	2534	typedef FilterArcs<Undirected, ArcFilter> Parent;
deba@414	2535
deba@414	2536	const CapacityMap* _capacity;
deba@414	2537	FlowMap* _flow;
deba@414	2538
deba@416	2539	Undirected _graph;
deba@414	2540	ForwardFilter _forward_filter;
deba@414	2541	BackwardFilter _backward_filter;
deba@414	2542	ArcFilter _arc_filter;
deba@414	2543
deba@414	2544	public:
deba@414	2545
deba@414	2546	/// \brief Constructor of the residual digraph.
deba@414	2547	///
deba@416	2548	/// Constructor of the residual graph. The parameters are the digraph,
deba@414	2549	/// the flow map, the capacity map and a tolerance object.
deba@416	2550	Residual(const Digraph& digraph, const CapacityMap& capacity,
deba@416	2551	FlowMap& flow, const Tolerance& tolerance = Tolerance())
deba@414	2552	: Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
deba@416	2553	_forward_filter(capacity, flow, tolerance),
deba@414	2554	_backward_filter(capacity, flow, tolerance),
deba@414	2555	_arc_filter(_forward_filter, _backward_filter)
deba@414	2556	{
deba@414	2557	Parent::setDigraph(_graph);
deba@414	2558	Parent::setArcFilterMap(_arc_filter);
deba@414	2559	}
deba@414	2560
deba@414	2561	typedef typename Parent::Arc Arc;
deba@414	2562
deba@414	2563	/// \brief Gives back the residual capacity of the arc.
deba@414	2564	///
deba@414	2565	/// Gives back the residual capacity of the arc.
deba@416	2566	Value residualCapacity(const Arc& a) const {
deba@416	2567	if (Undirected::direction(a)) {
deba@416	2568	return (_capacity)[a] - (_flow)[a];
deba@414	2569	} else {
deba@416	2570	return (*_flow)[a];
deba@414	2571	}
deba@416	2572	}
deba@416	2573
deba@416	2574	/// \brief Augment on the given arc in the residual graph.
deba@414	2575	///
deba@416	2576	/// Augment on the given arc in the residual graph. It increase
deba@414	2577	/// or decrease the flow on the original arc depend on the direction
deba@414	2578	/// of the residual arc.
deba@416	2579	void augment(const Arc& a, const Value& v) const {
deba@416	2580	if (Undirected::direction(a)) {
deba@416	2581	_flow->set(a, (*_flow)[a] + v);
deba@416	2582	} else {
deba@416	2583	_flow->set(a, (*_flow)[a] - v);
deba@414	2584	}
deba@414	2585	}
deba@414	2586
deba@414	2587	/// \brief Returns the direction of the arc.
deba@414	2588	///
deba@414	2589	/// Returns true when the arc is same oriented as the original arc.
deba@416	2590	static bool forward(const Arc& a) {
deba@416	2591	return Undirected::direction(a);
deba@414	2592	}
deba@414	2593
deba@414	2594	/// \brief Returns the direction of the arc.
deba@414	2595	///
deba@414	2596	/// Returns true when the arc is opposite oriented as the original arc.
deba@416	2597	static bool backward(const Arc& a) {
deba@416	2598	return !Undirected::direction(a);
deba@414	2599	}
deba@414	2600
deba@414	2601	/// \brief Gives back the forward oriented residual arc.
deba@414	2602	///
deba@414	2603	/// Gives back the forward oriented residual arc.
deba@416	2604	static Arc forward(const typename Digraph::Arc& a) {
deba@416	2605	return Undirected::direct(a, true);
deba@414	2606	}
deba@414	2607
deba@414	2608	/// \brief Gives back the backward oriented residual arc.
deba@414	2609	///
deba@414	2610	/// Gives back the backward oriented residual arc.
deba@416	2611	static Arc backward(const typename Digraph::Arc& a) {
deba@416	2612	return Undirected::direct(a, false);
deba@414	2613	}
deba@414	2614
deba@414	2615	/// \brief Residual capacity map.
deba@414	2616	///
deba@416	2617	/// In generic residual graph the residual capacity can be obtained
deba@416	2618	/// as a map.
deba@416	2619	class ResidualCapacity {
deba@414	2620	protected:
deba@414	2621	const Adaptor* _adaptor;
deba@414	2622	public:
deba@416	2623	/// The Key type
deba@414	2624	typedef Arc Key;
deba@416	2625	/// The Value type
deba@414	2626	typedef typename _CapacityMap::Value Value;
deba@414	2627
deba@416	2628	/// Constructor
deba@416	2629	ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
deba@416	2630
deba@416	2631	/// \e
deba@416	2632	Value operator[](const Arc& a) const {
deba@416	2633	return _adaptor->residualCapacity(a);
deba@414	2634	}
deba@416	2635
deba@414	2636	};
deba@414	2637
deba@414	2638	};
deba@414	2639
deba@414	2640	template <typename _Digraph>
deba@416	2641	class SplitNodesBase {
deba@414	2642	public:
deba@414	2643
deba@414	2644	typedef _Digraph Digraph;
deba@414	2645	typedef DigraphAdaptorBase<const _Digraph> Parent;
deba@416	2646	typedef SplitNodesBase Adaptor;
deba@414	2647
deba@414	2648	typedef typename Digraph::Node DigraphNode;
deba@414	2649	typedef typename Digraph::Arc DigraphArc;
deba@414	2650
deba@414	2651	class Node;
deba@414	2652	class Arc;
deba@414	2653
deba@414	2654	private:
deba@414	2655
deba@414	2656	template <typename T> class NodeMapBase;
deba@414	2657	template <typename T> class ArcMapBase;
deba@414	2658
deba@414	2659	public:
deba@416	2660
deba@414	2661	class Node : public DigraphNode {
deba@416	2662	friend class SplitNodesBase;
deba@414	2663	template <typename T> friend class NodeMapBase;
deba@414	2664	private:
deba@414	2665
deba@414	2666	bool _in;
deba@414	2667	Node(DigraphNode node, bool in)
deba@416	2668	: DigraphNode(node), _in(in) {}
deba@416	2669
deba@414	2670	public:
deba@414	2671
deba@414	2672	Node() {}
deba@414	2673	Node(Invalid) : DigraphNode(INVALID), _in(true) {}
deba@414	2674
deba@414	2675	bool operator==(const Node& node) const {
deba@416	2676	return DigraphNode::operator==(node) && _in == node._in;
deba@414	2677	}
deba@416	2678
deba@414	2679	bool operator!=(const Node& node) const {
deba@416	2680	return !(*this == node);
deba@414	2681	}
deba@416	2682
deba@414	2683	bool operator<(const Node& node) const {
deba@416	2684	return DigraphNode::operator<(node) \|\|
deba@416	2685	(DigraphNode::operator==(node) && _in < node._in);
deba@414	2686	}
deba@414	2687	};
deba@414	2688
deba@414	2689	class Arc {
deba@416	2690	friend class SplitNodesBase;
deba@414	2691	template <typename T> friend class ArcMapBase;
deba@414	2692	private:
deba@414	2693	typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
deba@414	2694
deba@414	2695	explicit Arc(const DigraphArc& arc) : _item(arc) {}
deba@414	2696	explicit Arc(const DigraphNode& node) : _item(node) {}
deba@416	2697
deba@414	2698	ArcImpl _item;
deba@414	2699
deba@414	2700	public:
deba@414	2701	Arc() {}
deba@414	2702	Arc(Invalid) : _item(DigraphArc(INVALID)) {}
deba@414	2703
deba@414	2704	bool operator==(const Arc& arc) const {
deba@414	2705	if (_item.firstState()) {
deba@414	2706	if (arc._item.firstState()) {
deba@414	2707	return _item.first() == arc._item.first();
deba@414	2708	}
deba@414	2709	} else {
deba@414	2710	if (arc._item.secondState()) {
deba@414	2711	return _item.second() == arc._item.second();
deba@414	2712	}
deba@414	2713	}
deba@414	2714	return false;
deba@414	2715	}
deba@416	2716
deba@414	2717	bool operator!=(const Arc& arc) const {
deba@416	2718	return !(*this == arc);
deba@414	2719	}
deba@416	2720
deba@414	2721	bool operator<(const Arc& arc) const {
deba@414	2722	if (_item.firstState()) {
deba@414	2723	if (arc._item.firstState()) {
deba@414	2724	return _item.first() < arc._item.first();
deba@414	2725	}
deba@414	2726	return false;
deba@414	2727	} else {
deba@414	2728	if (arc._item.secondState()) {
deba@414	2729	return _item.second() < arc._item.second();
deba@414	2730	}
deba@414	2731	return true;
deba@414	2732	}
deba@414	2733	}
deba@414	2734
deba@414	2735	operator DigraphArc() const { return _item.first(); }
deba@414	2736	operator DigraphNode() const { return _item.second(); }
deba@414	2737
deba@414	2738	};
deba@414	2739
deba@414	2740	void first(Node& n) const {
deba@414	2741	_digraph->first(n);
deba@414	2742	n._in = true;
deba@414	2743	}
deba@414	2744
deba@414	2745	void next(Node& n) const {
deba@414	2746	if (n._in) {
deba@416	2747	n._in = false;
deba@414	2748	} else {
deba@416	2749	n._in = true;
deba@416	2750	_digraph->next(n);
deba@414	2751	}
deba@414	2752	}
deba@414	2753
deba@414	2754	void first(Arc& e) const {
deba@414	2755	e._item.setSecond();
deba@414	2756	_digraph->first(e._item.second());
deba@414	2757	if (e._item.second() == INVALID) {
deba@414	2758	e._item.setFirst();
deba@416	2759	_digraph->first(e._item.first());
deba@414	2760	}
deba@414	2761	}
deba@414	2762
deba@414	2763	void next(Arc& e) const {
deba@414	2764	if (e._item.secondState()) {
deba@416	2765	_digraph->next(e._item.second());
deba@414	2766	if (e._item.second() == INVALID) {
deba@414	2767	e._item.setFirst();
deba@414	2768	_digraph->first(e._item.first());
deba@414	2769	}
deba@414	2770	} else {
deba@416	2771	_digraph->next(e._item.first());
deba@416	2772	}
deba@414	2773	}
deba@414	2774
deba@414	2775	void firstOut(Arc& e, const Node& n) const {
deba@414	2776	if (n._in) {
deba@414	2777	e._item.setSecond(n);
deba@414	2778	} else {
deba@414	2779	e._item.setFirst();
deba@416	2780	_digraph->firstOut(e._item.first(), n);
deba@414	2781	}
deba@414	2782	}
deba@414	2783
deba@414	2784	void nextOut(Arc& e) const {
deba@414	2785	if (!e._item.firstState()) {
deba@416	2786	e._item.setFirst(INVALID);
deba@414	2787	} else {
deba@416	2788	_digraph->nextOut(e._item.first());
deba@416	2789	}
deba@414	2790	}
deba@414	2791
deba@414	2792	void firstIn(Arc& e, const Node& n) const {
deba@414	2793	if (!n._in) {
deba@416	2794	e._item.setSecond(n);
deba@414	2795	} else {
deba@414	2796	e._item.setFirst();
deba@416	2797	_digraph->firstIn(e._item.first(), n);
deba@414	2798	}
deba@414	2799	}
deba@414	2800
deba@414	2801	void nextIn(Arc& e) const {
deba@414	2802	if (!e._item.firstState()) {
deba@416	2803	e._item.setFirst(INVALID);
deba@414	2804	} else {
deba@416	2805	_digraph->nextIn(e._item.first());
deba@414	2806	}
deba@414	2807	}
deba@414	2808
deba@414	2809	Node source(const Arc& e) const {
deba@414	2810	if (e._item.firstState()) {
deba@416	2811	return Node(_digraph->source(e._item.first()), false);
deba@414	2812	} else {
deba@416	2813	return Node(e._item.second(), true);
deba@414	2814	}
deba@414	2815	}
deba@414	2816
deba@414	2817	Node target(const Arc& e) const {
deba@414	2818	if (e._item.firstState()) {
deba@416	2819	return Node(_digraph->target(e._item.first()), true);
deba@414	2820	} else {
deba@416	2821	return Node(e._item.second(), false);
deba@414	2822	}
deba@414	2823	}
deba@414	2824
deba@414	2825	int id(const Node& n) const {
deba@414	2826	return (_digraph->id(n) << 1) \| (n._in ? 0 : 1);
deba@414	2827	}
deba@414	2828	Node nodeFromId(int ix) const {
deba@414	2829	return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
deba@414	2830	}
deba@414	2831	int maxNodeId() const {
deba@414	2832	return 2 * _digraph->maxNodeId() + 1;
deba@414	2833	}
deba@414	2834
deba@414	2835	int id(const Arc& e) const {
deba@414	2836	if (e._item.firstState()) {
deba@414	2837	return _digraph->id(e._item.first()) << 1;
deba@414	2838	} else {
deba@414	2839	return (_digraph->id(e._item.second()) << 1) \| 1;
deba@414	2840	}
deba@414	2841	}
deba@414	2842	Arc arcFromId(int ix) const {
deba@414	2843	if ((ix & 1) == 0) {
deba@414	2844	return Arc(_digraph->arcFromId(ix >> 1));
deba@414	2845	} else {
deba@414	2846	return Arc(_digraph->nodeFromId(ix >> 1));
deba@414	2847	}
deba@414	2848	}
deba@414	2849	int maxArcId() const {
deba@416	2850	return std::max(_digraph->maxNodeId() << 1,
deba@414	2851	(_digraph->maxArcId() << 1) \| 1);
deba@414	2852	}
deba@414	2853
deba@414	2854	static bool inNode(const Node& n) {
deba@414	2855	return n._in;
deba@414	2856	}
deba@414	2857
deba@414	2858	static bool outNode(const Node& n) {
deba@414	2859	return !n._in;
deba@414	2860	}
deba@414	2861
deba@414	2862	static bool origArc(const Arc& e) {
deba@414	2863	return e._item.firstState();
deba@414	2864	}
deba@414	2865
deba@414	2866	static bool bindArc(const Arc& e) {
deba@414	2867	return e._item.secondState();
deba@414	2868	}
deba@414	2869
deba@414	2870	static Node inNode(const DigraphNode& n) {
deba@414	2871	return Node(n, true);
deba@414	2872	}
deba@414	2873
deba@414	2874	static Node outNode(const DigraphNode& n) {
deba@414	2875	return Node(n, false);
deba@414	2876	}
deba@414	2877
deba@414	2878	static Arc arc(const DigraphNode& n) {
deba@414	2879	return Arc(n);
deba@414	2880	}
deba@414	2881
deba@414	2882	static Arc arc(const DigraphArc& e) {
deba@414	2883	return Arc(e);
deba@414	2884	}
deba@414	2885
deba@414	2886	typedef True NodeNumTag;
deba@414	2887
deba@414	2888	int nodeNum() const {
deba@414	2889	return 2 * countNodes(*_digraph);
deba@414	2890	}
deba@414	2891
deba@414	2892	typedef True EdgeNumTag;
deba@414	2893	int arcNum() const {
deba@414	2894	return countArcs(_digraph) + countNodes(_digraph);
deba@414	2895	}
deba@414	2896
deba@414	2897	typedef True FindEdgeTag;
deba@416	2898	Arc findArc(const Node& u, const Node& v,
deba@416	2899	const Arc& prev = INVALID) const {
deba@414	2900	if (inNode(u)) {
deba@414	2901	if (outNode(v)) {
deba@416	2902	if (static_cast<const DigraphNode&>(u) ==
deba@414	2903	static_cast<const DigraphNode&>(v) && prev == INVALID) {
deba@414	2904	return Arc(u);
deba@414	2905	}
deba@414	2906	}
deba@414	2907	} else {
deba@414	2908	if (inNode(v)) {
deba@414	2909	return Arc(::lemon::findArc(*_digraph, u, v, prev));
deba@414	2910	}
deba@414	2911	}
deba@414	2912	return INVALID;
deba@414	2913	}
deba@414	2914
deba@414	2915	private:
deba@416	2916
deba@414	2917	template <typename _Value>
deba@416	2918	class NodeMapBase
deba@414	2919	: public MapTraits<typename Parent::template NodeMap<_Value> > {
deba@414	2920	typedef typename Parent::template NodeMap<_Value> NodeImpl;
deba@414	2921	public:
deba@414	2922	typedef Node Key;
deba@414	2923	typedef _Value Value;
deba@416	2924
deba@416	2925	NodeMapBase(const Adaptor& adaptor)
deba@416	2926	: _in_map(adaptor._digraph), _out_map(adaptor._digraph) {}
deba@416	2927	NodeMapBase(const Adaptor& adaptor, const Value& value)
deba@416	2928	: _in_map(*adaptor._digraph, value),
deba@416	2929	_out_map(*adaptor._digraph, value) {}
deba@414	2930
deba@414	2931	void set(const Node& key, const Value& val) {
deba@416	2932	if (Adaptor::inNode(key)) { _in_map.set(key, val); }
deba@416	2933	else {_out_map.set(key, val); }
deba@414	2934	}
deba@416	2935
deba@416	2936	typename MapTraits<NodeImpl>::ReturnValue
deba@414	2937	operator[](const Node& key) {
deba@416	2938	if (Adaptor::inNode(key)) { return _in_map[key]; }
deba@416	2939	else { return _out_map[key]; }
deba@414	2940	}
deba@414	2941
deba@414	2942	typename MapTraits<NodeImpl>::ConstReturnValue
deba@414	2943	operator[](const Node& key) const {
deba@416	2944	if (Adaptor::inNode(key)) { return _in_map[key]; }
deba@416	2945	else { return _out_map[key]; }
deba@414	2946	}
deba@414	2947
deba@414	2948	private:
deba@414	2949	NodeImpl _in_map, _out_map;
deba@414	2950	};
deba@414	2951
deba@414	2952	template <typename _Value>
deba@416	2953	class ArcMapBase
deba@414	2954	: public MapTraits<typename Parent::template ArcMap<_Value> > {
deba@414	2955	typedef typename Parent::template ArcMap<_Value> ArcImpl;
deba@414	2956	typedef typename Parent::template NodeMap<_Value> NodeImpl;
deba@414	2957	public:
deba@414	2958	typedef Arc Key;
deba@414	2959	typedef _Value Value;
deba@414	2960
deba@416	2961	ArcMapBase(const Adaptor& adaptor)
deba@416	2962	: _arc_map(adaptor._digraph), _node_map(adaptor._digraph) {}
deba@416	2963	ArcMapBase(const Adaptor& adaptor, const Value& value)
deba@416	2964	: _arc_map(*adaptor._digraph, value),
deba@416	2965	_node_map(*adaptor._digraph, value) {}
deba@414	2966
deba@414	2967	void set(const Arc& key, const Value& val) {
deba@416	2968	if (Adaptor::origArc(key)) {
deba@416	2969	_arc_map.set(key._item.first(), val);
deba@414	2970	} else {
deba@416	2971	_node_map.set(key._item.second(), val);
deba@414	2972	}
deba@414	2973	}
deba@416	2974
deba@414	2975	typename MapTraits<ArcImpl>::ReturnValue
deba@414	2976	operator[](const Arc& key) {
deba@416	2977	if (Adaptor::origArc(key)) {
deba@414	2978	return _arc_map[key._item.first()];
deba@414	2979	} else {
deba@414	2980	return _node_map[key._item.second()];
deba@414	2981	}
deba@414	2982	}
deba@414	2983
deba@414	2984	typename MapTraits<ArcImpl>::ConstReturnValue
deba@414	2985	operator[](const Arc& key) const {
deba@416	2986	if (Adaptor::origArc(key)) {
deba@414	2987	return _arc_map[key._item.first()];
deba@414	2988	} else {
deba@414	2989	return _node_map[key._item.second()];
deba@414	2990	}
deba@414	2991	}
deba@414	2992
deba@414	2993	private:
deba@414	2994	ArcImpl _arc_map;
deba@414	2995	NodeImpl _node_map;
deba@414	2996	};
deba@414	2997
deba@414	2998	public:
deba@414	2999
deba@414	3000	template <typename _Value>
deba@416	3001	class NodeMap
deba@416	3002	: public SubMapExtender<Adaptor, NodeMapBase<_Value> >
deba@414	3003	{
deba@414	3004	public:
deba@414	3005	typedef _Value Value;
deba@414	3006	typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
deba@416	3007
deba@416	3008	NodeMap(const Adaptor& adaptor)
deba@416	3009	: Parent(adaptor) {}
deba@416	3010
deba@416	3011	NodeMap(const Adaptor& adaptor, const Value& value)
deba@416	3012	: Parent(adaptor, value) {}
deba@416	3013
deba@414	3014	private:
deba@414	3015	NodeMap& operator=(const NodeMap& cmap) {
deba@416	3016	return operator=<NodeMap>(cmap);
deba@414	3017	}
deba@416	3018
deba@414	3019	template <typename CMap>
deba@414	3020	NodeMap& operator=(const CMap& cmap) {
deba@414	3021	Parent::operator=(cmap);
deba@416	3022	return *this;
deba@414	3023	}
deba@414	3024	};
deba@414	3025
deba@414	3026	template <typename _Value>
deba@416	3027	class ArcMap
deba@416	3028	: public SubMapExtender<Adaptor, ArcMapBase<_Value> >
deba@414	3029	{
deba@414	3030	public:
deba@414	3031	typedef _Value Value;
deba@414	3032	typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
deba@416	3033
deba@416	3034	ArcMap(const Adaptor& adaptor)
deba@416	3035	: Parent(adaptor) {}
deba@416	3036
deba@416	3037	ArcMap(const Adaptor& adaptor, const Value& value)
deba@416	3038	: Parent(adaptor, value) {}
deba@416	3039
deba@414	3040	private:
deba@414	3041	ArcMap& operator=(const ArcMap& cmap) {
deba@416	3042	return operator=<ArcMap>(cmap);
deba@414	3043	}
deba@416	3044
deba@414	3045	template <typename CMap>
deba@414	3046	ArcMap& operator=(const CMap& cmap) {
deba@414	3047	Parent::operator=(cmap);
deba@416	3048	return *this;
deba@414	3049	}
deba@414	3050	};
deba@414	3051
deba@414	3052	protected:
deba@414	3053
deba@416	3054	SplitNodesBase() : _digraph(0) {}
deba@414	3055
deba@414	3056	Digraph* _digraph;
deba@414	3057
deba@414	3058	void setDigraph(Digraph& digraph) {
deba@414	3059	_digraph = &digraph;
deba@414	3060	}
deba@416	3061
deba@414	3062	};
deba@414	3063
deba@414	3064	/// \ingroup graph_adaptors
deba@414	3065	///
deba@416	3066	/// \brief Split the nodes of a directed graph
deba@416	3067	///
deba@416	3068	/// The SplitNodes adaptor splits each node into an in-node and an
deba@416	3069	/// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
deba@416	3070	/// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
deba@416	3071	/// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
deba@416	3072	/// original digraph the new target of the arc will be \f$ u_{in} \f$
deba@416	3073	/// and similarly the source of the original \f$ (u, v) \f$ arc
deba@416	3074	/// will be \f$ u_{out} \f$. The adaptor will add for each node in
deba@416	3075	/// the original digraph an additional arc which connects
deba@414	3076	/// \f$ (u_{in}, u_{out}) \f$.
deba@414	3077	///
deba@416	3078	/// The aim of this class is to run algorithm with node costs if the
deba@414	3079	/// algorithm can use directly just arc costs. In this case we should use
deba@416	3080	/// a \c SplitNodes and set the node cost of the graph to the
deba@416	3081	/// bind arc in the adapted graph.
deba@414	3082	///
deba@416	3083	/// \tparam _Digraph It must be conform to the \ref concepts::Digraph
deba@416	3084	/// "Digraph concept". The type can be specified to be const.
deba@414	3085	template <typename _Digraph>
deba@416	3086	class SplitNodes
deba@416	3087	: public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
deba@414	3088	public:
deba@414	3089	typedef _Digraph Digraph;
deba@416	3090	typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
deba@414	3091
deba@415	3092	typedef typename Digraph::Node DigraphNode;
deba@415	3093	typedef typename Digraph::Arc DigraphArc;
deba@415	3094
deba@414	3095	typedef typename Parent::Node Node;
deba@414	3096	typedef typename Parent::Arc Arc;
deba@414	3097
deba@414	3098	/// \brief Constructor of the adaptor.
deba@414	3099	///
deba@414	3100	/// Constructor of the adaptor.
deba@416	3101	SplitNodes(Digraph& g) {
deba@414	3102	Parent::setDigraph(g);
deba@414	3103	}
deba@414	3104
deba@415	3105	/// \brief Returns true when the node is in-node.
deba@415	3106	///
deba@415	3107	/// Returns true when the node is in-node.
deba@415	3108	static bool inNode(const Node& n) {
deba@415	3109	return Parent::inNode(n);
deba@415	3110	}
deba@415	3111
deba@415	3112	/// \brief Returns true when the node is out-node.
deba@415	3113	///
deba@415	3114	/// Returns true when the node is out-node.
deba@415	3115	static bool outNode(const Node& n) {
deba@415	3116	return Parent::outNode(n);
deba@415	3117	}
deba@415	3118
deba@415	3119	/// \brief Returns true when the arc is arc in the original digraph.
deba@415	3120	///
deba@415	3121	/// Returns true when the arc is arc in the original digraph.
deba@415	3122	static bool origArc(const Arc& a) {
deba@415	3123	return Parent::origArc(a);
deba@415	3124	}
deba@415	3125
deba@415	3126	/// \brief Returns true when the arc binds an in-node and an out-node.
deba@415	3127	///
deba@415	3128	/// Returns true when the arc binds an in-node and an out-node.
deba@415	3129	static bool bindArc(const Arc& a) {
deba@415	3130	return Parent::bindArc(a);
deba@415	3131	}
deba@415	3132
deba@415	3133	/// \brief Gives back the in-node created from the \c node.
deba@415	3134	///
deba@415	3135	/// Gives back the in-node created from the \c node.
deba@415	3136	static Node inNode(const DigraphNode& n) {
deba@415	3137	return Parent::inNode(n);
deba@415	3138	}
deba@415	3139
deba@415	3140	/// \brief Gives back the out-node created from the \c node.
deba@415	3141	///
deba@415	3142	/// Gives back the out-node created from the \c node.
deba@415	3143	static Node outNode(const DigraphNode& n) {
deba@415	3144	return Parent::outNode(n);
deba@415	3145	}
deba@415	3146
deba@415	3147	/// \brief Gives back the arc binds the two part of the node.
deba@416	3148	///
deba@415	3149	/// Gives back the arc binds the two part of the node.
deba@415	3150	static Arc arc(const DigraphNode& n) {
deba@415	3151	return Parent::arc(n);
deba@415	3152	}
deba@415	3153
deba@415	3154	/// \brief Gives back the arc of the original arc.
deba@416	3155	///
deba@415	3156	/// Gives back the arc of the original arc.
deba@415	3157	static Arc arc(const DigraphArc& a) {
deba@415	3158	return Parent::arc(a);
deba@415	3159	}
deba@415	3160
deba@414	3161	/// \brief NodeMap combined from two original NodeMap
deba@414	3162	///
deba@414	3163	/// This class adapt two of the original digraph NodeMap to
deba@414	3164	/// get a node map on the adapted digraph.
deba@414	3165	template <typename InNodeMap, typename OutNodeMap>
deba@414	3166	class CombinedNodeMap {
deba@414	3167	public:
deba@414	3168
deba@414	3169	typedef Node Key;
deba@414	3170	typedef typename InNodeMap::Value Value;
deba@414	3171
deba@414	3172	/// \brief Constructor
deba@414	3173	///
deba@414	3174	/// Constructor.
deba@416	3175	CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
deba@416	3176	: _in_map(in_map), _out_map(out_map) {}
deba@414	3177
deba@414	3178	/// \brief The subscript operator.
deba@414	3179	///
deba@414	3180	/// The subscript operator.
deba@414	3181	Value& operator[](const Key& key) {
deba@416	3182	if (Parent::inNode(key)) {
deba@416	3183	return _in_map[key];
deba@416	3184	} else {
deba@416	3185	return _out_map[key];
deba@416	3186	}
deba@414	3187	}
deba@414	3188
deba@414	3189	/// \brief The const subscript operator.
deba@414	3190	///
deba@414	3191	/// The const subscript operator.
deba@414	3192	Value operator[](const Key& key) const {
deba@416	3193	if (Parent::inNode(key)) {
deba@416	3194	return _in_map[key];
deba@416	3195	} else {
deba@416	3196	return _out_map[key];
deba@416	3197	}
deba@414	3198	}
deba@414	3199
deba@414	3200	/// \brief The setter function of the map.
deba@416	3201	///
deba@414	3202	/// The setter function of the map.
deba@414	3203	void set(const Key& key, const Value& value) {
deba@416	3204	if (Parent::inNode(key)) {
deba@416	3205	_in_map.set(key, value);
deba@416	3206	} else {
deba@416	3207	_out_map.set(key, value);
deba@416	3208	}
deba@414	3209	}
deba@416	3210
deba@414	3211	private:
deba@416	3212
deba@414	3213	InNodeMap& _in_map;
deba@414	3214	OutNodeMap& _out_map;
deba@416	3215
deba@414	3216	};
deba@414	3217
deba@414	3218
deba@416	3219	/// \brief Just gives back a combined node map
deba@416	3220	///
deba@416	3221	/// Just gives back a combined node map
deba@414	3222	template <typename InNodeMap, typename OutNodeMap>
deba@416	3223	static CombinedNodeMap<InNodeMap, OutNodeMap>
deba@414	3224	combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
deba@414	3225	return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
deba@414	3226	}
deba@414	3227
deba@414	3228	template <typename InNodeMap, typename OutNodeMap>
deba@416	3229	static CombinedNodeMap<const InNodeMap, OutNodeMap>
deba@414	3230	combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
deba@414	3231	return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
deba@414	3232	}
deba@414	3233
deba@414	3234	template <typename InNodeMap, typename OutNodeMap>
deba@416	3235	static CombinedNodeMap<InNodeMap, const OutNodeMap>
deba@414	3236	combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
deba@414	3237	return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
deba@414	3238	}
deba@414	3239
deba@414	3240	template <typename InNodeMap, typename OutNodeMap>
deba@416	3241	static CombinedNodeMap<const InNodeMap, const OutNodeMap>
deba@414	3242	combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
deba@416	3243	return CombinedNodeMap<const InNodeMap,
deba@414	3244	const OutNodeMap>(in_map, out_map);
deba@414	3245	}
deba@414	3246
deba@416	3247	/// \brief ArcMap combined from an original ArcMap and a NodeMap
deba@414	3248	///
deba@416	3249	/// This class adapt an original ArcMap and a NodeMap to get an
deba@416	3250	/// arc map on the adapted digraph
deba@414	3251	template <typename DigraphArcMap, typename DigraphNodeMap>
deba@414	3252	class CombinedArcMap {
deba@414	3253	public:
deba@416	3254
deba@414	3255	typedef Arc Key;
deba@414	3256	typedef typename DigraphArcMap::Value Value;
deba@416	3257
deba@414	3258	/// \brief Constructor
deba@414	3259	///
deba@414	3260	/// Constructor.
deba@416	3261	CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
deba@416	3262	: _arc_map(arc_map), _node_map(node_map) {}
deba@414	3263
deba@414	3264	/// \brief The subscript operator.
deba@414	3265	///
deba@414	3266	/// The subscript operator.
deba@414	3267	void set(const Arc& arc, const Value& val) {
deba@416	3268	if (Parent::origArc(arc)) {
deba@416	3269	_arc_map.set(arc, val);
deba@416	3270	} else {
deba@416	3271	_node_map.set(arc, val);
deba@416	3272	}
deba@414	3273	}
deba@414	3274
deba@414	3275	/// \brief The const subscript operator.
deba@414	3276	///
deba@414	3277	/// The const subscript operator.
deba@414	3278	Value operator[](const Key& arc) const {
deba@416	3279	if (Parent::origArc(arc)) {
deba@416	3280	return _arc_map[arc];
deba@416	3281	} else {
deba@416	3282	return _node_map[arc];
deba@416	3283	}
deba@416	3284	}
deba@414	3285
deba@414	3286	/// \brief The const subscript operator.
deba@414	3287	///
deba@414	3288	/// The const subscript operator.
deba@414	3289	Value& operator[](const Key& arc) {
deba@416	3290	if (Parent::origArc(arc)) {
deba@416	3291	return _arc_map[arc];
deba@416	3292	} else {
deba@416	3293	return _node_map[arc];
deba@416	3294	}
deba@416	3295	}
deba@416	3296
deba@414	3297	private:
deba@414	3298	DigraphArcMap& _arc_map;
deba@414	3299	DigraphNodeMap& _node_map;
deba@414	3300	};
deba@416	3301
deba@416	3302	/// \brief Just gives back a combined arc map
deba@416	3303	///
deba@416	3304	/// Just gives back a combined arc map
deba@414	3305	template <typename DigraphArcMap, typename DigraphNodeMap>
deba@416	3306	static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
deba@414	3307	combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
deba@414	3308	return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
deba@414	3309	}
deba@414	3310
deba@414	3311	template <typename DigraphArcMap, typename DigraphNodeMap>
deba@416	3312	static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
deba@414	3313	combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
deba@416	3314	return CombinedArcMap<const DigraphArcMap,
deba@414	3315	DigraphNodeMap>(arc_map, node_map);
deba@414	3316	}
deba@414	3317
deba@414	3318	template <typename DigraphArcMap, typename DigraphNodeMap>
deba@416	3319	static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
deba@414	3320	combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
deba@416	3321	return CombinedArcMap<DigraphArcMap,
deba@414	3322	const DigraphNodeMap>(arc_map, node_map);
deba@414	3323	}
deba@414	3324
deba@414	3325	template <typename DigraphArcMap, typename DigraphNodeMap>
deba@416	3326	static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
deba@416	3327	combinedArcMap(const DigraphArcMap& arc_map,
deba@416	3328	const DigraphNodeMap& node_map) {
deba@416	3329	return CombinedArcMap<const DigraphArcMap,
deba@414	3330	const DigraphNodeMap>(arc_map, node_map);
deba@414	3331	}
deba@414	3332
deba@414	3333	};
deba@414	3334
deba@416	3335	/// \brief Just gives back a node splitter
deba@414	3336	///
deba@416	3337	/// Just gives back a node splitter
deba@414	3338	template<typename Digraph>
deba@416	3339	SplitNodes<Digraph>
deba@416	3340	splitNodes(const Digraph& digraph) {
deba@416	3341	return SplitNodes<Digraph>(digraph);
deba@414	3342	}
deba@414	3343
deba@414	3344
deba@414	3345	} //namespace lemon
deba@414	3346
deba@416	3347	#endif //LEMON_ADAPTORS_H

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 12 Dec 2008 21:41:05 +0000
changeset 432	e9a568cc86e3
parent 415	4b6112235fad
child 440	88ed40ad0d4f
child 446	d369e885d196
permissions	-rw-r--r--