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

author	Peter Kovacs <kpeter@inf.elte.hu>
	Mon, 14 Jul 2008 19:06:29 +0200
changeset 218	0d6511647639
parent 209	765619b7cbb2
child 220	a5d8c039f218
child 244	c30731a37f91
permissions	-rw-r--r--