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