lemon-1.1: comparison lemon/bfs.h

equal deleted inserted replaced

-:fb394ec778b5
+:30ec9245b163
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
-* This file is a part of LEMON, a generic C++ optimization library
+* This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 #include <lemon/maps.h>
 namespace lemon {
 ///Default traits class of Bfs class.
 ///Default traits class of Bfs class.
 ///\tparam GR Digraph type.
 template<class GR>
 struct BfsDefaultTraits
 {
 ///The digraph type the algorithm runs on.
 typedef GR Digraph;
 ///\brief The type of the map that stores the last
 ///arcs of the shortest paths.
 ///
 ///The type of the map that stores the last
 ///arcs of the shortest paths.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 ///
 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
 ///Instantiates a PredMap.
 ///This function instantiates a \ref PredMap.
 ///\param G is the digraph, to which we would like to define the PredMap.
 ///\todo The digraph alone may be insufficient to initialize
 static PredMap *createPredMap(const GR &G)
 {
 return new PredMap(G);
 }
 ///The type of the map that indicates which nodes are processed.
 ///The type of the map that indicates which nodes are processed.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 ///\todo named parameter to set this type, function to read and write.
 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 ///Instantiates a ProcessedMap.
 ///This function instantiates a \ref ProcessedMap.
 ///\param g is the digraph, to which
 ///we would like to define the \ref ProcessedMap
 #ifdef DOXYGEN
 static ProcessedMap *createProcessedMap(const GR &g)
 #else
 #endif
 {
 return new ProcessedMap();
 }
 ///The type of the map that indicates which nodes are reached.
 ///The type of the map that indicates which nodes are reached.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 ///\todo named parameter to set this type, function to read and write.
 typedef typename Digraph::template NodeMap<bool> ReachedMap;
 ///Instantiates a ReachedMap.
 ///This function instantiates a \ref ReachedMap.
 ///\param G is the digraph, to which
 ///we would like to define the \ref ReachedMap.
 static ReachedMap *createReachedMap(const GR &G)
 {
 return new ReachedMap(G);
 }
 ///The type of the map that stores the dists of the nodes.
 ///The type of the map that stores the dists of the nodes.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 ///
 typedef typename Digraph::template NodeMap<int> DistMap;
 ///Instantiates a DistMap.
 ///This function instantiates a \ref DistMap.
 ///\param G is the digraph, to which we would like to define the \ref DistMap
 static DistMap *createDistMap(const GR &G)
 {
 return new DistMap(G);
 }
 };
 ///%BFS algorithm class.
 ///\ingroup search
 ///This class provides an efficient implementation of the %BFS algorithm.
 ///
 ///\tparam GR The digraph type the algorithm runs on. The default value is
 ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
 ///See \ref BfsDefaultTraits for the documentation of
 ///a Bfs traits class.
 #ifdef DOXYGEN
 template <typename GR,
-	    typename TR>
+typename TR>
 #else
 template <typename GR=ListDigraph,
-	    typename TR=BfsDefaultTraits<GR> >
+typename TR=BfsDefaultTraits<GR> >
 #endif
 class Bfs {
 public:
 /**
 * \brief \ref Exception for uninitialized parameters.
 * of the parameters of the algorithms.
 */
 class UninitializedParameter : public lemon::UninitializedParameter {
 public:
 virtual const char* what() const throw() {
-	return "lemon::Bfs::UninitializedParameter";
+return "lemon::Bfs::UninitializedParameter";
 }
 };
 typedef TR Traits;
 ///The type of the underlying digraph.
 typedef typename TR::Digraph Digraph;
 ///\brief The type of the map that stores the last
 ///arcs of the shortest paths.
 typedef typename TR::PredMap PredMap;
 ///The type of the map indicating which nodes are reached.
 typedef typename TR::ReachedMap ReachedMap;
 std::vector<typename Digraph::Node> _queue;
 int _queue_head,_queue_tail,_queue_next_dist;
 int _curr_dist;
 ///Creates the maps if necessary.
 ///\todo Better memory allocation (instead of new).
 void create_maps()
 {
 if(!_pred) {
-	local_pred = true;
+local_pred = true;
-	_pred = Traits::createPredMap(*G);
+_pred = Traits::createPredMap(*G);
 }
 if(!_dist) {
-	local_dist = true;
+local_dist = true;
-	_dist = Traits::createDistMap(*G);
+_dist = Traits::createDistMap(*G);
 }
 if(!_reached) {
-	local_reached = true;
+local_reached = true;
-	_reached = Traits::createReachedMap(*G);
+_reached = Traits::createReachedMap(*G);
 }
 if(!_processed) {
-	local_processed = true;
+local_processed = true;
-	_processed = Traits::createProcessedMap(*G);
+_processed = Traits::createProcessedMap(*G);
 }
 }
 protected:
 Bfs() {}
 public:
 typedef Bfs Create;
 ///\name Named template parameters
 ///@{
 template <class T>
 struct DefPredMapTraits : public Traits {
 typedef T PredMap;
 static PredMap *createPredMap(const Digraph &)
 {
-	throw UninitializedParameter();
+throw UninitializedParameter();
 }
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///PredMap type
 ///
 ///\ref named-templ-param "Named parameter" for setting PredMap type
 ///
 template <class T>
 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
 typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
 };
 template <class T>
 struct DefDistMapTraits : public Traits {
 typedef T DistMap;
 static DistMap *createDistMap(const Digraph &)
 {
-	throw UninitializedParameter();
+throw UninitializedParameter();
 }
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///DistMap type
 ///
 ///\ref named-templ-param "Named parameter" for setting DistMap type
 ///
 template <class T>
 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
 typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
 };
 template <class T>
 struct DefReachedMapTraits : public Traits {
 typedef T ReachedMap;
 static ReachedMap *createReachedMap(const Digraph &)
 {
-	throw UninitializedParameter();
+throw UninitializedParameter();
 }
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///ReachedMap type
 ///
 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
 ///
 template <class T>
 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
 typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
 };
 template <class T>
 struct DefProcessedMapTraits : public Traits {
 typedef T ProcessedMap;
 static ProcessedMap *createProcessedMap(const Digraph &)
 {
-	throw UninitializedParameter();
+throw UninitializedParameter();
 }
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///ProcessedMap type
 ///
 ///
 template <class T>
 struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
 typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
 };
 struct DefDigraphProcessedMapTraits : public Traits {
 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 static ProcessedMap *createProcessedMap(const Digraph &G)
 {
-	return new ProcessedMap(G);
+return new ProcessedMap(G);
 }
 };
 ///\brief \ref named-templ-param "Named parameter"
 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
 ///
 ///\ref named-templ-param "Named parameter"
 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
 ///If you don't set it explicitly, it will be automatically allocated.
 template <class T>
 struct DefProcessedMapToBeDefaultMap :
 public Bfs< Digraph, DefDigraphProcessedMapTraits> {
 typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
 };
 ///@}
 public:
 ///Constructor.
 ///\param _G the digraph the algorithm will run on.
 ///
 Bfs(const Digraph& _G) :
 G(&_G),
 _pred(NULL), local_pred(false),
 _dist(NULL), local_dist(false),
 _reached(NULL), local_reached(false),
 _processed(NULL), local_processed(false)
 { }
 ///Destructor.
 ~Bfs()
 {
 if(local_pred) delete _pred;
 if(local_dist) delete _dist;
 if(local_reached) delete _reached;
 if(local_processed) delete _processed;
 ///Sets the map storing the predecessor arcs.
 ///If you don't use this function before calling \ref run(),
 ///it will allocate one. The destructor deallocates this
 ///automatically allocated map, of course.
 ///\return <tt> (*this) </tt>
 Bfs &predMap(PredMap &m)
 {
 if(local_pred) {
-	delete _pred;
+delete _pred;
-	local_pred=false;
+local_pred=false;
 }
 _pred = &m;
 return *this;
 }
 ///Sets the map indicating the reached nodes.
 ///If you don't use this function before calling \ref run(),
 ///it will allocate one. The destructor deallocates this
 ///automatically allocated map, of course.
 ///\return <tt> (*this) </tt>
 Bfs &reachedMap(ReachedMap &m)
 {
 if(local_reached) {
-	delete _reached;
+delete _reached;
-	local_reached=false;
+local_reached=false;
 }
 _reached = &m;
 return *this;
 }
 ///Sets the map indicating the processed nodes.
 ///If you don't use this function before calling \ref run(),
 ///it will allocate one. The destructor deallocates this
 ///automatically allocated map, of course.
 ///\return <tt> (*this) </tt>
 Bfs &processedMap(ProcessedMap &m)
 {
 if(local_processed) {
-	delete _processed;
+delete _processed;
-	local_processed=false;
+local_processed=false;
 }
 _processed = &m;
 return *this;
 }
 ///Sets the map storing the distances calculated by the algorithm.
 ///If you don't use this function before calling \ref run(),
 ///it will allocate one. The destructor deallocates this
 ///automatically allocated map, of course.
 ///\return <tt> (*this) </tt>
 Bfs &distMap(DistMap &m)
 {
 if(local_dist) {
-	delete _dist;
+delete _dist;
-	local_dist=false;
+local_dist=false;
 }
 _dist = &m;
 return *this;
 }
 create_maps();
 _queue.resize(countNodes(*G));
 _queue_head=_queue_tail=0;
 _curr_dist=1;
 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
-	_pred->set(u,INVALID);
+_pred->set(u,INVALID);
-	_reached->set(u,false);
+_reached->set(u,false);
-	_processed->set(u,false);
+_processed->set(u,false);
 }
 }
 ///Adds a new source node.
 ///Adds a new source node to the set of nodes to be processed.
 ///
 void addSource(Node s)
 {
 if(!(*_reached)[s])
-	{
+{
-	  _reached->set(s,true);
+_reached->set(s,true);
-	  _pred->set(s,INVALID);
+_pred->set(s,INVALID);
-	  _dist->set(s,0);
+_dist->set(s,0);
-	  _queue[_queue_head++]=s;
+_queue[_queue_head++]=s;
-	  _queue_next_dist=_queue_head;
+_queue_next_dist=_queue_head;
-	}
+}
 }
 ///Processes the next node.
 ///Processes the next node.
 ///
 ///\return The processed node.
 ///
 ///\warning The queue must not be empty!
 Node processNextNode()
 {
 if(_queue_tail==_queue_next_dist) {
-	_curr_dist++;
+_curr_dist++;
-	_queue_next_dist=_queue_head;
+_queue_next_dist=_queue_head;
 }
 Node n=_queue[_queue_tail++];
 _processed->set(n,true);
 Node m;
 for(OutArcIt e(*G,n);e!=INVALID;++e)
-	if(!(*_reached)[m=G->target(e)]) {
+if(!(*_reached)[m=G->target(e)]) {
-	  _queue[_queue_head++]=m;
+_queue[_queue_head++]=m;
-	  _reached->set(m,true);
+_reached->set(m,true);
-	  _pred->set(m,e);
+_pred->set(m,e);
-	  _dist->set(m,_curr_dist);
+_dist->set(m,_curr_dist);
-	}
+}
 return n;
 }
 ///Processes the next node.
 ///
 ///\warning The queue must not be empty!
 Node processNextNode(Node target, bool& reach)
 {
 if(_queue_tail==_queue_next_dist) {
-	_curr_dist++;
+_curr_dist++;
-	_queue_next_dist=_queue_head;
+_queue_next_dist=_queue_head;
 }
 Node n=_queue[_queue_tail++];
 _processed->set(n,true);
 Node m;
 for(OutArcIt e(*G,n);e!=INVALID;++e)
-	if(!(*_reached)[m=G->target(e)]) {
+if(!(*_reached)[m=G->target(e)]) {
-	  _queue[_queue_head++]=m;
+_queue[_queue_head++]=m;
-	  _reached->set(m,true);
+_reached->set(m,true);
-	  _pred->set(m,e);
+_pred->set(m,e);
-	  _dist->set(m,_curr_dist);
+_dist->set(m,_curr_dist);
 reach = reach || (target == m);
-	}
+}
 return n;
 }
 ///Processes the next node.
 ///\warning The queue must not be empty!
 template<class NM>
 Node processNextNode(const NM& nm, Node& rnode)
 {
 if(_queue_tail==_queue_next_dist) {
-	_curr_dist++;
+_curr_dist++;
-	_queue_next_dist=_queue_head;
+_queue_next_dist=_queue_head;
 }
 Node n=_queue[_queue_tail++];
 _processed->set(n,true);
 Node m;
 for(OutArcIt e(*G,n);e!=INVALID;++e)
-	if(!(*_reached)[m=G->target(e)]) {
+if(!(*_reached)[m=G->target(e)]) {
-	  _queue[_queue_head++]=m;
+_queue[_queue_head++]=m;
-	  _reached->set(m,true);
+_reached->set(m,true);
-	  _pred->set(m,e);
+_pred->set(m,e);
-	  _dist->set(m,_curr_dist);
+_dist->set(m,_curr_dist);
-	  if (nm[m] && rnode == INVALID) rnode = m;
+if (nm[m] && rnode == INVALID) rnode = m;
-	}
+}
 return n;
 }
 ///Next node to be processed.
 ///Next node to be processed.
 ///
 ///\return The next node to be processed or INVALID if the queue is
 /// empty.
 Node nextNode()
 {
 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
 }
 ///\brief Returns \c false if there are nodes
 ///to be processed in the queue
 ///
 ///Returns \c false if there are nodes
 ///to be processed in the queue
 bool emptyQueue() { return _queue_tail==_queue_head; }
 ///Returns the number of the nodes to be processed.
 ///Returns the number of the nodes to be processed in the queue.
 int queueSize() { return _queue_head-_queue_tail; }
 ///Executes the algorithm.
 ///Executes the algorithm.
 ///
 ///\pre init() must be called and at least one node should be added
 ///- The distance of each node from the root(s).
 void start()
 {
 while ( !emptyQueue() ) processNextNode();
 }
 ///Executes the algorithm until \c dest is reached.
 ///Executes the algorithm until \c dest is reached.
 ///
 ///\pre init() must be called and at least one node should be added
 void start(Node dest)
 {
 bool reach = false;
 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
 }
 ///Executes the algorithm until a condition is met.
 ///Executes the algorithm until a condition is met.
 ///
 ///\pre init() must be called and at least one node should be added
 template<class NM>
 Node start(const NM &nm)
 {
 Node rnode = INVALID;
 while ( !emptyQueue() && rnode == INVALID ) {
-	processNextNode(nm, rnode);
+processNextNode(nm, rnode);
 }
 return rnode;
 }
 ///Runs %BFS algorithm from node \c s.
 ///This method runs the %BFS algorithm from a root node \c s
 ///in order to
 ///compute the
 ///shortest path to each node. The algorithm computes
 ///- The shortest path tree.
 void run(Node s) {
 init();
 addSource(s);
 start();
 }
 ///Finds the shortest path between \c s and \c t.
 ///Finds the shortest path between \c s and \c t.
 ///
 ///\return The length of the shortest s---t path if there exists one,
 ///0 otherwise.
 ///\note Apart from the return value, b.run(s) is
 init();
 addSource(s);
 start(t);
 return reached(t) ? _curr_dist : 0;
 }
 ///@}
 ///\name Query Functions
 ///The result of the %BFS algorithm can be obtained using these
 ///functions.\n
 ///Before the use of these functions,
 ///either run() or start() must be calleb.
 ///@{
 typedef PredMapPath<Digraph, PredMap> Path;
 ///Gives back the shortest path.
 ///Gives back the shortest path.
 ///\pre The \c t should be reachable from the source.
 Path path(Node t)
 {
 return Path(*G, *_pred, t);
 }
 ///The distance of a node from the root(s).
 ///The shortest path tree used here is equal to the shortest path
 ///tree used in \ref predArc().
 ///\pre Either \ref run() or \ref start() must be called before
 ///using this function.
 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
