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@440: * Copyright (C) 2003-2009 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 kpeter@278: #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@492: ///Instantiates a \c PredMap. alpar@209: kpeter@492: ///This function instantiates a \ref PredMap. kpeter@244: ///\param g is the digraph, to which we would like to define the kpeter@492: ///\ref PredMap. 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. alpar@100: typedef NullMap ProcessedMap; kpeter@492: ///Instantiates a \c ProcessedMap. alpar@209: kpeter@492: ///This function instantiates a \ref ProcessedMap. alpar@100: ///\param g is the digraph, to which kpeter@492: ///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: kpeter@405: ///The type of the map that indicates which nodes are reached. kpeter@405: ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; kpeter@492: ///Instantiates a \c ReachedMap. alpar@209: kpeter@492: ///This function instantiates a \ref ReachedMap. kpeter@244: ///\param g is the digraph, to which kpeter@492: ///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@492: ///Instantiates a \c DistMap. alpar@209: kpeter@492: ///This function instantiates a \ref DistMap. kpeter@244: ///\param g is the digraph, to which we would like to define the kpeter@492: ///\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@278: ///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@405: ///The default type is \ref ListDigraph. alpar@100: #ifdef DOXYGEN alpar@100: template alpar@100: #else alpar@100: template > alpar@100: #endif alpar@100: class Bfs { alpar@100: public: 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@405: ///The \ref BfsDefaultTraits "traits class" of the algorithm. 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@280: //Creates the maps if necessary. 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: kpeter@405: ///\name Named Template Parameters alpar@100: alpar@100: ///@{ alpar@100: alpar@100: template kpeter@257: struct SetPredMapTraits : public Traits { alpar@100: typedef T PredMap; alpar@209: static PredMap *createPredMap(const Digraph &) alpar@100: { deba@290: LEMON_ASSERT(false, "PredMap is not initialized"); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@492: ///\c PredMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@492: ///\c PredMap type. kpeter@405: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: template kpeter@257: struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > { kpeter@257: typedef Bfs< Digraph, SetPredMapTraits > Create; alpar@100: }; alpar@209: alpar@100: template kpeter@257: struct SetDistMapTraits : public Traits { alpar@100: typedef T DistMap; alpar@209: static DistMap *createDistMap(const Digraph &) alpar@100: { deba@290: LEMON_ASSERT(false, "DistMap is not initialized"); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@492: ///\c DistMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@492: ///\c DistMap type. kpeter@405: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: template kpeter@257: struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > { kpeter@257: typedef Bfs< Digraph, SetDistMapTraits > Create; alpar@100: }; alpar@209: alpar@100: template kpeter@257: struct SetReachedMapTraits : public Traits { alpar@100: typedef T ReachedMap; alpar@209: static ReachedMap *createReachedMap(const Digraph &) alpar@100: { deba@290: LEMON_ASSERT(false, "ReachedMap is not initialized"); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@492: ///\c ReachedMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@492: ///\c ReachedMap type. kpeter@405: ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. alpar@100: template kpeter@257: struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > { kpeter@257: typedef Bfs< Digraph, SetReachedMapTraits > Create; alpar@100: }; alpar@209: alpar@100: template kpeter@257: struct SetProcessedMapTraits : public Traits { alpar@100: typedef T ProcessedMap; alpar@209: static ProcessedMap *createProcessedMap(const Digraph &) alpar@100: { deba@290: LEMON_ASSERT(false, "ProcessedMap is not initialized"); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@492: ///\c ProcessedMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@492: ///\c ProcessedMap type. kpeter@405: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: template kpeter@257: struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > { kpeter@257: typedef Bfs< Digraph, SetProcessedMapTraits > Create; alpar@100: }; alpar@209: kpeter@257: struct SetStandardProcessedMapTraits : 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); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; kpeter@244: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@492: ///\c ProcessedMap type to be Digraph::NodeMap. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@492: ///\c ProcessedMap type to be Digraph::NodeMap. alpar@100: ///If you don't set it explicitly, it will be automatically allocated. kpeter@257: struct SetStandardProcessedMap : kpeter@257: public Bfs< Digraph, SetStandardProcessedMapTraits > { kpeter@257: typedef Bfs< Digraph, SetStandardProcessedMapTraits > 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. kpeter@405: ///If you don't use this function before calling \ref run(Node) "run()" kpeter@405: ///or \ref init(), an instance will be allocated automatically. kpeter@405: ///The destructor deallocates this automatically allocated map, kpeter@405: ///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. kpeter@405: ///If you don't use this function before calling \ref run(Node) "run()" kpeter@405: ///or \ref init(), an instance will be allocated automatically. kpeter@405: ///The destructor deallocates this automatically allocated map, kpeter@405: ///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. kpeter@405: ///If you don't use this function before calling \ref run(Node) "run()" kpeter@405: ///or \ref init(), an instance will be allocated automatically. kpeter@405: ///The destructor deallocates this automatically allocated map, kpeter@405: ///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. kpeter@405: ///If you don't use this function before calling \ref run(Node) "run()" kpeter@405: ///or \ref init(), an instance will be allocated automatically. kpeter@405: ///The destructor deallocates this automatically allocated map, kpeter@405: ///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: kpeter@405: ///\name Execution Control kpeter@405: ///The simplest way to execute the BFS algorithm is to use one of the kpeter@405: ///member functions called \ref run(Node) "run()".\n kpeter@405: ///If you need more control on the execution, first you have to call kpeter@405: ///\ref init(), then you can add several source nodes with kpeter@405: ///\ref addSource(). Finally the actual path computation can be kpeter@405: ///performed with one of the \ref start() functions. alpar@100: alpar@100: ///@{ alpar@100: kpeter@405: ///\brief Initializes the internal data structures. kpeter@405: /// kpeter@244: ///Initializes the internal data structures. 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: kpeter@405: ///Returns \c false if there are nodes to be processed. kpeter@405: kpeter@405: ///Returns \c false if there are nodes to be processed kpeter@405: ///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: kpeter@405: ///Returns the number of the nodes to be processed kpeter@405: ///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) kpeter@286: ///in order to compute the shortest path to \c t. kpeter@244: /// alpar@100: ///The algorithm computes kpeter@286: ///- the shortest path to \c t, kpeter@286: ///- the distance of \c t 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 kpeter@286: void start(Node t) alpar@100: { alpar@100: bool reach = false; kpeter@286: while ( !emptyQueue() && !reach ) processNextNode(t, 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@286: ///Runs the algorithm from the given source 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@286: ///in order to compute the shortest path to node \c t kpeter@286: ///(it stops searching when \c t is processed). alpar@100: /// kpeter@286: ///\return \c true if \c t is reachable form \c s. 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 kpeter@286: bool run(Node s,Node t) { alpar@100: init(); alpar@100: addSource(s); alpar@100: start(t); kpeter@286: return reached(t); 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 kpeter@405: ///The results of the BFS algorithm can be obtained using these alpar@100: ///functions.\n kpeter@405: ///Either \ref run(Node) "run()" or \ref start() should be called kpeter@405: ///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@405: ///\warning \c t should be reached from the root(s). kpeter@244: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() kpeter@405: ///must be called before 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@405: ///\warning If node \c v is not reached from the root(s), then kpeter@244: ///the return value of this function is undefined. kpeter@244: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() kpeter@405: ///must be called before 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@405: ///shortest path from a root to \c v. It is \c INVALID if \c v kpeter@405: ///is not reached 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@405: ///\pre Either \ref run(Node) "run()" or \ref init() kpeter@405: ///must be called before 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@405: ///from a shortest path from a root to \c v. It is \c INVALID kpeter@405: ///if \c v is not reached 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: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() kpeter@405: ///must be called before 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@405: ///\pre Either \ref run(Node) "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: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() alpar@100: ///must be called before using this function. alpar@100: const PredMap &predMap() const { return *_pred;} alpar@209: kpeter@405: ///Checks if a node is reached from the root(s). alpar@100: kpeter@405: ///Returns \c true if \c v is reached from the root(s). kpeter@405: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() 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@278: typedef typename Digraph::template NodeMap PredMap; kpeter@301: ///Instantiates a PredMap. alpar@209: kpeter@301: ///This function instantiates a PredMap. kpeter@244: ///\param g is the digraph, to which we would like to define the kpeter@301: ///PredMap. kpeter@244: static PredMap *createPredMap(const Digraph &g) alpar@100: { kpeter@278: return new PredMap(g); 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. kpeter@278: ///By default it is a NullMap. alpar@100: typedef NullMap ProcessedMap; kpeter@301: ///Instantiates a ProcessedMap. alpar@209: kpeter@301: ///This function instantiates a ProcessedMap. alpar@100: ///\param g is the digraph, to which kpeter@301: ///we would like to define the 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@301: ///Instantiates a ReachedMap. alpar@209: kpeter@301: ///This function instantiates a ReachedMap. kpeter@244: ///\param g is the digraph, to which kpeter@301: ///we would like to define the 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. kpeter@278: typedef typename Digraph::template NodeMap DistMap; kpeter@301: ///Instantiates a DistMap. alpar@209: kpeter@301: ///This function instantiates a DistMap. alpar@210: ///\param g is the digraph, to which we would like to define kpeter@301: ///the DistMap kpeter@244: static DistMap *createDistMap(const Digraph &g) alpar@100: { kpeter@278: return new DistMap(g); alpar@100: } kpeter@278: kpeter@278: ///The type of the shortest paths. kpeter@278: kpeter@278: ///The type of the shortest paths. kpeter@278: ///It must meet the \ref concepts::Path "Path" concept. kpeter@278: typedef lemon::Path Path; alpar@100: }; alpar@209: kpeter@301: /// Default traits class used by 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@278: //Pointer to the shortest path to the target node. kpeter@278: void *_path; kpeter@278: //Pointer to the distance of the target node. kpeter@278: int *_di; alpar@209: alpar@100: public: alpar@100: /// Constructor. alpar@209: alpar@100: /// This constructor does not require parameters, therefore it initiates kpeter@278: /// all of the attributes to \c 0. alpar@100: BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), kpeter@278: _dist(0), _path(0), _di(0) {} alpar@100: alpar@100: /// Constructor. alpar@209: kpeter@278: /// This constructor requires one parameter, kpeter@278: /// others are initiated to \c 0. kpeter@244: /// \param g The digraph the algorithm runs on. kpeter@278: BfsWizardBase(const GR &g) : alpar@209: _g(reinterpret_cast(const_cast(&g))), kpeter@278: _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} alpar@100: alpar@100: }; alpar@209: kpeter@278: /// Auxiliary class for the function-type interface of BFS algorithm. alpar@100: kpeter@278: /// This auxiliary class is created to implement the kpeter@278: /// \ref bfs() "function-type interface" of \ref Bfs algorithm. kpeter@405: /// It does not have own \ref run(Node) "run()" method, it uses the kpeter@405: /// functions and features of the plain \ref Bfs. alpar@100: /// kpeter@278: /// This class should only be used through the \ref bfs() function, kpeter@278: /// which makes it easier to use the algorithm. 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; kpeter@278: ///The type of the shortest paths kpeter@278: typedef typename TR::Path Path; 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. kpeter@278: /// \param g The digraph the algorithm runs on. kpeter@278: BfsWizard(const Digraph &g) : kpeter@278: TR(g) {} alpar@100: alpar@100: ///Copy constructor alpar@100: BfsWizard(const TR &b) : TR(b) {} alpar@100: alpar@100: ~BfsWizard() {} alpar@100: kpeter@278: ///Runs BFS algorithm from the given source node. alpar@209: kpeter@278: ///This method runs BFS algorithm from node \c s kpeter@278: ///in order to compute the shortest path to each node. kpeter@278: void run(Node s) kpeter@278: { kpeter@278: Bfs alg(*reinterpret_cast(Base::_g)); kpeter@278: if (Base::_pred) kpeter@278: alg.predMap(*reinterpret_cast(Base::_pred)); kpeter@278: if (Base::_dist) kpeter@278: alg.distMap(*reinterpret_cast(Base::_dist)); kpeter@278: if (Base::_reached) kpeter@278: alg.reachedMap(*reinterpret_cast(Base::_reached)); kpeter@278: if (Base::_processed) kpeter@278: alg.processedMap(*reinterpret_cast(Base::_processed)); kpeter@278: if (s!=INVALID) kpeter@278: alg.run(s); kpeter@278: else kpeter@278: alg.run(); kpeter@278: } kpeter@278: kpeter@278: ///Finds the shortest path between \c s and \c t. kpeter@278: kpeter@278: ///This method runs BFS algorithm from node \c s kpeter@278: ///in order to compute the shortest path to node \c t kpeter@278: ///(it stops searching when \c t is processed). kpeter@278: /// kpeter@278: ///\return \c true if \c t is reachable form \c s. kpeter@278: bool run(Node s, Node t) kpeter@278: { kpeter@278: Bfs alg(*reinterpret_cast(Base::_g)); kpeter@278: if (Base::_pred) kpeter@278: alg.predMap(*reinterpret_cast(Base::_pred)); kpeter@278: if (Base::_dist) kpeter@278: alg.distMap(*reinterpret_cast(Base::_dist)); kpeter@278: if (Base::_reached) kpeter@278: alg.reachedMap(*reinterpret_cast(Base::_reached)); kpeter@278: if (Base::_processed) kpeter@278: alg.processedMap(*reinterpret_cast(Base::_processed)); kpeter@278: alg.run(s,t); kpeter@278: if (Base::_path) kpeter@278: *reinterpret_cast(Base::_path) = alg.path(t); kpeter@278: if (Base::_di) kpeter@278: *Base::_di = alg.dist(t); kpeter@278: return alg.reached(t); kpeter@278: } kpeter@278: kpeter@278: ///Runs BFS algorithm to visit all nodes in the digraph. kpeter@278: kpeter@278: ///This method runs BFS algorithm in order to compute kpeter@278: ///the shortest path to each node. alpar@100: void run() alpar@100: { kpeter@278: run(INVALID); alpar@100: } alpar@209: kpeter@244: template kpeter@257: struct SetPredMapBase : public Base { kpeter@244: typedef T PredMap; kpeter@244: static PredMap *createPredMap(const Digraph &) { return 0; }; kpeter@257: SetPredMapBase(const TR &b) : TR(b) {} kpeter@244: }; kpeter@278: ///\brief \ref named-func-param "Named parameter" kpeter@301: ///for setting PredMap object. kpeter@244: /// kpeter@278: ///\ref named-func-param "Named parameter" kpeter@301: ///for setting PredMap object. kpeter@244: template kpeter@257: BfsWizard > predMap(const T &t) kpeter@244: { kpeter@244: Base::_pred=reinterpret_cast(const_cast(&t)); kpeter@257: return BfsWizard >(*this); kpeter@244: } kpeter@244: kpeter@244: template kpeter@257: struct SetReachedMapBase : public Base { kpeter@244: typedef T ReachedMap; kpeter@244: static ReachedMap *createReachedMap(const Digraph &) { return 0; }; kpeter@257: SetReachedMapBase(const TR &b) : TR(b) {} kpeter@244: }; kpeter@278: ///\brief \ref named-func-param "Named parameter" kpeter@301: ///for setting ReachedMap object. kpeter@244: /// kpeter@278: /// \ref named-func-param "Named parameter" kpeter@301: ///for setting ReachedMap object. kpeter@244: template kpeter@257: BfsWizard > reachedMap(const T &t) kpeter@244: { kpeter@244: Base::_reached=reinterpret_cast(const_cast(&t)); kpeter@257: return BfsWizard >(*this); kpeter@244: } kpeter@244: kpeter@244: template kpeter@278: struct SetDistMapBase : public Base { kpeter@278: typedef T DistMap; kpeter@278: static DistMap *createDistMap(const Digraph &) { return 0; }; kpeter@278: SetDistMapBase(const TR &b) : TR(b) {} kpeter@278: }; kpeter@278: ///\brief \ref named-func-param "Named parameter" kpeter@301: ///for setting DistMap object. kpeter@278: /// kpeter@278: /// \ref named-func-param "Named parameter" kpeter@301: ///for setting DistMap object. kpeter@278: template kpeter@278: BfsWizard > distMap(const T &t) kpeter@278: { kpeter@278: Base::_dist=reinterpret_cast(const_cast(&t)); kpeter@278: return BfsWizard >(*this); kpeter@278: } kpeter@278: kpeter@278: template kpeter@257: struct SetProcessedMapBase : public Base { kpeter@244: typedef T ProcessedMap; kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; kpeter@257: SetProcessedMapBase(const TR &b) : TR(b) {} kpeter@244: }; kpeter@278: ///\brief \ref named-func-param "Named parameter" kpeter@301: ///for setting ProcessedMap object. kpeter@244: /// kpeter@278: /// \ref named-func-param "Named parameter" kpeter@301: ///for setting ProcessedMap object. kpeter@244: template kpeter@257: BfsWizard > processedMap(const T &t) kpeter@244: { kpeter@244: Base::_processed=reinterpret_cast(const_cast(&t)); kpeter@257: return BfsWizard >(*this); kpeter@244: } kpeter@244: kpeter@244: template kpeter@278: struct SetPathBase : public Base { kpeter@278: typedef T Path; kpeter@278: SetPathBase(const TR &b) : TR(b) {} kpeter@244: }; kpeter@278: ///\brief \ref named-func-param "Named parameter" kpeter@278: ///for getting the shortest path to the target node. kpeter@244: /// kpeter@278: ///\ref named-func-param "Named parameter" kpeter@278: ///for getting the shortest path to the target node. kpeter@244: template kpeter@278: BfsWizard > path(const T &t) kpeter@244: { kpeter@278: Base::_path=reinterpret_cast(const_cast(&t)); kpeter@278: return BfsWizard >(*this); kpeter@278: } kpeter@278: kpeter@278: ///\brief \ref named-func-param "Named parameter" kpeter@278: ///for getting the distance of the target node. kpeter@278: /// kpeter@278: ///\ref named-func-param "Named parameter" kpeter@278: ///for getting the distance of the target node. kpeter@278: BfsWizard dist(const int &d) kpeter@278: { kpeter@278: Base::_di=const_cast(&d); kpeter@278: return *this; kpeter@244: } kpeter@244: alpar@100: }; alpar@209: kpeter@278: ///Function-type interface for BFS algorithm. alpar@100: alpar@100: /// \ingroup search kpeter@278: ///Function-type interface for BFS algorithm. alpar@100: /// kpeter@278: ///This function also has several \ref named-func-param "named parameters", alpar@100: ///they are declared as the members of class \ref BfsWizard. kpeter@278: ///The following examples show how to use these parameters. alpar@100: ///\code kpeter@278: /// // Compute shortest path from node s to each node kpeter@278: /// bfs(g).predMap(preds).distMap(dists).run(s); kpeter@278: /// kpeter@278: /// // Compute shortest path from s to t kpeter@278: /// bool reached = bfs(g).path(p).dist(d).run(s,t); alpar@100: ///\endcode kpeter@405: ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()" alpar@100: ///to the end of the parameter list. alpar@100: ///\sa BfsWizard alpar@100: ///\sa Bfs alpar@100: template alpar@100: BfsWizard > kpeter@278: bfs(const GR &digraph) alpar@100: { kpeter@278: return BfsWizard >(digraph); 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. kpeter@492: template alpar@100: struct BfsVisitor { kpeter@492: typedef GR 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 kpeter@492: template alpar@100: struct BfsVisitor { kpeter@492: typedef GR 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@953: Constraints() {} 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@492: /// \tparam GR The type of the digraph the algorithm runs on. kpeter@492: template alpar@100: struct BfsVisitDefaultTraits { alpar@100: kpeter@244: /// \brief The type of the digraph the algorithm runs on. kpeter@492: typedef GR 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@301: /// \brief Instantiates a ReachedMap. alpar@100: /// kpeter@301: /// This function instantiates a ReachedMap. alpar@100: /// \param digraph is the digraph, to which kpeter@301: /// we would like to define the 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@492: /// \brief BFS algorithm class with visitor interface. alpar@209: /// kpeter@492: /// This class provides an efficient implementation of the BFS algorithm alpar@100: /// with visitor interface. alpar@100: /// kpeter@492: /// 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@252: /// This interface of the BFS algorithm should be used in special cases kpeter@252: /// when extra actions have to be performed in connection with certain kpeter@252: /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs() kpeter@252: /// instead. kpeter@252: /// kpeter@492: /// \tparam GR The type of the digraph the algorithm runs on. kpeter@492: /// The default type is \ref ListDigraph. kpeter@492: /// The value of GR is not used directly by \ref BfsVisit, kpeter@492: /// it is only passed to \ref BfsVisitDefaultTraits. kpeter@492: /// \tparam VS The Visitor type that is used by the algorithm. kpeter@492: /// \ref BfsVisitor "BfsVisitor" 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. kpeter@492: /// \tparam TR Traits class to set various data types used by the alpar@100: /// algorithm. The default traits class is kpeter@492: /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits". alpar@100: /// See \ref BfsVisitDefaultTraits for the documentation of kpeter@244: /// a BFS visit traits class. alpar@100: #ifdef DOXYGEN kpeter@492: template alpar@100: #else kpeter@492: template , kpeter@492: typename TR = BfsVisitDefaultTraits > alpar@100: #endif alpar@100: class BfsVisit { alpar@100: public: alpar@209: kpeter@244: ///The traits class. kpeter@492: typedef TR 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. kpeter@492: typedef VS 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: alpar@280: //Creates the maps if necessary. 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: kpeter@405: /// \name Named Template Parameters alpar@100: alpar@100: ///@{ alpar@100: template kpeter@257: struct SetReachedMapTraits : public Traits { alpar@100: typedef T ReachedMap; alpar@100: static ReachedMap *createReachedMap(const Digraph &digraph) { deba@290: LEMON_ASSERT(false, "ReachedMap is not initialized"); deba@290: return 0; // ignore warnings 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 kpeter@257: struct SetReachedMap : public BfsVisit< Digraph, Visitor, kpeter@257: SetReachedMapTraits > { kpeter@257: typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits > 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. kpeter@405: /// If you don't use this function before calling \ref run(Node) "run()" kpeter@405: /// or \ref init(), an instance will be allocated automatically. kpeter@405: /// The destructor deallocates this automatically allocated map, kpeter@405: /// 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: kpeter@405: /// \name Execution Control kpeter@405: /// The simplest way to execute the BFS algorithm is to use one of the kpeter@405: /// member functions called \ref run(Node) "run()".\n kpeter@405: /// If you need more control on the execution, first you have to call kpeter@405: /// \ref init(), then you can add several source nodes with kpeter@405: /// \ref addSource(). Finally the actual path computation can be kpeter@405: /// performed with one of the \ref start() functions. 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@286: /// in order to compute the shortest path to \c t. kpeter@244: /// kpeter@244: /// The algorithm computes kpeter@286: /// - the shortest path to \c t, kpeter@286: /// - the distance of \c t 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 kpeter@286: void start(Node t) { alpar@100: bool reach = false; kpeter@286: while ( !emptyQueue() && !reach ) processNextNode(t, 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@286: /// \brief Runs the algorithm from the given source 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@286: /// \brief Finds the shortest path between \c s and \c t. kpeter@286: /// kpeter@286: /// This method runs the %BFS algorithm from node \c s kpeter@286: /// in order to compute the shortest path to node \c t kpeter@286: /// (it stops searching when \c t is processed). kpeter@286: /// kpeter@286: /// \return \c true if \c t is reachable form \c s. kpeter@286: /// kpeter@286: /// \note Apart from the return value, b.run(s,t) is just a kpeter@286: /// shortcut of the following code. kpeter@286: ///\code kpeter@286: /// b.init(); kpeter@286: /// b.addSource(s); kpeter@286: /// b.start(t); kpeter@286: ///\endcode kpeter@286: bool run(Node s,Node t) { kpeter@286: init(); kpeter@286: addSource(s); kpeter@286: start(t); kpeter@286: return reached(t); kpeter@286: } kpeter@286: 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 kpeter@405: /// The results of the BFS algorithm can be obtained using these alpar@100: /// functions.\n kpeter@405: /// Either \ref run(Node) "run()" or \ref start() should be called kpeter@405: /// before using them. kpeter@405: alpar@100: ///@{ alpar@100: kpeter@405: /// \brief Checks if a node is reached from the root(s). alpar@100: /// kpeter@405: /// Returns \c true if \c v is reached from the root(s). kpeter@405: /// kpeter@405: /// \pre Either \ref run(Node) "run()" or \ref init() alpar@100: /// must be called before using this function. kpeter@420: bool reached(Node v) const { return (*_reached)[v]; } kpeter@244: alpar@100: ///@} kpeter@244: alpar@100: }; alpar@100: alpar@100: } //END OF NAMESPACE LEMON alpar@100: alpar@100: #endif