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