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