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