lemon-main: lemon/graph_utils.h@c5a40fc54f1a (annotated)

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

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 18 Jul 2008 16:36:58 +0100
changeset 225	c5a40fc54f1a
parent 209	765619b7cbb2
permissions	-rw-r--r--