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

author	Peter Kovacs <kpeter@inf.elte.hu>
	Fri, 17 Apr 2009 09:58:50 +0200
changeset 586	d657c71db7db
parent 550	c5fd2d996909
child 609	4137ef9aacc6
permissions	-rw-r--r--