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

author	Alpar Juttner <alpar@cs.elte.hu>
	Sun, 30 Mar 2008 22:16:35 +0100
changeset 119	82a2639a05bb
child 139	701c529ba737
permissions	-rw-r--r--