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

author	Peter Kovacs <kpeter@inf.elte.hu>
	Fri, 12 Dec 2008 22:09:29 +0100
changeset 447	3c0d39b6388c
parent 446	d369e885d196
child 448	9d9990909fc8
permissions	-rw-r--r--