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

author	Balazs Dezso <deba@inf.elte.hu>
	Thu, 24 Apr 2008 13:53:09 +0100
changeset 149	2f7ae34e1333
parent 147	7c39a090cfc3
child 157	2ccc1afc2c52
permissions	-rw-r--r--