lemon-1.2: lemon/adaptors.h@bb70ad62c95f (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@512	40	#ifdef _MSC_VER
deba@512	41	#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
deba@512	42	#else
deba@512	43	#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
deba@512	44	#endif
deba@512	45
deba@512	46	template<typename DGR>
deba@414	47	class DigraphAdaptorBase {
deba@414	48	public:
deba@512	49	typedef DGR Digraph;
deba@414	50	typedef DigraphAdaptorBase Adaptor;
deba@414	51
deba@414	52	protected:
deba@512	53	DGR* _digraph;
deba@414	54	DigraphAdaptorBase() : _digraph(0) { }
deba@512	55	void initialize(DGR& digraph) { _digraph = &digraph; }
deba@414	56
deba@414	57	public:
deba@512	58	DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
deba@512	59
deba@512	60	typedef typename DGR::Node Node;
deba@512	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@512	76	typedef NodeNumTagIndicator<DGR> NodeNumTag;
deba@414	77	int nodeNum() const { return _digraph->nodeNum(); }
deba@416	78
deba@512	79	typedef ArcNumTagIndicator<DGR> ArcNumTag;
deba@414	80	int arcNum() const { return _digraph->arcNum(); }
deba@414	81
deba@512	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@512	104	typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
deba@416	105	NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
deba@414	106
deba@512	107	typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
deba@416	108	ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
deba@416	109
deba@512	110	template <typename V>
deba@512	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@512	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@512	133	template <typename V>
deba@512	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@512	138	explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
deba@416	139	: Parent(*adaptor._digraph) {}
deba@512	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@512	158	template<typename GR>
deba@416	159	class GraphAdaptorBase {
deba@416	160	public:
deba@512	161	typedef GR Graph;
deba@416	162
deba@416	163	protected:
deba@512	164	GR* _graph;
deba@416	165
deba@416	166	GraphAdaptorBase() : _graph(0) {}
deba@416	167
deba@512	168	void initialize(GR& graph) { _graph = &graph; }
deba@416	169
deba@416	170	public:
deba@512	171	GraphAdaptorBase(GR& graph) : _graph(&graph) {}
deba@512	172
deba@512	173	typedef typename GR::Node Node;
deba@512	174	typedef typename GR::Arc Arc;
deba@512	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@512	243	typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@416	244	NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
deba@416	245
deba@512	246	typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
deba@416	247	ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
deba@416	248
deba@512	249	typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
deba@416	250	EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
deba@416	251
deba@512	252	template <typename V>
deba@512	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@512	257	explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
deba@416	258	: Parent(*adapter._graph) {}
deba@512	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@512	275	template <typename V>
deba@512	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@512	280	explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
deba@416	281	: Parent(*adapter._graph) {}
deba@512	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@512	297	template <typename V>
deba@512	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@512	302	explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
deba@416	303	: Parent(*adapter._graph) {}
deba@512	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@512	321	template <typename DGR>
deba@512	322	class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
kpeter@617	323	typedef DigraphAdaptorBase<DGR> Parent;
deba@414	324	public:
deba@512	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@512	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@512	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@512	369	template<typename DGR>
kpeter@453	370	#ifdef DOXYGEN
kpeter@453	371	class ReverseDigraph {
kpeter@453	372	#else
deba@416	373	class ReverseDigraph :
deba@512	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@512	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@512	387	explicit ReverseDigraph(DGR& digraph) {
deba@512	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@512	397	template<typename DGR>
deba@512	398	ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
deba@512	399	return ReverseDigraph<const DGR>(digraph);
deba@414	400	}
deba@414	401
kpeter@451	402
deba@512	403	template <typename DGR, typename NF, typename AF, bool ch = true>
deba@512	404	class SubDigraphBase : public DigraphAdaptorBase<DGR> {
kpeter@617	405	typedef DigraphAdaptorBase<DGR> Parent;
deba@414	406	public:
deba@512	407	typedef DGR Digraph;
deba@512	408	typedef NF NodeFilterMap;
deba@512	409	typedef AF ArcFilterMap;
deba@414	410
deba@416	411	typedef SubDigraphBase Adaptor;
deba@414	412	protected:
deba@512	413	NF* _node_filter;
deba@512	414	AF* _arc_filter;
deba@416	415	SubDigraphBase()
deba@414	416	: Parent(), _node_filter(0), _arc_filter(0) { }
deba@414	417
deba@512	418	void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
deba@512	419	Parent::initialize(digraph);
deba@414	420	_node_filter = &node_filter;
deba@512	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@512	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@512	505	public:
deba@512	506
deba@512	507	template <typename V>
deba@512	508	class NodeMap
deba@512	509	: public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
deba@512	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@512	515	typedef V Value;
deba@512	516
deba@512	517	NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
deba@512	518	: Parent(adaptor) {}
deba@512	519	NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
deba@512	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@512	529	Parent::operator=(cmap);
deba@416	530	return *this;
deba@414	531	}
deba@414	532	};
deba@414	533
deba@512	534	template <typename V>
deba@512	535	class ArcMap
deba@512	536	: public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
deba@512	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@512	542	typedef V Value;
deba@512	543
deba@512	544	ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
deba@512	545	: Parent(adaptor) {}
deba@512	546	ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
deba@512	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@512	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@512	563	template <typename DGR, typename NF, typename AF>
deba@512	564	class SubDigraphBase<DGR, NF, AF, false>
deba@512	565	: public DigraphAdaptorBase<DGR> {
kpeter@617	566	typedef DigraphAdaptorBase<DGR> Parent;
deba@414	567	public:
deba@512	568	typedef DGR Digraph;
deba@512	569	typedef NF NodeFilterMap;
deba@512	570	typedef AF ArcFilterMap;
deba@414	571
deba@416	572	typedef SubDigraphBase Adaptor;
deba@414	573	protected:
deba@512	574	NF* _node_filter;
deba@512	575	AF* _arc_filter;
deba@416	576	SubDigraphBase()
deba@414	577	: Parent(), _node_filter(0), _arc_filter(0) { }
deba@414	578
deba@512	579	void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
deba@512	580	Parent::initialize(digraph);
deba@414	581	_node_filter = &node_filter;
deba@512	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@512	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@512	650	template <typename V>
deba@512	651	class NodeMap
deba@512	652	: public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
deba@512	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@512	658	typedef V Value;
deba@512	659
deba@512	660	NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
deba@512	661	: Parent(adaptor) {}
deba@512	662	NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
deba@512	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@512	672	Parent::operator=(cmap);
deba@416	673	return *this;
deba@414	674	}
deba@414	675	};
deba@414	676
deba@512	677	template <typename V>
deba@512	678	class ArcMap
deba@512	679	: public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
deba@512	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@512	685	typedef V Value;
deba@512	686
deba@512	687	ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
deba@512	688	: Parent(adaptor) {}
deba@512	689	ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
deba@512	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@512	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@512	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@512	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@512	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@512	740	template<typename DGR, typename NF, typename AF>
kpeter@453	741	class SubDigraph {
kpeter@451	742	#else
deba@512	743	template<typename DGR,
deba@512	744	typename NF = typename DGR::template NodeMap<bool>,
deba@512	745	typename AF = typename DGR::template ArcMap<bool> >
kpeter@453	746	class SubDigraph :
deba@512	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@512	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@512	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@512	771	SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
deba@512	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@512	834	template<typename DGR, typename NF, typename AF>
deba@512	835	SubDigraph<const DGR, NF, AF>
deba@512	836	subDigraph(const DGR& digraph,
deba@512	837	NF& node_filter, AF& arc_filter) {
deba@512	838	return SubDigraph<const DGR, NF, AF>
deba@512	839	(digraph, node_filter, arc_filter);
deba@414	840	}
deba@414	841
deba@512	842	template<typename DGR, typename NF, typename AF>
deba@512	843	SubDigraph<const DGR, const NF, AF>
deba@512	844	subDigraph(const DGR& digraph,
deba@512	845	const NF& node_filter, AF& arc_filter) {
deba@512	846	return SubDigraph<const DGR, const NF, AF>
deba@512	847	(digraph, node_filter, arc_filter);
deba@414	848	}
deba@414	849
deba@512	850	template<typename DGR, typename NF, typename AF>
deba@512	851	SubDigraph<const DGR, NF, const AF>
deba@512	852	subDigraph(const DGR& digraph,
deba@512	853	NF& node_filter, const AF& arc_filter) {
deba@512	854	return SubDigraph<const DGR, NF, const AF>
deba@512	855	(digraph, node_filter, arc_filter);
deba@414	856	}
deba@414	857
deba@512	858	template<typename DGR, typename NF, typename AF>
deba@512	859	SubDigraph<const DGR, const NF, const AF>
deba@512	860	subDigraph(const DGR& digraph,
deba@512	861	const NF& node_filter, const AF& arc_filter) {
deba@512	862	return SubDigraph<const DGR, const NF, const AF>
deba@512	863	(digraph, node_filter, arc_filter);
deba@414	864	}
deba@414	865
deba@414	866
deba@512	867	template <typename GR, typename NF, typename EF, bool ch = true>
deba@512	868	class SubGraphBase : public GraphAdaptorBase<GR> {
kpeter@617	869	typedef GraphAdaptorBase<GR> Parent;
deba@416	870	public:
deba@512	871	typedef GR Graph;
deba@512	872	typedef NF NodeFilterMap;
deba@512	873	typedef EF EdgeFilterMap;
kpeter@449	874
deba@416	875	typedef SubGraphBase Adaptor;
deba@416	876	protected:
deba@416	877
deba@512	878	NF* _node_filter;
deba@512	879	EF* _edge_filter;
deba@416	880
deba@416	881	SubGraphBase()
deba@512	882	: Parent(), _node_filter(0), _edge_filter(0) { }
deba@512	883
deba@512	884	void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
deba@512	885	Parent::initialize(graph);
deba@512	886	_node_filter = &node_filter;
deba@512	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@512	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@512	903	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	904	\|\| !(*_node_filter)[Parent::source(i)]
deba@512	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@512	911	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	912	\|\| !(*_node_filter)[Parent::u(i)]
deba@512	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@512	919	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	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@512	926	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	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@512	933	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	934	\|\| !(*_node_filter)[Parent::u(i)]
deba@512	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@512	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@512	946	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	947	\|\| !(*_node_filter)[Parent::source(i)]
deba@512	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@512	954	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	955	\|\| !(*_node_filter)[Parent::u(i)]
deba@512	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@512	962	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	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@512	969	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	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@512	976	while (i!=INVALID && (!(*_edge_filter)[i]
deba@512	977	\|\| !(*_node_filter)[Parent::u(i)]
deba@512	978	\|\| !(*_node_filter)[Parent::v(i)]))
deba@416	979	Parent::nextInc(i, d);
deba@416	980	}
deba@416	981
deba@512	982	void status(const Node& n, bool v) const { _node_filter->set(n, v); }
deba@512	983	void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
deba@512	984
deba@512	985	bool status(const Node& n) const { return (*_node_filter)[n]; }
deba@512	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@512	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@512	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@512	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@512	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@512	1018	template <typename V>
deba@512	1019	class NodeMap
deba@512	1020	: public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
deba@512	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@512	1026	typedef V Value;
deba@512	1027
deba@512	1028	NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
deba@512	1029	: Parent(adaptor) {}
deba@512	1030	NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
deba@512	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@512	1040	Parent::operator=(cmap);
deba@416	1041	return *this;
deba@416	1042	}
deba@416	1043	};
deba@416	1044
deba@512	1045	template <typename V>
deba@512	1046	class ArcMap
deba@512	1047	: public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
deba@512	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@512	1053	typedef V Value;
deba@512	1054
deba@512	1055	ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
deba@512	1056	: Parent(adaptor) {}
deba@512	1057	ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
deba@512	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@512	1067	Parent::operator=(cmap);
deba@416	1068	return *this;
deba@416	1069	}
deba@416	1070	};
deba@416	1071
deba@512	1072	template <typename V>
deba@512	1073	class EdgeMap
deba@512	1074	: public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
deba@512	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@512	1080	typedef V Value;
deba@512	1081
deba@512	1082	EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
deba@512	1083	: Parent(adaptor) {}
deba@512	1084
deba@512	1085	EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
deba@512	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@512	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@512	1102	template <typename GR, typename NF, typename EF>
deba@512	1103	class SubGraphBase<GR, NF, EF, false>
deba@512	1104	: public GraphAdaptorBase<GR> {
kpeter@617	1105	typedef GraphAdaptorBase<GR> Parent;
deba@416	1106	public:
deba@512	1107	typedef GR Graph;
deba@512	1108	typedef NF NodeFilterMap;
deba@512	1109	typedef EF EdgeFilterMap;
kpeter@449	1110
deba@416	1111	typedef SubGraphBase Adaptor;
deba@416	1112	protected:
deba@512	1113	NF* _node_filter;
deba@512	1114	EF* _edge_filter;
deba@512	1115	SubGraphBase()
deba@512	1116	: Parent(), _node_filter(0), _edge_filter(0) { }
deba@512	1117
deba@512	1118	void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
deba@512	1119	Parent::initialize(graph);
deba@512	1120	_node_filter = &node_filter;
deba@512	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@512	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@512	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@512	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@512	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@512	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@512	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@512	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@512	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@512	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@512	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@512	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@512	1183	while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
deba@416	1184	}
deba@416	1185
deba@512	1186	void status(const Node& n, bool v) const { _node_filter->set(n, v); }
deba@512	1187	void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
deba@512	1188
deba@512	1189	bool status(const Node& n) const { return (*_node_filter)[n]; }
deba@512	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@512	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@512	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@512	1216	template <typename V>
deba@512	1217	class NodeMap
deba@512	1218	: public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
deba@512	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@512	1224	typedef V Value;
deba@512	1225
deba@512	1226	NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
deba@512	1227	: Parent(adaptor) {}
deba@512	1228	NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
deba@512	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@512	1238	Parent::operator=(cmap);
deba@416	1239	return *this;
deba@416	1240	}
deba@416	1241	};
deba@416	1242
deba@512	1243	template <typename V>
deba@512	1244	class ArcMap
deba@512	1245	: public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
deba@512	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@512	1251	typedef V Value;
deba@512	1252
deba@512	1253	ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
deba@512	1254	: Parent(adaptor) {}
deba@512	1255	ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
deba@512	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@512	1265	Parent::operator=(cmap);
deba@416	1266	return *this;
deba@416	1267	}
deba@416	1268	};
deba@416	1269
deba@512	1270	template <typename V>
deba@512	1271	class EdgeMap
deba@512	1272	: public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
deba@512	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@512	1278	typedef V Value;
deba@512	1279
deba@512	1280	EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
deba@512	1281	: Parent(adaptor) {}
deba@512	1282
deba@512	1283	EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
deba@512	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@512	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@512	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@512	1366	SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
deba@512	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@512	1431	subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
kpeter@453	1432	return SubGraph<const GR, NF, EF>
deba@512	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@512	1438	subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
kpeter@453	1439	return SubGraph<const GR, const NF, EF>
deba@512	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@512	1445	subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
kpeter@453	1446	return SubGraph<const GR, NF, const EF>
deba@512	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@512	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@512	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@512	1494	SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
deba@512	1495	true> > {
deba@416	1496	#endif
kpeter@453	1497	typedef DigraphAdaptorExtender<
deba@512	1498	SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
deba@512	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@512	1509	ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
deba@512	1510
deba@512	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@512	1519	FilterNodes(GR& graph, NF& node_filter)
deba@512	1520	: Parent(), const_true_map()
kpeter@453	1521	{
deba@512	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@512	1557	SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
deba@512	1558	true> > {
kpeter@453	1559
kpeter@453	1560	typedef GraphAdaptorExtender<
deba@512	1561	SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
deba@512	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@512	1572	ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
deba@512	1573
deba@512	1574	FilterNodes() : const_true_map() {}
deba@416	1575
deba@416	1576	public:
deba@416	1577
deba@512	1578	FilterNodes(GR& graph, NodeFilterMap& node_filter) :
deba@512	1579	Parent(), const_true_map() {
deba@512	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@512	1598	filterNodes(const GR& graph, NF& node_filter) {
deba@512	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@512	1604	filterNodes(const GR& graph, const NF& node_filter) {
deba@512	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@512	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@512	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@512	1633	template<typename DGR,
kpeter@453	1634	typename AF>
kpeter@453	1635	class FilterArcs {
kpeter@451	1636	#else
deba@512	1637	template<typename DGR,
deba@512	1638	typename AF = typename DGR::template ArcMap<bool> >
kpeter@453	1639	class FilterArcs :
kpeter@453	1640	public DigraphAdaptorExtender<
deba@512	1641	SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
deba@512	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@512	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@512	1658	ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
deba@512	1659
deba@512	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@512	1668	FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
deba@512	1669	: Parent(), const_true_map() {
deba@512	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@512	1706	template<typename DGR, typename AF>
deba@512	1707	FilterArcs<const DGR, AF>
deba@512	1708	filterArcs(const DGR& digraph, AF& arc_filter) {
deba@512	1709	return FilterArcs<const DGR, AF>(digraph, arc_filter);
deba@414	1710	}
deba@414	1711
deba@512	1712	template<typename DGR, typename AF>
deba@512	1713	FilterArcs<const DGR, const AF>
deba@512	1714	filterArcs(const DGR& digraph, const AF& arc_filter) {
deba@512	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@512	1751	SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
deba@512	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@512	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@512	1780	FilterEdges(GR& graph, EF& edge_filter)
deba@512	1781	: Parent(), const_true_map() {
deba@512	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@512	1820	filterEdges(const GR& graph, EF& edge_filter) {
deba@512	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@512	1826	filterEdges(const GR& graph, const EF& edge_filter) {
deba@512	1827	return FilterEdges<const GR, const EF>(graph, edge_filter);
deba@416	1828	}
deba@416	1829
kpeter@451	1830
deba@512	1831	template <typename DGR>
deba@416	1832	class UndirectorBase {
deba@414	1833	public:
deba@512	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@656	1842	class Arc {
deba@416	1843	friend class UndirectorBase;
deba@414	1844	protected:
deba@656	1845	Edge _edge;
deba@414	1846	bool _forward;
deba@414	1847
deba@656	1848	Arc(const Edge& edge, bool forward)
deba@656	1849	: _edge(edge), _forward(forward) {}
deba@414	1850
deba@414	1851	public:
deba@414	1852	Arc() {}
deba@414	1853
deba@656	1854	Arc(Invalid) : _edge(INVALID), _forward(true) {}
deba@656	1855
deba@656	1856	operator const Edge&() const { return _edge; }
deba@414	1857
deba@414	1858	bool operator==(const Arc &other) const {
deba@656	1859	return _forward == other._forward && _edge == other._edge;
deba@414	1860	}
deba@414	1861	bool operator!=(const Arc &other) const {
deba@656	1862	return _forward != other._forward \|\| _edge != other._edge;
deba@414	1863	}
deba@414	1864	bool operator<(const Arc &other) const {
deba@416	1865	return _forward < other._forward \|\|
deba@656	1866	(_forward == other._forward && _edge < other._edge);
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@656	1879	_digraph->first(a._edge);
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@656	1887	_digraph->next(a._edge);
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@656	1901	_digraph->firstIn(a._edge, n);
deba@656	1902	if (a._edge != INVALID ) {
deba@416	1903	a._forward = false;
deba@414	1904	} else {
deba@656	1905	_digraph->firstOut(a._edge, 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@656	1911	Node n = _digraph->target(a._edge);
deba@656	1912	_digraph->nextIn(a._edge);
deba@656	1913	if (a._edge == INVALID) {
deba@656	1914	_digraph->firstOut(a._edge, n);
deba@416	1915	a._forward = true;
deba@416	1916	}
deba@414	1917	}
deba@414	1918	else {
deba@656	1919	_digraph->nextOut(a._edge);
deba@414	1920	}
deba@414	1921	}
deba@414	1922
deba@414	1923	void firstIn(Arc &a, const Node &n) const {
deba@656	1924	_digraph->firstOut(a._edge, n);
deba@656	1925	if (a._edge != INVALID ) {
deba@416	1926	a._forward = false;
deba@414	1927	} else {
deba@656	1928	_digraph->firstIn(a._edge, 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@656	1934	Node n = _digraph->source(a._edge);
deba@656	1935	_digraph->nextOut(a._edge);
deba@656	1936	if (a._edge == INVALID ) {
deba@656	1937	_digraph->firstIn(a._edge, n);
deba@416	1938	a._forward = true;
deba@416	1939	}
deba@414	1940	}
deba@414	1941	else {
deba@656	1942	_digraph->nextIn(a._edge);
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@656	1975	return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
deba@414	1976	}
deba@414	1977
deba@414	1978	Node target(const Arc &a) const {
deba@656	1979	return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
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
deba@414	1986	static bool direction(const Arc &a) { return a._forward; }
deba@414	1987
deba@414	1988	Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
deba@414	1989	Arc arcFromId(int ix) const {
deba@414	1990	return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
deba@414	1991	}
deba@414	1992	Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
deba@414	1993
deba@414	1994	int id(const Node &n) const { return _digraph->id(n); }
deba@414	1995	int id(const Arc &a) const {
deba@414	1996	return (_digraph->id(a) << 1) \| (a._forward ? 1 : 0);
deba@414	1997	}
deba@414	1998	int id(const Edge &e) const { return _digraph->id(e); }
deba@414	1999
deba@414	2000	int maxNodeId() const { return _digraph->maxNodeId(); }
deba@414	2001	int maxArcId() const { return (_digraph->maxArcId() << 1) \| 1; }
deba@414	2002	int maxEdgeId() const { return _digraph->maxArcId(); }
deba@414	2003
deba@414	2004	Node addNode() { return _digraph->addNode(); }
deba@416	2005	Edge addEdge(const Node& u, const Node& v) {
deba@416	2006	return _digraph->addArc(u, v);
deba@414	2007	}
deba@414	2008
deba@414	2009	void erase(const Node& i) { _digraph->erase(i); }
deba@414	2010	void erase(const Edge& i) { _digraph->erase(i); }
deba@416	2011
deba@414	2012	void clear() { _digraph->clear(); }
deba@414	2013
deba@414	2014	typedef NodeNumTagIndicator<Digraph> NodeNumTag;
kpeter@449	2015	int nodeNum() const { return _digraph->nodeNum(); }
kpeter@446	2016
kpeter@446	2017	typedef ArcNumTagIndicator<Digraph> ArcNumTag;
deba@414	2018	int arcNum() const { return 2 * _digraph->arcNum(); }
kpeter@446	2019
kpeter@446	2020	typedef ArcNumTag EdgeNumTag;
deba@414	2021	int edgeNum() const { return _digraph->arcNum(); }
deba@414	2022
kpeter@446	2023	typedef FindArcTagIndicator<Digraph> FindArcTag;
deba@414	2024	Arc findArc(Node s, Node t, Arc p = INVALID) const {
deba@414	2025	if (p == INVALID) {
deba@416	2026	Edge arc = _digraph->findArc(s, t);
deba@416	2027	if (arc != INVALID) return direct(arc, true);
deba@416	2028	arc = _digraph->findArc(t, s);
deba@416	2029	if (arc != INVALID) return direct(arc, false);
deba@414	2030	} else if (direction(p)) {
deba@416	2031	Edge arc = _digraph->findArc(s, t, p);
deba@416	2032	if (arc != INVALID) return direct(arc, true);
deba@416	2033	arc = _digraph->findArc(t, s);
deba@416	2034	if (arc != INVALID) return direct(arc, false);
deba@414	2035	} else {
deba@416	2036	Edge arc = _digraph->findArc(t, s, p);
deba@416	2037	if (arc != INVALID) return direct(arc, false);
deba@414	2038	}
deba@414	2039	return INVALID;
deba@414	2040	}
deba@414	2041
kpeter@446	2042	typedef FindArcTag FindEdgeTag;
deba@414	2043	Edge findEdge(Node s, Node t, Edge p = INVALID) const {
deba@414	2044	if (s != t) {
deba@414	2045	if (p == INVALID) {
deba@414	2046	Edge arc = _digraph->findArc(s, t);
deba@414	2047	if (arc != INVALID) return arc;
deba@414	2048	arc = _digraph->findArc(t, s);
deba@414	2049	if (arc != INVALID) return arc;
kpeter@449	2050	} else if (_digraph->source(p) == s) {
deba@414	2051	Edge arc = _digraph->findArc(s, t, p);
deba@414	2052	if (arc != INVALID) return arc;
deba@414	2053	arc = _digraph->findArc(t, s);
deba@416	2054	if (arc != INVALID) return arc;
deba@414	2055	} else {
deba@414	2056	Edge arc = _digraph->findArc(t, s, p);
deba@416	2057	if (arc != INVALID) return arc;
deba@414	2058	}
deba@414	2059	} else {
deba@414	2060	return _digraph->findArc(s, t, p);
deba@414	2061	}
deba@414	2062	return INVALID;
deba@414	2063	}
deba@414	2064
deba@414	2065	private:
deba@416	2066
deba@512	2067	template <typename V>
deba@414	2068	class ArcMapBase {
deba@414	2069	private:
deba@416	2070
deba@512	2071	typedef typename DGR::template ArcMap<V> MapImpl;
deba@416	2072
deba@414	2073	public:
deba@414	2074
deba@414	2075	typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
deba@414	2076
deba@512	2077	typedef V Value;
deba@414	2078	typedef Arc Key;
kpeter@449	2079	typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
kpeter@449	2080	typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
kpeter@449	2081	typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
kpeter@449	2082	typedef typename MapTraits<MapImpl>::ReturnValue Reference;
deba@416	2083
deba@512	2084	ArcMapBase(const UndirectorBase<DGR>& adaptor) :
deba@416	2085	_forward(adaptor._digraph), _backward(adaptor._digraph) {}
deba@416	2086
deba@512	2087	ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
deba@512	2088	: _forward(*adaptor._digraph, value),
deba@512	2089	_backward(*adaptor._digraph, value) {}
deba@512	2090
deba@512	2091	void set(const Arc& a, const V& value) {
deba@416	2092	if (direction(a)) {
deba@512	2093	_forward.set(a, value);
deba@416	2094	} else {
deba@512	2095	_backward.set(a, value);
deba@414	2096	}
deba@414	2097	}
deba@414	2098
kpeter@449	2099	ConstReturnValue operator[](const Arc& a) const {
deba@416	2100	if (direction(a)) {
deba@416	2101	return _forward[a];
deba@416	2102	} else {
deba@416	2103	return _backward[a];
deba@414	2104	}
deba@414	2105	}
deba@414	2106
kpeter@449	2107	ReturnValue operator[](const Arc& a) {
deba@416	2108	if (direction(a)) {
deba@416	2109	return _forward[a];
deba@416	2110	} else {
deba@416	2111	return _backward[a];
deba@416	2112	}
deba@416	2113	}
deba@416	2114
deba@414	2115	protected:
deba@414	2116
deba@416	2117	MapImpl _forward, _backward;
deba@414	2118
deba@414	2119	};
deba@414	2120
deba@414	2121	public:
deba@414	2122
deba@512	2123	template <typename V>
deba@512	2124	class NodeMap : public DGR::template NodeMap<V> {
kpeter@617	2125	typedef typename DGR::template NodeMap<V> Parent;
kpeter@617	2126
deba@414	2127	public:
deba@512	2128	typedef V Value;
deba@512	2129
deba@512	2130	explicit NodeMap(const UndirectorBase<DGR>& adaptor)
deba@416	2131	: Parent(*adaptor._digraph) {}
deba@414	2132
deba@512	2133	NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
deba@416	2134	: Parent(*adaptor._digraph, value) { }
deba@414	2135
deba@414	2136	private:
deba@414	2137	NodeMap& operator=(const NodeMap& cmap) {
deba@414	2138	return operator=<NodeMap>(cmap);
deba@414	2139	}
deba@414	2140
deba@414	2141	template <typename CMap>
deba@414	2142	NodeMap& operator=(const CMap& cmap) {
deba@414	2143	Parent::operator=(cmap);
deba@414	2144	return *this;
deba@414	2145	}
deba@416	2146
deba@414	2147	};
deba@414	2148
deba@512	2149	template <typename V>
deba@416	2150	class ArcMap
kpeter@617	2151	: public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
kpeter@617	2152	typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
kpeter@617	2153
deba@414	2154	public:
deba@512	2155	typedef V Value;
deba@512	2156
deba@512	2157	explicit ArcMap(const UndirectorBase<DGR>& adaptor)
deba@416	2158	: Parent(adaptor) {}
deba@416	2159
deba@512	2160	ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
deba@416	2161	: Parent(adaptor, value) {}
deba@416	2162
deba@414	2163	private:
deba@414	2164	ArcMap& operator=(const ArcMap& cmap) {
deba@416	2165	return operator=<ArcMap>(cmap);
deba@414	2166	}
deba@416	2167
deba@414	2168	template <typename CMap>
deba@414	2169	ArcMap& operator=(const CMap& cmap) {
deba@414	2170	Parent::operator=(cmap);
deba@416	2171	return *this;
deba@414	2172	}
deba@414	2173	};
deba@416	2174
deba@512	2175	template <typename V>
deba@512	2176	class EdgeMap : public Digraph::template ArcMap<V> {
kpeter@617	2177	typedef typename Digraph::template ArcMap<V> Parent;
kpeter@617	2178
deba@414	2179	public:
deba@512	2180	typedef V Value;
deba@512	2181
deba@512	2182	explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
deba@416	2183	: Parent(*adaptor._digraph) {}
deba@414	2184
deba@512	2185	EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
deba@416	2186	: Parent(*adaptor._digraph, value) {}
deba@414	2187
deba@414	2188	private:
deba@414	2189	EdgeMap& operator=(const EdgeMap& cmap) {
deba@414	2190	return operator=<EdgeMap>(cmap);
deba@414	2191	}
deba@414	2192
deba@414	2193	template <typename CMap>
deba@414	2194	EdgeMap& operator=(const CMap& cmap) {
deba@414	2195	Parent::operator=(cmap);
deba@414	2196	return *this;
deba@414	2197	}
deba@414	2198
deba@414	2199	};
deba@414	2200
deba@512	2201	typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
deba@416	2202	NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
deba@414	2203
deba@512	2204	typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
kpeter@449	2205	EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
kpeter@579	2206
kpeter@579	2207	typedef EdgeNotifier ArcNotifier;
kpeter@579	2208	ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
kpeter@449	2209
deba@414	2210	protected:
deba@414	2211
deba@416	2212	UndirectorBase() : _digraph(0) {}
deba@414	2213
deba@512	2214	DGR* _digraph;
deba@512	2215
deba@512	2216	void initialize(DGR& digraph) {
deba@414	2217	_digraph = &digraph;
deba@414	2218	}
deba@416	2219
deba@414	2220	};
deba@414	2221
deba@416	2222	/// \ingroup graph_adaptors
deba@414	2223	///
kpeter@451	2224	/// \brief Adaptor class for viewing a digraph as an undirected graph.
deba@414	2225	///
kpeter@451	2226	/// Undirector adaptor can be used for viewing a digraph as an undirected
kpeter@451	2227	/// graph. All arcs of the underlying digraph are showed in the
kpeter@451	2228	/// adaptor as an edge (and also as a pair of arcs, of course).
kpeter@451	2229	/// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
deba@414	2230	///
kpeter@451	2231	/// The adapted digraph can also be modified through this adaptor
kpeter@453	2232	/// by adding or removing nodes or edges, unless the \c GR template
kpeter@451	2233	/// parameter is set to be \c const.
kpeter@451	2234	///
deba@512	2235	/// \tparam DGR The type of the adapted digraph.
kpeter@451	2236	/// It must conform to the \ref concepts::Digraph "Digraph" concept.
kpeter@451	2237	/// It can also be specified to be \c const.
kpeter@451	2238	///
kpeter@451	2239	/// \note The \c Node type of this adaptor and the adapted digraph are
kpeter@451	2240	/// convertible to each other, moreover the \c Edge type of the adaptor
kpeter@451	2241	/// and the \c Arc type of the adapted digraph are also convertible to
kpeter@451	2242	/// each other.
kpeter@451	2243	/// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
kpeter@451	2244	/// of the adapted digraph.)
deba@512	2245	template<typename DGR>
kpeter@453	2246	#ifdef DOXYGEN
kpeter@453	2247	class Undirector {
kpeter@453	2248	#else
kpeter@453	2249	class Undirector :
deba@512	2250	public GraphAdaptorExtender<UndirectorBase<DGR> > {
kpeter@453	2251	#endif
kpeter@617	2252	typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
deba@414	2253	public:
kpeter@453	2254	/// The type of the adapted digraph.
deba@512	2255	typedef DGR Digraph;
deba@414	2256	protected:
deba@416	2257	Undirector() { }
deba@414	2258	public:
deba@414	2259
deba@414	2260	/// \brief Constructor
deba@414	2261	///
kpeter@451	2262	/// Creates an undirected graph from the given digraph.
deba@512	2263	Undirector(DGR& digraph) {
deba@512	2264	initialize(digraph);
deba@414	2265	}
deba@414	2266
kpeter@451	2267	/// \brief Arc map combined from two original arc maps
deba@414	2268	///
kpeter@451	2269	/// This map adaptor class adapts two arc maps of the underlying
kpeter@451	2270	/// digraph to get an arc map of the undirected graph.
kpeter@559	2271	/// Its value type is inherited from the first arc map type (\c FW).
kpeter@559	2272	/// \tparam FW The type of the "foward" arc map.
kpeter@559	2273	/// \tparam BK The type of the "backward" arc map.
kpeter@559	2274	template <typename FW, typename BK>
deba@414	2275	class CombinedArcMap {
deba@414	2276	public:
deba@416	2277
kpeter@451	2278	/// The key type of the map
kpeter@451	2279	typedef typename Parent::Arc Key;
kpeter@451	2280	/// The value type of the map
kpeter@559	2281	typedef typename FW::Value Value;
kpeter@559	2282
kpeter@559	2283	typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
kpeter@559	2284
kpeter@559	2285	typedef typename MapTraits<FW>::ReturnValue ReturnValue;
kpeter@559	2286	typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
kpeter@559	2287	typedef typename MapTraits<FW>::ReturnValue Reference;
kpeter@559	2288	typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
kpeter@449	2289
deba@416	2290	/// Constructor
kpeter@559	2291	CombinedArcMap(FW& forward, BK& backward)
deba@414	2292	: _forward(&forward), _backward(&backward) {}
deba@416	2293
kpeter@451	2294	/// Sets the value associated with the given key.
deba@416	2295	void set(const Key& e, const Value& a) {
deba@416	2296	if (Parent::direction(e)) {
deba@416	2297	_forward->set(e, a);
deba@416	2298	} else {
deba@416	2299	_backward->set(e, a);
deba@416	2300	}
deba@414	2301	}
deba@414	2302
kpeter@451	2303	/// Returns the value associated with the given key.
kpeter@449	2304	ConstReturnValue operator[](const Key& e) const {
deba@416	2305	if (Parent::direction(e)) {
deba@416	2306	return (*_forward)[e];
deba@416	2307	} else {
deba@416	2308	return (*_backward)[e];
deba@414	2309	}
deba@414	2310	}
deba@414	2311
kpeter@451	2312	/// Returns a reference to the value associated with the given key.
kpeter@449	2313	ReturnValue operator[](const Key& e) {
deba@416	2314	if (Parent::direction(e)) {
deba@416	2315	return (*_forward)[e];
deba@416	2316	} else {
deba@416	2317	return (*_backward)[e];
deba@414	2318	}
deba@414	2319	}
deba@414	2320
deba@416	2321	protected:
deba@416	2322
kpeter@559	2323	FW* _forward;
kpeter@559	2324	BK* _backward;
deba@416	2325
deba@416	2326	};
deba@416	2327
kpeter@451	2328	/// \brief Returns a combined arc map
deba@416	2329	///
kpeter@451	2330	/// This function just returns a combined arc map.
kpeter@559	2331	template <typename FW, typename BK>
kpeter@559	2332	static CombinedArcMap<FW, BK>
kpeter@559	2333	combinedArcMap(FW& forward, BK& backward) {
kpeter@559	2334	return CombinedArcMap<FW, BK>(forward, backward);
deba@416	2335	}
deba@416	2336
kpeter@559	2337	template <typename FW, typename BK>
kpeter@559	2338	static CombinedArcMap<const FW, BK>
kpeter@559	2339	combinedArcMap(const FW& forward, BK& backward) {
kpeter@559	2340	return CombinedArcMap<const FW, BK>(forward, backward);
deba@416	2341	}
deba@416	2342
kpeter@559	2343	template <typename FW, typename BK>
kpeter@559	2344	static CombinedArcMap<FW, const BK>
kpeter@559	2345	combinedArcMap(FW& forward, const BK& backward) {
kpeter@559	2346	return CombinedArcMap<FW, const BK>(forward, backward);
deba@416	2347	}
deba@416	2348
kpeter@559	2349	template <typename FW, typename BK>
kpeter@559	2350	static CombinedArcMap<const FW, const BK>
kpeter@559	2351	combinedArcMap(const FW& forward, const BK& backward) {
kpeter@559	2352	return CombinedArcMap<const FW, const BK>(forward, backward);
deba@416	2353	}
deba@416	2354
deba@416	2355	};
deba@416	2356
kpeter@451	2357	/// \brief Returns a read-only Undirector adaptor
deba@416	2358	///
kpeter@451	2359	/// This function just returns a read-only \ref Undirector adaptor.
kpeter@451	2360	/// \ingroup graph_adaptors
kpeter@451	2361	/// \relates Undirector
deba@512	2362	template<typename DGR>
deba@512	2363	Undirector<const DGR> undirector(const DGR& digraph) {
deba@512	2364	return Undirector<const DGR>(digraph);
deba@416	2365	}
deba@416	2366
kpeter@451	2367
deba@512	2368	template <typename GR, typename DM>
deba@416	2369	class OrienterBase {
deba@416	2370	public:
deba@416	2371
deba@512	2372	typedef GR Graph;
deba@512	2373	typedef DM DirectionMap;
deba@512	2374
deba@512	2375	typedef typename GR::Node Node;
deba@512	2376	typedef typename GR::Edge Arc;
deba@416	2377
deba@416	2378	void reverseArc(const Arc& arc) {
deba@416	2379	_direction->set(arc, !(*_direction)[arc]);
deba@416	2380	}
deba@416	2381
deba@416	2382	void first(Node& i) const { _graph->first(i); }
deba@416	2383	void first(Arc& i) const { _graph->first(i); }
deba@416	2384	void firstIn(Arc& i, const Node& n) const {
kpeter@447	2385	bool d = true;
deba@416	2386	_graph->firstInc(i, d, n);
deba@416	2387	while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2388	}
deba@416	2389	void firstOut(Arc& i, const Node& n ) const {
kpeter@447	2390	bool d = true;
deba@416	2391	_graph->firstInc(i, d, n);
deba@416	2392	while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2393	}
deba@416	2394
deba@416	2395	void next(Node& i) const { _graph->next(i); }
deba@416	2396	void next(Arc& i) const { _graph->next(i); }
deba@416	2397	void nextIn(Arc& i) const {
deba@416	2398	bool d = !(*_direction)[i];
deba@416	2399	_graph->nextInc(i, d);
deba@416	2400	while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2401	}
deba@416	2402	void nextOut(Arc& i) const {
deba@416	2403	bool d = (*_direction)[i];
deba@416	2404	_graph->nextInc(i, d);
deba@416	2405	while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2406	}
deba@416	2407
deba@416	2408	Node source(const Arc& e) const {
deba@416	2409	return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
deba@416	2410	}
deba@416	2411	Node target(const Arc& e) const {
deba@416	2412	return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
deba@416	2413	}
deba@416	2414
deba@416	2415	typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@416	2416	int nodeNum() const { return _graph->nodeNum(); }
deba@416	2417
kpeter@446	2418	typedef EdgeNumTagIndicator<Graph> ArcNumTag;
deba@416	2419	int arcNum() const { return _graph->edgeNum(); }
deba@416	2420
kpeter@446	2421	typedef FindEdgeTagIndicator<Graph> FindArcTag;
deba@416	2422	Arc findArc(const Node& u, const Node& v,
kpeter@448	2423	const Arc& prev = INVALID) const {
kpeter@449	2424	Arc arc = _graph->findEdge(u, v, prev);
kpeter@449	2425	while (arc != INVALID && source(arc) != u) {
deba@416	2426	arc = _graph->findEdge(u, v, arc);
deba@414	2427	}
deba@416	2428	return arc;
deba@416	2429	}
deba@416	2430
deba@416	2431	Node addNode() {
deba@416	2432	return Node(_graph->addNode());
deba@416	2433	}
deba@416	2434
deba@416	2435	Arc addArc(const Node& u, const Node& v) {
kpeter@449	2436	Arc arc = _graph->addEdge(u, v);
kpeter@449	2437	_direction->set(arc, _graph->u(arc) == u);
deba@416	2438	return arc;
deba@416	2439	}
deba@416	2440
deba@416	2441	void erase(const Node& i) { _graph->erase(i); }
deba@416	2442	void erase(const Arc& i) { _graph->erase(i); }
deba@416	2443
deba@416	2444	void clear() { _graph->clear(); }
deba@416	2445
deba@416	2446	int id(const Node& v) const { return _graph->id(v); }
deba@416	2447	int id(const Arc& e) const { return _graph->id(e); }
deba@416	2448
deba@416	2449	Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
deba@416	2450	Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
deba@416	2451
deba@416	2452	int maxNodeId() const { return _graph->maxNodeId(); }
deba@416	2453	int maxArcId() const { return _graph->maxEdgeId(); }
deba@416	2454
deba@512	2455	typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@416	2456	NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
deba@416	2457
deba@512	2458	typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
deba@416	2459	ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
deba@416	2460
deba@512	2461	template <typename V>
deba@512	2462	class NodeMap : public GR::template NodeMap<V> {
kpeter@617	2463	typedef typename GR::template NodeMap<V> Parent;
kpeter@617	2464
deba@416	2465	public:
deba@416	2466
deba@512	2467	explicit NodeMap(const OrienterBase<GR, DM>& adapter)
deba@416	2468	: Parent(*adapter._graph) {}
deba@416	2469
deba@512	2470	NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
deba@416	2471	: Parent(*adapter._graph, value) {}
deba@416	2472
deba@416	2473	private:
deba@416	2474	NodeMap& operator=(const NodeMap& cmap) {
deba@416	2475	return operator=<NodeMap>(cmap);
deba@416	2476	}
deba@416	2477
deba@416	2478	template <typename CMap>
deba@416	2479	NodeMap& operator=(const CMap& cmap) {
deba@416	2480	Parent::operator=(cmap);
deba@416	2481	return *this;
deba@416	2482	}
deba@414	2483
deba@414	2484	};
deba@414	2485
deba@512	2486	template <typename V>
deba@512	2487	class ArcMap : public GR::template EdgeMap<V> {
kpeter@617	2488	typedef typename Graph::template EdgeMap<V> Parent;
kpeter@617	2489
deba@416	2490	public:
deba@416	2491
deba@512	2492	explicit ArcMap(const OrienterBase<GR, DM>& adapter)
deba@416	2493	: Parent(*adapter._graph) { }
deba@416	2494
deba@512	2495	ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
deba@416	2496	: Parent(*adapter._graph, value) { }
deba@416	2497
deba@416	2498	private:
deba@416	2499	ArcMap& operator=(const ArcMap& cmap) {
deba@416	2500	return operator=<ArcMap>(cmap);
deba@416	2501	}
deba@416	2502
deba@416	2503	template <typename CMap>
deba@416	2504	ArcMap& operator=(const CMap& cmap) {
deba@416	2505	Parent::operator=(cmap);
deba@416	2506	return *this;
deba@416	2507	}
deba@416	2508	};
deba@416	2509
deba@416	2510
deba@416	2511
deba@416	2512	protected:
deba@416	2513	Graph* _graph;
deba@512	2514	DM* _direction;
deba@512	2515
deba@512	2516	void initialize(GR& graph, DM& direction) {
deba@512	2517	_graph = &graph;
deba@416	2518	_direction = &direction;
deba@416	2519	}
deba@416	2520
deba@414	2521	};
deba@414	2522
deba@416	2523	/// \ingroup graph_adaptors
deba@414	2524	///
kpeter@451	2525	/// \brief Adaptor class for orienting the edges of a graph to get a digraph
deba@416	2526	///
kpeter@451	2527	/// Orienter adaptor can be used for orienting the edges of a graph to
kpeter@451	2528	/// get a digraph. A \c bool edge map of the underlying graph must be
kpeter@451	2529	/// specified, which define the direction of the arcs in the adaptor.
kpeter@451	2530	/// The arcs can be easily reversed by the \c reverseArc() member function
kpeter@451	2531	/// of the adaptor.
kpeter@451	2532	/// This class conforms to the \ref concepts::Digraph "Digraph" concept.
deba@416	2533	///
kpeter@451	2534	/// The adapted graph can also be modified through this adaptor
kpeter@453	2535	/// by adding or removing nodes or arcs, unless the \c GR template
kpeter@451	2536	/// parameter is set to be \c const.
deba@416	2537	///
kpeter@453	2538	/// \tparam GR The type of the adapted graph.
kpeter@451	2539	/// It must conform to the \ref concepts::Graph "Graph" concept.
kpeter@451	2540	/// It can also be specified to be \c const.
kpeter@453	2541	/// \tparam DM The type of the direction map.
kpeter@453	2542	/// It must be a \c bool (or convertible) edge map of the
kpeter@453	2543	/// adapted graph. The default type is
kpeter@453	2544	/// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
kpeter@451	2545	///
kpeter@451	2546	/// \note The \c Node type of this adaptor and the adapted graph are
kpeter@451	2547	/// convertible to each other, moreover the \c Arc type of the adaptor
kpeter@451	2548	/// and the \c Edge type of the adapted graph are also convertible to
kpeter@451	2549	/// each other.
kpeter@451	2550	#ifdef DOXYGEN
kpeter@453	2551	template<typename GR,
kpeter@453	2552	typename DM>
kpeter@453	2553	class Orienter {
kpeter@451	2554	#else
kpeter@453	2555	template<typename GR,
kpeter@453	2556	typename DM = typename GR::template EdgeMap<bool> >
kpeter@453	2557	class Orienter :
kpeter@453	2558	public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
kpeter@451	2559	#endif
kpeter@617	2560	typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
deba@416	2561	public:
kpeter@451	2562
kpeter@451	2563	/// The type of the adapted graph.
kpeter@453	2564	typedef GR Graph;
kpeter@451	2565	/// The type of the direction edge map.
kpeter@453	2566	typedef DM DirectionMap;
kpeter@453	2567
deba@416	2568	typedef typename Parent::Arc Arc;
kpeter@617	2569
deba@416	2570	protected:
deba@416	2571	Orienter() { }
kpeter@617	2572
deba@416	2573	public:
deba@416	2574
kpeter@451	2575	/// \brief Constructor
deba@416	2576	///
kpeter@451	2577	/// Constructor of the adaptor.
deba@512	2578	Orienter(GR& graph, DM& direction) {
deba@512	2579	Parent::initialize(graph, direction);
deba@416	2580	}
deba@416	2581
kpeter@451	2582	/// \brief Reverses the given arc
deba@416	2583	///
kpeter@451	2584	/// This function reverses the given arc.
kpeter@451	2585	/// It is done by simply negate the assigned value of \c a
kpeter@451	2586	/// in the direction map.
deba@416	2587	void reverseArc(const Arc& a) {
deba@416	2588	Parent::reverseArc(a);
deba@416	2589	}
deba@416	2590	};
deba@416	2591
kpeter@451	2592	/// \brief Returns a read-only Orienter adaptor
deba@416	2593	///
kpeter@451	2594	/// This function just returns a read-only \ref Orienter adaptor.
kpeter@451	2595	/// \ingroup graph_adaptors
kpeter@451	2596	/// \relates Orienter
kpeter@453	2597	template<typename GR, typename DM>
kpeter@453	2598	Orienter<const GR, DM>
deba@512	2599	orienter(const GR& graph, DM& direction) {
deba@512	2600	return Orienter<const GR, DM>(graph, direction);
deba@414	2601	}
deba@414	2602
kpeter@453	2603	template<typename GR, typename DM>
kpeter@453	2604	Orienter<const GR, const DM>
deba@512	2605	orienter(const GR& graph, const DM& direction) {
deba@512	2606	return Orienter<const GR, const DM>(graph, direction);
deba@416	2607	}
deba@416	2608
deba@416	2609	namespace _adaptor_bits {
deba@416	2610
deba@512	2611	template <typename DGR, typename CM, typename FM, typename TL>
deba@416	2612	class ResForwardFilter {
deba@416	2613	public:
deba@416	2614
deba@512	2615	typedef typename DGR::Arc Key;
deba@416	2616	typedef bool Value;
deba@416	2617
deba@416	2618	private:
deba@416	2619
deba@512	2620	const CM* _capacity;
deba@512	2621	const FM* _flow;
deba@512	2622	TL _tolerance;
deba@512	2623
deba@416	2624	public:
deba@416	2625
deba@512	2626	ResForwardFilter(const CM& capacity, const FM& flow,
deba@512	2627	const TL& tolerance = TL())
deba@416	2628	: _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416	2629
deba@512	2630	bool operator[](const typename DGR::Arc& a) const {
deba@416	2631	return _tolerance.positive((_capacity)[a] - (_flow)[a]);
deba@416	2632	}
deba@416	2633	};
deba@416	2634
deba@512	2635	template<typename DGR,typename CM, typename FM, typename TL>
deba@416	2636	class ResBackwardFilter {
deba@416	2637	public:
deba@416	2638
deba@512	2639	typedef typename DGR::Arc Key;
deba@416	2640	typedef bool Value;
deba@416	2641
deba@416	2642	private:
deba@416	2643
deba@512	2644	const CM* _capacity;
deba@512	2645	const FM* _flow;
deba@512	2646	TL _tolerance;
deba@416	2647
deba@416	2648	public:
deba@416	2649
deba@512	2650	ResBackwardFilter(const CM& capacity, const FM& flow,
deba@512	2651	const TL& tolerance = TL())
deba@416	2652	: _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416	2653
deba@512	2654	bool operator[](const typename DGR::Arc& a) const {
deba@416	2655	return _tolerance.positive((*_flow)[a]);
deba@416	2656	}
deba@416	2657	};
deba@416	2658
deba@416	2659	}
deba@416	2660
deba@416	2661	/// \ingroup graph_adaptors
deba@416	2662	///
kpeter@451	2663	/// \brief Adaptor class for composing the residual digraph for directed
deba@416	2664	/// flow and circulation problems.
deba@416	2665	///
kpeter@464	2666	/// ResidualDigraph can be used for composing the \e residual digraph
kpeter@464	2667	/// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
kpeter@464	2668	/// be a directed graph and let \f$ F \f$ be a number type.
kpeter@464	2669	/// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
kpeter@451	2670	/// This adaptor implements a digraph structure with node set \f$ V \f$
kpeter@451	2671	/// and arc set \f$ A_{forward}\cup A_{backward} \f$,
kpeter@451	2672	/// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
kpeter@451	2673	/// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
kpeter@451	2674	/// called residual digraph.
kpeter@451	2675	/// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
kpeter@451	2676	/// multiplicities are counted, i.e. the adaptor has exactly
kpeter@451	2677	/// \f$ \|A_{forward}\| + \|A_{backward}\|\f$ arcs (it may have parallel
kpeter@451	2678	/// arcs).
kpeter@451	2679	/// This class conforms to the \ref concepts::Digraph "Digraph" concept.
deba@416	2680	///
deba@512	2681	/// \tparam DGR The type of the adapted digraph.
kpeter@451	2682	/// It must conform to the \ref concepts::Digraph "Digraph" concept.
kpeter@451	2683	/// It is implicitly \c const.
kpeter@453	2684	/// \tparam CM The type of the capacity map.
kpeter@453	2685	/// It must be an arc map of some numerical type, which defines
kpeter@451	2686	/// the capacities in the flow problem. It is implicitly \c const.
kpeter@453	2687	/// The default type is
kpeter@453	2688	/// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
kpeter@453	2689	/// \tparam FM The type of the flow map.
kpeter@453	2690	/// It must be an arc map of some numerical type, which defines
kpeter@453	2691	/// the flow values in the flow problem. The default type is \c CM.
kpeter@453	2692	/// \tparam TL The tolerance type for handling inexact computation.
kpeter@451	2693	/// The default tolerance type depends on the value type of the
kpeter@451	2694	/// capacity map.
deba@416	2695	///
kpeter@451	2696	/// \note This adaptor is implemented using Undirector and FilterArcs
kpeter@451	2697	/// adaptors.
kpeter@451	2698	///
kpeter@451	2699	/// \note The \c Node type of this adaptor and the adapted digraph are
kpeter@451	2700	/// convertible to each other, moreover the \c Arc type of the adaptor
kpeter@451	2701	/// is convertible to the \c Arc type of the adapted digraph.
kpeter@451	2702	#ifdef DOXYGEN
deba@512	2703	template<typename DGR, typename CM, typename FM, typename TL>
kpeter@464	2704	class ResidualDigraph
kpeter@451	2705	#else
deba@512	2706	template<typename DGR,
deba@512	2707	typename CM = typename DGR::template ArcMap<int>,
kpeter@453	2708	typename FM = CM,
kpeter@453	2709	typename TL = Tolerance<typename CM::Value> >
deba@512	2710	class ResidualDigraph
deba@512	2711	: public SubDigraph<
deba@512	2712	Undirector<const DGR>,
deba@512	2713	ConstMap<typename DGR::Node, Const<bool, true> >,
deba@512	2714	typename Undirector<const DGR>::template CombinedArcMap<
deba@512	2715	_adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
deba@512	2716	_adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
kpeter@451	2717	#endif
deba@416	2718	{
deba@414	2719	public:
deba@414	2720
kpeter@451	2721	/// The type of the underlying digraph.
deba@512	2722	typedef DGR Digraph;
kpeter@451	2723	/// The type of the capacity map.
kpeter@453	2724	typedef CM CapacityMap;
kpeter@451	2725	/// The type of the flow map.
kpeter@453	2726	typedef FM FlowMap;
kpeter@453	2727	/// The tolerance type.
kpeter@453	2728	typedef TL Tolerance;
deba@414	2729
deba@414	2730	typedef typename CapacityMap::Value Value;
kpeter@464	2731	typedef ResidualDigraph Adaptor;
deba@414	2732
deba@414	2733	protected:
deba@414	2734
deba@416	2735	typedef Undirector<const Digraph> Undirected;
deba@416	2736
deba@512	2737	typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
deba@512	2738
deba@512	2739	typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
deba@512	2740	FM, TL> ForwardFilter;
deba@512	2741
deba@512	2742	typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
deba@512	2743	FM, TL> BackwardFilter;
deba@416	2744
deba@416	2745	typedef typename Undirected::
kpeter@453	2746	template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
deba@414	2747
deba@512	2748	typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
deba@414	2749
deba@414	2750	const CapacityMap* _capacity;
deba@414	2751	FlowMap* _flow;
deba@414	2752
deba@416	2753	Undirected _graph;
deba@512	2754	NodeFilter _node_filter;
deba@414	2755	ForwardFilter _forward_filter;
deba@414	2756	BackwardFilter _backward_filter;
deba@414	2757	ArcFilter _arc_filter;
deba@414	2758
deba@414	2759	public:
deba@414	2760
kpeter@451	2761	/// \brief Constructor
deba@414	2762	///
kpeter@451	2763	/// Constructor of the residual digraph adaptor. The parameters are the
kpeter@451	2764	/// digraph, the capacity map, the flow map, and a tolerance object.
deba@512	2765	ResidualDigraph(const DGR& digraph, const CM& capacity,
deba@512	2766	FM& flow, const TL& tolerance = Tolerance())
deba@512	2767	: Parent(), _capacity(&capacity), _flow(&flow),
deba@512	2768	_graph(digraph), _node_filter(),
deba@416	2769	_forward_filter(capacity, flow, tolerance),
deba@414	2770	_backward_filter(capacity, flow, tolerance),
deba@414	2771	_arc_filter(_forward_filter, _backward_filter)
deba@414	2772	{
deba@512	2773	Parent::initialize(_graph, _node_filter, _arc_filter);
deba@414	2774	}
deba@414	2775
deba@414	2776	typedef typename Parent::Arc Arc;
deba@414	2777
kpeter@451	2778	/// \brief Returns the residual capacity of the given arc.
deba@414	2779	///
kpeter@451	2780	/// Returns the residual capacity of the given arc.
deba@416	2781	Value residualCapacity(const Arc& a) const {
deba@416	2782	if (Undirected::direction(a)) {
deba@416	2783	return (_capacity)[a] - (_flow)[a];
deba@414	2784	} else {
deba@416	2785	return (*_flow)[a];
deba@414	2786	}
deba@416	2787	}
deba@416	2788
kpeter@452	2789	/// \brief Augments on the given arc in the residual digraph.
deba@414	2790	///
kpeter@452	2791	/// Augments on the given arc in the residual digraph. It increases
kpeter@451	2792	/// or decreases the flow value on the original arc according to the
kpeter@451	2793	/// direction of the residual arc.
deba@416	2794	void augment(const Arc& a, const Value& v) const {
deba@416	2795	if (Undirected::direction(a)) {
deba@416	2796	_flow->set(a, (*_flow)[a] + v);
deba@416	2797	} else {
deba@416	2798	_flow->set(a, (*_flow)[a] - v);
deba@414	2799	}
deba@414	2800	}
deba@414	2801
kpeter@451	2802	/// \brief Returns \c true if the given residual arc is a forward arc.
deba@414	2803	///
kpeter@451	2804	/// Returns \c true if the given residual arc has the same orientation
kpeter@451	2805	/// as the original arc, i.e. it is a so called forward arc.
deba@416	2806	static bool forward(const Arc& a) {
deba@416	2807	return Undirected::direction(a);
deba@414	2808	}
deba@414	2809
kpeter@451	2810	/// \brief Returns \c true if the given residual arc is a backward arc.
deba@414	2811	///
kpeter@451	2812	/// Returns \c true if the given residual arc has the opposite orientation
kpeter@451	2813	/// than the original arc, i.e. it is a so called backward arc.
deba@416	2814	static bool backward(const Arc& a) {
deba@416	2815	return !Undirected::direction(a);
deba@414	2816	}
deba@414	2817
kpeter@451	2818	/// \brief Returns the forward oriented residual arc.
deba@414	2819	///
kpeter@451	2820	/// Returns the forward oriented residual arc related to the given
kpeter@451	2821	/// arc of the underlying digraph.
deba@416	2822	static Arc forward(const typename Digraph::Arc& a) {
deba@416	2823	return Undirected::direct(a, true);
deba@414	2824	}
deba@414	2825
kpeter@451	2826	/// \brief Returns the backward oriented residual arc.
deba@414	2827	///
kpeter@451	2828	/// Returns the backward oriented residual arc related to the given
kpeter@451	2829	/// arc of the underlying digraph.
deba@416	2830	static Arc backward(const typename Digraph::Arc& a) {
deba@416	2831	return Undirected::direct(a, false);
deba@414	2832	}
deba@414	2833
deba@414	2834	/// \brief Residual capacity map.
deba@414	2835	///
kpeter@451	2836	/// This map adaptor class can be used for obtaining the residual
kpeter@451	2837	/// capacities as an arc map of the residual digraph.
kpeter@451	2838	/// Its value type is inherited from the capacity map.
deba@416	2839	class ResidualCapacity {
deba@414	2840	protected:
deba@414	2841	const Adaptor* _adaptor;
deba@414	2842	public:
kpeter@451	2843	/// The key type of the map
deba@414	2844	typedef Arc Key;
kpeter@451	2845	/// The value type of the map
kpeter@453	2846	typedef typename CapacityMap::Value Value;
deba@414	2847
deba@416	2848	/// Constructor
deba@512	2849	ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
deba@512	2850	: _adaptor(&adaptor) {}
deba@416	2851
kpeter@451	2852	/// Returns the value associated with the given residual arc
deba@416	2853	Value operator[](const Arc& a) const {
deba@416	2854	return _adaptor->residualCapacity(a);
deba@414	2855	}
deba@416	2856
deba@414	2857	};
deba@414	2858
kpeter@450	2859	/// \brief Returns a residual capacity map
kpeter@450	2860	///
kpeter@450	2861	/// This function just returns a residual capacity map.
kpeter@450	2862	ResidualCapacity residualCapacity() const {
kpeter@450	2863	return ResidualCapacity(*this);
kpeter@450	2864	}
kpeter@450	2865
deba@414	2866	};
deba@414	2867
kpeter@450	2868	/// \brief Returns a (read-only) Residual adaptor
kpeter@450	2869	///
deba@512	2870	/// This function just returns a (read-only) \ref ResidualDigraph adaptor.
kpeter@450	2871	/// \ingroup graph_adaptors
deba@512	2872	/// \relates ResidualDigraph
deba@512	2873	template<typename DGR, typename CM, typename FM>
deba@512	2874	ResidualDigraph<DGR, CM, FM>
deba@512	2875	residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
deba@512	2876	return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
kpeter@450	2877	}
kpeter@450	2878
kpeter@450	2879
deba@512	2880	template <typename DGR>
deba@416	2881	class SplitNodesBase {
kpeter@617	2882	typedef DigraphAdaptorBase<const DGR> Parent;
kpeter@617	2883
deba@414	2884	public:
deba@414	2885
deba@512	2886	typedef DGR Digraph;
deba@416	2887	typedef SplitNodesBase Adaptor;
deba@414	2888
deba@512	2889	typedef typename DGR::Node DigraphNode;
deba@512	2890	typedef typename DGR::Arc DigraphArc;
deba@414	2891
deba@414	2892	class Node;
deba@414	2893	class Arc;
deba@414	2894
deba@414	2895	private:
deba@414	2896
deba@414	2897	template <typename T> class NodeMapBase;
deba@414	2898	template <typename T> class ArcMapBase;
deba@414	2899
deba@414	2900	public:
deba@416	2901
deba@414	2902	class Node : public DigraphNode {
deba@416	2903	friend class SplitNodesBase;
deba@414	2904	template <typename T> friend class NodeMapBase;
deba@414	2905	private:
deba@414	2906
deba@414	2907	bool _in;
deba@414	2908	Node(DigraphNode node, bool in)
deba@416	2909	: DigraphNode(node), _in(in) {}
deba@416	2910
deba@414	2911	public:
deba@414	2912
deba@414	2913	Node() {}
deba@414	2914	Node(Invalid) : DigraphNode(INVALID), _in(true) {}
deba@414	2915
deba@414	2916	bool operator==(const Node& node) const {
deba@416	2917	return DigraphNode::operator==(node) && _in == node._in;
deba@414	2918	}
deba@416	2919
deba@414	2920	bool operator!=(const Node& node) const {
deba@416	2921	return !(*this == node);
deba@414	2922	}
deba@416	2923
deba@414	2924	bool operator<(const Node& node) const {
deba@416	2925	return DigraphNode::operator<(node) \|\|
deba@416	2926	(DigraphNode::operator==(node) && _in < node._in);
deba@414	2927	}
deba@414	2928	};
deba@414	2929
deba@414	2930	class Arc {
deba@416	2931	friend class SplitNodesBase;
deba@414	2932	template <typename T> friend class ArcMapBase;
deba@414	2933	private:
deba@414	2934	typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
deba@414	2935
deba@414	2936	explicit Arc(const DigraphArc& arc) : _item(arc) {}
deba@414	2937	explicit Arc(const DigraphNode& node) : _item(node) {}
deba@416	2938
deba@414	2939	ArcImpl _item;
deba@414	2940
deba@414	2941	public:
deba@414	2942	Arc() {}
deba@414	2943	Arc(Invalid) : _item(DigraphArc(INVALID)) {}
deba@414	2944
deba@414	2945	bool operator==(const Arc& arc) const {
deba@414	2946	if (_item.firstState()) {
deba@414	2947	if (arc._item.firstState()) {
deba@414	2948	return _item.first() == arc._item.first();
deba@414	2949	}
deba@414	2950	} else {
deba@414	2951	if (arc._item.secondState()) {
deba@414	2952	return _item.second() == arc._item.second();
deba@414	2953	}
deba@414	2954	}
deba@414	2955	return false;
deba@414	2956	}
deba@416	2957
deba@414	2958	bool operator!=(const Arc& arc) const {
deba@416	2959	return !(*this == arc);
deba@414	2960	}
deba@416	2961
deba@414	2962	bool operator<(const Arc& arc) const {
deba@414	2963	if (_item.firstState()) {
deba@414	2964	if (arc._item.firstState()) {
deba@414	2965	return _item.first() < arc._item.first();
deba@414	2966	}
deba@414	2967	return false;
deba@414	2968	} else {
deba@414	2969	if (arc._item.secondState()) {
deba@414	2970	return _item.second() < arc._item.second();
deba@414	2971	}
deba@414	2972	return true;
deba@414	2973	}
deba@414	2974	}
deba@414	2975
deba@414	2976	operator DigraphArc() const { return _item.first(); }
deba@414	2977	operator DigraphNode() const { return _item.second(); }
deba@414	2978
deba@414	2979	};
deba@414	2980
deba@414	2981	void first(Node& n) const {
deba@414	2982	_digraph->first(n);
deba@414	2983	n._in = true;
deba@414	2984	}
deba@414	2985
deba@414	2986	void next(Node& n) const {
deba@414	2987	if (n._in) {
deba@416	2988	n._in = false;
deba@414	2989	} else {
deba@416	2990	n._in = true;
deba@416	2991	_digraph->next(n);
deba@414	2992	}
deba@414	2993	}
deba@414	2994
deba@414	2995	void first(Arc& e) const {
deba@414	2996	e._item.setSecond();
deba@414	2997	_digraph->first(e._item.second());
deba@414	2998	if (e._item.second() == INVALID) {
deba@414	2999	e._item.setFirst();
deba@416	3000	_digraph->first(e._item.first());
deba@414	3001	}
deba@414	3002	}
deba@414	3003
deba@414	3004	void next(Arc& e) const {
deba@414	3005	if (e._item.secondState()) {
deba@416	3006	_digraph->next(e._item.second());
deba@414	3007	if (e._item.second() == INVALID) {
deba@414	3008	e._item.setFirst();
deba@414	3009	_digraph->first(e._item.first());
deba@414	3010	}
deba@414	3011	} else {
deba@416	3012	_digraph->next(e._item.first());
deba@416	3013	}
deba@414	3014	}
deba@414	3015
deba@414	3016	void firstOut(Arc& e, const Node& n) const {
deba@414	3017	if (n._in) {
deba@414	3018	e._item.setSecond(n);
deba@414	3019	} else {
deba@414	3020	e._item.setFirst();
deba@416	3021	_digraph->firstOut(e._item.first(), n);
deba@414	3022	}
deba@414	3023	}
deba@414	3024
deba@414	3025	void nextOut(Arc& e) const {
deba@414	3026	if (!e._item.firstState()) {
deba@416	3027	e._item.setFirst(INVALID);
deba@414	3028	} else {
deba@416	3029	_digraph->nextOut(e._item.first());
deba@416	3030	}
deba@414	3031	}
deba@414	3032
deba@414	3033	void firstIn(Arc& e, const Node& n) const {
deba@414	3034	if (!n._in) {
deba@416	3035	e._item.setSecond(n);
deba@414	3036	} else {
deba@414	3037	e._item.setFirst();
deba@416	3038	_digraph->firstIn(e._item.first(), n);
deba@414	3039	}
deba@414	3040	}
deba@414	3041
deba@414	3042	void nextIn(Arc& e) const {
deba@414	3043	if (!e._item.firstState()) {
deba@416	3044	e._item.setFirst(INVALID);
deba@414	3045	} else {
deba@416	3046	_digraph->nextIn(e._item.first());
deba@414	3047	}
deba@414	3048	}
deba@414	3049
deba@414	3050	Node source(const Arc& e) const {
deba@414	3051	if (e._item.firstState()) {
deba@416	3052	return Node(_digraph->source(e._item.first()), false);
deba@414	3053	} else {
deba@416	3054	return Node(e._item.second(), true);
deba@414	3055	}
deba@414	3056	}
deba@414	3057
deba@414	3058	Node target(const Arc& e) const {
deba@414	3059	if (e._item.firstState()) {
deba@416	3060	return Node(_digraph->target(e._item.first()), true);
deba@414	3061	} else {
deba@416	3062	return Node(e._item.second(), false);
deba@414	3063	}
deba@414	3064	}
deba@414	3065
deba@414	3066	int id(const Node& n) const {
deba@414	3067	return (_digraph->id(n) << 1) \| (n._in ? 0 : 1);
deba@414	3068	}
deba@414	3069	Node nodeFromId(int ix) const {
deba@414	3070	return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
deba@414	3071	}
deba@414	3072	int maxNodeId() const {
deba@414	3073	return 2 * _digraph->maxNodeId() + 1;
deba@414	3074	}
deba@414	3075
deba@414	3076	int id(const Arc& e) const {
deba@414	3077	if (e._item.firstState()) {
deba@414	3078	return _digraph->id(e._item.first()) << 1;
deba@414	3079	} else {
deba@414	3080	return (_digraph->id(e._item.second()) << 1) \| 1;
deba@414	3081	}
deba@414	3082	}
deba@414	3083	Arc arcFromId(int ix) const {
deba@414	3084	if ((ix & 1) == 0) {
deba@414	3085	return Arc(_digraph->arcFromId(ix >> 1));
deba@414	3086	} else {
deba@414	3087	return Arc(_digraph->nodeFromId(ix >> 1));
deba@414	3088	}
deba@414	3089	}
deba@414	3090	int maxArcId() const {
deba@416	3091	return std::max(_digraph->maxNodeId() << 1,
deba@414	3092	(_digraph->maxArcId() << 1) \| 1);
deba@414	3093	}
deba@414	3094
deba@414	3095	static bool inNode(const Node& n) {
deba@414	3096	return n._in;
deba@414	3097	}
deba@414	3098
deba@414	3099	static bool outNode(const Node& n) {
deba@414	3100	return !n._in;
deba@414	3101	}
deba@414	3102
deba@414	3103	static bool origArc(const Arc& e) {
deba@414	3104	return e._item.firstState();
deba@414	3105	}
deba@414	3106
deba@414	3107	static bool bindArc(const Arc& e) {
deba@414	3108	return e._item.secondState();
deba@414	3109	}
deba@414	3110
deba@414	3111	static Node inNode(const DigraphNode& n) {
deba@414	3112	return Node(n, true);
deba@414	3113	}
deba@414	3114
deba@414	3115	static Node outNode(const DigraphNode& n) {
deba@414	3116	return Node(n, false);
deba@414	3117	}
deba@414	3118
deba@414	3119	static Arc arc(const DigraphNode& n) {
deba@414	3120	return Arc(n);
deba@414	3121	}
deba@414	3122
deba@414	3123	static Arc arc(const DigraphArc& e) {
deba@414	3124	return Arc(e);
deba@414	3125	}
deba@414	3126
deba@414	3127	typedef True NodeNumTag;
deba@414	3128	int nodeNum() const {
deba@414	3129	return 2 * countNodes(*_digraph);
deba@414	3130	}
deba@414	3131
kpeter@446	3132	typedef True ArcNumTag;
deba@414	3133	int arcNum() const {
deba@414	3134	return countArcs(_digraph) + countNodes(_digraph);
deba@414	3135	}
deba@414	3136
kpeter@446	3137	typedef True FindArcTag;
deba@416	3138	Arc findArc(const Node& u, const Node& v,
deba@416	3139	const Arc& prev = INVALID) const {
kpeter@449	3140	if (inNode(u) && outNode(v)) {
kpeter@449	3141	if (static_cast<const DigraphNode&>(u) ==
kpeter@449	3142	static_cast<const DigraphNode&>(v) && prev == INVALID) {
kpeter@449	3143	return Arc(u);
deba@414	3144	}
kpeter@449	3145	}
kpeter@449	3146	else if (outNode(u) && inNode(v)) {
kpeter@449	3147	return Arc(::lemon::findArc(*_digraph, u, v, prev));
deba@414	3148	}
deba@414	3149	return INVALID;
deba@414	3150	}
deba@414	3151
deba@414	3152	private:
deba@416	3153
deba@512	3154	template <typename V>
deba@416	3155	class NodeMapBase
deba@512	3156	: public MapTraits<typename Parent::template NodeMap<V> > {
deba@512	3157	typedef typename Parent::template NodeMap<V> NodeImpl;
deba@414	3158	public:
deba@414	3159	typedef Node Key;
deba@512	3160	typedef V Value;
kpeter@449	3161	typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
kpeter@449	3162	typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
kpeter@449	3163	typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
kpeter@449	3164	typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
kpeter@449	3165	typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
deba@416	3166
deba@512	3167	NodeMapBase(const SplitNodesBase<DGR>& adaptor)
deba@416	3168	: _in_map(adaptor._digraph), _out_map(adaptor._digraph) {}
deba@512	3169	NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
deba@416	3170	: _in_map(*adaptor._digraph, value),
deba@416	3171	_out_map(*adaptor._digraph, value) {}
deba@414	3172
deba@512	3173	void set(const Node& key, const V& val) {
deba@512	3174	if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
deba@416	3175	else {_out_map.set(key, val); }
deba@414	3176	}
deba@416	3177
kpeter@449	3178	ReturnValue operator[](const Node& key) {
deba@512	3179	if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
deba@416	3180	else { return _out_map[key]; }
deba@414	3181	}
deba@414	3182
kpeter@449	3183	ConstReturnValue operator[](const Node& key) const {
deba@416	3184	if (Adaptor::inNode(key)) { return _in_map[key]; }
deba@416	3185	else { return _out_map[key]; }
deba@414	3186	}
deba@414	3187
deba@414	3188	private:
deba@414	3189	NodeImpl _in_map, _out_map;
deba@414	3190	};
deba@414	3191
deba@512	3192	template <typename V>
deba@416	3193	class ArcMapBase
deba@512	3194	: public MapTraits<typename Parent::template ArcMap<V> > {
deba@512	3195	typedef typename Parent::template ArcMap<V> ArcImpl;
deba@512	3196	typedef typename Parent::template NodeMap<V> NodeImpl;
deba@414	3197	public:
deba@414	3198	typedef Arc Key;
deba@512	3199	typedef V Value;
kpeter@449	3200	typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
kpeter@449	3201	typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
kpeter@449	3202	typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
kpeter@449	3203	typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
kpeter@449	3204	typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
deba@414	3205
deba@512	3206	ArcMapBase(const SplitNodesBase<DGR>& adaptor)
deba@416	3207	: _arc_map(adaptor._digraph), _node_map(adaptor._digraph) {}
deba@512	3208	ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
deba@416	3209	: _arc_map(*adaptor._digraph, value),
deba@416	3210	_node_map(*adaptor._digraph, value) {}
deba@414	3211
deba@512	3212	void set(const Arc& key, const V& val) {
deba@512	3213	if (SplitNodesBase<DGR>::origArc(key)) {
kpeter@516	3214	_arc_map.set(static_cast<const DigraphArc&>(key), val);
deba@414	3215	} else {
kpeter@516	3216	_node_map.set(static_cast<const DigraphNode&>(key), val);
deba@414	3217	}
deba@414	3218	}
deba@416	3219
kpeter@449	3220	ReturnValue operator[](const Arc& key) {
deba@512	3221	if (SplitNodesBase<DGR>::origArc(key)) {
kpeter@516	3222	return _arc_map[static_cast<const DigraphArc&>(key)];
deba@414	3223	} else {
kpeter@516	3224	return _node_map[static_cast<const DigraphNode&>(key)];
deba@414	3225	}
deba@414	3226	}
deba@414	3227
kpeter@449	3228	ConstReturnValue operator[](const Arc& key) const {
deba@512	3229	if (SplitNodesBase<DGR>::origArc(key)) {
kpeter@516	3230	return _arc_map[static_cast<const DigraphArc&>(key)];
deba@414	3231	} else {
kpeter@516	3232	return _node_map[static_cast<const DigraphNode&>(key)];
deba@414	3233	}
deba@414	3234	}
deba@414	3235
deba@414	3236	private:
deba@414	3237	ArcImpl _arc_map;
deba@414	3238	NodeImpl _node_map;
deba@414	3239	};
deba@414	3240
deba@414	3241	public:
deba@414	3242
deba@512	3243	template <typename V>
deba@416	3244	class NodeMap
kpeter@617	3245	: public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
kpeter@617	3246	typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
kpeter@617	3247
deba@414	3248	public:
deba@512	3249	typedef V Value;
deba@512	3250
deba@512	3251	NodeMap(const SplitNodesBase<DGR>& adaptor)
deba@416	3252	: Parent(adaptor) {}
deba@416	3253
deba@512	3254	NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
deba@416	3255	: Parent(adaptor, value) {}
deba@416	3256
deba@414	3257	private:
deba@414	3258	NodeMap& operator=(const NodeMap& cmap) {
deba@416	3259	return operator=<NodeMap>(cmap);
deba@414	3260	}
deba@416	3261
deba@414	3262	template <typename CMap>
deba@414	3263	NodeMap& operator=(const CMap& cmap) {
deba@414	3264	Parent::operator=(cmap);
deba@416	3265	return *this;
deba@414	3266	}
deba@414	3267	};
deba@414	3268
deba@512	3269	template <typename V>
deba@416	3270	class ArcMap
kpeter@617	3271	: public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
kpeter@617	3272	typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
kpeter@617	3273
deba@414	3274	public:
deba@512	3275	typedef V Value;
deba@512	3276
deba@512	3277	ArcMap(const SplitNodesBase<DGR>& adaptor)
deba@416	3278	: Parent(adaptor) {}
deba@416	3279
deba@512	3280	ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
deba@416	3281	: Parent(adaptor, value) {}
deba@416	3282
deba@414	3283	private:
deba@414	3284	ArcMap& operator=(const ArcMap& cmap) {
deba@416	3285	return operator=<ArcMap>(cmap);
deba@414	3286	}
deba@416	3287
deba@414	3288	template <typename CMap>
deba@414	3289	ArcMap& operator=(const CMap& cmap) {
deba@414	3290	Parent::operator=(cmap);
deba@416	3291	return *this;
deba@414	3292	}
deba@414	3293	};
deba@414	3294
deba@414	3295	protected:
deba@414	3296
deba@416	3297	SplitNodesBase() : _digraph(0) {}
deba@414	3298
deba@512	3299	DGR* _digraph;
deba@512	3300
deba@512	3301	void initialize(Digraph& digraph) {
deba@414	3302	_digraph = &digraph;
deba@414	3303	}
deba@416	3304
deba@414	3305	};
deba@414	3306
deba@414	3307	/// \ingroup graph_adaptors
deba@414	3308	///
kpeter@451	3309	/// \brief Adaptor class for splitting the nodes of a digraph.
deba@416	3310	///
kpeter@451	3311	/// SplitNodes adaptor can be used for splitting each node into an
kpeter@451	3312	/// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
kpeter@451	3313	/// replaces each node \f$ u \f$ in the digraph with two nodes,
kpeter@451	3314	/// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
kpeter@451	3315	/// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
kpeter@451	3316	/// new target of the arc will be \f$ u_{in} \f$ and similarly the
kpeter@451	3317	/// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
kpeter@451	3318	/// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
kpeter@451	3319	/// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
deba@414	3320	///
kpeter@451	3321	/// The aim of this class is running an algorithm with respect to node
kpeter@451	3322	/// costs or capacities if the algorithm considers only arc costs or
kpeter@451	3323	/// capacities directly.
kpeter@451	3324	/// In this case you can use \c SplitNodes adaptor, and set the node
kpeter@451	3325	/// costs/capacities of the original digraph to the \e bind \e arcs
kpeter@451	3326	/// in the adaptor.
deba@414	3327	///
deba@512	3328	/// \tparam DGR The type of the adapted digraph.
kpeter@451	3329	/// It must conform to the \ref concepts::Digraph "Digraph" concept.
kpeter@451	3330	/// It is implicitly \c const.
kpeter@451	3331	///
kpeter@451	3332	/// \note The \c Node type of this adaptor is converible to the \c Node
kpeter@451	3333	/// type of the adapted digraph.
deba@512	3334	template <typename DGR>
kpeter@453	3335	#ifdef DOXYGEN
kpeter@453	3336	class SplitNodes {
kpeter@453	3337	#else
deba@416	3338	class SplitNodes
deba@512	3339	: public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
kpeter@453	3340	#endif
kpeter@617	3341	typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
kpeter@617	3342
deba@414	3343	public:
deba@512	3344	typedef DGR Digraph;
deba@512	3345
deba@512	3346	typedef typename DGR::Node DigraphNode;
deba@512	3347	typedef typename DGR::Arc DigraphArc;
deba@415	3348
deba@414	3349	typedef typename Parent::Node Node;
deba@414	3350	typedef typename Parent::Arc Arc;
deba@414	3351
kpeter@451	3352	/// \brief Constructor
deba@414	3353	///
deba@414	3354	/// Constructor of the adaptor.
deba@512	3355	SplitNodes(const DGR& g) {
deba@512	3356	Parent::initialize(g);
deba@414	3357	}
deba@414	3358
kpeter@451	3359	/// \brief Returns \c true if the given node is an in-node.
deba@415	3360	///
kpeter@451	3361	/// Returns \c true if the given node is an in-node.
deba@415	3362	static bool inNode(const Node& n) {
deba@415	3363	return Parent::inNode(n);
deba@415	3364	}
deba@415	3365
kpeter@451	3366	/// \brief Returns \c true if the given node is an out-node.
deba@415	3367	///
kpeter@451	3368	/// Returns \c true if the given node is an out-node.
deba@415	3369	static bool outNode(const Node& n) {
deba@415	3370	return Parent::outNode(n);
deba@415	3371	}
deba@415	3372
kpeter@451	3373	/// \brief Returns \c true if the given arc is an original arc.
deba@415	3374	///
kpeter@451	3375	/// Returns \c true if the given arc is one of the arcs in the
kpeter@451	3376	/// original digraph.
deba@415	3377	static bool origArc(const Arc& a) {
deba@415	3378	return Parent::origArc(a);
deba@415	3379	}
deba@415	3380
kpeter@451	3381	/// \brief Returns \c true if the given arc is a bind arc.
deba@415	3382	///
kpeter@451	3383	/// Returns \c true if the given arc is a bind arc, i.e. it connects
kpeter@451	3384	/// an in-node and an out-node.
deba@415	3385	static bool bindArc(const Arc& a) {
deba@415	3386	return Parent::bindArc(a);
deba@415	3387	}
deba@415	3388
kpeter@451	3389	/// \brief Returns the in-node created from the given original node.
deba@415	3390	///
kpeter@451	3391	/// Returns the in-node created from the given original node.
deba@415	3392	static Node inNode(const DigraphNode& n) {
deba@415	3393	return Parent::inNode(n);
deba@415	3394	}
deba@415	3395
kpeter@451	3396	/// \brief Returns the out-node created from the given original node.
deba@415	3397	///
kpeter@451	3398	/// Returns the out-node created from the given original node.
deba@415	3399	static Node outNode(const DigraphNode& n) {
deba@415	3400	return Parent::outNode(n);
deba@415	3401	}
deba@415	3402
kpeter@451	3403	/// \brief Returns the bind arc that corresponds to the given
kpeter@451	3404	/// original node.
deba@416	3405	///
kpeter@451	3406	/// Returns the bind arc in the adaptor that corresponds to the given
kpeter@451	3407	/// original node, i.e. the arc connecting the in-node and out-node
kpeter@451	3408	/// of \c n.
deba@415	3409	static Arc arc(const DigraphNode& n) {
deba@415	3410	return Parent::arc(n);
deba@415	3411	}
deba@415	3412
kpeter@451	3413	/// \brief Returns the arc that corresponds to the given original arc.
deba@416	3414	///
kpeter@451	3415	/// Returns the arc in the adaptor that corresponds to the given
kpeter@451	3416	/// original arc.
deba@415	3417	static Arc arc(const DigraphArc& a) {
deba@415	3418	return Parent::arc(a);
deba@415	3419	}
deba@415	3420
kpeter@451	3421	/// \brief Node map combined from two original node maps
deba@414	3422	///
kpeter@451	3423	/// This map adaptor class adapts two node maps of the original digraph
kpeter@451	3424	/// to get a node map of the split digraph.
kpeter@559	3425	/// Its value type is inherited from the first node map type (\c IN).
kpeter@559	3426	/// \tparam IN The type of the node map for the in-nodes.
kpeter@559	3427	/// \tparam OUT The type of the node map for the out-nodes.
kpeter@559	3428	template <typename IN, typename OUT>
deba@414	3429	class CombinedNodeMap {
deba@414	3430	public:
deba@414	3431
kpeter@451	3432	/// The key type of the map
deba@414	3433	typedef Node Key;
kpeter@451	3434	/// The value type of the map
kpeter@559	3435	typedef typename IN::Value Value;
kpeter@559	3436
kpeter@559	3437	typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
kpeter@559	3438	typedef typename MapTraits<IN>::ReturnValue ReturnValue;
kpeter@559	3439	typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
kpeter@559	3440	typedef typename MapTraits<IN>::ReturnValue Reference;
kpeter@559	3441	typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
kpeter@449	3442
kpeter@451	3443	/// Constructor
kpeter@559	3444	CombinedNodeMap(IN& in_map, OUT& out_map)
deba@416	3445	: _in_map(in_map), _out_map(out_map) {}
deba@414	3446
kpeter@451	3447	/// Returns the value associated with the given key.
kpeter@451	3448	Value operator[](const Key& key) const {
deba@512	3449	if (SplitNodesBase<const DGR>::inNode(key)) {
kpeter@451	3450	return _in_map[key];
kpeter@451	3451	} else {
kpeter@451	3452	return _out_map[key];
kpeter@451	3453	}
kpeter@451	3454	}
kpeter@451	3455
kpeter@451	3456	/// Returns a reference to the value associated with the given key.
deba@414	3457	Value& operator[](const Key& key) {
deba@512	3458	if (SplitNodesBase<const DGR>::inNode(key)) {
deba@416	3459	return _in_map[key];
deba@416	3460	} else {
deba@416	3461	return _out_map[key];
deba@416	3462	}
deba@414	3463	}
deba@414	3464
kpeter@451	3465	/// Sets the value associated with the given key.
deba@414	3466	void set(const Key& key, const Value& value) {
deba@512	3467	if (SplitNodesBase<const DGR>::inNode(key)) {
deba@416	3468	_in_map.set(key, value);
deba@416	3469	} else {
deba@416	3470	_out_map.set(key, value);
deba@416	3471	}
deba@414	3472	}
deba@416	3473
deba@414	3474	private:
deba@416	3475
kpeter@559	3476	IN& _in_map;
kpeter@559	3477	OUT& _out_map;
deba@416	3478
deba@414	3479	};
deba@414	3480
deba@414	3481
kpeter@451	3482	/// \brief Returns a combined node map
deba@416	3483	///
kpeter@451	3484	/// This function just returns a combined node map.
kpeter@559	3485	template <typename IN, typename OUT>
kpeter@559	3486	static CombinedNodeMap<IN, OUT>
kpeter@559	3487	combinedNodeMap(IN& in_map, OUT& out_map) {
kpeter@559	3488	return CombinedNodeMap<IN, OUT>(in_map, out_map);
deba@414	3489	}
deba@414	3490
kpeter@559	3491	template <typename IN, typename OUT>
kpeter@559	3492	static CombinedNodeMap<const IN, OUT>
kpeter@559	3493	combinedNodeMap(const IN& in_map, OUT& out_map) {
kpeter@559	3494	return CombinedNodeMap<const IN, OUT>(in_map, out_map);
deba@414	3495	}
deba@414	3496
kpeter@559	3497	template <typename IN, typename OUT>
kpeter@559	3498	static CombinedNodeMap<IN, const OUT>
kpeter@559	3499	combinedNodeMap(IN& in_map, const OUT& out_map) {
kpeter@559	3500	return CombinedNodeMap<IN, const OUT>(in_map, out_map);
deba@414	3501	}
deba@414	3502
kpeter@559	3503	template <typename IN, typename OUT>
kpeter@559	3504	static CombinedNodeMap<const IN, const OUT>
kpeter@559	3505	combinedNodeMap(const IN& in_map, const OUT& out_map) {
kpeter@559	3506	return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
deba@414	3507	}
deba@414	3508
kpeter@451	3509	/// \brief Arc map combined from an arc map and a node map of the
kpeter@451	3510	/// original digraph.
deba@414	3511	///
kpeter@451	3512	/// This map adaptor class adapts an arc map and a node map of the
kpeter@451	3513	/// original digraph to get an arc map of the split digraph.
kpeter@559	3514	/// Its value type is inherited from the original arc map type (\c AM).
kpeter@559	3515	/// \tparam AM The type of the arc map.
kpeter@559	3516	/// \tparam NM the type of the node map.
kpeter@559	3517	template <typename AM, typename NM>
deba@414	3518	class CombinedArcMap {
deba@414	3519	public:
deba@416	3520
kpeter@451	3521	/// The key type of the map
deba@414	3522	typedef Arc Key;
kpeter@451	3523	/// The value type of the map
kpeter@559	3524	typedef typename AM::Value Value;
kpeter@559	3525
kpeter@559	3526	typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
kpeter@559	3527	typedef typename MapTraits<AM>::ReturnValue ReturnValue;
kpeter@559	3528	typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
kpeter@559	3529	typedef typename MapTraits<AM>::ReturnValue Reference;
kpeter@559	3530	typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
kpeter@449	3531
kpeter@451	3532	/// Constructor
kpeter@559	3533	CombinedArcMap(AM& arc_map, NM& node_map)
deba@416	3534	: _arc_map(arc_map), _node_map(node_map) {}
deba@414	3535
kpeter@451	3536	/// Returns the value associated with the given key.
kpeter@451	3537	Value operator[](const Key& arc) const {
deba@512	3538	if (SplitNodesBase<const DGR>::origArc(arc)) {
kpeter@451	3539	return _arc_map[arc];
kpeter@451	3540	} else {
kpeter@451	3541	return _node_map[arc];
kpeter@451	3542	}
kpeter@451	3543	}
kpeter@451	3544
kpeter@451	3545	/// Returns a reference to the value associated with the given key.
kpeter@451	3546	Value& operator[](const Key& arc) {
deba@512	3547	if (SplitNodesBase<const DGR>::origArc(arc)) {
kpeter@451	3548	return _arc_map[arc];
kpeter@451	3549	} else {
kpeter@451	3550	return _node_map[arc];
kpeter@451	3551	}
kpeter@451	3552	}
kpeter@451	3553
kpeter@451	3554	/// Sets the value associated with the given key.
deba@414	3555	void set(const Arc& arc, const Value& val) {
deba@512	3556	if (SplitNodesBase<const DGR>::origArc(arc)) {
deba@416	3557	_arc_map.set(arc, val);
deba@416	3558	} else {
deba@416	3559	_node_map.set(arc, val);
deba@416	3560	}
deba@414	3561	}
deba@414	3562
deba@414	3563	private:
kpeter@559	3564
kpeter@559	3565	AM& _arc_map;
kpeter@559	3566	NM& _node_map;
kpeter@559	3567
deba@414	3568	};
deba@416	3569
kpeter@451	3570	/// \brief Returns a combined arc map
deba@416	3571	///
kpeter@451	3572	/// This function just returns a combined arc map.
kpeter@453	3573	template <typename ArcMap, typename NodeMap>
kpeter@453	3574	static CombinedArcMap<ArcMap, NodeMap>
kpeter@453	3575	combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
kpeter@453	3576	return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
deba@414	3577	}
deba@414	3578
kpeter@453	3579	template <typename ArcMap, typename NodeMap>
kpeter@453	3580	static CombinedArcMap<const ArcMap, NodeMap>
kpeter@453	3581	combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
kpeter@453	3582	return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
deba@414	3583	}
deba@414	3584
kpeter@453	3585	template <typename ArcMap, typename NodeMap>
kpeter@453	3586	static CombinedArcMap<ArcMap, const NodeMap>
kpeter@453	3587	combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
kpeter@453	3588	return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
deba@414	3589	}
deba@414	3590
kpeter@453	3591	template <typename ArcMap, typename NodeMap>
kpeter@453	3592	static CombinedArcMap<const ArcMap, const NodeMap>
kpeter@453	3593	combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
kpeter@453	3594	return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
deba@414	3595	}
deba@414	3596
deba@414	3597	};
deba@414	3598
kpeter@451	3599	/// \brief Returns a (read-only) SplitNodes adaptor
deba@414	3600	///
kpeter@451	3601	/// This function just returns a (read-only) \ref SplitNodes adaptor.
kpeter@451	3602	/// \ingroup graph_adaptors
kpeter@451	3603	/// \relates SplitNodes
deba@512	3604	template<typename DGR>
deba@512	3605	SplitNodes<DGR>
deba@512	3606	splitNodes(const DGR& digraph) {
deba@512	3607	return SplitNodes<DGR>(digraph);
deba@414	3608	}
deba@414	3609
deba@512	3610	#undef LEMON_SCOPE_FIX
deba@512	3611
deba@414	3612	} //namespace lemon
deba@414	3613
deba@416	3614	#endif //LEMON_ADAPTORS_H

author	Balazs Dezso <deba@inf.elte.hu>
	Thu, 24 Jun 2010 09:27:53 +0200
changeset 894	bb70ad62c95f
parent 617	4137ef9aacc6
child 787	c2230649a493
child 963	761fe0846f49
permissions	-rw-r--r--