lemon-1.0: lemon/graph_utils.h@2ccc1afc2c52 (annotated)

alpar@100	1	/* -- C++ --
alpar@100	2	*
alpar@100	3	* This file is a part of LEMON, a generic C++ optimization library
alpar@100	4	*
alpar@100	5	* Copyright (C) 2003-2008
alpar@100	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100	8	*
alpar@100	9	* Permission to use, modify and distribute this software is granted
alpar@100	10	* provided that this copyright notice appears in all copies. For
alpar@100	11	* precise terms see the accompanying LICENSE file.
alpar@100	12	*
alpar@100	13	* This software is provided "AS IS" with no warranty of any kind,
alpar@100	14	* express or implied, and with no claim as to its suitability for any
alpar@100	15	* purpose.
alpar@100	16	*
alpar@100	17	*/
alpar@100	18
alpar@100	19	#ifndef LEMON_GRAPH_UTILS_H
alpar@100	20	#define LEMON_GRAPH_UTILS_H
alpar@100	21
alpar@100	22	#include <iterator>
alpar@100	23	#include <vector>
alpar@100	24	#include <map>
alpar@100	25	#include <cmath>
alpar@100	26	#include <algorithm>
alpar@100	27
alpar@100	28	#include <lemon/bits/invalid.h>
alpar@100	29	#include <lemon/bits/utility.h>
alpar@100	30	#include <lemon/maps.h>
alpar@100	31	#include <lemon/bits/traits.h>
alpar@100	32
alpar@100	33	#include <lemon/bits/alteration_notifier.h>
alpar@100	34	#include <lemon/bits/default_map.h>
alpar@100	35
alpar@100	36	///\ingroup gutils
alpar@100	37	///\file
deba@139	38	///\brief Graph utilities.
alpar@100	39
alpar@100	40	namespace lemon {
alpar@100	41
alpar@100	42	/// \addtogroup gutils
alpar@100	43	/// @{
alpar@100	44
alpar@100	45	///Creates convenience typedefs for the digraph types and iterators
alpar@100	46
alpar@100	47	///This \c \#define creates convenience typedefs for the following types
alpar@100	48	///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
deba@139	49	///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
deba@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.
deba@139	55	#define DIGRAPH_TYPEDEFS(Digraph) \
deba@148	56	typedef Digraph::Node Node; \
deba@148	57	typedef Digraph::NodeIt NodeIt; \
deba@148	58	typedef Digraph::Arc Arc; \
deba@148	59	typedef Digraph::ArcIt ArcIt; \
deba@148	60	typedef Digraph::InArcIt InArcIt; \
deba@148	61	typedef Digraph::OutArcIt OutArcIt; \
deba@148	62	typedef Digraph::NodeMap<bool> BoolNodeMap; \
deba@148	63	typedef Digraph::NodeMap<int> IntNodeMap; \
deba@148	64	typedef Digraph::NodeMap<double> DoubleNodeMap; \
deba@148	65	typedef Digraph::ArcMap<bool> BoolArcMap; \
deba@148	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.
deba@148	75	#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
deba@148	76	typedef typename Digraph::Node Node; \
deba@148	77	typedef typename Digraph::NodeIt NodeIt; \
deba@148	78	typedef typename Digraph::Arc Arc; \
deba@148	79	typedef typename Digraph::ArcIt ArcIt; \
deba@148	80	typedef typename Digraph::InArcIt InArcIt; \
deba@148	81	typedef typename Digraph::OutArcIt OutArcIt; \
deba@148	82	typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
deba@148	83	typedef typename Digraph::template NodeMap<int> IntNodeMap; \
deba@148	84	typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
deba@148	85	typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
deba@148	86	typedef typename Digraph::template ArcMap<int> IntArcMap; \
deba@148	87	typedef typename Digraph::template ArcMap<double> DoubleArcMap
deba@148	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.
deba@139	99	#define GRAPH_TYPEDEFS(Graph) \
deba@139	100	DIGRAPH_TYPEDEFS(Graph); \
deba@148	101	typedef Graph::Edge Edge; \
deba@148	102	typedef Graph::EdgeIt EdgeIt; \
deba@148	103	typedef Graph::IncEdgeIt IncEdgeIt; \
deba@148	104	typedef Graph::EdgeMap<bool> BoolEdgeMap; \
deba@148	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.
deba@148	114	#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
deba@148	115	TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
deba@148	116	typedef typename Graph::Edge Edge; \
deba@148	117	typedef typename Graph::EdgeIt EdgeIt; \
deba@148	118	typedef typename Graph::IncEdgeIt IncEdgeIt; \
deba@148	119	typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
deba@148	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@100	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<
deba@139	151	Graph, typename
deba@139	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@100	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	///
deba@139	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@100	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<
deba@139	187	Graph,
deba@139	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@100	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	///
deba@139	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@100	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<
deba@139	222	Graph,
deba@139	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@100	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	///
deba@139	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
deba@139	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
deba@139	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
deba@139	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@100	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<
deba@139	304	Graph,
deba@139	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@100	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>
deba@139	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@100	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@100	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@100	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@100	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++() {
deba@139	385	Parent::operator=(findArc(_graph, _graph.source(*this),
deba@139	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@100	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 {
alpar@100	405	b = g.source(e) == u;
alpar@100	406	g.nextInc(e, b);
alpar@100	407	}
alpar@100	408	while (e != INVALID && (b ? g.target(e) : g.source(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	}
alpar@100	418	while (e != INVALID && (!b \|\| g.target(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<
deba@139	428	Graph,
deba@139	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@100	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@100	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	///
alpar@100	458	///\sa ConArcIt
alpar@100	459
deba@139	460	template <typename Graph>
deba@139	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@100	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@100	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@100	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++() {
deba@139	507	Parent::operator=(findEdge(_graph, _graph.source(*this),
deba@139	508	_graph.target(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@100	521
alpar@100	522	virtual ~MapCopyBase() {}
alpar@100	523	};
alpar@100	524
alpar@100	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@100	530	MapCopy(ToMap& tmap, const FromMap& map)
alpar@100	531	: _tmap(tmap), _map(map) {}
alpar@100	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@100	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@100	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@100	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@100	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@100	604	arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
alpar@100	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@100	612	Digraph,
alpar@100	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@100	631	edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
alpar@100	632	nodeRefMap[from.target(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@100	639	Graph,
alpar@100	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@100	700
alpar@100	701
alpar@100	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.
deba@139	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) {
deba@139	733	_node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
deba@139	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,
deba@139	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) {
deba@139	758	_node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
deba@139	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) {
deba@139	767	_node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
deba@139	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) {
deba@139	777	_arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
deba@139	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,
deba@139	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@100	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@100	798	/// type.
alpar@100	799	template <typename ToMap, typename FromMap>
alpar@100	800	DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
deba@139	801	_arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
deba@139	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) {
deba@139	810	_arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
deba@139	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@100	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
deba@139	837	std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
deba@139	838	_node_maps;
alpar@100	839
deba@139	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@100	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@100	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,
deba@139	920	const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
deba@139	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 {
alpar@100	928	bool forward =
deba@139	929	(_from.direction(key) ==
deba@139	930	(_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
deba@139	931	return _to.direct(_edge_ref[key], forward);
alpar@100	932	}
alpar@100	933
deba@139	934	const To& _to;
deba@139	935	const From& _from;
deba@139	936	const EdgeRefMap& _edge_ref;
deba@139	937	const NodeRefMap& _node_ref;
alpar@100	938	};
alpar@100	939
alpar@100	940
alpar@100	941	public:
alpar@100	942
alpar@100	943
deba@139	944	/// \brief Constructor for the GraphCopy.
alpar@100	945	///
deba@139	946	/// It copies the content of the \c _from graph into the
deba@139	947	/// \c _to graph.
deba@139	948	GraphCopy(To& to, const From& from)
deba@139	949	: _from(from), _to(to) {}
alpar@100	950
deba@139	951	/// \brief Destructor of the GraphCopy
alpar@100	952	///
deba@139	953	/// Destructor of the GraphCopy
alpar@100	954	~GraphCopy() {
deba@139	955	for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139	956	delete _node_maps[i];
alpar@100	957	}
deba@139	958	for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139	959	delete _arc_maps[i];
alpar@100	960	}
deba@139	961	for (int i = 0; i < int(_edge_maps.size()); ++i) {
deba@139	962	delete _edge_maps[i];
alpar@100	963	}
alpar@100	964
alpar@100	965	}
alpar@100	966
alpar@100	967	/// \brief Copies the node references into the given map.
alpar@100	968	///
alpar@100	969	/// Copies the node references into the given map.
alpar@100	970	template <typename NodeRef>
alpar@100	971	GraphCopy& nodeRef(NodeRef& map) {
deba@139	972	_node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
deba@139	973	NodeRefMap, NodeRef>(map));
alpar@100	974	return *this;
alpar@100	975	}
alpar@100	976
alpar@100	977	/// \brief Copies the node cross references into the given map.
alpar@100	978	///
alpar@100	979	/// Copies the node cross references (reverse references) into
alpar@100	980	/// the given map.
alpar@100	981	template <typename NodeCrossRef>
alpar@100	982	GraphCopy& nodeCrossRef(NodeCrossRef& map) {
deba@139	983	_node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
deba@139	984	NodeRefMap, NodeCrossRef>(map));
alpar@100	985	return *this;
alpar@100	986	}
alpar@100	987
alpar@100	988	/// \brief Make copy of the given map.
alpar@100	989	///
deba@139	990	/// Makes copy of the given map for the newly created graph.
deba@139	991	/// The new map's key type is the to graph's node type,
deba@139	992	/// and the copied map's key type is the from graph's node
alpar@100	993	/// type.
alpar@100	994	template <typename ToMap, typename FromMap>
alpar@100	995	GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
deba@139	996	_node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
deba@139	997	NodeRefMap, ToMap, FromMap>(tmap, map));
alpar@100	998	return *this;
alpar@100	999	}
alpar@100	1000
alpar@100	1001	/// \brief Make a copy of the given node.
alpar@100	1002	///
alpar@100	1003	/// Make a copy of the given node.
alpar@100	1004	GraphCopy& node(TNode& tnode, const Node& snode) {
deba@139	1005	_node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
deba@139	1006	NodeRefMap, TNode>(tnode, snode));
alpar@100	1007	return *this;
alpar@100	1008	}
alpar@100	1009
alpar@100	1010	/// \brief Copies the arc references into the given map.
alpar@100	1011	///
alpar@100	1012	/// Copies the arc references into the given map.
alpar@100	1013	template <typename ArcRef>
alpar@100	1014	GraphCopy& arcRef(ArcRef& map) {
deba@139	1015	_arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
deba@139	1016	ArcRefMap, ArcRef>(map));
alpar@100	1017	return *this;
alpar@100	1018	}
alpar@100	1019
alpar@100	1020	/// \brief Copies the arc cross references into the given map.
alpar@100	1021	///
alpar@100	1022	/// Copies the arc cross references (reverse references) into
alpar@100	1023	/// the given map.
alpar@100	1024	template <typename ArcCrossRef>
alpar@100	1025	GraphCopy& arcCrossRef(ArcCrossRef& map) {
deba@139	1026	_arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
deba@139	1027	ArcRefMap, ArcCrossRef>(map));
alpar@100	1028	return *this;
alpar@100	1029	}
alpar@100	1030
alpar@100	1031	/// \brief Make copy of the given map.
alpar@100	1032	///
deba@139	1033	/// Makes copy of the given map for the newly created graph.
deba@139	1034	/// The new map's key type is the to graph's arc type,
deba@139	1035	/// and the copied map's key type is the from graph's arc
alpar@100	1036	/// type.
alpar@100	1037	template <typename ToMap, typename FromMap>
alpar@100	1038	GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
deba@139	1039	_arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
deba@139	1040	ArcRefMap, ToMap, FromMap>(tmap, map));
alpar@100	1041	return *this;
alpar@100	1042	}
alpar@100	1043
alpar@100	1044	/// \brief Make a copy of the given arc.
alpar@100	1045	///
alpar@100	1046	/// Make a copy of the given arc.
alpar@100	1047	GraphCopy& arc(TArc& tarc, const Arc& sarc) {
deba@139	1048	_arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
deba@139	1049	ArcRefMap, TArc>(tarc, sarc));
alpar@100	1050	return *this;
alpar@100	1051	}
alpar@100	1052
alpar@100	1053	/// \brief Copies the edge references into the given map.
alpar@100	1054	///
alpar@100	1055	/// Copies the edge references into the given map.
alpar@100	1056	template <typename EdgeRef>
alpar@100	1057	GraphCopy& edgeRef(EdgeRef& map) {
deba@139	1058	_edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
deba@139	1059	EdgeRefMap, EdgeRef>(map));
alpar@100	1060	return *this;
alpar@100	1061	}
alpar@100	1062
alpar@100	1063	/// \brief Copies the edge cross references into the given map.
alpar@100	1064	///
alpar@100	1065	/// Copies the edge cross references (reverse
alpar@100	1066	/// references) into the given map.
alpar@100	1067	template <typename EdgeCrossRef>
alpar@100	1068	GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
deba@139	1069	_edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
deba@139	1070	Edge, EdgeRefMap, EdgeCrossRef>(map));
alpar@100	1071	return *this;
alpar@100	1072	}
alpar@100	1073
alpar@100	1074	/// \brief Make copy of the given map.
alpar@100	1075	///
deba@139	1076	/// Makes copy of the given map for the newly created graph.
deba@139	1077	/// The new map's key type is the to graph's edge type,
deba@139	1078	/// and the copied map's key type is the from graph's edge
alpar@100	1079	/// type.
alpar@100	1080	template <typename ToMap, typename FromMap>
alpar@100	1081	GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
deba@139	1082	_edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
deba@139	1083	EdgeRefMap, ToMap, FromMap>(tmap, map));
alpar@100	1084	return *this;
alpar@100	1085	}
alpar@100	1086
alpar@100	1087	/// \brief Make a copy of the given edge.
alpar@100	1088	///
alpar@100	1089	/// Make a copy of the given edge.
alpar@100	1090	GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
deba@139	1091	_edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
deba@139	1092	EdgeRefMap, TEdge>(tedge, sedge));
alpar@100	1093	return *this;
alpar@100	1094	}
alpar@100	1095
alpar@100	1096	/// \brief Executes the copies.
alpar@100	1097	///
alpar@100	1098	/// Executes the copies.
alpar@100	1099	void run() {
deba@139	1100	NodeRefMap nodeRefMap(_from);
deba@139	1101	EdgeRefMap edgeRefMap(_from);
deba@139	1102	ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
deba@139	1103	_graph_utils_bits::GraphCopySelector<To>::
deba@139	1104	copy(_to, _from, nodeRefMap, edgeRefMap);
deba@139	1105	for (int i = 0; i < int(_node_maps.size()); ++i) {
deba@139	1106	_node_maps[i]->copy(_from, nodeRefMap);
alpar@100	1107	}
deba@139	1108	for (int i = 0; i < int(_edge_maps.size()); ++i) {
deba@139	1109	_edge_maps[i]->copy(_from, edgeRefMap);
alpar@100	1110	}
deba@139	1111	for (int i = 0; i < int(_arc_maps.size()); ++i) {
deba@139	1112	_arc_maps[i]->copy(_from, arcRefMap);
alpar@100	1113	}
alpar@100	1114	}
alpar@100	1115
alpar@100	1116	private:
alpar@100	1117
deba@139	1118	const From& _from;
deba@139	1119	To& _to;
alpar@100	1120
deba@139	1121	std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
deba@139	1122	_node_maps;
alpar@100	1123
deba@139	1124	std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
deba@139	1125	_arc_maps;
alpar@100	1126
deba@139	1127	std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
deba@139	1128	_edge_maps;
alpar@100	1129
alpar@100	1130	};
alpar@100	1131
deba@139	1132	/// \brief Copy a graph to another graph.
alpar@100	1133	///
deba@139	1134	/// Copy a graph to another graph. The complete usage of the
deba@139	1135	/// function is detailed in the GraphCopy class, but a short
deba@139	1136	/// example shows a basic work:
alpar@100	1137	///\code
alpar@100	1138	/// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
alpar@100	1139	///\endcode
alpar@100	1140	///
alpar@100	1141	/// After the copy the \c nr map will contain the mapping from the
deba@139	1142	/// nodes of the \c from graph to the nodes of the \c to graph and
deba@139	1143	/// \c ecr will contain the mapping from the arcs of the \c to graph
deba@139	1144	/// to the arcs of the \c from graph.
alpar@100	1145	///
alpar@100	1146	/// \see GraphCopy
alpar@100	1147	template <typename To, typename From>
alpar@100	1148	GraphCopy<To, From>
alpar@100	1149	copyGraph(To& to, const From& from) {
alpar@100	1150	return GraphCopy<To, From>(to, from);
alpar@100	1151	}
alpar@100	1152
alpar@100	1153	/// @}
alpar@100	1154
deba@139	1155	/// \addtogroup graph_maps
alpar@100	1156	/// @{
alpar@100	1157
deba@139	1158	/// Provides an immutable and unique id for each item in the graph.
alpar@100	1159
alpar@100	1160	/// The IdMap class provides a unique and immutable id for each item of the
deba@139	1161	/// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
alpar@100	1162	/// different items (nodes) get different ids <li>\b immutable: the id of an
alpar@100	1163	/// item (node) does not change (even if you delete other nodes). </ul>
alpar@100	1164	/// Through this map you get access (i.e. can read) the inner id values of
deba@139	1165	/// the items stored in the graph. This map can be inverted with its member
deba@139	1166	/// class \c InverseMap or with the \c operator() member.
alpar@100	1167	///
deba@139	1168	template <typename _Graph, typename _Item>
alpar@100	1169	class IdMap {
alpar@100	1170	public:
deba@139	1171	typedef _Graph Graph;
alpar@100	1172	typedef int Value;
alpar@100	1173	typedef _Item Item;
alpar@100	1174	typedef _Item Key;
alpar@100	1175
alpar@100	1176	/// \brief Constructor.
alpar@100	1177	///
alpar@100	1178	/// Constructor of the map.
deba@139	1179	explicit IdMap(const Graph& graph) : _graph(&graph) {}
alpar@100	1180
alpar@100	1181	/// \brief Gives back the \e id of the item.
alpar@100	1182	///
alpar@100	1183	/// Gives back the immutable and unique \e id of the item.
deba@139	1184	int operator[](const Item& item) const { return _graph->id(item);}
alpar@100	1185
alpar@100	1186	/// \brief Gives back the item by its id.
alpar@100	1187	///
alpar@100	1188	/// Gives back the item by its id.
deba@139	1189	Item operator()(int id) { return _graph->fromId(id, Item()); }
alpar@100	1190
alpar@100	1191	private:
deba@139	1192	const Graph* _graph;
alpar@100	1193
alpar@100	1194	public:
alpar@100	1195
alpar@100	1196	/// \brief The class represents the inverse of its owner (IdMap).
alpar@100	1197	///
alpar@100	1198	/// The class represents the inverse of its owner (IdMap).
alpar@100	1199	/// \see inverse()
alpar@100	1200	class InverseMap {
alpar@100	1201	public:
alpar@100	1202
alpar@100	1203	/// \brief Constructor.
alpar@100	1204	///
alpar@100	1205	/// Constructor for creating an id-to-item map.
deba@139	1206	explicit InverseMap(const Graph& graph) : _graph(&graph) {}
alpar@100	1207
alpar@100	1208	/// \brief Constructor.
alpar@100	1209	///
alpar@100	1210	/// Constructor for creating an id-to-item map.
deba@139	1211	explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
alpar@100	1212
alpar@100	1213	/// \brief Gives back the given item from its id.
alpar@100	1214	///
alpar@100	1215	/// Gives back the given item from its id.
alpar@100	1216	///
deba@139	1217	Item operator[](int id) const { return _graph->fromId(id, Item());}
alpar@100	1218
alpar@100	1219	private:
deba@139	1220	const Graph* _graph;
alpar@100	1221	};
alpar@100	1222
alpar@100	1223	/// \brief Gives back the inverse of the map.
alpar@100	1224	///
alpar@100	1225	/// Gives back the inverse of the IdMap.
deba@139	1226	InverseMap inverse() const { return InverseMap(*_graph);}
alpar@100	1227
alpar@100	1228	};
alpar@100	1229
alpar@100	1230
deba@139	1231	/// \brief General invertable graph-map type.
alpar@100	1232
deba@139	1233	/// This type provides simple invertable graph-maps.
alpar@100	1234	/// The InvertableMap wraps an arbitrary ReadWriteMap
alpar@100	1235	/// and if a key is set to a new value then store it
alpar@100	1236	/// in the inverse map.
alpar@100	1237	///
alpar@100	1238	/// The values of the map can be accessed
alpar@100	1239	/// with stl compatible forward iterator.
alpar@100	1240	///
kpeter@157	1241	/// \tparam _Graph The graph type.
kpeter@157	1242	/// \tparam _Item The item type of the graph.
kpeter@157	1243	/// \tparam _Value The value type of the map.
alpar@100	1244	///
alpar@100	1245	/// \see IterableValueMap
deba@139	1246	template <typename _Graph, typename _Item, typename _Value>
deba@139	1247	class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
alpar@100	1248	private:
alpar@100	1249
deba@139	1250	typedef DefaultMap<_Graph, _Item, _Value> Map;
deba@139	1251	typedef _Graph Graph;
alpar@100	1252
alpar@100	1253	typedef std::map<_Value, _Item> Container;
deba@139	1254	Container _inv_map;
alpar@100	1255
alpar@100	1256	public:
alpar@100	1257
alpar@100	1258	/// The key type of InvertableMap (Node, Arc, Edge).
alpar@100	1259	typedef typename Map::Key Key;
alpar@100	1260	/// The value type of the InvertableMap.
alpar@100	1261	typedef typename Map::Value Value;
alpar@100	1262
alpar@100	1263
alpar@100	1264
alpar@100	1265	/// \brief Constructor.
alpar@100	1266	///
deba@139	1267	/// Construct a new InvertableMap for the graph.
alpar@100	1268	///
deba@139	1269	explicit InvertableMap(const Graph& graph) : Map(graph) {}
alpar@100	1270
alpar@100	1271	/// \brief Forward iterator for values.
alpar@100	1272	///
alpar@100	1273	/// This iterator is an stl compatible forward
alpar@100	1274	/// iterator on the values of the map. The values can
alpar@100	1275	/// be accessed in the [beginValue, endValue) range.
alpar@100	1276	///
alpar@100	1277	class ValueIterator
alpar@100	1278	: public std::iterator<std::forward_iterator_tag, Value> {
alpar@100	1279	friend class InvertableMap;
alpar@100	1280	private:
alpar@100	1281	ValueIterator(typename Container::const_iterator _it)
alpar@100	1282	: it(_it) {}
alpar@100	1283	public:
alpar@100	1284
alpar@100	1285	ValueIterator() {}
alpar@100	1286
alpar@100	1287	ValueIterator& operator++() { ++it; return *this; }
alpar@100	1288	ValueIterator operator++(int) {
alpar@100	1289	ValueIterator tmp(*this);
alpar@100	1290	operator++();
alpar@100	1291	return tmp;
alpar@100	1292	}
alpar@100	1293
alpar@100	1294	const Value& operator*() const { return it->first; }
alpar@100	1295	const Value* operator->() const { return &(it->first); }
alpar@100	1296
alpar@100	1297	bool operator==(ValueIterator jt) const { return it == jt.it; }
alpar@100	1298	bool operator!=(ValueIterator jt) const { return it != jt.it; }
alpar@100	1299
alpar@100	1300	private:
alpar@100	1301	typename Container::const_iterator it;
alpar@100	1302	};
alpar@100	1303
alpar@100	1304	/// \brief Returns an iterator to the first value.
alpar@100	1305	///
alpar@100	1306	/// Returns an stl compatible iterator to the
alpar@100	1307	/// first value of the map. The values of the
alpar@100	1308	/// map can be accessed in the [beginValue, endValue)
alpar@100	1309	/// range.
alpar@100	1310	ValueIterator beginValue() const {
deba@139	1311	return ValueIterator(_inv_map.begin());
alpar@100	1312	}
alpar@100	1313
alpar@100	1314	/// \brief Returns an iterator after the last value.
alpar@100	1315	///
alpar@100	1316	/// Returns an stl compatible iterator after the
alpar@100	1317	/// last value of the map. The values of the
alpar@100	1318	/// map can be accessed in the [beginValue, endValue)
alpar@100	1319	/// range.
alpar@100	1320	ValueIterator endValue() const {
deba@139	1321	return ValueIterator(_inv_map.end());
alpar@100	1322	}
alpar@100	1323
alpar@100	1324	/// \brief The setter function of the map.
alpar@100	1325	///
alpar@100	1326	/// Sets the mapped value.
alpar@100	1327	void set(const Key& key, const Value& val) {
alpar@100	1328	Value oldval = Map::operator[](key);
deba@139	1329	typename Container::iterator it = _inv_map.find(oldval);
deba@139	1330	if (it != _inv_map.end() && it->second == key) {
deba@139	1331	_inv_map.erase(it);
alpar@100	1332	}
deba@139	1333	_inv_map.insert(make_pair(val, key));
alpar@100	1334	Map::set(key, val);
alpar@100	1335	}
alpar@100	1336
alpar@100	1337	/// \brief The getter function of the map.
alpar@100	1338	///
alpar@100	1339	/// It gives back the value associated with the key.
alpar@100	1340	typename MapTraits<Map>::ConstReturnValue
alpar@100	1341	operator[](const Key& key) const {
alpar@100	1342	return Map::operator[](key);
alpar@100	1343	}
alpar@100	1344
alpar@100	1345	/// \brief Gives back the item by its value.
alpar@100	1346	///
alpar@100	1347	/// Gives back the item by its value.
alpar@100	1348	Key operator()(const Value& key) const {
deba@139	1349	typename Container::const_iterator it = _inv_map.find(key);
deba@139	1350	return it != _inv_map.end() ? it->second : INVALID;
alpar@100	1351	}
alpar@100	1352
alpar@100	1353	protected:
alpar@100	1354
alpar@100	1355	/// \brief Erase the key from the map.
alpar@100	1356	///
alpar@100	1357	/// Erase the key to the map. It is called by the
alpar@100	1358	/// \c AlterationNotifier.
alpar@100	1359	virtual void erase(const Key& key) {
alpar@100	1360	Value val = Map::operator[](key);
deba@139	1361	typename Container::iterator it = _inv_map.find(val);
deba@139	1362	if (it != _inv_map.end() && it->second == key) {
deba@139	1363	_inv_map.erase(it);
alpar@100	1364	}
alpar@100	1365	Map::erase(key);
alpar@100	1366	}
alpar@100	1367
alpar@100	1368	/// \brief Erase more keys from the map.
alpar@100	1369	///
alpar@100	1370	/// Erase more keys from the map. It is called by the
alpar@100	1371	/// \c AlterationNotifier.
alpar@100	1372	virtual void erase(const std::vector<Key>& keys) {
alpar@100	1373	for (int i = 0; i < int(keys.size()); ++i) {
alpar@100	1374	Value val = Map::operator[](keys[i]);
deba@139	1375	typename Container::iterator it = _inv_map.find(val);
deba@139	1376	if (it != _inv_map.end() && it->second == keys[i]) {
deba@139	1377	_inv_map.erase(it);
alpar@100	1378	}
alpar@100	1379	}
alpar@100	1380	Map::erase(keys);
alpar@100	1381	}
alpar@100	1382
alpar@100	1383	/// \brief Clear the keys from the map and inverse map.
alpar@100	1384	///
alpar@100	1385	/// Clear the keys from the map and inverse map. It is called by the
alpar@100	1386	/// \c AlterationNotifier.
alpar@100	1387	virtual void clear() {
deba@139	1388	_inv_map.clear();
alpar@100	1389	Map::clear();
alpar@100	1390	}
alpar@100	1391
alpar@100	1392	public:
alpar@100	1393
alpar@100	1394	/// \brief The inverse map type.
alpar@100	1395	///
alpar@100	1396	/// The inverse of this map. The subscript operator of the map
alpar@100	1397	/// gives back always the item what was last assigned to the value.
alpar@100	1398	class InverseMap {
alpar@100	1399	public:
alpar@100	1400	/// \brief Constructor of the InverseMap.
alpar@100	1401	///
alpar@100	1402	/// Constructor of the InverseMap.
deba@139	1403	explicit InverseMap(const InvertableMap& inverted)
deba@139	1404	: _inverted(inverted) {}
alpar@100	1405
alpar@100	1406	/// The value type of the InverseMap.
alpar@100	1407	typedef typename InvertableMap::Key Value;
alpar@100	1408	/// The key type of the InverseMap.
alpar@100	1409	typedef typename InvertableMap::Value Key;
alpar@100	1410
alpar@100	1411	/// \brief Subscript operator.
alpar@100	1412	///
alpar@100	1413	/// Subscript operator. It gives back always the item
alpar@100	1414	/// what was last assigned to the value.
alpar@100	1415	Value operator[](const Key& key) const {
deba@139	1416	return _inverted(key);
alpar@100	1417	}
alpar@100	1418
alpar@100	1419	private:
deba@139	1420	const InvertableMap& _inverted;
alpar@100	1421	};
alpar@100	1422
alpar@100	1423	/// \brief It gives back the just readable inverse map.
alpar@100	1424	///
alpar@100	1425	/// It gives back the just readable inverse map.
alpar@100	1426	InverseMap inverse() const {
alpar@100	1427	return InverseMap(*this);
alpar@100	1428	}
alpar@100	1429
alpar@100	1430
alpar@100	1431
alpar@100	1432	};
alpar@100	1433
alpar@100	1434	/// \brief Provides a mutable, continuous and unique descriptor for each
deba@139	1435	/// item in the graph.
alpar@100	1436	///
alpar@100	1437	/// The DescriptorMap class provides a unique and continuous (but mutable)
alpar@100	1438	/// descriptor (id) for each item of the same type (e.g. node) in the
deba@139	1439	/// graph. This id is <ul><li>\b unique: different items (nodes) get
alpar@100	1440	/// different ids <li>\b continuous: the range of the ids is the set of
alpar@100	1441	/// integers between 0 and \c n-1, where \c n is the number of the items of
alpar@100	1442	/// this type (e.g. nodes) (so the id of a node can change if you delete an
alpar@100	1443	/// other node, i.e. this id is mutable). </ul> This map can be inverted
deba@139	1444	/// with its member class \c InverseMap, or with the \c operator() member.
alpar@100	1445	///
kpeter@157	1446	/// \tparam _Graph The graph class the \c DescriptorMap belongs to.
kpeter@157	1447	/// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
alpar@100	1448	/// Edge.
deba@139	1449	template <typename _Graph, typename _Item>
deba@139	1450	class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
alpar@100	1451
alpar@100	1452	typedef _Item Item;
deba@139	1453	typedef DefaultMap<_Graph, _Item, int> Map;
alpar@100	1454
alpar@100	1455	public:
deba@139	1456	/// The graph class of DescriptorMap.
deba@139	1457	typedef _Graph Graph;
alpar@100	1458
alpar@100	1459	/// The key type of DescriptorMap (Node, Arc, Edge).
alpar@100	1460	typedef typename Map::Key Key;
alpar@100	1461	/// The value type of DescriptorMap.
alpar@100	1462	typedef typename Map::Value Value;
alpar@100	1463
alpar@100	1464	/// \brief Constructor.
alpar@100	1465	///
alpar@100	1466	/// Constructor for descriptor map.
deba@139	1467	explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
alpar@100	1468	Item it;
alpar@100	1469	const typename Map::Notifier* nf = Map::notifier();
alpar@100	1470	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@139	1471	Map::set(it, _inv_map.size());
deba@139	1472	_inv_map.push_back(it);
alpar@100	1473	}
alpar@100	1474	}
alpar@100	1475
alpar@100	1476	protected:
alpar@100	1477
alpar@100	1478	/// \brief Add a new key to the map.
alpar@100	1479	///
alpar@100	1480	/// Add a new key to the map. It is called by the
alpar@100	1481	/// \c AlterationNotifier.
alpar@100	1482	virtual void add(const Item& item) {
alpar@100	1483	Map::add(item);
deba@139	1484	Map::set(item, _inv_map.size());
deba@139	1485	_inv_map.push_back(item);
alpar@100	1486	}
alpar@100	1487
alpar@100	1488	/// \brief Add more new keys to the map.
alpar@100	1489	///
alpar@100	1490	/// Add more new keys to the map. It is called by the
alpar@100	1491	/// \c AlterationNotifier.
alpar@100	1492	virtual void add(const std::vector<Item>& items) {
alpar@100	1493	Map::add(items);
alpar@100	1494	for (int i = 0; i < int(items.size()); ++i) {
deba@139	1495	Map::set(items[i], _inv_map.size());
deba@139	1496	_inv_map.push_back(items[i]);
alpar@100	1497	}
alpar@100	1498	}
alpar@100	1499
alpar@100	1500	/// \brief Erase the key from the map.
alpar@100	1501	///
alpar@100	1502	/// Erase the key from the map. It is called by the
alpar@100	1503	/// \c AlterationNotifier.
alpar@100	1504	virtual void erase(const Item& item) {
deba@139	1505	Map::set(_inv_map.back(), Map::operator[](item));
deba@139	1506	_inv_map[Map::operator[](item)] = _inv_map.back();
deba@139	1507	_inv_map.pop_back();
alpar@100	1508	Map::erase(item);
alpar@100	1509	}
alpar@100	1510
alpar@100	1511	/// \brief Erase more keys from the map.
alpar@100	1512	///
alpar@100	1513	/// Erase more keys from the map. It is called by the
alpar@100	1514	/// \c AlterationNotifier.
alpar@100	1515	virtual void erase(const std::vector<Item>& items) {
alpar@100	1516	for (int i = 0; i < int(items.size()); ++i) {
deba@139	1517	Map::set(_inv_map.back(), Map::operator[](items[i]));
deba@139	1518	_inv_map[Map::operator[](items[i])] = _inv_map.back();
deba@139	1519	_inv_map.pop_back();
alpar@100	1520	}
alpar@100	1521	Map::erase(items);
alpar@100	1522	}
alpar@100	1523
alpar@100	1524	/// \brief Build the unique map.
alpar@100	1525	///
alpar@100	1526	/// Build the unique map. It is called by the
alpar@100	1527	/// \c AlterationNotifier.
alpar@100	1528	virtual void build() {
alpar@100	1529	Map::build();
alpar@100	1530	Item it;
alpar@100	1531	const typename Map::Notifier* nf = Map::notifier();
alpar@100	1532	for (nf->first(it); it != INVALID; nf->next(it)) {
deba@139	1533	Map::set(it, _inv_map.size());
deba@139	1534	_inv_map.push_back(it);
alpar@100	1535	}
alpar@100	1536	}
alpar@100	1537
alpar@100	1538	/// \brief Clear the keys from the map.
alpar@100	1539	///
alpar@100	1540	/// Clear the keys from the map. It is called by the
alpar@100	1541	/// \c AlterationNotifier.
alpar@100	1542	virtual void clear() {
deba@139	1543	_inv_map.clear();
alpar@100	1544	Map::clear();
alpar@100	1545	}
alpar@100	1546
alpar@100	1547	public:
alpar@100	1548
alpar@100	1549	/// \brief Returns the maximal value plus one.
alpar@100	1550	///
alpar@100	1551	/// Returns the maximal value plus one in the map.
alpar@100	1552	unsigned int size() const {
deba@139	1553	return _inv_map.size();
alpar@100	1554	}
alpar@100	1555
alpar@100	1556	/// \brief Swaps the position of the two items in the map.
alpar@100	1557	///
alpar@100	1558	/// Swaps the position of the two items in the map.
alpar@100	1559	void swap(const Item& p, const Item& q) {
alpar@100	1560	int pi = Map::operator[](p);
alpar@100	1561	int qi = Map::operator[](q);
alpar@100	1562	Map::set(p, qi);
deba@139	1563	_inv_map[qi] = p;
alpar@100	1564	Map::set(q, pi);
deba@139	1565	_inv_map[pi] = q;
alpar@100	1566	}
alpar@100	1567
alpar@100	1568	/// \brief Gives back the \e descriptor of the item.
alpar@100	1569	///
alpar@100	1570	/// Gives back the mutable and unique \e descriptor of the map.
alpar@100	1571	int operator[](const Item& item) const {
alpar@100	1572	return Map::operator[](item);
alpar@100	1573	}
alpar@100	1574
alpar@100	1575	/// \brief Gives back the item by its descriptor.
alpar@100	1576	///
alpar@100	1577	/// Gives back th item by its descriptor.
alpar@100	1578	Item operator()(int id) const {
deba@139	1579	return _inv_map[id];
alpar@100	1580	}
alpar@100	1581
alpar@100	1582	private:
alpar@100	1583
alpar@100	1584	typedef std::vector<Item> Container;
deba@139	1585	Container _inv_map;
alpar@100	1586
alpar@100	1587	public:
alpar@100	1588	/// \brief The inverse map type of DescriptorMap.
alpar@100	1589	///
alpar@100	1590	/// The inverse map type of DescriptorMap.
alpar@100	1591	class InverseMap {
alpar@100	1592	public:
alpar@100	1593	/// \brief Constructor of the InverseMap.
alpar@100	1594	///
alpar@100	1595	/// Constructor of the InverseMap.
deba@139	1596	explicit InverseMap(const DescriptorMap& inverted)
deba@139	1597	: _inverted(inverted) {}
alpar@100	1598
alpar@100	1599
alpar@100	1600	/// The value type of the InverseMap.
alpar@100	1601	typedef typename DescriptorMap::Key Value;
alpar@100	1602	/// The key type of the InverseMap.
alpar@100	1603	typedef typename DescriptorMap::Value Key;
alpar@100	1604
alpar@100	1605	/// \brief Subscript operator.
alpar@100	1606	///
alpar@100	1607	/// Subscript operator. It gives back the item
alpar@100	1608	/// that the descriptor belongs to currently.
alpar@100	1609	Value operator[](const Key& key) const {
deba@139	1610	return _inverted(key);
alpar@100	1611	}
alpar@100	1612
alpar@100	1613	/// \brief Size of the map.
alpar@100	1614	///
alpar@100	1615	/// Returns the size of the map.
alpar@100	1616	unsigned int size() const {
deba@139	1617	return _inverted.size();
alpar@100	1618	}
alpar@100	1619
alpar@100	1620	private:
deba@139	1621	const DescriptorMap& _inverted;
alpar@100	1622	};
alpar@100	1623
alpar@100	1624	/// \brief Gives back the inverse of the map.
alpar@100	1625	///
alpar@100	1626	/// Gives back the inverse of the map.
alpar@100	1627	const InverseMap inverse() const {
alpar@100	1628	return InverseMap(*this);
alpar@100	1629	}
alpar@100	1630	};
alpar@100	1631
alpar@100	1632	/// \brief Returns the source of the given arc.
alpar@100	1633	///
alpar@100	1634	/// The SourceMap gives back the source Node of the given arc.
alpar@100	1635	/// \see TargetMap
alpar@100	1636	template <typename Digraph>
alpar@100	1637	class SourceMap {
alpar@100	1638	public:
alpar@100	1639
alpar@100	1640	typedef typename Digraph::Node Value;
alpar@100	1641	typedef typename Digraph::Arc Key;
alpar@100	1642
alpar@100	1643	/// \brief Constructor
alpar@100	1644	///
alpar@100	1645	/// Constructor
alpar@100	1646	/// \param _digraph The digraph that the map belongs to.
deba@139	1647	explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
alpar@100	1648
alpar@100	1649	/// \brief The subscript operator.
alpar@100	1650	///
alpar@100	1651	/// The subscript operator.
alpar@100	1652	/// \param arc The arc
alpar@100	1653	/// \return The source of the arc
alpar@100	1654	Value operator[](const Key& arc) const {
deba@139	1655	return _digraph.source(arc);
alpar@100	1656	}
alpar@100	1657
alpar@100	1658	private:
deba@139	1659	const Digraph& _digraph;
alpar@100	1660	};
alpar@100	1661
alpar@100	1662	/// \brief Returns a \ref SourceMap class.
alpar@100	1663	///
alpar@100	1664	/// This function just returns an \ref SourceMap class.
alpar@100	1665	/// \relates SourceMap
alpar@100	1666	template <typename Digraph>
alpar@100	1667	inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
alpar@100	1668	return SourceMap<Digraph>(digraph);
alpar@100	1669	}
alpar@100	1670
alpar@100	1671	/// \brief Returns the target of the given arc.
alpar@100	1672	///
alpar@100	1673	/// The TargetMap gives back the target Node of the given arc.
alpar@100	1674	/// \see SourceMap
alpar@100	1675	template <typename Digraph>
alpar@100	1676	class TargetMap {
alpar@100	1677	public:
alpar@100	1678
alpar@100	1679	typedef typename Digraph::Node Value;
alpar@100	1680	typedef typename Digraph::Arc Key;
alpar@100	1681
alpar@100	1682	/// \brief Constructor
alpar@100	1683	///
alpar@100	1684	/// Constructor
alpar@100	1685	/// \param _digraph The digraph that the map belongs to.
deba@139	1686	explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
alpar@100	1687
alpar@100	1688	/// \brief The subscript operator.
alpar@100	1689	///
alpar@100	1690	/// The subscript operator.
alpar@100	1691	/// \param e The arc
alpar@100	1692	/// \return The target of the arc
alpar@100	1693	Value operator[](const Key& e) const {
deba@139	1694	return _digraph.target(e);
alpar@100	1695	}
alpar@100	1696
alpar@100	1697	private:
deba@139	1698	const Digraph& _digraph;
alpar@100	1699	};
alpar@100	1700
alpar@100	1701	/// \brief Returns a \ref TargetMap class.
alpar@100	1702	///
alpar@100	1703	/// This function just returns a \ref TargetMap class.
alpar@100	1704	/// \relates TargetMap
alpar@100	1705	template <typename Digraph>
alpar@100	1706	inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
alpar@100	1707	return TargetMap<Digraph>(digraph);
alpar@100	1708	}
alpar@100	1709
alpar@100	1710	/// \brief Returns the "forward" directed arc view of an edge.
alpar@100	1711	///
alpar@100	1712	/// Returns the "forward" directed arc view of an edge.
alpar@100	1713	/// \see BackwardMap
deba@139	1714	template <typename Graph>
alpar@100	1715	class ForwardMap {
alpar@100	1716	public:
alpar@100	1717
deba@139	1718	typedef typename Graph::Arc Value;
deba@139	1719	typedef typename Graph::Edge Key;
alpar@100	1720
alpar@100	1721	/// \brief Constructor
alpar@100	1722	///
alpar@100	1723	/// Constructor
deba@139	1724	/// \param _graph The graph that the map belongs to.
deba@139	1725	explicit ForwardMap(const Graph& graph) : _graph(graph) {}
alpar@100	1726
alpar@100	1727	/// \brief The subscript operator.
alpar@100	1728	///
alpar@100	1729	/// The subscript operator.
alpar@100	1730	/// \param key An edge
alpar@100	1731	/// \return The "forward" directed arc view of edge
alpar@100	1732	Value operator[](const Key& key) const {
deba@139	1733	return _graph.direct(key, true);
alpar@100	1734	}
alpar@100	1735
alpar@100	1736	private:
deba@139	1737	const Graph& _graph;
alpar@100	1738	};
alpar@100	1739
alpar@100	1740	/// \brief Returns a \ref ForwardMap class.
alpar@100	1741	///
alpar@100	1742	/// This function just returns an \ref ForwardMap class.
alpar@100	1743	/// \relates ForwardMap
deba@139	1744	template <typename Graph>
deba@139	1745	inline ForwardMap<Graph> forwardMap(const Graph& graph) {
deba@139	1746	return ForwardMap<Graph>(graph);
alpar@100	1747	}
alpar@100	1748
alpar@100	1749	/// \brief Returns the "backward" directed arc view of an edge.
alpar@100	1750	///
alpar@100	1751	/// Returns the "backward" directed arc view of an edge.
alpar@100	1752	/// \see ForwardMap
deba@139	1753	template <typename Graph>
alpar@100	1754	class BackwardMap {
alpar@100	1755	public:
alpar@100	1756
deba@139	1757	typedef typename Graph::Arc Value;
deba@139	1758	typedef typename Graph::Edge Key;
alpar@100	1759
alpar@100	1760	/// \brief Constructor
alpar@100	1761	///
alpar@100	1762	/// Constructor
deba@139	1763	/// \param _graph The graph that the map belongs to.
deba@139	1764	explicit BackwardMap(const Graph& graph) : _graph(graph) {}
alpar@100	1765
alpar@100	1766	/// \brief The subscript operator.
alpar@100	1767	///
alpar@100	1768	/// The subscript operator.
alpar@100	1769	/// \param key An edge
alpar@100	1770	/// \return The "backward" directed arc view of edge
alpar@100	1771	Value operator[](const Key& key) const {
deba@139	1772	return _graph.direct(key, false);
alpar@100	1773	}
alpar@100	1774
alpar@100	1775	private:
deba@139	1776	const Graph& _graph;
alpar@100	1777	};
alpar@100	1778
alpar@100	1779	/// \brief Returns a \ref BackwardMap class
alpar@100	1780
alpar@100	1781	/// This function just returns a \ref BackwardMap class.
alpar@100	1782	/// \relates BackwardMap
deba@139	1783	template <typename Graph>
deba@139	1784	inline BackwardMap<Graph> backwardMap(const Graph& graph) {
deba@139	1785	return BackwardMap<Graph>(graph);
alpar@100	1786	}
alpar@100	1787
alpar@100	1788	/// \brief Potential difference map
alpar@100	1789	///
alpar@100	1790	/// If there is an potential map on the nodes then we
alpar@100	1791	/// can get an arc map as we get the substraction of the
alpar@100	1792	/// values of the target and source.
alpar@100	1793	template <typename Digraph, typename NodeMap>
alpar@100	1794	class PotentialDifferenceMap {
alpar@100	1795	public:
alpar@100	1796	typedef typename Digraph::Arc Key;
alpar@100	1797	typedef typename NodeMap::Value Value;
alpar@100	1798
alpar@100	1799	/// \brief Constructor
alpar@100	1800	///
alpar@100	1801	/// Contructor of the map
deba@139	1802	explicit PotentialDifferenceMap(const Digraph& digraph,
deba@139	1803	const NodeMap& potential)
deba@139	1804	: _digraph(digraph), _potential(potential) {}
alpar@100	1805
alpar@100	1806	/// \brief Const subscription operator
alpar@100	1807	///
alpar@100	1808	/// Const subscription operator
alpar@100	1809	Value operator[](const Key& arc) const {
deba@139	1810	return _potential[_digraph.target(arc)] -
deba@139	1811	_potential[_digraph.source(arc)];
alpar@100	1812	}
alpar@100	1813
alpar@100	1814	private:
deba@139	1815	const Digraph& _digraph;
deba@139	1816	const NodeMap& _potential;
alpar@100	1817	};
alpar@100	1818
alpar@100	1819	/// \brief Returns a PotentialDifferenceMap.
alpar@100	1820	///
alpar@100	1821	/// This function just returns a PotentialDifferenceMap.
alpar@100	1822	/// \relates PotentialDifferenceMap
alpar@100	1823	template <typename Digraph, typename NodeMap>
alpar@100	1824	PotentialDifferenceMap<Digraph, NodeMap>
alpar@100	1825	potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
alpar@100	1826	return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
alpar@100	1827	}
alpar@100	1828
alpar@100	1829	/// \brief Map of the node in-degrees.
alpar@100	1830	///
alpar@100	1831	/// This map returns the in-degree of a node. Once it is constructed,
alpar@100	1832	/// the degrees are stored in a standard NodeMap, so each query is done
alpar@100	1833	/// in constant time. On the other hand, the values are updated automatically
alpar@100	1834	/// whenever the digraph changes.
alpar@100	1835	///
alpar@100	1836	/// \warning Besides addNode() and addArc(), a digraph structure may provide
alpar@100	1837	/// alternative ways to modify the digraph. The correct behavior of InDegMap
alpar@100	1838	/// is not guarantied if these additional features are used. For example
alpar@100	1839	/// the functions \ref ListDigraph::changeSource() "changeSource()",
alpar@100	1840	/// \ref ListDigraph::changeTarget() "changeTarget()" and
alpar@100	1841	/// \ref ListDigraph::reverseArc() "reverseArc()"
alpar@100	1842	/// of \ref ListDigraph will \e not update the degree values correctly.
alpar@100	1843	///
alpar@100	1844	/// \sa OutDegMap
alpar@100	1845
alpar@100	1846	template <typename _Digraph>
alpar@100	1847	class InDegMap
alpar@100	1848	: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
alpar@100	1849	::ItemNotifier::ObserverBase {
alpar@100	1850
alpar@100	1851	public:
alpar@100	1852
alpar@100	1853	typedef _Digraph Digraph;
alpar@100	1854	typedef int Value;
alpar@100	1855	typedef typename Digraph::Node Key;
alpar@100	1856
deba@139	1857	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
alpar@100	1858	::ItemNotifier::ObserverBase Parent;
alpar@100	1859
alpar@100	1860	private:
alpar@100	1861
deba@139	1862	class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
alpar@100	1863	public:
alpar@100	1864
deba@139	1865	typedef DefaultMap<Digraph, Key, int> Parent;
alpar@100	1866
alpar@100	1867	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
alpar@100	1868
alpar@100	1869	virtual void add(const Key& key) {
alpar@100	1870	Parent::add(key);
alpar@100	1871	Parent::set(key, 0);
alpar@100	1872	}
alpar@100	1873
alpar@100	1874	virtual void add(const std::vector<Key>& keys) {
alpar@100	1875	Parent::add(keys);
alpar@100	1876	for (int i = 0; i < int(keys.size()); ++i) {
alpar@100	1877	Parent::set(keys[i], 0);
alpar@100	1878	}
alpar@100	1879	}
alpar@100	1880
alpar@100	1881	virtual void build() {
alpar@100	1882	Parent::build();
alpar@100	1883	Key it;
alpar@100	1884	typename Parent::Notifier* nf = Parent::notifier();
alpar@100	1885	for (nf->first(it); it != INVALID; nf->next(it)) {
alpar@100	1886	Parent::set(it, 0);
alpar@100	1887	}
alpar@100	1888	}
alpar@100	1889	};
alpar@100	1890
alpar@100	1891	public:
alpar@100	1892
alpar@100	1893	/// \brief Constructor.
alpar@100	1894	///
alpar@100	1895	/// Constructor for creating in-degree map.
deba@139	1896	explicit InDegMap(const Digraph& digraph)
deba@139	1897	: _digraph(digraph), _deg(digraph) {
deba@139	1898	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
alpar@100	1899
deba@139	1900	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	1901	_deg[it] = countInArcs(_digraph, it);
alpar@100	1902	}
alpar@100	1903	}
alpar@100	1904
alpar@100	1905	/// Gives back the in-degree of a Node.
alpar@100	1906	int operator[](const Key& key) const {
deba@139	1907	return _deg[key];
alpar@100	1908	}
alpar@100	1909
alpar@100	1910	protected:
alpar@100	1911
alpar@100	1912	typedef typename Digraph::Arc Arc;
alpar@100	1913
alpar@100	1914	virtual void add(const Arc& arc) {
deba@139	1915	++_deg[_digraph.target(arc)];
alpar@100	1916	}
alpar@100	1917
alpar@100	1918	virtual void add(const std::vector<Arc>& arcs) {
alpar@100	1919	for (int i = 0; i < int(arcs.size()); ++i) {
deba@139	1920	++_deg[_digraph.target(arcs[i])];
alpar@100	1921	}
alpar@100	1922	}
alpar@100	1923
alpar@100	1924	virtual void erase(const Arc& arc) {
deba@139	1925	--_deg[_digraph.target(arc)];
alpar@100	1926	}
alpar@100	1927
alpar@100	1928	virtual void erase(const std::vector<Arc>& arcs) {
alpar@100	1929	for (int i = 0; i < int(arcs.size()); ++i) {
deba@139	1930	--_deg[_digraph.target(arcs[i])];
alpar@100	1931	}
alpar@100	1932	}
alpar@100	1933
alpar@100	1934	virtual void build() {
deba@139	1935	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	1936	_deg[it] = countInArcs(_digraph, it);
alpar@100	1937	}
alpar@100	1938	}
alpar@100	1939
alpar@100	1940	virtual void clear() {
deba@139	1941	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	1942	_deg[it] = 0;
alpar@100	1943	}
alpar@100	1944	}
alpar@100	1945	private:
alpar@100	1946
deba@139	1947	const Digraph& _digraph;
deba@139	1948	AutoNodeMap _deg;
alpar@100	1949	};
alpar@100	1950
alpar@100	1951	/// \brief Map of the node out-degrees.
alpar@100	1952	///
alpar@100	1953	/// This map returns the out-degree of a node. Once it is constructed,
alpar@100	1954	/// the degrees are stored in a standard NodeMap, so each query is done
alpar@100	1955	/// in constant time. On the other hand, the values are updated automatically
alpar@100	1956	/// whenever the digraph changes.
alpar@100	1957	///
alpar@100	1958	/// \warning Besides addNode() and addArc(), a digraph structure may provide
alpar@100	1959	/// alternative ways to modify the digraph. The correct behavior of OutDegMap
alpar@100	1960	/// is not guarantied if these additional features are used. For example
alpar@100	1961	/// the functions \ref ListDigraph::changeSource() "changeSource()",
alpar@100	1962	/// \ref ListDigraph::changeTarget() "changeTarget()" and
alpar@100	1963	/// \ref ListDigraph::reverseArc() "reverseArc()"
alpar@100	1964	/// of \ref ListDigraph will \e not update the degree values correctly.
alpar@100	1965	///
alpar@100	1966	/// \sa InDegMap
alpar@100	1967
alpar@100	1968	template <typename _Digraph>
alpar@100	1969	class OutDegMap
alpar@100	1970	: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
alpar@100	1971	::ItemNotifier::ObserverBase {
alpar@100	1972
alpar@100	1973	public:
alpar@100	1974
alpar@100	1975	typedef _Digraph Digraph;
alpar@100	1976	typedef int Value;
alpar@100	1977	typedef typename Digraph::Node Key;
alpar@100	1978
deba@139	1979	typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@139	1980	::ItemNotifier::ObserverBase Parent;
deba@139	1981
alpar@100	1982	private:
alpar@100	1983
deba@139	1984	class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
alpar@100	1985	public:
alpar@100	1986
deba@139	1987	typedef DefaultMap<Digraph, Key, int> Parent;
alpar@100	1988
alpar@100	1989	AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
alpar@100	1990
alpar@100	1991	virtual void add(const Key& key) {
alpar@100	1992	Parent::add(key);
alpar@100	1993	Parent::set(key, 0);
alpar@100	1994	}
alpar@100	1995	virtual void add(const std::vector<Key>& keys) {
alpar@100	1996	Parent::add(keys);
alpar@100	1997	for (int i = 0; i < int(keys.size()); ++i) {
alpar@100	1998	Parent::set(keys[i], 0);
alpar@100	1999	}
alpar@100	2000	}
alpar@100	2001	virtual void build() {
alpar@100	2002	Parent::build();
alpar@100	2003	Key it;
alpar@100	2004	typename Parent::Notifier* nf = Parent::notifier();
alpar@100	2005	for (nf->first(it); it != INVALID; nf->next(it)) {
alpar@100	2006	Parent::set(it, 0);
alpar@100	2007	}
alpar@100	2008	}
alpar@100	2009	};
alpar@100	2010
alpar@100	2011	public:
alpar@100	2012
alpar@100	2013	/// \brief Constructor.
alpar@100	2014	///
alpar@100	2015	/// Constructor for creating out-degree map.
deba@139	2016	explicit OutDegMap(const Digraph& digraph)
deba@139	2017	: _digraph(digraph), _deg(digraph) {
deba@139	2018	Parent::attach(_digraph.notifier(typename Digraph::Arc()));
alpar@100	2019
deba@139	2020	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	2021	_deg[it] = countOutArcs(_digraph, it);
alpar@100	2022	}
alpar@100	2023	}
alpar@100	2024
alpar@100	2025	/// Gives back the out-degree of a Node.
alpar@100	2026	int operator[](const Key& key) const {
deba@139	2027	return _deg[key];
alpar@100	2028	}
alpar@100	2029
alpar@100	2030	protected:
alpar@100	2031
alpar@100	2032	typedef typename Digraph::Arc Arc;
alpar@100	2033
alpar@100	2034	virtual void add(const Arc& arc) {
deba@139	2035	++_deg[_digraph.source(arc)];
alpar@100	2036	}
alpar@100	2037
alpar@100	2038	virtual void add(const std::vector<Arc>& arcs) {
alpar@100	2039	for (int i = 0; i < int(arcs.size()); ++i) {
deba@139	2040	++_deg[_digraph.source(arcs[i])];
alpar@100	2041	}
alpar@100	2042	}
alpar@100	2043
alpar@100	2044	virtual void erase(const Arc& arc) {
deba@139	2045	--_deg[_digraph.source(arc)];
alpar@100	2046	}
alpar@100	2047
alpar@100	2048	virtual void erase(const std::vector<Arc>& arcs) {
alpar@100	2049	for (int i = 0; i < int(arcs.size()); ++i) {
deba@139	2050	--_deg[_digraph.source(arcs[i])];
alpar@100	2051	}
alpar@100	2052	}
alpar@100	2053
alpar@100	2054	virtual void build() {
deba@139	2055	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	2056	_deg[it] = countOutArcs(_digraph, it);
alpar@100	2057	}
alpar@100	2058	}
alpar@100	2059
alpar@100	2060	virtual void clear() {
deba@139	2061	for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@139	2062	_deg[it] = 0;
alpar@100	2063	}
alpar@100	2064	}
alpar@100	2065	private:
alpar@100	2066
deba@139	2067	const Digraph& _digraph;
deba@139	2068	AutoNodeMap _deg;
alpar@100	2069	};
alpar@100	2070
alpar@100	2071
alpar@100	2072	///Dynamic arc look up between given endpoints.
alpar@100	2073
alpar@100	2074	///\ingroup gutils
alpar@100	2075	///Using this class, you can find an arc in a digraph from a given
alpar@100	2076	///source to a given target in amortized time <em>O(log d)</em>,
alpar@100	2077	///where <em>d</em> is the out-degree of the source node.
alpar@100	2078	///
alpar@100	2079	///It is possible to find \e all parallel arcs between two nodes with
alpar@100	2080	///the \c findFirst() and \c findNext() members.
alpar@100	2081	///
alpar@100	2082	///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
deba@139	2083	///digraph is not changed so frequently.
alpar@100	2084	///
alpar@100	2085	///This class uses a self-adjusting binary search tree, Sleator's
alpar@100	2086	///and Tarjan's Splay tree for guarantee the logarithmic amortized
alpar@100	2087	///time bound for arc lookups. This class also guarantees the
alpar@100	2088	///optimal time bound in a constant factor for any distribution of
alpar@100	2089	///queries.
alpar@100	2090	///
kpeter@157	2091	///\tparam G The type of the underlying digraph.
alpar@100	2092	///
alpar@100	2093	///\sa ArcLookUp
alpar@100	2094	///\sa AllArcLookUp
alpar@100	2095	template<class G>
alpar@100	2096	class DynArcLookUp
alpar@100	2097	: protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
alpar@100	2098	{
alpar@100	2099	public:
alpar@100	2100	typedef typename ItemSetTraits<G, typename G::Arc>
alpar@100	2101	::ItemNotifier::ObserverBase Parent;
alpar@100	2102
deba@148	2103	TEMPLATE_DIGRAPH_TYPEDEFS(G);
alpar@100	2104	typedef G Digraph;
alpar@100	2105
alpar@100	2106	protected:
alpar@100	2107
alpar@100	2108	class AutoNodeMap : public DefaultMap<G, Node, Arc> {
alpar@100	2109	public:
alpar@100	2110
alpar@100	2111	typedef DefaultMap<G, Node, Arc> Parent;
alpar@100	2112
alpar@100	2113	AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
alpar@100	2114
alpar@100	2115	virtual void add(const Node& node) {
alpar@100	2116	Parent::add(node);
alpar@100	2117	Parent::set(node, INVALID);
alpar@100	2118	}
alpar@100	2119
alpar@100	2120	virtual void add(const std::vector<Node>& nodes) {
alpar@100	2121	Parent::add(nodes);
alpar@100	2122	for (int i = 0; i < int(nodes.size()); ++i) {
alpar@100	2123	Parent::set(nodes[i], INVALID);
alpar@100	2124	}
alpar@100	2125	}
alpar@100	2126
alpar@100	2127	virtual void build() {
alpar@100	2128	Parent::build();
alpar@100	2129	Node it;
alpar@100	2130	typename Parent::Notifier* nf = Parent::notifier();
alpar@100	2131	for (nf->first(it); it != INVALID; nf->next(it)) {
alpar@100	2132	Parent::set(it, INVALID);
alpar@100	2133	}
alpar@100	2134	}
alpar@100	2135	};
alpar@100	2136
alpar@100	2137	const Digraph &_g;
alpar@100	2138	AutoNodeMap _head;
alpar@100	2139	typename Digraph::template ArcMap<Arc> _parent;
alpar@100	2140	typename Digraph::template ArcMap<Arc> _left;
alpar@100	2141	typename Digraph::template ArcMap<Arc> _right;
alpar@100	2142
alpar@100	2143	class ArcLess {
alpar@100	2144	const Digraph &g;
alpar@100	2145	public:
alpar@100	2146	ArcLess(const Digraph &_g) : g(_g) {}
alpar@100	2147	bool operator()(Arc a,Arc b) const
alpar@100	2148	{
alpar@100	2149	return g.target(a)<g.target(b);
alpar@100	2150	}
alpar@100	2151	};
alpar@100	2152
alpar@100	2153	public:
alpar@100	2154
alpar@100	2155	///Constructor
alpar@100	2156
alpar@100	2157	///Constructor.
alpar@100	2158	///
alpar@100	2159	///It builds up the search database.
alpar@100	2160	DynArcLookUp(const Digraph &g)
alpar@100	2161	: _g(g),_head(g),_parent(g),_left(g),_right(g)
alpar@100	2162	{
alpar@100	2163	Parent::attach(_g.notifier(typename Digraph::Arc()));
alpar@100	2164	refresh();
alpar@100	2165	}
alpar@100	2166
alpar@100	2167	protected:
alpar@100	2168
alpar@100	2169	virtual void add(const Arc& arc) {
alpar@100	2170	insert(arc);
alpar@100	2171	}
alpar@100	2172
alpar@100	2173	virtual void add(const std::vector<Arc>& arcs) {
alpar@100	2174	for (int i = 0; i < int(arcs.size()); ++i) {
alpar@100	2175	insert(arcs[i]);
alpar@100	2176	}
alpar@100	2177	}
alpar@100	2178
alpar@100	2179	virtual void erase(const Arc& arc) {
alpar@100	2180	remove(arc);
alpar@100	2181	}
alpar@100	2182
alpar@100	2183	virtual void erase(const std::vector<Arc>& arcs) {
alpar@100	2184	for (int i = 0; i < int(arcs.size()); ++i) {
alpar@100	2185	remove(arcs[i]);
alpar@100	2186	}
alpar@100	2187	}
alpar@100	2188
alpar@100	2189	virtual void build() {
alpar@100	2190	refresh();
alpar@100	2191	}
alpar@100	2192
alpar@100	2193	virtual void clear() {
alpar@100	2194	for(NodeIt n(_g);n!=INVALID;++n) {
alpar@100	2195	_head.set(n, INVALID);
alpar@100	2196	}
alpar@100	2197	}
alpar@100	2198
alpar@100	2199	void insert(Arc arc) {
alpar@100	2200	Node s = _g.source(arc);
alpar@100	2201	Node t = _g.target(arc);
alpar@100	2202	_left.set(arc, INVALID);
alpar@100	2203	_right.set(arc, INVALID);
alpar@100	2204
alpar@100	2205	Arc e = _head[s];
alpar@100	2206	if (e == INVALID) {
alpar@100	2207	_head.set(s, arc);
alpar@100	2208	_parent.set(arc, INVALID);
alpar@100	2209	return;
alpar@100	2210	}
alpar@100	2211	while (true) {
alpar@100	2212	if (t < _g.target(e)) {
alpar@100	2213	if (_left[e] == INVALID) {
alpar@100	2214	_left.set(e, arc);
alpar@100	2215	_parent.set(arc, e);
alpar@100	2216	splay(arc);
alpar@100	2217	return;
alpar@100	2218	} else {
alpar@100	2219	e = _left[e];
alpar@100	2220	}
alpar@100	2221	} else {
alpar@100	2222	if (_right[e] == INVALID) {
alpar@100	2223	_right.set(e, arc);
alpar@100	2224	_parent.set(arc, e);
alpar@100	2225	splay(arc);
alpar@100	2226	return;
alpar@100	2227	} else {
alpar@100	2228	e = _right[e];
alpar@100	2229	}
alpar@100	2230	}
alpar@100	2231	}
alpar@100	2232	}
alpar@100	2233
alpar@100	2234	void remove(Arc arc) {
alpar@100	2235	if (_left[arc] == INVALID) {
alpar@100	2236	if (_right[arc] != INVALID) {
alpar@100	2237	_parent.set(_right[arc], _parent[arc]);
alpar@100	2238	}
alpar@100	2239	if (_parent[arc] != INVALID) {
alpar@100	2240	if (_left[_parent[arc]] == arc) {
alpar@100	2241	_left.set(_parent[arc], _right[arc]);
alpar@100	2242	} else {
alpar@100	2243	_right.set(_parent[arc], _right[arc]);
alpar@100	2244	}
alpar@100	2245	} else {
alpar@100	2246	_head.set(_g.source(arc), _right[arc]);
alpar@100	2247	}
alpar@100	2248	} else if (_right[arc] == INVALID) {
alpar@100	2249	_parent.set(_left[arc], _parent[arc]);
alpar@100	2250	if (_parent[arc] != INVALID) {
alpar@100	2251	if (_left[_parent[arc]] == arc) {
alpar@100	2252	_left.set(_parent[arc], _left[arc]);
alpar@100	2253	} else {
alpar@100	2254	_right.set(_parent[arc], _left[arc]);
alpar@100	2255	}
alpar@100	2256	} else {
alpar@100	2257	_head.set(_g.source(arc), _left[arc]);
alpar@100	2258	}
alpar@100	2259	} else {
alpar@100	2260	Arc e = _left[arc];
alpar@100	2261	if (_right[e] != INVALID) {
alpar@100	2262	e = _right[e];
alpar@100	2263	while (_right[e] != INVALID) {
alpar@100	2264	e = _right[e];
alpar@100	2265	}
alpar@100	2266	Arc s = _parent[e];
alpar@100	2267	_right.set(_parent[e], _left[e]);
alpar@100	2268	if (_left[e] != INVALID) {
alpar@100	2269	_parent.set(_left[e], _parent[e]);
alpar@100	2270	}
alpar@100	2271
alpar@100	2272	_left.set(e, _left[arc]);
alpar@100	2273	_parent.set(_left[arc], e);
alpar@100	2274	_right.set(e, _right[arc]);
alpar@100	2275	_parent.set(_right[arc], e);
alpar@100	2276
alpar@100	2277	_parent.set(e, _parent[arc]);
alpar@100	2278	if (_parent[arc] != INVALID) {
alpar@100	2279	if (_left[_parent[arc]] == arc) {
alpar@100	2280	_left.set(_parent[arc], e);
alpar@100	2281	} else {
alpar@100	2282	_right.set(_parent[arc], e);
alpar@100	2283	}
alpar@100	2284	}
alpar@100	2285	splay(s);
alpar@100	2286	} else {
alpar@100	2287	_right.set(e, _right[arc]);
alpar@100	2288	_parent.set(_right[arc], e);
alpar@100	2289
alpar@100	2290	if (_parent[arc] != INVALID) {
alpar@100	2291	if (_left[_parent[arc]] == arc) {
alpar@100	2292	_left.set(_parent[arc], e);
alpar@100	2293	} else {
alpar@100	2294	_right.set(_parent[arc], e);
alpar@100	2295	}
alpar@100	2296	} else {
alpar@100	2297	_head.set(_g.source(arc), e);
alpar@100	2298	}
alpar@100	2299	}
alpar@100	2300	}
alpar@100	2301	}
alpar@100	2302
alpar@100	2303	Arc refreshRec(std::vector<Arc> &v,int a,int b)
alpar@100	2304	{
alpar@100	2305	int m=(a+b)/2;
alpar@100	2306	Arc me=v[m];
alpar@100	2307	if (a < m) {
alpar@100	2308	Arc left = refreshRec(v,a,m-1);
alpar@100	2309	_left.set(me, left);
alpar@100	2310	_parent.set(left, me);
alpar@100	2311	} else {
alpar@100	2312	_left.set(me, INVALID);
alpar@100	2313	}
alpar@100	2314	if (m < b) {
alpar@100	2315	Arc right = refreshRec(v,m+1,b);
alpar@100	2316	_right.set(me, right);
alpar@100	2317	_parent.set(right, me);
alpar@100	2318	} else {
alpar@100	2319	_right.set(me, INVALID);
alpar@100	2320	}
alpar@100	2321	return me;
alpar@100	2322	}
alpar@100	2323
alpar@100	2324	void refresh() {
alpar@100	2325	for(NodeIt n(_g);n!=INVALID;++n) {
alpar@100	2326	std::vector<Arc> v;
alpar@100	2327	for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
alpar@100	2328	if(v.size()) {
alpar@100	2329	std::sort(v.begin(),v.end(),ArcLess(_g));
alpar@100	2330	Arc head = refreshRec(v,0,v.size()-1);
alpar@100	2331	_head.set(n, head);
alpar@100	2332	_parent.set(head, INVALID);
alpar@100	2333	}
alpar@100	2334	else _head.set(n, INVALID);
alpar@100	2335	}
alpar@100	2336	}
alpar@100	2337
alpar@100	2338	void zig(Arc v) {
alpar@100	2339	Arc w = _parent[v];
alpar@100	2340	_parent.set(v, _parent[w]);
alpar@100	2341	_parent.set(w, v);
alpar@100	2342	_left.set(w, _right[v]);
alpar@100	2343	_right.set(v, w);
alpar@100	2344	if (_parent[v] != INVALID) {
alpar@100	2345	if (_right[_parent[v]] == w) {
alpar@100	2346	_right.set(_parent[v], v);
alpar@100	2347	} else {
alpar@100	2348	_left.set(_parent[v], v);
alpar@100	2349	}
alpar@100	2350	}
alpar@100	2351	if (_left[w] != INVALID){
alpar@100	2352	_parent.set(_left[w], w);
alpar@100	2353	}
alpar@100	2354	}
alpar@100	2355
alpar@100	2356	void zag(Arc v) {
alpar@100	2357	Arc w = _parent[v];
alpar@100	2358	_parent.set(v, _parent[w]);
alpar@100	2359	_parent.set(w, v);
alpar@100	2360	_right.set(w, _left[v]);
alpar@100	2361	_left.set(v, w);
alpar@100	2362	if (_parent[v] != INVALID){
alpar@100	2363	if (_left[_parent[v]] == w) {
alpar@100	2364	_left.set(_parent[v], v);
alpar@100	2365	} else {
alpar@100	2366	_right.set(_parent[v], v);
alpar@100	2367	}
alpar@100	2368	}
alpar@100	2369	if (_right[w] != INVALID){
alpar@100	2370	_parent.set(_right[w], w);
alpar@100	2371	}
alpar@100	2372	}
alpar@100	2373
alpar@100	2374	void splay(Arc v) {
alpar@100	2375	while (_parent[v] != INVALID) {
alpar@100	2376	if (v == _left[_parent[v]]) {
alpar@100	2377	if (_parent[_parent[v]] == INVALID) {
alpar@100	2378	zig(v);
alpar@100	2379	} else {
alpar@100	2380	if (_parent[v] == _left[_parent[_parent[v]]]) {
alpar@100	2381	zig(_parent[v]);
alpar@100	2382	zig(v);
alpar@100	2383	} else {
alpar@100	2384	zig(v);
alpar@100	2385	zag(v);
alpar@100	2386	}
alpar@100	2387	}
alpar@100	2388	} else {
alpar@100	2389	if (_parent[_parent[v]] == INVALID) {
alpar@100	2390	zag(v);
alpar@100	2391	} else {
alpar@100	2392	if (_parent[v] == _left[_parent[_parent[v]]]) {
alpar@100	2393	zag(v);
alpar@100	2394	zig(v);
alpar@100	2395	} else {
alpar@100	2396	zag(_parent[v]);
alpar@100	2397	zag(v);
alpar@100	2398	}
alpar@100	2399	}
alpar@100	2400	}
alpar@100	2401	}
alpar@100	2402	_head[_g.source(v)] = v;
alpar@100	2403	}
alpar@100	2404
alpar@100	2405
alpar@100	2406	public:
alpar@100	2407
alpar@100	2408	///Find an arc between two nodes.
alpar@100	2409
alpar@100	2410	///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
alpar@100	2411	/// <em>d</em> is the number of outgoing arcs of \c s.
alpar@100	2412	///\param s The source node
alpar@100	2413	///\param t The target node
alpar@100	2414	///\return An arc from \c s to \c t if there exists,
alpar@100	2415	///\ref INVALID otherwise.
alpar@100	2416	Arc operator()(Node s, Node t) const
alpar@100	2417	{
deba@139	2418	Arc a = _head[s];
alpar@100	2419	while (true) {
deba@139	2420	if (_g.target(a) == t) {
deba@139	2421	const_cast<DynArcLookUp&>(*this).splay(a);
deba@139	2422	return a;
deba@139	2423	} else if (t < _g.target(a)) {
deba@139	2424	if (_left[a] == INVALID) {
deba@139	2425	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2426	return INVALID;
alpar@100	2427	} else {
deba@139	2428	a = _left[a];
alpar@100	2429	}
alpar@100	2430	} else {
deba@139	2431	if (_right[a] == INVALID) {
deba@139	2432	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2433	return INVALID;
alpar@100	2434	} else {
deba@139	2435	a = _right[a];
alpar@100	2436	}
alpar@100	2437	}
alpar@100	2438	}
alpar@100	2439	}
alpar@100	2440
alpar@100	2441	///Find the first arc between two nodes.
alpar@100	2442
alpar@100	2443	///Find the first arc between two nodes in time
alpar@100	2444	/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
alpar@100	2445	/// outgoing arcs of \c s.
alpar@100	2446	///\param s The source node
alpar@100	2447	///\param t The target node
alpar@100	2448	///\return An arc from \c s to \c t if there exists, \ref INVALID
alpar@100	2449	/// otherwise.
alpar@100	2450	Arc findFirst(Node s, Node t) const
alpar@100	2451	{
deba@139	2452	Arc a = _head[s];
alpar@100	2453	Arc r = INVALID;
alpar@100	2454	while (true) {
deba@139	2455	if (_g.target(a) < t) {
deba@139	2456	if (_right[a] == INVALID) {
deba@139	2457	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2458	return r;
alpar@100	2459	} else {
deba@139	2460	a = _right[a];
alpar@100	2461	}
alpar@100	2462	} else {
deba@139	2463	if (_g.target(a) == t) {
deba@139	2464	r = a;
alpar@100	2465	}
deba@139	2466	if (_left[a] == INVALID) {
deba@139	2467	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2468	return r;
alpar@100	2469	} else {
deba@139	2470	a = _left[a];
alpar@100	2471	}
alpar@100	2472	}
alpar@100	2473	}
alpar@100	2474	}
alpar@100	2475
alpar@100	2476	///Find the next arc between two nodes.
alpar@100	2477
alpar@100	2478	///Find the next arc between two nodes in time
alpar@100	2479	/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
alpar@100	2480	/// outgoing arcs of \c s.
alpar@100	2481	///\param s The source node
alpar@100	2482	///\param t The target node
alpar@100	2483	///\return An arc from \c s to \c t if there exists, \ref INVALID
alpar@100	2484	/// otherwise.
alpar@100	2485
alpar@100	2486	///\note If \c e is not the result of the previous \c findFirst()
alpar@100	2487	///operation then the amorized time bound can not be guaranteed.
alpar@100	2488	#ifdef DOXYGEN
deba@139	2489	Arc findNext(Node s, Node t, Arc a) const
alpar@100	2490	#else
deba@139	2491	Arc findNext(Node, Node t, Arc a) const
alpar@100	2492	#endif
alpar@100	2493	{
deba@139	2494	if (_right[a] != INVALID) {
deba@139	2495	a = _right[a];
deba@139	2496	while (_left[a] != INVALID) {
deba@139	2497	a = _left[a];
alpar@100	2498	}
deba@139	2499	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2500	} else {
deba@139	2501	while (_parent[a] != INVALID && _right[_parent[a]] == a) {
deba@139	2502	a = _parent[a];
alpar@100	2503	}
deba@139	2504	if (_parent[a] == INVALID) {
alpar@100	2505	return INVALID;
alpar@100	2506	} else {
deba@139	2507	a = _parent[a];
deba@139	2508	const_cast<DynArcLookUp&>(*this).splay(a);
alpar@100	2509	}
alpar@100	2510	}
deba@139	2511	if (_g.target(a) == t) return a;
alpar@100	2512	else return INVALID;
alpar@100	2513	}
alpar@100	2514
alpar@100	2515	};
alpar@100	2516
alpar@100	2517	///Fast arc look up between given endpoints.
alpar@100	2518
alpar@100	2519	///\ingroup gutils
alpar@100	2520	///Using this class, you can find an arc in a digraph from a given
alpar@100	2521	///source to a given target in time <em>O(log d)</em>,
alpar@100	2522	///where <em>d</em> is the out-degree of the source node.
alpar@100	2523	///
alpar@100	2524	///It is not possible to find \e all parallel arcs between two nodes.
alpar@100	2525	///Use \ref AllArcLookUp for this purpose.
alpar@100	2526	///
alpar@100	2527	///\warning This class is static, so you should refresh() (or at least
alpar@100	2528	///refresh(Node)) this data structure
alpar@100	2529	///whenever the digraph changes. This is a time consuming (superlinearly
alpar@100	2530	///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
alpar@100	2531	///
kpeter@157	2532	///\tparam G The type of the underlying digraph.
alpar@100	2533	///
alpar@100	2534	///\sa DynArcLookUp
alpar@100	2535	///\sa AllArcLookUp
alpar@100	2536	template<class G>
alpar@100	2537	class ArcLookUp
alpar@100	2538	{
alpar@100	2539	public:
deba@148	2540	TEMPLATE_DIGRAPH_TYPEDEFS(G);
alpar@100	2541	typedef G Digraph;
alpar@100	2542
alpar@100	2543	protected:
alpar@100	2544	const Digraph &_g;
alpar@100	2545	typename Digraph::template NodeMap<Arc> _head;
alpar@100	2546	typename Digraph::template ArcMap<Arc> _left;
alpar@100	2547	typename Digraph::template ArcMap<Arc> _right;
alpar@100	2548
alpar@100	2549	class ArcLess {
alpar@100	2550	const Digraph &g;
alpar@100	2551	public:
alpar@100	2552	ArcLess(const Digraph &_g) : g(_g) {}
alpar@100	2553	bool operator()(Arc a,Arc b) const
alpar@100	2554	{
alpar@100	2555	return g.target(a)<g.target(b);
alpar@100	2556	}
alpar@100	2557	};
alpar@100	2558
alpar@100	2559	public:
alpar@100	2560
alpar@100	2561	///Constructor
alpar@100	2562
alpar@100	2563	///Constructor.
alpar@100	2564	///
alpar@100	2565	///It builds up the search database, which remains valid until the digraph
alpar@100	2566	///changes.
alpar@100	2567	ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
alpar@100	2568
alpar@100	2569	private:
alpar@100	2570	Arc refreshRec(std::vector<Arc> &v,int a,int b)
alpar@100	2571	{
alpar@100	2572	int m=(a+b)/2;
alpar@100	2573	Arc me=v[m];
alpar@100	2574	_left[me] = a<m?refreshRec(v,a,m-1):INVALID;
alpar@100	2575	_right[me] = m<b?refreshRec(v,m+1,b):INVALID;
alpar@100	2576	return me;
alpar@100	2577	}
alpar@100	2578	public:
alpar@100	2579	///Refresh the data structure at a node.
alpar@100	2580
alpar@100	2581	///Build up the search database of node \c n.
alpar@100	2582	///
alpar@100	2583	///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
alpar@100	2584	///the number of the outgoing arcs of \c n.
alpar@100	2585	void refresh(Node n)
alpar@100	2586	{
alpar@100	2587	std::vector<Arc> v;
alpar@100	2588	for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
alpar@100	2589	if(v.size()) {
alpar@100	2590	std::sort(v.begin(),v.end(),ArcLess(_g));
alpar@100	2591	_head[n]=refreshRec(v,0,v.size()-1);
alpar@100	2592	}
alpar@100	2593	else _head[n]=INVALID;
alpar@100	2594	}
alpar@100	2595	///Refresh the full data structure.
alpar@100	2596
alpar@100	2597	///Build up the full search database. In fact, it simply calls
alpar@100	2598	///\ref refresh(Node) "refresh(n)" for each node \c n.
alpar@100	2599	///
alpar@100	2600	///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
alpar@100	2601	///the number of the arcs of \c n and <em>D</em> is the maximum
alpar@100	2602	///out-degree of the digraph.
alpar@100	2603
alpar@100	2604	void refresh()
alpar@100	2605	{
alpar@100	2606	for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
alpar@100	2607	}
alpar@100	2608
alpar@100	2609	///Find an arc between two nodes.
alpar@100	2610
alpar@100	2611	///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
alpar@100	2612	/// <em>d</em> is the number of outgoing arcs of \c s.
alpar@100	2613	///\param s The source node
alpar@100	2614	///\param t The target node
alpar@100	2615	///\return An arc from \c s to \c t if there exists,
alpar@100	2616	///\ref INVALID otherwise.
alpar@100	2617	///
alpar@100	2618	///\warning If you change the digraph, refresh() must be called before using
alpar@100	2619	///this operator. If you change the outgoing arcs of
alpar@100	2620	///a single node \c n, then
alpar@100	2621	///\ref refresh(Node) "refresh(n)" is enough.
alpar@100	2622	///
alpar@100	2623	Arc operator()(Node s, Node t) const
alpar@100	2624	{
alpar@100	2625	Arc e;
alpar@100	2626	for(e=_head[s];
alpar@100	2627	e!=INVALID&&_g.target(e)!=t;
alpar@100	2628	e = t < _g.target(e)?_left[e]:_right[e]) ;
alpar@100	2629	return e;
alpar@100	2630	}
alpar@100	2631
alpar@100	2632	};
alpar@100	2633
alpar@100	2634	///Fast look up of all arcs between given endpoints.
alpar@100	2635
alpar@100	2636	///\ingroup gutils
alpar@100	2637	///This class is the same as \ref ArcLookUp, with the addition
alpar@100	2638	///that it makes it possible to find all arcs between given endpoints.
alpar@100	2639	///
alpar@100	2640	///\warning This class is static, so you should refresh() (or at least
alpar@100	2641	///refresh(Node)) this data structure
alpar@100	2642	///whenever the digraph changes. This is a time consuming (superlinearly
alpar@100	2643	///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
alpar@100	2644	///
kpeter@157	2645	///\tparam G The type of the underlying digraph.
alpar@100	2646	///
alpar@100	2647	///\sa DynArcLookUp
alpar@100	2648	///\sa ArcLookUp
alpar@100	2649	template<class G>
alpar@100	2650	class AllArcLookUp : public ArcLookUp<G>
alpar@100	2651	{
alpar@100	2652	using ArcLookUp<G>::_g;
alpar@100	2653	using ArcLookUp<G>::_right;
alpar@100	2654	using ArcLookUp<G>::_left;
alpar@100	2655	using ArcLookUp<G>::_head;
alpar@100	2656
deba@148	2657	TEMPLATE_DIGRAPH_TYPEDEFS(G);
alpar@100	2658	typedef G Digraph;
alpar@100	2659
alpar@100	2660	typename Digraph::template ArcMap<Arc> _next;
alpar@100	2661
alpar@100	2662	Arc refreshNext(Arc head,Arc next=INVALID)
alpar@100	2663	{
alpar@100	2664	if(head==INVALID) return next;
alpar@100	2665	else {
alpar@100	2666	next=refreshNext(_right[head],next);
alpar@100	2667	// _next[head]=next;
alpar@100	2668	_next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
alpar@100	2669	? next : INVALID;
alpar@100	2670	return refreshNext(_left[head],head);
alpar@100	2671	}
alpar@100	2672	}
alpar@100	2673
alpar@100	2674	void refreshNext()
alpar@100	2675	{
alpar@100	2676	for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
alpar@100	2677	}
alpar@100	2678
alpar@100	2679	public:
alpar@100	2680	///Constructor
alpar@100	2681
alpar@100	2682	///Constructor.
alpar@100	2683	///
alpar@100	2684	///It builds up the search database, which remains valid until the digraph
alpar@100	2685	///changes.
alpar@100	2686	AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
alpar@100	2687
alpar@100	2688	///Refresh the data structure at a node.
alpar@100	2689
alpar@100	2690	///Build up the search database of node \c n.
alpar@100	2691	///
alpar@100	2692	///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
alpar@100	2693	///the number of the outgoing arcs of \c n.
alpar@100	2694
alpar@100	2695	void refresh(Node n)
alpar@100	2696	{
alpar@100	2697	ArcLookUp<G>::refresh(n);
alpar@100	2698	refreshNext(_head[n]);
alpar@100	2699	}
alpar@100	2700
alpar@100	2701	///Refresh the full data structure.
alpar@100	2702
alpar@100	2703	///Build up the full search database. In fact, it simply calls
alpar@100	2704	///\ref refresh(Node) "refresh(n)" for each node \c n.
alpar@100	2705	///
alpar@100	2706	///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
alpar@100	2707	///the number of the arcs of \c n and <em>D</em> is the maximum
alpar@100	2708	///out-degree of the digraph.
alpar@100	2709
alpar@100	2710	void refresh()
alpar@100	2711	{
alpar@100	2712	for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
alpar@100	2713	}
alpar@100	2714
alpar@100	2715	///Find an arc between two nodes.
alpar@100	2716
alpar@100	2717	///Find an arc between two nodes.
alpar@100	2718	///\param s The source node
alpar@100	2719	///\param t The target node
alpar@100	2720	///\param prev The previous arc between \c s and \c t. It it is INVALID or
alpar@100	2721	///not given, the operator finds the first appropriate arc.
alpar@100	2722	///\return An arc from \c s to \c t after \c prev or
alpar@100	2723	///\ref INVALID if there is no more.
alpar@100	2724	///
alpar@100	2725	///For example, you can count the number of arcs from \c u to \c v in the
alpar@100	2726	///following way.
alpar@100	2727	///\code
alpar@100	2728	///AllArcLookUp<ListDigraph> ae(g);
alpar@100	2729	///...
alpar@100	2730	///int n=0;
alpar@100	2731	///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
alpar@100	2732	///\endcode
alpar@100	2733	///
alpar@100	2734	///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
alpar@100	2735	/// <em>d</em> is the number of outgoing arcs of \c s. Then, the
alpar@100	2736	///consecutive arcs are found in constant time.
alpar@100	2737	///
alpar@100	2738	///\warning If you change the digraph, refresh() must be called before using
alpar@100	2739	///this operator. If you change the outgoing arcs of
alpar@100	2740	///a single node \c n, then
alpar@100	2741	///\ref refresh(Node) "refresh(n)" is enough.
alpar@100	2742	///
alpar@100	2743	#ifdef DOXYGEN
alpar@100	2744	Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
alpar@100	2745	#else
alpar@100	2746	using ArcLookUp<G>::operator() ;
alpar@100	2747	Arc operator()(Node s, Node t, Arc prev) const
alpar@100	2748	{
alpar@100	2749	return prev==INVALID?(*this)(s,t):_next[prev];
alpar@100	2750	}
alpar@100	2751	#endif
alpar@100	2752
alpar@100	2753	};
alpar@100	2754
alpar@100	2755	/// @}
alpar@100	2756
alpar@100	2757	} //END OF NAMESPACE LEMON
alpar@100	2758
alpar@100	2759	#endif

author	Peter Kovacs <kpeter@inf.elte.hu>
	Sat, 24 May 2008 23:20:49 +0200
changeset 157	2ccc1afc2c52
parent 148	4e2581021300
child 169	5b507a86ad72
permissions	-rw-r--r--