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