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

author	Peter Kovacs <kpeter@inf.elte.hu>
	Fri, 12 Dec 2008 22:18:41 +0100
changeset 448	9d9990909fc8
parent 447	3c0d39b6388c
child 449	91fcb8ed4cdc
permissions	-rw-r--r--