COIN-OR::LEMON - Graph Library

Changeset 1218:5331168bbb18 in lemon-0.x for src/lemon/bfs.h


Ignore:
Timestamp:
03/16/05 08:56:25 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1638
Message:
  • Several updates and clarifications on dijkstra.h
  • bfs.h and dfs.h is synchronized with dijkstra.h
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/bfs.h

    r1164 r1218  
    2121///\file
    2222///\brief Bfs algorithm.
    23 ///
    24 ///\todo Revise Manual.
    25 
    26 #include <lemon/bin_heap.h>
     23
     24#include <lemon/list_graph.h>
     25#include <lemon/graph_utils.h>
    2726#include <lemon/invalid.h>
    28 #include <lemon/graph_utils.h>
     27#include <lemon/error.h>
     28#include <lemon/maps.h>
    2929
    3030namespace lemon {
    3131
    32 /// \addtogroup flowalgs
    33 /// @{
    34 
     32
     33 
     34  ///Default traits class of Bfs class.
     35
     36  ///Default traits class of Bfs class.
     37  ///\param GR Graph type.
     38  template<class GR>
     39  struct BfsDefaultTraits
     40  {
     41    ///The graph type the algorithm runs on.
     42    typedef GR Graph;
     43    ///\brief The type of the map that stores the last
     44    ///edges of the shortest paths.
     45    ///
     46    ///The type of the map that stores the last
     47    ///edges of the shortest paths.
     48    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     49    ///
     50    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
     51    ///Instantiates a PredMap.
     52 
     53    ///This function instantiates a \ref PredMap.
     54    ///\param G is the graph, to which we would like to define the PredMap.
     55    ///\todo The graph alone may be insufficient to initialize
     56    static PredMap *createPredMap(const GR &G)
     57    {
     58      return new PredMap(G);
     59    }
     60//     ///\brief The type of the map that stores the last but one
     61//     ///nodes of the shortest paths.
     62//     ///
     63//     ///The type of the map that stores the last but one
     64//     ///nodes of the shortest paths.
     65//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     66//     ///
     67//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
     68//     ///Instantiates a PredNodeMap.
     69   
     70//     ///This function instantiates a \ref PredNodeMap.
     71//     ///\param G is the graph, to which
     72//     ///we would like to define the \ref PredNodeMap
     73//     static PredNodeMap *createPredNodeMap(const GR &G)
     74//     {
     75//       return new PredNodeMap();
     76//     }
     77
     78    ///The type of the map that indicates which nodes are processed.
     79 
     80    ///The type of the map that indicates which nodes are processed.
     81    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     82    ///\todo named parameter to set this type, function to read and write.
     83    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
     84    ///Instantiates a ProcessedMap.
     85 
     86    ///This function instantiates a \ref ProcessedMap.
     87    ///\param G is the graph, to which
     88    ///we would like to define the \ref ProcessedMap
     89    static ProcessedMap *createProcessedMap(const GR &G)
     90    {
     91      return new ProcessedMap();
     92    }
     93    ///The type of the map that indicates which nodes are reached.
     94 
     95    ///The type of the map that indicates which nodes are reached.
     96    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     97    ///\todo named parameter to set this type, function to read and write.
     98    typedef typename Graph::template NodeMap<bool> ReachedMap;
     99    ///Instantiates a ReachedMap.
     100 
     101    ///This function instantiates a \ref ReachedMap.
     102    ///\param G is the graph, to which
     103    ///we would like to define the \ref ReachedMap.
     104    static ReachedMap *createReachedMap(const GR &G)
     105    {
     106      return new ReachedMap(G);
     107    }
     108    ///The type of the map that stores the dists of the nodes.
     109 
     110    ///The type of the map that stores the dists of the nodes.
     111    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     112    ///
     113    typedef typename Graph::template NodeMap<int> DistMap;
     114    ///Instantiates a DistMap.
     115 
     116    ///This function instantiates a \ref DistMap.
     117    ///\param G is the graph, to which we would like to define the \ref DistMap
     118    static DistMap *createDistMap(const GR &G)
     119    {
     120      return new DistMap(G);
     121    }
     122  };
     123 
    35124  ///%BFS algorithm class.
    36 
    37   ///This class provides an efficient implementation of %BFS algorithm.
    38   ///\param GR The graph type the algorithm runs on.
    39   ///This class does the same as Dijkstra does with constant 1 edge length,
    40   ///but it is faster.
     125 
     126  ///\ingroup flowalgs
     127  ///This class provides an efficient implementation of the %BFS algorithm.
    41128  ///
    42   ///\author Alpar Juttner
     129  ///\param GR The graph type the algorithm runs on. The default value is
     130  ///\ref ListGraph. The value of GR is not used directly by Bfs, it
     131  ///is only passed to \ref BfsDefaultTraits.
     132  ///\param TR Traits class to set various data types used by the algorithm.
     133  ///The default traits class is
     134  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
     135  ///See \ref BfsDefaultTraits for the documentation of
     136  ///a Bfs traits class.
     137  ///
     138  ///\author Jacint Szabo and Alpar Juttner
     139  ///\todo A compare object would be nice.
    43140
    44141#ifdef DOXYGEN
    45   template <typename GR>
     142  template <typename GR,
     143            typename TR>
    46144#else
    47   template <typename GR>
     145  template <typename GR=ListGraph,
     146            typename TR=BfsDefaultTraits<GR> >
    48147#endif
    49   class Bfs{
     148  class Bfs {
    50149  public:
     150    /**
     151     * \brief \ref Exception for uninitialized parameters.
     152     *
     153     * This error represents problems in the initialization
     154     * of the parameters of the algorithms.
     155     */
     156    class UninitializedParameter : public lemon::UninitializedParameter {
     157    public:
     158      virtual const char* exceptionName() const {
     159        return "lemon::Bfs::UninitializedParameter";
     160      }
     161    };
     162
     163    typedef TR Traits;
    51164    ///The type of the underlying graph.
    52     typedef GR Graph;
     165    typedef typename TR::Graph Graph;
    53166    ///\e
    54167    typedef typename Graph::Node Node;
     
    62175    ///\brief The type of the map that stores the last
    63176    ///edges of the shortest paths.
    64     typedef typename Graph::template NodeMap<Edge> PredMap;
    65     ///\brief The type of the map that stores the last but one
    66     ///nodes of the shortest paths.
    67     typedef typename Graph::template NodeMap<Node> PredNodeMap;
     177    typedef typename TR::PredMap PredMap;
     178//     ///\brief The type of the map that stores the last but one
     179//     ///nodes of the shortest paths.
     180//     typedef typename TR::PredNodeMap PredNodeMap;
     181    ///The type of the map indicating which nodes are reached.
     182    typedef typename TR::ReachedMap ReachedMap;
     183    ///The type of the map indicating which nodes are processed.
     184    typedef typename TR::ProcessedMap ProcessedMap;
    68185    ///The type of the map that stores the dists of the nodes.
    69     typedef typename Graph::template NodeMap<int> DistMap;
    70 
     186    typedef typename TR::DistMap DistMap;
    71187  private:
    72188    /// Pointer to the underlying graph.
    73189    const Graph *G;
    74190    ///Pointer to the map of predecessors edges.
    75     PredMap *predecessor;
    76     ///Indicates if \ref predecessor is locally allocated (\c true) or not.
    77     bool local_predecessor;
    78     ///Pointer to the map of predecessors nodes.
    79     PredNodeMap *pred_node;
    80     ///Indicates if \ref pred_node is locally allocated (\c true) or not.
    81     bool local_pred_node;
     191    PredMap *_pred;
     192    ///Indicates if \ref _pred is locally allocated (\c true) or not.
     193    bool local_pred;
     194//     ///Pointer to the map of predecessors nodes.
     195//     PredNodeMap *_predNode;
     196//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
     197//     bool local_predNode;
    82198    ///Pointer to the map of distances.
    83     DistMap *distance;
    84     ///Indicates if \ref distance is locally allocated (\c true) or not.
    85     bool local_distance;
    86 
    87     ///The source node of the last execution.
    88     Node source;
    89 
    90 
    91     ///Initializes the maps.
    92     void init_maps()
    93     {
    94       if(!predecessor) {
    95         local_predecessor = true;
    96         predecessor = new PredMap(*G);
    97       }
    98       if(!pred_node) {
    99         local_pred_node = true;
    100         pred_node = new PredNodeMap(*G);
    101       }
    102       if(!distance) {
    103         local_distance = true;
    104         distance = new DistMap(*G);
    105       }
    106     }
    107    
    108   public :   
     199    DistMap *_dist;
     200    ///Indicates if \ref _dist is locally allocated (\c true) or not.
     201    bool local_dist;
     202    ///Pointer to the map of reached status of the nodes.
     203    ReachedMap *_reached;
     204    ///Indicates if \ref _reached is locally allocated (\c true) or not.
     205    bool local_reached;
     206    ///Pointer to the map of processed status of the nodes.
     207    ProcessedMap *_processed;
     208    ///Indicates if \ref _processed is locally allocated (\c true) or not.
     209    bool local_processed;
     210
     211    std::vector<typename Graph::Node> _queue;
     212    int _queue_head,_queue_tail,_queue_next_dist;
     213    int _curr_dist;
     214//     ///The source node of the last execution.
     215//     Node source;
     216
     217    ///Creates the maps if necessary.
     218   
     219    ///\todo Error if \c G are \c NULL.
     220    ///\todo Better memory allocation (instead of new).
     221    void create_maps()
     222    {
     223      if(!_pred) {
     224        local_pred = true;
     225        _pred = Traits::createPredMap(*G);
     226      }
     227//       if(!_predNode) {
     228//      local_predNode = true;
     229//      _predNode = Traits::createPredNodeMap(*G);
     230//       }
     231      if(!_dist) {
     232        local_dist = true;
     233        _dist = Traits::createDistMap(*G);
     234      }
     235      if(!_reached) {
     236        local_reached = true;
     237        _reached = Traits::createReachedMap(*G);
     238      }
     239      if(!_processed) {
     240        local_processed = true;
     241        _processed = Traits::createProcessedMap(*G);
     242      }
     243    }
     244   
     245  public :
     246 
     247    ///\name Named template parameters
     248
     249    ///@{
     250
     251    template <class T>
     252    struct DefPredMapTraits : public Traits {
     253      typedef T PredMap;
     254      static PredMap *createPredMap(const Graph &G)
     255      {
     256        throw UninitializedParameter();
     257      }
     258    };
     259    ///\ref named-templ-param "Named parameter" for setting PredMap type
     260
     261    ///\ref named-templ-param "Named parameter" for setting PredMap type
     262    ///
     263    template <class T>
     264    class DefPredMap : public Bfs< Graph,
     265                                        DefPredMapTraits<T> > { };
     266   
     267//     template <class T>
     268//     struct DefPredNodeMapTraits : public Traits {
     269//       typedef T PredNodeMap;
     270//       static PredNodeMap *createPredNodeMap(const Graph &G)
     271//       {
     272//      throw UninitializedParameter();
     273//       }
     274//     };
     275//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     276
     277//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     278//     ///
     279//     template <class T>
     280//     class DefPredNodeMap : public Bfs< Graph,
     281//                                          LengthMap,
     282//                                          DefPredNodeMapTraits<T> > { };
     283   
     284    template <class T>
     285    struct DefDistMapTraits : public Traits {
     286      typedef T DistMap;
     287      static DistMap *createDistMap(const Graph &G)
     288      {
     289        throw UninitializedParameter();
     290      }
     291    };
     292    ///\ref named-templ-param "Named parameter" for setting DistMap type
     293
     294    ///\ref named-templ-param "Named parameter" for setting DistMap type
     295    ///
     296    template <class T>
     297    class DefDistMap : public Bfs< Graph,
     298                                   DefDistMapTraits<T> > { };
     299   
     300    template <class T>
     301    struct DefReachedMapTraits : public Traits {
     302      typedef T ReachedMap;
     303      static ReachedMap *createReachedMap(const Graph &G)
     304      {
     305        throw UninitializedParameter();
     306      }
     307    };
     308    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     309
     310    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     311    ///
     312    template <class T>
     313    class DefReachedMap : public Bfs< Graph,
     314                                      DefReachedMapTraits<T> > { };
     315   
     316    struct DefGraphReachedMapTraits : public Traits {
     317      typedef typename Graph::template NodeMap<bool> ReachedMap;
     318      static ReachedMap *createReachedMap(const Graph &G)
     319      {
     320        return new ReachedMap(G);
     321      }
     322    };
     323    template <class T>
     324    struct DefProcessedMapTraits : public Traits {
     325      typedef T ProcessedMap;
     326      static ProcessedMap *createProcessedMap(const Graph &G)
     327      {
     328        throw UninitializedParameter();
     329      }
     330    };
     331    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     332
     333    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     334    ///
     335    template <class T>
     336    class DefProcessedMap : public Bfs< Graph,
     337                                        DefProcessedMapTraits<T> > { };
     338   
     339    struct DefGraphProcessedMapTraits : public Traits {
     340      typedef typename Graph::template NodeMap<bool> ProcessedMap;
     341      static ProcessedMap *createProcessedMap(const Graph &G)
     342      {
     343        return new ProcessedMap(G);
     344      }
     345    };
     346    ///\brief \ref named-templ-param "Named parameter"
     347    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
     348    ///
     349    ///\ref named-templ-param "Named parameter"
     350    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
     351    ///If you don't set it explicitely, it will be automatically allocated.
     352    template <class T>
     353    class DefProcessedMapToBeDefaultMap :
     354      public Bfs< Graph,
     355                  DefGraphProcessedMapTraits> { };
     356   
     357    ///@}
     358
     359  public:     
     360   
    109361    ///Constructor.
    110362   
     
    113365    Bfs(const Graph& _G) :
    114366      G(&_G),
    115       predecessor(NULL), local_predecessor(false),
    116       pred_node(NULL), local_pred_node(false),
    117       distance(NULL), local_distance(false)
     367      _pred(NULL), local_pred(false),
     368//       _predNode(NULL), local_predNode(false),
     369      _dist(NULL), local_dist(false),
     370      _reached(NULL), local_reached(false),
     371      _processed(NULL), local_processed(false)
    118372    { }
    119373   
     
    121375    ~Bfs()
    122376    {
    123       if(local_predecessor) delete predecessor;
    124       if(local_pred_node) delete pred_node;
    125       if(local_distance) delete distance;
     377      if(local_pred) delete _pred;
     378//       if(local_predNode) delete _predNode;
     379      if(local_dist) delete _dist;
     380      if(local_reached) delete _reached;
     381      if(local_processed) delete _processed;
    126382    }
    127383
     
    133389    ///automatically allocated map, of course.
    134390    ///\return <tt> (*this) </tt>
    135     Bfs &setPredMap(PredMap &m)
    136     {
    137       if(local_predecessor) {
    138         delete predecessor;
    139         local_predecessor=false;
    140       }
    141       predecessor = &m;
     391    Bfs &predMap(PredMap &m)
     392    {
     393      if(local_pred) {
     394        delete _pred;
     395        local_pred=false;
     396      }
     397      _pred = &m;
    142398      return *this;
    143399    }
    144400
    145     ///Sets the map storing the predecessor nodes.
    146 
    147     ///Sets the map storing the predecessor nodes.
     401    ///Sets the map indicating the reached nodes.
     402
     403    ///Sets the map indicating the reached nodes.
    148404    ///If you don't use this function before calling \ref run(),
    149405    ///it will allocate one. The destuctor deallocates this
    150406    ///automatically allocated map, of course.
    151407    ///\return <tt> (*this) </tt>
    152     Bfs &setPredNodeMap(PredNodeMap &m)
    153     {
    154       if(local_pred_node) {
    155         delete pred_node;
    156         local_pred_node=false;
    157       }
    158       pred_node = &m;
     408    Bfs &reachedMap(ReachedMap &m)
     409    {
     410      if(local_reached) {
     411        delete _reached;
     412        local_reached=false;
     413      }
     414      _reached = &m;
    159415      return *this;
    160416    }
     417
     418    ///Sets the map indicating the processed nodes.
     419
     420    ///Sets the map indicating the processed nodes.
     421    ///If you don't use this function before calling \ref run(),
     422    ///it will allocate one. The destuctor deallocates this
     423    ///automatically allocated map, of course.
     424    ///\return <tt> (*this) </tt>
     425    Bfs &processedMap(ProcessedMap &m)
     426    {
     427      if(local_processed) {
     428        delete _processed;
     429        local_processed=false;
     430      }
     431      _processed = &m;
     432      return *this;
     433    }
     434
     435//     ///Sets the map storing the predecessor nodes.
     436
     437//     ///Sets the map storing the predecessor nodes.
     438//     ///If you don't use this function before calling \ref run(),
     439//     ///it will allocate one. The destuctor deallocates this
     440//     ///automatically allocated map, of course.
     441//     ///\return <tt> (*this) </tt>
     442//     Bfs &predNodeMap(PredNodeMap &m)
     443//     {
     444//       if(local_predNode) {
     445//      delete _predNode;
     446//      local_predNode=false;
     447//       }
     448//       _predNode = &m;
     449//       return *this;
     450//     }
    161451
    162452    ///Sets the map storing the distances calculated by the algorithm.
     
    167457    ///automatically allocated map, of course.
    168458    ///\return <tt> (*this) </tt>
    169     Bfs &setDistMap(DistMap &m)
    170     {
    171       if(local_distance) {
    172         delete distance;
    173         local_distance=false;
    174       }
    175       distance = &m;
     459    Bfs &distMap(DistMap &m)
     460    {
     461      if(local_dist) {
     462        delete _dist;
     463        local_dist=false;
     464      }
     465      _dist = &m;
    176466      return *this;
    177467    }
    178    
    179   ///Runs %BFS algorithm from node \c s.
    180 
    181   ///This method runs the %BFS algorithm from a root node \c s
    182   ///in order to
    183   ///compute a
    184   ///shortest path to each node. The algorithm computes
    185   ///- The %BFS tree.
    186   ///- The distance of each node from the root.
    187  
     468
     469  public:
     470    ///\name Execution control
     471    ///The simplest way to execute the algorithm is to use
     472    ///one of the member functions called \c run(...).
     473    ///\n
     474    ///If you need more control on the execution,
     475    ///first you must call \ref init(), then you can add several source nodes
     476    ///with \ref addSource().
     477    ///Finally \ref start() will perform the actual path
     478    ///computation.
     479
     480    ///@{
     481
     482    ///Initializes the internal data structures.
     483
     484    ///Initializes the internal data structures.
     485    ///
     486    void init()
     487    {
     488      create_maps();
     489      _queue.resize(countNodes(*G));
     490      _queue_head=_queue_tail=0;
     491      _curr_dist=1;
     492      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
     493        _pred->set(u,INVALID);
     494//      _predNode->set(u,INVALID);
     495        _reached->set(u,false);
     496        _processed->set(u,false);
     497      }
     498    }
     499   
     500    ///Adds a new source node.
     501
     502    ///Adds a new source node to the set of nodes to be processed.
     503    ///
     504    void addSource(Node s)
     505    {
     506      if(!(*_reached)[s])
     507        {
     508          _reached->set(s,true);
     509          _pred->set(s,INVALID);
     510          _dist->set(s,0);
     511          _queue[_queue_head++]=s;
     512          _queue_next_dist=_queue_head;
     513        }
     514    }
     515   
     516    ///Processes the next node.
     517
     518    ///Processes the next node.
     519    ///
     520    ///\warning The queue must not be empty!
     521    void processNextNode()
     522    {
     523      if(_queue_tail==_queue_next_dist) {
     524        _curr_dist++;
     525        _queue_next_dist=_queue_head;
     526      }
     527      Node n=_queue[_queue_tail++];
     528      _processed->set(n,true);
     529      Node m;
     530      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
     531        if(!(*_reached)[m=G->target(e)]) {
     532          _queue[_queue_head++]=m;
     533          _reached->set(m,true);
     534          _pred->set(m,e);
     535//        _pred_node->set(m,n);
     536          _dist->set(m,_curr_dist);
     537        }
     538    }
     539     
     540    ///\brief Returns \c false if there are nodes
     541    ///to be processed in the queue
     542    ///
     543    ///Returns \c false if there are nodes
     544    ///to be processed in the queue
     545    bool emptyQueue() { return _queue_tail==_queue_head; }
     546    ///Returns the number of the nodes to be processed.
     547   
     548    ///Returns the number of the nodes to be processed in the queue.
     549    ///
     550    int queueSize() { return _queue_head-_queue_tail; }
     551   
     552    ///Executes the algorithm.
     553
     554    ///Executes the algorithm.
     555    ///
     556    ///\pre init() must be called and at least one node should be added
     557    ///with addSource() before using this function.
     558    ///
     559    ///This method runs the %BFS algorithm from the root node(s)
     560    ///in order to
     561    ///compute the
     562    ///shortest path to each node. The algorithm computes
     563    ///- The shortest path tree.
     564    ///- The distance of each node from the root(s).
     565    ///
     566    void start()
     567    {
     568      while ( !emptyQueue() ) processNextNode();
     569    }
     570   
     571    ///Executes the algorithm until \c dest is reached.
     572
     573    ///Executes the algorithm until \c dest is reached.
     574    ///
     575    ///\pre init() must be called and at least one node should be added
     576    ///with addSource() before using this function.
     577    ///
     578    ///This method runs the %BFS algorithm from the root node(s)
     579    ///in order to
     580    ///compute the
     581    ///shortest path to \c dest. The algorithm computes
     582    ///- The shortest path to \c  dest.
     583    ///- The distance of \c dest from the root(s).
     584    ///
     585    void start(Node dest)
     586    {
     587      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
     588    }
     589   
     590    ///Executes the algorithm until a condition is met.
     591
     592    ///Executes the algorithm until a condition is met.
     593    ///
     594    ///\pre init() must be called and at least one node should be added
     595    ///with addSource() before using this function.
     596    ///
     597    ///\param nm must be a bool (or convertible) node map. The algorithm
     598    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
     599    template<class NM>
     600      void start(const NM &nm)
     601      {
     602        while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
     603      }
     604   
     605    ///Runs %BFS algorithm from node \c s.
     606   
     607    ///This method runs the %BFS algorithm from a root node \c s
     608    ///in order to
     609    ///compute the
     610    ///shortest path to each node. The algorithm computes
     611    ///- The shortest path tree.
     612    ///- The distance of each node from the root.
     613    ///
     614    ///\note d.run(s) is just a shortcut of the following code.
     615    ///\code
     616    ///  d.init();
     617    ///  d.addSource(s);
     618    ///  d.start();
     619    ///\endcode
    188620    void run(Node s) {
    189      
    190       init_maps();
    191      
    192       source = s;
    193      
    194       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    195         predecessor->set(u,INVALID);
    196         pred_node->set(u,INVALID);
    197       }
    198      
    199       int N = countNodes(*G);
    200       std::vector<typename Graph::Node> Q(N);
    201       int Qh=0;
    202       int Qt=0;
    203      
    204       Q[Qh++]=source;
    205       distance->set(s, 0);
    206       do {
    207         Node m;
    208         Node n=Q[Qt++];
    209         int d= (*distance)[n]+1;
    210        
    211         for(OutEdgeIt e(*G,n);e!=INVALID;++e)
    212           if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) {
    213             Q[Qh++]=m;
    214             predecessor->set(m,e);
    215             pred_node->set(m,n);
    216             distance->set(m,d);
    217           }
    218       } while(Qt!=Qh);
    219     }
    220    
    221     ///The distance of a node from the root.
    222 
    223     ///Returns the distance of a node from the root.
     621      init();
     622      addSource(s);
     623      start();
     624    }
     625   
     626    ///Finds the shortest path between \c s and \c t.
     627   
     628    ///Finds the shortest path between \c s and \c t.
     629    ///
     630    ///\return The length of the shortest s---t path if there exists one,
     631    ///0 otherwise.
     632    ///\note Apart from the return value, d.run(s) is
     633    ///just a shortcut of the following code.
     634    ///\code
     635    ///  d.init();
     636    ///  d.addSource(s);
     637    ///  d.start(t);
     638    ///\endcode
     639    int run(Node s,Node t) {
     640      init();
     641      addSource(s);
     642      start(t);
     643      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
     644    }
     645   
     646    ///@}
     647
     648    ///\name Query Functions
     649    ///The result of the %BFS algorithm can be obtained using these
     650    ///functions.\n
     651    ///Before the use of these functions,
     652    ///either run() or start() must be called.
     653   
     654    ///@{
     655
     656    ///The distance of a node from the root(s).
     657
     658    ///Returns the distance of a node from the root(s).
    224659    ///\pre \ref run() must be called before using this function.
    225     ///\warning If node \c v in unreachable from the root the return value
     660    ///\warning If node \c v in unreachable from the root(s) the return value
    226661    ///of this funcion is undefined.
    227     int dist(Node v) const { return (*distance)[v]; }
    228 
    229     ///Returns the 'previous edge' of the %BFS path tree.
    230 
    231     ///For a node \c v it returns the 'previous edge' of the %BFS tree,
    232     ///i.e. it returns the last edge of a shortest path from the root to \c
     662    int dist(Node v) const { return (*_dist)[v]; }
     663
     664    ///Returns the 'previous edge' of the shortest path tree.
     665
     666    ///For a node \c v it returns the 'previous edge'
     667    ///of the shortest path tree,
     668    ///i.e. it returns the last edge of a shortest path from the root(s) to \c
    233669    ///v. It is \ref INVALID
    234     ///if \c v is unreachable from the root or if \c v=s. The
    235     ///%BFS tree used here is equal to the %BFS tree used in
    236     ///\ref predNode(Node v).  \pre \ref run() must be called before using
     670    ///if \c v is unreachable from the root(s) or \c v is a root. The
     671    ///shortest path tree used here is equal to the shortest path tree used in
     672    ///\ref predNode(Node v).
     673    ///\pre Either \ref run() or \ref start() must be called before using
    237674    ///this function.
    238     Edge pred(Node v) const { return (*predecessor)[v]; }
    239 
    240     ///Returns the 'previous node' of the %BFS tree.
    241 
    242     ///For a node \c v it returns the 'previous node' on the %BFS tree,
     675    ///\todo predEdge could be a better name.
     676    Edge pred(Node v) const { return (*_pred)[v];}
     677
     678    ///Returns the 'previous node' of the shortest path tree.
     679
     680    ///For a node \c v it returns the 'previous node'
     681    ///of the shortest path tree,
    243682    ///i.e. it returns the last but one node from a shortest path from the
    244     ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
    245     ///\c v=s. The shortest path tree used here is equal to the %BFS
    246     ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
     683    ///root(a) to \c /v.
     684    ///It is INVALID if \c v is unreachable from the root(s) or
     685    ///if \c v itself a root.
     686    ///The shortest path tree used here is equal to the shortest path
     687    ///tree used in \ref pred(Node v).
     688    ///\pre Either \ref run() or \ref start() must be called before
    247689    ///using this function.
    248     Node predNode(Node v) const { return (*pred_node)[v]; }
     690    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
     691                                  G->source((*_pred)[v]); }
    249692   
    250693    ///Returns a reference to the NodeMap of distances.
    251    
    252     ///Returns a reference to the NodeMap of distances. \pre \ref run() must
     694
     695    ///Returns a reference to the NodeMap of distances.
     696    ///\pre Either \ref run() or \ref init() must
    253697    ///be called before using this function.
    254     const DistMap &distMap() const { return *distance;}
    255  
    256     ///Returns a reference to the %BFS tree map.
     698    const DistMap &distMap() const { return *_dist;}
     699 
     700    ///Returns a reference to the shortest path tree map.
    257701
    258702    ///Returns a reference to the NodeMap of the edges of the
    259     ///%BFS tree.
    260     ///\pre \ref run() must be called before using this function.
    261     const PredMap &predMap() const { return *predecessor;}
    262  
    263     ///Returns a reference to the map of last but one nodes of shortest paths.
    264 
    265     ///Returns a reference to the NodeMap of the last but one nodes on the
    266     ///%BFS tree.
    267     ///\pre \ref run() must be called before using this function.
    268     const PredNodeMap &predNodeMap() const { return *pred_node;}
     703    ///shortest path tree.
     704    ///\pre Either \ref run() or \ref init()
     705    ///must be called before using this function.
     706    const PredMap &predMap() const { return *_pred;}
     707 
     708//     ///Returns a reference to the map of nodes of shortest paths.
     709
     710//     ///Returns a reference to the NodeMap of the last but one nodes of the
     711//     ///shortest path tree.
     712//     ///\pre \ref run() must be called before using this function.
     713//     const PredNodeMap &predNodeMap() const { return *_predNode;}
    269714
    270715    ///Checks if a node is reachable from the root.
    271716
    272717    ///Returns \c true if \c v is reachable from the root.
    273     ///\note The root node is reported to be reached!
    274     ///
    275     ///\pre \ref run() must be called before using this function.
    276     ///
    277     bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
    278    
     718    ///\warning The source nodes are inditated as unreached.
     719    ///\pre Either \ref run() or \ref start()
     720    ///must be called before using this function.
     721    ///
     722    bool reached(Node v) { return (*_reached)[v]; }
     723   
     724    ///@}
     725  };
     726
     727  ///Default traits class of Bfs function.
     728
     729  ///Default traits class of Bfs function.
     730  ///\param GR Graph type.
     731  template<class GR>
     732  struct BfsWizardDefaultTraits
     733  {
     734    ///The graph type the algorithm runs on.
     735    typedef GR Graph;
     736    ///\brief The type of the map that stores the last
     737    ///edges of the shortest paths.
     738    ///
     739    ///The type of the map that stores the last
     740    ///edges of the shortest paths.
     741    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     742    ///
     743    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
     744    ///Instantiates a PredMap.
     745 
     746    ///This function instantiates a \ref PredMap.
     747    ///\param G is the graph, to which we would like to define the PredMap.
     748    ///\todo The graph alone may be insufficient to initialize
     749    static PredMap *createPredMap(const GR &G)
     750    {
     751      return new PredMap();
     752    }
     753//     ///\brief The type of the map that stores the last but one
     754//     ///nodes of the shortest paths.
     755//     ///
     756//     ///The type of the map that stores the last but one
     757//     ///nodes of the shortest paths.
     758//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     759//     ///
     760//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
     761//     ///Instantiates a PredNodeMap.
     762   
     763//     ///This function instantiates a \ref PredNodeMap.
     764//     ///\param G is the graph, to which
     765//     ///we would like to define the \ref PredNodeMap
     766//     static PredNodeMap *createPredNodeMap(const GR &G)
     767//     {
     768//       return new PredNodeMap();
     769//     }
     770
     771    ///The type of the map that indicates which nodes are processed.
     772 
     773    ///The type of the map that indicates which nodes are processed.
     774    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     775    ///\todo named parameter to set this type, function to read and write.
     776    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
     777    ///Instantiates a ProcessedMap.
     778 
     779    ///This function instantiates a \ref ProcessedMap.
     780    ///\param G is the graph, to which
     781    ///we would like to define the \ref ProcessedMap
     782    static ProcessedMap *createProcessedMap(const GR &G)
     783    {
     784      return new ProcessedMap();
     785    }
     786    ///The type of the map that indicates which nodes are reached.
     787 
     788    ///The type of the map that indicates which nodes are reached.
     789    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     790    ///\todo named parameter to set this type, function to read and write.
     791    typedef typename Graph::template NodeMap<bool> ReachedMap;
     792    ///Instantiates a ReachedMap.
     793 
     794    ///This function instantiates a \ref ReachedMap.
     795    ///\param G is the graph, to which
     796    ///we would like to define the \ref ReachedMap.
     797    static ReachedMap *createReachedMap(const GR &G)
     798    {
     799      return new ReachedMap(G);
     800    }
     801    ///The type of the map that stores the dists of the nodes.
     802 
     803    ///The type of the map that stores the dists of the nodes.
     804    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     805    ///
     806    typedef NullMap<typename Graph::Node,int> DistMap;
     807    ///Instantiates a DistMap.
     808 
     809    ///This function instantiates a \ref DistMap.
     810    ///\param G is the graph, to which we would like to define the \ref DistMap
     811    static DistMap *createDistMap(const GR &G)
     812    {
     813      return new DistMap();
     814    }
    279815  };
    280816 
    281 /// @}
     817  /// Default traits used by \ref BfsWizard
     818
     819  /// To make it easier to use Bfs algorithm
     820  ///we have created a wizard class.
     821  /// This \ref BfsWizard class needs default traits,
     822  ///as well as the \ref Bfs class.
     823  /// The \ref BfsWizardBase is a class to be the default traits of the
     824  /// \ref BfsWizard class.
     825  template<class GR>
     826  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     827  {
     828
     829    typedef BfsWizardDefaultTraits<GR> Base;
     830  protected:
     831    /// Type of the nodes in the graph.
     832    typedef typename Base::Graph::Node Node;
     833
     834    /// Pointer to the underlying graph.
     835    void *_g;
     836    ///Pointer to the map of reached nodes.
     837    void *_reached;
     838    ///Pointer to the map of processed nodes.
     839    void *_processed;
     840    ///Pointer to the map of predecessors edges.
     841    void *_pred;
     842//     ///Pointer to the map of predecessors nodes.
     843//     void *_predNode;
     844    ///Pointer to the map of distances.
     845    void *_dist;
     846    ///Pointer to the source node.
     847    Node _source;
     848   
     849    public:
     850    /// Constructor.
     851   
     852    /// This constructor does not require parameters, therefore it initiates
     853    /// all of the attributes to default values (0, INVALID).
     854    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     855//                         _predNode(0),
     856                           _dist(0), _source(INVALID) {}
     857
     858    /// Constructor.
     859   
     860    /// This constructor requires some parameters,
     861    /// listed in the parameters list.
     862    /// Others are initiated to 0.
     863    /// \param g is the initial value of  \ref _g
     864    /// \param s is the initial value of  \ref _source
     865    BfsWizardBase(const GR &g, Node s=INVALID) :
     866      _g((void *)&g), _reached(0), _processed(0), _pred(0),
     867//       _predNode(0),
     868      _dist(0), _source(s) {}
     869
     870  };
    282871 
     872  /// A class to make the usage of Bfs algorithm easier
     873
     874  /// This class is created to make it easier to use Bfs algorithm.
     875  /// It uses the functions and features of the plain \ref Bfs,
     876  /// but it is much simpler to use it.
     877  ///
     878  /// Simplicity means that the way to change the types defined
     879  /// in the traits class is based on functions that returns the new class
     880  /// and not on templatable built-in classes.
     881  /// When using the plain \ref Bfs
     882  /// the new class with the modified type comes from
     883  /// the original class by using the ::
     884  /// operator. In the case of \ref BfsWizard only
     885  /// a function have to be called and it will
     886  /// return the needed class.
     887  ///
     888  /// It does not have own \ref run method. When its \ref run method is called
     889  /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
     890  /// method of it.
     891  template<class TR>
     892  class BfsWizard : public TR
     893  {
     894    typedef TR Base;
     895
     896    ///The type of the underlying graph.
     897    typedef typename TR::Graph Graph;
     898    //\e
     899    typedef typename Graph::Node Node;
     900    //\e
     901    typedef typename Graph::NodeIt NodeIt;
     902    //\e
     903    typedef typename Graph::Edge Edge;
     904    //\e
     905    typedef typename Graph::OutEdgeIt OutEdgeIt;
     906   
     907    ///\brief The type of the map that stores
     908    ///the reached nodes
     909    typedef typename TR::ReachedMap ReachedMap;
     910    ///\brief The type of the map that stores
     911    ///the processed nodes
     912    typedef typename TR::ProcessedMap ProcessedMap;
     913    ///\brief The type of the map that stores the last
     914    ///edges of the shortest paths.
     915    typedef typename TR::PredMap PredMap;
     916//     ///\brief The type of the map that stores the last but one
     917//     ///nodes of the shortest paths.
     918//     typedef typename TR::PredNodeMap PredNodeMap;
     919    ///The type of the map that stores the dists of the nodes.
     920    typedef typename TR::DistMap DistMap;
     921
     922public:
     923    /// Constructor.
     924    BfsWizard() : TR() {}
     925
     926    /// Constructor that requires parameters.
     927
     928    /// Constructor that requires parameters.
     929    /// These parameters will be the default values for the traits class.
     930    BfsWizard(const Graph &g, Node s=INVALID) :
     931      TR(g,s) {}
     932
     933    ///Copy constructor
     934    BfsWizard(const TR &b) : TR(b) {}
     935
     936    ~BfsWizard() {}
     937
     938    ///Runs Bfs algorithm from a given node.
     939   
     940    ///Runs Bfs algorithm from a given node.
     941    ///The node can be given by the \ref source function.
     942    void run()
     943    {
     944      if(Base::_source==INVALID) throw UninitializedParameter();
     945      Bfs<Graph,TR> alg(*(Graph*)Base::_g);
     946      if(Base::_reached)
     947        alg.reachedMap(*(ReachedMap*)Base::_reached);
     948      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
     949      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
     950//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
     951      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
     952      alg.run(Base::_source);
     953    }
     954
     955    ///Runs Bfs algorithm from the given node.
     956
     957    ///Runs Bfs algorithm from the given node.
     958    ///\param s is the given source.
     959    void run(Node s)
     960    {
     961      Base::_source=s;
     962      run();
     963    }
     964
     965    template<class T>
     966    struct DefPredMapBase : public Base {
     967      typedef T PredMap;
     968      static PredMap *createPredMap(const Graph &G) { return 0; };
     969      DefPredMapBase(const Base &b) : Base(b) {}
     970    };
     971   
     972    ///\brief \ref named-templ-param "Named parameter"
     973    ///function for setting PredMap
     974    ///
     975    /// \ref named-templ-param "Named parameter"
     976    ///function for setting PredMap
     977    ///
     978    template<class T>
     979    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
     980    {
     981      Base::_pred=(void *)&t;
     982      return BfsWizard<DefPredMapBase<T> >(*this);
     983    }
     984   
     985 
     986    template<class T>
     987    struct DefReachedMapBase : public Base {
     988      typedef T ReachedMap;
     989      static ReachedMap *createReachedMap(const Graph &G) { return 0; };
     990      DefReachedMapBase(const Base &b) : Base(b) {}
     991    };
     992   
     993    ///\brief \ref named-templ-param "Named parameter"
     994    ///function for setting ReachedMap
     995    ///
     996    /// \ref named-templ-param "Named parameter"
     997    ///function for setting ReachedMap
     998    ///
     999    template<class T>
     1000    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
     1001    {
     1002      Base::_pred=(void *)&t;
     1003      return BfsWizard<DefReachedMapBase<T> >(*this);
     1004    }
     1005   
     1006
     1007    template<class T>
     1008    struct DefProcessedMapBase : public Base {
     1009      typedef T ProcessedMap;
     1010      static ProcessedMap *createProcessedMap(const Graph &G) { return 0; };
     1011      DefProcessedMapBase(const Base &b) : Base(b) {}
     1012    };
     1013   
     1014    ///\brief \ref named-templ-param "Named parameter"
     1015    ///function for setting ProcessedMap
     1016    ///
     1017    /// \ref named-templ-param "Named parameter"
     1018    ///function for setting ProcessedMap
     1019    ///
     1020    template<class T>
     1021    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     1022    {
     1023      Base::_pred=(void *)&t;
     1024      return BfsWizard<DefProcessedMapBase<T> >(*this);
     1025    }
     1026   
     1027
     1028//     template<class T>
     1029//     struct DefPredNodeMapBase : public Base {
     1030//       typedef T PredNodeMap;
     1031//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
     1032//       DefPredNodeMapBase(const Base &b) : Base(b) {}
     1033//     };
     1034   
     1035//     ///\brief \ref named-templ-param "Named parameter"
     1036//     ///function for setting PredNodeMap type
     1037//     ///
     1038//     /// \ref named-templ-param "Named parameter"
     1039//     ///function for setting PredNodeMap type
     1040//     ///
     1041//     template<class T>
     1042//     BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
     1043//     {
     1044//       Base::_predNode=(void *)&t;
     1045//       return BfsWizard<DefPredNodeMapBase<T> >(*this);
     1046//     }
     1047   
     1048    template<class T>
     1049    struct DefDistMapBase : public Base {
     1050      typedef T DistMap;
     1051      static DistMap *createDistMap(const Graph &G) { return 0; };
     1052      DefDistMapBase(const Base &b) : Base(b) {}
     1053    };
     1054   
     1055    ///\brief \ref named-templ-param "Named parameter"
     1056    ///function for setting DistMap type
     1057    ///
     1058    /// \ref named-templ-param "Named parameter"
     1059    ///function for setting DistMap type
     1060    ///
     1061    template<class T>
     1062    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
     1063    {
     1064      Base::_dist=(void *)&t;
     1065      return BfsWizard<DefDistMapBase<T> >(*this);
     1066    }
     1067   
     1068    /// Sets the source node, from which the Bfs algorithm runs.
     1069
     1070    /// Sets the source node, from which the Bfs algorithm runs.
     1071    /// \param s is the source node.
     1072    BfsWizard<TR> &source(Node s)
     1073    {
     1074      Base::_source=s;
     1075      return *this;
     1076    }
     1077   
     1078  };
     1079 
     1080  ///Function type interface for Bfs algorithm.
     1081
     1082  /// \ingroup flowalgs
     1083  ///Function type interface for Bfs algorithm.
     1084  ///
     1085  ///This function also has several
     1086  ///\ref named-templ-func-param "named parameters",
     1087  ///they are declared as the members of class \ref BfsWizard.
     1088  ///The following
     1089  ///example shows how to use these parameters.
     1090  ///\code
     1091  ///  bfs(g,source).predMap(preds).run();
     1092  ///\endcode
     1093  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1094  ///to the end of the parameter list.
     1095  ///\sa BfsWizard
     1096  ///\sa Bfs
     1097  template<class GR>
     1098  BfsWizard<BfsWizardBase<GR> >
     1099  bfs(const GR &g,typename GR::Node s=INVALID)
     1100  {
     1101    return BfsWizard<BfsWizardBase<GR> >(g,s);
     1102  }
     1103
    2831104} //END OF NAMESPACE LEMON
    2841105
    2851106#endif
    2861107
    287 
Note: See TracChangeset for help on using the changeset viewer.