alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@100: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. alpar@100: * alpar@100: * Copyright (C) 2003-2008 alpar@100: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@100: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@100: * alpar@100: * Permission to use, modify and distribute this software is granted alpar@100: * provided that this copyright notice appears in all copies. For alpar@100: * precise terms see the accompanying LICENSE file. alpar@100: * alpar@100: * This software is provided "AS IS" with no warranty of any kind, alpar@100: * express or implied, and with no claim as to its suitability for any alpar@100: * purpose. alpar@100: * alpar@100: */ alpar@100: alpar@100: #ifndef LEMON_BFS_H alpar@100: #define LEMON_BFS_H alpar@100: alpar@100: ///\ingroup search alpar@100: ///\file kpeter@244: ///\brief BFS algorithm. alpar@100: alpar@100: #include alpar@100: #include deba@220: #include alpar@100: #include alpar@100: #include alpar@100: alpar@100: namespace lemon { alpar@100: alpar@100: ///Default traits class of Bfs class. alpar@100: alpar@100: ///Default traits class of Bfs class. kpeter@157: ///\tparam GR Digraph type. alpar@100: template alpar@100: struct BfsDefaultTraits alpar@100: { kpeter@244: ///The type of the digraph the algorithm runs on. alpar@100: typedef GR Digraph; kpeter@244: kpeter@244: ///\brief The type of the map that stores the predecessor alpar@100: ///arcs of the shortest paths. alpar@209: /// kpeter@244: ///The type of the map that stores the predecessor alpar@100: ///arcs of the shortest paths. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. kpeter@244: typedef typename Digraph::template NodeMap PredMap; kpeter@244: ///Instantiates a \ref PredMap. alpar@209: alpar@209: ///This function instantiates a \ref PredMap. kpeter@244: ///\param g is the digraph, to which we would like to define the kpeter@244: ///\ref PredMap. alpar@100: ///\todo The digraph alone may be insufficient to initialize kpeter@244: static PredMap *createPredMap(const Digraph &g) alpar@100: { kpeter@244: return new PredMap(g); alpar@100: } kpeter@244: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@209: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. kpeter@244: ///By default it is a NullMap. alpar@100: typedef NullMap ProcessedMap; kpeter@244: ///Instantiates a \ref ProcessedMap. alpar@209: alpar@209: ///This function instantiates a \ref ProcessedMap. alpar@100: ///\param g is the digraph, to which alpar@100: ///we would like to define the \ref ProcessedMap alpar@100: #ifdef DOXYGEN kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &g) alpar@100: #else kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &) alpar@100: #endif alpar@100: { alpar@100: return new ProcessedMap(); alpar@100: } kpeter@244: alpar@100: ///The type of the map that indicates which nodes are reached. alpar@209: alpar@100: ///The type of the map that indicates which nodes are reached. kpeter@244: ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; kpeter@244: ///Instantiates a \ref ReachedMap. alpar@209: alpar@209: ///This function instantiates a \ref ReachedMap. kpeter@244: ///\param g is the digraph, to which alpar@100: ///we would like to define the \ref ReachedMap. kpeter@244: static ReachedMap *createReachedMap(const Digraph &g) alpar@100: { kpeter@244: return new ReachedMap(g); alpar@100: } alpar@209: kpeter@244: ///The type of the map that stores the distances of the nodes. kpeter@244: kpeter@244: ///The type of the map that stores the distances of the nodes. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: typedef typename Digraph::template NodeMap DistMap; kpeter@244: ///Instantiates a \ref DistMap. alpar@209: alpar@209: ///This function instantiates a \ref DistMap. kpeter@244: ///\param g is the digraph, to which we would like to define the kpeter@244: ///\ref DistMap. kpeter@244: static DistMap *createDistMap(const Digraph &g) alpar@100: { kpeter@244: return new DistMap(g); alpar@100: } alpar@100: }; alpar@209: alpar@100: ///%BFS algorithm class. alpar@209: alpar@100: ///\ingroup search alpar@100: ///This class provides an efficient implementation of the %BFS algorithm. alpar@100: /// kpeter@244: ///There is also a \ref bfs() "function type interface" for the BFS kpeter@244: ///algorithm, which is convenient in the simplier cases and it can be kpeter@244: ///used easier. kpeter@244: /// kpeter@244: ///\tparam GR The type of the digraph the algorithm runs on. kpeter@244: ///The default value is \ref ListDigraph. The value of GR is not used kpeter@244: ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. kpeter@157: ///\tparam TR Traits class to set various data types used by the algorithm. alpar@100: ///The default traits class is alpar@100: ///\ref BfsDefaultTraits "BfsDefaultTraits". alpar@100: ///See \ref BfsDefaultTraits for the documentation of alpar@100: ///a Bfs traits class. alpar@100: #ifdef DOXYGEN alpar@100: template alpar@100: #else alpar@100: template > alpar@100: #endif alpar@100: class Bfs { alpar@100: public: kpeter@244: ///\ref Exception for uninitialized parameters. kpeter@244: kpeter@244: ///This error represents problems in the initialization of the kpeter@244: ///parameters of the algorithm. alpar@100: class UninitializedParameter : public lemon::UninitializedParameter { alpar@100: public: alpar@100: virtual const char* what() const throw() { alpar@209: return "lemon::Bfs::UninitializedParameter"; alpar@100: } alpar@100: }; alpar@100: kpeter@244: ///The type of the digraph the algorithm runs on. alpar@100: typedef typename TR::Digraph Digraph; alpar@209: kpeter@244: ///\brief The type of the map that stores the predecessor arcs of the kpeter@244: ///shortest paths. alpar@100: typedef typename TR::PredMap PredMap; kpeter@244: ///The type of the map that stores the distances of the nodes. kpeter@244: typedef typename TR::DistMap DistMap; kpeter@244: ///The type of the map that indicates which nodes are reached. alpar@100: typedef typename TR::ReachedMap ReachedMap; kpeter@244: ///The type of the map that indicates which nodes are processed. alpar@100: typedef typename TR::ProcessedMap ProcessedMap; kpeter@244: ///The type of the paths. kpeter@244: typedef PredMapPath Path; kpeter@244: kpeter@244: ///The traits class. kpeter@244: typedef TR Traits; kpeter@244: alpar@100: private: alpar@100: alpar@100: typedef typename Digraph::Node Node; alpar@100: typedef typename Digraph::NodeIt NodeIt; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::OutArcIt OutArcIt; alpar@100: kpeter@244: //Pointer to the underlying digraph. alpar@100: const Digraph *G; kpeter@244: //Pointer to the map of predecessor arcs. alpar@100: PredMap *_pred; kpeter@244: //Indicates if _pred is locally allocated (true) or not. alpar@100: bool local_pred; kpeter@244: //Pointer to the map of distances. alpar@100: DistMap *_dist; kpeter@244: //Indicates if _dist is locally allocated (true) or not. alpar@100: bool local_dist; kpeter@244: //Pointer to the map of reached status of the nodes. alpar@100: ReachedMap *_reached; kpeter@244: //Indicates if _reached is locally allocated (true) or not. alpar@100: bool local_reached; kpeter@244: //Pointer to the map of processed status of the nodes. alpar@100: ProcessedMap *_processed; kpeter@244: //Indicates if _processed is locally allocated (true) or not. alpar@100: bool local_processed; alpar@100: alpar@100: std::vector _queue; alpar@100: int _queue_head,_queue_tail,_queue_next_dist; alpar@100: int _curr_dist; alpar@100: alpar@100: ///Creates the maps if necessary. alpar@100: ///\todo Better memory allocation (instead of new). alpar@209: void create_maps() alpar@100: { alpar@100: if(!_pred) { alpar@209: local_pred = true; alpar@209: _pred = Traits::createPredMap(*G); alpar@100: } alpar@100: if(!_dist) { alpar@209: local_dist = true; alpar@209: _dist = Traits::createDistMap(*G); alpar@100: } alpar@100: if(!_reached) { alpar@209: local_reached = true; alpar@209: _reached = Traits::createReachedMap(*G); alpar@100: } alpar@100: if(!_processed) { alpar@209: local_processed = true; alpar@209: _processed = Traits::createProcessedMap(*G); alpar@100: } alpar@100: } alpar@100: alpar@100: protected: alpar@209: alpar@100: Bfs() {} alpar@209: alpar@100: public: alpar@209: alpar@100: typedef Bfs Create; alpar@100: alpar@100: ///\name Named template parameters alpar@100: alpar@100: ///@{ alpar@100: alpar@100: template alpar@100: struct DefPredMapTraits : public Traits { alpar@100: typedef T PredMap; alpar@209: static PredMap *createPredMap(const Digraph &) alpar@100: { alpar@209: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref PredMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref PredMap type. alpar@100: template alpar@209: struct DefPredMap : public Bfs< Digraph, DefPredMapTraits > { alpar@100: typedef Bfs< Digraph, DefPredMapTraits > Create; alpar@100: }; alpar@209: alpar@100: template alpar@100: struct DefDistMapTraits : public Traits { alpar@100: typedef T DistMap; alpar@209: static DistMap *createDistMap(const Digraph &) alpar@100: { alpar@209: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref DistMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref DistMap type. alpar@100: template alpar@209: struct DefDistMap : public Bfs< Digraph, DefDistMapTraits > { alpar@100: typedef Bfs< Digraph, DefDistMapTraits > Create; alpar@100: }; alpar@209: alpar@100: template alpar@100: struct DefReachedMapTraits : public Traits { alpar@100: typedef T ReachedMap; alpar@209: static ReachedMap *createReachedMap(const Digraph &) alpar@100: { alpar@209: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref ReachedMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref ReachedMap type. alpar@100: template alpar@209: struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits > { alpar@100: typedef Bfs< Digraph, DefReachedMapTraits > Create; alpar@100: }; alpar@209: alpar@100: template alpar@100: struct DefProcessedMapTraits : public Traits { alpar@100: typedef T ProcessedMap; alpar@209: static ProcessedMap *createProcessedMap(const Digraph &) alpar@100: { alpar@209: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref ProcessedMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref ProcessedMap type. alpar@100: template alpar@100: struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits > { alpar@100: typedef Bfs< Digraph, DefProcessedMapTraits > Create; alpar@100: }; alpar@209: alpar@100: struct DefDigraphProcessedMapTraits : public Traits { alpar@100: typedef typename Digraph::template NodeMap ProcessedMap; kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &g) alpar@100: { kpeter@244: return new ProcessedMap(g); alpar@100: } alpar@100: }; kpeter@244: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref ProcessedMap type to be Digraph::NodeMap. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@244: ///\ref ProcessedMap type to be Digraph::NodeMap. alpar@100: ///If you don't set it explicitly, it will be automatically allocated. alpar@100: template alpar@100: struct DefProcessedMapToBeDefaultMap : alpar@209: public Bfs< Digraph, DefDigraphProcessedMapTraits> { alpar@100: typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create; alpar@100: }; alpar@209: alpar@100: ///@} alpar@100: alpar@209: public: alpar@209: alpar@100: ///Constructor. alpar@209: kpeter@244: ///Constructor. kpeter@244: ///\param g The digraph the algorithm runs on. kpeter@244: Bfs(const Digraph &g) : kpeter@244: G(&g), alpar@100: _pred(NULL), local_pred(false), alpar@100: _dist(NULL), local_dist(false), alpar@100: _reached(NULL), local_reached(false), alpar@100: _processed(NULL), local_processed(false) alpar@100: { } alpar@209: alpar@100: ///Destructor. alpar@209: ~Bfs() alpar@100: { alpar@100: if(local_pred) delete _pred; alpar@100: if(local_dist) delete _dist; alpar@100: if(local_reached) delete _reached; alpar@100: if(local_processed) delete _processed; alpar@100: } alpar@100: kpeter@244: ///Sets the map that stores the predecessor arcs. alpar@100: kpeter@244: ///Sets the map that stores the predecessor arcs. alpar@100: ///If you don't use this function before calling \ref run(), alpar@100: ///it will allocate one. The destructor deallocates this alpar@100: ///automatically allocated map, of course. alpar@100: ///\return (*this) alpar@209: Bfs &predMap(PredMap &m) alpar@100: { alpar@100: if(local_pred) { alpar@209: delete _pred; alpar@209: local_pred=false; alpar@100: } alpar@100: _pred = &m; alpar@100: return *this; alpar@100: } alpar@100: kpeter@244: ///Sets the map that indicates which nodes are reached. alpar@100: kpeter@244: ///Sets the map that indicates which nodes are reached. alpar@100: ///If you don't use this function before calling \ref run(), alpar@100: ///it will allocate one. The destructor deallocates this alpar@100: ///automatically allocated map, of course. alpar@100: ///\return (*this) alpar@209: Bfs &reachedMap(ReachedMap &m) alpar@100: { alpar@100: if(local_reached) { alpar@209: delete _reached; alpar@209: local_reached=false; alpar@100: } alpar@100: _reached = &m; alpar@100: return *this; alpar@100: } alpar@100: kpeter@244: ///Sets the map that indicates which nodes are processed. alpar@100: kpeter@244: ///Sets the map that indicates which nodes are processed. alpar@100: ///If you don't use this function before calling \ref run(), alpar@100: ///it will allocate one. The destructor deallocates this alpar@100: ///automatically allocated map, of course. alpar@100: ///\return (*this) alpar@209: Bfs &processedMap(ProcessedMap &m) alpar@100: { alpar@100: if(local_processed) { alpar@209: delete _processed; alpar@209: local_processed=false; alpar@100: } alpar@100: _processed = &m; alpar@100: return *this; alpar@100: } alpar@100: kpeter@244: ///Sets the map that stores the distances of the nodes. alpar@100: kpeter@244: ///Sets the map that stores the distances of the nodes calculated by kpeter@244: ///the algorithm. alpar@100: ///If you don't use this function before calling \ref run(), alpar@100: ///it will allocate one. The destructor deallocates this alpar@100: ///automatically allocated map, of course. alpar@100: ///\return (*this) alpar@209: Bfs &distMap(DistMap &m) alpar@100: { alpar@100: if(local_dist) { alpar@209: delete _dist; alpar@209: local_dist=false; alpar@100: } alpar@100: _dist = &m; alpar@100: return *this; alpar@100: } alpar@100: alpar@100: public: kpeter@244: alpar@100: ///\name Execution control alpar@100: ///The simplest way to execute the algorithm is to use kpeter@244: ///one of the member functions called \ref lemon::Bfs::run() "run()". alpar@100: ///\n kpeter@244: ///If you need more control on the execution, first you must call kpeter@244: ///\ref lemon::Bfs::init() "init()", then you can add several source kpeter@244: ///nodes with \ref lemon::Bfs::addSource() "addSource()". kpeter@244: ///Finally \ref lemon::Bfs::start() "start()" will perform the kpeter@244: ///actual path computation. alpar@100: alpar@100: ///@{ alpar@100: kpeter@244: ///Initializes the internal data structures. kpeter@244: alpar@100: ///Initializes the internal data structures. alpar@100: /// alpar@100: void init() alpar@100: { alpar@100: create_maps(); alpar@100: _queue.resize(countNodes(*G)); alpar@100: _queue_head=_queue_tail=0; alpar@100: _curr_dist=1; alpar@100: for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { alpar@209: _pred->set(u,INVALID); alpar@209: _reached->set(u,false); alpar@209: _processed->set(u,false); alpar@100: } alpar@100: } alpar@209: alpar@100: ///Adds a new source node. alpar@100: alpar@100: ///Adds a new source node to the set of nodes to be processed. alpar@100: /// alpar@100: void addSource(Node s) alpar@100: { alpar@100: if(!(*_reached)[s]) alpar@209: { alpar@209: _reached->set(s,true); alpar@209: _pred->set(s,INVALID); alpar@209: _dist->set(s,0); alpar@209: _queue[_queue_head++]=s; alpar@209: _queue_next_dist=_queue_head; alpar@209: } alpar@100: } alpar@209: alpar@100: ///Processes the next node. alpar@100: alpar@100: ///Processes the next node. alpar@100: /// alpar@100: ///\return The processed node. alpar@100: /// kpeter@244: ///\pre The queue must not be empty. alpar@100: Node processNextNode() alpar@100: { alpar@100: if(_queue_tail==_queue_next_dist) { alpar@209: _curr_dist++; alpar@209: _queue_next_dist=_queue_head; alpar@100: } alpar@100: Node n=_queue[_queue_tail++]; alpar@100: _processed->set(n,true); alpar@100: Node m; alpar@100: for(OutArcIt e(*G,n);e!=INVALID;++e) alpar@209: if(!(*_reached)[m=G->target(e)]) { alpar@209: _queue[_queue_head++]=m; alpar@209: _reached->set(m,true); alpar@209: _pred->set(m,e); alpar@209: _dist->set(m,_curr_dist); alpar@209: } alpar@100: return n; alpar@100: } alpar@100: alpar@100: ///Processes the next node. alpar@100: kpeter@244: ///Processes the next node and checks if the given target node alpar@100: ///is reached. If the target node is reachable from the processed kpeter@244: ///node, then the \c reach parameter will be set to \c true. alpar@100: /// alpar@100: ///\param target The target node. kpeter@244: ///\retval reach Indicates if the target node is reached. kpeter@244: ///It should be initially \c false. kpeter@244: /// alpar@100: ///\return The processed node. alpar@100: /// kpeter@244: ///\pre The queue must not be empty. alpar@100: Node processNextNode(Node target, bool& reach) alpar@100: { alpar@100: if(_queue_tail==_queue_next_dist) { alpar@209: _curr_dist++; alpar@209: _queue_next_dist=_queue_head; alpar@100: } alpar@100: Node n=_queue[_queue_tail++]; alpar@100: _processed->set(n,true); alpar@100: Node m; alpar@100: for(OutArcIt e(*G,n);e!=INVALID;++e) alpar@209: if(!(*_reached)[m=G->target(e)]) { alpar@209: _queue[_queue_head++]=m; alpar@209: _reached->set(m,true); alpar@209: _pred->set(m,e); alpar@209: _dist->set(m,_curr_dist); alpar@100: reach = reach || (target == m); alpar@209: } alpar@100: return n; alpar@100: } alpar@100: alpar@100: ///Processes the next node. alpar@100: kpeter@244: ///Processes the next node and checks if at least one of reached kpeter@244: ///nodes has \c true value in the \c nm node map. If one node kpeter@244: ///with \c true value is reachable from the processed node, then the kpeter@244: ///\c rnode parameter will be set to the first of such nodes. alpar@100: /// kpeter@244: ///\param nm A \c bool (or convertible) node map that indicates the kpeter@244: ///possible targets. alpar@100: ///\retval rnode The reached target node. kpeter@244: ///It should be initially \c INVALID. kpeter@244: /// alpar@100: ///\return The processed node. alpar@100: /// kpeter@244: ///\pre The queue must not be empty. alpar@100: template alpar@100: Node processNextNode(const NM& nm, Node& rnode) alpar@100: { alpar@100: if(_queue_tail==_queue_next_dist) { alpar@209: _curr_dist++; alpar@209: _queue_next_dist=_queue_head; alpar@100: } alpar@100: Node n=_queue[_queue_tail++]; alpar@100: _processed->set(n,true); alpar@100: Node m; alpar@100: for(OutArcIt e(*G,n);e!=INVALID;++e) alpar@209: if(!(*_reached)[m=G->target(e)]) { alpar@209: _queue[_queue_head++]=m; alpar@209: _reached->set(m,true); alpar@209: _pred->set(m,e); alpar@209: _dist->set(m,_curr_dist); alpar@209: if (nm[m] && rnode == INVALID) rnode = m; alpar@209: } alpar@100: return n; alpar@100: } alpar@209: kpeter@244: ///The next node to be processed. alpar@100: kpeter@244: ///Returns the next node to be processed or \c INVALID if the queue kpeter@244: ///is empty. kpeter@244: Node nextNode() const alpar@209: { alpar@100: return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; alpar@100: } alpar@209: alpar@100: ///\brief Returns \c false if there are nodes kpeter@244: ///to be processed. alpar@100: /// alpar@100: ///Returns \c false if there are nodes kpeter@244: ///to be processed in the queue. kpeter@244: bool emptyQueue() const { return _queue_tail==_queue_head; } kpeter@244: alpar@100: ///Returns the number of the nodes to be processed. alpar@209: alpar@100: ///Returns the number of the nodes to be processed in the queue. kpeter@244: int queueSize() const { return _queue_head-_queue_tail; } alpar@209: alpar@100: ///Executes the algorithm. alpar@100: alpar@100: ///Executes the algorithm. alpar@100: /// kpeter@244: ///This method runs the %BFS algorithm from the root node(s) kpeter@244: ///in order to compute the shortest path to each node. alpar@100: /// kpeter@244: ///The algorithm computes kpeter@244: ///- the shortest path tree (forest), kpeter@244: ///- the distance of each node from the root(s). kpeter@244: /// kpeter@244: ///\pre init() must be called and at least one root node should be kpeter@244: ///added with addSource() before using this function. kpeter@244: /// kpeter@244: ///\note b.start() is just a shortcut of the following code. kpeter@244: ///\code kpeter@244: /// while ( !b.emptyQueue() ) { kpeter@244: /// b.processNextNode(); kpeter@244: /// } kpeter@244: ///\endcode alpar@100: void start() alpar@100: { alpar@100: while ( !emptyQueue() ) processNextNode(); alpar@100: } alpar@209: kpeter@244: ///Executes the algorithm until the given target node is reached. alpar@100: kpeter@244: ///Executes the algorithm until the given target node is reached. alpar@100: /// alpar@100: ///This method runs the %BFS algorithm from the root node(s) alpar@100: ///in order to compute the shortest path to \c dest. kpeter@244: /// alpar@100: ///The algorithm computes kpeter@244: ///- the shortest path to \c dest, kpeter@244: ///- the distance of \c dest from the root(s). kpeter@244: /// kpeter@244: ///\pre init() must be called and at least one root node should be kpeter@244: ///added with addSource() before using this function. kpeter@244: /// kpeter@244: ///\note b.start(t) is just a shortcut of the following code. kpeter@244: ///\code kpeter@244: /// bool reach = false; kpeter@244: /// while ( !b.emptyQueue() && !reach ) { kpeter@244: /// b.processNextNode(t, reach); kpeter@244: /// } kpeter@244: ///\endcode alpar@100: void start(Node dest) alpar@100: { alpar@100: bool reach = false; alpar@100: while ( !emptyQueue() && !reach ) processNextNode(dest, reach); alpar@100: } alpar@209: alpar@100: ///Executes the algorithm until a condition is met. alpar@100: alpar@100: ///Executes the algorithm until a condition is met. alpar@100: /// kpeter@244: ///This method runs the %BFS algorithm from the root node(s) in kpeter@244: ///order to compute the shortest path to a node \c v with kpeter@244: /// nm[v] true, if such a node can be found. alpar@100: /// kpeter@244: ///\param nm A \c bool (or convertible) node map. The algorithm kpeter@244: ///will stop when it reaches a node \c v with nm[v] true. alpar@100: /// alpar@100: ///\return The reached node \c v with nm[v] true or alpar@100: ///\c INVALID if no such node was found. kpeter@244: /// kpeter@244: ///\pre init() must be called and at least one root node should be kpeter@244: ///added with addSource() before using this function. kpeter@244: /// kpeter@244: ///\note b.start(nm) is just a shortcut of the following code. kpeter@244: ///\code kpeter@244: /// Node rnode = INVALID; kpeter@244: /// while ( !b.emptyQueue() && rnode == INVALID ) { kpeter@244: /// b.processNextNode(nm, rnode); kpeter@244: /// } kpeter@244: /// return rnode; kpeter@244: ///\endcode kpeter@244: template kpeter@244: Node start(const NodeBoolMap &nm) alpar@100: { alpar@100: Node rnode = INVALID; alpar@100: while ( !emptyQueue() && rnode == INVALID ) { alpar@209: processNextNode(nm, rnode); alpar@100: } alpar@100: return rnode; alpar@100: } alpar@209: kpeter@244: ///Runs the algorithm from the given node. alpar@209: kpeter@244: ///This method runs the %BFS algorithm from node \c s kpeter@244: ///in order to compute the shortest path to each node. alpar@100: /// kpeter@244: ///The algorithm computes kpeter@244: ///- the shortest path tree, kpeter@244: ///- the distance of each node from the root. kpeter@244: /// kpeter@244: ///\note b.run(s) is just a shortcut of the following code. alpar@100: ///\code alpar@100: /// b.init(); alpar@100: /// b.addSource(s); alpar@100: /// b.start(); alpar@100: ///\endcode alpar@100: void run(Node s) { alpar@100: init(); alpar@100: addSource(s); alpar@100: start(); alpar@100: } alpar@209: alpar@100: ///Finds the shortest path between \c s and \c t. alpar@209: kpeter@244: ///This method runs the %BFS algorithm from node \c s kpeter@244: ///in order to compute the shortest path to \c t. alpar@100: /// kpeter@244: ///\return The length of the shortest s--t path, kpeter@244: ///if \c t is reachable form \c s, \c 0 otherwise. kpeter@244: /// kpeter@244: ///\note Apart from the return value, b.run(s,t) is just a kpeter@244: ///shortcut of the following code. alpar@100: ///\code alpar@100: /// b.init(); alpar@100: /// b.addSource(s); alpar@100: /// b.start(t); alpar@100: ///\endcode alpar@100: int run(Node s,Node t) { alpar@100: init(); alpar@100: addSource(s); alpar@100: start(t); alpar@100: return reached(t) ? _curr_dist : 0; alpar@100: } alpar@209: kpeter@244: ///Runs the algorithm to visit all nodes in the digraph. kpeter@244: kpeter@244: ///This method runs the %BFS algorithm in order to kpeter@244: ///compute the shortest path to each node. kpeter@244: /// kpeter@244: ///The algorithm computes kpeter@244: ///- the shortest path tree (forest), kpeter@244: ///- the distance of each node from the root(s). kpeter@244: /// kpeter@244: ///\note b.run(s) is just a shortcut of the following code. kpeter@244: ///\code kpeter@244: /// b.init(); kpeter@244: /// for (NodeIt n(gr); n != INVALID; ++n) { kpeter@244: /// if (!b.reached(n)) { kpeter@244: /// b.addSource(n); kpeter@244: /// b.start(); kpeter@244: /// } kpeter@244: /// } kpeter@244: ///\endcode kpeter@244: void run() { kpeter@244: init(); kpeter@244: for (NodeIt n(*G); n != INVALID; ++n) { kpeter@244: if (!reached(n)) { kpeter@244: addSource(n); kpeter@244: start(); kpeter@244: } kpeter@244: } kpeter@244: } kpeter@244: alpar@100: ///@} alpar@100: alpar@100: ///\name Query Functions alpar@100: ///The result of the %BFS algorithm can be obtained using these alpar@100: ///functions.\n kpeter@244: ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start() kpeter@244: ///"start()" must be called before using them. alpar@209: alpar@100: ///@{ alpar@100: kpeter@244: ///The shortest path to a node. alpar@100: kpeter@244: ///Returns the shortest path to a node. kpeter@244: /// kpeter@244: ///\warning \c t should be reachable from the root(s). kpeter@244: /// kpeter@244: ///\pre Either \ref run() or \ref start() must be called before kpeter@244: ///using this function. kpeter@244: Path path(Node t) const { return Path(*G, *_pred, t); } alpar@100: alpar@100: ///The distance of a node from the root(s). alpar@100: alpar@100: ///Returns the distance of a node from the root(s). kpeter@244: /// kpeter@244: ///\warning If node \c v is not reachable from the root(s), then kpeter@244: ///the return value of this function is undefined. kpeter@244: /// kpeter@244: ///\pre Either \ref run() or \ref start() must be called before kpeter@244: ///using this function. alpar@100: int dist(Node v) const { return (*_dist)[v]; } alpar@100: kpeter@244: ///Returns the 'previous arc' of the shortest path tree for a node. alpar@100: kpeter@244: ///This function returns the 'previous arc' of the shortest path kpeter@244: ///tree for the node \c v, i.e. it returns the last arc of a kpeter@244: ///shortest path from the root(s) to \c v. It is \c INVALID if \c v kpeter@244: ///is not reachable from the root(s) or if \c v is a root. kpeter@244: /// kpeter@244: ///The shortest path tree used here is equal to the shortest path kpeter@244: ///tree used in \ref predNode(). kpeter@244: /// kpeter@244: ///\pre Either \ref run() or \ref start() must be called before kpeter@244: ///using this function. alpar@100: Arc predArc(Node v) const { return (*_pred)[v];} alpar@100: kpeter@244: ///Returns the 'previous node' of the shortest path tree for a node. alpar@100: kpeter@244: ///This function returns the 'previous node' of the shortest path kpeter@244: ///tree for the node \c v, i.e. it returns the last but one node kpeter@244: ///from a shortest path from the root(s) to \c v. It is \c INVALID kpeter@244: ///if \c v is not reachable from the root(s) or if \c v is a root. kpeter@244: /// alpar@100: ///The shortest path tree used here is equal to the shortest path alpar@100: ///tree used in \ref predArc(). kpeter@244: /// alpar@100: ///\pre Either \ref run() or \ref start() must be called before alpar@100: ///using this function. alpar@100: Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: alpar@209: G->source((*_pred)[v]); } alpar@209: kpeter@244: ///\brief Returns a const reference to the node map that stores the kpeter@244: /// distances of the nodes. kpeter@244: /// kpeter@244: ///Returns a const reference to the node map that stores the distances kpeter@244: ///of the nodes calculated by the algorithm. kpeter@244: /// kpeter@244: ///\pre Either \ref run() or \ref init() kpeter@244: ///must be called before using this function. alpar@100: const DistMap &distMap() const { return *_dist;} alpar@209: kpeter@244: ///\brief Returns a const reference to the node map that stores the kpeter@244: ///predecessor arcs. kpeter@244: /// kpeter@244: ///Returns a const reference to the node map that stores the predecessor kpeter@244: ///arcs, which form the shortest path tree. kpeter@244: /// alpar@100: ///\pre Either \ref run() or \ref init() alpar@100: ///must be called before using this function. alpar@100: const PredMap &predMap() const { return *_pred;} alpar@209: kpeter@244: ///Checks if a node is reachable from the root(s). alpar@100: kpeter@244: ///Returns \c true if \c v is reachable from the root(s). alpar@100: ///\pre Either \ref run() or \ref start() alpar@100: ///must be called before using this function. kpeter@244: bool reached(Node v) const { return (*_reached)[v]; } alpar@209: alpar@100: ///@} alpar@100: }; alpar@100: kpeter@244: ///Default traits class of bfs() function. alpar@100: kpeter@244: ///Default traits class of bfs() function. kpeter@157: ///\tparam GR Digraph type. alpar@100: template alpar@100: struct BfsWizardDefaultTraits alpar@100: { kpeter@244: ///The type of the digraph the algorithm runs on. alpar@100: typedef GR Digraph; kpeter@244: kpeter@244: ///\brief The type of the map that stores the predecessor alpar@100: ///arcs of the shortest paths. alpar@209: /// kpeter@244: ///The type of the map that stores the predecessor alpar@100: ///arcs of the shortest paths. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. kpeter@244: typedef NullMap PredMap; kpeter@244: ///Instantiates a \ref PredMap. alpar@209: alpar@209: ///This function instantiates a \ref PredMap. kpeter@244: ///\param g is the digraph, to which we would like to define the kpeter@244: ///\ref PredMap. alpar@100: ///\todo The digraph alone may be insufficient to initialize alpar@100: #ifdef DOXYGEN kpeter@244: static PredMap *createPredMap(const Digraph &g) alpar@100: #else kpeter@244: static PredMap *createPredMap(const Digraph &) alpar@100: #endif alpar@100: { alpar@100: return new PredMap(); alpar@100: } alpar@100: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@209: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: typedef NullMap ProcessedMap; kpeter@244: ///Instantiates a \ref ProcessedMap. alpar@209: alpar@209: ///This function instantiates a \ref ProcessedMap. alpar@100: ///\param g is the digraph, to which kpeter@244: ///we would like to define the \ref ProcessedMap. alpar@100: #ifdef DOXYGEN kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &g) alpar@100: #else kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &) alpar@100: #endif alpar@100: { alpar@100: return new ProcessedMap(); alpar@100: } kpeter@244: alpar@100: ///The type of the map that indicates which nodes are reached. alpar@209: alpar@100: ///The type of the map that indicates which nodes are reached. kpeter@244: ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; kpeter@244: ///Instantiates a \ref ReachedMap. alpar@209: alpar@209: ///This function instantiates a \ref ReachedMap. kpeter@244: ///\param g is the digraph, to which alpar@100: ///we would like to define the \ref ReachedMap. kpeter@244: static ReachedMap *createReachedMap(const Digraph &g) alpar@100: { kpeter@244: return new ReachedMap(g); alpar@100: } alpar@209: kpeter@244: ///The type of the map that stores the distances of the nodes. kpeter@244: kpeter@244: ///The type of the map that stores the distances of the nodes. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: /// alpar@100: typedef NullMap DistMap; kpeter@244: ///Instantiates a \ref DistMap. alpar@209: alpar@209: ///This function instantiates a \ref DistMap. alpar@210: ///\param g is the digraph, to which we would like to define alpar@210: ///the \ref DistMap alpar@100: #ifdef DOXYGEN kpeter@244: static DistMap *createDistMap(const Digraph &g) alpar@100: #else kpeter@244: static DistMap *createDistMap(const Digraph &) alpar@100: #endif alpar@100: { alpar@100: return new DistMap(); alpar@100: } alpar@100: }; alpar@209: kpeter@244: /// Default traits class used by \ref BfsWizard alpar@100: alpar@100: /// To make it easier to use Bfs algorithm kpeter@244: /// we have created a wizard class. alpar@100: /// This \ref BfsWizard class needs default traits, kpeter@244: /// as well as the \ref Bfs class. alpar@100: /// The \ref BfsWizardBase is a class to be the default traits of the alpar@100: /// \ref BfsWizard class. alpar@100: template alpar@100: class BfsWizardBase : public BfsWizardDefaultTraits alpar@100: { alpar@100: alpar@100: typedef BfsWizardDefaultTraits Base; alpar@100: protected: kpeter@244: //The type of the nodes in the digraph. alpar@100: typedef typename Base::Digraph::Node Node; alpar@100: kpeter@244: //Pointer to the digraph the algorithm runs on. alpar@100: void *_g; kpeter@244: //Pointer to the map of reached nodes. alpar@100: void *_reached; kpeter@244: //Pointer to the map of processed nodes. alpar@100: void *_processed; kpeter@244: //Pointer to the map of predecessors arcs. alpar@100: void *_pred; kpeter@244: //Pointer to the map of distances. alpar@100: void *_dist; kpeter@244: //Pointer to the source node. alpar@100: Node _source; alpar@209: alpar@100: public: alpar@100: /// Constructor. alpar@209: alpar@100: /// This constructor does not require parameters, therefore it initiates alpar@100: /// all of the attributes to default values (0, INVALID). alpar@100: BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), kpeter@244: _dist(0), _source(INVALID) {} alpar@100: alpar@100: /// Constructor. alpar@209: alpar@100: /// This constructor requires some parameters, alpar@100: /// listed in the parameters list. alpar@100: /// Others are initiated to 0. kpeter@244: /// \param g The digraph the algorithm runs on. kpeter@244: /// \param s The source node. alpar@100: BfsWizardBase(const GR &g, Node s=INVALID) : alpar@209: _g(reinterpret_cast(const_cast(&g))), alpar@100: _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} alpar@100: alpar@100: }; alpar@209: kpeter@244: /// Auxiliary class for the function type interface of BFS algorithm. alpar@100: kpeter@244: /// This auxiliary class is created to implement the function type kpeter@244: /// interface of \ref Bfs algorithm. It uses the functions and features kpeter@244: /// of the plain \ref Bfs, but it is much simpler to use it. kpeter@244: /// It should only be used through the \ref bfs() function, which makes kpeter@244: /// it easier to use the algorithm. alpar@100: /// alpar@100: /// Simplicity means that the way to change the types defined alpar@100: /// in the traits class is based on functions that returns the new class alpar@100: /// and not on templatable built-in classes. alpar@100: /// When using the plain \ref Bfs alpar@100: /// the new class with the modified type comes from alpar@100: /// the original class by using the :: alpar@100: /// operator. In the case of \ref BfsWizard only kpeter@244: /// a function have to be called, and it will alpar@100: /// return the needed class. alpar@100: /// kpeter@244: /// It does not have own \ref run() method. When its \ref run() method kpeter@244: /// is called, it initiates a plain \ref Bfs object, and calls the kpeter@244: /// \ref Bfs::run() method of it. alpar@100: template alpar@100: class BfsWizard : public TR alpar@100: { alpar@100: typedef TR Base; alpar@100: kpeter@244: ///The type of the digraph the algorithm runs on. alpar@100: typedef typename TR::Digraph Digraph; kpeter@244: alpar@100: typedef typename Digraph::Node Node; alpar@100: typedef typename Digraph::NodeIt NodeIt; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::OutArcIt OutArcIt; alpar@209: kpeter@244: ///\brief The type of the map that stores the predecessor alpar@100: ///arcs of the shortest paths. alpar@100: typedef typename TR::PredMap PredMap; kpeter@244: ///\brief The type of the map that stores the distances of the nodes. alpar@100: typedef typename TR::DistMap DistMap; kpeter@244: ///\brief The type of the map that indicates which nodes are reached. kpeter@244: typedef typename TR::ReachedMap ReachedMap; kpeter@244: ///\brief The type of the map that indicates which nodes are processed. kpeter@244: typedef typename TR::ProcessedMap ProcessedMap; alpar@100: alpar@100: public: kpeter@244: alpar@100: /// Constructor. alpar@100: BfsWizard() : TR() {} alpar@100: alpar@100: /// Constructor that requires parameters. alpar@100: alpar@100: /// Constructor that requires parameters. alpar@100: /// These parameters will be the default values for the traits class. alpar@100: BfsWizard(const Digraph &g, Node s=INVALID) : alpar@100: TR(g,s) {} alpar@100: alpar@100: ///Copy constructor alpar@100: BfsWizard(const TR &b) : TR(b) {} alpar@100: alpar@100: ~BfsWizard() {} alpar@100: kpeter@244: ///Runs BFS algorithm from a source node. alpar@209: kpeter@244: ///Runs BFS algorithm from a source node. kpeter@244: ///The node can be given with the \ref source() function. alpar@100: void run() alpar@100: { alpar@100: if(Base::_source==INVALID) throw UninitializedParameter(); alpar@100: Bfs alg(*reinterpret_cast(Base::_g)); alpar@100: if(Base::_reached) alpar@209: alg.reachedMap(*reinterpret_cast(Base::_reached)); alpar@209: if(Base::_processed) alpar@100: alg.processedMap(*reinterpret_cast(Base::_processed)); alpar@209: if(Base::_pred) alpar@100: alg.predMap(*reinterpret_cast(Base::_pred)); alpar@209: if(Base::_dist) alpar@100: alg.distMap(*reinterpret_cast(Base::_dist)); alpar@100: alg.run(Base::_source); alpar@100: } alpar@100: kpeter@244: ///Runs BFS algorithm from the given node. alpar@100: kpeter@244: ///Runs BFS algorithm from the given node. alpar@100: ///\param s is the given source. alpar@100: void run(Node s) alpar@100: { alpar@100: Base::_source=s; alpar@100: run(); alpar@100: } alpar@100: alpar@100: /// Sets the source node, from which the Bfs algorithm runs. alpar@100: alpar@100: /// Sets the source node, from which the Bfs algorithm runs. alpar@100: /// \param s is the source node. alpar@209: BfsWizard &source(Node s) alpar@100: { alpar@100: Base::_source=s; alpar@100: return *this; alpar@100: } alpar@209: kpeter@244: template kpeter@244: struct DefPredMapBase : public Base { kpeter@244: typedef T PredMap; kpeter@244: static PredMap *createPredMap(const Digraph &) { return 0; }; kpeter@244: DefPredMapBase(const TR &b) : TR(b) {} kpeter@244: }; kpeter@244: ///\brief \ref named-templ-param "Named parameter" kpeter@244: ///for setting \ref PredMap object. kpeter@244: /// kpeter@244: /// \ref named-templ-param "Named parameter" kpeter@244: ///for setting \ref PredMap object. kpeter@244: template kpeter@244: BfsWizard > predMap(const T &t) kpeter@244: { kpeter@244: Base::_pred=reinterpret_cast(const_cast(&t)); kpeter@244: return BfsWizard >(*this); kpeter@244: } kpeter@244: kpeter@244: template kpeter@244: struct DefReachedMapBase : public Base { kpeter@244: typedef T ReachedMap; kpeter@244: static ReachedMap *createReachedMap(const Digraph &) { return 0; }; kpeter@244: DefReachedMapBase(const TR &b) : TR(b) {} kpeter@244: }; kpeter@244: ///\brief \ref named-templ-param "Named parameter" kpeter@244: ///for setting \ref ReachedMap object. kpeter@244: /// kpeter@244: /// \ref named-templ-param "Named parameter" kpeter@244: ///for setting \ref ReachedMap object. kpeter@244: template kpeter@244: BfsWizard > reachedMap(const T &t) kpeter@244: { kpeter@244: Base::_reached=reinterpret_cast(const_cast(&t)); kpeter@244: return BfsWizard >(*this); kpeter@244: } kpeter@244: kpeter@244: template kpeter@244: struct DefProcessedMapBase : public Base { kpeter@244: typedef T ProcessedMap; kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; kpeter@244: DefProcessedMapBase(const TR &b) : TR(b) {} kpeter@244: }; kpeter@244: ///\brief \ref named-templ-param "Named parameter" kpeter@244: ///for setting \ref ProcessedMap object. kpeter@244: /// kpeter@244: /// \ref named-templ-param "Named parameter" kpeter@244: ///for setting \ref ProcessedMap object. kpeter@244: template kpeter@244: BfsWizard > processedMap(const T &t) kpeter@244: { kpeter@244: Base::_processed=reinterpret_cast(const_cast(&t)); kpeter@244: return BfsWizard >(*this); kpeter@244: } kpeter@244: kpeter@244: template kpeter@244: struct DefDistMapBase : public Base { kpeter@244: typedef T DistMap; kpeter@244: static DistMap *createDistMap(const Digraph &) { return 0; }; kpeter@244: DefDistMapBase(const TR &b) : TR(b) {} kpeter@244: }; kpeter@244: ///\brief \ref named-templ-param "Named parameter" kpeter@244: ///for setting \ref DistMap object. kpeter@244: /// kpeter@244: /// \ref named-templ-param "Named parameter" kpeter@244: ///for setting \ref DistMap object. kpeter@244: template kpeter@244: BfsWizard > distMap(const T &t) kpeter@244: { kpeter@244: Base::_dist=reinterpret_cast(const_cast(&t)); kpeter@244: return BfsWizard >(*this); kpeter@244: } kpeter@244: alpar@100: }; alpar@209: alpar@100: ///Function type interface for Bfs algorithm. alpar@100: alpar@100: /// \ingroup search alpar@100: ///Function type interface for Bfs algorithm. alpar@100: /// alpar@100: ///This function also has several alpar@100: ///\ref named-templ-func-param "named parameters", alpar@100: ///they are declared as the members of class \ref BfsWizard. alpar@100: ///The following alpar@100: ///example shows how to use these parameters. alpar@100: ///\code alpar@100: /// bfs(g,source).predMap(preds).run(); alpar@100: ///\endcode alpar@100: ///\warning Don't forget to put the \ref BfsWizard::run() "run()" alpar@100: ///to the end of the parameter list. alpar@100: ///\sa BfsWizard alpar@100: ///\sa Bfs alpar@100: template alpar@100: BfsWizard > alpar@100: bfs(const GR &g,typename GR::Node s=INVALID) alpar@100: { alpar@100: return BfsWizard >(g,s); alpar@100: } alpar@100: alpar@100: #ifdef DOXYGEN kpeter@244: /// \brief Visitor class for BFS. alpar@209: /// alpar@100: /// This class defines the interface of the BfsVisit events, and kpeter@244: /// it could be the base of a real visitor class. alpar@100: template alpar@100: struct BfsVisitor { alpar@100: typedef _Digraph Digraph; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::Node Node; kpeter@244: /// \brief Called for the source node(s) of the BFS. alpar@209: /// kpeter@244: /// This function is called for the source node(s) of the BFS. kpeter@244: void start(const Node& node) {} kpeter@244: /// \brief Called when a node is reached first time. kpeter@244: /// kpeter@244: /// This function is called when a node is reached first time. kpeter@244: void reach(const Node& node) {} kpeter@244: /// \brief Called when a node is processed. kpeter@244: /// kpeter@244: /// This function is called when a node is processed. kpeter@244: void process(const Node& node) {} kpeter@244: /// \brief Called when an arc reaches a new node. kpeter@244: /// kpeter@244: /// This function is called when the BFS finds an arc whose target node kpeter@244: /// is not reached yet. alpar@100: void discover(const Arc& arc) {} kpeter@244: /// \brief Called when an arc is examined but its target node is alpar@100: /// already discovered. alpar@209: /// kpeter@244: /// This function is called when an arc is examined but its target node is alpar@100: /// already discovered. alpar@100: void examine(const Arc& arc) {} alpar@100: }; alpar@100: #else alpar@100: template alpar@100: struct BfsVisitor { alpar@100: typedef _Digraph Digraph; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::Node Node; kpeter@244: void start(const Node&) {} kpeter@244: void reach(const Node&) {} kpeter@244: void process(const Node&) {} alpar@100: void discover(const Arc&) {} alpar@100: void examine(const Arc&) {} alpar@100: alpar@100: template alpar@100: struct Constraints { alpar@100: void constraints() { alpar@209: Arc arc; alpar@209: Node node; kpeter@244: visitor.start(node); kpeter@244: visitor.reach(node); kpeter@244: visitor.process(node); alpar@209: visitor.discover(arc); alpar@209: visitor.examine(arc); alpar@100: } alpar@100: _Visitor& visitor; alpar@100: }; alpar@100: }; alpar@100: #endif alpar@100: alpar@100: /// \brief Default traits class of BfsVisit class. alpar@100: /// alpar@100: /// Default traits class of BfsVisit class. kpeter@244: /// \tparam _Digraph The type of the digraph the algorithm runs on. alpar@100: template alpar@100: struct BfsVisitDefaultTraits { alpar@100: kpeter@244: /// \brief The type of the digraph the algorithm runs on. alpar@100: typedef _Digraph Digraph; alpar@100: alpar@100: /// \brief The type of the map that indicates which nodes are reached. alpar@209: /// alpar@100: /// The type of the map that indicates which nodes are reached. kpeter@244: /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; alpar@100: kpeter@244: /// \brief Instantiates a \ref ReachedMap. alpar@100: /// alpar@209: /// This function instantiates a \ref ReachedMap. alpar@100: /// \param digraph is the digraph, to which alpar@100: /// we would like to define the \ref ReachedMap. alpar@100: static ReachedMap *createReachedMap(const Digraph &digraph) { alpar@100: return new ReachedMap(digraph); alpar@100: } alpar@100: alpar@100: }; alpar@100: alpar@100: /// \ingroup search alpar@209: /// kpeter@244: /// \brief %BFS algorithm class with visitor interface. alpar@209: /// alpar@100: /// This class provides an efficient implementation of the %BFS algorithm alpar@100: /// with visitor interface. alpar@100: /// alpar@100: /// The %BfsVisit class provides an alternative interface to the Bfs alpar@100: /// class. It works with callback mechanism, the BfsVisit object calls kpeter@244: /// the member functions of the \c Visitor class on every BFS event. alpar@100: /// kpeter@244: /// \tparam _Digraph The type of the digraph the algorithm runs on. alpar@210: /// The default value is kpeter@244: /// \ref ListDigraph. The value of _Digraph is not used directly by kpeter@244: /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits. kpeter@244: /// \tparam _Visitor The Visitor type that is used by the algorithm. kpeter@244: /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which kpeter@244: /// does not observe the BFS events. If you want to observe the BFS kpeter@244: /// events, you should implement your own visitor class. alpar@209: /// \tparam _Traits Traits class to set various data types used by the alpar@100: /// algorithm. The default traits class is alpar@100: /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". alpar@100: /// See \ref BfsVisitDefaultTraits for the documentation of kpeter@244: /// a BFS visit traits class. alpar@100: #ifdef DOXYGEN alpar@100: template alpar@100: #else alpar@100: template , alpar@209: typename _Traits = BfsDefaultTraits<_Digraph> > alpar@100: #endif alpar@100: class BfsVisit { alpar@100: public: alpar@209: alpar@100: /// \brief \ref Exception for uninitialized parameters. alpar@100: /// alpar@100: /// This error represents problems in the initialization kpeter@244: /// of the parameters of the algorithm. alpar@100: class UninitializedParameter : public lemon::UninitializedParameter { alpar@100: public: alpar@209: virtual const char* what() const throw() alpar@100: { alpar@209: return "lemon::BfsVisit::UninitializedParameter"; alpar@100: } alpar@100: }; alpar@100: kpeter@244: ///The traits class. alpar@100: typedef _Traits Traits; alpar@100: kpeter@244: ///The type of the digraph the algorithm runs on. alpar@100: typedef typename Traits::Digraph Digraph; alpar@100: kpeter@244: ///The visitor type used by the algorithm. alpar@100: typedef _Visitor Visitor; alpar@100: kpeter@244: ///The type of the map that indicates which nodes are reached. alpar@100: typedef typename Traits::ReachedMap ReachedMap; alpar@100: alpar@100: private: alpar@100: alpar@100: typedef typename Digraph::Node Node; alpar@100: typedef typename Digraph::NodeIt NodeIt; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::OutArcIt OutArcIt; alpar@100: kpeter@244: //Pointer to the underlying digraph. alpar@100: const Digraph *_digraph; kpeter@244: //Pointer to the visitor object. alpar@100: Visitor *_visitor; kpeter@244: //Pointer to the map of reached status of the nodes. alpar@100: ReachedMap *_reached; kpeter@244: //Indicates if _reached is locally allocated (true) or not. alpar@100: bool local_reached; alpar@100: alpar@100: std::vector _list; alpar@100: int _list_front, _list_back; alpar@100: kpeter@244: ///Creates the maps if necessary. kpeter@244: ///\todo Better memory allocation (instead of new). alpar@100: void create_maps() { alpar@100: if(!_reached) { alpar@209: local_reached = true; alpar@209: _reached = Traits::createReachedMap(*_digraph); alpar@100: } alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: BfsVisit() {} alpar@209: alpar@100: public: alpar@100: alpar@100: typedef BfsVisit Create; alpar@100: alpar@100: /// \name Named template parameters alpar@100: alpar@100: ///@{ alpar@100: template alpar@100: struct DefReachedMapTraits : public Traits { alpar@100: typedef T ReachedMap; alpar@100: static ReachedMap *createReachedMap(const Digraph &digraph) { alpar@209: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@209: /// \brief \ref named-templ-param "Named parameter" for setting kpeter@244: /// ReachedMap type. alpar@100: /// kpeter@244: /// \ref named-templ-param "Named parameter" for setting ReachedMap type. alpar@100: template alpar@100: struct DefReachedMap : public BfsVisit< Digraph, Visitor, alpar@209: DefReachedMapTraits > { alpar@100: typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits > Create; alpar@100: }; alpar@100: ///@} alpar@100: alpar@209: public: alpar@209: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Constructor. alpar@100: /// kpeter@244: /// \param digraph The digraph the algorithm runs on. kpeter@244: /// \param visitor The visitor object of the algorithm. alpar@209: BfsVisit(const Digraph& digraph, Visitor& visitor) alpar@100: : _digraph(&digraph), _visitor(&visitor), alpar@209: _reached(0), local_reached(false) {} alpar@209: alpar@100: /// \brief Destructor. alpar@100: ~BfsVisit() { alpar@100: if(local_reached) delete _reached; alpar@100: } alpar@100: kpeter@244: /// \brief Sets the map that indicates which nodes are reached. alpar@100: /// kpeter@244: /// Sets the map that indicates which nodes are reached. alpar@100: /// If you don't use this function before calling \ref run(), kpeter@244: /// it will allocate one. The destructor deallocates this alpar@100: /// automatically allocated map, of course. alpar@100: /// \return (*this) alpar@100: BfsVisit &reachedMap(ReachedMap &m) { alpar@100: if(local_reached) { alpar@209: delete _reached; alpar@209: local_reached = false; alpar@100: } alpar@100: _reached = &m; alpar@100: return *this; alpar@100: } alpar@100: alpar@100: public: kpeter@244: alpar@100: /// \name Execution control alpar@100: /// The simplest way to execute the algorithm is to use kpeter@244: /// one of the member functions called \ref lemon::BfsVisit::run() kpeter@244: /// "run()". alpar@100: /// \n kpeter@244: /// If you need more control on the execution, first you must call kpeter@244: /// \ref lemon::BfsVisit::init() "init()", then you can add several kpeter@244: /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". kpeter@244: /// Finally \ref lemon::BfsVisit::start() "start()" will perform the kpeter@244: /// actual path computation. alpar@100: alpar@100: /// @{ kpeter@244: alpar@100: /// \brief Initializes the internal data structures. alpar@100: /// alpar@100: /// Initializes the internal data structures. alpar@100: void init() { alpar@100: create_maps(); alpar@100: _list.resize(countNodes(*_digraph)); alpar@100: _list_front = _list_back = -1; alpar@100: for (NodeIt u(*_digraph) ; u != INVALID ; ++u) { alpar@209: _reached->set(u, false); alpar@100: } alpar@100: } alpar@209: alpar@100: /// \brief Adds a new source node. alpar@100: /// alpar@100: /// Adds a new source node to the set of nodes to be processed. alpar@100: void addSource(Node s) { alpar@100: if(!(*_reached)[s]) { alpar@209: _reached->set(s,true); alpar@209: _visitor->start(s); alpar@209: _visitor->reach(s); alpar@100: _list[++_list_back] = s; alpar@209: } alpar@100: } alpar@209: alpar@100: /// \brief Processes the next node. alpar@100: /// alpar@100: /// Processes the next node. alpar@100: /// alpar@100: /// \return The processed node. alpar@100: /// kpeter@244: /// \pre The queue must not be empty. alpar@209: Node processNextNode() { alpar@100: Node n = _list[++_list_front]; alpar@100: _visitor->process(n); alpar@100: Arc e; alpar@100: for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) { alpar@100: Node m = _digraph->target(e); alpar@100: if (!(*_reached)[m]) { alpar@100: _visitor->discover(e); alpar@100: _visitor->reach(m); alpar@100: _reached->set(m, true); alpar@100: _list[++_list_back] = m; alpar@100: } else { alpar@100: _visitor->examine(e); alpar@100: } alpar@100: } alpar@100: return n; alpar@100: } alpar@100: alpar@100: /// \brief Processes the next node. alpar@100: /// kpeter@244: /// Processes the next node and checks if the given target node alpar@100: /// is reached. If the target node is reachable from the processed kpeter@244: /// node, then the \c reach parameter will be set to \c true. alpar@100: /// alpar@100: /// \param target The target node. kpeter@244: /// \retval reach Indicates if the target node is reached. kpeter@244: /// It should be initially \c false. kpeter@244: /// alpar@100: /// \return The processed node. alpar@100: /// kpeter@244: /// \pre The queue must not be empty. alpar@100: Node processNextNode(Node target, bool& reach) { alpar@100: Node n = _list[++_list_front]; alpar@100: _visitor->process(n); alpar@100: Arc e; alpar@100: for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) { alpar@100: Node m = _digraph->target(e); alpar@100: if (!(*_reached)[m]) { alpar@100: _visitor->discover(e); alpar@100: _visitor->reach(m); alpar@100: _reached->set(m, true); alpar@100: _list[++_list_back] = m; alpar@100: reach = reach || (target == m); alpar@100: } else { alpar@100: _visitor->examine(e); alpar@100: } alpar@100: } alpar@100: return n; alpar@100: } alpar@100: alpar@100: /// \brief Processes the next node. alpar@100: /// kpeter@244: /// Processes the next node and checks if at least one of reached kpeter@244: /// nodes has \c true value in the \c nm node map. If one node kpeter@244: /// with \c true value is reachable from the processed node, then the kpeter@244: /// \c rnode parameter will be set to the first of such nodes. alpar@100: /// kpeter@244: /// \param nm A \c bool (or convertible) node map that indicates the kpeter@244: /// possible targets. alpar@100: /// \retval rnode The reached target node. kpeter@244: /// It should be initially \c INVALID. kpeter@244: /// alpar@100: /// \return The processed node. alpar@100: /// kpeter@244: /// \pre The queue must not be empty. alpar@100: template alpar@100: Node processNextNode(const NM& nm, Node& rnode) { alpar@100: Node n = _list[++_list_front]; alpar@100: _visitor->process(n); alpar@100: Arc e; alpar@100: for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) { alpar@100: Node m = _digraph->target(e); alpar@100: if (!(*_reached)[m]) { alpar@100: _visitor->discover(e); alpar@100: _visitor->reach(m); alpar@100: _reached->set(m, true); alpar@100: _list[++_list_back] = m; alpar@100: if (nm[m] && rnode == INVALID) rnode = m; alpar@100: } else { alpar@100: _visitor->examine(e); alpar@100: } alpar@100: } alpar@100: return n; alpar@100: } alpar@100: kpeter@244: /// \brief The next node to be processed. alpar@100: /// kpeter@244: /// Returns the next node to be processed or \c INVALID if the queue kpeter@244: /// is empty. kpeter@244: Node nextNode() const { alpar@100: return _list_front != _list_back ? _list[_list_front + 1] : INVALID; alpar@100: } alpar@100: alpar@100: /// \brief Returns \c false if there are nodes kpeter@244: /// to be processed. alpar@100: /// alpar@100: /// Returns \c false if there are nodes kpeter@244: /// to be processed in the queue. kpeter@244: bool emptyQueue() const { return _list_front == _list_back; } alpar@100: alpar@100: /// \brief Returns the number of the nodes to be processed. alpar@100: /// alpar@100: /// Returns the number of the nodes to be processed in the queue. kpeter@244: int queueSize() const { return _list_back - _list_front; } alpar@209: alpar@100: /// \brief Executes the algorithm. alpar@100: /// alpar@100: /// Executes the algorithm. alpar@100: /// kpeter@244: /// This method runs the %BFS algorithm from the root node(s) kpeter@244: /// in order to compute the shortest path to each node. kpeter@244: /// kpeter@244: /// The algorithm computes kpeter@244: /// - the shortest path tree (forest), kpeter@244: /// - the distance of each node from the root(s). kpeter@244: /// kpeter@244: /// \pre init() must be called and at least one root node should be added alpar@100: /// with addSource() before using this function. kpeter@244: /// kpeter@244: /// \note b.start() is just a shortcut of the following code. kpeter@244: /// \code kpeter@244: /// while ( !b.emptyQueue() ) { kpeter@244: /// b.processNextNode(); kpeter@244: /// } kpeter@244: /// \endcode alpar@100: void start() { alpar@100: while ( !emptyQueue() ) processNextNode(); alpar@100: } alpar@209: kpeter@244: /// \brief Executes the algorithm until the given target node is reached. alpar@100: /// kpeter@244: /// Executes the algorithm until the given target node is reached. alpar@100: /// kpeter@244: /// This method runs the %BFS algorithm from the root node(s) kpeter@244: /// in order to compute the shortest path to \c dest. kpeter@244: /// kpeter@244: /// The algorithm computes kpeter@244: /// - the shortest path to \c dest, kpeter@244: /// - the distance of \c dest from the root(s). kpeter@244: /// kpeter@244: /// \pre init() must be called and at least one root node should be kpeter@244: /// added with addSource() before using this function. kpeter@244: /// kpeter@244: /// \note b.start(t) is just a shortcut of the following code. kpeter@244: /// \code kpeter@244: /// bool reach = false; kpeter@244: /// while ( !b.emptyQueue() && !reach ) { kpeter@244: /// b.processNextNode(t, reach); kpeter@244: /// } kpeter@244: /// \endcode alpar@100: void start(Node dest) { alpar@100: bool reach = false; alpar@100: while ( !emptyQueue() && !reach ) processNextNode(dest, reach); alpar@100: } alpar@209: alpar@100: /// \brief Executes the algorithm until a condition is met. alpar@100: /// alpar@100: /// Executes the algorithm until a condition is met. alpar@100: /// kpeter@244: /// This method runs the %BFS algorithm from the root node(s) in kpeter@244: /// order to compute the shortest path to a node \c v with kpeter@244: /// nm[v] true, if such a node can be found. alpar@100: /// kpeter@244: /// \param nm must be a bool (or convertible) node map. The kpeter@244: /// algorithm will stop when it reaches a node \c v with alpar@100: /// nm[v] true. alpar@100: /// kpeter@244: /// \return The reached node \c v with nm[v] true or kpeter@244: /// \c INVALID if no such node was found. kpeter@244: /// kpeter@244: /// \pre init() must be called and at least one root node should be kpeter@244: /// added with addSource() before using this function. kpeter@244: /// kpeter@244: /// \note b.start(nm) is just a shortcut of the following code. kpeter@244: /// \code kpeter@244: /// Node rnode = INVALID; kpeter@244: /// while ( !b.emptyQueue() && rnode == INVALID ) { kpeter@244: /// b.processNextNode(nm, rnode); kpeter@244: /// } kpeter@244: /// return rnode; kpeter@244: /// \endcode alpar@100: template alpar@100: Node start(const NM &nm) { alpar@100: Node rnode = INVALID; alpar@100: while ( !emptyQueue() && rnode == INVALID ) { alpar@209: processNextNode(nm, rnode); alpar@100: } alpar@100: return rnode; alpar@100: } alpar@100: kpeter@244: /// \brief Runs the algorithm from the given node. alpar@100: /// kpeter@244: /// This method runs the %BFS algorithm from node \c s kpeter@244: /// in order to compute the shortest path to each node. kpeter@244: /// kpeter@244: /// The algorithm computes kpeter@244: /// - the shortest path tree, kpeter@244: /// - the distance of each node from the root. kpeter@244: /// kpeter@244: /// \note b.run(s) is just a shortcut of the following code. alpar@100: ///\code alpar@100: /// b.init(); alpar@100: /// b.addSource(s); alpar@100: /// b.start(); alpar@100: ///\endcode alpar@100: void run(Node s) { alpar@100: init(); alpar@100: addSource(s); alpar@100: start(); alpar@100: } alpar@100: kpeter@244: /// \brief Runs the algorithm to visit all nodes in the digraph. alpar@209: /// alpar@100: /// This method runs the %BFS algorithm in order to kpeter@244: /// compute the shortest path to each node. alpar@100: /// kpeter@244: /// The algorithm computes kpeter@244: /// - the shortest path tree (forest), kpeter@244: /// - the distance of each node from the root(s). kpeter@244: /// kpeter@244: /// \note b.run(s) is just a shortcut of the following code. alpar@100: ///\code alpar@100: /// b.init(); kpeter@244: /// for (NodeIt n(gr); n != INVALID; ++n) { kpeter@244: /// if (!b.reached(n)) { kpeter@244: /// b.addSource(n); alpar@100: /// b.start(); alpar@100: /// } alpar@100: /// } alpar@100: ///\endcode alpar@100: void run() { alpar@100: init(); alpar@100: for (NodeIt it(*_digraph); it != INVALID; ++it) { alpar@100: if (!reached(it)) { alpar@100: addSource(it); alpar@100: start(); alpar@100: } alpar@100: } alpar@100: } kpeter@244: alpar@100: ///@} alpar@100: alpar@100: /// \name Query Functions alpar@100: /// The result of the %BFS algorithm can be obtained using these alpar@100: /// functions.\n kpeter@244: /// Either \ref lemon::BfsVisit::run() "run()" or kpeter@244: /// \ref lemon::BfsVisit::start() "start()" must be called before kpeter@244: /// using them. alpar@100: ///@{ alpar@100: kpeter@244: /// \brief Checks if a node is reachable from the root(s). alpar@100: /// alpar@100: /// Returns \c true if \c v is reachable from the root(s). alpar@100: /// \pre Either \ref run() or \ref start() alpar@100: /// must be called before using this function. alpar@100: bool reached(Node v) { return (*_reached)[v]; } kpeter@244: alpar@100: ///@} kpeter@244: alpar@100: }; alpar@100: alpar@100: } //END OF NAMESPACE LEMON alpar@100: alpar@100: #endif