lemon-main: lemon/dfs.h@9ce7a01a95c7 (annotated)

alpar@209	1	/* -- mode: C++; indent-tabs-mode: nil; --
alpar@100	2	*
alpar@209	3	* This file is a part of LEMON, a generic C++ optimization library.
alpar@100	4	*
alpar@100	5	* Copyright (C) 2003-2008
alpar@100	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100	8	*
alpar@100	9	* Permission to use, modify and distribute this software is granted
alpar@100	10	* provided that this copyright notice appears in all copies. For
alpar@100	11	* precise terms see the accompanying LICENSE file.
alpar@100	12	*
alpar@100	13	* This software is provided "AS IS" with no warranty of any kind,
alpar@100	14	* express or implied, and with no claim as to its suitability for any
alpar@100	15	* purpose.
alpar@100	16	*
alpar@100	17	*/
alpar@100	18
alpar@100	19	#ifndef LEMON_DFS_H
alpar@100	20	#define LEMON_DFS_H
alpar@100	21
alpar@100	22	///\ingroup search
alpar@100	23	///\file
alpar@100	24	///\brief Dfs algorithm.
alpar@100	25
alpar@100	26	#include <lemon/list_graph.h>
alpar@100	27	#include <lemon/bits/path_dump.h>
deba@220	28	#include <lemon/core.h>
alpar@100	29	#include <lemon/error.h>
alpar@100	30	#include <lemon/maps.h>
alpar@100	31
alpar@100	32	#include <lemon/concept_check.h>
alpar@100	33
alpar@100	34	namespace lemon {
alpar@100	35
alpar@209	36
alpar@100	37	///Default traits class of Dfs class.
alpar@100	38
alpar@100	39	///Default traits class of Dfs class.
kpeter@157	40	///\tparam GR Digraph type.
alpar@100	41	template<class GR>
alpar@100	42	struct DfsDefaultTraits
alpar@100	43	{
alpar@209	44	///The digraph type the algorithm runs on.
alpar@100	45	typedef GR Digraph;
alpar@100	46	///\brief The type of the map that stores the last
alpar@100	47	///arcs of the %DFS paths.
alpar@209	48	///
alpar@100	49	///The type of the map that stores the last
alpar@100	50	///arcs of the %DFS paths.
alpar@100	51	///It must meet the \ref concepts::WriteMap "WriteMap" concept.
alpar@100	52	///
alpar@100	53	typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
alpar@100	54	///Instantiates a PredMap.
alpar@209	55
alpar@209	56	///This function instantiates a \ref PredMap.
alpar@100	57	///\param G is the digraph, to which we would like to define the PredMap.
alpar@100	58	///\todo The digraph alone may be insufficient to initialize
alpar@209	59	static PredMap *createPredMap(const GR &G)
alpar@100	60	{
alpar@100	61	return new PredMap(G);
alpar@100	62	}
alpar@100	63
alpar@100	64	///The type of the map that indicates which nodes are processed.
alpar@209	65
alpar@100	66	///The type of the map that indicates which nodes are processed.
alpar@100	67	///It must meet the \ref concepts::WriteMap "WriteMap" concept.
alpar@100	68	///\todo named parameter to set this type, function to read and write.
alpar@100	69	typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
alpar@100	70	///Instantiates a ProcessedMap.
alpar@209	71
alpar@209	72	///This function instantiates a \ref ProcessedMap.
alpar@100	73	///\param g is the digraph, to which
alpar@100	74	///we would like to define the \ref ProcessedMap
alpar@100	75	#ifdef DOXYGEN
alpar@100	76	static ProcessedMap *createProcessedMap(const GR &g)
alpar@100	77	#else
alpar@100	78	static ProcessedMap *createProcessedMap(const GR &)
alpar@100	79	#endif
alpar@100	80	{
alpar@100	81	return new ProcessedMap();
alpar@100	82	}
alpar@100	83	///The type of the map that indicates which nodes are reached.
alpar@209	84
alpar@100	85	///The type of the map that indicates which nodes are reached.
alpar@100	86	///It must meet the \ref concepts::WriteMap "WriteMap" concept.
alpar@100	87	///\todo named parameter to set this type, function to read and write.
alpar@100	88	typedef typename Digraph::template NodeMap<bool> ReachedMap;
alpar@100	89	///Instantiates a ReachedMap.
alpar@209	90
alpar@209	91	///This function instantiates a \ref ReachedMap.
alpar@100	92	///\param G is the digraph, to which
alpar@100	93	///we would like to define the \ref ReachedMap.
alpar@100	94	static ReachedMap *createReachedMap(const GR &G)
alpar@100	95	{
alpar@100	96	return new ReachedMap(G);
alpar@100	97	}
alpar@100	98	///The type of the map that stores the dists of the nodes.
alpar@209	99
alpar@100	100	///The type of the map that stores the dists of the nodes.
alpar@100	101	///It must meet the \ref concepts::WriteMap "WriteMap" concept.
alpar@100	102	///
alpar@100	103	typedef typename Digraph::template NodeMap<int> DistMap;
alpar@100	104	///Instantiates a DistMap.
alpar@209	105
alpar@209	106	///This function instantiates a \ref DistMap.
alpar@210	107	///\param G is the digraph, to which we would like to define
alpar@210	108	///the \ref DistMap
alpar@100	109	static DistMap *createDistMap(const GR &G)
alpar@100	110	{
alpar@100	111	return new DistMap(G);
alpar@100	112	}
alpar@100	113	};
alpar@209	114
alpar@100	115	///%DFS algorithm class.
alpar@209	116
alpar@100	117	///\ingroup search
alpar@100	118	///This class provides an efficient implementation of the %DFS algorithm.
alpar@100	119	///
kpeter@157	120	///\tparam GR The digraph type the algorithm runs on. The default value is
alpar@100	121	///\ref ListDigraph. The value of GR is not used directly by Dfs, it
alpar@100	122	///is only passed to \ref DfsDefaultTraits.
kpeter@157	123	///\tparam TR Traits class to set various data types used by the algorithm.
alpar@100	124	///The default traits class is
alpar@100	125	///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
alpar@100	126	///See \ref DfsDefaultTraits for the documentation of
alpar@100	127	///a Dfs traits class.
alpar@100	128	#ifdef DOXYGEN
alpar@100	129	template <typename GR,
alpar@209	130	typename TR>
alpar@100	131	#else
alpar@100	132	template <typename GR=ListDigraph,
alpar@209	133	typename TR=DfsDefaultTraits<GR> >
alpar@100	134	#endif
alpar@100	135	class Dfs {
alpar@100	136	public:
alpar@100	137	/**
alpar@100	138	* \brief \ref Exception for uninitialized parameters.
alpar@100	139	*
alpar@100	140	* This error represents problems in the initialization
alpar@100	141	* of the parameters of the algorithms.
alpar@100	142	*/
alpar@100	143	class UninitializedParameter : public lemon::UninitializedParameter {
alpar@100	144	public:
alpar@100	145	virtual const char* what() const throw() {
alpar@209	146	return "lemon::Dfs::UninitializedParameter";
alpar@100	147	}
alpar@100	148	};
alpar@100	149
alpar@100	150	typedef TR Traits;
alpar@100	151	///The type of the underlying digraph.
alpar@100	152	typedef typename TR::Digraph Digraph;
alpar@100	153	///\e
alpar@100	154	typedef typename Digraph::Node Node;
alpar@100	155	///\e
alpar@100	156	typedef typename Digraph::NodeIt NodeIt;
alpar@100	157	///\e
alpar@100	158	typedef typename Digraph::Arc Arc;
alpar@100	159	///\e
alpar@100	160	typedef typename Digraph::OutArcIt OutArcIt;
alpar@209	161
alpar@100	162	///\brief The type of the map that stores the last
alpar@100	163	///arcs of the %DFS paths.
alpar@100	164	typedef typename TR::PredMap PredMap;
alpar@100	165	///The type of the map indicating which nodes are reached.
alpar@100	166	typedef typename TR::ReachedMap ReachedMap;
alpar@100	167	///The type of the map indicating which nodes are processed.
alpar@100	168	typedef typename TR::ProcessedMap ProcessedMap;
alpar@100	169	///The type of the map that stores the dists of the nodes.
alpar@100	170	typedef typename TR::DistMap DistMap;
alpar@100	171	private:
alpar@100	172	/// Pointer to the underlying digraph.
alpar@100	173	const Digraph *G;
alpar@100	174	///Pointer to the map of predecessors arcs.
alpar@100	175	PredMap *_pred;
alpar@100	176	///Indicates if \ref _pred is locally allocated (\c true) or not.
alpar@100	177	bool local_pred;
alpar@100	178	///Pointer to the map of distances.
alpar@100	179	DistMap *_dist;
alpar@100	180	///Indicates if \ref _dist is locally allocated (\c true) or not.
alpar@100	181	bool local_dist;
alpar@100	182	///Pointer to the map of reached status of the nodes.
alpar@100	183	ReachedMap *_reached;
alpar@100	184	///Indicates if \ref _reached is locally allocated (\c true) or not.
alpar@100	185	bool local_reached;
alpar@100	186	///Pointer to the map of processed status of the nodes.
alpar@100	187	ProcessedMap *_processed;
alpar@100	188	///Indicates if \ref _processed is locally allocated (\c true) or not.
alpar@100	189	bool local_processed;
alpar@100	190
alpar@100	191	std::vector<typename Digraph::OutArcIt> _stack;
alpar@100	192	int _stack_head;
alpar@100	193
alpar@100	194	///Creates the maps if necessary.
alpar@209	195
alpar@100	196	///\todo Better memory allocation (instead of new).
alpar@209	197	void create_maps()
alpar@100	198	{
alpar@100	199	if(!_pred) {
alpar@209	200	local_pred = true;
alpar@209	201	_pred = Traits::createPredMap(*G);
alpar@100	202	}
alpar@100	203	if(!_dist) {
alpar@209	204	local_dist = true;
alpar@209	205	_dist = Traits::createDistMap(*G);
alpar@100	206	}
alpar@100	207	if(!_reached) {
alpar@209	208	local_reached = true;
alpar@209	209	_reached = Traits::createReachedMap(*G);
alpar@100	210	}
alpar@100	211	if(!_processed) {
alpar@209	212	local_processed = true;
alpar@209	213	_processed = Traits::createProcessedMap(*G);
alpar@100	214	}
alpar@100	215	}
alpar@100	216
alpar@100	217	protected:
alpar@100	218
alpar@100	219	Dfs() {}
alpar@209	220
alpar@100	221	public:
alpar@100	222
alpar@100	223	typedef Dfs Create;
alpar@100	224
alpar@100	225	///\name Named template parameters
alpar@100	226
alpar@100	227	///@{
alpar@100	228
alpar@100	229	template <class T>
alpar@100	230	struct DefPredMapTraits : public Traits {
alpar@100	231	typedef T PredMap;
alpar@209	232	static PredMap *createPredMap(const Digraph &G)
alpar@100	233	{
alpar@209	234	throw UninitializedParameter();
alpar@100	235	}
alpar@100	236	};
alpar@100	237	///\brief \ref named-templ-param "Named parameter" for setting
alpar@100	238	///PredMap type
alpar@100	239	///
alpar@100	240	///\ref named-templ-param "Named parameter" for setting PredMap type
alpar@100	241	///
alpar@100	242	template <class T>
alpar@100	243	struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
alpar@100	244	typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
alpar@100	245	};
alpar@209	246
alpar@209	247
alpar@100	248	template <class T>
alpar@100	249	struct DefDistMapTraits : public Traits {
alpar@100	250	typedef T DistMap;
alpar@209	251	static DistMap *createDistMap(const Digraph &)
alpar@100	252	{
alpar@209	253	throw UninitializedParameter();
alpar@100	254	}
alpar@100	255	};
alpar@100	256	///\brief \ref named-templ-param "Named parameter" for setting
alpar@100	257	///DistMap type
alpar@100	258	///
alpar@100	259	///\ref named-templ-param "Named parameter" for setting DistMap
alpar@100	260	///type
alpar@100	261	template <class T>
alpar@100	262	struct DefDistMap {
alpar@100	263	typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
alpar@100	264	};
alpar@209	265
alpar@100	266	template <class T>
alpar@100	267	struct DefReachedMapTraits : public Traits {
alpar@100	268	typedef T ReachedMap;
alpar@209	269	static ReachedMap *createReachedMap(const Digraph &)
alpar@100	270	{
alpar@209	271	throw UninitializedParameter();
alpar@100	272	}
alpar@100	273	};
alpar@100	274	///\brief \ref named-templ-param "Named parameter" for setting
alpar@100	275	///ReachedMap type
alpar@100	276	///
alpar@100	277	///\ref named-templ-param "Named parameter" for setting ReachedMap type
alpar@100	278	///
alpar@100	279	template <class T>
alpar@100	280	struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
alpar@100	281	typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
alpar@100	282	};
alpar@100	283
alpar@100	284	template <class T>
alpar@100	285	struct DefProcessedMapTraits : public Traits {
alpar@100	286	typedef T ProcessedMap;
alpar@209	287	static ProcessedMap *createProcessedMap(const Digraph &)
alpar@100	288	{
alpar@209	289	throw UninitializedParameter();
alpar@100	290	}
alpar@100	291	};
alpar@100	292	///\brief \ref named-templ-param "Named parameter" for setting
alpar@100	293	///ProcessedMap type
alpar@100	294	///
alpar@100	295	///\ref named-templ-param "Named parameter" for setting ProcessedMap type
alpar@100	296	///
alpar@100	297	template <class T>
alpar@209	298	struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
alpar@100	299	typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
alpar@100	300	};
alpar@209	301
alpar@100	302	struct DefDigraphProcessedMapTraits : public Traits {
alpar@100	303	typedef typename Digraph::template NodeMap<bool> ProcessedMap;
alpar@209	304	static ProcessedMap *createProcessedMap(const Digraph &G)
alpar@100	305	{
alpar@209	306	return new ProcessedMap(G);
alpar@100	307	}
alpar@100	308	};
alpar@100	309	///\brief \ref named-templ-param "Named parameter"
alpar@100	310	///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
alpar@100	311	///
alpar@100	312	///\ref named-templ-param "Named parameter"
alpar@100	313	///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
alpar@100	314	///If you don't set it explicitely, it will be automatically allocated.
alpar@100	315	template <class T>
alpar@100	316	class DefProcessedMapToBeDefaultMap :
alpar@209	317	public Dfs< Digraph, DefDigraphProcessedMapTraits> {
alpar@100	318	typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
alpar@100	319	};
alpar@209	320
alpar@100	321	///@}
alpar@100	322
alpar@209	323	public:
alpar@209	324
alpar@100	325	///Constructor.
alpar@209	326
alpar@100	327	///\param _G the digraph the algorithm will run on.
alpar@100	328	///
alpar@100	329	Dfs(const Digraph& _G) :
alpar@100	330	G(&_G),
alpar@100	331	_pred(NULL), local_pred(false),
alpar@100	332	_dist(NULL), local_dist(false),
alpar@100	333	_reached(NULL), local_reached(false),
alpar@100	334	_processed(NULL), local_processed(false)
alpar@100	335	{ }
alpar@209	336
alpar@100	337	///Destructor.
alpar@209	338	~Dfs()
alpar@100	339	{
alpar@100	340	if(local_pred) delete _pred;
alpar@100	341	if(local_dist) delete _dist;
alpar@100	342	if(local_reached) delete _reached;
alpar@100	343	if(local_processed) delete _processed;
alpar@100	344	}
alpar@100	345
alpar@100	346	///Sets the map storing the predecessor arcs.
alpar@100	347
alpar@100	348	///Sets the map storing the predecessor arcs.
alpar@100	349	///If you don't use this function before calling \ref run(),
alpar@100	350	///it will allocate one. The destuctor deallocates this
alpar@100	351	///automatically allocated map, of course.
alpar@100	352	///\return <tt> (*this) </tt>
alpar@209	353	Dfs &predMap(PredMap &m)
alpar@100	354	{
alpar@100	355	if(local_pred) {
alpar@209	356	delete _pred;
alpar@209	357	local_pred=false;
alpar@100	358	}
alpar@100	359	_pred = &m;
alpar@100	360	return *this;
alpar@100	361	}
alpar@100	362
alpar@100	363	///Sets the map storing the distances calculated by the algorithm.
alpar@100	364
alpar@100	365	///Sets the map storing the distances calculated by the algorithm.
alpar@100	366	///If you don't use this function before calling \ref run(),
alpar@100	367	///it will allocate one. The destuctor deallocates this
alpar@100	368	///automatically allocated map, of course.
alpar@100	369	///\return <tt> (*this) </tt>
alpar@209	370	Dfs &distMap(DistMap &m)
alpar@100	371	{
alpar@100	372	if(local_dist) {
alpar@209	373	delete _dist;
alpar@209	374	local_dist=false;
alpar@100	375	}
alpar@100	376	_dist = &m;
alpar@100	377	return *this;
alpar@100	378	}
alpar@100	379
alpar@100	380	///Sets the map indicating if a node is reached.
alpar@100	381
alpar@100	382	///Sets the map indicating if a node is reached.
alpar@100	383	///If you don't use this function before calling \ref run(),
alpar@100	384	///it will allocate one. The destuctor deallocates this
alpar@100	385	///automatically allocated map, of course.
alpar@100	386	///\return <tt> (*this) </tt>
alpar@209	387	Dfs &reachedMap(ReachedMap &m)
alpar@100	388	{
alpar@100	389	if(local_reached) {
alpar@209	390	delete _reached;
alpar@209	391	local_reached=false;
alpar@100	392	}
alpar@100	393	_reached = &m;
alpar@100	394	return *this;
alpar@100	395	}
alpar@100	396
alpar@100	397	///Sets the map indicating if a node is processed.
alpar@100	398
alpar@100	399	///Sets the map indicating if a node is processed.
alpar@100	400	///If you don't use this function before calling \ref run(),
alpar@100	401	///it will allocate one. The destuctor deallocates this
alpar@100	402	///automatically allocated map, of course.
alpar@100	403	///\return <tt> (*this) </tt>
alpar@209	404	Dfs &processedMap(ProcessedMap &m)
alpar@100	405	{
alpar@100	406	if(local_processed) {
alpar@209	407	delete _processed;
alpar@209	408	local_processed=false;
alpar@100	409	}
alpar@100	410	_processed = &m;
alpar@100	411	return *this;
alpar@100	412	}
alpar@100	413
alpar@100	414	public:
alpar@100	415	///\name Execution control
alpar@100	416	///The simplest way to execute the algorithm is to use
alpar@100	417	///one of the member functions called \c run(...).
alpar@100	418	///\n
alpar@100	419	///If you need more control on the execution,
alpar@100	420	///first you must call \ref init(), then you can add a source node
alpar@100	421	///with \ref addSource().
alpar@100	422	///Finally \ref start() will perform the actual path
alpar@100	423	///computation.
alpar@100	424
alpar@100	425	///@{
alpar@100	426
alpar@100	427	///Initializes the internal data structures.
alpar@100	428
alpar@100	429	///Initializes the internal data structures.
alpar@100	430	///
alpar@100	431	void init()
alpar@100	432	{
alpar@100	433	create_maps();
alpar@100	434	_stack.resize(countNodes(*G));
alpar@100	435	_stack_head=-1;
alpar@100	436	for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
alpar@209	437	_pred->set(u,INVALID);
alpar@209	438	// _predNode->set(u,INVALID);
alpar@209	439	_reached->set(u,false);
alpar@209	440	_processed->set(u,false);
alpar@100	441	}
alpar@100	442	}
alpar@209	443
alpar@100	444	///Adds a new source node.
alpar@100	445
alpar@100	446	///Adds a new source node to the set of nodes to be processed.
alpar@100	447	///
alpar@100	448	///\warning dists are wrong (or at least strange)
alpar@100	449	///in case of multiple sources.
alpar@100	450	void addSource(Node s)
alpar@100	451	{
alpar@100	452	if(!(*_reached)[s])
alpar@209	453	{
alpar@209	454	_reached->set(s,true);
alpar@209	455	_pred->set(s,INVALID);
alpar@209	456	OutArcIt e(*G,s);
alpar@209	457	if(e!=INVALID) {
alpar@209	458	_stack[++_stack_head]=e;
alpar@209	459	_dist->set(s,_stack_head);
alpar@209	460	}
alpar@209	461	else {
alpar@209	462	_processed->set(s,true);
alpar@209	463	_dist->set(s,0);
alpar@209	464	}
alpar@209	465	}
alpar@100	466	}
alpar@209	467
alpar@100	468	///Processes the next arc.
alpar@100	469
alpar@100	470	///Processes the next arc.
alpar@100	471	///
alpar@100	472	///\return The processed arc.
alpar@100	473	///
alpar@100	474	///\pre The stack must not be empty!
alpar@100	475	Arc processNextArc()
alpar@209	476	{
alpar@100	477	Node m;
alpar@100	478	Arc e=_stack[_stack_head];
alpar@100	479	if(!(*_reached)[m=G->target(e)]) {
alpar@209	480	_pred->set(m,e);
alpar@209	481	_reached->set(m,true);
alpar@209	482	++_stack_head;
alpar@209	483	_stack[_stack_head] = OutArcIt(*G, m);
alpar@209	484	_dist->set(m,_stack_head);
alpar@100	485	}
alpar@100	486	else {
alpar@209	487	m=G->source(e);
alpar@209	488	++_stack[_stack_head];
alpar@100	489	}
alpar@100	490	while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
alpar@209	491	_processed->set(m,true);
alpar@209	492	--_stack_head;
alpar@209	493	if(_stack_head>=0) {
alpar@209	494	m=G->source(_stack[_stack_head]);
alpar@209	495	++_stack[_stack_head];
alpar@209	496	}
alpar@100	497	}
alpar@100	498	return e;
alpar@100	499	}
alpar@100	500	///Next arc to be processed.
alpar@100	501
alpar@100	502	///Next arc to be processed.
alpar@100	503	///
alpar@100	504	///\return The next arc to be processed or INVALID if the stack is
alpar@100	505	/// empty.
alpar@100	506	OutArcIt nextArc()
alpar@209	507	{
alpar@100	508	return _stack_head>=0?_stack[_stack_head]:INVALID;
alpar@100	509	}
alpar@100	510
alpar@100	511	///\brief Returns \c false if there are nodes
alpar@100	512	///to be processed in the queue
alpar@100	513	///
alpar@100	514	///Returns \c false if there are nodes
alpar@100	515	///to be processed in the queue
alpar@100	516	bool emptyQueue() { return _stack_head<0; }
alpar@100	517	///Returns the number of the nodes to be processed.
alpar@209	518
alpar@100	519	///Returns the number of the nodes to be processed in the queue.
alpar@100	520	int queueSize() { return _stack_head+1; }
alpar@209	521
alpar@100	522	///Executes the algorithm.
alpar@100	523
alpar@100	524	///Executes the algorithm.
alpar@100	525	///
alpar@100	526	///\pre init() must be called and at least one node should be added
alpar@100	527	///with addSource() before using this function.
alpar@100	528	///
alpar@100	529	///This method runs the %DFS algorithm from the root node(s)
alpar@100	530	///in order to
alpar@100	531	///compute the
alpar@100	532	///%DFS path to each node. The algorithm computes
alpar@100	533	///- The %DFS tree.
alpar@100	534	///- The distance of each node from the root(s) in the %DFS tree.
alpar@100	535	///
alpar@100	536	void start()
alpar@100	537	{
alpar@100	538	while ( !emptyQueue() ) processNextArc();
alpar@100	539	}
alpar@209	540
alpar@100	541	///Executes the algorithm until \c dest is reached.
alpar@100	542
alpar@100	543	///Executes the algorithm until \c dest is reached.
alpar@100	544	///
alpar@100	545	///\pre init() must be called and at least one node should be added
alpar@100	546	///with addSource() before using this function.
alpar@100	547	///
alpar@100	548	///This method runs the %DFS algorithm from the root node(s)
alpar@100	549	///in order to
alpar@100	550	///compute the
alpar@100	551	///%DFS path to \c dest. The algorithm computes
alpar@100	552	///- The %DFS path to \c dest.
alpar@100	553	///- The distance of \c dest from the root(s) in the %DFS tree.
alpar@100	554	///
alpar@100	555	void start(Node dest)
alpar@100	556	{
alpar@209	557	while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
alpar@209	558	processNextArc();
alpar@100	559	}
alpar@209	560
alpar@100	561	///Executes the algorithm until a condition is met.
alpar@100	562
alpar@100	563	///Executes the algorithm until a condition is met.
alpar@100	564	///
alpar@100	565	///\pre init() must be called and at least one node should be added
alpar@100	566	///with addSource() before using this function.
alpar@100	567	///
alpar@100	568	///\param em must be a bool (or convertible) arc map. The algorithm
alpar@100	569	///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
alpar@100	570	///
alpar@100	571	///\return The reached arc \c e with <tt>em[e]</tt> true or
alpar@100	572	///\c INVALID if no such arc was found.
alpar@100	573	///
alpar@100	574	///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
alpar@100	575	///not a node map.
alpar@100	576	template<class EM>
alpar@100	577	Arc start(const EM &em)
alpar@100	578	{
alpar@100	579	while ( !emptyQueue() && !em[_stack[_stack_head]] )
alpar@100	580	processNextArc();
alpar@100	581	return emptyQueue() ? INVALID : _stack[_stack_head];
alpar@100	582	}
alpar@100	583
alpar@100	584	///Runs %DFS algorithm to visit all nodes in the digraph.
alpar@209	585
alpar@100	586	///This method runs the %DFS algorithm in order to
alpar@100	587	///compute the
alpar@100	588	///%DFS path to each node. The algorithm computes
alpar@100	589	///- The %DFS tree.
alpar@100	590	///- The distance of each node from the root in the %DFS tree.
alpar@100	591	///
alpar@100	592	///\note d.run() is just a shortcut of the following code.
alpar@100	593	///\code
alpar@100	594	/// d.init();
alpar@100	595	/// for (NodeIt it(digraph); it != INVALID; ++it) {
alpar@100	596	/// if (!d.reached(it)) {
alpar@100	597	/// d.addSource(it);
alpar@100	598	/// d.start();
alpar@100	599	/// }
alpar@100	600	/// }
alpar@100	601	///\endcode
alpar@100	602	void run() {
alpar@100	603	init();
alpar@100	604	for (NodeIt it(*G); it != INVALID; ++it) {
alpar@100	605	if (!reached(it)) {
alpar@100	606	addSource(it);
alpar@100	607	start();
alpar@100	608	}
alpar@100	609	}
alpar@100	610	}
alpar@100	611
alpar@100	612	///Runs %DFS algorithm from node \c s.
alpar@209	613
alpar@100	614	///This method runs the %DFS algorithm from a root node \c s
alpar@100	615	///in order to
alpar@100	616	///compute the
alpar@100	617	///%DFS path to each node. The algorithm computes
alpar@100	618	///- The %DFS tree.
alpar@100	619	///- The distance of each node from the root in the %DFS tree.
alpar@100	620	///
alpar@100	621	///\note d.run(s) is just a shortcut of the following code.
alpar@100	622	///\code
alpar@100	623	/// d.init();
alpar@100	624	/// d.addSource(s);
alpar@100	625	/// d.start();
alpar@100	626	///\endcode
alpar@100	627	void run(Node s) {
alpar@100	628	init();
alpar@100	629	addSource(s);
alpar@100	630	start();
alpar@100	631	}
alpar@209	632
alpar@100	633	///Finds the %DFS path between \c s and \c t.
alpar@209	634
alpar@100	635	///Finds the %DFS path between \c s and \c t.
alpar@100	636	///
alpar@100	637	///\return The length of the %DFS s---t path if there exists one,
alpar@100	638	///0 otherwise.
alpar@100	639	///\note Apart from the return value, d.run(s,t) is
alpar@100	640	///just a shortcut of the following code.
alpar@100	641	///\code
alpar@100	642	/// d.init();
alpar@100	643	/// d.addSource(s);
alpar@100	644	/// d.start(t);
alpar@100	645	///\endcode
alpar@100	646	int run(Node s,Node t) {
alpar@100	647	init();
alpar@100	648	addSource(s);
alpar@100	649	start(t);
alpar@100	650	return reached(t)?_stack_head+1:0;
alpar@100	651	}
alpar@209	652
alpar@100	653	///@}
alpar@100	654
alpar@100	655	///\name Query Functions
alpar@100	656	///The result of the %DFS algorithm can be obtained using these
alpar@100	657	///functions.\n
alpar@100	658	///Before the use of these functions,
alpar@100	659	///either run() or start() must be called.
alpar@209	660
alpar@100	661	///@{
alpar@100	662
alpar@100	663	typedef PredMapPath<Digraph, PredMap> Path;
alpar@100	664
alpar@100	665	///Gives back the shortest path.
alpar@209	666
alpar@100	667	///Gives back the shortest path.
alpar@100	668	///\pre The \c t should be reachable from the source.
alpar@209	669	Path path(Node t)
alpar@100	670	{
alpar@100	671	return Path(G, _pred, t);
alpar@100	672	}
alpar@100	673
alpar@100	674	///The distance of a node from the root(s).
alpar@100	675
alpar@100	676	///Returns the distance of a node from the root(s).
alpar@100	677	///\pre \ref run() must be called before using this function.
alpar@209	678	///\warning If node \c v is unreachable from the root(s) then the return
alpar@100	679	///value of this funcion is undefined.
alpar@100	680	int dist(Node v) const { return (*_dist)[v]; }
alpar@100	681
alpar@100	682	///Returns the 'previous arc' of the %DFS tree.
alpar@100	683
alpar@100	684	///For a node \c v it returns the 'previous arc'
alpar@100	685	///of the %DFS path,
alpar@100	686	///i.e. it returns the last arc of a %DFS path from the root(s) to \c
alpar@100	687	///v. It is \ref INVALID
alpar@100	688	///if \c v is unreachable from the root(s) or \c v is a root. The
alpar@100	689	///%DFS tree used here is equal to the %DFS tree used in
alpar@100	690	///\ref predNode().
alpar@100	691	///\pre Either \ref run() or \ref start() must be called before using
alpar@100	692	///this function.
alpar@100	693	Arc predArc(Node v) const { return (*_pred)[v];}
alpar@100	694
alpar@100	695	///Returns the 'previous node' of the %DFS tree.
alpar@100	696
alpar@100	697	///For a node \c v it returns the 'previous node'
alpar@100	698	///of the %DFS tree,
alpar@100	699	///i.e. it returns the last but one node from a %DFS path from the
alpar@100	700	///root(s) to \c v.
alpar@100	701	///It is INVALID if \c v is unreachable from the root(s) or
alpar@100	702	///if \c v itself a root.
alpar@100	703	///The %DFS tree used here is equal to the %DFS
alpar@100	704	///tree used in \ref predArc().
alpar@100	705	///\pre Either \ref run() or \ref start() must be called before
alpar@100	706	///using this function.
alpar@100	707	Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
alpar@209	708	G->source((*_pred)[v]); }
alpar@209	709
alpar@100	710	///Returns a reference to the NodeMap of distances.
alpar@100	711
alpar@100	712	///Returns a reference to the NodeMap of distances.
alpar@100	713	///\pre Either \ref run() or \ref init() must
alpar@100	714	///be called before using this function.
alpar@100	715	const DistMap &distMap() const { return *_dist;}
alpar@209	716
alpar@100	717	///Returns a reference to the %DFS arc-tree map.
alpar@100	718
alpar@100	719	///Returns a reference to the NodeMap of the arcs of the
alpar@100	720	///%DFS tree.
alpar@100	721	///\pre Either \ref run() or \ref init()
alpar@100	722	///must be called before using this function.
alpar@100	723	const PredMap &predMap() const { return *_pred;}
alpar@209	724
alpar@100	725	///Checks if a node is reachable from the root.
alpar@100	726
alpar@100	727	///Returns \c true if \c v is reachable from the root(s).
alpar@100	728	///\warning The source nodes are inditated as unreachable.
alpar@100	729	///\pre Either \ref run() or \ref start()
alpar@100	730	///must be called before using this function.
alpar@100	731	///
alpar@100	732	bool reached(Node v) { return (*_reached)[v]; }
alpar@209	733
alpar@100	734	///@}
alpar@100	735	};
alpar@100	736
alpar@100	737	///Default traits class of Dfs function.
alpar@100	738
alpar@100	739	///Default traits class of Dfs function.
kpeter@157	740	///\tparam GR Digraph type.
alpar@100	741	template<class GR>
alpar@100	742	struct DfsWizardDefaultTraits
alpar@100	743	{
alpar@209	744	///The digraph type the algorithm runs on.
alpar@100	745	typedef GR Digraph;
alpar@100	746	///\brief The type of the map that stores the last
alpar@100	747	///arcs of the %DFS paths.
alpar@209	748	///
alpar@100	749	///The type of the map that stores the last
alpar@100	750	///arcs of the %DFS paths.
alpar@100	751	///It must meet the \ref concepts::WriteMap "WriteMap" concept.
alpar@100	752	///
alpar@100	753	typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
alpar@100	754	///Instantiates a PredMap.
alpar@209	755
alpar@209	756	///This function instantiates a \ref PredMap.
alpar@100	757	///\param g is the digraph, to which we would like to define the PredMap.
alpar@100	758	///\todo The digraph alone may be insufficient to initialize
alpar@100	759	#ifdef DOXYGEN
alpar@209	760	static PredMap *createPredMap(const GR &g)
alpar@100	761	#else
alpar@209	762	static PredMap *createPredMap(const GR &)
alpar@100	763	#endif
alpar@100	764	{
alpar@100	765	return new PredMap();
alpar@100	766	}
alpar@100	767
alpar@100	768	///The type of the map that indicates which nodes are processed.
alpar@209	769
alpar@100	770	///The type of the map that indicates which nodes are processed.
alpar@100	771	///It must meet the \ref concepts::WriteMap "WriteMap" concept.
alpar@100	772	///\todo named parameter to set this type, function to read and write.
alpar@100	773	typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
alpar@100	774	///Instantiates a ProcessedMap.
alpar@209	775
alpar@209	776	///This function instantiates a \ref ProcessedMap.
alpar@100	777	///\param g is the digraph, to which
alpar@100	778	///we would like to define the \ref ProcessedMap
alpar@100	779	#ifdef DOXYGEN
alpar@100	780	static ProcessedMap *createProcessedMap(const GR &g)
alpar@100	781	#else
alpar@100	782	static ProcessedMap *createProcessedMap(const GR &)
alpar@100	783	#endif
alpar@100	784	{
alpar@100	785	return new ProcessedMap();
alpar@100	786	}
alpar@100	787	///The type of the map that indicates which nodes are reached.
alpar@209	788
alpar@100	789	///The type of the map that indicates which nodes are reached.
alpar@100	790	///It must meet the \ref concepts::WriteMap "WriteMap" concept.
alpar@100	791	///\todo named parameter to set this type, function to read and write.
alpar@100	792	typedef typename Digraph::template NodeMap<bool> ReachedMap;
alpar@100	793	///Instantiates a ReachedMap.
alpar@209	794
alpar@209	795	///This function instantiates a \ref ReachedMap.
alpar@100	796	///\param G is the digraph, to which
alpar@100	797	///we would like to define the \ref ReachedMap.
alpar@100	798	static ReachedMap *createReachedMap(const GR &G)
alpar@100	799	{
alpar@100	800	return new ReachedMap(G);
alpar@100	801	}
alpar@100	802	///The type of the map that stores the dists of the nodes.
alpar@209	803
alpar@100	804	///The type of the map that stores the dists of the nodes.
alpar@100	805	///It must meet the \ref concepts::WriteMap "WriteMap" concept.
alpar@100	806	///
alpar@100	807	typedef NullMap<typename Digraph::Node,int> DistMap;
alpar@100	808	///Instantiates a DistMap.
alpar@209	809
alpar@209	810	///This function instantiates a \ref DistMap.
alpar@210	811	///\param g is the digraph, to which we would like to define
alpar@210	812	///the \ref DistMap
alpar@100	813	#ifdef DOXYGEN
alpar@100	814	static DistMap *createDistMap(const GR &g)
alpar@100	815	#else
alpar@100	816	static DistMap *createDistMap(const GR &)
alpar@100	817	#endif
alpar@100	818	{
alpar@100	819	return new DistMap();
alpar@100	820	}
alpar@100	821	};
alpar@209	822
alpar@100	823	/// Default traits used by \ref DfsWizard
alpar@100	824
alpar@100	825	/// To make it easier to use Dfs algorithm
alpar@100	826	///we have created a wizard class.
alpar@100	827	/// This \ref DfsWizard class needs default traits,
alpar@100	828	///as well as the \ref Dfs class.
alpar@100	829	/// The \ref DfsWizardBase is a class to be the default traits of the
alpar@100	830	/// \ref DfsWizard class.
alpar@100	831	template<class GR>
alpar@100	832	class DfsWizardBase : public DfsWizardDefaultTraits<GR>
alpar@100	833	{
alpar@100	834
alpar@100	835	typedef DfsWizardDefaultTraits<GR> Base;
alpar@100	836	protected:
alpar@100	837	/// Type of the nodes in the digraph.
alpar@100	838	typedef typename Base::Digraph::Node Node;
alpar@100	839
alpar@100	840	/// Pointer to the underlying digraph.
alpar@100	841	void *_g;
alpar@100	842	///Pointer to the map of reached nodes.
alpar@100	843	void *_reached;
alpar@100	844	///Pointer to the map of processed nodes.
alpar@100	845	void *_processed;
alpar@100	846	///Pointer to the map of predecessors arcs.
alpar@100	847	void *_pred;
alpar@100	848	///Pointer to the map of distances.
alpar@100	849	void *_dist;
alpar@100	850	///Pointer to the source node.
alpar@100	851	Node _source;
alpar@209	852
alpar@100	853	public:
alpar@100	854	/// Constructor.
alpar@209	855
alpar@100	856	/// This constructor does not require parameters, therefore it initiates
alpar@100	857	/// all of the attributes to default values (0, INVALID).
alpar@100	858	DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
alpar@209	859	_dist(0), _source(INVALID) {}
alpar@100	860
alpar@100	861	/// Constructor.
alpar@209	862
alpar@100	863	/// This constructor requires some parameters,
alpar@100	864	/// listed in the parameters list.
alpar@100	865	/// Others are initiated to 0.
alpar@100	866	/// \param g is the initial value of \ref _g
alpar@100	867	/// \param s is the initial value of \ref _source
alpar@100	868	DfsWizardBase(const GR &g, Node s=INVALID) :
alpar@209	869	_g(reinterpret_cast<void>(const_cast<GR>(&g))),
alpar@100	870	_reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
alpar@100	871
alpar@100	872	};
alpar@209	873
alpar@100	874	/// A class to make the usage of the Dfs algorithm easier
alpar@100	875
alpar@100	876	/// This class is created to make it easier to use the Dfs algorithm.
alpar@100	877	/// It uses the functions and features of the plain \ref Dfs,
alpar@100	878	/// but it is much simpler to use it.
alpar@100	879	///
alpar@100	880	/// Simplicity means that the way to change the types defined
alpar@100	881	/// in the traits class is based on functions that returns the new class
alpar@100	882	/// and not on templatable built-in classes.
alpar@100	883	/// When using the plain \ref Dfs
alpar@100	884	/// the new class with the modified type comes from
alpar@100	885	/// the original class by using the ::
alpar@100	886	/// operator. In the case of \ref DfsWizard only
alpar@100	887	/// a function have to be called and it will
alpar@100	888	/// return the needed class.
alpar@100	889	///
alpar@100	890	/// It does not have own \ref run method. When its \ref run method is called
alpar@100	891	/// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
alpar@100	892	/// method of it.
alpar@100	893	template<class TR>
alpar@100	894	class DfsWizard : public TR
alpar@100	895	{
alpar@100	896	typedef TR Base;
alpar@100	897
alpar@100	898	///The type of the underlying digraph.
alpar@100	899	typedef typename TR::Digraph Digraph;
alpar@100	900	//\e
alpar@100	901	typedef typename Digraph::Node Node;
alpar@100	902	//\e
alpar@100	903	typedef typename Digraph::NodeIt NodeIt;
alpar@100	904	//\e
alpar@100	905	typedef typename Digraph::Arc Arc;
alpar@100	906	//\e
alpar@100	907	typedef typename Digraph::OutArcIt OutArcIt;
alpar@209	908
alpar@100	909	///\brief The type of the map that stores
alpar@100	910	///the reached nodes
alpar@100	911	typedef typename TR::ReachedMap ReachedMap;
alpar@100	912	///\brief The type of the map that stores
alpar@100	913	///the processed nodes
alpar@100	914	typedef typename TR::ProcessedMap ProcessedMap;
alpar@100	915	///\brief The type of the map that stores the last
alpar@100	916	///arcs of the %DFS paths.
alpar@100	917	typedef typename TR::PredMap PredMap;
alpar@100	918	///The type of the map that stores the distances of the nodes.
alpar@100	919	typedef typename TR::DistMap DistMap;
alpar@100	920
alpar@100	921	public:
alpar@100	922	/// Constructor.
alpar@100	923	DfsWizard() : TR() {}
alpar@100	924
alpar@100	925	/// Constructor that requires parameters.
alpar@100	926
alpar@100	927	/// Constructor that requires parameters.
alpar@100	928	/// These parameters will be the default values for the traits class.
alpar@100	929	DfsWizard(const Digraph &g, Node s=INVALID) :
alpar@100	930	TR(g,s) {}
alpar@100	931
alpar@100	932	///Copy constructor
alpar@100	933	DfsWizard(const TR &b) : TR(b) {}
alpar@100	934
alpar@100	935	~DfsWizard() {}
alpar@100	936
alpar@100	937	///Runs Dfs algorithm from a given node.
alpar@209	938
alpar@100	939	///Runs Dfs algorithm from a given node.
alpar@100	940	///The node can be given by the \ref source function.
alpar@100	941	void run()
alpar@100	942	{
alpar@100	943	if(Base::_source==INVALID) throw UninitializedParameter();
alpar@100	944	Dfs<Digraph,TR> alg(reinterpret_cast<const Digraph>(Base::_g));
alpar@209	945	if(Base::_reached)
alpar@100	946	alg.reachedMap(reinterpret_cast<ReachedMap>(Base::_reached));
alpar@209	947	if(Base::_processed)
alpar@100	948	alg.processedMap(reinterpret_cast<ProcessedMap>(Base::_processed));
alpar@209	949	if(Base::_pred)
alpar@100	950	alg.predMap(reinterpret_cast<PredMap>(Base::_pred));
alpar@209	951	if(Base::_dist)
alpar@100	952	alg.distMap(reinterpret_cast<DistMap>(Base::_dist));
alpar@100	953	alg.run(Base::_source);
alpar@100	954	}
alpar@100	955
alpar@100	956	///Runs Dfs algorithm from the given node.
alpar@100	957
alpar@100	958	///Runs Dfs algorithm from the given node.
alpar@100	959	///\param s is the given source.
alpar@100	960	void run(Node s)
alpar@100	961	{
alpar@100	962	Base::_source=s;
alpar@100	963	run();
alpar@100	964	}
alpar@100	965
alpar@100	966	template<class T>
alpar@100	967	struct DefPredMapBase : public Base {
alpar@100	968	typedef T PredMap;
alpar@100	969	static PredMap *createPredMap(const Digraph &) { return 0; };
alpar@100	970	DefPredMapBase(const TR &b) : TR(b) {}
alpar@100	971	};
alpar@209	972
alpar@100	973	///\brief \ref named-templ-param "Named parameter"
alpar@100	974	///function for setting PredMap type
alpar@100	975	///
alpar@100	976	/// \ref named-templ-param "Named parameter"
alpar@100	977	///function for setting PredMap type
alpar@100	978	///
alpar@100	979	template<class T>
alpar@209	980	DfsWizard<DefPredMapBase<T> > predMap(const T &t)
alpar@100	981	{
alpar@100	982	Base::_pred=reinterpret_cast<void>(const_cast<T>(&t));
alpar@100	983	return DfsWizard<DefPredMapBase<T> >(*this);
alpar@100	984	}
alpar@209	985
alpar@209	986
alpar@100	987	template<class T>
alpar@100	988	struct DefReachedMapBase : public Base {
alpar@100	989	typedef T ReachedMap;
alpar@100	990	static ReachedMap *createReachedMap(const Digraph &) { return 0; };
alpar@100	991	DefReachedMapBase(const TR &b) : TR(b) {}
alpar@100	992	};
alpar@209	993
alpar@100	994	///\brief \ref named-templ-param "Named parameter"
alpar@100	995	///function for setting ReachedMap
alpar@100	996	///
alpar@100	997	/// \ref named-templ-param "Named parameter"
alpar@100	998	///function for setting ReachedMap
alpar@100	999	///
alpar@100	1000	template<class T>
alpar@209	1001	DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
alpar@100	1002	{
deba@158	1003	Base::_reached=reinterpret_cast<void>(const_cast<T>(&t));
alpar@100	1004	return DfsWizard<DefReachedMapBase<T> >(*this);
alpar@100	1005	}
alpar@209	1006
alpar@100	1007
alpar@100	1008	template<class T>
alpar@100	1009	struct DefProcessedMapBase : public Base {
alpar@100	1010	typedef T ProcessedMap;
alpar@100	1011	static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
alpar@100	1012	DefProcessedMapBase(const TR &b) : TR(b) {}
alpar@100	1013	};
alpar@209	1014
alpar@100	1015	///\brief \ref named-templ-param "Named parameter"
alpar@100	1016	///function for setting ProcessedMap
alpar@100	1017	///
alpar@100	1018	/// \ref named-templ-param "Named parameter"
alpar@100	1019	///function for setting ProcessedMap
alpar@100	1020	///
alpar@100	1021	template<class T>
alpar@209	1022	DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
alpar@100	1023	{
deba@158	1024	Base::_processed=reinterpret_cast<void>(const_cast<T>(&t));
alpar@100	1025	return DfsWizard<DefProcessedMapBase<T> >(*this);
alpar@100	1026	}
alpar@209	1027
alpar@100	1028	template<class T>
alpar@100	1029	struct DefDistMapBase : public Base {
alpar@100	1030	typedef T DistMap;
alpar@100	1031	static DistMap *createDistMap(const Digraph &) { return 0; };
alpar@100	1032	DefDistMapBase(const TR &b) : TR(b) {}
alpar@100	1033	};
alpar@209	1034
alpar@100	1035	///\brief \ref named-templ-param "Named parameter"
alpar@100	1036	///function for setting DistMap type
alpar@100	1037	///
alpar@100	1038	/// \ref named-templ-param "Named parameter"
alpar@100	1039	///function for setting DistMap type
alpar@100	1040	///
alpar@100	1041	template<class T>
alpar@209	1042	DfsWizard<DefDistMapBase<T> > distMap(const T &t)
alpar@100	1043	{
alpar@100	1044	Base::_dist=reinterpret_cast<void>(const_cast<T>(&t));
alpar@100	1045	return DfsWizard<DefDistMapBase<T> >(*this);
alpar@100	1046	}
alpar@209	1047
alpar@100	1048	/// Sets the source node, from which the Dfs algorithm runs.
alpar@100	1049
alpar@100	1050	/// Sets the source node, from which the Dfs algorithm runs.
alpar@100	1051	/// \param s is the source node.
alpar@209	1052	DfsWizard<TR> &source(Node s)
alpar@100	1053	{
alpar@100	1054	Base::_source=s;
alpar@100	1055	return *this;
alpar@100	1056	}
alpar@209	1057
alpar@100	1058	};
alpar@209	1059
alpar@100	1060	///Function type interface for Dfs algorithm.
alpar@100	1061
alpar@100	1062	///\ingroup search
alpar@100	1063	///Function type interface for Dfs algorithm.
alpar@100	1064	///
alpar@100	1065	///This function also has several
alpar@100	1066	///\ref named-templ-func-param "named parameters",
alpar@100	1067	///they are declared as the members of class \ref DfsWizard.
alpar@100	1068	///The following
alpar@100	1069	///example shows how to use these parameters.
alpar@100	1070	///\code
alpar@100	1071	/// dfs(g,source).predMap(preds).run();
alpar@100	1072	///\endcode
alpar@100	1073	///\warning Don't forget to put the \ref DfsWizard::run() "run()"
alpar@100	1074	///to the end of the parameter list.
alpar@100	1075	///\sa DfsWizard
alpar@100	1076	///\sa Dfs
alpar@100	1077	template<class GR>
alpar@100	1078	DfsWizard<DfsWizardBase<GR> >
alpar@100	1079	dfs(const GR &g,typename GR::Node s=INVALID)
alpar@100	1080	{
alpar@100	1081	return DfsWizard<DfsWizardBase<GR> >(g,s);
alpar@100	1082	}
alpar@100	1083
alpar@100	1084	#ifdef DOXYGEN
alpar@100	1085	/// \brief Visitor class for dfs.
alpar@209	1086	///
alpar@209	1087	/// It gives a simple interface for a functional interface for dfs
alpar@209	1088	/// traversal. The traversal on a linear data structure.
alpar@100	1089	template <typename _Digraph>
alpar@100	1090	struct DfsVisitor {
alpar@100	1091	typedef _Digraph Digraph;
alpar@100	1092	typedef typename Digraph::Arc Arc;
alpar@100	1093	typedef typename Digraph::Node Node;
alpar@100	1094	/// \brief Called when the arc reach a node.
alpar@209	1095	///
alpar@100	1096	/// It is called when the dfs find an arc which target is not
alpar@100	1097	/// reached yet.
alpar@100	1098	void discover(const Arc& arc) {}
alpar@100	1099	/// \brief Called when the node reached first time.
alpar@209	1100	///
alpar@100	1101	/// It is Called when the node reached first time.
alpar@100	1102	void reach(const Node& node) {}
alpar@100	1103	/// \brief Called when we step back on an arc.
alpar@209	1104	///
alpar@100	1105	/// It is called when the dfs should step back on the arc.
alpar@100	1106	void backtrack(const Arc& arc) {}
alpar@100	1107	/// \brief Called when we step back from the node.
alpar@209	1108	///
alpar@100	1109	/// It is called when we step back from the node.
alpar@100	1110	void leave(const Node& node) {}
alpar@209	1111	/// \brief Called when the arc examined but target of the arc
alpar@100	1112	/// already discovered.
alpar@209	1113	///
alpar@209	1114	/// It called when the arc examined but the target of the arc
alpar@100	1115	/// already discovered.
alpar@100	1116	void examine(const Arc& arc) {}
alpar@100	1117	/// \brief Called for the source node of the dfs.
alpar@209	1118	///
alpar@100	1119	/// It is called for the source node of the dfs.
alpar@100	1120	void start(const Node& node) {}
alpar@100	1121	/// \brief Called when we leave the source node of the dfs.
alpar@209	1122	///
alpar@100	1123	/// It is called when we leave the source node of the dfs.
alpar@100	1124	void stop(const Node& node) {}
alpar@100	1125
alpar@100	1126	};
alpar@100	1127	#else
alpar@100	1128	template <typename _Digraph>
alpar@100	1129	struct DfsVisitor {
alpar@100	1130	typedef _Digraph Digraph;
alpar@100	1131	typedef typename Digraph::Arc Arc;
alpar@100	1132	typedef typename Digraph::Node Node;
alpar@100	1133	void discover(const Arc&) {}
alpar@100	1134	void reach(const Node&) {}
alpar@100	1135	void backtrack(const Arc&) {}
alpar@100	1136	void leave(const Node&) {}
alpar@100	1137	void examine(const Arc&) {}
alpar@100	1138	void start(const Node&) {}
alpar@100	1139	void stop(const Node&) {}
alpar@100	1140
alpar@100	1141	template <typename _Visitor>
alpar@100	1142	struct Constraints {
alpar@100	1143	void constraints() {
alpar@209	1144	Arc arc;
alpar@209	1145	Node node;
alpar@209	1146	visitor.discover(arc);
alpar@209	1147	visitor.reach(node);
alpar@209	1148	visitor.backtrack(arc);
alpar@209	1149	visitor.leave(node);
alpar@209	1150	visitor.examine(arc);
alpar@209	1151	visitor.start(node);
alpar@209	1152	visitor.stop(arc);
alpar@100	1153	}
alpar@100	1154	_Visitor& visitor;
alpar@100	1155	};
alpar@100	1156	};
alpar@100	1157	#endif
alpar@100	1158
alpar@100	1159	/// \brief Default traits class of DfsVisit class.
alpar@100	1160	///
alpar@100	1161	/// Default traits class of DfsVisit class.
kpeter@157	1162	/// \tparam _Digraph Digraph type.
alpar@100	1163	template<class _Digraph>
alpar@100	1164	struct DfsVisitDefaultTraits {
alpar@100	1165
alpar@209	1166	/// \brief The digraph type the algorithm runs on.
alpar@100	1167	typedef _Digraph Digraph;
alpar@100	1168
alpar@100	1169	/// \brief The type of the map that indicates which nodes are reached.
alpar@209	1170	///
alpar@100	1171	/// The type of the map that indicates which nodes are reached.
alpar@100	1172	/// It must meet the \ref concepts::WriteMap "WriteMap" concept.
alpar@100	1173	/// \todo named parameter to set this type, function to read and write.
alpar@100	1174	typedef typename Digraph::template NodeMap<bool> ReachedMap;
alpar@100	1175
alpar@100	1176	/// \brief Instantiates a ReachedMap.
alpar@100	1177	///
alpar@209	1178	/// This function instantiates a \ref ReachedMap.
alpar@100	1179	/// \param digraph is the digraph, to which
alpar@100	1180	/// we would like to define the \ref ReachedMap.
alpar@100	1181	static ReachedMap *createReachedMap(const Digraph &digraph) {
alpar@100	1182	return new ReachedMap(digraph);
alpar@100	1183	}
alpar@100	1184
alpar@100	1185	};
alpar@209	1186
alpar@100	1187	/// %DFS Visit algorithm class.
alpar@209	1188
alpar@100	1189	/// \ingroup search
alpar@100	1190	/// This class provides an efficient implementation of the %DFS algorithm
alpar@100	1191	/// with visitor interface.
alpar@100	1192	///
alpar@100	1193	/// The %DfsVisit class provides an alternative interface to the Dfs
alpar@100	1194	/// class. It works with callback mechanism, the DfsVisit object calls
alpar@209	1195	/// on every dfs event the \c Visitor class member functions.
alpar@100	1196	///
alpar@210	1197	/// \tparam _Digraph The digraph type the algorithm runs on.
alpar@210	1198	/// The default value is
alpar@100	1199	/// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
alpar@100	1200	/// is only passed to \ref DfsDefaultTraits.
alpar@209	1201	/// \tparam _Visitor The Visitor object for the algorithm. The
alpar@100	1202	/// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
alpar@100	1203	/// does not observe the Dfs events. If you want to observe the dfs
alpar@100	1204	/// events you should implement your own Visitor class.
alpar@209	1205	/// \tparam _Traits Traits class to set various data types used by the
alpar@100	1206	/// algorithm. The default traits class is
alpar@100	1207	/// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
alpar@100	1208	/// See \ref DfsVisitDefaultTraits for the documentation of
alpar@100	1209	/// a Dfs visit traits class.
alpar@100	1210	///
alpar@100	1211	/// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
alpar@100	1212	#ifdef DOXYGEN
alpar@100	1213	template <typename _Digraph, typename _Visitor, typename _Traits>
alpar@100	1214	#else
alpar@100	1215	template <typename _Digraph = ListDigraph,
alpar@209	1216	typename _Visitor = DfsVisitor<_Digraph>,
alpar@209	1217	typename _Traits = DfsDefaultTraits<_Digraph> >
alpar@100	1218	#endif
alpar@100	1219	class DfsVisit {
alpar@100	1220	public:
alpar@209	1221
alpar@100	1222	/// \brief \ref Exception for uninitialized parameters.
alpar@100	1223	///
alpar@100	1224	/// This error represents problems in the initialization
alpar@100	1225	/// of the parameters of the algorithms.
alpar@100	1226	class UninitializedParameter : public lemon::UninitializedParameter {
alpar@100	1227	public:
alpar@209	1228	virtual const char* what() const throw()
alpar@100	1229	{
alpar@209	1230	return "lemon::DfsVisit::UninitializedParameter";
alpar@100	1231	}
alpar@100	1232	};
alpar@100	1233
alpar@100	1234	typedef _Traits Traits;
alpar@100	1235
alpar@100	1236	typedef typename Traits::Digraph Digraph;
alpar@100	1237
alpar@100	1238	typedef _Visitor Visitor;
alpar@100	1239
alpar@100	1240	///The type of the map indicating which nodes are reached.
alpar@100	1241	typedef typename Traits::ReachedMap ReachedMap;
alpar@100	1242
alpar@100	1243	private:
alpar@100	1244
alpar@100	1245	typedef typename Digraph::Node Node;
alpar@100	1246	typedef typename Digraph::NodeIt NodeIt;
alpar@100	1247	typedef typename Digraph::Arc Arc;
alpar@100	1248	typedef typename Digraph::OutArcIt OutArcIt;
alpar@100	1249
alpar@100	1250	/// Pointer to the underlying digraph.
alpar@100	1251	const Digraph *_digraph;
alpar@100	1252	/// Pointer to the visitor object.
alpar@100	1253	Visitor *_visitor;
alpar@100	1254	///Pointer to the map of reached status of the nodes.
alpar@100	1255	ReachedMap *_reached;
alpar@100	1256	///Indicates if \ref _reached is locally allocated (\c true) or not.
alpar@100	1257	bool local_reached;
alpar@100	1258
alpar@100	1259	std::vector<typename Digraph::Arc> _stack;
alpar@100	1260	int _stack_head;
alpar@100	1261
alpar@100	1262	/// \brief Creates the maps if necessary.
alpar@100	1263	///
alpar@100	1264	/// Creates the maps if necessary.
alpar@100	1265	void create_maps() {
alpar@100	1266	if(!_reached) {
alpar@209	1267	local_reached = true;
alpar@209	1268	_reached = Traits::createReachedMap(*_digraph);
alpar@100	1269	}
alpar@100	1270	}
alpar@100	1271
alpar@100	1272	protected:
alpar@100	1273
alpar@100	1274	DfsVisit() {}
alpar@209	1275
alpar@100	1276	public:
alpar@100	1277
alpar@100	1278	typedef DfsVisit Create;
alpar@100	1279
alpar@100	1280	/// \name Named template parameters
alpar@100	1281
alpar@100	1282	///@{
alpar@100	1283	template <class T>
alpar@100	1284	struct DefReachedMapTraits : public Traits {
alpar@100	1285	typedef T ReachedMap;
alpar@100	1286	static ReachedMap *createReachedMap(const Digraph &digraph) {
alpar@209	1287	throw UninitializedParameter();
alpar@100	1288	}
alpar@100	1289	};
alpar@209	1290	/// \brief \ref named-templ-param "Named parameter" for setting
alpar@100	1291	/// ReachedMap type
alpar@100	1292	///
alpar@100	1293	/// \ref named-templ-param "Named parameter" for setting ReachedMap type
alpar@100	1294	template <class T>
alpar@100	1295	struct DefReachedMap : public DfsVisit< Digraph, Visitor,
alpar@209	1296	DefReachedMapTraits<T> > {
alpar@100	1297	typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
alpar@100	1298	};
alpar@100	1299	///@}
alpar@100	1300
alpar@209	1301	public:
alpar@209	1302
alpar@100	1303	/// \brief Constructor.
alpar@100	1304	///
alpar@100	1305	/// Constructor.
alpar@100	1306	///
alpar@100	1307	/// \param digraph the digraph the algorithm will run on.
alpar@100	1308	/// \param visitor The visitor of the algorithm.
alpar@100	1309	///
alpar@209	1310	DfsVisit(const Digraph& digraph, Visitor& visitor)
alpar@100	1311	: _digraph(&digraph), _visitor(&visitor),
alpar@209	1312	_reached(0), local_reached(false) {}
alpar@209	1313
alpar@100	1314	/// \brief Destructor.
alpar@100	1315	///
alpar@100	1316	/// Destructor.
alpar@100	1317	~DfsVisit() {
alpar@100	1318	if(local_reached) delete _reached;
alpar@100	1319	}
alpar@100	1320
alpar@100	1321	/// \brief Sets the map indicating if a node is reached.
alpar@100	1322	///
alpar@100	1323	/// Sets the map indicating if a node is reached.
alpar@100	1324	/// If you don't use this function before calling \ref run(),
alpar@100	1325	/// it will allocate one. The destuctor deallocates this
alpar@100	1326	/// automatically allocated map, of course.
alpar@100	1327	/// \return <tt> (*this) </tt>
alpar@100	1328	DfsVisit &reachedMap(ReachedMap &m) {
alpar@100	1329	if(local_reached) {
alpar@209	1330	delete _reached;
alpar@209	1331	local_reached=false;
alpar@100	1332	}
alpar@100	1333	_reached = &m;
alpar@100	1334	return *this;
alpar@100	1335	}
alpar@100	1336
alpar@100	1337	public:
alpar@100	1338	/// \name Execution control
alpar@100	1339	/// The simplest way to execute the algorithm is to use
alpar@100	1340	/// one of the member functions called \c run(...).
alpar@100	1341	/// \n
alpar@100	1342	/// If you need more control on the execution,
alpar@100	1343	/// first you must call \ref init(), then you can adda source node
alpar@100	1344	/// with \ref addSource().
alpar@100	1345	/// Finally \ref start() will perform the actual path
alpar@100	1346	/// computation.
alpar@100	1347
alpar@100	1348	/// @{
alpar@100	1349	/// \brief Initializes the internal data structures.
alpar@100	1350	///
alpar@100	1351	/// Initializes the internal data structures.
alpar@100	1352	///
alpar@100	1353	void init() {
alpar@100	1354	create_maps();
alpar@100	1355	_stack.resize(countNodes(*_digraph));
alpar@100	1356	_stack_head = -1;
alpar@100	1357	for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
alpar@209	1358	_reached->set(u, false);
alpar@100	1359	}
alpar@100	1360	}
alpar@209	1361
alpar@100	1362	/// \brief Adds a new source node.
alpar@100	1363	///
alpar@100	1364	/// Adds a new source node to the set of nodes to be processed.
alpar@100	1365	void addSource(Node s) {
alpar@100	1366	if(!(*_reached)[s]) {
alpar@209	1367	_reached->set(s,true);
alpar@209	1368	_visitor->start(s);
alpar@209	1369	_visitor->reach(s);
alpar@209	1370	Arc e;
alpar@209	1371	_digraph->firstOut(e, s);
alpar@209	1372	if (e != INVALID) {
alpar@209	1373	_stack[++_stack_head] = e;
alpar@209	1374	} else {
alpar@209	1375	_visitor->leave(s);
alpar@209	1376	}
alpar@209	1377	}
alpar@100	1378	}
alpar@209	1379
alpar@100	1380	/// \brief Processes the next arc.
alpar@100	1381	///
alpar@100	1382	/// Processes the next arc.
alpar@100	1383	///
alpar@100	1384	/// \return The processed arc.
alpar@100	1385	///
alpar@100	1386	/// \pre The stack must not be empty!
alpar@209	1387	Arc processNextArc() {
alpar@100	1388	Arc e = _stack[_stack_head];
alpar@100	1389	Node m = _digraph->target(e);
alpar@100	1390	if(!(*_reached)[m]) {
alpar@209	1391	_visitor->discover(e);
alpar@209	1392	_visitor->reach(m);
alpar@209	1393	_reached->set(m, true);
alpar@209	1394	_digraph->firstOut(_stack[++_stack_head], m);
alpar@100	1395	} else {
alpar@209	1396	_visitor->examine(e);
alpar@209	1397	m = _digraph->source(e);
alpar@209	1398	_digraph->nextOut(_stack[_stack_head]);
alpar@100	1399	}
alpar@100	1400	while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
alpar@209	1401	_visitor->leave(m);
alpar@209	1402	--_stack_head;
alpar@209	1403	if (_stack_head >= 0) {
alpar@209	1404	_visitor->backtrack(_stack[_stack_head]);
alpar@209	1405	m = _digraph->source(_stack[_stack_head]);
alpar@209	1406	_digraph->nextOut(_stack[_stack_head]);
alpar@209	1407	} else {
alpar@209	1408	_visitor->stop(m);
alpar@209	1409	}
alpar@100	1410	}
alpar@100	1411	return e;
alpar@100	1412	}
alpar@100	1413
alpar@100	1414	/// \brief Next arc to be processed.
alpar@100	1415	///
alpar@100	1416	/// Next arc to be processed.
alpar@100	1417	///
alpar@100	1418	/// \return The next arc to be processed or INVALID if the stack is
alpar@100	1419	/// empty.
alpar@209	1420	Arc nextArc() {
alpar@100	1421	return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
alpar@100	1422	}
alpar@100	1423
alpar@100	1424	/// \brief Returns \c false if there are nodes
alpar@100	1425	/// to be processed in the queue
alpar@100	1426	///
alpar@100	1427	/// Returns \c false if there are nodes
alpar@100	1428	/// to be processed in the queue
alpar@100	1429	bool emptyQueue() { return _stack_head < 0; }
alpar@100	1430
alpar@100	1431	/// \brief Returns the number of the nodes to be processed.
alpar@100	1432	///
alpar@100	1433	/// Returns the number of the nodes to be processed in the queue.
alpar@100	1434	int queueSize() { return _stack_head + 1; }
alpar@209	1435
alpar@100	1436	/// \brief Executes the algorithm.
alpar@100	1437	///
alpar@100	1438	/// Executes the algorithm.
alpar@100	1439	///
alpar@100	1440	/// \pre init() must be called and at least one node should be added
alpar@100	1441	/// with addSource() before using this function.
alpar@100	1442	void start() {
alpar@100	1443	while ( !emptyQueue() ) processNextArc();
alpar@100	1444	}
alpar@209	1445
alpar@100	1446	/// \brief Executes the algorithm until \c dest is reached.
alpar@100	1447	///
alpar@100	1448	/// Executes the algorithm until \c dest is reached.
alpar@100	1449	///
alpar@100	1450	/// \pre init() must be called and at least one node should be added
alpar@100	1451	/// with addSource() before using this function.
alpar@100	1452	void start(Node dest) {
alpar@209	1453	while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
alpar@209	1454	processNextArc();
alpar@100	1455	}
alpar@209	1456
alpar@100	1457	/// \brief Executes the algorithm until a condition is met.
alpar@100	1458	///
alpar@100	1459	/// Executes the algorithm until a condition is met.
alpar@100	1460	///
alpar@100	1461	/// \pre init() must be called and at least one node should be added
alpar@100	1462	/// with addSource() before using this function.
alpar@100	1463	///
alpar@100	1464	/// \param em must be a bool (or convertible) arc map. The algorithm
alpar@100	1465	/// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
alpar@100	1466	///
alpar@100	1467	///\return The reached arc \c e with <tt>em[e]</tt> true or
alpar@100	1468	///\c INVALID if no such arc was found.
alpar@100	1469	///
alpar@100	1470	/// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
alpar@100	1471	/// not a node map.
alpar@100	1472	template <typename EM>
alpar@100	1473	Arc start(const EM &em) {
alpar@100	1474	while ( !emptyQueue() && !em[_stack[_stack_head]] )
alpar@100	1475	processNextArc();
alpar@100	1476	return emptyQueue() ? INVALID : _stack[_stack_head];
alpar@100	1477	}
alpar@100	1478
alpar@100	1479	/// \brief Runs %DFSVisit algorithm from node \c s.
alpar@100	1480	///
alpar@100	1481	/// This method runs the %DFS algorithm from a root node \c s.
alpar@100	1482	/// \note d.run(s) is just a shortcut of the following code.
alpar@100	1483	///\code
alpar@100	1484	/// d.init();
alpar@100	1485	/// d.addSource(s);
alpar@100	1486	/// d.start();
alpar@100	1487	///\endcode
alpar@100	1488	void run(Node s) {
alpar@100	1489	init();
alpar@100	1490	addSource(s);
alpar@100	1491	start();
alpar@100	1492	}
alpar@100	1493
alpar@100	1494	/// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
alpar@209	1495
alpar@100	1496	/// This method runs the %DFS algorithm in order to
alpar@100	1497	/// compute the %DFS path to each node. The algorithm computes
alpar@100	1498	/// - The %DFS tree.
alpar@100	1499	/// - The distance of each node from the root in the %DFS tree.
alpar@100	1500	///
alpar@100	1501	///\note d.run() is just a shortcut of the following code.
alpar@100	1502	///\code
alpar@100	1503	/// d.init();
alpar@100	1504	/// for (NodeIt it(digraph); it != INVALID; ++it) {
alpar@100	1505	/// if (!d.reached(it)) {
alpar@100	1506	/// d.addSource(it);
alpar@100	1507	/// d.start();
alpar@100	1508	/// }
alpar@100	1509	/// }
alpar@100	1510	///\endcode
alpar@100	1511	void run() {
alpar@100	1512	init();
alpar@100	1513	for (NodeIt it(*_digraph); it != INVALID; ++it) {
alpar@100	1514	if (!reached(it)) {
alpar@100	1515	addSource(it);
alpar@100	1516	start();
alpar@100	1517	}
alpar@100	1518	}
alpar@100	1519	}
alpar@100	1520	///@}
alpar@100	1521
alpar@100	1522	/// \name Query Functions
alpar@100	1523	/// The result of the %DFS algorithm can be obtained using these
alpar@100	1524	/// functions.\n
alpar@100	1525	/// Before the use of these functions,
alpar@100	1526	/// either run() or start() must be called.
alpar@100	1527	///@{
alpar@100	1528	/// \brief Checks if a node is reachable from the root.
alpar@100	1529	///
alpar@100	1530	/// Returns \c true if \c v is reachable from the root(s).
alpar@100	1531	/// \warning The source nodes are inditated as unreachable.
alpar@100	1532	/// \pre Either \ref run() or \ref start()
alpar@100	1533	/// must be called before using this function.
alpar@100	1534	///
alpar@100	1535	bool reached(Node v) { return (*_reached)[v]; }
alpar@100	1536	///@}
alpar@100	1537	};
alpar@100	1538
alpar@100	1539
alpar@100	1540	} //END OF NAMESPACE LEMON
alpar@100	1541
alpar@100	1542	#endif
alpar@100	1543

author	Alpar Juttner <alpar@cs.elte.hu>
	Wed, 23 Jul 2008 16:51:07 +0100
changeset 231	9ce7a01a95c7
parent 210	81cfc04531e8
child 247	f1158744a112
permissions	-rw-r--r--