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