-				  G->source((*_pred)[v]); }
+G->source((*_pred)[v]); }
 ///Returns a reference to the NodeMap of distances.
 ///Returns a reference to the NodeMap of distances.
 ///\pre Either \ref run() or \ref init() must
 ///be called before using this function.
 const DistMap &distMap() const { return *_dist;}
 ///Returns a reference to the shortest path tree map.
 ///Returns a reference to the NodeMap of the arcs of the
 ///shortest path tree.
 ///\pre Either \ref run() or \ref init()
 ///must be called before using this function.
 const PredMap &predMap() const { return *_pred;}
 ///Checks if a node is reachable from the root.
 ///Returns \c true if \c v is reachable from the root.
 ///\warning The source nodes are indicated as unreached.
 ///\pre Either \ref run() or \ref start()
 ///must be called before using this function.
 ///
 bool reached(Node v) { return (*_reached)[v]; }
 ///@}
 };
 ///Default traits class of Bfs function.
 ///Default traits class of Bfs function.
 ///\tparam GR Digraph type.
 template<class GR>
 struct BfsWizardDefaultTraits
 {
 ///The digraph type the algorithm runs on.
 typedef GR Digraph;
 ///\brief The type of the map that stores the last
 ///arcs of the shortest paths.
 ///
 ///The type of the map that stores the last
 ///arcs of the shortest paths.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 ///
 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
 ///Instantiates a PredMap.
 ///This function instantiates a \ref PredMap.
 ///\param g is the digraph, to which we would like to define the PredMap.
 ///\todo The digraph alone may be insufficient to initialize
 #ifdef DOXYGEN
 static PredMap *createPredMap(const GR &g)
 #else
 static PredMap *createPredMap(const GR &)
 #endif
 {
 return new PredMap();
 }
 ///The type of the map that indicates which nodes are processed.
 ///The type of the map that indicates which nodes are processed.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 ///\todo named parameter to set this type, function to read and write.
 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 ///Instantiates a ProcessedMap.
 ///This function instantiates a \ref ProcessedMap.
 ///\param g is the digraph, to which
 ///we would like to define the \ref ProcessedMap
 #ifdef DOXYGEN
 static ProcessedMap *createProcessedMap(const GR &g)
 #else
 #endif
 {
 return new ProcessedMap();
 }
 ///The type of the map that indicates which nodes are reached.
 ///The type of the map that indicates which nodes are reached.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 ///\todo named parameter to set this type, function to read and write.
 typedef typename Digraph::template NodeMap<bool> ReachedMap;
 ///Instantiates a ReachedMap.
 ///This function instantiates a \ref ReachedMap.
 ///\param G is the digraph, to which
 ///we would like to define the \ref ReachedMap.
 static ReachedMap *createReachedMap(const GR &G)
 {
 return new ReachedMap(G);
 }
 ///The type of the map that stores the dists of the nodes.
 ///The type of the map that stores the dists of the nodes.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 ///
 typedef NullMap<typename Digraph::Node,int> DistMap;
 ///Instantiates a DistMap.
 ///This function instantiates a \ref DistMap.
 ///\param g is the digraph, to which we would like to define the \ref DistMap
 #ifdef DOXYGEN
 static DistMap *createDistMap(const GR &g)
 #else
 static DistMap *createDistMap(const GR &)
 #endif
 {
 return new DistMap();
 }
 };
 /// Default traits used by \ref BfsWizard
 /// To make it easier to use Bfs algorithm
 ///we have created a wizard class.
 /// This \ref BfsWizard class needs default traits,
 void *_pred;
 ///Pointer to the map of distances.
 void *_dist;
 ///Pointer to the source node.
 Node _source;
 public:
 /// Constructor.
 /// This constructor does not require parameters, therefore it initiates
 /// all of the attributes to default values (0, INVALID).
 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
