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

author	Peter Kovacs <kpeter@inf.elte.hu>
	Fri, 09 Jan 2009 12:43:52 +0100
changeset 450	14bb8812b8af
parent 449	91fcb8ed4cdc
child 451	fbd6e04acf44
permissions	-rw-r--r--