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

author	Akos Ladanyi <ladanyi@tmit.bme.hu>
	Tue, 28 Apr 2009 13:51:34 +0100
changeset 627	20dac2104519
parent 579	d11bf7998905
child 656	cb38ccedd2c1
permissions	-rw-r--r--