-			   _dist(0), _source(INVALID) {}
+_dist(0), _source(INVALID) {}
 /// Constructor.
 /// This constructor requires some parameters,
 /// listed in the parameters list.
 /// Others are initiated to 0.
 /// \param g is the initial value of  \ref _g
 /// \param s is the initial value of  \ref _source
 BfsWizardBase(const GR &g, Node s=INVALID) :
 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
 };
 /// A class to make the usage of Bfs algorithm easier
 /// This class is created to make it easier to use Bfs algorithm.
 /// It uses the functions and features of the plain \ref Bfs,
 /// but it is much simpler to use it.
 typedef typename Digraph::NodeIt NodeIt;
 //\e
 typedef typename Digraph::Arc Arc;
 //\e
 typedef typename Digraph::OutArcIt OutArcIt;
 ///\brief The type of the map that stores
 ///the reached nodes
 typedef typename TR::ReachedMap ReachedMap;
 ///\brief The type of the map that stores
 ///the processed nodes
 BfsWizard(const TR &b) : TR(b) {}
 ~BfsWizard() {}
 ///Runs Bfs algorithm from a given node.
 ///Runs Bfs algorithm from a given node.
 ///The node can be given by the \ref source function.
 void run()
 {
 if(Base::_source==INVALID) throw UninitializedParameter();
 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 if(Base::_reached)
-	alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
+alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 if(Base::_processed)
 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 if(Base::_pred)
 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 if(Base::_dist)
 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 alg.run(Base::_source);
 }
 ///Runs Bfs algorithm from the given node.
 struct DefPredMapBase : public Base {
 typedef T PredMap;
 static PredMap *createPredMap(const Digraph &) { return 0; };
 DefPredMapBase(const TR &b) : TR(b) {}
 };
 ///\brief \ref named-templ-param "Named parameter"
 ///function for setting PredMap
 ///
 /// \ref named-templ-param "Named parameter"
 ///function for setting PredMap
 ///
 template<class T>
 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
 {
 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 return BfsWizard<DefPredMapBase<T> >(*this);
 }
 template<class T>
 struct DefReachedMapBase : public Base {
 typedef T ReachedMap;
 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 DefReachedMapBase(const TR &b) : TR(b) {}
 };
 ///\brief \ref named-templ-param "Named parameter"
 ///function for setting ReachedMap
 ///
 /// \ref named-templ-param "Named parameter"
 ///function for setting ReachedMap
 ///
 template<class T>
 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
 {
 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
 return BfsWizard<DefReachedMapBase<T> >(*this);
 }
 template<class T>
 struct DefProcessedMapBase : public Base {
 typedef T ProcessedMap;
 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 DefProcessedMapBase(const TR &b) : TR(b) {}
 };
 ///\brief \ref named-templ-param "Named parameter"
 ///function for setting ProcessedMap
 ///
 /// \ref named-templ-param "Named parameter"
 ///function for setting ProcessedMap
 ///
 template<class T>
 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
 {
 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 return BfsWizard<DefProcessedMapBase<T> >(*this);
 }
 template<class T>
 struct DefDistMapBase : public Base {
 typedef T DistMap;
 static DistMap *createDistMap(const Digraph &) { return 0; };
 DefDistMapBase(const TR &b) : TR(b) {}
 };
 ///\brief \ref named-templ-param "Named parameter"
 ///function for setting DistMap type
 ///
 /// \ref named-templ-param "Named parameter"
 ///function for setting DistMap type
 ///
 template<class T>
 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
 {
 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 return BfsWizard<DefDistMapBase<T> >(*this);
 }
 /// Sets the source node, from which the Bfs algorithm runs.
 /// Sets the source node, from which the Bfs algorithm runs.
 /// \param s is the source node.
 BfsWizard<TR> &source(Node s)
 {
 Base::_source=s;
 return *this;
 }
 };
 ///Function type interface for Bfs algorithm.
 /// \ingroup search
 ///Function type interface for Bfs algorithm.
 ///
 return BfsWizard<BfsWizardBase<GR> >(g,s);
 }
 #ifdef DOXYGEN
 /// \brief Visitor class for bfs.
 ///
 /// This class defines the interface of the BfsVisit events, and
 /// it could be the base of a real Visitor class.
 template <typename _Digraph>
 struct BfsVisitor {
 typedef _Digraph Digraph;
 typedef typename Digraph::Arc Arc;
 typedef typename Digraph::Node Node;
 /// \brief Called when the arc reach a node.
 ///
 /// It is called when the bfs find an arc which target is not
 /// reached yet.
 void discover(const Arc& arc) {}
 /// \brief Called when the node reached first time.
 ///
 /// It is Called when the node reached first time.
 void reach(const Node& node) {}
 /// \brief Called when the arc examined but target of the arc
 /// already discovered.
 ///
 /// It called when the arc examined but the target of the arc
 /// already discovered.
 void examine(const Arc& arc) {}
 /// \brief Called for the source node of the bfs.
 ///
 /// It is called for the source node of the bfs.
 void start(const Node& node) {}
 /// \brief Called when the node processed.
 ///
 /// It is Called when the node processed.
 void process(const Node& node) {}
 };
 #else
 template <typename _Digraph>
 void process(const Node&) {}
 template <typename _Visitor>
 struct Constraints {
 void constraints() {
-	Arc arc;
+Arc arc;
-	Node node;
+Node node;
-	visitor.discover(arc);
+visitor.discover(arc);
-	visitor.reach(node);
+visitor.reach(node);
-	visitor.examine(arc);
+visitor.examine(arc);
-	visitor.start(node);
+visitor.start(node);
 visitor.process(node);
 }
 _Visitor& visitor;
 };
 };
 /// Default traits class of BfsVisit class.
 /// \tparam _Digraph Digraph type.
 template<class _Digraph>
 struct BfsVisitDefaultTraits {
 /// \brief The digraph type the algorithm runs on.
 typedef _Digraph Digraph;
 /// \brief The type of the map that indicates which nodes are reached.
 ///
 /// The type of the map that indicates which nodes are reached.
 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
 /// \todo named parameter to set this type, function to read and write.
 typedef typename Digraph::template NodeMap<bool> ReachedMap;
 /// \brief Instantiates a ReachedMap.
 ///
 /// This function instantiates a \ref ReachedMap.
 /// \param digraph is the digraph, to which
 /// we would like to define the \ref ReachedMap.
 static ReachedMap *createReachedMap(const Digraph &digraph) {
 return new ReachedMap(digraph);
 }
 };
 /// \ingroup search
 ///
 /// \brief %BFS Visit algorithm class.
 ///
 /// This class provides an efficient implementation of the %BFS algorithm
 /// with visitor interface.
 ///
 /// The %BfsVisit class provides an alternative interface to the Bfs
 /// class. It works with callback mechanism, the BfsVisit object calls
 /// on every bfs event the \c Visitor class member functions.
 ///
 /// \tparam _Digraph The digraph type the algorithm runs on. The default value is
 /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
 /// is only passed to \ref BfsDefaultTraits.
 /// \tparam _Visitor The Visitor object for the algorithm. The
 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
 /// does not observe the Bfs events. If you want to observe the bfs
 /// events you should implement your own Visitor class.
 /// \tparam _Traits Traits class to set various data types used by the
 /// algorithm. The default traits class is
 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
 /// See \ref BfsVisitDefaultTraits for the documentation of
 /// a Bfs visit traits class.
 #ifdef DOXYGEN
 template <typename _Digraph, typename _Visitor, typename _Traits>
 #else
 template <typename _Digraph = ListDigraph,
