lemon-1.1: lemon/adaptors.h@6ac5d9ae1d3d (annotated)

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

author	Peter Kovacs <kpeter@inf.elte.hu>
	Fri, 03 Apr 2009 18:59:15 +0200
changeset 600	6ac5d9ae1d3d
parent 495	dab9e610e37d
child 550	c5fd2d996909
permissions	-rw-r--r--