lemon-main: lemon/adaptors.h@a3402913cffe (annotated)

deba@416	1	/* -- mode: C++; indent-tabs-mode: nil; --
deba@414	2	*
deba@416	3	* This file is a part of LEMON, a generic C++ optimization library.
deba@414	4	*
alpar@454	5	* Copyright (C) 2003-2009
deba@414	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@414	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@414	8	*
deba@414	9	* Permission to use, modify and distribute this software is granted
deba@414	10	* provided that this copyright notice appears in all copies. For
deba@414	11	* precise terms see the accompanying LICENSE file.
deba@414	12	*
deba@414	13	* This software is provided "AS IS" with no warranty of any kind,
deba@414	14	* express or implied, and with no claim as to its suitability for any
deba@414	15	* purpose.
deba@414	16	*
deba@414	17	*/
deba@414	18
deba@416	19	#ifndef LEMON_ADAPTORS_H
deba@416	20	#define LEMON_ADAPTORS_H
deba@416	21
deba@416	22	/// \ingroup graph_adaptors
deba@416	23	/// \file
kpeter@451	24	/// \brief Adaptor classes for digraphs and graphs
deba@414	25	///
deba@416	26	/// This file contains several useful adaptors for digraphs and graphs.
deba@414	27
deba@414	28	#include <lemon/core.h>
deba@414	29	#include <lemon/maps.h>
deba@414	30	#include <lemon/bits/variant.h>
deba@414	31
deba@414	32	#include <lemon/bits/graph_adaptor_extender.h>
deba@519	33	#include <lemon/bits/map_extender.h>
deba@414	34	#include <lemon/tolerance.h>
deba@414	35
deba@414	36	#include <algorithm>
deba@414	37
deba@414	38	namespace lemon {
deba@414	39
deba@488	40	#ifdef _MSC_VER
deba@488	41	#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
deba@488	42	#else
deba@488	43	#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
deba@488	44	#endif
deba@488	45
deba@488	46	template<typename DGR>
deba@414	47	class DigraphAdaptorBase {
deba@414	48	public:
deba@488	49	typedef DGR Digraph;
deba@414	50	typedef DigraphAdaptorBase Adaptor;
deba@414	51
deba@414	52	protected:
deba@488	53	DGR* _digraph;
deba@414	54	DigraphAdaptorBase() : _digraph(0) { }
deba@488	55	void initialize(DGR& digraph) { _digraph = &digraph; }
deba@414	56
deba@414	57	public:
deba@488	58	DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
deba@488	59
deba@488	60	typedef typename DGR::Node Node;
deba@488	61	typedef typename DGR::Arc Arc;
deba@416	62
deba@414	63	void first(Node& i) const { _digraph->first(i); }
deba@414	64	void first(Arc& i) const { _digraph->first(i); }
deba@414	65	void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
deba@414	66	void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
deba@414	67
deba@414	68	void next(Node& i) const { _digraph->next(i); }
deba@414	69	void next(Arc& i) const { _digraph->next(i); }
deba@414	70	void nextIn(Arc& i) const { _digraph->nextIn(i); }
deba@414	71	void nextOut(Arc& i) const { _digraph->nextOut(i); }
deba@414	72
deba@414	73	Node source(const Arc& a) const { return _digraph->source(a); }
deba@414	74	Node target(const Arc& a) const { return _digraph->target(a); }
deba@414	75
deba@488	76	typedef NodeNumTagIndicator<DGR> NodeNumTag;
deba@414	77	int nodeNum() const { return _digraph->nodeNum(); }
deba@416	78
deba@488	79	typedef ArcNumTagIndicator<DGR> ArcNumTag;
deba@414	80	int arcNum() const { return _digraph->arcNum(); }
deba@414	81
deba@488	82	typedef FindArcTagIndicator<DGR> FindArcTag;
kpeter@448	83	Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
deba@414	84	return _digraph->findArc(u, v, prev);
deba@414	85	}
deba@416	86
deba@414	87	Node addNode() { return _digraph->addNode(); }
deba@414	88	Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
deba@414	89
kpeter@448	90	void erase(const Node& n) { _digraph->erase(n); }
kpeter@448	91	void erase(const Arc& a) { _digraph->erase(a); }
kpeter@448	92
kpeter@448	93	void clear() { _digraph->clear(); }
deba@416	94
deba@414	95	int id(const Node& n) const { return _digraph->id(n); }
deba@414	96	int id(const Arc& a) const { return _digraph->id(a); }
deba@414	97
deba@414	98	Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
deba@414	99	Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
deba@414	100
deba@414	101	int maxNodeId() const { return _digraph->maxNodeId(); }
deba@414	102	int maxArcId() const { return _digraph->maxArcId(); }
deba@414	103
deba@488	104	typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
deba@416	105	NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
deba@414	106
deba@488	107	typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
deba@416	108	ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
deba@416	109
deba@488	110	template <typename V>
deba@488	111	class NodeMap : public DGR::template NodeMap<V> {
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@559	2257	/// Its value type is inherited from the first arc map type (\c FW).
kpeter@559	2258	/// \tparam FW The type of the "foward" arc map.
kpeter@559	2259	/// \tparam BK The type of the "backward" arc map.
kpeter@559	2260	template <typename FW, typename BK>
deba@414	2261	class CombinedArcMap {
deba@414	2262	public:
deba@416	2263
kpeter@451	2264	/// The key type of the map
kpeter@451	2265	typedef typename Parent::Arc Key;
kpeter@451	2266	/// The value type of the map
kpeter@559	2267	typedef typename FW::Value Value;
kpeter@559	2268
kpeter@559	2269	typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
kpeter@559	2270
kpeter@559	2271	typedef typename MapTraits<FW>::ReturnValue ReturnValue;
kpeter@559	2272	typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
kpeter@559	2273	typedef typename MapTraits<FW>::ReturnValue Reference;
kpeter@559	2274	typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
kpeter@449	2275
deba@416	2276	/// Constructor
kpeter@559	2277	CombinedArcMap(FW& forward, BK& backward)
deba@414	2278	: _forward(&forward), _backward(&backward) {}
deba@416	2279
kpeter@451	2280	/// Sets the value associated with the given key.
deba@416	2281	void set(const Key& e, const Value& a) {
deba@416	2282	if (Parent::direction(e)) {
deba@416	2283	_forward->set(e, a);
deba@416	2284	} else {
deba@416	2285	_backward->set(e, a);
deba@416	2286	}
deba@414	2287	}
deba@414	2288
kpeter@451	2289	/// Returns the value associated with the given key.
kpeter@449	2290	ConstReturnValue operator[](const Key& e) const {
deba@416	2291	if (Parent::direction(e)) {
deba@416	2292	return (*_forward)[e];
deba@416	2293	} else {
deba@416	2294	return (*_backward)[e];
deba@414	2295	}
deba@414	2296	}
deba@414	2297
kpeter@451	2298	/// Returns a reference to the value associated with the given key.
kpeter@449	2299	ReturnValue operator[](const Key& e) {
deba@416	2300	if (Parent::direction(e)) {
deba@416	2301	return (*_forward)[e];
deba@416	2302	} else {
deba@416	2303	return (*_backward)[e];
deba@414	2304	}
deba@414	2305	}
deba@414	2306
deba@416	2307	protected:
deba@416	2308
kpeter@559	2309	FW* _forward;
kpeter@559	2310	BK* _backward;
deba@416	2311
deba@416	2312	};
deba@416	2313
kpeter@451	2314	/// \brief Returns a combined arc map
deba@416	2315	///
kpeter@451	2316	/// This function just returns a combined arc map.
kpeter@559	2317	template <typename FW, typename BK>
kpeter@559	2318	static CombinedArcMap<FW, BK>
kpeter@559	2319	combinedArcMap(FW& forward, BK& backward) {
kpeter@559	2320	return CombinedArcMap<FW, BK>(forward, backward);
deba@416	2321	}
deba@416	2322
kpeter@559	2323	template <typename FW, typename BK>
kpeter@559	2324	static CombinedArcMap<const FW, BK>
kpeter@559	2325	combinedArcMap(const FW& forward, BK& backward) {
kpeter@559	2326	return CombinedArcMap<const FW, BK>(forward, backward);
deba@416	2327	}
deba@416	2328
kpeter@559	2329	template <typename FW, typename BK>
kpeter@559	2330	static CombinedArcMap<FW, const BK>
kpeter@559	2331	combinedArcMap(FW& forward, const BK& backward) {
kpeter@559	2332	return CombinedArcMap<FW, const BK>(forward, backward);
deba@416	2333	}
deba@416	2334
kpeter@559	2335	template <typename FW, typename BK>
kpeter@559	2336	static CombinedArcMap<const FW, const BK>
kpeter@559	2337	combinedArcMap(const FW& forward, const BK& backward) {
kpeter@559	2338	return CombinedArcMap<const FW, const BK>(forward, backward);
deba@416	2339	}
deba@416	2340
deba@416	2341	};
deba@416	2342
kpeter@451	2343	/// \brief Returns a read-only Undirector adaptor
deba@416	2344	///
kpeter@451	2345	/// This function just returns a read-only \ref Undirector adaptor.
kpeter@451	2346	/// \ingroup graph_adaptors
kpeter@451	2347	/// \relates Undirector
deba@488	2348	template<typename DGR>
deba@488	2349	Undirector<const DGR> undirector(const DGR& digraph) {
deba@488	2350	return Undirector<const DGR>(digraph);
deba@416	2351	}
deba@416	2352
kpeter@451	2353
deba@488	2354	template <typename GR, typename DM>
deba@416	2355	class OrienterBase {
deba@416	2356	public:
deba@416	2357
deba@488	2358	typedef GR Graph;
deba@488	2359	typedef DM DirectionMap;
deba@488	2360
deba@488	2361	typedef typename GR::Node Node;
deba@488	2362	typedef typename GR::Edge Arc;
deba@416	2363
deba@416	2364	void reverseArc(const Arc& arc) {
deba@416	2365	_direction->set(arc, !(*_direction)[arc]);
deba@416	2366	}
deba@416	2367
deba@416	2368	void first(Node& i) const { _graph->first(i); }
deba@416	2369	void first(Arc& i) const { _graph->first(i); }
deba@416	2370	void firstIn(Arc& i, const Node& n) const {
kpeter@447	2371	bool d = true;
deba@416	2372	_graph->firstInc(i, d, n);
deba@416	2373	while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2374	}
deba@416	2375	void firstOut(Arc& i, const Node& n ) const {
kpeter@447	2376	bool d = true;
deba@416	2377	_graph->firstInc(i, d, n);
deba@416	2378	while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2379	}
deba@416	2380
deba@416	2381	void next(Node& i) const { _graph->next(i); }
deba@416	2382	void next(Arc& i) const { _graph->next(i); }
deba@416	2383	void nextIn(Arc& i) const {
deba@416	2384	bool d = !(*_direction)[i];
deba@416	2385	_graph->nextInc(i, d);
deba@416	2386	while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2387	}
deba@416	2388	void nextOut(Arc& i) const {
deba@416	2389	bool d = (*_direction)[i];
deba@416	2390	_graph->nextInc(i, d);
deba@416	2391	while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
deba@416	2392	}
deba@416	2393
deba@416	2394	Node source(const Arc& e) const {
deba@416	2395	return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
deba@416	2396	}
deba@416	2397	Node target(const Arc& e) const {
deba@416	2398	return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
deba@416	2399	}
deba@416	2400
deba@416	2401	typedef NodeNumTagIndicator<Graph> NodeNumTag;
deba@416	2402	int nodeNum() const { return _graph->nodeNum(); }
deba@416	2403
kpeter@446	2404	typedef EdgeNumTagIndicator<Graph> ArcNumTag;
deba@416	2405	int arcNum() const { return _graph->edgeNum(); }
deba@416	2406
kpeter@446	2407	typedef FindEdgeTagIndicator<Graph> FindArcTag;
deba@416	2408	Arc findArc(const Node& u, const Node& v,
kpeter@448	2409	const Arc& prev = INVALID) const {
kpeter@449	2410	Arc arc = _graph->findEdge(u, v, prev);
kpeter@449	2411	while (arc != INVALID && source(arc) != u) {
deba@416	2412	arc = _graph->findEdge(u, v, arc);
deba@414	2413	}
deba@416	2414	return arc;
deba@416	2415	}
deba@416	2416
deba@416	2417	Node addNode() {
deba@416	2418	return Node(_graph->addNode());
deba@416	2419	}
deba@416	2420
deba@416	2421	Arc addArc(const Node& u, const Node& v) {
kpeter@449	2422	Arc arc = _graph->addEdge(u, v);
kpeter@449	2423	_direction->set(arc, _graph->u(arc) == u);
deba@416	2424	return arc;
deba@416	2425	}
deba@416	2426
deba@416	2427	void erase(const Node& i) { _graph->erase(i); }
deba@416	2428	void erase(const Arc& i) { _graph->erase(i); }
deba@416	2429
deba@416	2430	void clear() { _graph->clear(); }
deba@416	2431
deba@416	2432	int id(const Node& v) const { return _graph->id(v); }
deba@416	2433	int id(const Arc& e) const { return _graph->id(e); }
deba@416	2434
deba@416	2435	Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
deba@416	2436	Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
deba@416	2437
deba@416	2438	int maxNodeId() const { return _graph->maxNodeId(); }
deba@416	2439	int maxArcId() const { return _graph->maxEdgeId(); }
deba@416	2440
deba@488	2441	typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@416	2442	NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
deba@416	2443
deba@488	2444	typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
deba@416	2445	ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
deba@416	2446
deba@488	2447	template <typename V>
deba@488	2448	class NodeMap : public GR::template NodeMap<V> {
deba@416	2449	public:
deba@416	2450
deba@488	2451	typedef typename GR::template NodeMap<V> Parent;
deba@488	2452
deba@488	2453	explicit NodeMap(const OrienterBase<GR, DM>& adapter)
deba@416	2454	: Parent(*adapter._graph) {}
deba@416	2455
deba@488	2456	NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
deba@416	2457	: Parent(*adapter._graph, value) {}
deba@416	2458
deba@416	2459	private:
deba@416	2460	NodeMap& operator=(const NodeMap& cmap) {
deba@416	2461	return operator=<NodeMap>(cmap);
deba@416	2462	}
deba@416	2463
deba@416	2464	template <typename CMap>
deba@416	2465	NodeMap& operator=(const CMap& cmap) {
deba@416	2466	Parent::operator=(cmap);
deba@416	2467	return *this;
deba@416	2468	}
deba@414	2469
deba@414	2470	};
deba@414	2471
deba@488	2472	template <typename V>
deba@488	2473	class ArcMap : public GR::template EdgeMap<V> {
deba@416	2474	public:
deba@416	2475
deba@488	2476	typedef typename Graph::template EdgeMap<V> Parent;
deba@488	2477
deba@488	2478	explicit ArcMap(const OrienterBase<GR, DM>& adapter)
deba@416	2479	: Parent(*adapter._graph) { }
deba@416	2480
deba@488	2481	ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
deba@416	2482	: Parent(*adapter._graph, value) { }
deba@416	2483
deba@416	2484	private:
deba@416	2485	ArcMap& operator=(const ArcMap& cmap) {
deba@416	2486	return operator=<ArcMap>(cmap);
deba@416	2487	}
deba@416	2488
deba@416	2489	template <typename CMap>
deba@416	2490	ArcMap& operator=(const CMap& cmap) {
deba@416	2491	Parent::operator=(cmap);
deba@416	2492	return *this;
deba@416	2493	}
deba@416	2494	};
deba@416	2495
deba@416	2496
deba@416	2497
deba@416	2498	protected:
deba@416	2499	Graph* _graph;
deba@488	2500	DM* _direction;
deba@488	2501
deba@488	2502	void initialize(GR& graph, DM& direction) {
deba@488	2503	_graph = &graph;
deba@416	2504	_direction = &direction;
deba@416	2505	}
deba@416	2506
deba@414	2507	};
deba@414	2508
deba@416	2509	/// \ingroup graph_adaptors
deba@414	2510	///
kpeter@451	2511	/// \brief Adaptor class for orienting the edges of a graph to get a digraph
deba@416	2512	///
kpeter@451	2513	/// Orienter adaptor can be used for orienting the edges of a graph to
kpeter@451	2514	/// get a digraph. A \c bool edge map of the underlying graph must be
kpeter@451	2515	/// specified, which define the direction of the arcs in the adaptor.
kpeter@451	2516	/// The arcs can be easily reversed by the \c reverseArc() member function
kpeter@451	2517	/// of the adaptor.
kpeter@451	2518	/// This class conforms to the \ref concepts::Digraph "Digraph" concept.
deba@416	2519	///
kpeter@451	2520	/// The adapted graph can also be modified through this adaptor
kpeter@453	2521	/// by adding or removing nodes or arcs, unless the \c GR template
kpeter@451	2522	/// parameter is set to be \c const.
deba@416	2523	///
kpeter@453	2524	/// \tparam GR The type of the adapted graph.
kpeter@451	2525	/// It must conform to the \ref concepts::Graph "Graph" concept.
kpeter@451	2526	/// It can also be specified to be \c const.
kpeter@453	2527	/// \tparam DM The type of the direction map.
kpeter@453	2528	/// It must be a \c bool (or convertible) edge map of the
kpeter@453	2529	/// adapted graph. The default type is
kpeter@453	2530	/// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
kpeter@451	2531	///
kpeter@451	2532	/// \note The \c Node type of this adaptor and the adapted graph are
kpeter@451	2533	/// convertible to each other, moreover the \c Arc type of the adaptor
kpeter@451	2534	/// and the \c Edge type of the adapted graph are also convertible to
kpeter@451	2535	/// each other.
kpeter@451	2536	#ifdef DOXYGEN
kpeter@453	2537	template<typename GR,
kpeter@453	2538	typename DM>
kpeter@453	2539	class Orienter {
kpeter@451	2540	#else
kpeter@453	2541	template<typename GR,
kpeter@453	2542	typename DM = typename GR::template EdgeMap<bool> >
kpeter@453	2543	class Orienter :
kpeter@453	2544	public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
kpeter@451	2545	#endif
deba@416	2546	public:
kpeter@451	2547
kpeter@451	2548	/// The type of the adapted graph.
kpeter@453	2549	typedef GR Graph;
kpeter@451	2550	/// The type of the direction edge map.
kpeter@453	2551	typedef DM DirectionMap;
kpeter@453	2552
kpeter@453	2553	typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
deba@416	2554	typedef typename Parent::Arc Arc;
deba@416	2555	protected:
deba@416	2556	Orienter() { }
deba@416	2557	public:
deba@416	2558
kpeter@451	2559	/// \brief Constructor
deba@416	2560	///
kpeter@451	2561	/// Constructor of the adaptor.
deba@488	2562	Orienter(GR& graph, DM& direction) {
deba@488	2563	Parent::initialize(graph, direction);
deba@416	2564	}
deba@416	2565
kpeter@451	2566	/// \brief Reverses the given arc
deba@416	2567	///
kpeter@451	2568	/// This function reverses the given arc.
kpeter@451	2569	/// It is done by simply negate the assigned value of \c a
kpeter@451	2570	/// in the direction map.
deba@416	2571	void reverseArc(const Arc& a) {
deba@416	2572	Parent::reverseArc(a);
deba@416	2573	}
deba@416	2574	};
deba@416	2575
kpeter@451	2576	/// \brief Returns a read-only Orienter adaptor
deba@416	2577	///
kpeter@451	2578	/// This function just returns a read-only \ref Orienter adaptor.
kpeter@451	2579	/// \ingroup graph_adaptors
kpeter@451	2580	/// \relates Orienter
kpeter@453	2581	template<typename GR, typename DM>
kpeter@453	2582	Orienter<const GR, DM>
deba@488	2583	orienter(const GR& graph, DM& direction) {
deba@488	2584	return Orienter<const GR, DM>(graph, direction);
deba@414	2585	}
deba@414	2586
kpeter@453	2587	template<typename GR, typename DM>
kpeter@453	2588	Orienter<const GR, const DM>
deba@488	2589	orienter(const GR& graph, const DM& direction) {
deba@488	2590	return Orienter<const GR, const DM>(graph, direction);
deba@416	2591	}
deba@416	2592
deba@416	2593	namespace _adaptor_bits {
deba@416	2594
deba@488	2595	template <typename DGR, typename CM, typename FM, typename TL>
deba@416	2596	class ResForwardFilter {
deba@416	2597	public:
deba@416	2598
deba@488	2599	typedef typename DGR::Arc Key;
deba@416	2600	typedef bool Value;
deba@416	2601
deba@416	2602	private:
deba@416	2603
deba@488	2604	const CM* _capacity;
deba@488	2605	const FM* _flow;
deba@488	2606	TL _tolerance;
deba@488	2607
deba@416	2608	public:
deba@416	2609
deba@488	2610	ResForwardFilter(const CM& capacity, const FM& flow,
deba@488	2611	const TL& tolerance = TL())
deba@416	2612	: _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416	2613
deba@488	2614	bool operator[](const typename DGR::Arc& a) const {
deba@416	2615	return _tolerance.positive((_capacity)[a] - (_flow)[a]);
deba@416	2616	}
deba@416	2617	};
deba@416	2618
deba@488	2619	template<typename DGR,typename CM, typename FM, typename TL>
deba@416	2620	class ResBackwardFilter {
deba@416	2621	public:
deba@416	2622
deba@488	2623	typedef typename DGR::Arc Key;
deba@416	2624	typedef bool Value;
deba@416	2625
deba@416	2626	private:
deba@416	2627
deba@488	2628	const CM* _capacity;
deba@488	2629	const FM* _flow;
deba@488	2630	TL _tolerance;
deba@416	2631
deba@416	2632	public:
deba@416	2633
deba@488	2634	ResBackwardFilter(const CM& capacity, const FM& flow,
deba@488	2635	const TL& tolerance = TL())
deba@416	2636	: _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
deba@416	2637
deba@488	2638	bool operator[](const typename DGR::Arc& a) const {
deba@416	2639	return _tolerance.positive((*_flow)[a]);
deba@416	2640	}
deba@416	2641	};
deba@416	2642
deba@416	2643	}
deba@416	2644
deba@416	2645	/// \ingroup graph_adaptors
deba@416	2646	///
kpeter@451	2647	/// \brief Adaptor class for composing the residual digraph for directed
deba@416	2648	/// flow and circulation problems.
deba@416	2649	///
kpeter@464	2650	/// ResidualDigraph can be used for composing the \e residual digraph
kpeter@464	2651	/// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
kpeter@464	2652	/// be a directed graph and let \f$ F \f$ be a number type.
kpeter@464	2653	/// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
kpeter@451	2654	/// This adaptor implements a digraph structure with node set \f$ V \f$
kpeter@451	2655	/// and arc set \f$ A_{forward}\cup A_{backward} \f$,
kpeter@451	2656	/// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
kpeter@451	2657	/// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
kpeter@451	2658	/// called residual digraph.
kpeter@451	2659	/// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
kpeter@451	2660	/// multiplicities are counted, i.e. the adaptor has exactly
kpeter@451	2661	/// \f$ \|A_{forward}\| + \|A_{backward}\|\f$ arcs (it may have parallel
kpeter@451	2662	/// arcs).
kpeter@451	2663	/// This class conforms to the \ref concepts::Digraph "Digraph" concept.
deba@416	2664	///
deba@488	2665	/// \tparam DGR The type of the adapted digraph.
kpeter@451	2666	/// It must conform to the \ref concepts::Digraph "Digraph" concept.
kpeter@451	2667	/// It is implicitly \c const.
kpeter@453	2668	/// \tparam CM The type of the capacity map.
kpeter@453	2669	/// It must be an arc map of some numerical type, which defines
kpeter@451	2670	/// the capacities in the flow problem. It is implicitly \c const.
kpeter@453	2671	/// The default type is
kpeter@453	2672	/// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
kpeter@453	2673	/// \tparam FM The type of the flow map.
kpeter@453	2674	/// It must be an arc map of some numerical type, which defines
kpeter@453	2675	/// the flow values in the flow problem. The default type is \c CM.
kpeter@453	2676	/// \tparam TL The tolerance type for handling inexact computation.
kpeter@451	2677	/// The default tolerance type depends on the value type of the
kpeter@451	2678	/// capacity map.
deba@416	2679	///
kpeter@451	2680	/// \note This adaptor is implemented using Undirector and FilterArcs
kpeter@451	2681	/// adaptors.
kpeter@451	2682	///
kpeter@451	2683	/// \note The \c Node type of this adaptor and the adapted digraph are
kpeter@451	2684	/// convertible to each other, moreover the \c Arc type of the adaptor
kpeter@451	2685	/// is convertible to the \c Arc type of the adapted digraph.
kpeter@451	2686	#ifdef DOXYGEN
deba@488	2687	template<typename DGR, typename CM, typename FM, typename TL>
kpeter@464	2688	class ResidualDigraph
kpeter@451	2689	#else
deba@488	2690	template<typename DGR,
deba@488	2691	typename CM = typename DGR::template ArcMap<int>,
kpeter@453	2692	typename FM = CM,
kpeter@453	2693	typename TL = Tolerance<typename CM::Value> >
deba@488	2694	class ResidualDigraph
deba@488	2695	: public SubDigraph<
deba@488	2696	Undirector<const DGR>,
deba@488	2697	ConstMap<typename DGR::Node, Const<bool, true> >,
deba@488	2698	typename Undirector<const DGR>::template CombinedArcMap<
deba@488	2699	_adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
deba@488	2700	_adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
kpeter@451	2701	#endif
deba@416	2702	{
deba@414	2703	public:
deba@414	2704
kpeter@451	2705	/// The type of the underlying digraph.
deba@488	2706	typedef DGR Digraph;
kpeter@451	2707	/// The type of the capacity map.
kpeter@453	2708	typedef CM CapacityMap;
kpeter@451	2709	/// The type of the flow map.
kpeter@453	2710	typedef FM FlowMap;
kpeter@453	2711	/// The tolerance type.
kpeter@453	2712	typedef TL Tolerance;
deba@414	2713
deba@414	2714	typedef typename CapacityMap::Value Value;
kpeter@464	2715	typedef ResidualDigraph Adaptor;
deba@414	2716
deba@414	2717	protected:
deba@414	2718
deba@416	2719	typedef Undirector<const Digraph> Undirected;
deba@416	2720
deba@488	2721	typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
deba@488	2722
deba@488	2723	typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
deba@488	2724	FM, TL> ForwardFilter;
deba@488	2725
deba@488	2726	typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
deba@488	2727	FM, TL> BackwardFilter;
deba@416	2728
deba@416	2729	typedef typename Undirected::
kpeter@453	2730	template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
deba@414	2731
deba@488	2732	typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
deba@414	2733
deba@414	2734	const CapacityMap* _capacity;
deba@414	2735	FlowMap* _flow;
deba@414	2736
deba@416	2737	Undirected _graph;
deba@488	2738	NodeFilter _node_filter;
deba@414	2739	ForwardFilter _forward_filter;
deba@414	2740	BackwardFilter _backward_filter;
deba@414	2741	ArcFilter _arc_filter;
deba@414	2742
deba@414	2743	public:
deba@414	2744
kpeter@451	2745	/// \brief Constructor
deba@414	2746	///
kpeter@451	2747	/// Constructor of the residual digraph adaptor. The parameters are the
kpeter@451	2748	/// digraph, the capacity map, the flow map, and a tolerance object.
deba@488	2749	ResidualDigraph(const DGR& digraph, const CM& capacity,
deba@488	2750	FM& flow, const TL& tolerance = Tolerance())
deba@488	2751	: Parent(), _capacity(&capacity), _flow(&flow),
deba@488	2752	_graph(digraph), _node_filter(),
deba@416	2753	_forward_filter(capacity, flow, tolerance),
deba@414	2754	_backward_filter(capacity, flow, tolerance),
deba@414	2755	_arc_filter(_forward_filter, _backward_filter)
deba@414	2756	{
deba@488	2757	Parent::initialize(_graph, _node_filter, _arc_filter);
deba@414	2758	}
deba@414	2759
deba@414	2760	typedef typename Parent::Arc Arc;
deba@414	2761
kpeter@451	2762	/// \brief Returns the residual capacity of the given arc.
deba@414	2763	///
kpeter@451	2764	/// Returns the residual capacity of the given arc.
deba@416	2765	Value residualCapacity(const Arc& a) const {
deba@416	2766	if (Undirected::direction(a)) {
deba@416	2767	return (_capacity)[a] - (_flow)[a];
deba@414	2768	} else {
deba@416	2769	return (*_flow)[a];
deba@414	2770	}
deba@416	2771	}
deba@416	2772
kpeter@452	2773	/// \brief Augments on the given arc in the residual digraph.
deba@414	2774	///
kpeter@452	2775	/// Augments on the given arc in the residual digraph. It increases
kpeter@451	2776	/// or decreases the flow value on the original arc according to the
kpeter@451	2777	/// direction of the residual arc.
deba@416	2778	void augment(const Arc& a, const Value& v) const {
deba@416	2779	if (Undirected::direction(a)) {
deba@416	2780	_flow->set(a, (*_flow)[a] + v);
deba@416	2781	} else {
deba@416	2782	_flow->set(a, (*_flow)[a] - v);
deba@414	2783	}
deba@414	2784	}
deba@414	2785
kpeter@451	2786	/// \brief Returns \c true if the given residual arc is a forward arc.
deba@414	2787	///
kpeter@451	2788	/// Returns \c true if the given residual arc has the same orientation
kpeter@451	2789	/// as the original arc, i.e. it is a so called forward arc.
deba@416	2790	static bool forward(const Arc& a) {
deba@416	2791	return Undirected::direction(a);
deba@414	2792	}
deba@414	2793
kpeter@451	2794	/// \brief Returns \c true if the given residual arc is a backward arc.
deba@414	2795	///
kpeter@451	2796	/// Returns \c true if the given residual arc has the opposite orientation
kpeter@451	2797	/// than the original arc, i.e. it is a so called backward arc.
deba@416	2798	static bool backward(const Arc& a) {
deba@416	2799	return !Undirected::direction(a);
deba@414	2800	}
deba@414	2801
kpeter@451	2802	/// \brief Returns the forward oriented residual arc.
deba@414	2803	///
kpeter@451	2804	/// Returns the forward oriented residual arc related to the given
kpeter@451	2805	/// arc of the underlying digraph.
deba@416	2806	static Arc forward(const typename Digraph::Arc& a) {
deba@416	2807	return Undirected::direct(a, true);
deba@414	2808	}
deba@414	2809
kpeter@451	2810	/// \brief Returns the backward oriented residual arc.
deba@414	2811	///
kpeter@451	2812	/// Returns the backward oriented residual arc related to the given
kpeter@451	2813	/// arc of the underlying digraph.
deba@416	2814	static Arc backward(const typename Digraph::Arc& a) {
deba@416	2815	return Undirected::direct(a, false);
deba@414	2816	}
deba@414	2817
deba@414	2818	/// \brief Residual capacity map.
deba@414	2819	///
kpeter@451	2820	/// This map adaptor class can be used for obtaining the residual
kpeter@451	2821	/// capacities as an arc map of the residual digraph.
kpeter@451	2822	/// Its value type is inherited from the capacity map.
deba@416	2823	class ResidualCapacity {
deba@414	2824	protected:
deba@414	2825	const Adaptor* _adaptor;
deba@414	2826	public:
kpeter@451	2827	/// The key type of the map
deba@414	2828	typedef Arc Key;
kpeter@451	2829	/// The value type of the map
kpeter@453	2830	typedef typename CapacityMap::Value Value;
deba@414	2831
deba@416	2832	/// Constructor
deba@488	2833	ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
deba@488	2834	: _adaptor(&adaptor) {}
deba@416	2835
kpeter@451	2836	/// Returns the value associated with the given residual arc
deba@416	2837	Value operator[](const Arc& a) const {
deba@416	2838	return _adaptor->residualCapacity(a);
deba@414	2839	}
deba@416	2840
deba@414	2841	};
deba@414	2842
kpeter@450	2843	/// \brief Returns a residual capacity map
kpeter@450	2844	///
kpeter@450	2845	/// This function just returns a residual capacity map.
kpeter@450	2846	ResidualCapacity residualCapacity() const {
kpeter@450	2847	return ResidualCapacity(*this);
kpeter@450	2848	}
kpeter@450	2849
deba@414	2850	};
deba@414	2851
kpeter@450	2852	/// \brief Returns a (read-only) Residual adaptor
kpeter@450	2853	///
deba@488	2854	/// This function just returns a (read-only) \ref ResidualDigraph adaptor.
kpeter@450	2855	/// \ingroup graph_adaptors
deba@488	2856	/// \relates ResidualDigraph
deba@488	2857	template<typename DGR, typename CM, typename FM>
deba@488	2858	ResidualDigraph<DGR, CM, FM>
deba@488	2859	residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
deba@488	2860	return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
kpeter@450	2861	}
kpeter@450	2862
kpeter@450	2863
deba@488	2864	template <typename DGR>
deba@416	2865	class SplitNodesBase {
deba@414	2866	public:
deba@414	2867
deba@488	2868	typedef DGR Digraph;
deba@488	2869	typedef DigraphAdaptorBase<const DGR> Parent;
deba@416	2870	typedef SplitNodesBase Adaptor;
deba@414	2871
deba@488	2872	typedef typename DGR::Node DigraphNode;
deba@488	2873	typedef typename DGR::Arc DigraphArc;
deba@414	2874
deba@414	2875	class Node;
deba@414	2876	class Arc;
deba@414	2877
deba@414	2878	private:
deba@414	2879
deba@414	2880	template <typename T> class NodeMapBase;
deba@414	2881	template <typename T> class ArcMapBase;
deba@414	2882
deba@414	2883	public:
deba@416	2884
deba@414	2885	class Node : public DigraphNode {
deba@416	2886	friend class SplitNodesBase;
deba@414	2887	template <typename T> friend class NodeMapBase;
deba@414	2888	private:
deba@414	2889
deba@414	2890	bool _in;
deba@414	2891	Node(DigraphNode node, bool in)
deba@416	2892	: DigraphNode(node), _in(in) {}
deba@416	2893
deba@414	2894	public:
deba@414	2895
deba@414	2896	Node() {}
deba@414	2897	Node(Invalid) : DigraphNode(INVALID), _in(true) {}
deba@414	2898
deba@414	2899	bool operator==(const Node& node) const {
deba@416	2900	return DigraphNode::operator==(node) && _in == node._in;
deba@414	2901	}
deba@416	2902
deba@414	2903	bool operator!=(const Node& node) const {
deba@416	2904	return !(*this == node);
deba@414	2905	}
deba@416	2906
deba@414	2907	bool operator<(const Node& node) const {
deba@416	2908	return DigraphNode::operator<(node) \|\|
deba@416	2909	(DigraphNode::operator==(node) && _in < node._in);
deba@414	2910	}
deba@414	2911	};
deba@414	2912
deba@414	2913	class Arc {
deba@416	2914	friend class SplitNodesBase;
deba@414	2915	template <typename T> friend class ArcMapBase;
deba@414	2916	private:
deba@414	2917	typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
deba@414	2918
deba@414	2919	explicit Arc(const DigraphArc& arc) : _item(arc) {}
deba@414	2920	explicit Arc(const DigraphNode& node) : _item(node) {}
deba@416	2921
deba@414	2922	ArcImpl _item;
deba@414	2923
deba@414	2924	public:
deba@414	2925	Arc() {}
deba@414	2926	Arc(Invalid) : _item(DigraphArc(INVALID)) {}
deba@414	2927
deba@414	2928	bool operator==(const Arc& arc) const {
deba@414	2929	if (_item.firstState()) {
deba@414	2930	if (arc._item.firstState()) {
deba@414	2931	return _item.first() == arc._item.first();
deba@414	2932	}
deba@414	2933	} else {
deba@414	2934	if (arc._item.secondState()) {
deba@414	2935	return _item.second() == arc._item.second();
deba@414	2936	}
deba@414	2937	}
deba@414	2938	return false;
deba@414	2939	}
deba@416	2940
deba@414	2941	bool operator!=(const Arc& arc) const {
deba@416	2942	return !(*this == arc);
deba@414	2943	}
deba@416	2944
deba@414	2945	bool operator<(const Arc& arc) const {
deba@414	2946	if (_item.firstState()) {
deba@414	2947	if (arc._item.firstState()) {
deba@414	2948	return _item.first() < arc._item.first();
deba@414	2949	}
deba@414	2950	return false;
deba@414	2951	} else {
deba@414	2952	if (arc._item.secondState()) {
deba@414	2953	return _item.second() < arc._item.second();
deba@414	2954	}
deba@414	2955	return true;
deba@414	2956	}
deba@414	2957	}
deba@414	2958
deba@414	2959	operator DigraphArc() const { return _item.first(); }
deba@414	2960	operator DigraphNode() const { return _item.second(); }
deba@414	2961
deba@414	2962	};
deba@414	2963
deba@414	2964	void first(Node& n) const {
deba@414	2965	_digraph->first(n);
deba@414	2966	n._in = true;
deba@414	2967	}
deba@414	2968
deba@414	2969	void next(Node& n) const {
deba@414	2970	if (n._in) {
deba@416	2971	n._in = false;
deba@414	2972	} else {
deba@416	2973	n._in = true;
deba@416	2974	_digraph->next(n);
deba@414	2975	}
deba@414	2976	}
deba@414	2977
deba@414	2978	void first(Arc& e) const {
deba@414	2979	e._item.setSecond();
deba@414	2980	_digraph->first(e._item.second());
deba@414	2981	if (e._item.second() == INVALID) {
deba@414	2982	e._item.setFirst();
deba@416	2983	_digraph->first(e._item.first());
deba@414	2984	}
deba@414	2985	}
deba@414	2986
deba@414	2987	void next(Arc& e) const {
deba@414	2988	if (e._item.secondState()) {
deba@416	2989	_digraph->next(e._item.second());
deba@414	2990	if (e._item.second() == INVALID) {
deba@414	2991	e._item.setFirst();
deba@414	2992	_digraph->first(e._item.first());
deba@414	2993	}
deba@414	2994	} else {
deba@416	2995	_digraph->next(e._item.first());
deba@416	2996	}
deba@414	2997	}
deba@414	2998
deba@414	2999	void firstOut(Arc& e, const Node& n) const {
deba@414	3000	if (n._in) {
deba@414	3001	e._item.setSecond(n);
deba@414	3002	} else {
deba@414	3003	e._item.setFirst();
deba@416	3004	_digraph->firstOut(e._item.first(), n);
deba@414	3005	}
deba@414	3006	}
deba@414	3007
deba@414	3008	void nextOut(Arc& e) const {
deba@414	3009	if (!e._item.firstState()) {
deba@416	3010	e._item.setFirst(INVALID);
deba@414	3011	} else {
deba@416	3012	_digraph->nextOut(e._item.first());
deba@416	3013	}
deba@414	3014	}
deba@414	3015
deba@414	3016	void firstIn(Arc& e, const Node& n) const {
deba@414	3017	if (!n._in) {
deba@416	3018	e._item.setSecond(n);
deba@414	3019	} else {
deba@414	3020	e._item.setFirst();
deba@416	3021	_digraph->firstIn(e._item.first(), n);
deba@414	3022	}
deba@414	3023	}
deba@414	3024
deba@414	3025	void nextIn(Arc& e) const {
deba@414	3026	if (!e._item.firstState()) {
deba@416	3027	e._item.setFirst(INVALID);
deba@414	3028	} else {
deba@416	3029	_digraph->nextIn(e._item.first());
deba@414	3030	}
deba@414	3031	}
deba@414	3032
deba@414	3033	Node source(const Arc& e) const {
deba@414	3034	if (e._item.firstState()) {
deba@416	3035	return Node(_digraph->source(e._item.first()), false);
deba@414	3036	} else {
deba@416	3037	return Node(e._item.second(), true);
deba@414	3038	}
deba@414	3039	}
deba@414	3040
deba@414	3041	Node target(const Arc& e) const {
deba@414	3042	if (e._item.firstState()) {
deba@416	3043	return Node(_digraph->target(e._item.first()), true);
deba@414	3044	} else {
deba@416	3045	return Node(e._item.second(), false);
deba@414	3046	}
deba@414	3047	}
deba@414	3048
deba@414	3049	int id(const Node& n) const {
deba@414	3050	return (_digraph->id(n) << 1) \| (n._in ? 0 : 1);
deba@414	3051	}
deba@414	3052	Node nodeFromId(int ix) const {
deba@414	3053	return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
deba@414	3054	}
deba@414	3055	int maxNodeId() const {
deba@414	3056	return 2 * _digraph->maxNodeId() + 1;
deba@414	3057	}
deba@414	3058
deba@414	3059	int id(const Arc& e) const {
deba@414	3060	if (e._item.firstState()) {
deba@414	3061	return _digraph->id(e._item.first()) << 1;
deba@414	3062	} else {
deba@414	3063	return (_digraph->id(e._item.second()) << 1) \| 1;
deba@414	3064	}
deba@414	3065	}
deba@414	3066	Arc arcFromId(int ix) const {
deba@414	3067	if ((ix & 1) == 0) {
deba@414	3068	return Arc(_digraph->arcFromId(ix >> 1));
deba@414	3069	} else {
deba@414	3070	return Arc(_digraph->nodeFromId(ix >> 1));
deba@414	3071	}
deba@414	3072	}
deba@414	3073	int maxArcId() const {
deba@416	3074	return std::max(_digraph->maxNodeId() << 1,
deba@414	3075	(_digraph->maxArcId() << 1) \| 1);
deba@414	3076	}
deba@414	3077
deba@414	3078	static bool inNode(const Node& n) {
deba@414	3079	return n._in;
deba@414	3080	}
deba@414	3081
deba@414	3082	static bool outNode(const Node& n) {
deba@414	3083	return !n._in;
deba@414	3084	}
deba@414	3085
deba@414	3086	static bool origArc(const Arc& e) {
deba@414	3087	return e._item.firstState();
deba@414	3088	}
deba@414	3089
deba@414	3090	static bool bindArc(const Arc& e) {
deba@414	3091	return e._item.secondState();
deba@414	3092	}
deba@414	3093
deba@414	3094	static Node inNode(const DigraphNode& n) {
deba@414	3095	return Node(n, true);
deba@414	3096	}
deba@414	3097
deba@414	3098	static Node outNode(const DigraphNode& n) {
deba@414	3099	return Node(n, false);
deba@414	3100	}
deba@414	3101
deba@414	3102	static Arc arc(const DigraphNode& n) {
deba@414	3103	return Arc(n);
deba@414	3104	}
deba@414	3105
deba@414	3106	static Arc arc(const DigraphArc& e) {
deba@414	3107	return Arc(e);
deba@414	3108	}
deba@414	3109
deba@414	3110	typedef True NodeNumTag;
deba@414	3111	int nodeNum() const {
deba@414	3112	return 2 * countNodes(*_digraph);
deba@414	3113	}
deba@414	3114
kpeter@446	3115	typedef True ArcNumTag;
deba@414	3116	int arcNum() const {
deba@414	3117	return countArcs(_digraph) + countNodes(_digraph);
deba@414	3118	}
deba@414	3119
kpeter@446	3120	typedef True FindArcTag;
deba@416	3121	Arc findArc(const Node& u, const Node& v,
deba@416	3122	const Arc& prev = INVALID) const {
kpeter@449	3123	if (inNode(u) && outNode(v)) {
kpeter@449	3124	if (static_cast<const DigraphNode&>(u) ==
kpeter@449	3125	static_cast<const DigraphNode&>(v) && prev == INVALID) {
kpeter@449	3126	return Arc(u);
deba@414	3127	}
kpeter@449	3128	}
kpeter@449	3129	else if (outNode(u) && inNode(v)) {
kpeter@449	3130	return Arc(::lemon::findArc(*_digraph, u, v, prev));
deba@414	3131	}
deba@414	3132	return INVALID;
deba@414	3133	}
deba@414	3134
deba@414	3135	private:
deba@416	3136
deba@488	3137	template <typename V>
deba@416	3138	class NodeMapBase
deba@488	3139	: public MapTraits<typename Parent::template NodeMap<V> > {
deba@488	3140	typedef typename Parent::template NodeMap<V> NodeImpl;
deba@414	3141	public:
deba@414	3142	typedef Node Key;
deba@488	3143	typedef V Value;
kpeter@449	3144	typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
kpeter@449	3145	typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
kpeter@449	3146	typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
kpeter@449	3147	typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
kpeter@449	3148	typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
deba@416	3149
deba@488	3150	NodeMapBase(const SplitNodesBase<DGR>& adaptor)
deba@416	3151	: _in_map(adaptor._digraph), _out_map(adaptor._digraph) {}
deba@488	3152	NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
deba@416	3153	: _in_map(*adaptor._digraph, value),
deba@416	3154	_out_map(*adaptor._digraph, value) {}
deba@414	3155
deba@488	3156	void set(const Node& key, const V& val) {
deba@488	3157	if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
deba@416	3158	else {_out_map.set(key, val); }
deba@414	3159	}
deba@416	3160
kpeter@449	3161	ReturnValue operator[](const Node& key) {
deba@488	3162	if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
deba@416	3163	else { return _out_map[key]; }
deba@414	3164	}
deba@414	3165
kpeter@449	3166	ConstReturnValue operator[](const Node& key) const {
deba@416	3167	if (Adaptor::inNode(key)) { return _in_map[key]; }
deba@416	3168	else { return _out_map[key]; }
deba@414	3169	}
deba@414	3170
deba@414	3171	private:
deba@414	3172	NodeImpl _in_map, _out_map;
deba@414	3173	};
deba@414	3174
deba@488	3175	template <typename V>
deba@416	3176	class ArcMapBase
deba@488	3177	: public MapTraits<typename Parent::template ArcMap<V> > {
deba@488	3178	typedef typename Parent::template ArcMap<V> ArcImpl;
deba@488	3179	typedef typename Parent::template NodeMap<V> NodeImpl;
deba@414	3180	public:
deba@414	3181	typedef Arc Key;
deba@488	3182	typedef V Value;
kpeter@449	3183	typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
kpeter@449	3184	typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
kpeter@449	3185	typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
kpeter@449	3186	typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
kpeter@449	3187	typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
deba@414	3188
deba@488	3189	ArcMapBase(const SplitNodesBase<DGR>& adaptor)
deba@416	3190	: _arc_map(adaptor._digraph), _node_map(adaptor._digraph) {}
deba@488	3191	ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
deba@416	3192	: _arc_map(*adaptor._digraph, value),
deba@416	3193	_node_map(*adaptor._digraph, value) {}
deba@414	3194
deba@488	3195	void set(const Arc& key, const V& val) {
deba@488	3196	if (SplitNodesBase<DGR>::origArc(key)) {
kpeter@495	3197	_arc_map.set(static_cast<const DigraphArc&>(key), val);
deba@414	3198	} else {
kpeter@495	3199	_node_map.set(static_cast<const DigraphNode&>(key), val);
deba@414	3200	}
deba@414	3201	}
deba@416	3202
kpeter@449	3203	ReturnValue operator[](const Arc& key) {
deba@488	3204	if (SplitNodesBase<DGR>::origArc(key)) {
kpeter@495	3205	return _arc_map[static_cast<const DigraphArc&>(key)];
deba@414	3206	} else {
kpeter@495	3207	return _node_map[static_cast<const DigraphNode&>(key)];
deba@414	3208	}
deba@414	3209	}
deba@414	3210
kpeter@449	3211	ConstReturnValue operator[](const Arc& key) const {
deba@488	3212	if (SplitNodesBase<DGR>::origArc(key)) {
kpeter@495	3213	return _arc_map[static_cast<const DigraphArc&>(key)];
deba@414	3214	} else {
kpeter@495	3215	return _node_map[static_cast<const DigraphNode&>(key)];
deba@414	3216	}
deba@414	3217	}
deba@414	3218
deba@414	3219	private:
deba@414	3220	ArcImpl _arc_map;
deba@414	3221	NodeImpl _node_map;
deba@414	3222	};
deba@414	3223
deba@414	3224	public:
deba@414	3225
deba@488	3226	template <typename V>
deba@416	3227	class NodeMap
deba@488	3228	: public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >
deba@414	3229	{
deba@414	3230	public:
deba@488	3231	typedef V Value;
deba@488	3232	typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
deba@488	3233
deba@488	3234	NodeMap(const SplitNodesBase<DGR>& adaptor)
deba@416	3235	: Parent(adaptor) {}
deba@416	3236
deba@488	3237	NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
deba@416	3238	: Parent(adaptor, value) {}
deba@416	3239
deba@414	3240	private:
deba@414	3241	NodeMap& operator=(const NodeMap& cmap) {
deba@416	3242	return operator=<NodeMap>(cmap);
deba@414	3243	}
deba@416	3244
deba@414	3245	template <typename CMap>
deba@414	3246	NodeMap& operator=(const CMap& cmap) {
deba@414	3247	Parent::operator=(cmap);
deba@416	3248	return *this;
deba@414	3249	}
deba@414	3250	};
deba@414	3251
deba@488	3252	template <typename V>
deba@416	3253	class ArcMap
deba@488	3254	: public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >
deba@414	3255	{
deba@414	3256	public:
deba@488	3257	typedef V Value;
deba@488	3258	typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
deba@488	3259
deba@488	3260	ArcMap(const SplitNodesBase<DGR>& adaptor)
deba@416	3261	: Parent(adaptor) {}
deba@416	3262
deba@488	3263	ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
deba@416	3264	: Parent(adaptor, value) {}
deba@416	3265
deba@414	3266	private:
deba@414	3267	ArcMap& operator=(const ArcMap& cmap) {
deba@416	3268	return operator=<ArcMap>(cmap);
deba@414	3269	}
deba@416	3270
deba@414	3271	template <typename CMap>
deba@414	3272	ArcMap& operator=(const CMap& cmap) {
deba@414	3273	Parent::operator=(cmap);
deba@416	3274	return *this;
deba@414	3275	}
deba@414	3276	};
deba@414	3277
deba@414	3278	protected:
deba@414	3279
deba@416	3280	SplitNodesBase() : _digraph(0) {}
deba@414	3281
deba@488	3282	DGR* _digraph;
deba@488	3283
deba@488	3284	void initialize(Digraph& digraph) {
deba@414	3285	_digraph = &digraph;
deba@414	3286	}
deba@416	3287
deba@414	3288	};
deba@414	3289
deba@414	3290	/// \ingroup graph_adaptors
deba@414	3291	///
kpeter@451	3292	/// \brief Adaptor class for splitting the nodes of a digraph.
deba@416	3293	///
kpeter@451	3294	/// SplitNodes adaptor can be used for splitting each node into an
kpeter@451	3295	/// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
kpeter@451	3296	/// replaces each node \f$ u \f$ in the digraph with two nodes,
kpeter@451	3297	/// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
kpeter@451	3298	/// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
kpeter@451	3299	/// new target of the arc will be \f$ u_{in} \f$ and similarly the
kpeter@451	3300	/// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
kpeter@451	3301	/// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
kpeter@451	3302	/// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
deba@414	3303	///
kpeter@451	3304	/// The aim of this class is running an algorithm with respect to node
kpeter@451	3305	/// costs or capacities if the algorithm considers only arc costs or
kpeter@451	3306	/// capacities directly.
kpeter@451	3307	/// In this case you can use \c SplitNodes adaptor, and set the node
kpeter@451	3308	/// costs/capacities of the original digraph to the \e bind \e arcs
kpeter@451	3309	/// in the adaptor.
deba@414	3310	///
deba@488	3311	/// \tparam DGR The type of the adapted digraph.
kpeter@451	3312	/// It must conform to the \ref concepts::Digraph "Digraph" concept.
kpeter@451	3313	/// It is implicitly \c const.
kpeter@451	3314	///
kpeter@451	3315	/// \note The \c Node type of this adaptor is converible to the \c Node
kpeter@451	3316	/// type of the adapted digraph.
deba@488	3317	template <typename DGR>
kpeter@453	3318	#ifdef DOXYGEN
kpeter@453	3319	class SplitNodes {
kpeter@453	3320	#else
deba@416	3321	class SplitNodes
deba@488	3322	: public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
kpeter@453	3323	#endif
deba@414	3324	public:
deba@488	3325	typedef DGR Digraph;
deba@488	3326	typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
deba@488	3327
deba@488	3328	typedef typename DGR::Node DigraphNode;
deba@488	3329	typedef typename DGR::Arc DigraphArc;
deba@415	3330
deba@414	3331	typedef typename Parent::Node Node;
deba@414	3332	typedef typename Parent::Arc Arc;
deba@414	3333
kpeter@451	3334	/// \brief Constructor
deba@414	3335	///
deba@414	3336	/// Constructor of the adaptor.
deba@488	3337	SplitNodes(const DGR& g) {
deba@488	3338	Parent::initialize(g);
deba@414	3339	}
deba@414	3340
kpeter@451	3341	/// \brief Returns \c true if the given node is an in-node.
deba@415	3342	///
kpeter@451	3343	/// Returns \c true if the given node is an in-node.
deba@415	3344	static bool inNode(const Node& n) {
deba@415	3345	return Parent::inNode(n);
deba@415	3346	}
deba@415	3347
kpeter@451	3348	/// \brief Returns \c true if the given node is an out-node.
deba@415	3349	///
kpeter@451	3350	/// Returns \c true if the given node is an out-node.
deba@415	3351	static bool outNode(const Node& n) {
deba@415	3352	return Parent::outNode(n);
deba@415	3353	}
deba@415	3354
kpeter@451	3355	/// \brief Returns \c true if the given arc is an original arc.
deba@415	3356	///
kpeter@451	3357	/// Returns \c true if the given arc is one of the arcs in the
kpeter@451	3358	/// original digraph.
deba@415	3359	static bool origArc(const Arc& a) {
deba@415	3360	return Parent::origArc(a);
deba@415	3361	}
deba@415	3362
kpeter@451	3363	/// \brief Returns \c true if the given arc is a bind arc.
deba@415	3364	///
kpeter@451	3365	/// Returns \c true if the given arc is a bind arc, i.e. it connects
kpeter@451	3366	/// an in-node and an out-node.
deba@415	3367	static bool bindArc(const Arc& a) {
deba@415	3368	return Parent::bindArc(a);
deba@415	3369	}
deba@415	3370
kpeter@451	3371	/// \brief Returns the in-node created from the given original node.
deba@415	3372	///
kpeter@451	3373	/// Returns the in-node created from the given original node.
deba@415	3374	static Node inNode(const DigraphNode& n) {
deba@415	3375	return Parent::inNode(n);
deba@415	3376	}
deba@415	3377
kpeter@451	3378	/// \brief Returns the out-node created from the given original node.
deba@415	3379	///
kpeter@451	3380	/// Returns the out-node created from the given original node.
deba@415	3381	static Node outNode(const DigraphNode& n) {
deba@415	3382	return Parent::outNode(n);
deba@415	3383	}
deba@415	3384
kpeter@451	3385	/// \brief Returns the bind arc that corresponds to the given
kpeter@451	3386	/// original node.
deba@416	3387	///
kpeter@451	3388	/// Returns the bind arc in the adaptor that corresponds to the given
kpeter@451	3389	/// original node, i.e. the arc connecting the in-node and out-node
kpeter@451	3390	/// of \c n.
deba@415	3391	static Arc arc(const DigraphNode& n) {
deba@415	3392	return Parent::arc(n);
deba@415	3393	}
deba@415	3394
kpeter@451	3395	/// \brief Returns the arc that corresponds to the given original arc.
deba@416	3396	///
kpeter@451	3397	/// Returns the arc in the adaptor that corresponds to the given
kpeter@451	3398	/// original arc.
deba@415	3399	static Arc arc(const DigraphArc& a) {
deba@415	3400	return Parent::arc(a);
deba@415	3401	}
deba@415	3402
kpeter@451	3403	/// \brief Node map combined from two original node maps
deba@414	3404	///
kpeter@451	3405	/// This map adaptor class adapts two node maps of the original digraph
kpeter@451	3406	/// to get a node map of the split digraph.
kpeter@559	3407	/// Its value type is inherited from the first node map type (\c IN).
kpeter@559	3408	/// \tparam IN The type of the node map for the in-nodes.
kpeter@559	3409	/// \tparam OUT The type of the node map for the out-nodes.
kpeter@559	3410	template <typename IN, typename OUT>
deba@414	3411	class CombinedNodeMap {
deba@414	3412	public:
deba@414	3413
kpeter@451	3414	/// The key type of the map
deba@414	3415	typedef Node Key;
kpeter@451	3416	/// The value type of the map
kpeter@559	3417	typedef typename IN::Value Value;
kpeter@559	3418
kpeter@559	3419	typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
kpeter@559	3420	typedef typename MapTraits<IN>::ReturnValue ReturnValue;
kpeter@559	3421	typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
kpeter@559	3422	typedef typename MapTraits<IN>::ReturnValue Reference;
kpeter@559	3423	typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
kpeter@449	3424
kpeter@451	3425	/// Constructor
kpeter@559	3426	CombinedNodeMap(IN& in_map, OUT& out_map)
deba@416	3427	: _in_map(in_map), _out_map(out_map) {}
deba@414	3428
kpeter@451	3429	/// Returns the value associated with the given key.
kpeter@451	3430	Value operator[](const Key& key) const {
deba@488	3431	if (SplitNodesBase<const DGR>::inNode(key)) {
kpeter@451	3432	return _in_map[key];
kpeter@451	3433	} else {
kpeter@451	3434	return _out_map[key];
kpeter@451	3435	}
kpeter@451	3436	}
kpeter@451	3437
kpeter@451	3438	/// Returns a reference to the value associated with the given key.
deba@414	3439	Value& operator[](const Key& key) {
deba@488	3440	if (SplitNodesBase<const DGR>::inNode(key)) {
deba@416	3441	return _in_map[key];
deba@416	3442	} else {
deba@416	3443	return _out_map[key];
deba@416	3444	}
deba@414	3445	}
deba@414	3446
kpeter@451	3447	/// Sets the value associated with the given key.
deba@414	3448	void set(const Key& key, const Value& value) {
deba@488	3449	if (SplitNodesBase<const DGR>::inNode(key)) {
deba@416	3450	_in_map.set(key, value);
deba@416	3451	} else {
deba@416	3452	_out_map.set(key, value);
deba@416	3453	}
deba@414	3454	}
deba@416	3455
deba@414	3456	private:
deba@416	3457
kpeter@559	3458	IN& _in_map;
kpeter@559	3459	OUT& _out_map;
deba@416	3460
deba@414	3461	};
deba@414	3462
deba@414	3463
kpeter@451	3464	/// \brief Returns a combined node map
deba@416	3465	///
kpeter@451	3466	/// This function just returns a combined node map.
kpeter@559	3467	template <typename IN, typename OUT>
kpeter@559	3468	static CombinedNodeMap<IN, OUT>
kpeter@559	3469	combinedNodeMap(IN& in_map, OUT& out_map) {
kpeter@559	3470	return CombinedNodeMap<IN, OUT>(in_map, out_map);
deba@414	3471	}
deba@414	3472
kpeter@559	3473	template <typename IN, typename OUT>
kpeter@559	3474	static CombinedNodeMap<const IN, OUT>
kpeter@559	3475	combinedNodeMap(const IN& in_map, OUT& out_map) {
kpeter@559	3476	return CombinedNodeMap<const IN, OUT>(in_map, out_map);
deba@414	3477	}
deba@414	3478
kpeter@559	3479	template <typename IN, typename OUT>
kpeter@559	3480	static CombinedNodeMap<IN, const OUT>
kpeter@559	3481	combinedNodeMap(IN& in_map, const OUT& out_map) {
kpeter@559	3482	return CombinedNodeMap<IN, const OUT>(in_map, out_map);
deba@414	3483	}
deba@414	3484
kpeter@559	3485	template <typename IN, typename OUT>
kpeter@559	3486	static CombinedNodeMap<const IN, const OUT>
kpeter@559	3487	combinedNodeMap(const IN& in_map, const OUT& out_map) {
kpeter@559	3488	return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
deba@414	3489	}
deba@414	3490
kpeter@451	3491	/// \brief Arc map combined from an arc map and a node map of the
kpeter@451	3492	/// original digraph.
deba@414	3493	///
kpeter@451	3494	/// This map adaptor class adapts an arc map and a node map of the
kpeter@451	3495	/// original digraph to get an arc map of the split digraph.
kpeter@559	3496	/// Its value type is inherited from the original arc map type (\c AM).
kpeter@559	3497	/// \tparam AM The type of the arc map.
kpeter@559	3498	/// \tparam NM the type of the node map.
kpeter@559	3499	template <typename AM, typename NM>
deba@414	3500	class CombinedArcMap {
deba@414	3501	public:
deba@416	3502
kpeter@451	3503	/// The key type of the map
deba@414	3504	typedef Arc Key;
kpeter@451	3505	/// The value type of the map
kpeter@559	3506	typedef typename AM::Value Value;
kpeter@559	3507
kpeter@559	3508	typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
kpeter@559	3509	typedef typename MapTraits<AM>::ReturnValue ReturnValue;
kpeter@559	3510	typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
kpeter@559	3511	typedef typename MapTraits<AM>::ReturnValue Reference;
kpeter@559	3512	typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
kpeter@449	3513
kpeter@451	3514	/// Constructor
kpeter@559	3515	CombinedArcMap(AM& arc_map, NM& node_map)
deba@416	3516	: _arc_map(arc_map), _node_map(node_map) {}
deba@414	3517
kpeter@451	3518	/// Returns the value associated with the given key.
kpeter@451	3519	Value operator[](const Key& arc) const {
deba@488	3520	if (SplitNodesBase<const DGR>::origArc(arc)) {
kpeter@451	3521	return _arc_map[arc];
kpeter@451	3522	} else {
kpeter@451	3523	return _node_map[arc];
kpeter@451	3524	}
kpeter@451	3525	}
kpeter@451	3526
kpeter@451	3527	/// Returns a reference to the value associated with the given key.
kpeter@451	3528	Value& operator[](const Key& arc) {
deba@488	3529	if (SplitNodesBase<const DGR>::origArc(arc)) {
kpeter@451	3530	return _arc_map[arc];
kpeter@451	3531	} else {
kpeter@451	3532	return _node_map[arc];
kpeter@451	3533	}
kpeter@451	3534	}
kpeter@451	3535
kpeter@451	3536	/// Sets the value associated with the given key.
deba@414	3537	void set(const Arc& arc, const Value& val) {
deba@488	3538	if (SplitNodesBase<const DGR>::origArc(arc)) {
deba@416	3539	_arc_map.set(arc, val);
deba@416	3540	} else {
deba@416	3541	_node_map.set(arc, val);
deba@416	3542	}
deba@414	3543	}
deba@414	3544
deba@414	3545	private:
kpeter@559	3546
kpeter@559	3547	AM& _arc_map;
kpeter@559	3548	NM& _node_map;
kpeter@559	3549
deba@414	3550	};
deba@416	3551
kpeter@451	3552	/// \brief Returns a combined arc map
deba@416	3553	///
kpeter@451	3554	/// This function just returns a combined arc map.
kpeter@453	3555	template <typename ArcMap, typename NodeMap>
kpeter@453	3556	static CombinedArcMap<ArcMap, NodeMap>
kpeter@453	3557	combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
kpeter@453	3558	return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
deba@414	3559	}
deba@414	3560
kpeter@453	3561	template <typename ArcMap, typename NodeMap>
kpeter@453	3562	static CombinedArcMap<const ArcMap, NodeMap>
kpeter@453	3563	combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
kpeter@453	3564	return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
deba@414	3565	}
deba@414	3566
kpeter@453	3567	template <typename ArcMap, typename NodeMap>
kpeter@453	3568	static CombinedArcMap<ArcMap, const NodeMap>
kpeter@453	3569	combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
kpeter@453	3570	return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
deba@414	3571	}
deba@414	3572
kpeter@453	3573	template <typename ArcMap, typename NodeMap>
kpeter@453	3574	static CombinedArcMap<const ArcMap, const NodeMap>
kpeter@453	3575	combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
kpeter@453	3576	return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
deba@414	3577	}
deba@414	3578
deba@414	3579	};
deba@414	3580
kpeter@451	3581	/// \brief Returns a (read-only) SplitNodes adaptor
deba@414	3582	///
kpeter@451	3583	/// This function just returns a (read-only) \ref SplitNodes adaptor.
kpeter@451	3584	/// \ingroup graph_adaptors
kpeter@451	3585	/// \relates SplitNodes
deba@488	3586	template<typename DGR>
deba@488	3587	SplitNodes<DGR>
deba@488	3588	splitNodes(const DGR& digraph) {
deba@488	3589	return SplitNodes<DGR>(digraph);
deba@414	3590	}
deba@414	3591
deba@488	3592	#undef LEMON_SCOPE_FIX
deba@488	3593
deba@414	3594	} //namespace lemon
deba@414	3595
deba@416	3596	#endif //LEMON_ADAPTORS_H

author	Balazs Dezso <deba@inf.elte.hu>
	Sat, 18 Apr 2009 21:54:30 +0200
changeset 598	a3402913cffe
parent 519	c786cd201266
child 579	d11bf7998905
permissions	-rw-r--r--