lemon-1.0: lemon/graph_utils.h@701c529ba737 (annotated)

alpar@100	1	/* -- C++ --
alpar@100	2	*
alpar@100	3	* This file is a part of LEMON, a generic C++ optimization library
alpar@100	4	*
alpar@100	5	* Copyright (C) 2003-2008
alpar@100	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100	8	*
alpar@100	9	* Permission to use, modify and distribute this software is granted
alpar@100	10	* provided that this copyright notice appears in all copies. For
alpar@100	11	* precise terms see the accompanying LICENSE file.
alpar@100	12	*
alpar@100	13	* This software is provided "AS IS" with no warranty of any kind,
alpar@100	14	* express or implied, and with no claim as to its suitability for any
alpar@100	15	* purpose.
alpar@100	16	*
alpar@100	17	*/
alpar@100	18
alpar@100	19	#ifndef LEMON_GRAPH_UTILS_H
alpar@100	20	#define LEMON_GRAPH_UTILS_H
alpar@100	21
alpar@100	22	#include <iterator>
alpar@100	23	#include <vector>
alpar@100	24	#include <map>
alpar@100	25	#include <cmath>
alpar@100	26	#include <algorithm>
alpar@100	27
alpar@100	28	#include <lemon/bits/invalid.h>
alpar@100	29	#include <lemon/bits/utility.h>
alpar@100	30	#include <lemon/maps.h>
alpar@100	31	#include <lemon/bits/traits.h>
alpar@100	32
alpar@100	33	#include <lemon/bits/alteration_notifier.h>
alpar@100	34	#include <lemon/bits/default_map.h>
alpar@100	35
alpar@100	36	///\ingroup gutils
alpar@100	37	///\file
deba@139	38	///\brief Graph utilities.
alpar@100	39
alpar@100	40	namespace lemon {
alpar@100	41
alpar@100	42	/// \addtogroup gutils
alpar@100	43	/// @{
alpar@100	44
alpar@100	45	///Creates convenience typedefs for the digraph types and iterators
alpar@100	46
alpar@100	47	///This \c \#define creates convenience typedefs for the following types
alpar@100	48	///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
deba@139	49	///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
deba@139	50	///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
deba@139	51	#define DIGRAPH_TYPEDEFS(Digraph) \
deba@139	52	typedef Digraph::Node Node; \
deba@139	53	typedef Digraph::NodeIt NodeIt; \
deba@139	54	typedef Digraph::Arc Arc; \
deba@139	55	typedef Digraph::ArcIt ArcIt; \
deba@139	56	typedef Digraph::InArcIt InArcIt; \
deba@139	57	typedef Digraph::OutArcIt OutArcIt
alpar@100	58
alpar@100	59	///Creates convenience typedefs for the graph types and iterators
alpar@100	60
deba@139	61	///This \c \#define creates the same convenience typedefs as defined
deba@139	62	///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
deba@139	63	///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
deba@139	64	///\c DoubleEdgeMap.
deba@139	65	#define GRAPH_TYPEDEFS(Graph) \
deba@139	66	DIGRAPH_TYPEDEFS(Graph); \
deba@139	67	typedef Graph::Edge Edge; \
deba@139	68	typedef Graph::EdgeIt EdgeIt; \
deba@139	69	typedef Graph::IncEdgeIt IncEdgeIt
deba@139	70
deba@139	71	/// \brief Function to count the items in the graph.
alpar@100	72	///
deba@139	73	/// This function counts the items (nodes, arcs etc) in the graph.
alpar@100	74	/// The complexity of the function is O(n) because
alpar@100	75	/// it iterates on all of the items.
deba@139	76	template <typename Graph, typename Item>
deba@139	77	inline int countItems(const Graph& g) {
deba@139	78	typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
alpar@100	79	int num = 0;
alpar@100	80	for (ItemIt it(g); it != INVALID; ++it) {
alpar@100	81	++num;
alpar@100	82	}
alpar@100	83	return num;
alpar@100	84	}
alpar@100	85
alpar@100	86	// Node counting:
alpar@100	87
deba@139	88	namespace _graph_utils_bits {
alpar@100	89
deba@139	90	template <typename Graph, typename Enable = void>
alpar@100	91	struct CountNodesSelector {
deba@139	92	static int count(const Graph &g) {
deba@139	93	return countItems<Graph, typename Graph::Node>(g);
alpar@100	94	}
alpar@100	95	};
alpar@100	96
deba@139	97	template <typename Graph>
alpar@100	98	struct CountNodesSelector<
deba@139	99	Graph, typename
deba@139	100	enable_if<typename Graph::NodeNumTag, void>::type>
alpar@100	101	{
deba@139	102	static int count(const Graph &g) {
alpar@100	103	return g.nodeNum();
alpar@100	104	}
alpar@100	105	};
alpar@100	106	}
alpar@100	107
deba@139	108	/// \brief Function to count the nodes in the graph.
alpar@100	109	///
deba@139	110	/// This function counts the nodes in the graph.
alpar@100	111	/// The complexity of the function is O(n) but for some
deba@139	112	/// graph structures it is specialized to run in O(1).
alpar@100	113	///
deba@139	114	/// If the graph contains a \e nodeNum() member function and a
alpar@100	115	/// \e NodeNumTag tag then this function calls directly the member
alpar@100	116	/// function to query the cardinality of the node set.
deba@139	117	template <typename Graph>
deba@139	118	inline int countNodes(const Graph& g) {
deba@139	119	return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
alpar@100	120	}
alpar@100	121
deba@139	122	// Arc counting:
deba@139	123
deba@139	124	namespace _graph_utils_bits {
alpar@100	125
deba@139	126	template <typename Graph, typename Enable = void>
deba@139	127	struct CountArcsSelector {
deba@139	128	static int count(const Graph &g) {
deba@139	129	return countItems<Graph, typename Graph::Arc>(g);
alpar@100	130	}
alpar@100	131	};
alpar@100	132
deba@139	133	template <typename Graph>
deba@139	134	struct CountArcsSelector<
deba@139	135	Graph,
deba@139	136	typename enable_if<typename Graph::ArcNumTag, void>::type>
alpar@100	137	{
deba@139	138	static int count(const Graph &g) {
alpar@100	139	return g.arcNum();
alpar@100	140	}
alpar@100	141	};
alpar@100	142	}
alpar@100	143
deba@139	144	/// \brief Function to count the arcs in the graph.
alpar@100	145	///
deba@139	146	/// This function counts the arcs in the graph.
alpar@100	147	/// The complexity of the function is O(e) but for some
deba@139	148	/// graph structures it is specialized to run in O(1).
alpar@100	149	///
deba@139	150	/// If the graph contains a \e arcNum() member function and a
deba@139	151	/// \e EdgeNumTag tag then this function calls directly the member
alpar@100	152	/// function to query the cardinality of the arc set.
deba@139	153	template <typename Graph>
deba@139	154	inline int countArcs(const Graph& g) {
deba@139	155	return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
alpar@100	156	}
alpar@100	157
deba@139	158	// Edge counting:
deba@139	159	namespace _graph_utils_bits {
alpar@100	160
deba@139	161	template <typename Graph, typename Enable = void>
alpar@100	162	struct CountEdgesSelector {
deba@139	163	static int count(const Graph &g) {
deba@139	164	return countItems<Graph, typename Graph::Edge>(g);
alpar@100	165	}
alpar@100	166	};
alpar@100	167
deba@139	168	template <typename Graph>
alpar@100	169	struct CountEdgesSelector<
deba@139	170	Graph,
deba@139	171	typename enable_if<typename Graph::EdgeNumTag, void>::type>
alpar@100	172	{
deba@139	173	static int count(const Graph &g) {
alpar@100	174	return g.edgeNum();
alpar@100	175	}
alpar@100	176	};
alpar@100	177	}
alpar@100	178
deba@139	179	/// \brief Function to count the edges in the graph.
alpar@100	180	///
deba@139	181	/// This function counts the edges in the graph.
deba@139	182	/// The complexity of the function is O(m) but for some
deba@139	183	/// graph structures it is specialized to run in O(1).
alpar@100	184	///
deba@139	185	/// If the graph contains a \e edgeNum() member function and a
deba@139	186	/// \e EdgeNumTag tag then this function calls directly the member
alpar@100	187	/// function to query the cardinality of the edge set.
deba@139	188	template <typename Graph>
deba@139	189	inline int countEdges(const Graph& g) {
deba@139	190	return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
alpar@100	191
alpar@100	192	}
alpar@100	193
alpar@100	194
deba@139	195	template <typename Graph, typename DegIt>
deba@139	196	inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
alpar@100	197	int num = 0;
alpar@100	198	for (DegIt it(_g, _n); it != INVALID; ++it) {
alpar@100	199	++num;
alpar@100	200	}
alpar@100	201	return num;
alpar@100	202	}
alpar@100	203
alpar@100	204	/// \brief Function to count the number of the out-arcs from node \c n.
alpar@100	205	///
alpar@100	206	/// This function counts the number of the out-arcs from node \c n
deba@139	207	/// in the graph.
deba@139	208	template <typename Graph>
deba@139	209	inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
deba@139	210	return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
alpar@100	211	}
alpar@100	212
alpar@100	213	/// \brief Function to count the number of the in-arcs to node \c n.
alpar@100	214	///
alpar@100	215	/// This function counts the number of the in-arcs to node \c n
deba@139	216	/// in the graph.
deba@139	217	template <typename Graph>
deba@139	218	inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
deba@139	219	return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
alpar@100	220	}
alpar@100	221
deba@139	222	/// \brief Function to count the number of the inc-edges to node \c n.
alpar@100	223	///
deba@139	224	/// This function counts the number of the inc-edges to node \c n
deba@139	225	/// in the graph.
deba@139	226	template <typename Graph>
deba@139	227	inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
deba@139	228	return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
alpar@100	229	}
alpar@100	230
deba@139	231	namespace _graph_utils_bits {
alpar@100	232
deba@139	233	template <typename Graph, typename Enable = void>
alpar@100	234	struct FindArcSelector {
deba@139	235	typedef typename Graph::Node Node;
deba@139	236	typedef typename Graph::Arc Arc;
deba@139	237	static Arc find(const Graph &g, Node u, Node v, Arc e) {
alpar@100	238	if (e == INVALID) {
alpar@100	239	g.firstOut(e, u);
alpar@100	240	} else {
alpar@100	241	g.nextOut(e);
alpar@100	242	}
alpar@100	243	while (e != INVALID && g.target(e) != v) {
alpar@100	244	g.nextOut(e);
alpar@100	245	}
alpar@100	246	return e;
alpar@100	247	}
alpar@100	248	};
alpar@100	249
deba@139	250	template <typename Graph>
alpar@100	251	struct FindArcSelector<
deba@139	252	Graph,
deba@139	253	typename enable_if<typename Graph::FindEdgeTag, void>::type>
alpar@100	254	{
deba@139	255	typedef typename Graph::Node Node;
deba@139	256	typedef typename Graph::Arc Arc;
deba@139	257	static Arc find(const Graph &g, Node u, Node v, Arc prev) {
alpar@100	258	return g.findArc(u, v, prev);
alpar@100	259	}
alpar@100	260	};
alpar@100	261	}
alpar@100	262
deba@139	263	/// \brief Finds an arc between two nodes of a graph.
alpar@100	264	///
deba@139	265	/// Finds an arc from node \c u to node \c v in graph \c g.
alpar@100	266	///
alpar@100	267	/// If \c prev is \ref INVALID (this is the default value), then
alpar@100	268	/// it finds the first arc from \c u to \c v. Otherwise it looks for
alpar@100	269	/// the next arc from \c u to \c v after \c prev.
alpar@100	270	/// \return The found arc or \ref INVALID if there is no such an arc.
alpar@100	271	///
alpar@100	272	/// Thus you can iterate through each arc from \c u to \c v as it follows.
alpar@100	273	///\code
alpar@100	274	/// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
alpar@100	275	/// ...
alpar@100	276	/// }
alpar@100	277	///\endcode
alpar@100	278	///
alpar@100	279	///\sa ArcLookUp
alpar@100	280	///\sa AllArcLookUp
alpar@100	281	///\sa DynArcLookUp
alpar@100	282	///\sa ConArcIt
deba@139	283	template <typename Graph>
deba@139	284	inline typename Graph::Arc
deba@139	285	findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
deba@139	286	typename Graph::Arc prev = INVALID) {
deba@139	287	return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
alpar@100	288	}
alpar@100	289
alpar@100	290	/// \brief Iterator for iterating on arcs connected the same nodes.
alpar@100	291	///
alpar@100	292	/// Iterator for iterating on arcs connected the same nodes. It is
alpar@100	293	/// higher level interface for the findArc() function. You can
alpar@100	294	/// use it the following way:
alpar@100	295	///\code
deba@139	296	/// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
alpar@100	297	/// ...
alpar@100	298	/// }
alpar@100	299	///\endcode
alpar@100	300	///
alpar@100	301	///\sa findArc()
alpar@100	302	///\sa ArcLookUp
alpar@100	303	///\sa AllArcLookUp
alpar@100	304	///\sa DynArcLookUp
alpar@100	305	///
alpar@100	306	/// \author Balazs Dezso
deba@139	307	template <typename _Graph>
deba@139	308	class ConArcIt : public _Graph::Arc {
alpar@100	309	public:
alpar@100	310
deba@139	311	typedef _Graph Graph;
deba@139	312	typedef typename Graph::Arc Parent;
alpar@100	313
deba@139	314	typedef typename Graph::Arc Arc;
deba@139	315	typedef typename Graph::Node Node;
alpar@100	316
alpar@100	317	/// \brief Constructor.
alpar@100	318	///
alpar@100	319	/// Construct a new ConArcIt iterating on the arcs which
alpar@100	320	/// connects the \c u and \c v node.
deba@139	321	ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
deba@139	322	Parent::operator=(findArc(_graph, u, v));
alpar@100	323	}
alpar@100	324
alpar@100	325	/// \brief Constructor.
alpar@100	326	///
alpar@100	327	/// Construct a new ConArcIt which continues the iterating from
alpar@100	328	/// the \c e arc.
deba@139	329	ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
alpar@100	330
alpar@100	331	/// \brief Increment operator.
alpar@100	332	///
alpar@100	333	/// It increments the iterator and gives back the next arc.
alpar@100	334	ConArcIt& operator++() {
deba@139	335	Parent::operator=(findArc(_graph, _graph.source(*this),
deba@139	336	_graph.target(this), this));
alpar@100	337	return *this;
alpar@100	338	}
alpar@100	339	private:
deba@139	340	const Graph& _graph;
alpar@100	341	};
alpar@100	342
deba@139	343	namespace _graph_utils_bits {
alpar@100	344
deba@139	345	template <typename Graph, typename Enable = void>
alpar@100	346	struct FindEdgeSelector {
deba@139	347	typedef typename Graph::Node Node;
deba@139	348	typedef typename Graph::Edge Edge;
deba@139	349	static Edge find(const Graph &g, Node u, Node v, Edge e) {
alpar@100	350	bool b;
alpar@100	351	if (u != v) {
alpar@100	352	if (e == INVALID) {
alpar@100	353	g.firstInc(e, b, u);
alpar@100	354	} else {
alpar@100	355	b = g.source(e) == u;
alpar@100	356	g.nextInc(e, b);
alpar@100	357	}
alpar@100	358	while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) {
alpar@100	359	g.nextInc(e, b);
alpar@100	360	}
alpar@100	361	} else {
alpar@100	362	if (e == INVALID) {
alpar@100	363	g.firstInc(e, b, u);
alpar@100	364	} else {
alpar@100	365	b = true;
alpar@100	366	g.nextInc(e, b);
alpar@100	367	}
alpar@100	368	while (e != INVALID && (!b \|\| g.target(e) != v)) {
alpar@100	369	g.nextInc(e, b);
alpar@100	370	}
alpar@100	371	}
alpar@100	372	return e;
alpar@100	373	}
alpar@100	374	};
alpar@100	375
deba@139	376	template <typename Graph>
alpar@100	377	struct FindEdgeSelector<
deba@139	378	Graph,
deba@139	379	typename enable_if<typename Graph::FindEdgeTag, void>::type>
alpar@100	380	{
deba@139	381	typedef typename Graph::Node Node;
deba@139	382	typedef typename Graph::Edge Edge;
deba@139	383	static Edge find(const Graph &g, Node u, Node v, Edge prev) {
alpar@100	384	return g.findEdge(u, v, prev);
alpar@100	385	}
alpar@100	386	};
alpar@100	387	}
alpar@100	388
deba@139	389	/// \brief Finds an edge between two nodes of a graph.
alpar@100	390	///
deba@139	391	/// Finds an edge from node \c u to node \c v in graph \c g.
deba@139	392	/// If the node \c u and node \c v is equal then each loop edge
deba@139	393	/// will be enumerated once.
alpar@100	394	///
alpar@100	395	/// If \c prev is \ref INVALID (this is the default value), then
alpar@100	396	/// it finds the first arc from \c u to \c v. Otherwise it looks for
alpar@100	397	/// the next arc from \c u to \c v after \c prev.
alpar@100	398	/// \return The found arc or \ref INVALID if there is no such an arc.
alpar@100	399	///
alpar@100	400	/// Thus you can iterate through each arc from \c u to \c v as it follows.
alpar@100	401	///\code
alpar@100	402	/// for(Edge e = findEdge(g,u,v); e != INVALID;
alpar@100	403	/// e = findEdge(g,u,v,e)) {
alpar@100	404	/// ...
alpar@100	405	/// }
alpar@100	406	///\endcode
alpar@100	407	///
alpar@100	408	///\sa ConArcIt
alpar@100	409
deba@139	410	template <typename Graph>
deba@139	411	inline typename Graph::Edge
deba@139	412	findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
deba@139	413	typename Graph::Edge p = INVALID) {
deba@139	414	return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
alpar@100	415	}
alpar@100	416
alpar@100	417	/// \brief Iterator for iterating on edges connected the same nodes.
alpar@100	418	///
alpar@100	419	/// Iterator for iterating on edges connected the same nodes. It is
alpar@100	420	/// higher level interface for the findEdge() function. You can
alpar@100	421	/// use it the following way:
alpar@100	422	///\code
deba@139	423	/// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
alpar@100	424	/// ...
alpar@100	425	/// }
alpar@100	426	///\endcode
alpar@100	427	///
alpar@100	428	///\sa findEdge()
alpar@100	429	///
alpar@100	430	/// \author Balazs Dezso
deba@139	431	template <typename _Graph>
deba@139	432	class ConEdgeIt : public _Graph::Edge {
alpar@100	433	public:
alpar@100	434
deba@139	435	typedef _Graph Graph;
deba@139	436	typedef typename Graph::Edge Parent;
alpar@100	437
deba@139	438	typedef typename Graph::Edge Edge;
deba@139	439	typedef typename Graph::Node Node;
alpar@100	440
alpar@100	441	/// \brief Constructor.
alpar@100	442	///
deba@139	443	/// Construct a new ConEdgeIt iterating on the edges which
alpar@100	444	/// connects the \c u and \c v node.
deba@139	445	ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
deba@139	446	Parent::operator=(findEdge(_graph, u, v));
alpar@100	447	}
alpar@100	448
alpar@100	449	/// \brief Constructor.
alpar@100	450	///
alpar@100	451	/// Construct a new ConEdgeIt which continues the iterating from
deba@139	452	/// the \c e edge.
deba@139	453	ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
alpar@100	454
alpar@100	455	/// \brief Increment operator.
alpar@100	456	///
deba@139	457	/// It increments the iterator and gives back the next edge.
alpar@100	458	ConEdgeIt& operator++() {
deba@139	459	Parent::operator=(findEdge(_graph, _graph.source(*this),
deba@139	460	_graph.target(this), this));
alpar@100	461	return *this;
alpar@100	462	}
alpar@100	463	private:
deba@139	464	const Graph& _graph;
alpar@100	465	};
alpar@100	466
deba@139	467	namespace _graph_utils_bits {
alpar@100	468
alpar@100	469	template <typename Digraph, typename Item, typename RefMap>
alpar@100	470	class MapCopyBase {
alpar@100	471	public:
alpar@100	472	virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
alpar@100	473
alpar@100	474	virtual ~MapCopyBase() {}
alpar@100	475	};
alpar@100	476
alpar@100	477	template <typename Digraph, typename Item, typename RefMap,
alpar@100	478	typename ToMap, typename FromMap>
alpar@100	479	class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
alpar@100	480	public:
alpar@100	481
alpar@100	482	MapCopy(ToMap& tmap, const FromMap& map)
alpar@100	483	: _tmap(tmap), _map(map) {}
alpar@100	484
alpar@100	485	virtual void copy(const Digraph& digraph, const RefMap& refMap) {
alpar@100	486	typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
alpar@100	487	for (ItemIt it(digraph); it != INVALID; ++it) {
alpar@100	488	_tmap.set(refMap[it], _map[it]);
alpar@100	489	}
alpar@100	490	}
alpar@100	491
alpar@100	492	private:
alpar@100	493	ToMap& _tmap;
alpar@100	494	const FromMap& _map;
alpar@100	495	};
alpar@100	496
alpar@100	497	template <typename Digraph, typename Item, typename RefMap, typename It>
alpar@100	498	class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
alpar@100	499	public:
alpar@100	500
alpar@100	501	ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
alpar@100	502
alpar@100	503	virtual void copy(const Digraph&, const RefMap& refMap) {
alpar@100	504	_it = refMap[_item];
alpar@100	505	}
alpar@100	506
alpar@100	507	private:
alpar@100	508	It& _it;
alpar@100	509	Item _item;
alpar@100	510	};
alpar@100	511
alpar@100	512	template <typename Digraph, typename Item, typename RefMap, typename Ref>
alpar@100	513	class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
alpar@100	514	public:
alpar@100	515
alpar@100	516	RefCopy(Ref& map) : _map(map) {}
alpar@100	517
alpar@100	518	virtual void copy(const Digraph& digraph, const RefMap& refMap) {
alpar@100	519	typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
alpar@100	520	for (ItemIt it(digraph); it != INVALID; ++it) {
alpar@100	521	_map.set(it, refMap[it]);
alpar@100	522	}
alpar@100	523	}
alpar@100	524
alpar@100	525	private:
alpar@100	526	Ref& _map;
alpar@100	527	};
alpar@100	528
alpar@100	529	template <typename Digraph, typename Item, typename RefMap,
alpar@100	530	typename CrossRef>
alpar@100	531	class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
alpar@100	532	public:
alpar@100	533
alpar@100	534	CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
alpar@100	535
alpar@100	536	virtual void copy(const Digraph& digraph, const RefMap& refMap) {
alpar@100	537	typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
alpar@100	538	for (ItemIt it(digraph); it != INVALID; ++it) {
alpar@100	539	_cmap.set(refMap[it], it);
alpar@100	540	}
alpar@100	541	}
alpar@100	542
alpar@100	543	private:
alpar@100	544	CrossRef& _cmap;
alpar@100	545	};
alpar@100	546
alpar@100	547	template <typename Digraph, typename Enable = void>
alpar@100	548	struct DigraphCopySelector {
alpar@100	549	template <typename From, typename NodeRefMap, typename ArcRefMap>
alpar@100	550	static void copy(Digraph &to, const From& from,
alpar@100	551	NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
alpar@100	552	for (typename From::NodeIt it(from); it != INVALID; ++it) {
alpar@100	553	nodeRefMap[it] = to.addNode();
alpar@100	554	}
alpar@100	555	for (typename From::ArcIt it(from); it != INVALID; ++it) {
alpar@100	556	arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
alpar@100	557	nodeRefMap[from.target(it)]);
alpar@100	558	}
alpar@100	559	}
alpar@100	560	};
alpar@100	561
alpar@100	562	template <typename Digraph>
alpar@100	563	struct DigraphCopySelector<
alpar@100	564	Digraph,
alpar@100	565	typename enable_if<typename Digraph::BuildTag, void>::type>
alpar@100	566	{
alpar@100	567	template <typename From, typename NodeRefMap, typename ArcRefMap>
alpar@100	568	static void copy(Digraph &to, const From& from,
alpar@100	569	NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
alpar@100	570	to.build(from, nodeRefMap, arcRefMap);
alpar@100	571	}
alpar@100	572	};
alpar@100	573
alpar@100	574	template <typename Graph, typename Enable = void>
alpar@100	575	struct GraphCopySelector {
alpar@100	576	template <typename From, typename NodeRefMap, typename EdgeRefMap>
alpar@100	577	static void copy(Graph &to, const From& from,
alpar@100	578	NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
alpar@100	579	for (typename From::NodeIt it(from); it != INVALID; ++it) {
alpar@100	580	nodeRefMap[it] = to.addNode();
alpar@100	581	}
alpar@100	582	for (typename From::EdgeIt it(from); it != INVALID; ++it) {
alpar@100	583	edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
alpar@100	584	nodeRefMap[from.target(it)]);
alpar@100	585	}
alpar@100	586	}
alpar@100	587	};
alpar@100	588
alpar@100	589	template <typename Graph>
alpar@100	590	struct GraphCopySelector<
alpar@100	591	Graph,
alpar@100	592	typename enable_if<typename Graph::BuildTag, void>::type>
alpar@100	593	{
alpar@100	594	template <typename From, typename NodeRefMap, typename EdgeRefMap>
alpar@100	595	static void copy(Graph &to, const From& from,
alpar@100	596	NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
alpar@100	597	to.build(from, nodeRefMap, edgeRefMap);
alpar@100	598	}
alpar@100	599	};
alpar@100	600
alpar@100	601	}
alpar@100	602
alpar@100	603	/// \brief Class to copy a digraph.
alpar@100	604	///
alpar@100	605	/// Class to copy a digraph to another digraph (duplicate a digraph). The
alpar@100	606	/// simplest way of using it is through the \c copyDigraph() function.
deba@139	607	///
deba@139	608	/// This class not just make a copy of a graph, but it can create
deba@139	609	/// references and cross references between the nodes and arcs of
deba@139	610	/// the two graphs, it can copy maps for use with the newly created
deba@139	611	/// graph and copy nodes and arcs.
deba@139	612	///
deba@139	613	/// To make a copy from a graph, first an instance of DigraphCopy
deba@139	614	/// should be created, then the data belongs to the graph should
deba@139	615	/// assigned to copy. In the end, the \c run() member should be
deba@139	616	/// called.
deba@139	617	///
deba@139	618	/// The next code copies a graph with several data:
deba@139	619	///\code
deba@139	620	/// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
deba@139	621	/// // create a reference for the nodes
deba@139	622	/// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
deba@139	623	/// dc.nodeRef(nr);
deba@139	624	/// // create a cross reference (inverse) for the arcs
deba@139	625	/// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
deba@139	626	/// dc.arcCrossRef(acr);
deba@139	627	/// // copy an arc map
deba@139	628	/// OrigGraph::ArcMap<double> oamap(orig_graph);
deba@139	629	/// NewGraph::ArcMap<double> namap(new_graph);
deba@139	630	/// dc.arcMap(namap, oamap);
deba@139	631	/// // copy a node
deba@139	632	/// OrigGraph::Node on;
deba@139	633	/// NewGraph::Node nn;
deba@139	634	/// dc.node(nn, on);
deba@139	635	/// // Executions of copy
deba@139	636	/// dc.run();
deba@139	637	///\endcode
alpar@100	638	template <typename To, typename From>
alpar@100	639	class DigraphCopy {
alpar@100	640	private:
alpar@100	641
alpar@100	642	typedef typename From::Node Node;
alpar@100	643	typedef typename From::NodeIt NodeIt;
alpar@100	644	typedef typename From::Arc Arc;
alpar@100	645	typedef typename From::ArcIt ArcIt;
alpar@100	646
alpar@100	647	typedef typename To::Node TNode;
alpar@100	648	typedef typename To::Arc TArc;
alpar@100	649
alpar@100	650	typedef typename From::template NodeMap<TNode> NodeRefMap;
alpar@100	651	typedef typename From::template ArcMap<TArc> ArcRefMap;
alpar@100	652
alpar@100	653
alpar@100	654	public:
alpar@100	655
alpar@100	656
alpar@100	657	/// \brief Constructor for the DigraphCopy.
alpar@100	658	///
alpar@100	659	/// It copies the content of the \c _from digraph into the
alpar@100	660	/// \c _to digraph.
deba@139	661	DigraphCopy(To& to, const From& from)
deba@139	662	: _from(from), _to(to) {}
alpar@100	663
alpar@100	664	/// \brief Destructor of the DigraphCopy
alpar@100	665	///
alpar@100	666	/// Destructor of the DigraphCopy
alpar@100	667	~DigraphCopy() {
deba@139	668	for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139	669	delete _node_maps[i];
alpar@100	670	}
deba@139	671	for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139	672	delete _arc_maps[i];
alpar@100	673	}
alpar@100	674
alpar@100	675	}
alpar@100	676
alpar@100	677	/// \brief Copies the node references into the given map.
alpar@100	678	///
deba@139	679	/// Copies the node references into the given map. The parameter
deba@139	680	/// should be a map, which key type is the Node type of the source
deba@139	681	/// graph, while the value type is the Node type of the
deba@139	682	/// destination graph.
alpar@100	683	template <typename NodeRef>
alpar@100	684	DigraphCopy& nodeRef(NodeRef& map) {
deba@139	685	_node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
deba@139	686	NodeRefMap, NodeRef>(map));
alpar@100	687	return *this;
alpar@100	688	}
alpar@100	689
alpar@100	690	/// \brief Copies the node cross references into the given map.
alpar@100	691	///
alpar@100	692	/// Copies the node cross references (reverse references) into
deba@139	693	/// the given map. The parameter should be a map, which key type
deba@139	694	/// is the Node type of the destination graph, while the value type is
deba@139	695	/// the Node type of the source graph.
alpar@100	696	template <typename NodeCrossRef>
alpar@100	697	DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
deba@139	698	_node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
deba@139	699	NodeRefMap, NodeCrossRef>(map));
alpar@100	700	return *this;
alpar@100	701	}
alpar@100	702
alpar@100	703	/// \brief Make copy of the given map.
alpar@100	704	///
deba@139	705	/// Makes copy of the given map for the newly created digraph.
deba@139	706	/// The new map's key type is the destination graph's node type,
deba@139	707	/// and the copied map's key type is the source graph's node type.
alpar@100	708	template <typename ToMap, typename FromMap>
alpar@100	709	DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
deba@139	710	_node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
deba@139	711	NodeRefMap, ToMap, FromMap>(tmap, map));
alpar@100	712	return *this;
alpar@100	713	}
alpar@100	714
alpar@100	715	/// \brief Make a copy of the given node.
alpar@100	716	///
alpar@100	717	/// Make a copy of the given node.
alpar@100	718	DigraphCopy& node(TNode& tnode, const Node& snode) {
deba@139	719	_node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
deba@139	720	NodeRefMap, TNode>(tnode, snode));
alpar@100	721	return *this;
alpar@100	722	}
alpar@100	723
alpar@100	724	/// \brief Copies the arc references into the given map.
alpar@100	725	///
alpar@100	726	/// Copies the arc references into the given map.
alpar@100	727	template <typename ArcRef>
alpar@100	728	DigraphCopy& arcRef(ArcRef& map) {
deba@139	729	_arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
deba@139	730	ArcRefMap, ArcRef>(map));
alpar@100	731	return *this;
alpar@100	732	}
alpar@100	733
alpar@100	734	/// \brief Copies the arc cross references into the given map.
alpar@100	735	///
alpar@100	736	/// Copies the arc cross references (reverse references) into
alpar@100	737	/// the given map.
alpar@100	738	template <typename ArcCrossRef>
alpar@100	739	DigraphCopy& arcCrossRef(ArcCrossRef& map) {
deba@139	740	_arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
deba@139	741	ArcRefMap, ArcCrossRef>(map));
alpar@100	742	return *this;
alpar@100	743	}
alpar@100	744
alpar@100	745	/// \brief Make copy of the given map.
alpar@100	746	///
alpar@100	747	/// Makes copy of the given map for the newly created digraph.
alpar@100	748	/// The new map's key type is the to digraph's arc type,
alpar@100	749	/// and the copied map's key type is the from digraph's arc
alpar@100	750	/// type.
alpar@100	751	template <typename ToMap, typename FromMap>
alpar@100	752	DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
deba@139	753	_arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
deba@139	754	ArcRefMap, ToMap, FromMap>(tmap, map));
alpar@100	755	return *this;
alpar@100	756	}
alpar@100	757
alpar@100	758	/// \brief Make a copy of the given arc.
alpar@100	759	///
alpar@100	760	/// Make a copy of the given arc.
alpar@100	761	DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
deba@139	762	_arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
deba@139	763	ArcRefMap, TArc>(tarc, sarc));
alpar@100	764	return *this;
alpar@100	765	}
alpar@100	766
alpar@100	767	/// \brief Executes the copies.
alpar@100	768	///
alpar@100	769	/// Executes the copies.
alpar@100	770	void run() {
deba@139	771	NodeRefMap nodeRefMap(_from);
deba@139	772	ArcRefMap arcRefMap(_from);
deba@139	773	_graph_utils_bits::DigraphCopySelector<To>::
deba@139	774	copy(_to, _from, nodeRefMap, arcRefMap);
deba@139	775	for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139	776	_node_maps[i]->copy(_from, nodeRefMap);
alpar@100	777	}
deba@139	778	for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139	779	_arc_maps[i]->copy(_from, arcRefMap);
alpar@100	780	}
alpar@100	781	}
alpar@100	782
alpar@100	783	protected:
alpar@100	784
alpar@100	785
deba@139	786	const From& _from;
deba@139	787	To& _to;
alpar@100	788
deba@139	789	std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
deba@139	790	_node_maps;
alpar@100	791
deba@139	792	std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
deba@139	793	_arc_maps;
alpar@100	794
alpar@100	795	};
alpar@100	796
alpar@100	797	/// \brief Copy a digraph to another digraph.
alpar@100	798	///
deba@139	799	/// Copy a digraph to another digraph. The complete usage of the
deba@139	800	/// function is detailed in the DigraphCopy class, but a short
deba@139	801	/// example shows a basic work:
alpar@100	802	///\code
alpar@100	803	/// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
alpar@100	804	///\endcode
alpar@100	805	///
alpar@100	806	/// After the copy the \c nr map will contain the mapping from the
alpar@100	807	/// nodes of the \c from digraph to the nodes of the \c to digraph and
alpar@100	808	/// \c ecr will contain the mapping from the arcs of the \c to digraph
alpar@100	809	/// to the arcs of the \c from digraph.
alpar@100	810	///
alpar@100	811	/// \see DigraphCopy
alpar@100	812	template <typename To, typename From>
alpar@100	813	DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
alpar@100	814	return DigraphCopy<To, From>(to, from);
alpar@100	815	}
alpar@100	816
deba@139	817	/// \brief Class to copy a graph.
alpar@100	818	///
deba@139	819	/// Class to copy a graph to another graph (duplicate a graph). The
deba@139	820	/// simplest way of using it is through the \c copyGraph() function.
deba@139	821	///
deba@139	822	/// This class not just make a copy of a graph, but it can create
deba@139	823	/// references and cross references between the nodes, edges and arcs of
deba@139	824	/// the two graphs, it can copy maps for use with the newly created
deba@139	825	/// graph and copy nodes, edges and arcs.
deba@139	826	///
deba@139	827	/// To make a copy from a graph, first an instance of GraphCopy
deba@139	828	/// should be created, then the data belongs to the graph should
deba@139	829	/// assigned to copy. In the end, the \c run() member should be
deba@139	830	/// called.
deba@139	831	///
deba@139	832	/// The next code copies a graph with several data:
deba@139	833	///\code
deba@139	834	/// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
deba@139	835	/// // create a reference for the nodes
deba@139	836	/// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
deba@139	837	/// dc.nodeRef(nr);
deba@139	838	/// // create a cross reference (inverse) for the edges
deba@139	839	/// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
deba@139	840	/// dc.edgeCrossRef(ecr);
deba@139	841	/// // copy an arc map
deba@139	842	/// OrigGraph::ArcMap<double> oamap(orig_graph);
deba@139	843	/// NewGraph::ArcMap<double> namap(new_graph);
deba@139	844	/// dc.arcMap(namap, oamap);
deba@139	845	/// // copy a node
deba@139	846	/// OrigGraph::Node on;
deba@139	847	/// NewGraph::Node nn;
deba@139	848	/// dc.node(nn, on);
deba@139	849	/// // Executions of copy
deba@139	850	/// dc.run();
deba@139	851	///\endcode
alpar@100	852	template <typename To, typename From>
alpar@100	853	class GraphCopy {
alpar@100	854	private:
alpar@100	855
alpar@100	856	typedef typename From::Node Node;
alpar@100	857	typedef typename From::NodeIt NodeIt;
alpar@100	858	typedef typename From::Arc Arc;
alpar@100	859	typedef typename From::ArcIt ArcIt;
alpar@100	860	typedef typename From::Edge Edge;
alpar@100	861	typedef typename From::EdgeIt EdgeIt;
alpar@100	862
alpar@100	863	typedef typename To::Node TNode;
alpar@100	864	typedef typename To::Arc TArc;
alpar@100	865	typedef typename To::Edge TEdge;
alpar@100	866
alpar@100	867	typedef typename From::template NodeMap<TNode> NodeRefMap;
alpar@100	868	typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
alpar@100	869
alpar@100	870	struct ArcRefMap {
deba@139	871	ArcRefMap(const To& to, const From& from,
deba@139	872	const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
deba@139	873	: _to(to), _from(from),
deba@139	874	_edge_ref(edge_ref), _node_ref(node_ref) {}
alpar@100	875
alpar@100	876	typedef typename From::Arc Key;
alpar@100	877	typedef typename To::Arc Value;
alpar@100	878
alpar@100	879	Value operator[](const Key& key) const {
alpar@100	880	bool forward =
deba@139	881	(_from.direction(key) ==
deba@139	882	(_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
deba@139	883	return _to.direct(_edge_ref[key], forward);
alpar@100	884	}
alpar@100	885
deba@139	886	const To& _to;
deba@139	887	const From& _from;
deba@139	888	const EdgeRefMap& _edge_ref;
deba@139	889	const NodeRefMap& _node_ref;
alpar@100	890	};
alpar@100	891
alpar@100	892
alpar@100	893	public:
alpar@100	894
alpar@100	895
deba@139	896	/// \brief Constructor for the GraphCopy.
alpar@100	897	///
deba@139	898	/// It copies the content of the \c _from graph into the
deba@139	899	/// \c _to graph.
deba@139	900	GraphCopy(To& to, const From& from)
deba@139	901	: _from(from), _to(to) {}
alpar@100	902
deba@139	903	/// \brief Destructor of the GraphCopy
alpar@100	904	///
deba@139	905	/// Destructor of the GraphCopy
alpar@100	906	~GraphCopy() {
deba@139	907	for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139	908	delete _node_maps[i];
alpar@100	909	}
deba@139	910	for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139	911	delete _arc_maps[i];
alpar@100	912	}
deba@139	913	for (int i = 0; i < int(_edge_maps.size()); ++i) {
deba@139	914	delete _edge_maps[i];
alpar@100	915	}
alpar@100	916
alpar@100	917	}
alpar@100	918
alpar@100	919	/// \brief Copies the node references into the given map.
alpar@100	920	///
alpar@100	921	/// Copies the node references into the given map.
alpar@100	922	template <typename NodeRef>
alpar@100	923	GraphCopy& nodeRef(NodeRef& map) {
deba@139	924	_node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
deba@139	925	NodeRefMap, NodeRef>(map));
alpar@100	926	return *this;
alpar@100	927	}
alpar@100	928
alpar@100	929	/// \brief Copies the node cross references into the given map.
alpar@100	930	///
alpar@100	931	/// Copies the node cross references (reverse references) into
alpar@100	932	/// the given map.
alpar@100	933	template <typename NodeCrossRef>
alpar@100	934	GraphCopy& nodeCrossRef(NodeCrossRef& map) {
deba@139	935	_node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
deba@139	936	NodeRefMap, NodeCrossRef>(map));
alpar@100	937	return *this;
alpar@100	938	}
alpar@100	939
alpar@100	940	/// \brief Make copy of the given map.
alpar@100	941	///
deba@139	942	/// Makes copy of the given map for the newly created graph.
deba@139	943	/// The new map's key type is the to graph's node type,
deba@139	944	/// and the copied map's key type is the from graph's node
alpar@100	945	/// type.
alpar@100	946	template <typename ToMap, typename FromMap>
alpar@100	947	GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
deba@139	948	_node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
deba@139	949	NodeRefMap, ToMap, FromMap>(tmap, map));
alpar@100	950	return *this;
alpar@100	951	}
alpar@100	952
alpar@100	953	/// \brief Make a copy of the given node.
alpar@100	954	///
alpar@100	955	/// Make a copy of the given node.
alpar@100	956	GraphCopy& node(TNode& tnode, const Node& snode) {
deba@139	957	_node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
deba@139	958	NodeRefMap, TNode>(tnode, snode));
alpar@100	959	return *this;
alpar@100	960	}
alpar@100	961
alpar@100	962	/// \brief Copies the arc references into the given map.
alpar@100	963	///
alpar@100	964	/// Copies the arc references into the given map.
alpar@100	965	template <typename ArcRef>
alpar@100	966	GraphCopy& arcRef(ArcRef& map) {
deba@139	967	_arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
deba@139	968	ArcRefMap, ArcRef>(map));
alpar@100	969	return *this;
alpar@100	970	}
alpar@100	971
alpar@100	972	/// \brief Copies the arc cross references into the given map.
alpar@100	973	///
alpar@100	974	/// Copies the arc cross references (reverse references) into
alpar@100	975	/// the given map.
alpar@100	976	template <typename ArcCrossRef>
alpar@100	977	GraphCopy& arcCrossRef(ArcCrossRef& map) {
deba@139	978	_arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
deba@139	979	ArcRefMap, ArcCrossRef>(map));
alpar@100	980	return *this;
alpar@100	981	}
alpar@100	982
alpar@100	983	/// \brief Make copy of the given map.
alpar@100	984	///
deba@139	985	/// Makes copy of the given map for the newly created graph.
deba@139	986	/// The new map's key type is the to graph's arc type,
deba@139	987	/// and the copied map's key type is the from graph's arc
alpar@100	988	/// type.
alpar@100	989	template <typename ToMap, typename FromMap>
alpar@100	990	GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
deba@139	991	_arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
deba@139	992	ArcRefMap, ToMap, FromMap>(tmap, map));
alpar@100	993	return *this;
alpar@100	994	}
alpar@100	995
alpar@100	996	/// \brief Make a copy of the given arc.
alpar@100	997	///
alpar@100	998	/// Make a copy of the given arc.
alpar@100	999	GraphCopy& arc(TArc& tarc, const Arc& sarc) {
deba@139	1000	_arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
deba@139	1001	ArcRefMap, TArc>(tarc, sarc));
alpar@100	1002	return *this;
alpar@100	1003	}
alpar@100	1004
alpar@100	1005	/// \brief Copies the edge references into the given map.
alpar@100	1006	///
alpar@100	1007	/// Copies the edge references into the given map.
alpar@100	1008	template <typename EdgeRef>
alpar@100	1009	GraphCopy& edgeRef(EdgeRef& map) {
deba@139	1010	_edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
deba@139	1011	EdgeRefMap, EdgeRef>(map));
alpar@100	1012	return *this;
alpar@100	1013	}
alpar@100	1014
alpar@100	1015	/// \brief Copies the edge cross references into the given map.
alpar@100	1016	///
alpar@100	1017	/// Copies the edge cross references (reverse
alpar@100	1018	/// references) into the given map.
alpar@100	1019	template <typename EdgeCrossRef>
alpar@100	1020	GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
deba@139	1021	_edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
deba@139	1022	Edge, EdgeRefMap, EdgeCrossRef>(map));
alpar@100	1023	return *this;
alpar@100	1024	}
alpar@100	1025
alpar@100	1026	/// \brief Make copy of the given map.
alpar@100	1027	///
deba@139	1028	/// Makes copy of the given map for the newly created graph.
deba@139	1029	/// The new map's key type is the to graph's edge type,
deba@139	1030	/// and the copied map's key type is the from graph's edge
alpar@100	1031	/// type.
alpar@100	1032	template <typename ToMap, typename FromMap>
alpar@100	1033	GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
deba@139	1034	_edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
deba@139	1035	EdgeRefMap, ToMap, FromMap>(tmap, map));
alpar@100	1036	return *this;
alpar@100	1037	}
alpar@100	1038
alpar@100	1039	/// \brief Make a copy of the given edge.
alpar@100	1040	///
alpar@100	1041	/// Make a copy of the given edge.
alpar@100	1042	GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
deba@139	1043	_edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
deba@139	1044	EdgeRefMap, TEdge>(tedge, sedge));
alpar@100	1045	return *this;
alpar@100	1046	}
alpar@100	1047
alpar@100	1048	/// \brief Executes the copies.
alpar@100	1049	///
alpar@100	1050	/// Executes the copies.
alpar@100	1051	void run() {
deba@139	1052	NodeRefMap nodeRefMap(_from);
deba@139	1053	EdgeRefMap edgeRefMap(_from);
deba@139	1054	ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
deba@139	1055	_graph_utils_bits::GraphCopySelector<To>::
deba@139	1056	copy(_to, _from, nodeRefMap, edgeRefMap);
deba@139	1057	for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139	1058	_node_maps[i]->copy(_from, nodeRefMap);
alpar@100	1059	}
deba@139	1060	for (int i = 0; i < int(_edge_maps.size()); ++i) {
deba@139	1061	_edge_maps[i]->copy(_from, edgeRefMap);
alpar@100	1062	}
deba@139	1063	for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139	1064	_arc_maps[i]->copy(_from, arcRefMap);
alpar@100	1065	}
alpar@100	1066	}
alpar@100	1067
alpar@100	1068	private:
alpar@100	1069
deba@139	1070	const From& _from;
deba@139	1071	To& _to;
alpar@100	1072
deba@139	1073	std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
deba@139	1074	_node_maps;
alpar@100	1075
deba@139	1076	std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
deba@139	1077	_arc_maps;
alpar@100	1078
deba@139	1079	std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
deba@139	1080	_edge_maps;
alpar@100	1081
alpar@100	1082	};
alpar@100	1083
deba@139	1084	/// \brief Copy a graph to another graph.
alpar@100	1085	///
deba@139	1086	/// Copy a graph to another graph. The complete usage of the
deba@139	1087	/// function is detailed in the GraphCopy class, but a short
deba@139	1088	/// example shows a basic work:
alpar@100	1089	///\code
alpar@100	1090	/// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
alpar@100	1091	///\endcode
alpar@100	1092	///
alpar@100	1093	/// After the copy the \c nr map will contain the mapping from the
deba@139	1094	/// nodes of the \c from graph to the nodes of the \c to graph and
deba@139	1095	/// \c ecr will contain the mapping from the arcs of the \c to graph
deba@139	1096	/// to the arcs of the \c from graph.
alpar@100	1097	///
alpar@100	1098	/// \see GraphCopy
alpar@100	1099	template <typename To, typename From>
alpar@100	1100	GraphCopy<To, From>
alpar@100	1101	copyGraph(To& to, const From& from) {
alpar@100	1102	return GraphCopy<To, From>(to, from);
alpar@100	1103	}
alpar@100	1104
alpar@100	1105	/// @}
alpar@100	1106
deba@139	1107	/// \addtogroup graph_maps
alpar@100	1108	/// @{
alpar@100	1109
deba@139	1110	/// Provides an immutable and unique id for each item in the graph.
alpar@100	1111
alpar@100	1112	/// The IdMap class provides a unique and immutable id for each item of the
deba@139	1113	/// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
alpar@100	1114	/// different items (nodes) get different ids <li>\b immutable: the id of an
alpar@100	1115	/// item (node) does not change (even if you delete other nodes). </ul>
alpar@100	1116	/// Through this map you get access (i.e. can read) the inner id values of
deba@139	1117	/// the items stored in the graph. This map can be inverted with its member
deba@139	1118	/// class \c InverseMap or with the \c operator() member.
alpar@100	1119	///
deba@139	1120	template <typename _Graph, typename _Item>
alpar@100	1121	class IdMap {
alpar@100	1122	public:
deba@139	1123	typedef _Graph Graph;
alpar@100	1124	typedef int Value;
alpar@100	1125	typedef _Item Item;
alpar@100	1126	typedef _Item Key;
alpar@100	1127
alpar@100	1128	/// \brief Constructor.
alpar@100	1129	///
alpar@100	1130	/// Constructor of the map.
deba@139	1131	explicit IdMap(const Graph& graph) : _graph(&graph) {}
alpar@100	1132
alpar@100	1133	/// \brief Gives back the \e id of the item.
alpar@100	1134	///
alpar@100	1135	/// Gives back the immutable and unique \e id of the item.
deba@139	1136	int operator[](const Item& item) const { return _graph->id(item);}
alpar@100	1137
alpar@100	1138	/// \brief Gives back the item by its id.
alpar@100	1139	///
alpar@100	1140	/// Gives back the item by its id.
deba@139	1141	Item operator()(int id) { return _graph->fromId(id, Item()); }
alpar@100	1142
alpar@100	1143	private:
deba@139	1144	const Graph* _graph;
alpar@100	1145
alpar@100	1146	public:
alpar@100	1147
alpar@100	1148	/// \brief The class represents the inverse of its owner (IdMap).
alpar@100	1149	///
alpar@100	1150	/// The class represents the inverse of its owner (IdMap).
alpar@100	1151	/// \see inverse()
alpar@100	1152	class InverseMap {
alpar@100	1153	public:
alpar@100	1154
alpar@100	1155	/// \brief Constructor.
alpar@100	1156	///
alpar@100	1157	/// Constructor for creating an id-to-item map.
deba@139	1158	explicit InverseMap(const Graph& graph) : _graph(&graph) {}
alpar@100	1159
alpar@100	1160	/// \brief Constructor.
alpar@100	1161	///
alpar@100	1162	/// Constructor for creating an id-to-item map.
deba@139	1163	explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
alpar@100	1164
alpar@100	1165	/// \brief Gives back the given item from its id.
alpar@100	1166	///
alpar@100	1167	/// Gives back the given item from its id.
alpar@100	1168	///
deba@139	1169	Item operator[](int id) const { return _graph->fromId(id, Item());}
alpar@100	1170
alpar@100	1171	private:
deba@139	1172	const Graph* _graph;
alpar@100	1173	};
alpar@100	1174
alpar@100	1175	/// \brief Gives back the inverse of the map.
alpar@100	1176	///
alpar@100	1177	/// Gives back the inverse of the IdMap.
deba@139	1178	InverseMap inverse() const { return InverseMap(*_graph);}
alpar@100	1179
alpar@100	1180	};
alpar@100	1181
alpar@100	1182
deba@139	1183	/// \brief General invertable graph-map type.
alpar@100	1184
deba@139	1185	/// This type provides simple invertable graph-maps.
alpar@100	1186	/// The InvertableMap wraps an arbitrary ReadWriteMap
alpar@100	1187	/// and if a key is set to a new value then store it
alpar@100	1188	/// in the inverse map.
alpar@100	1189	///
alpar@100	1190	/// The values of the map can be accessed
alpar@100	1191	/// with stl compatible forward iterator.
alpar@100	1192	///
deba@139	1193	/// \param _Graph The graph type.
deba@139	1194	/// \param _Item The item type of the graph.
alpar@100	1195	/// \param _Value The value type of the map.
alpar@100	1196	///
alpar@100	1197	/// \see IterableValueMap
deba@139	1198	template <typename _Graph, typename _Item, typename _Value>
deba@139	1199	class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
alpar@100	1200	private:
alpar@100	1201
deba@139	1202	typedef DefaultMap<_Graph, _Item, _Value> Map;
deba@139	1203	typedef _Graph Graph;
alpar@100	1204
alpar@100	1205	typedef std::map<_Value, _Item> Container;
deba@139	1206	Container _inv_map;
alpar@100	1207
alpar@100	1208	public:
alpar@100	1209
alpar@100	1210	/// The key type of InvertableMap (Node, Arc, Edge).
alpar@100	1211	typedef typename Map::Key Key;
alpar@100	1212	/// The value type of the InvertableMap.
alpar@100	1213	typedef typename Map::Value Value;
alpar@100	1214
alpar@100	1215
alpar@100	1216
alpar@100	1217	/// \brief Constructor.
alpar@100	1218	///
deba@139	1219	/// Construct a new InvertableMap for the graph.
alpar@100	1220	///
deba@139	1221	explicit InvertableMap(const Graph& graph) : Map(graph) {}
alpar@100	1222
alpar@100	1223	/// \brief Forward iterator for values.
alpar@100	1224	///
alpar@100	1225	/// This iterator is an stl compatible forward
alpar@100	1226	/// iterator on the values of the map. The values can
alpar@100	1227	/// be accessed in the [beginValue, endValue) range.
alpar@100	1228	///
alpar@100	1229	class ValueIterator
alpar@100	1230	: public std::iterator<std::forward_iterator_tag, Value> {
alpar@100	1231	friend class InvertableMap;
alpar@100	1232	private:
alpar@100	1233	ValueIterator(typename Container::const_iterator _it)
alpar@100	1234	: it(_it) {}
alpar@100	1235	public:
alpar@100	1236
alpar@100	1237	ValueIterator() {}
alpar@100	1238
alpar@100	1239	ValueIterator& operator++() { ++it; return *this; }
alpar@100	1240	ValueIterator operator++(int) {
alpar@100	1241	ValueIterator tmp(*this);
alpar@100	1242	operator++();
alpar@100	1243	return tmp;
alpar@100	1244	}
alpar@100	1245
alpar@100	1246	const Value& operator*() const { return it->first; }
alpar@100	1247	const Value* operator->() const { return &(it->first); }
alpar@100	1248
alpar@100	1249	bool operator==(ValueIterator jt) const { return it == jt.it; }
alpar@100	1250	bool operator!=(ValueIterator jt) const { return it != jt.it; }
alpar@100	1251
alpar@100	1252	private:
alpar@100	1253	typename Container::const_iterator it;
alpar@100	1254	};
alpar@100	1255
alpar@100	1256	/// \brief Returns an iterator to the first value.
alpar@100	1257	///
alpar@100	1258	/// Returns an stl compatible iterator to the
alpar@100	1259	/// first value of the map. The values of the
alpar@100	1260	/// map can be accessed in the [beginValue, endValue)
alpar@100	1261	/// range.
alpar@100	1262	ValueIterator beginValue() const {
deba@139	1263	return ValueIterator(_inv_map.begin());
alpar@100	1264	}
alpar@100	1265
alpar@100	1266	/// \brief Returns an iterator after the last value.
alpar@100	1267	///
alpar@100	1268	/// Returns an stl compatible iterator after the
alpar@100	1269	/// last value of the map. The values of the
alpar@100	1270	/// map can be accessed in the [beginValue, endValue)
alpar@100	1271	/// range.
alpar@100	1272	ValueIterator endValue() const {
deba@139	1273	return ValueIterator(_inv_map.end());
alpar@100	1274	}
alpar@100	1275
alpar@100	1276	/// \brief The setter function of the map.
alpar@100	1277	///
alpar@100	1278	/// Sets the mapped value.
alpar@100	1279	void set(const Key& key, const Value& val) {
alpar@100	1280	Value oldval = Map::operator[](key);
deba@139	1281	typename Container::iterator it = _inv_map.find(oldval);
deba@139	1282	if (it != _inv_map.end() && it->second == key) {
deba@139	1283	_inv_map.erase(it);
alpar@100	1284	}
deba@139	1285	_inv_map.insert(make_pair(val, key));
alpar@100	1286	Map::set(key, val);
alpar@100	1287	}
alpar@100	1288
alpar@100	1289	/// \brief The getter function of the map.
alpar@100	1290	///
alpar@100	1291	/// It gives back the value associated with the key.
alpar@100	1292	typename MapTraits<Map>::ConstReturnValue
alpar@100	1293	operator[](const Key& key) const {
alpar@100	1294	return Map::operator[](key);
alpar@100	1295	}
alpar@100	1296
alpar@100	1297	/// \brief Gives back the item by its value.
alpar@100	1298	///
alpar@100	1299	/// Gives back the item by its value.
alpar@100	1300	Key operator()(const Value& key) const {
deba@139	1301	typename Container::const_iterator it = _inv_map.find(key);
deba@139	1302	return it != _inv_map.end() ? it->second : INVALID;
alpar@100	1303	}
alpar@100	1304
alpar@100	1305	protected:
alpar@100	1306
alpar@100	1307	/// \brief Erase the key from the map.
alpar@100	1308	///
alpar@100	1309	/// Erase the key to the map. It is called by the
alpar@100	1310	/// \c AlterationNotifier.
alpar@100	1311	virtual void erase(const Key& key) {
alpar@100	1312	Value val = Map::operator[](key);
deba@139	1313	typename Container::iterator it = _inv_map.find(val);
deba@139	1314	if (it != _inv_map.end() && it->second == key) {
deba@139	1315	_inv_map.erase(it);
alpar@100	1316	}
alpar@100	1317	Map::erase(key);
alpar@100	1318	}
alpar@100	1319
alpar@100	1320	/// \brief Erase more keys from the map.
alpar@100	1321	///
alpar@100	1322	/// Erase more keys from the map. It is called by the
alpar@100	1323	/// \c AlterationNotifier.
alpar@100	1324	virtual void erase(const std::vector<Key>& keys) {
alpar@100	1325	for (int i = 0; i < int(keys.size()); ++i) {
alpar@100	1326	Value val = Map::operator[](keys[i]);
deba@139	1327	typename Container::iterator it = _inv_map.find(val);
deba@139	1328	if (it != _inv_map.end() && it->second == keys[i]) {
deba@139	1329	_inv_map.erase(it);
alpar@100	1330	}
alpar@100	1331	}
alpar@100	1332	Map::erase(keys);
alpar@100	1333	}
alpar@100	1334
alpar@100	1335	/// \brief Clear the keys from the map and inverse map.
alpar@100	1336	///
alpar@100	1337	/// Clear the keys from the map and inverse map. It is called by the
alpar@100	1338	/// \c AlterationNotifier.
alpar@100	1339	virtual void clear() {
deba@139	1340	_inv_map.clear();
alpar@100	1341	Map::clear();
alpar@100	1342	}
alpar@100	1343
alpar@100	1344	public:
alpar@100	1345
alpar@100	1346	/// \brief The inverse map type.
alpar@100	1347	///
alpar@100	1348	/// The inverse of this map. The subscript operator of the map
alpar@100	1349	/// gives back always the item what was last assigned to the value.
alpar@100	1350	class InverseMap {
alpar@100	1351	public:
alpar@100	1352	/// \brief Constructor of the InverseMap.
alpar@100	1353	///
alpar@100	1354	/// Constructor of the InverseMap.
deba@139	1355	explicit InverseMap(const InvertableMap& inverted)
deba@139	1356	: _inverted(inverted) {}
alpar@100	1357
alpar@100	1358	/// The value type of the InverseMap.
alpar@100	1359	typedef typename InvertableMap::Key Value;
alpar@100	1360	/// The key type of the InverseMap.
alpar@100	1361	typedef typename InvertableMap::Value Key;
alpar@100	1362
alpar@100	1363	/// \brief Subscript operator.
alpar@100	1364	///
alpar@100	1365	/// Subscript operator. It gives back always the item
alpar@100	1366	/// what was last assigned to the value.
alpar@100	1367	Value operator[](const Key& key) const {
deba@139	1368	return _inverted(key);
alpar@100	1369	}
alpar@100	1370
alpar@100	1371	private:
deba@139	1372	const InvertableMap& _inverted;
alpar@100	1373	};
alpar@100	1374
alpar@100	1375	/// \brief It gives back the just readable inverse map.
alpar@100	1376	///
alpar@100	1377	/// It gives back the just readable inverse map.
alpar@100	1378	InverseMap inverse() const {
alpar@100	1379	return InverseMap(*this);
alpar@100	1380	}
alpar@100	1381
alpar@100	1382
alpar@100	1383
alpar@100	1384	};
alpar@100	1385
alpar@100	1386	/// \brief Provides a mutable, continuous and unique descriptor for each
deba@139	1387	/// item in the graph.
alpar@100	1388	///
alpar@100	1389	/// The DescriptorMap class provides a unique and continuous (but mutable)
alpar@100	1390	/// descriptor (id) for each item of the same type (e.g. node) in the
deba@139	1391	/// graph. This id is <ul><li>\b unique: different items (nodes) get
alpar@100	1392	/// different ids <li>\b continuous: the range of the ids is the set of
alpar@100	1393	/// integers between 0 and \c n-1, where \c n is the number of the items of
alpar@100	1394	/// this type (e.g. nodes) (so the id of a node can change if you delete an
alpar@100	1395	/// other node, i.e. this id is mutable). </ul> This map can be inverted
deba@139	1396	/// with its member class \c InverseMap, or with the \c operator() member.
alpar@100	1397	///
deba@139	1398	/// \param _Graph The graph class the \c DescriptorMap belongs to.
alpar@100	1399	/// \param _Item The Item is the Key of the Map. It may be Node, Arc or
alpar@100	1400	/// Edge.
deba@139	1401	template <typename _Graph, typename _Item>
deba@139	1402	class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
alpar@100	1403
alpar@100	1404	typedef _Item Item;
deba@139	1405	typedef DefaultMap<_Graph, _Item, int> Map;
alpar@100	1406
alpar@100	1407	public:
deba@139	1408	/// The graph class of DescriptorMap.
deba@139	1409	typedef _Graph Graph;
alpar@100	1410
alpar@100	1411	/// The key type of DescriptorMap (Node, Arc, Edge).
alpar@100	1412	typedef typename Map::Key Key;
alpar@100	1413	/// The value type of DescriptorMap.
alpar@100	1414	typedef typename Map::Value Value;
alpar@100	1415
alpar@100	1416	/// \brief Constructor.
alpar@100	1417	///
alpar@100	1418	/// Constructor for descriptor map.
deba@139	1419	explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
alpar@100	1420	Item it;
alpar@100	1421	const typename Map::Notifier* nf = Map::notifier();
alpar@100	1422	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@139	1423	Map::set(it, _inv_map.size());
deba@139	1424	_inv_map.push_back(it);
alpar@100	1425	}
alpar@100	1426	}
alpar@100	1427
alpar@100	1428	protected:
alpar@100	1429
alpar@100	1430	/// \brief Add a new key to the map.
alpar@100	1431	///
alpar@100	1432	/// Add a new key to the map. It is called by the
alpar@100	1433	/// \c AlterationNotifier.
alpar@100	1434	virtual void add(const Item& item) {
alpar@100	1435	Map::add(item);
deba@139	1436	Map::set(item, _inv_map.size());
deba@139	1437	_inv_map.push_back(item);
alpar@100	1438	}
alpar@100	1439
alpar@100	1440	/// \brief Add more new keys to the map.
alpar@100	1441	///
alpar@100	1442	/// Add more new keys to the map. It is called by the
alpar@100	1443	/// \c AlterationNotifier.
alpar@100	1444	virtual void add(const std::vector<Item>& items) {
alpar@100	1445	Map::add(items);
alpar@100	1446	for (int i = 0; i < int(items.size()); ++i) {
deba@139	1447	Map::set(items[i], _inv_map.size());
deba@139	1448	_inv_map.push_back(items[i]);
alpar@100	1449	}
alpar@100	1450	}
alpar@100	1451
alpar@100	1452	/// \brief Erase the key from the map.
alpar@100	1453	///
alpar@100	1454	/// Erase the key from the map. It is called by the
alpar@100	1455	/// \c AlterationNotifier.
alpar@100	1456	virtual void erase(const Item& item) {
deba@139	1457	Map::set(_inv_map.back(), Map::operator[](item));
deba@139	1458	_inv_map[Map::operator[](item)] = _inv_map.back();
deba@139	1459	_inv_map.pop_back();
alpar@100	1460	Map::erase(item);
alpar@100	1461	}
alpar@100	1462
alpar@100	1463	/// \brief Erase more keys from the map.
alpar@100	1464	///
alpar@100	1465	/// Erase more keys from the map. It is called by the
alpar@100	1466	/// \c AlterationNotifier.
alpar@100	1467	virtual void erase(const std::vector<Item>& items) {
alpar@100	1468	for (int i = 0; i < int(items.size()); ++i) {
deba@139	1469	Map::set(_inv_map.back(), Map::operator[](items[i]));
deba@139	1470	_inv_map[Map::operator[](items[i])] = _inv_map.back();
deba@139	1471	_inv_map.pop_back();
alpar@100	1472	}
alpar@100	1473	Map::erase(items);
alpar@100	1474	}
alpar@100	1475
alpar@100	1476	/// \brief Build the unique map.
alpar@100	1477	///
alpar@100	1478	/// Build the unique map. It is called by the
alpar@100	1479	/// \c AlterationNotifier.
alpar@100	1480	virtual void build() {
alpar@100	1481	Map::build();
alpar@100	1482	Item it;
alpar@100	1483	const typename Map::Notifier* nf = Map::notifier();
alpar@100	1484	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@139	1485	Map::set(it, _inv_map.size());
deba@139	1486	_inv_map.push_back(it);
alpar@100	1487	}
alpar@100	1488	}
alpar@100	1489
alpar@100	1490	/// \brief Clear the keys from the map.
alpar@100	1491	///
alpar@100	1492	/// Clear the keys from the map. It is called by the
alpar@100	1493	/// \c AlterationNotifier.
alpar@100	1494	virtual void clear() {
deba@139	1495	_inv_map.clear();
alpar@100	1496	Map::clear();
alpar@100	1497	}
alpar@100	1498
alpar@100	1499	public:
alpar@100	1500
alpar@100	1501	/// \brief Returns the maximal value plus one.
alpar@100	1502	///
alpar@100	1503	/// Returns the maximal value plus one in the map.
alpar@100	1504	unsigned int size() const {
deba@139	1505	return _inv_map.size();
alpar@100	1506	}
alpar@100	1507
alpar@100	1508	/// \brief Swaps the position of the two items in the map.
alpar@100	1509	///
alpar@100	1510	/// Swaps the position of the two items in the map.
alpar@100	1511	void swap(const Item& p, const Item& q) {
alpar@100	1512	int pi = Map::operator[](p);
alpar@100	1513	int qi = Map::operator[](q);
alpar@100	1514	Map::set(p, qi);
deba@139	1515	_inv_map[qi] = p;
alpar@100	1516	Map::set(q, pi);
deba@139	1517	_inv_map[pi] = q;
alpar@100	1518	}
alpar@100	1519
alpar@100	1520	/// \brief Gives back the \e descriptor of the item.
alpar@100	1521	///
alpar@100	1522	/// Gives back the mutable and unique \e descriptor of the map.
alpar@100	1523	int operator[](const Item& item) const {
alpar@100	1524	return Map::operator[](item);
alpar@100	1525	}
alpar@100	1526
alpar@100	1527	/// \brief Gives back the item by its descriptor.
alpar@100	1528	///
alpar@100	1529	/// Gives back th item by its descriptor.
alpar@100	1530	Item operator()(int id) const {
deba@139	1531	return _inv_map[id];
alpar@100	1532	}
alpar@100	1533
alpar@100	1534	private:
alpar@100	1535
alpar@100	1536	typedef std::vector<Item> Container;
deba@139	1537	Container _inv_map;
alpar@100	1538
alpar@100	1539	public:
alpar@100	1540	/// \brief The inverse map type of DescriptorMap.
alpar@100	1541	///
alpar@100	1542	/// The inverse map type of DescriptorMap.
alpar@100	1543	class InverseMap {
alpar@100	1544	public:
alpar@100	1545	/// \brief Constructor of the InverseMap.
alpar@100	1546	///
alpar@100	1547	/// Constructor of the InverseMap.
deba@139	1548	explicit InverseMap(const DescriptorMap& inverted)
deba@139	1549	: _inverted(inverted) {}
alpar@100	1550
alpar@100	1551
alpar@100	1552	/// The value type of the InverseMap.
alpar@100	1553	typedef typename DescriptorMap::Key Value;
alpar@100	1554	/// The key type of the InverseMap.
alpar@100	1555	typedef typename DescriptorMap::Value Key;
alpar@100	1556
alpar@100	1557	/// \brief Subscript operator.
alpar@100	1558	///
alpar@100	1559	/// Subscript operator. It gives back the item
alpar@100	1560	/// that the descriptor belongs to currently.
alpar@100	1561	Value operator[](const Key& key) const {
deba@139	1562	return _inverted(key);
alpar@100	1563	}
alpar@100	1564
alpar@100	1565	/// \brief Size of the map.
alpar@100	1566	///
alpar@100	1567	/// Returns the size of the map.
alpar@100	1568	unsigned int size() const {
deba@139	1569	return _inverted.size();
alpar@100	1570	}
alpar@100	1571
alpar@100	1572	private:
deba@139	1573	const DescriptorMap& _inverted;
alpar@100	1574	};
alpar@100	1575
alpar@100	1576	/// \brief Gives back the inverse of the map.
alpar@100	1577	///
alpar@100	1578	/// Gives back the inverse of the map.
alpar@100	1579	const InverseMap inverse() const {
alpar@100	1580	return InverseMap(*this);
alpar@100	1581	}
alpar@100	1582	};
alpar@100	1583
alpar@100	1584	/// \brief Returns the source of the given arc.
alpar@100	1585	///
alpar@100	1586	/// The SourceMap gives back the source Node of the given arc.
alpar@100	1587	/// \see TargetMap
alpar@100	1588	/// \author Balazs Dezso
alpar@100	1589	template <typename Digraph>
alpar@100	1590	class SourceMap {
alpar@100	1591	public:
alpar@100	1592
alpar@100	1593	typedef typename Digraph::Node Value;
alpar@100	1594	typedef typename Digraph::Arc Key;
alpar@100	1595
alpar@100	1596	/// \brief Constructor
alpar@100	1597	///
alpar@100	1598	/// Constructor
alpar@100	1599	/// \param _digraph The digraph that the map belongs to.
deba@139	1600	explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
alpar@100	1601
alpar@100	1602	/// \brief The subscript operator.
alpar@100	1603	///
alpar@100	1604	/// The subscript operator.
alpar@100	1605	/// \param arc The arc
alpar@100	1606	/// \return The source of the arc
alpar@100	1607	Value operator[](const Key& arc) const {
deba@139	1608	return _digraph.source(arc);
alpar@100	1609	}
alpar@100	1610
alpar@100	1611	private:
deba@139	1612	const Digraph& _digraph;
alpar@100	1613	};
alpar@100	1614
alpar@100	1615	/// \brief Returns a \ref SourceMap class.
alpar@100	1616	///
alpar@100	1617	/// This function just returns an \ref SourceMap class.
alpar@100	1618	/// \relates SourceMap
alpar@100	1619	template <typename Digraph>
alpar@100	1620	inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
alpar@100	1621	return SourceMap<Digraph>(digraph);
alpar@100	1622	}
alpar@100	1623
alpar@100	1624	/// \brief Returns the target of the given arc.
alpar@100	1625	///
alpar@100	1626	/// The TargetMap gives back the target Node of the given arc.
alpar@100	1627	/// \see SourceMap
alpar@100	1628	/// \author Balazs Dezso
alpar@100	1629	template <typename Digraph>
alpar@100	1630	class TargetMap {
alpar@100	1631	public:
alpar@100	1632
alpar@100	1633	typedef typename Digraph::Node Value;
alpar@100	1634	typedef typename Digraph::Arc Key;
alpar@100	1635
alpar@100	1636	/// \brief Constructor
alpar@100	1637	///
alpar@100	1638	/// Constructor
alpar@100	1639	/// \param _digraph The digraph that the map belongs to.
deba@139	1640	explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
alpar@100	1641
alpar@100	1642	/// \brief The subscript operator.
alpar@100	1643	///
alpar@100	1644	/// The subscript operator.
alpar@100	1645	/// \param e The arc
alpar@100	1646	/// \return The target of the arc
alpar@100	1647	Value operator[](const Key& e) const {
deba@139	1648	return _digraph.target(e);
alpar@100	1649	}
alpar@100	1650
alpar@100	1651	private:
deba@139	1652	const Digraph& _digraph;
alpar@100	1653	};
alpar@100	1654
alpar@100	1655	/// \brief Returns a \ref TargetMap class.
alpar@100	1656	///
alpar@100	1657	/// This function just returns a \ref TargetMap class.
alpar@100	1658	/// \relates TargetMap
alpar@100	1659	template <typename Digraph>
alpar@100	1660	inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
alpar@100	1661	return TargetMap<Digraph>(digraph);
alpar@100	1662	}
alpar@100	1663
alpar@100	1664	/// \brief Returns the "forward" directed arc view of an edge.
alpar@100	1665	///
alpar@100	1666	/// Returns the "forward" directed arc view of an edge.
alpar@100	1667	/// \see BackwardMap
alpar@100	1668	/// \author Balazs Dezso
deba@139	1669	template <typename Graph>
alpar@100	1670	class ForwardMap {
alpar@100	1671	public:
alpar@100	1672
deba@139	1673	typedef typename Graph::Arc Value;
deba@139	1674	typedef typename Graph::Edge Key;
alpar@100	1675
alpar@100	1676	/// \brief Constructor
alpar@100	1677	///
alpar@100	1678	/// Constructor
deba@139	1679	/// \param _graph The graph that the map belongs to.
deba@139	1680	explicit ForwardMap(const Graph& graph) : _graph(graph) {}
alpar@100	1681
alpar@100	1682	/// \brief The subscript operator.
alpar@100	1683	///
alpar@100	1684	/// The subscript operator.
alpar@100	1685	/// \param key An edge
alpar@100	1686	/// \return The "forward" directed arc view of edge
alpar@100	1687	Value operator[](const Key& key) const {
deba@139	1688	return _graph.direct(key, true);
alpar@100	1689	}
alpar@100	1690
alpar@100	1691	private:
deba@139	1692	const Graph& _graph;
alpar@100	1693	};
alpar@100	1694
alpar@100	1695	/// \brief Returns a \ref ForwardMap class.
alpar@100	1696	///
alpar@100	1697	/// This function just returns an \ref ForwardMap class.
alpar@100	1698	/// \relates ForwardMap
deba@139	1699	template <typename Graph>
deba@139	1700	inline ForwardMap<Graph> forwardMap(const Graph& graph) {
deba@139	1701	return ForwardMap<Graph>(graph);
alpar@100	1702	}
alpar@100	1703
alpar@100	1704	/// \brief Returns the "backward" directed arc view of an edge.
alpar@100	1705	///
alpar@100	1706	/// Returns the "backward" directed arc view of an edge.
alpar@100	1707	/// \see ForwardMap
alpar@100	1708	/// \author Balazs Dezso
deba@139	1709	template <typename Graph>
alpar@100	1710	class BackwardMap {
alpar@100	1711	public:
alpar@100	1712
deba@139	1713	typedef typename Graph::Arc Value;
deba@139	1714	typedef typename Graph::Edge Key;
alpar@100	1715
alpar@100	1716	/// \brief Constructor
alpar@100	1717	///
alpar@100	1718	/// Constructor
deba@139	1719	/// \param _graph The graph that the map belongs to.
deba@139	1720	explicit BackwardMap(const Graph& graph) : _graph(graph) {}
alpar@100	1721
alpar@100	1722	/// \brief The subscript operator.
alpar@100	1723	///
alpar@100	1724	/// The subscript operator.
alpar@100	1725	/// \param key An edge
alpar@100	1726	/// \return The "backward" directed arc view of edge
alpar@100	1727	Value operator[](const Key& key) const {
deba@139	1728	return _graph.direct(key, false);
alpar@100	1729	}
alpar@100	1730
alpar@100	1731	private:
deba@139	1732	const Graph& _graph;
alpar@100	1733	};
alpar@100	1734
alpar@100	1735	/// \brief Returns a \ref BackwardMap class
alpar@100	1736
alpar@100	1737	/// This function just returns a \ref BackwardMap class.
alpar@100	1738	/// \relates BackwardMap
deba@139	1739	template <typename Graph>
deba@139	1740	inline BackwardMap<Graph> backwardMap(const Graph& graph) {
deba@139	1741	return BackwardMap<Graph>(graph);
alpar@100	1742	}
alpar@100	1743
alpar@100	1744	/// \brief Potential difference map
alpar@100	1745	///
alpar@100	1746	/// If there is an potential map on the nodes then we
alpar@100	1747	/// can get an arc map as we get the substraction of the
alpar@100	1748	/// values of the target and source.
alpar@100	1749	template <typename Digraph, typename NodeMap>
alpar@100	1750	class PotentialDifferenceMap {
alpar@100	1751	public:
alpar@100	1752	typedef typename Digraph::Arc Key;
alpar@100	1753	typedef typename NodeMap::Value Value;
alpar@100	1754
alpar@100	1755	/// \brief Constructor
alpar@100	1756	///
alpar@100	1757	/// Contructor of the map
deba@139	1758	explicit PotentialDifferenceMap(const Digraph& digraph,
deba@139	1759	const NodeMap& potential)
deba@139	1760	: _digraph(digraph), _potential(potential) {}
alpar@100	1761
alpar@100	1762	/// \brief Const subscription operator
alpar@100	1763	///
alpar@100	1764	/// Const subscription operator
alpar@100	1765	Value operator[](const Key& arc) const {
deba@139	1766	return _potential[_digraph.target(arc)] -
deba@139	1767	_potential[_digraph.source(arc)];
alpar@100	1768	}
alpar@100	1769
alpar@100	1770	private:
deba@139	1771	const Digraph& _digraph;
deba@139	1772	const NodeMap& _potential;
alpar@100	1773	};
alpar@100	1774
alpar@100	1775	/// \brief Returns a PotentialDifferenceMap.
alpar@100	1776	///
alpar@100	1777	/// This function just returns a PotentialDifferenceMap.
alpar@100	1778	/// \relates PotentialDifferenceMap
alpar@100	1779	template <typename Digraph, typename NodeMap>
alpar@100	1780	PotentialDifferenceMap<Digraph, NodeMap>
alpar@100	1781	potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
alpar@100	1782	return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
alpar@100	1783	}
alpar@100	1784
alpar@100	1785	/// \brief Map of the node in-degrees.
alpar@100	1786	///
alpar@100	1787	/// This map returns the in-degree of a node. Once it is constructed,
alpar@100	1788	/// the degrees are stored in a standard NodeMap, so each query is done
alpar@100	1789	/// in constant time. On the other hand, the values are updated automatically
alpar@100	1790	/// whenever the digraph changes.
alpar@100	1791	///
alpar@100	1792	/// \warning Besides addNode() and addArc(), a digraph structure may provide
alpar@100	1793	/// alternative ways to modify the digraph. The correct behavior of InDegMap
alpar@100	1794	/// is not guarantied if these additional features are used. For example
alpar@100	1795	/// the functions \ref ListDigraph::changeSource() "changeSource()",
alpar@100	1796	/// \ref ListDigraph::changeTarget() "changeTarget()" and
alpar@100	1797	/// \ref ListDigraph::reverseArc() "reverseArc()"
alpar@100	1798	/// of \ref ListDigraph will \e not update the degree values correctly.
alpar@100	1799	///
alpar@100	1800	/// \sa OutDegMap
alpar@100	1801
alpar@100	1802	template <typename _Digraph>
alpar@100	1803	class InDegMap
alpar@100	1804	: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
alpar@100	1805	::ItemNotifier::ObserverBase {
alpar@100	1806
alpar@100	1807	public:
alpar@100	1808
alpar@100	1809	typedef _Digraph Digraph;
alpar@100	1810	typedef int Value;
alpar@100	1811	typedef typename Digraph::Node Key;
alpar@100	1812
deba@139	1813	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
alpar@100	1814	::ItemNotifier::ObserverBase Parent;
alpar@100	1815
alpar@100	1816	private:
alpar@100	1817
deba@139	1818	class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
alpar@100	1819	public:
alpar@100	1820
deba@139	1821	typedef DefaultMap<Digraph, Key, int> Parent;
alpar@100	1822
alpar@100	1823	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
alpar@100	1824
alpar@100	1825	virtual void add(const Key& key) {
alpar@100	1826	Parent::add(key);
alpar@100	1827	Parent::set(key, 0);
alpar@100	1828	}
alpar@100	1829
alpar@100	1830	virtual void add(const std::vector<Key>& keys) {
alpar@100	1831	Parent::add(keys);
alpar@100	1832	for (int i = 0; i < int(keys.size()); ++i) {
alpar@100	1833	Parent::set(keys[i], 0);
alpar@100	1834	}
alpar@100	1835	}
alpar@100	1836
alpar@100	1837	virtual void build() {
alpar@100	1838	Parent::build();
alpar@100	1839	Key it;
alpar@100	1840	typename Parent::Notifier* nf = Parent::notifier();
alpar@100	1841	for (nf->first(it); it != INVALID; nf->next(it)) {
alpar@100	1842	Parent::set(it, 0);
alpar@100	1843	}
alpar@100	1844	}
alpar@100	1845	};
alpar@100	1846
alpar@100	1847	public:
alpar@100	1848
alpar@100	1849	/// \brief Constructor.
alpar@100	1850	///
alpar@100	1851	/// Constructor for creating in-degree map.
deba@139	1852	explicit InDegMap(const Digraph& digraph)
deba@139	1853	: _digraph(digraph), _deg(digraph) {
deba@139	1854	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
alpar@100	1855
deba@139	1856	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	1857	_deg[it] = countInArcs(_digraph, it);
alpar@100	1858	}
alpar@100	1859	}
alpar@100	1860
alpar@100	1861	/// Gives back the in-degree of a Node.
alpar@100	1862	int operator[](const Key& key) const {
deba@139	1863	return _deg[key];
alpar@100	1864	}
alpar@100	1865
alpar@100	1866	protected:
alpar@100	1867
alpar@100	1868	typedef typename Digraph::Arc Arc;
alpar@100	1869
alpar@100	1870	virtual void add(const Arc& arc) {
deba@139	1871	++_deg[_digraph.target(arc)];
alpar@100	1872	}
alpar@100	1873
alpar@100	1874	virtual void add(const std::vector<Arc>& arcs) {
alpar@100	1875	for (int i = 0; i < int(arcs.size()); ++i) {
deba@139	1876	++_deg[_digraph.target(arcs[i])];
alpar@100	1877	}
alpar@100	1878	}
alpar@100	1879
alpar@100	1880	virtual void erase(const Arc& arc) {
deba@139	1881	--_deg[_digraph.target(arc)];
alpar@100	1882	}
alpar@100	1883
alpar@100	1884	virtual void erase(const std::vector<Arc>& arcs) {
alpar@100	1885	for (int i = 0; i < int(arcs.size()); ++i) {
deba@139	1886	--_deg[_digraph.target(arcs[i])];
alpar@100	1887	}
alpar@100	1888	}
alpar@100	1889
alpar@100	1890	virtual void build() {
deba@139	1891	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	1892	_deg[it] = countInArcs(_digraph, it);
alpar@100	1893	}
alpar@100	1894	}
alpar@100	1895
alpar@100	1896	virtual void clear() {
deba@139	1897	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	1898	_deg[it] = 0;
alpar@100	1899	}
alpar@100	1900	}
alpar@100	1901	private:
alpar@100	1902
deba@139	1903	const Digraph& _digraph;
deba@139	1904	AutoNodeMap _deg;
alpar@100	1905	};
alpar@100	1906
alpar@100	1907	/// \brief Map of the node out-degrees.
alpar@100	1908	///
alpar@100	1909	/// This map returns the out-degree of a node. Once it is constructed,
alpar@100	1910	/// the degrees are stored in a standard NodeMap, so each query is done
alpar@100	1911	/// in constant time. On the other hand, the values are updated automatically
alpar@100	1912	/// whenever the digraph changes.
alpar@100	1913	///
alpar@100	1914	/// \warning Besides addNode() and addArc(), a digraph structure may provide
alpar@100	1915	/// alternative ways to modify the digraph. The correct behavior of OutDegMap
alpar@100	1916	/// is not guarantied if these additional features are used. For example
alpar@100	1917	/// the functions \ref ListDigraph::changeSource() "changeSource()",
alpar@100	1918	/// \ref ListDigraph::changeTarget() "changeTarget()" and
alpar@100	1919	/// \ref ListDigraph::reverseArc() "reverseArc()"
alpar@100	1920	/// of \ref ListDigraph will \e not update the degree values correctly.
alpar@100	1921	///
alpar@100	1922	/// \sa InDegMap
alpar@100	1923
alpar@100	1924	template <typename _Digraph>
alpar@100	1925	class OutDegMap
alpar@100	1926	: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
alpar@100	1927	::ItemNotifier::ObserverBase {
alpar@100	1928
alpar@100	1929	public:
alpar@100	1930
alpar@100	1931	typedef _Digraph Digraph;
alpar@100	1932	typedef int Value;
alpar@100	1933	typedef typename Digraph::Node Key;
alpar@100	1934
deba@139	1935	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@139	1936	::ItemNotifier::ObserverBase Parent;
deba@139	1937
alpar@100	1938	private:
alpar@100	1939
deba@139	1940	class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
alpar@100	1941	public:
alpar@100	1942
deba@139	1943	typedef DefaultMap<Digraph, Key, int> Parent;
alpar@100	1944
alpar@100	1945	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
alpar@100	1946
alpar@100	1947	virtual void add(const Key& key) {
alpar@100	1948	Parent::add(key);
alpar@100	1949	Parent::set(key, 0);
alpar@100	1950	}
alpar@100	1951	virtual void add(const std::vector<Key>& keys) {
alpar@100	1952	Parent::add(keys);
alpar@100	1953	for (int i = 0; i < int(keys.size()); ++i) {
alpar@100	1954	Parent::set(keys[i], 0);
alpar@100	1955	}
alpar@100	1956	}
alpar@100	1957	virtual void build() {
alpar@100	1958	Parent::build();
alpar@100	1959	Key it;
alpar@100	1960	typename Parent::Notifier* nf = Parent::notifier();
alpar@100	1961	for (nf->first(it); it != INVALID; nf->next(it)) {
alpar@100	1962	Parent::set(it, 0);
alpar@100	1963	}
alpar@100	1964	}
alpar@100	1965	};
alpar@100	1966
alpar@100	1967	public:
alpar@100	1968
alpar@100	1969	/// \brief Constructor.
alpar@100	1970	///
alpar@100	1971	/// Constructor for creating out-degree map.
deba@139	1972	explicit OutDegMap(const Digraph& digraph)
deba@139	1973	: _digraph(digraph), _deg(digraph) {
deba@139	1974	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
alpar@100	1975
deba@139	1976	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	1977	_deg[it] = countOutArcs(_digraph, it);
alpar@100	1978	}
alpar@100	1979	}
alpar@100	1980
alpar@100	1981	/// Gives back the out-degree of a Node.
alpar@100	1982	int operator[](const Key& key) const {
deba@139	1983	return _deg[key];
alpar@100	1984	}
alpar@100	1985
alpar@100	1986	protected:
alpar@100	1987
alpar@100	1988	typedef typename Digraph::Arc Arc;
alpar@100	1989
alpar@100	1990	virtual void add(const Arc& arc) {
deba@139	1991	++_deg[_digraph.source(arc)];
alpar@100	1992	}
alpar@100	1993
alpar@100	1994	virtual void add(const std::vector<Arc>& arcs) {
alpar@100	1995	for (int i = 0; i < int(arcs.size()); ++i) {
deba@139	1996	++_deg[_digraph.source(arcs[i])];
alpar@100	1997	}
alpar@100	1998	}
alpar@100	1999
alpar@100	2000	virtual void erase(const Arc& arc) {
deba@139	2001	--_deg[_digraph.source(arc)];
alpar@100	2002	}
alpar@100	2003
alpar@100	2004	virtual void erase(const std::vector<Arc>& arcs) {
alpar@100	2005	for (int i = 0; i < int(arcs.size()); ++i) {
deba@139	2006	--_deg[_digraph.source(arcs[i])];
alpar@100	2007	}
alpar@100	2008	}
alpar@100	2009
alpar@100	2010	virtual void build() {
deba@139	2011	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	2012	_deg[it] = countOutArcs(_digraph, it);
alpar@100	2013	}
alpar@100	2014	}
alpar@100	2015
alpar@100	2016	virtual void clear() {
deba@139	2017	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	2018	_deg[it] = 0;
alpar@100	2019	}
alpar@100	2020	}
alpar@100	2021	private:
alpar@100	2022
deba@139	2023	const Digraph& _digraph;
deba@139	2024	AutoNodeMap _deg;
alpar@100	2025	};
alpar@100	2026
alpar@100	2027
alpar@100	2028	///Dynamic arc look up between given endpoints.
alpar@100	2029
alpar@100	2030	///\ingroup gutils
alpar@100	2031	///Using this class, you can find an arc in a digraph from a given
alpar@100	2032	///source to a given target in amortized time <em>O(log d)</em>,
alpar@100	2033	///where <em>d</em> is the out-degree of the source node.
alpar@100	2034	///
alpar@100	2035	///It is possible to find \e all parallel arcs between two nodes with
alpar@100	2036	///the \c findFirst() and \c findNext() members.
alpar@100	2037	///
alpar@100	2038	///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
deba@139	2039	///digraph is not changed so frequently.
alpar@100	2040	///
alpar@100	2041	///This class uses a self-adjusting binary search tree, Sleator's
alpar@100	2042	///and Tarjan's Splay tree for guarantee the logarithmic amortized
alpar@100	2043	///time bound for arc lookups. This class also guarantees the
alpar@100	2044	///optimal time bound in a constant factor for any distribution of
alpar@100	2045	///queries.
alpar@100	2046	///
alpar@100	2047	///\param G The type of the underlying digraph.
alpar@100	2048	///
alpar@100	2049	///\sa ArcLookUp
alpar@100	2050	///\sa AllArcLookUp
alpar@100	2051	template<class G>
alpar@100	2052	class DynArcLookUp
alpar@100	2053	: protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
alpar@100	2054	{
alpar@100	2055	public:
alpar@100	2056	typedef typename ItemSetTraits<G, typename G::Arc>
alpar@100	2057	::ItemNotifier::ObserverBase Parent;
alpar@100	2058
deba@139	2059	DIGRAPH_TYPEDEFS(typename G);
alpar@100	2060	typedef G Digraph;
alpar@100	2061
alpar@100	2062	protected:
alpar@100	2063
alpar@100	2064	class AutoNodeMap : public DefaultMap<G, Node, Arc> {
alpar@100	2065	public:
alpar@100	2066
alpar@100	2067	typedef DefaultMap<G, Node, Arc> Parent;
alpar@100	2068
alpar@100	2069	AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
alpar@100	2070
alpar@100	2071	virtual void add(const Node& node) {
alpar@100	2072	Parent::add(node);
alpar@100	2073	Parent::set(node, INVALID);
alpar@100	2074	}
alpar@100	2075
alpar@100	2076	virtual void add(const std::vector<Node>& nodes) {
alpar@100	2077	Parent::add(nodes);
alpar@100	2078	for (int i = 0; i < int(nodes.size()); ++i) {
alpar@100	2079	Parent::set(nodes[i], INVALID);
alpar@100	2080	}
alpar@100	2081	}
alpar@100	2082
alpar@100	2083	virtual void build() {
alpar@100	2084	Parent::build();
alpar@100	2085	Node it;
alpar@100	2086	typename Parent::Notifier* nf = Parent::notifier();
alpar@100	2087	for (nf->first(it); it != INVALID; nf->next(it)) {
alpar@100	2088	Parent::set(it, INVALID);
alpar@100	2089	}
alpar@100	2090	}
alpar@100	2091	};
alpar@100	2092
alpar@100	2093	const Digraph &_g;
alpar@100	2094	AutoNodeMap _head;
alpar@100	2095	typename Digraph::template ArcMap<Arc> _parent;
alpar@100	2096	typename Digraph::template ArcMap<Arc> _left;
alpar@100	2097	typename Digraph::template ArcMap<Arc> _right;
alpar@100	2098
alpar@100	2099	class ArcLess {
alpar@100	2100	const Digraph &g;
alpar@100	2101	public:
alpar@100	2102	ArcLess(const Digraph &_g) : g(_g) {}
alpar@100	2103	bool operator()(Arc a,Arc b) const
alpar@100	2104	{
alpar@100	2105	return g.target(a)<g.target(b);
alpar@100	2106	}
alpar@100	2107	};
alpar@100	2108
alpar@100	2109	public:
alpar@100	2110
alpar@100	2111	///Constructor
alpar@100	2112
alpar@100	2113	///Constructor.
alpar@100	2114	///
alpar@100	2115	///It builds up the search database.
alpar@100	2116	DynArcLookUp(const Digraph &g)
alpar@100	2117	: _g(g),_head(g),_parent(g),_left(g),_right(g)
alpar@100	2118	{
alpar@100	2119	Parent::attach(_g.notifier(typename Digraph::Arc()));
alpar@100	2120	refresh();
alpar@100	2121	}
alpar@100	2122
alpar@100	2123	protected:
alpar@100	2124
alpar@100	2125	virtual void add(const Arc& arc) {
alpar@100	2126	insert(arc);
alpar@100	2127	}
alpar@100	2128
alpar@100	2129	virtual void add(const std::vector<Arc>& arcs) {
alpar@100	2130	for (int i = 0; i < int(arcs.size()); ++i) {
alpar@100	2131	insert(arcs[i]);
alpar@100	2132	}
alpar@100	2133	}
alpar@100	2134
alpar@100	2135	virtual void erase(const Arc& arc) {
alpar@100	2136	remove(arc);
alpar@100	2137	}
alpar@100	2138
alpar@100	2139	virtual void erase(const std::vector<Arc>& arcs) {
alpar@100	2140	for (int i = 0; i < int(arcs.size()); ++i) {
alpar@100	2141	remove(arcs[i]);
alpar@100	2142	}
alpar@100	2143	}
alpar@100	2144
alpar@100	2145	virtual void build() {
alpar@100	2146	refresh();
alpar@100	2147	}
alpar@100	2148
alpar@100	2149	virtual void clear() {
alpar@100	2150	for(NodeIt n(_g);n!=INVALID;++n) {
alpar@100	2151	_head.set(n, INVALID);
alpar@100	2152	}
alpar@100	2153	}
alpar@100	2154
alpar@100	2155	void insert(Arc arc) {
alpar@100	2156	Node s = _g.source(arc);
alpar@100	2157	Node t = _g.target(arc);
alpar@100	2158	_left.set(arc, INVALID);
alpar@100	2159	_right.set(arc, INVALID);
alpar@100	2160
alpar@100	2161	Arc e = _head[s];
alpar@100	2162	if (e == INVALID) {
alpar@100	2163	_head.set(s, arc);
alpar@100	2164	_parent.set(arc, INVALID);
alpar@100	2165	return;
alpar@100	2166	}
alpar@100	2167	while (true) {
alpar@100	2168	if (t < _g.target(e)) {
alpar@100	2169	if (_left[e] == INVALID) {
alpar@100	2170	_left.set(e, arc);
alpar@100	2171	_parent.set(arc, e);
alpar@100	2172	splay(arc);
alpar@100	2173	return;
alpar@100	2174	} else {
alpar@100	2175	e = _left[e];
alpar@100	2176	}
alpar@100	2177	} else {
alpar@100	2178	if (_right[e] == INVALID) {
alpar@100	2179	_right.set(e, arc);
alpar@100	2180	_parent.set(arc, e);
alpar@100	2181	splay(arc);
alpar@100	2182	return;
alpar@100	2183	} else {
alpar@100	2184	e = _right[e];
alpar@100	2185	}
alpar@100	2186	}
alpar@100	2187	}
alpar@100	2188	}
alpar@100	2189
alpar@100	2190	void remove(Arc arc) {
alpar@100	2191	if (_left[arc] == INVALID) {
alpar@100	2192	if (_right[arc] != INVALID) {
alpar@100	2193	_parent.set(_right[arc], _parent[arc]);
alpar@100	2194	}
alpar@100	2195	if (_parent[arc] != INVALID) {
alpar@100	2196	if (_left[_parent[arc]] == arc) {
alpar@100	2197	_left.set(_parent[arc], _right[arc]);
alpar@100	2198	} else {
alpar@100	2199	_right.set(_parent[arc], _right[arc]);
alpar@100	2200	}
alpar@100	2201	} else {
alpar@100	2202	_head.set(_g.source(arc), _right[arc]);
alpar@100	2203	}
alpar@100	2204	} else if (_right[arc] == INVALID) {
alpar@100	2205	_parent.set(_left[arc], _parent[arc]);
alpar@100	2206	if (_parent[arc] != INVALID) {
alpar@100	2207	if (_left[_parent[arc]] == arc) {
alpar@100	2208	_left.set(_parent[arc], _left[arc]);
alpar@100	2209	} else {
alpar@100	2210	_right.set(_parent[arc], _left[arc]);
alpar@100	2211	}
alpar@100	2212	} else {
alpar@100	2213	_head.set(_g.source(arc), _left[arc]);
alpar@100	2214	}
alpar@100	2215	} else {
alpar@100	2216	Arc e = _left[arc];
alpar@100	2217	if (_right[e] != INVALID) {
alpar@100	2218	e = _right[e];
alpar@100	2219	while (_right[e] != INVALID) {
alpar@100	2220	e = _right[e];
alpar@100	2221	}
alpar@100	2222	Arc s = _parent[e];
alpar@100	2223	_right.set(_parent[e], _left[e]);
alpar@100	2224	if (_left[e] != INVALID) {
alpar@100	2225	_parent.set(_left[e], _parent[e]);
alpar@100	2226	}
alpar@100	2227
alpar@100	2228	_left.set(e, _left[arc]);
alpar@100	2229	_parent.set(_left[arc], e);
alpar@100	2230	_right.set(e, _right[arc]);
alpar@100	2231	_parent.set(_right[arc], e);
alpar@100	2232
alpar@100	2233	_parent.set(e, _parent[arc]);
alpar@100	2234	if (_parent[arc] != INVALID) {
alpar@100	2235	if (_left[_parent[arc]] == arc) {
alpar@100	2236	_left.set(_parent[arc], e);
alpar@100	2237	} else {
alpar@100	2238	_right.set(_parent[arc], e);
alpar@100	2239	}
alpar@100	2240	}
alpar@100	2241	splay(s);
alpar@100	2242	} else {
alpar@100	2243	_right.set(e, _right[arc]);
alpar@100	2244	_parent.set(_right[arc], e);
alpar@100	2245
alpar@100	2246	if (_parent[arc] != INVALID) {
alpar@100	2247	if (_left[_parent[arc]] == arc) {
alpar@100	2248	_left.set(_parent[arc], e);
alpar@100	2249	} else {
alpar@100	2250	_right.set(_parent[arc], e);
alpar@100	2251	}
alpar@100	2252	} else {
alpar@100	2253	_head.set(_g.source(arc), e);
alpar@100	2254	}
alpar@100	2255	}
alpar@100	2256	}
alpar@100	2257	}
alpar@100	2258
alpar@100	2259	Arc refreshRec(std::vector<Arc> &v,int a,int b)
alpar@100	2260	{
alpar@100	2261	int m=(a+b)/2;
alpar@100	2262	Arc me=v[m];
alpar@100	2263	if (a < m) {
alpar@100	2264	Arc left = refreshRec(v,a,m-1);
alpar@100	2265	_left.set(me, left);
alpar@100	2266	_parent.set(left, me);
alpar@100	2267	} else {
alpar@100	2268	_left.set(me, INVALID);
alpar@100	2269	}
alpar@100	2270	if (m < b) {
alpar@100	2271	Arc right = refreshRec(v,m+1,b);
alpar@100	2272	_right.set(me, right);
alpar@100	2273	_parent.set(right, me);
alpar@100	2274	} else {
alpar@100	2275	_right.set(me, INVALID);
alpar@100	2276	}
alpar@100	2277	return me;
alpar@100	2278	}
alpar@100	2279
alpar@100	2280	void refresh() {
alpar@100	2281	for(NodeIt n(_g);n!=INVALID;++n) {
alpar@100	2282	std::vector<Arc> v;
alpar@100	2283	for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
alpar@100	2284	if(v.size()) {
alpar@100	2285	std::sort(v.begin(),v.end(),ArcLess(_g));
alpar@100	2286	Arc head = refreshRec(v,0,v.size()-1);
alpar@100	2287	_head.set(n, head);
alpar@100	2288	_parent.set(head, INVALID);
alpar@100	2289	}
alpar@100	2290	else _head.set(n, INVALID);
alpar@100	2291	}
alpar@100	2292	}
alpar@100	2293
alpar@100	2294	void zig(Arc v) {
alpar@100	2295	Arc w = _parent[v];
alpar@100	2296	_parent.set(v, _parent[w]);
alpar@100	2297	_parent.set(w, v);
alpar@100	2298	_left.set(w, _right[v]);
alpar@100	2299	_right.set(v, w);
alpar@100	2300	if (_parent[v] != INVALID) {
alpar@100	2301	if (_right[_parent[v]] == w) {
alpar@100	2302	_right.set(_parent[v], v);
alpar@100	2303	} else {
alpar@100	2304	_left.set(_parent[v], v);
alpar@100	2305	}
alpar@100	2306	}
alpar@100	2307	if (_left[w] != INVALID){
alpar@100	2308	_parent.set(_left[w], w);
alpar@100	2309	}
alpar@100	2310	}
alpar@100	2311
alpar@100	2312	void zag(Arc v) {
alpar@100	2313	Arc w = _parent[v];
alpar@100	2314	_parent.set(v, _parent[w]);
alpar@100	2315	_parent.set(w, v);
alpar@100	2316	_right.set(w, _left[v]);
alpar@100	2317	_left.set(v, w);
alpar@100	2318	if (_parent[v] != INVALID){
alpar@100	2319	if (_left[_parent[v]] == w) {
alpar@100	2320	_left.set(_parent[v], v);
alpar@100	2321	} else {
alpar@100	2322	_right.set(_parent[v], v);
alpar@100	2323	}
alpar@100	2324	}
alpar@100	2325	if (_right[w] != INVALID){
alpar@100	2326	_parent.set(_right[w], w);
alpar@100	2327	}
alpar@100	2328	}
alpar@100	2329
alpar@100	2330	void splay(Arc v) {
alpar@100	2331	while (_parent[v] != INVALID) {
alpar@100	2332	if (v == _left[_parent[v]]) {
alpar@100	2333	if (_parent[_parent[v]] == INVALID) {
alpar@100	2334	zig(v);
alpar@100	2335	} else {
alpar@100	2336	if (_parent[v] == _left[_parent[_parent[v]]]) {
alpar@100	2337	zig(_parent[v]);
alpar@100	2338	zig(v);
alpar@100	2339	} else {
alpar@100	2340	zig(v);
alpar@100	2341	zag(v);
alpar@100	2342	}
alpar@100	2343	}
alpar@100	2344	} else {
alpar@100	2345	if (_parent[_parent[v]] == INVALID) {
alpar@100	2346	zag(v);
alpar@100	2347	} else {
alpar@100	2348	if (_parent[v] == _left[_parent[_parent[v]]]) {
alpar@100	2349	zag(v);
alpar@100	2350	zig(v);
alpar@100	2351	} else {
alpar@100	2352	zag(_parent[v]);
alpar@100	2353	zag(v);
alpar@100	2354	}
alpar@100	2355	}
alpar@100	2356	}
alpar@100	2357	}
alpar@100	2358	_head[_g.source(v)] = v;
alpar@100	2359	}
alpar@100	2360
alpar@100	2361
alpar@100	2362	public:
alpar@100	2363
alpar@100	2364	///Find an arc between two nodes.
alpar@100	2365
alpar@100	2366	///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
alpar@100	2367	/// <em>d</em> is the number of outgoing arcs of \c s.
alpar@100	2368	///\param s The source node
alpar@100	2369	///\param t The target node
alpar@100	2370	///\return An arc from \c s to \c t if there exists,
alpar@100	2371	///\ref INVALID otherwise.
alpar@100	2372	Arc operator()(Node s, Node t) const
alpar@100	2373	{
deba@139	2374	Arc a = _head[s];
alpar@100	2375	while (true) {
deba@139	2376	if (_g.target(a) == t) {
deba@139	2377	const_cast<DynArcLookUp&>(*this).splay(a);
deba@139	2378	return a;
deba@139	2379	} else if (t < _g.target(a)) {
deba@139	2380	if (_left[a] == INVALID) {
deba@139	2381	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2382	return INVALID;
alpar@100	2383	} else {
deba@139	2384	a = _left[a];
alpar@100	2385	}
alpar@100	2386	} else {
deba@139	2387	if (_right[a] == INVALID) {
deba@139	2388	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2389	return INVALID;
alpar@100	2390	} else {
deba@139	2391	a = _right[a];
alpar@100	2392	}
alpar@100	2393	}
alpar@100	2394	}
alpar@100	2395	}
alpar@100	2396
alpar@100	2397	///Find the first arc between two nodes.
alpar@100	2398
alpar@100	2399	///Find the first arc between two nodes in time
alpar@100	2400	/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
alpar@100	2401	/// outgoing arcs of \c s.
alpar@100	2402	///\param s The source node
alpar@100	2403	///\param t The target node
alpar@100	2404	///\return An arc from \c s to \c t if there exists, \ref INVALID
alpar@100	2405	/// otherwise.
alpar@100	2406	Arc findFirst(Node s, Node t) const
alpar@100	2407	{
deba@139	2408	Arc a = _head[s];
alpar@100	2409	Arc r = INVALID;
alpar@100	2410	while (true) {
deba@139	2411	if (_g.target(a) < t) {
deba@139	2412	if (_right[a] == INVALID) {
deba@139	2413	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2414	return r;
alpar@100	2415	} else {
deba@139	2416	a = _right[a];
alpar@100	2417	}
alpar@100	2418	} else {
deba@139	2419	if (_g.target(a) == t) {
deba@139	2420	r = a;
alpar@100	2421	}
deba@139	2422	if (_left[a] == INVALID) {
deba@139	2423	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2424	return r;
alpar@100	2425	} else {
deba@139	2426	a = _left[a];
alpar@100	2427	}
alpar@100	2428	}
alpar@100	2429	}
alpar@100	2430	}
alpar@100	2431
alpar@100	2432	///Find the next arc between two nodes.
alpar@100	2433
alpar@100	2434	///Find the next arc between two nodes in time
alpar@100	2435	/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
alpar@100	2436	/// outgoing arcs of \c s.
alpar@100	2437	///\param s The source node
alpar@100	2438	///\param t The target node
alpar@100	2439	///\return An arc from \c s to \c t if there exists, \ref INVALID
alpar@100	2440	/// otherwise.
alpar@100	2441
alpar@100	2442	///\note If \c e is not the result of the previous \c findFirst()
alpar@100	2443	///operation then the amorized time bound can not be guaranteed.
alpar@100	2444	#ifdef DOXYGEN
deba@139	2445	Arc findNext(Node s, Node t, Arc a) const
alpar@100	2446	#else
deba@139	2447	Arc findNext(Node, Node t, Arc a) const
alpar@100	2448	#endif
alpar@100	2449	{
deba@139	2450	if (_right[a] != INVALID) {
deba@139	2451	a = _right[a];
deba@139	2452	while (_left[a] != INVALID) {
deba@139	2453	a = _left[a];
alpar@100	2454	}
deba@139	2455	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2456	} else {
deba@139	2457	while (_parent[a] != INVALID && _right[_parent[a]] == a) {
deba@139	2458	a = _parent[a];
alpar@100	2459	}
deba@139	2460	if (_parent[a] == INVALID) {
alpar@100	2461	return INVALID;
alpar@100	2462	} else {
deba@139	2463	a = _parent[a];
deba@139	2464	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2465	}
alpar@100	2466	}
deba@139	2467	if (_g.target(a) == t) return a;
alpar@100	2468	else return INVALID;
alpar@100	2469	}
alpar@100	2470
alpar@100	2471	};
alpar@100	2472
alpar@100	2473	///Fast arc look up between given endpoints.
alpar@100	2474
alpar@100	2475	///\ingroup gutils
alpar@100	2476	///Using this class, you can find an arc in a digraph from a given
alpar@100	2477	///source to a given target in time <em>O(log d)</em>,
alpar@100	2478	///where <em>d</em> is the out-degree of the source node.
alpar@100	2479	///
alpar@100	2480	///It is not possible to find \e all parallel arcs between two nodes.
alpar@100	2481	///Use \ref AllArcLookUp for this purpose.
alpar@100	2482	///
alpar@100	2483	///\warning This class is static, so you should refresh() (or at least
alpar@100	2484	///refresh(Node)) this data structure
alpar@100	2485	///whenever the digraph changes. This is a time consuming (superlinearly
alpar@100	2486	///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
alpar@100	2487	///
alpar@100	2488	///\param G The type of the underlying digraph.
alpar@100	2489	///
alpar@100	2490	///\sa DynArcLookUp
alpar@100	2491	///\sa AllArcLookUp
alpar@100	2492	template<class G>
alpar@100	2493	class ArcLookUp
alpar@100	2494	{
alpar@100	2495	public:
deba@139	2496	DIGRAPH_TYPEDEFS(typename G);
alpar@100	2497	typedef G Digraph;
alpar@100	2498
alpar@100	2499	protected:
alpar@100	2500	const Digraph &_g;
alpar@100	2501	typename Digraph::template NodeMap<Arc> _head;
alpar@100	2502	typename Digraph::template ArcMap<Arc> _left;
alpar@100	2503	typename Digraph::template ArcMap<Arc> _right;
alpar@100	2504
alpar@100	2505	class ArcLess {
alpar@100	2506	const Digraph &g;
alpar@100	2507	public:
alpar@100	2508	ArcLess(const Digraph &_g) : g(_g) {}
alpar@100	2509	bool operator()(Arc a,Arc b) const
alpar@100	2510	{
alpar@100	2511	return g.target(a)<g.target(b);
alpar@100	2512	}
alpar@100	2513	};
alpar@100	2514
alpar@100	2515	public:
alpar@100	2516
alpar@100	2517	///Constructor
alpar@100	2518
alpar@100	2519	///Constructor.
alpar@100	2520	///
alpar@100	2521	///It builds up the search database, which remains valid until the digraph
alpar@100	2522	///changes.
alpar@100	2523	ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
alpar@100	2524
alpar@100	2525	private:
alpar@100	2526	Arc refreshRec(std::vector<Arc> &v,int a,int b)
alpar@100	2527	{
alpar@100	2528	int m=(a+b)/2;
alpar@100	2529	Arc me=v[m];
alpar@100	2530	_left[me] = a<m?refreshRec(v,a,m-1):INVALID;
alpar@100	2531	_right[me] = m<b?refreshRec(v,m+1,b):INVALID;
alpar@100	2532	return me;
alpar@100	2533	}
alpar@100	2534	public:
alpar@100	2535	///Refresh the data structure at a node.
alpar@100	2536
alpar@100	2537	///Build up the search database of node \c n.
alpar@100	2538	///
alpar@100	2539	///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
alpar@100	2540	///the number of the outgoing arcs of \c n.
alpar@100	2541	void refresh(Node n)
alpar@100	2542	{
alpar@100	2543	std::vector<Arc> v;
alpar@100	2544	for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
alpar@100	2545	if(v.size()) {
alpar@100	2546	std::sort(v.begin(),v.end(),ArcLess(_g));
alpar@100	2547	_head[n]=refreshRec(v,0,v.size()-1);
alpar@100	2548	}
alpar@100	2549	else _head[n]=INVALID;
alpar@100	2550	}
alpar@100	2551	///Refresh the full data structure.
alpar@100	2552
alpar@100	2553	///Build up the full search database. In fact, it simply calls
alpar@100	2554	///\ref refresh(Node) "refresh(n)" for each node \c n.
alpar@100	2555	///
alpar@100	2556	///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
alpar@100	2557	///the number of the arcs of \c n and <em>D</em> is the maximum
alpar@100	2558	///out-degree of the digraph.
alpar@100	2559
alpar@100	2560	void refresh()
alpar@100	2561	{
alpar@100	2562	for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
alpar@100	2563	}
alpar@100	2564
alpar@100	2565	///Find an arc between two nodes.
alpar@100	2566
alpar@100	2567	///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
alpar@100	2568	/// <em>d</em> is the number of outgoing arcs of \c s.
alpar@100	2569	///\param s The source node
alpar@100	2570	///\param t The target node
alpar@100	2571	///\return An arc from \c s to \c t if there exists,
alpar@100	2572	///\ref INVALID otherwise.
alpar@100	2573	///
alpar@100	2574	///\warning If you change the digraph, refresh() must be called before using
alpar@100	2575	///this operator. If you change the outgoing arcs of
alpar@100	2576	///a single node \c n, then
alpar@100	2577	///\ref refresh(Node) "refresh(n)" is enough.
alpar@100	2578	///
alpar@100	2579	Arc operator()(Node s, Node t) const
alpar@100	2580	{
alpar@100	2581	Arc e;
alpar@100	2582	for(e=_head[s];
alpar@100	2583	e!=INVALID&&_g.target(e)!=t;
alpar@100	2584	e = t < _g.target(e)?_left[e]:_right[e]) ;
alpar@100	2585	return e;
alpar@100	2586	}
alpar@100	2587
alpar@100	2588	};
alpar@100	2589
alpar@100	2590	///Fast look up of all arcs between given endpoints.
alpar@100	2591
alpar@100	2592	///\ingroup gutils
alpar@100	2593	///This class is the same as \ref ArcLookUp, with the addition
alpar@100	2594	///that it makes it possible to find all arcs between given endpoints.
alpar@100	2595	///
alpar@100	2596	///\warning This class is static, so you should refresh() (or at least
alpar@100	2597	///refresh(Node)) this data structure
alpar@100	2598	///whenever the digraph changes. This is a time consuming (superlinearly
alpar@100	2599	///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
alpar@100	2600	///
alpar@100	2601	///\param G The type of the underlying digraph.
alpar@100	2602	///
alpar@100	2603	///\sa DynArcLookUp
alpar@100	2604	///\sa ArcLookUp
alpar@100	2605	template<class G>
alpar@100	2606	class AllArcLookUp : public ArcLookUp<G>
alpar@100	2607	{
alpar@100	2608	using ArcLookUp<G>::_g;
alpar@100	2609	using ArcLookUp<G>::_right;
alpar@100	2610	using ArcLookUp<G>::_left;
alpar@100	2611	using ArcLookUp<G>::_head;
alpar@100	2612
deba@139	2613	DIGRAPH_TYPEDEFS(typename G);
alpar@100	2614	typedef G Digraph;
alpar@100	2615
alpar@100	2616	typename Digraph::template ArcMap<Arc> _next;
alpar@100	2617
alpar@100	2618	Arc refreshNext(Arc head,Arc next=INVALID)
alpar@100	2619	{
alpar@100	2620	if(head==INVALID) return next;
alpar@100	2621	else {
alpar@100	2622	next=refreshNext(_right[head],next);
alpar@100	2623	// _next[head]=next;
alpar@100	2624	_next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
alpar@100	2625	? next : INVALID;
alpar@100	2626	return refreshNext(_left[head],head);
alpar@100	2627	}
alpar@100	2628	}
alpar@100	2629
alpar@100	2630	void refreshNext()
alpar@100	2631	{
alpar@100	2632	for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
alpar@100	2633	}
alpar@100	2634
alpar@100	2635	public:
alpar@100	2636	///Constructor
alpar@100	2637
alpar@100	2638	///Constructor.
alpar@100	2639	///
alpar@100	2640	///It builds up the search database, which remains valid until the digraph
alpar@100	2641	///changes.
alpar@100	2642	AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
alpar@100	2643
alpar@100	2644	///Refresh the data structure at a node.
alpar@100	2645
alpar@100	2646	///Build up the search database of node \c n.
alpar@100	2647	///
alpar@100	2648	///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
alpar@100	2649	///the number of the outgoing arcs of \c n.
alpar@100	2650
alpar@100	2651	void refresh(Node n)
alpar@100	2652	{
alpar@100	2653	ArcLookUp<G>::refresh(n);
alpar@100	2654	refreshNext(_head[n]);
alpar@100	2655	}
alpar@100	2656
alpar@100	2657	///Refresh the full data structure.
alpar@100	2658
alpar@100	2659	///Build up the full search database. In fact, it simply calls
alpar@100	2660	///\ref refresh(Node) "refresh(n)" for each node \c n.
alpar@100	2661	///
alpar@100	2662	///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
alpar@100	2663	///the number of the arcs of \c n and <em>D</em> is the maximum
alpar@100	2664	///out-degree of the digraph.
alpar@100	2665
alpar@100	2666	void refresh()
alpar@100	2667	{
alpar@100	2668	for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
alpar@100	2669	}
alpar@100	2670
alpar@100	2671	///Find an arc between two nodes.
alpar@100	2672
alpar@100	2673	///Find an arc between two nodes.
alpar@100	2674	///\param s The source node
alpar@100	2675	///\param t The target node
alpar@100	2676	///\param prev The previous arc between \c s and \c t. It it is INVALID or
alpar@100	2677	///not given, the operator finds the first appropriate arc.
alpar@100	2678	///\return An arc from \c s to \c t after \c prev or
alpar@100	2679	///\ref INVALID if there is no more.
alpar@100	2680	///
alpar@100	2681	///For example, you can count the number of arcs from \c u to \c v in the
alpar@100	2682	///following way.
alpar@100	2683	///\code
alpar@100	2684	///AllArcLookUp<ListDigraph> ae(g);
alpar@100	2685	///...
alpar@100	2686	///int n=0;
alpar@100	2687	///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
alpar@100	2688	///\endcode
alpar@100	2689	///
alpar@100	2690	///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
alpar@100	2691	/// <em>d</em> is the number of outgoing arcs of \c s. Then, the
alpar@100	2692	///consecutive arcs are found in constant time.
alpar@100	2693	///
alpar@100	2694	///\warning If you change the digraph, refresh() must be called before using
alpar@100	2695	///this operator. If you change the outgoing arcs of
alpar@100	2696	///a single node \c n, then
alpar@100	2697	///\ref refresh(Node) "refresh(n)" is enough.
alpar@100	2698	///
alpar@100	2699	#ifdef DOXYGEN
alpar@100	2700	Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
alpar@100	2701	#else
alpar@100	2702	using ArcLookUp<G>::operator() ;
alpar@100	2703	Arc operator()(Node s, Node t, Arc prev) const
alpar@100	2704	{
alpar@100	2705	return prev==INVALID?(*this)(s,t):_next[prev];
alpar@100	2706	}
alpar@100	2707	#endif
alpar@100	2708
alpar@100	2709	};
alpar@100	2710
alpar@100	2711	/// @}
alpar@100	2712
alpar@100	2713	} //END OF NAMESPACE LEMON
alpar@100	2714
alpar@100	2715	#endif

author	Balazs Dezso <deba@inf.elte.hu>
	Tue, 22 Apr 2008 15:04:00 +0200
changeset 139	701c529ba737
parent 100	4f754b4cf82b
child 140	356930927a71
permissions	-rw-r--r--