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

author	Balazs Dezso <deba@inf.elte.hu>
	Wed, 23 Apr 2008 15:33:53 +0200
changeset 147	7c39a090cfc3
parent 140	356930927a71
child 148	4e2581021300
permissions	-rw-r--r--