-	    typename _Visitor = BfsVisitor<_Digraph>,
+typename _Visitor = BfsVisitor<_Digraph>,
-	    typename _Traits = BfsDefaultTraits<_Digraph> >
+typename _Traits = BfsDefaultTraits<_Digraph> >
 #endif
 class BfsVisit {
 public:
 /// \brief \ref Exception for uninitialized parameters.
 ///
 /// This error represents problems in the initialization
 /// of the parameters of the algorithms.
 class UninitializedParameter : public lemon::UninitializedParameter {
 public:
 virtual const char* what() const throw()
 {
-	return "lemon::BfsVisit::UninitializedParameter";
+return "lemon::BfsVisit::UninitializedParameter";
 }
 };
 typedef _Traits Traits;
 /// \brief Creates the maps if necessary.
 ///
 /// Creates the maps if necessary.
 void create_maps() {
 if(!_reached) {
-	local_reached = true;
+local_reached = true;
-	_reached = Traits::createReachedMap(*_digraph);
+_reached = Traits::createReachedMap(*_digraph);
 }
 }
 protected:
 BfsVisit() {}
 public:
 typedef BfsVisit Create;
 /// \name Named template parameters
 ///@{
 template <class T>
 struct DefReachedMapTraits : public Traits {
 typedef T ReachedMap;
 static ReachedMap *createReachedMap(const Digraph &digraph) {
-	throw UninitializedParameter();
+throw UninitializedParameter();
 }
 };
 /// \brief \ref named-templ-param "Named parameter" for setting
 /// ReachedMap type
 ///
 /// \ref named-templ-param "Named parameter" for setting ReachedMap type
 template <class T>
 struct DefReachedMap : public BfsVisit< Digraph, Visitor,
-					    DefReachedMapTraits<T> > {
+DefReachedMapTraits<T> > {
 typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
 };
 ///@}
 public:
 /// \brief Constructor.
 ///
 /// Constructor.
 ///
 /// \param digraph the digraph the algorithm will run on.
 /// \param visitor The visitor of the algorithm.
 ///
 BfsVisit(const Digraph& digraph, Visitor& visitor)
 : _digraph(&digraph), _visitor(&visitor),
-	_reached(0), local_reached(false) {}
+_reached(0), local_reached(false) {}
 /// \brief Destructor.
 ///
 /// Destructor.
 ~BfsVisit() {
 if(local_reached) delete _reached;
 /// it will allocate one. The destuctor deallocates this
 /// automatically allocated map, of course.
 /// \return <tt> (*this) </tt>
 BfsVisit &reachedMap(ReachedMap &m) {
 if(local_reached) {
-	delete _reached;
+delete _reached;
-	local_reached = false;
+local_reached = false;
 }
 _reached = &m;
 return *this;
 }
 void init() {
 create_maps();
 _list.resize(countNodes(*_digraph));
 _list_front = _list_back = -1;
 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
-	_reached->set(u, false);
+_reached->set(u, false);
 }
 }
 /// \brief Adds a new source node.
 ///
 /// Adds a new source node to the set of nodes to be processed.
 void addSource(Node s) {
 if(!(*_reached)[s]) {
-	  _reached->set(s,true);
+_reached->set(s,true);
-	  _visitor->start(s);
+_visitor->start(s);
-	  _visitor->reach(s);
+_visitor->reach(s);
 _list[++_list_back] = s;
-	}
+}
 }
 /// \brief Processes the next node.
 ///
 /// Processes the next node.
 ///
 /// \return The processed node.
 ///
 /// \pre The queue must not be empty!
 Node processNextNode() {
 Node n = _list[++_list_front];
 _visitor->process(n);
 Arc e;
 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 Node m = _digraph->target(e);
 ///
 /// Next node to be processed.
 ///
 /// \return The next node to be processed or INVALID if the stack is
 /// empty.
 Node nextNode() {
 return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
 }
 /// \brief Returns \c false if there are nodes
 /// to be processed in the queue
 /// \brief Returns the number of the nodes to be processed.
 ///
 /// Returns the number of the nodes to be processed in the queue.
 int queueSize() { return _list_back - _list_front; }
 /// \brief Executes the algorithm.
 ///
 /// Executes the algorithm.
 ///
 /// \pre init() must be called and at least one node should be added
 /// with addSource() before using this function.
 void start() {
 while ( !emptyQueue() ) processNextNode();
 }
 /// \brief Executes the algorithm until \c dest is reached.
 ///
 /// Executes the algorithm until \c dest is reached.
 ///
 /// \pre init() must be called and at least one node should be added
 /// with addSource() before using this function.
 void start(Node dest) {
 bool reach = false;
 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
 }
 /// \brief Executes the algorithm until a condition is met.
 ///
 /// Executes the algorithm until a condition is met.
 ///
 /// \pre init() must be called and at least one node should be added
 ///\c INVALID if no such node was found.
 template <typename NM>
 Node start(const NM &nm) {
 Node rnode = INVALID;
 while ( !emptyQueue() && rnode == INVALID ) {
-	processNextNode(nm, rnode);
+processNextNode(nm, rnode);
 }
 return rnode;
 }
 /// \brief Runs %BFSVisit algorithm from node \c s.
 addSource(s);
 start();
 }
 /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
 ///
 /// This method runs the %BFS algorithm in order to
 /// compute the %BFS path to each node. The algorithm computes
 /// - The %BFS tree.
 /// - The distance of each node from the root in the %BFS tree.
 ///

changeset 209	765619b7cbb2
parent 158	500f3cbff9e4
child 210	81cfc04531e8