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