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

author	Alpar Juttner <alpar@cs.elte.hu>
	Mon, 16 Feb 2009 18:15:52 +0000
changeset 492	b9b3473327e3
parent 464	acfb0f24d178
child 495	dab9e610e37d
permissions	-rw-r--r--