lemon/dfs.h
author ladanyi
Fri, 29 Jul 2005 12:01:37 +0000
changeset 1606 dc4ea2010dee
parent 1536 308150155bb5
child 1631 e15162d8eca1
permissions -rw-r--r--
added support for saving files
alpar@906
     1
/* -*- C++ -*-
ladanyi@1435
     2
 * lemon/dfs.h - Part of LEMON, a generic C++ optimization library
alpar@906
     3
 *
alpar@1164
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359
     5
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906
     6
 *
alpar@906
     7
 * Permission to use, modify and distribute this software is granted
alpar@906
     8
 * provided that this copyright notice appears in all copies. For
alpar@906
     9
 * precise terms see the accompanying LICENSE file.
alpar@906
    10
 *
alpar@906
    11
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    12
 * express or implied, and with no claim as to its suitability for any
alpar@906
    13
 * purpose.
alpar@906
    14
 *
alpar@906
    15
 */
alpar@906
    16
alpar@921
    17
#ifndef LEMON_DFS_H
alpar@921
    18
#define LEMON_DFS_H
alpar@780
    19
alpar@780
    20
///\ingroup flowalgs
alpar@780
    21
///\file
alpar@1218
    22
///\brief Dfs algorithm.
alpar@780
    23
alpar@1218
    24
#include <lemon/list_graph.h>
klao@946
    25
#include <lemon/graph_utils.h>
alpar@921
    26
#include <lemon/invalid.h>
alpar@1218
    27
#include <lemon/error.h>
alpar@1218
    28
#include <lemon/maps.h>
alpar@780
    29
alpar@921
    30
namespace lemon {
alpar@780
    31
alpar@780
    32
alpar@1218
    33
  
alpar@1218
    34
  ///Default traits class of Dfs class.
alpar@1218
    35
alpar@1218
    36
  ///Default traits class of Dfs class.
alpar@1218
    37
  ///\param GR Graph type.
alpar@1218
    38
  template<class GR>
alpar@1218
    39
  struct DfsDefaultTraits
alpar@1218
    40
  {
alpar@1218
    41
    ///The graph type the algorithm runs on. 
alpar@1218
    42
    typedef GR Graph;
alpar@1218
    43
    ///\brief The type of the map that stores the last
alpar@1218
    44
    ///edges of the %DFS paths.
alpar@1218
    45
    /// 
alpar@1218
    46
    ///The type of the map that stores the last
alpar@1218
    47
    ///edges of the %DFS paths.
alpar@1218
    48
    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@1218
    49
    ///
alpar@1218
    50
    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
alpar@1218
    51
    ///Instantiates a PredMap.
alpar@1218
    52
 
alpar@1218
    53
    ///This function instantiates a \ref PredMap. 
alpar@1218
    54
    ///\param G is the graph, to which we would like to define the PredMap.
alpar@1218
    55
    ///\todo The graph alone may be insufficient to initialize
alpar@1218
    56
    static PredMap *createPredMap(const GR &G) 
alpar@1218
    57
    {
alpar@1218
    58
      return new PredMap(G);
alpar@1218
    59
    }
alpar@1218
    60
//     ///\brief The type of the map that stores the last but one
alpar@1218
    61
//     ///nodes of the %DFS paths.
alpar@1218
    62
//     ///
alpar@1218
    63
//     ///The type of the map that stores the last but one
alpar@1218
    64
//     ///nodes of the %DFS paths.
alpar@1218
    65
//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@1218
    66
//     ///
alpar@1218
    67
//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
alpar@1218
    68
//     ///Instantiates a PredNodeMap.
alpar@1218
    69
    
alpar@1218
    70
//     ///This function instantiates a \ref PredNodeMap. 
alpar@1218
    71
//     ///\param G is the graph, to which
alpar@1218
    72
//     ///we would like to define the \ref PredNodeMap
alpar@1218
    73
//     static PredNodeMap *createPredNodeMap(const GR &G)
alpar@1218
    74
//     {
alpar@1218
    75
//       return new PredNodeMap();
alpar@1218
    76
//     }
alpar@1218
    77
alpar@1218
    78
    ///The type of the map that indicates which nodes are processed.
alpar@1218
    79
 
alpar@1218
    80
    ///The type of the map that indicates which nodes are processed.
alpar@1218
    81
    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@1218
    82
    ///\todo named parameter to set this type, function to read and write.
alpar@1218
    83
    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
alpar@1218
    84
    ///Instantiates a ProcessedMap.
alpar@1218
    85
 
alpar@1218
    86
    ///This function instantiates a \ref ProcessedMap. 
alpar@1536
    87
    ///\param g is the graph, to which
alpar@1218
    88
    ///we would like to define the \ref ProcessedMap
alpar@1536
    89
#ifdef DOXYGEN
alpar@1536
    90
    static ProcessedMap *createProcessedMap(const GR &g)
alpar@1536
    91
#else
alpar@1367
    92
    static ProcessedMap *createProcessedMap(const GR &)
alpar@1536
    93
#endif
alpar@1218
    94
    {
alpar@1218
    95
      return new ProcessedMap();
alpar@1218
    96
    }
alpar@1218
    97
    ///The type of the map that indicates which nodes are reached.
alpar@1218
    98
 
alpar@1218
    99
    ///The type of the map that indicates which nodes are reached.
alpar@1218
   100
    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@1218
   101
    ///\todo named parameter to set this type, function to read and write.
alpar@1218
   102
    typedef typename Graph::template NodeMap<bool> ReachedMap;
alpar@1218
   103
    ///Instantiates a ReachedMap.
alpar@1218
   104
 
alpar@1218
   105
    ///This function instantiates a \ref ReachedMap. 
alpar@1218
   106
    ///\param G is the graph, to which
alpar@1218
   107
    ///we would like to define the \ref ReachedMap.
alpar@1218
   108
    static ReachedMap *createReachedMap(const GR &G)
alpar@1218
   109
    {
alpar@1218
   110
      return new ReachedMap(G);
alpar@1218
   111
    }
alpar@1218
   112
    ///The type of the map that stores the dists of the nodes.
alpar@1218
   113
 
alpar@1218
   114
    ///The type of the map that stores the dists of the nodes.
alpar@1218
   115
    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@1218
   116
    ///
alpar@1218
   117
    typedef typename Graph::template NodeMap<int> DistMap;
alpar@1218
   118
    ///Instantiates a DistMap.
alpar@1218
   119
 
alpar@1218
   120
    ///This function instantiates a \ref DistMap. 
alpar@1218
   121
    ///\param G is the graph, to which we would like to define the \ref DistMap
alpar@1218
   122
    static DistMap *createDistMap(const GR &G)
alpar@1218
   123
    {
alpar@1218
   124
      return new DistMap(G);
alpar@1218
   125
    }
alpar@1218
   126
  };
alpar@1218
   127
  
alpar@781
   128
  ///%DFS algorithm class.
alpar@1218
   129
  
alpar@1218
   130
  ///\ingroup flowalgs
alpar@1218
   131
  ///This class provides an efficient implementation of the %DFS algorithm.
alpar@780
   132
  ///
alpar@1218
   133
  ///\param GR The graph type the algorithm runs on. The default value is
alpar@1218
   134
  ///\ref ListGraph. The value of GR is not used directly by Dfs, it
alpar@1218
   135
  ///is only passed to \ref DfsDefaultTraits.
alpar@1218
   136
  ///\param TR Traits class to set various data types used by the algorithm.
alpar@1218
   137
  ///The default traits class is
alpar@1218
   138
  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
alpar@1218
   139
  ///See \ref DfsDefaultTraits for the documentation of
alpar@1218
   140
  ///a Dfs traits class.
alpar@780
   141
  ///
alpar@1218
   142
  ///\author Jacint Szabo and Alpar Juttner
alpar@1218
   143
  ///\todo A compare object would be nice.
alpar@780
   144
alpar@780
   145
#ifdef DOXYGEN
alpar@1218
   146
  template <typename GR,
alpar@1218
   147
	    typename TR>
alpar@780
   148
#else
alpar@1218
   149
  template <typename GR=ListGraph,
alpar@1218
   150
	    typename TR=DfsDefaultTraits<GR> >
alpar@780
   151
#endif
alpar@1218
   152
  class Dfs {
alpar@780
   153
  public:
alpar@1218
   154
    /**
alpar@1218
   155
     * \brief \ref Exception for uninitialized parameters.
alpar@1218
   156
     *
alpar@1218
   157
     * This error represents problems in the initialization
alpar@1218
   158
     * of the parameters of the algorithms.
alpar@1218
   159
     */
alpar@1218
   160
    class UninitializedParameter : public lemon::UninitializedParameter {
alpar@1218
   161
    public:
alpar@1218
   162
      virtual const char* exceptionName() const {
alpar@1218
   163
	return "lemon::Dfs::UninitializedParameter";
alpar@1218
   164
      }
alpar@1218
   165
    };
alpar@1218
   166
alpar@1218
   167
    typedef TR Traits;
alpar@780
   168
    ///The type of the underlying graph.
alpar@1218
   169
    typedef typename TR::Graph Graph;
alpar@911
   170
    ///\e
alpar@780
   171
    typedef typename Graph::Node Node;
alpar@911
   172
    ///\e
alpar@780
   173
    typedef typename Graph::NodeIt NodeIt;
alpar@911
   174
    ///\e
alpar@780
   175
    typedef typename Graph::Edge Edge;
alpar@911
   176
    ///\e
alpar@780
   177
    typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@780
   178
    
alpar@780
   179
    ///\brief The type of the map that stores the last
alpar@1218
   180
    ///edges of the %DFS paths.
alpar@1218
   181
    typedef typename TR::PredMap PredMap;
alpar@1218
   182
//     ///\brief The type of the map that stores the last but one
alpar@1218
   183
//     ///nodes of the %DFS paths.
alpar@1218
   184
//     typedef typename TR::PredNodeMap PredNodeMap;
alpar@1218
   185
    ///The type of the map indicating which nodes are reached.
alpar@1218
   186
    typedef typename TR::ReachedMap ReachedMap;
alpar@1218
   187
    ///The type of the map indicating which nodes are processed.
alpar@1218
   188
    typedef typename TR::ProcessedMap ProcessedMap;
alpar@1218
   189
    ///The type of the map that stores the dists of the nodes.
alpar@1218
   190
    typedef typename TR::DistMap DistMap;
alpar@780
   191
  private:
alpar@802
   192
    /// Pointer to the underlying graph.
alpar@780
   193
    const Graph *G;
alpar@802
   194
    ///Pointer to the map of predecessors edges.
alpar@1218
   195
    PredMap *_pred;
alpar@1218
   196
    ///Indicates if \ref _pred is locally allocated (\c true) or not.
alpar@1218
   197
    bool local_pred;
alpar@1218
   198
//     ///Pointer to the map of predecessors nodes.
alpar@1218
   199
//     PredNodeMap *_predNode;
alpar@1218
   200
//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
alpar@1218
   201
//     bool local_predNode;
alpar@802
   202
    ///Pointer to the map of distances.
alpar@1218
   203
    DistMap *_dist;
alpar@1218
   204
    ///Indicates if \ref _dist is locally allocated (\c true) or not.
alpar@1218
   205
    bool local_dist;
alpar@1218
   206
    ///Pointer to the map of reached status of the nodes.
alpar@1218
   207
    ReachedMap *_reached;
alpar@1218
   208
    ///Indicates if \ref _reached is locally allocated (\c true) or not.
alpar@1218
   209
    bool local_reached;
alpar@1218
   210
    ///Pointer to the map of processed status of the nodes.
alpar@1218
   211
    ProcessedMap *_processed;
alpar@1218
   212
    ///Indicates if \ref _processed is locally allocated (\c true) or not.
alpar@1218
   213
    bool local_processed;
alpar@780
   214
alpar@1218
   215
    std::vector<typename Graph::OutEdgeIt> _stack;
alpar@1218
   216
    int _stack_head;
alpar@1218
   217
//     ///The source node of the last execution.
alpar@1218
   218
//     Node source;
alpar@780
   219
alpar@1218
   220
    ///Creates the maps if necessary.
alpar@1218
   221
    
alpar@1218
   222
    ///\todo Error if \c G are \c NULL.
alpar@1218
   223
    ///\todo Better memory allocation (instead of new).
alpar@1218
   224
    void create_maps() 
alpar@780
   225
    {
alpar@1218
   226
      if(!_pred) {
alpar@1218
   227
	local_pred = true;
alpar@1218
   228
	_pred = Traits::createPredMap(*G);
alpar@780
   229
      }
alpar@1218
   230
//       if(!_predNode) {
alpar@1218
   231
// 	local_predNode = true;
alpar@1218
   232
// 	_predNode = Traits::createPredNodeMap(*G);
alpar@1218
   233
//       }
alpar@1218
   234
      if(!_dist) {
alpar@1218
   235
	local_dist = true;
alpar@1218
   236
	_dist = Traits::createDistMap(*G);
alpar@780
   237
      }
alpar@1218
   238
      if(!_reached) {
alpar@1218
   239
	local_reached = true;
alpar@1218
   240
	_reached = Traits::createReachedMap(*G);
alpar@1218
   241
      }
alpar@1218
   242
      if(!_processed) {
alpar@1218
   243
	local_processed = true;
alpar@1218
   244
	_processed = Traits::createProcessedMap(*G);
alpar@780
   245
      }
alpar@780
   246
    }
alpar@780
   247
    
alpar@1218
   248
  public :
alpar@1218
   249
 
alpar@1218
   250
    ///\name Named template parameters
alpar@1218
   251
alpar@1218
   252
    ///@{
alpar@1218
   253
alpar@1218
   254
    template <class T>
alpar@1218
   255
    struct DefPredMapTraits : public Traits {
alpar@1218
   256
      typedef T PredMap;
alpar@1218
   257
      static PredMap *createPredMap(const Graph &G) 
alpar@1218
   258
      {
alpar@1218
   259
	throw UninitializedParameter();
alpar@1218
   260
      }
alpar@1218
   261
    };
alpar@1218
   262
    ///\ref named-templ-param "Named parameter" for setting PredMap type
alpar@1218
   263
alpar@1218
   264
    ///\ref named-templ-param "Named parameter" for setting PredMap type
alpar@1218
   265
    ///
alpar@1218
   266
    template <class T>
alpar@1218
   267
    class DefPredMap : public Dfs< Graph,
alpar@1218
   268
					DefPredMapTraits<T> > { };
alpar@1218
   269
    
alpar@1218
   270
//     template <class T>
alpar@1218
   271
//     struct DefPredNodeMapTraits : public Traits {
alpar@1218
   272
//       typedef T PredNodeMap;
alpar@1218
   273
//       static PredNodeMap *createPredNodeMap(const Graph &G) 
alpar@1218
   274
//       {
alpar@1218
   275
// 	throw UninitializedParameter();
alpar@1218
   276
//       }
alpar@1218
   277
//     };
alpar@1218
   278
//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
alpar@1218
   279
alpar@1218
   280
//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
alpar@1218
   281
//     ///
alpar@1218
   282
//     template <class T>
alpar@1218
   283
//     class DefPredNodeMap : public Dfs< Graph,
alpar@1218
   284
// 					    LengthMap,
alpar@1218
   285
// 					    DefPredNodeMapTraits<T> > { };
alpar@1218
   286
    
alpar@1218
   287
    template <class T>
alpar@1218
   288
    struct DefDistMapTraits : public Traits {
alpar@1218
   289
      typedef T DistMap;
alpar@1218
   290
      static DistMap *createDistMap(const Graph &G) 
alpar@1218
   291
      {
alpar@1218
   292
	throw UninitializedParameter();
alpar@1218
   293
      }
alpar@1218
   294
    };
alpar@1218
   295
    ///\ref named-templ-param "Named parameter" for setting DistMap type
alpar@1218
   296
alpar@1218
   297
    ///\ref named-templ-param "Named parameter" for setting DistMap type
alpar@1218
   298
    ///
alpar@1218
   299
    template <class T>
alpar@1218
   300
    class DefDistMap : public Dfs< Graph,
alpar@1218
   301
				   DefDistMapTraits<T> > { };
alpar@1218
   302
    
alpar@1218
   303
    template <class T>
alpar@1218
   304
    struct DefReachedMapTraits : public Traits {
alpar@1218
   305
      typedef T ReachedMap;
alpar@1218
   306
      static ReachedMap *createReachedMap(const Graph &G) 
alpar@1218
   307
      {
alpar@1218
   308
	throw UninitializedParameter();
alpar@1218
   309
      }
alpar@1218
   310
    };
alpar@1218
   311
    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
alpar@1218
   312
alpar@1218
   313
    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
alpar@1218
   314
    ///
alpar@1218
   315
    template <class T>
alpar@1218
   316
    class DefReachedMap : public Dfs< Graph,
alpar@1218
   317
				      DefReachedMapTraits<T> > { };
alpar@1218
   318
    
alpar@1218
   319
    struct DefGraphReachedMapTraits : public Traits {
alpar@1218
   320
      typedef typename Graph::template NodeMap<bool> ReachedMap;
alpar@1218
   321
      static ReachedMap *createReachedMap(const Graph &G) 
alpar@1218
   322
      {
alpar@1218
   323
	return new ReachedMap(G);
alpar@1218
   324
      }
alpar@1218
   325
    };
alpar@1218
   326
    template <class T>
alpar@1218
   327
    struct DefProcessedMapTraits : public Traits {
alpar@1218
   328
      typedef T ProcessedMap;
alpar@1218
   329
      static ProcessedMap *createProcessedMap(const Graph &G) 
alpar@1218
   330
      {
alpar@1218
   331
	throw UninitializedParameter();
alpar@1218
   332
      }
alpar@1218
   333
    };
alpar@1218
   334
    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
alpar@1218
   335
alpar@1218
   336
    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
alpar@1218
   337
    ///
alpar@1218
   338
    template <class T>
alpar@1218
   339
    class DefProcessedMap : public Dfs< Graph,
alpar@1218
   340
					DefProcessedMapTraits<T> > { };
alpar@1218
   341
    
alpar@1218
   342
    struct DefGraphProcessedMapTraits : public Traits {
alpar@1218
   343
      typedef typename Graph::template NodeMap<bool> ProcessedMap;
alpar@1218
   344
      static ProcessedMap *createProcessedMap(const Graph &G) 
alpar@1218
   345
      {
alpar@1218
   346
	return new ProcessedMap(G);
alpar@1218
   347
      }
alpar@1218
   348
    };
alpar@1218
   349
    ///\brief \ref named-templ-param "Named parameter"
alpar@1218
   350
    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
alpar@1218
   351
    ///
alpar@1218
   352
    ///\ref named-templ-param "Named parameter"
alpar@1218
   353
    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
alpar@1218
   354
    ///If you don't set it explicitely, it will be automatically allocated.
alpar@1218
   355
    template <class T>
alpar@1218
   356
    class DefProcessedMapToBeDefaultMap :
alpar@1218
   357
      public Dfs< Graph,
alpar@1218
   358
		  DefGraphProcessedMapTraits> { };
alpar@1218
   359
    
alpar@1218
   360
    ///@}
alpar@1218
   361
alpar@1218
   362
  public:      
alpar@1218
   363
    
alpar@802
   364
    ///Constructor.
alpar@802
   365
    
alpar@802
   366
    ///\param _G the graph the algorithm will run on.
alpar@911
   367
    ///
alpar@780
   368
    Dfs(const Graph& _G) :
alpar@780
   369
      G(&_G),
alpar@1218
   370
      _pred(NULL), local_pred(false),
alpar@1218
   371
//       _predNode(NULL), local_predNode(false),
alpar@1218
   372
      _dist(NULL), local_dist(false),
alpar@1218
   373
      _reached(NULL), local_reached(false),
alpar@1218
   374
      _processed(NULL), local_processed(false)
alpar@780
   375
    { }
alpar@780
   376
    
alpar@802
   377
    ///Destructor.
alpar@780
   378
    ~Dfs() 
alpar@780
   379
    {
alpar@1218
   380
      if(local_pred) delete _pred;
alpar@1218
   381
//       if(local_predNode) delete _predNode;
alpar@1218
   382
      if(local_dist) delete _dist;
alpar@1218
   383
      if(local_reached) delete _reached;
alpar@1218
   384
      if(local_processed) delete _processed;
alpar@780
   385
    }
alpar@780
   386
alpar@780
   387
    ///Sets the map storing the predecessor edges.
alpar@780
   388
alpar@780
   389
    ///Sets the map storing the predecessor edges.
alpar@780
   390
    ///If you don't use this function before calling \ref run(),
alpar@780
   391
    ///it will allocate one. The destuctor deallocates this
alpar@780
   392
    ///automatically allocated map, of course.
alpar@780
   393
    ///\return <tt> (*this) </tt>
alpar@1218
   394
    Dfs &predMap(PredMap &m) 
alpar@780
   395
    {
alpar@1218
   396
      if(local_pred) {
alpar@1218
   397
	delete _pred;
alpar@1218
   398
	local_pred=false;
alpar@780
   399
      }
alpar@1218
   400
      _pred = &m;
alpar@780
   401
      return *this;
alpar@780
   402
    }
alpar@780
   403
alpar@1218
   404
//     ///Sets the map storing the predecessor nodes.
alpar@780
   405
alpar@1218
   406
//     ///Sets the map storing the predecessor nodes.
alpar@1218
   407
//     ///If you don't use this function before calling \ref run(),
alpar@1218
   408
//     ///it will allocate one. The destuctor deallocates this
alpar@1218
   409
//     ///automatically allocated map, of course.
alpar@1218
   410
//     ///\return <tt> (*this) </tt>
alpar@1218
   411
//     Dfs &predNodeMap(PredNodeMap &m) 
alpar@1218
   412
//     {
alpar@1218
   413
//       if(local_predNode) {
alpar@1218
   414
// 	delete _predNode;
alpar@1218
   415
// 	local_predNode=false;
alpar@1218
   416
//       }
alpar@1218
   417
//       _predNode = &m;
alpar@1218
   418
//       return *this;
alpar@1218
   419
//     }
alpar@780
   420
alpar@780
   421
    ///Sets the map storing the distances calculated by the algorithm.
alpar@780
   422
alpar@780
   423
    ///Sets the map storing the distances calculated by the algorithm.
alpar@780
   424
    ///If you don't use this function before calling \ref run(),
alpar@780
   425
    ///it will allocate one. The destuctor deallocates this
alpar@780
   426
    ///automatically allocated map, of course.
alpar@780
   427
    ///\return <tt> (*this) </tt>
alpar@1218
   428
    Dfs &distMap(DistMap &m) 
alpar@780
   429
    {
alpar@1218
   430
      if(local_dist) {
alpar@1218
   431
	delete _dist;
alpar@1218
   432
	local_dist=false;
alpar@780
   433
      }
alpar@1218
   434
      _dist = &m;
alpar@780
   435
      return *this;
alpar@780
   436
    }
alpar@780
   437
alpar@1220
   438
    ///Sets the map indicating if a node is reached.
alpar@1220
   439
alpar@1220
   440
    ///Sets the map indicating if a node is reached.
alpar@1220
   441
    ///If you don't use this function before calling \ref run(),
alpar@1220
   442
    ///it will allocate one. The destuctor deallocates this
alpar@1220
   443
    ///automatically allocated map, of course.
alpar@1220
   444
    ///\return <tt> (*this) </tt>
alpar@1220
   445
    Dfs &reachedMap(ReachedMap &m) 
alpar@1220
   446
    {
alpar@1220
   447
      if(local_reached) {
alpar@1220
   448
	delete _reached;
alpar@1220
   449
	local_reached=false;
alpar@1220
   450
      }
alpar@1220
   451
      _reached = &m;
alpar@1220
   452
      return *this;
alpar@1220
   453
    }
alpar@1220
   454
alpar@1220
   455
    ///Sets the map indicating if a node is processed.
alpar@1220
   456
alpar@1220
   457
    ///Sets the map indicating if a node is processed.
alpar@1220
   458
    ///If you don't use this function before calling \ref run(),
alpar@1220
   459
    ///it will allocate one. The destuctor deallocates this
alpar@1220
   460
    ///automatically allocated map, of course.
alpar@1220
   461
    ///\return <tt> (*this) </tt>
alpar@1220
   462
    Dfs &processedMap(ProcessedMap &m) 
alpar@1220
   463
    {
alpar@1220
   464
      if(local_processed) {
alpar@1220
   465
	delete _processed;
alpar@1220
   466
	local_processed=false;
alpar@1220
   467
      }
alpar@1220
   468
      _processed = &m;
alpar@1220
   469
      return *this;
alpar@1220
   470
    }
alpar@1220
   471
alpar@1218
   472
  public:
alpar@1218
   473
    ///\name Execution control
alpar@1218
   474
    ///The simplest way to execute the algorithm is to use
alpar@1218
   475
    ///one of the member functions called \c run(...).
alpar@1218
   476
    ///\n
alpar@1218
   477
    ///If you need more control on the execution,
alpar@1218
   478
    ///first you must call \ref init(), then you can add several source nodes
alpar@1218
   479
    ///with \ref addSource().
alpar@1218
   480
    ///Finally \ref start() will perform the actual path
alpar@1218
   481
    ///computation.
alpar@1218
   482
alpar@1218
   483
    ///@{
alpar@1218
   484
alpar@1218
   485
    ///Initializes the internal data structures.
alpar@1218
   486
alpar@1218
   487
    ///Initializes the internal data structures.
alpar@1218
   488
    ///
alpar@1218
   489
    void init()
alpar@1218
   490
    {
alpar@1218
   491
      create_maps();
alpar@1218
   492
      _stack.resize(countNodes(*G));
alpar@1218
   493
      _stack_head=-1;
alpar@780
   494
      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
alpar@1218
   495
	_pred->set(u,INVALID);
alpar@1218
   496
	// _predNode->set(u,INVALID);
alpar@1218
   497
	_reached->set(u,false);
alpar@1218
   498
	_processed->set(u,false);
alpar@780
   499
      }
alpar@780
   500
    }
alpar@780
   501
    
alpar@1218
   502
    ///Adds a new source node.
alpar@780
   503
alpar@1218
   504
    ///Adds a new source node to the set of nodes to be processed.
alpar@1218
   505
    ///
athos@1443
   506
    ///\bug dists are wrong (or at least strange) in case of multiple sources.
alpar@1218
   507
    void addSource(Node s)
alpar@1218
   508
    {
alpar@1218
   509
      if(!(*_reached)[s])
alpar@1218
   510
	{
alpar@1218
   511
	  _reached->set(s,true);
alpar@1218
   512
	  _pred->set(s,INVALID);
alpar@1218
   513
	  // _predNode->set(u,INVALID);
alpar@1218
   514
	  _stack[++_stack_head]=OutEdgeIt(*G,s);
alpar@1218
   515
	  _dist->set(s,_stack_head);
alpar@1218
   516
	}
alpar@1218
   517
    }
alpar@1218
   518
    
deba@1529
   519
    ///Processes the next edge.
alpar@1218
   520
deba@1529
   521
    ///Processes the next edge.
alpar@1218
   522
    ///
alpar@1516
   523
    ///\return The processed edge.
alpar@1516
   524
    ///
athos@1443
   525
    ///\pre The stack must not be empty!
alpar@1516
   526
    Edge processNextEdge()
alpar@1218
   527
    { 
alpar@1218
   528
      Node m;
alpar@1218
   529
      Edge e=_stack[_stack_head];
alpar@1218
   530
      if(!(*_reached)[m=G->target(e)]) {
alpar@1218
   531
	_pred->set(m,e);
alpar@1218
   532
	_reached->set(m,true);
alpar@1218
   533
	//	  _pred_node->set(m,G->source(e));
alpar@1233
   534
	++_stack_head;
alpar@1233
   535
	_stack[_stack_head] = OutEdgeIt(*G, m);
alpar@1218
   536
	_dist->set(m,_stack_head);
alpar@1218
   537
      }
alpar@1218
   538
      else {
alpar@1218
   539
	Node n;
alpar@1218
   540
	while(_stack_head>=0 &&
alpar@1218
   541
	      (n=G->source(_stack[_stack_head]),
alpar@1218
   542
	       ++_stack[_stack_head]==INVALID))
alpar@1218
   543
	  {
alpar@1218
   544
	    _processed->set(n,true);
alpar@1218
   545
	    --_stack_head;
alpar@1218
   546
	  }
alpar@1218
   547
      }
alpar@1516
   548
      return e;
alpar@1218
   549
    }
alpar@1218
   550
      
alpar@1218
   551
    ///\brief Returns \c false if there are nodes
alpar@1218
   552
    ///to be processed in the queue
alpar@1218
   553
    ///
alpar@1218
   554
    ///Returns \c false if there are nodes
alpar@1218
   555
    ///to be processed in the queue
alpar@1218
   556
    bool emptyQueue() { return _stack_head<0; }
alpar@1218
   557
    ///Returns the number of the nodes to be processed.
alpar@1218
   558
    
alpar@1218
   559
    ///Returns the number of the nodes to be processed in the queue.
alpar@1218
   560
    ///
alpar@1218
   561
    int queueSize() { return _stack_head+1; }
alpar@1218
   562
    
alpar@1218
   563
    ///Executes the algorithm.
alpar@1218
   564
alpar@1218
   565
    ///Executes the algorithm.
alpar@1218
   566
    ///
alpar@1218
   567
    ///\pre init() must be called and at least one node should be added
alpar@1218
   568
    ///with addSource() before using this function.
alpar@1218
   569
    ///
alpar@1218
   570
    ///This method runs the %DFS algorithm from the root node(s)
alpar@1218
   571
    ///in order to
alpar@1218
   572
    ///compute the
alpar@1218
   573
    ///%DFS path to each node. The algorithm computes
alpar@1218
   574
    ///- The %DFS tree.
athos@1443
   575
    ///- The distance of each node from the root(s) in the %DFS tree.
alpar@1218
   576
    ///
alpar@1218
   577
    void start()
alpar@1218
   578
    {
alpar@1218
   579
      while ( !emptyQueue() ) processNextEdge();
alpar@1218
   580
    }
alpar@1218
   581
    
alpar@1218
   582
    ///Executes the algorithm until \c dest is reached.
alpar@1218
   583
alpar@1218
   584
    ///Executes the algorithm until \c dest is reached.
alpar@1218
   585
    ///
alpar@1218
   586
    ///\pre init() must be called and at least one node should be added
alpar@1218
   587
    ///with addSource() before using this function.
alpar@1218
   588
    ///
alpar@1218
   589
    ///This method runs the %DFS algorithm from the root node(s)
alpar@1218
   590
    ///in order to
alpar@1218
   591
    ///compute the
alpar@1218
   592
    ///%DFS path to \c dest. The algorithm computes
alpar@1218
   593
    ///- The %DFS path to \c  dest.
athos@1443
   594
    ///- The distance of \c dest from the root(s) in the %DFS tree.
alpar@1218
   595
    ///
alpar@1218
   596
    void start(Node dest)
alpar@1218
   597
    {
alpar@1233
   598
      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
alpar@1233
   599
	processNextEdge();
alpar@1218
   600
    }
alpar@1218
   601
    
alpar@1218
   602
    ///Executes the algorithm until a condition is met.
alpar@1218
   603
alpar@1218
   604
    ///Executes the algorithm until a condition is met.
alpar@1218
   605
    ///
alpar@1218
   606
    ///\pre init() must be called and at least one node should be added
alpar@1218
   607
    ///with addSource() before using this function.
alpar@1218
   608
    ///
alpar@1233
   609
    ///\param nm must be a bool (or convertible) edge map. The algorithm
athos@1438
   610
    ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
athos@1443
   611
    ///
athos@1438
   612
    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
alpar@1233
   613
    ///not a node map.
alpar@1218
   614
    template<class NM>
alpar@1218
   615
      void start(const NM &nm)
alpar@1218
   616
      {
alpar@1233
   617
	while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
alpar@1218
   618
      }
alpar@1218
   619
    
alpar@1218
   620
    ///Runs %DFS algorithm from node \c s.
alpar@1218
   621
    
alpar@1218
   622
    ///This method runs the %DFS algorithm from a root node \c s
alpar@1218
   623
    ///in order to
alpar@1218
   624
    ///compute the
alpar@1218
   625
    ///%DFS path to each node. The algorithm computes
alpar@1218
   626
    ///- The %DFS tree.
athos@1443
   627
    ///- The distance of each node from the root in the %DFS tree.
alpar@1218
   628
    ///
alpar@1218
   629
    ///\note d.run(s) is just a shortcut of the following code.
alpar@1218
   630
    ///\code
alpar@1218
   631
    ///  d.init();
alpar@1218
   632
    ///  d.addSource(s);
alpar@1218
   633
    ///  d.start();
alpar@1218
   634
    ///\endcode
alpar@1218
   635
    void run(Node s) {
alpar@1218
   636
      init();
alpar@1218
   637
      addSource(s);
alpar@1218
   638
      start();
alpar@1218
   639
    }
alpar@1218
   640
    
alpar@1218
   641
    ///Finds the %DFS path between \c s and \c t.
alpar@1218
   642
    
alpar@1218
   643
    ///Finds the %DFS path between \c s and \c t.
alpar@1218
   644
    ///
alpar@1218
   645
    ///\return The length of the %DFS s---t path if there exists one,
alpar@1218
   646
    ///0 otherwise.
athos@1540
   647
    ///\note Apart from the return value, d.run(s,t) is
alpar@1218
   648
    ///just a shortcut of the following code.
alpar@1218
   649
    ///\code
alpar@1218
   650
    ///  d.init();
alpar@1218
   651
    ///  d.addSource(s);
alpar@1218
   652
    ///  d.start(t);
alpar@1218
   653
    ///\endcode
alpar@1218
   654
    int run(Node s,Node t) {
alpar@1218
   655
      init();
alpar@1218
   656
      addSource(s);
alpar@1218
   657
      start(t);
alpar@1233
   658
      return reached(t)?_stack_head+1:0;
alpar@1218
   659
    }
alpar@1218
   660
    
alpar@1218
   661
    ///@}
alpar@1218
   662
alpar@1218
   663
    ///\name Query Functions
alpar@1218
   664
    ///The result of the %DFS algorithm can be obtained using these
alpar@1218
   665
    ///functions.\n
alpar@1218
   666
    ///Before the use of these functions,
alpar@1218
   667
    ///either run() or start() must be called.
alpar@1218
   668
    
alpar@1218
   669
    ///@{
alpar@1218
   670
alpar@1283
   671
    ///Copies the path to \c t on the DFS tree into \c p
alpar@1283
   672
    
athos@1443
   673
    ///This function copies the path to \c t on the DFS tree  into \c p.
athos@1438
   674
    ///If \c t is a source itself or unreachable, then it does not
alpar@1283
   675
    ///alter \c p.
athos@1438
   676
    ///\todo Is this the right way to handle unreachable nodes?
athos@1438
   677
    ///
alpar@1283
   678
    ///\return Returns \c true if a path to \c t was actually copied to \c p,
alpar@1283
   679
    ///\c false otherwise.
alpar@1283
   680
    ///\sa DirPath
alpar@1283
   681
    template<class P>
alpar@1283
   682
    bool getPath(P &p,Node t) 
alpar@1283
   683
    {
alpar@1283
   684
      if(reached(t)) {
alpar@1283
   685
	p.clear();
alpar@1283
   686
	typename P::Builder b(p);
alpar@1283
   687
	for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
alpar@1283
   688
	  b.pushFront(pred(t));
alpar@1283
   689
	b.commit();
alpar@1283
   690
	return true;
alpar@1283
   691
      }
alpar@1283
   692
      return false;
alpar@1283
   693
    }
alpar@1283
   694
alpar@1218
   695
    ///The distance of a node from the root(s).
alpar@1218
   696
alpar@1218
   697
    ///Returns the distance of a node from the root(s).
alpar@780
   698
    ///\pre \ref run() must be called before using this function.
athos@1438
   699
    ///\warning If node \c v is unreachable from the root(s) then the return value
alpar@780
   700
    ///of this funcion is undefined.
alpar@1218
   701
    int dist(Node v) const { return (*_dist)[v]; }
alpar@780
   702
alpar@1218
   703
    ///Returns the 'previous edge' of the %DFS tree.
alpar@780
   704
alpar@1218
   705
    ///For a node \c v it returns the 'previous edge'
alpar@1218
   706
    ///of the %DFS path,
alpar@1218
   707
    ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
alpar@780
   708
    ///v. It is \ref INVALID
alpar@1218
   709
    ///if \c v is unreachable from the root(s) or \c v is a root. The
alpar@781
   710
    ///%DFS tree used here is equal to the %DFS tree used in
alpar@1218
   711
    ///\ref predNode(Node v).
alpar@1218
   712
    ///\pre Either \ref run() or \ref start() must be called before using
alpar@780
   713
    ///this function.
alpar@1218
   714
    ///\todo predEdge could be a better name.
alpar@1218
   715
    Edge pred(Node v) const { return (*_pred)[v];}
alpar@780
   716
alpar@781
   717
    ///Returns the 'previous node' of the %DFS tree.
alpar@780
   718
alpar@1218
   719
    ///For a node \c v it returns the 'previous node'
alpar@1218
   720
    ///of the %DFS tree,
alpar@1218
   721
    ///i.e. it returns the last but one node from a %DFS path from the
alpar@1218
   722
    ///root(a) to \c /v.
alpar@1218
   723
    ///It is INVALID if \c v is unreachable from the root(s) or
alpar@1218
   724
    ///if \c v itself a root.
alpar@1218
   725
    ///The %DFS tree used here is equal to the %DFS
alpar@1218
   726
    ///tree used in \ref pred(Node v).
alpar@1218
   727
    ///\pre Either \ref run() or \ref start() must be called before
alpar@780
   728
    ///using this function.
alpar@1218
   729
    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
alpar@1218
   730
				  G->source((*_pred)[v]); }
alpar@780
   731
    
alpar@1218
   732
    ///Returns a reference to the NodeMap of distances.
alpar@1218
   733
alpar@1218
   734
    ///Returns a reference to the NodeMap of distances.
alpar@1218
   735
    ///\pre Either \ref run() or \ref init() must
alpar@780
   736
    ///be called before using this function.
alpar@1218
   737
    const DistMap &distMap() const { return *_dist;}
alpar@780
   738
 
alpar@1218
   739
    ///Returns a reference to the %DFS edge-tree map.
alpar@780
   740
alpar@780
   741
    ///Returns a reference to the NodeMap of the edges of the
alpar@781
   742
    ///%DFS tree.
alpar@1218
   743
    ///\pre Either \ref run() or \ref init()
alpar@1218
   744
    ///must be called before using this function.
alpar@1218
   745
    const PredMap &predMap() const { return *_pred;}
alpar@780
   746
 
alpar@1218
   747
//     ///Returns a reference to the map of nodes of %DFS paths.
alpar@780
   748
alpar@1218
   749
//     ///Returns a reference to the NodeMap of the last but one nodes of the
alpar@1218
   750
//     ///%DFS tree.
alpar@1218
   751
//     ///\pre \ref run() must be called before using this function.
alpar@1218
   752
//     const PredNodeMap &predNodeMap() const { return *_predNode;}
alpar@780
   753
alpar@780
   754
    ///Checks if a node is reachable from the root.
alpar@780
   755
athos@1438
   756
    ///Returns \c true if \c v is reachable from the root(s).
athos@1438
   757
    ///\warning The source nodes are inditated as unreachable.
alpar@1218
   758
    ///\pre Either \ref run() or \ref start()
alpar@1218
   759
    ///must be called before using this function.
alpar@780
   760
    ///
alpar@1218
   761
    bool reached(Node v) { return (*_reached)[v]; }
alpar@1218
   762
    
alpar@1218
   763
    ///@}
alpar@1218
   764
  };
alpar@1218
   765
alpar@1218
   766
  ///Default traits class of Dfs function.
alpar@1218
   767
alpar@1218
   768
  ///Default traits class of Dfs function.
alpar@1218
   769
  ///\param GR Graph type.
alpar@1218
   770
  template<class GR>
alpar@1218
   771
  struct DfsWizardDefaultTraits
alpar@1218
   772
  {
alpar@1218
   773
    ///The graph type the algorithm runs on. 
alpar@1218
   774
    typedef GR Graph;
alpar@1218
   775
    ///\brief The type of the map that stores the last
alpar@1218
   776
    ///edges of the %DFS paths.
alpar@1218
   777
    /// 
alpar@1218
   778
    ///The type of the map that stores the last
alpar@1218
   779
    ///edges of the %DFS paths.
alpar@1218
   780
    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@780
   781
    ///
alpar@1218
   782
    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
alpar@1218
   783
    ///Instantiates a PredMap.
alpar@1218
   784
 
alpar@1218
   785
    ///This function instantiates a \ref PredMap. 
alpar@1536
   786
    ///\param g is the graph, to which we would like to define the PredMap.
alpar@1218
   787
    ///\todo The graph alone may be insufficient to initialize
alpar@1536
   788
#ifdef DOXYGEN
alpar@1536
   789
    static PredMap *createPredMap(const GR &g) 
alpar@1536
   790
#else
alpar@1367
   791
    static PredMap *createPredMap(const GR &) 
alpar@1536
   792
#endif
alpar@1218
   793
    {
alpar@1218
   794
      return new PredMap();
alpar@1218
   795
    }
alpar@1218
   796
//     ///\brief The type of the map that stores the last but one
alpar@1218
   797
//     ///nodes of the %DFS paths.
alpar@1218
   798
//     ///
alpar@1218
   799
//     ///The type of the map that stores the last but one
alpar@1218
   800
//     ///nodes of the %DFS paths.
alpar@1218
   801
//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@1218
   802
//     ///
alpar@1218
   803
//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
alpar@1218
   804
//     ///Instantiates a PredNodeMap.
alpar@1218
   805
    
alpar@1218
   806
//     ///This function instantiates a \ref PredNodeMap. 
alpar@1218
   807
//     ///\param G is the graph, to which
alpar@1218
   808
//     ///we would like to define the \ref PredNodeMap
alpar@1218
   809
//     static PredNodeMap *createPredNodeMap(const GR &G)
alpar@1218
   810
//     {
alpar@1218
   811
//       return new PredNodeMap();
alpar@1218
   812
//     }
alpar@1218
   813
alpar@1218
   814
    ///The type of the map that indicates which nodes are processed.
alpar@1218
   815
 
alpar@1218
   816
    ///The type of the map that indicates which nodes are processed.
alpar@1218
   817
    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@1218
   818
    ///\todo named parameter to set this type, function to read and write.
alpar@1218
   819
    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
alpar@1218
   820
    ///Instantiates a ProcessedMap.
alpar@1218
   821
 
alpar@1218
   822
    ///This function instantiates a \ref ProcessedMap. 
alpar@1536
   823
    ///\param g is the graph, to which
alpar@1218
   824
    ///we would like to define the \ref ProcessedMap
alpar@1536
   825
#ifdef DOXYGEN
alpar@1536
   826
    static ProcessedMap *createProcessedMap(const GR &g)
alpar@1536
   827
#else
alpar@1367
   828
    static ProcessedMap *createProcessedMap(const GR &)
alpar@1536
   829
#endif
alpar@1218
   830
    {
alpar@1218
   831
      return new ProcessedMap();
alpar@1218
   832
    }
alpar@1218
   833
    ///The type of the map that indicates which nodes are reached.
alpar@1218
   834
 
alpar@1218
   835
    ///The type of the map that indicates which nodes are reached.
alpar@1218
   836
    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@1218
   837
    ///\todo named parameter to set this type, function to read and write.
alpar@1218
   838
    typedef typename Graph::template NodeMap<bool> ReachedMap;
alpar@1218
   839
    ///Instantiates a ReachedMap.
alpar@1218
   840
 
alpar@1218
   841
    ///This function instantiates a \ref ReachedMap. 
alpar@1218
   842
    ///\param G is the graph, to which
alpar@1218
   843
    ///we would like to define the \ref ReachedMap.
alpar@1218
   844
    static ReachedMap *createReachedMap(const GR &G)
alpar@1218
   845
    {
alpar@1218
   846
      return new ReachedMap(G);
alpar@1218
   847
    }
alpar@1218
   848
    ///The type of the map that stores the dists of the nodes.
alpar@1218
   849
 
alpar@1218
   850
    ///The type of the map that stores the dists of the nodes.
alpar@1218
   851
    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
alpar@1218
   852
    ///
alpar@1218
   853
    typedef NullMap<typename Graph::Node,int> DistMap;
alpar@1218
   854
    ///Instantiates a DistMap.
alpar@1218
   855
 
alpar@1218
   856
    ///This function instantiates a \ref DistMap. 
alpar@1536
   857
    ///\param g is the graph, to which we would like to define the \ref DistMap
alpar@1536
   858
#ifdef DOXYGEN
alpar@1536
   859
    static DistMap *createDistMap(const GR &g)
alpar@1536
   860
#else
alpar@1367
   861
    static DistMap *createDistMap(const GR &)
alpar@1536
   862
#endif
alpar@1218
   863
    {
alpar@1218
   864
      return new DistMap();
alpar@1218
   865
    }
alpar@1218
   866
  };
alpar@1218
   867
  
alpar@1218
   868
  /// Default traits used by \ref DfsWizard
alpar@1218
   869
alpar@1218
   870
  /// To make it easier to use Dfs algorithm
alpar@1218
   871
  ///we have created a wizard class.
alpar@1218
   872
  /// This \ref DfsWizard class needs default traits,
alpar@1218
   873
  ///as well as the \ref Dfs class.
alpar@1218
   874
  /// The \ref DfsWizardBase is a class to be the default traits of the
alpar@1218
   875
  /// \ref DfsWizard class.
alpar@1218
   876
  template<class GR>
alpar@1218
   877
  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
alpar@1218
   878
  {
alpar@1218
   879
alpar@1218
   880
    typedef DfsWizardDefaultTraits<GR> Base;
alpar@1218
   881
  protected:
alpar@1218
   882
    /// Type of the nodes in the graph.
alpar@1218
   883
    typedef typename Base::Graph::Node Node;
alpar@1218
   884
alpar@1218
   885
    /// Pointer to the underlying graph.
alpar@1218
   886
    void *_g;
alpar@1218
   887
    ///Pointer to the map of reached nodes.
alpar@1218
   888
    void *_reached;
alpar@1218
   889
    ///Pointer to the map of processed nodes.
alpar@1218
   890
    void *_processed;
alpar@1218
   891
    ///Pointer to the map of predecessors edges.
alpar@1218
   892
    void *_pred;
alpar@1218
   893
//     ///Pointer to the map of predecessors nodes.
alpar@1218
   894
//     void *_predNode;
alpar@1218
   895
    ///Pointer to the map of distances.
alpar@1218
   896
    void *_dist;
alpar@1218
   897
    ///Pointer to the source node.
alpar@1218
   898
    Node _source;
alpar@1218
   899
    
alpar@1218
   900
    public:
alpar@1218
   901
    /// Constructor.
alpar@1218
   902
    
alpar@1218
   903
    /// This constructor does not require parameters, therefore it initiates
alpar@1218
   904
    /// all of the attributes to default values (0, INVALID).
alpar@1218
   905
    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
alpar@1218
   906
// 			   _predNode(0),
alpar@1218
   907
			   _dist(0), _source(INVALID) {}
alpar@1218
   908
alpar@1218
   909
    /// Constructor.
alpar@1218
   910
    
alpar@1218
   911
    /// This constructor requires some parameters,
alpar@1218
   912
    /// listed in the parameters list.
alpar@1218
   913
    /// Others are initiated to 0.
alpar@1218
   914
    /// \param g is the initial value of  \ref _g
alpar@1218
   915
    /// \param s is the initial value of  \ref _source
alpar@1218
   916
    DfsWizardBase(const GR &g, Node s=INVALID) :
alpar@1218
   917
      _g((void *)&g), _reached(0), _processed(0), _pred(0),
alpar@1218
   918
//       _predNode(0),
alpar@1218
   919
      _dist(0), _source(s) {}
alpar@1218
   920
alpar@1218
   921
  };
alpar@1218
   922
  
athos@1443
   923
  /// A class to make the usage of the Dfs algorithm easier
alpar@1218
   924
athos@1443
   925
  /// This class is created to make it easier to use the Dfs algorithm.
alpar@1218
   926
  /// It uses the functions and features of the plain \ref Dfs,
alpar@1218
   927
  /// but it is much simpler to use it.
alpar@1218
   928
  ///
alpar@1218
   929
  /// Simplicity means that the way to change the types defined
alpar@1218
   930
  /// in the traits class is based on functions that returns the new class
alpar@1218
   931
  /// and not on templatable built-in classes.
alpar@1218
   932
  /// When using the plain \ref Dfs
alpar@1218
   933
  /// the new class with the modified type comes from
alpar@1218
   934
  /// the original class by using the ::
alpar@1218
   935
  /// operator. In the case of \ref DfsWizard only
alpar@1218
   936
  /// a function have to be called and it will
alpar@1218
   937
  /// return the needed class.
alpar@1218
   938
  ///
alpar@1218
   939
  /// It does not have own \ref run method. When its \ref run method is called
athos@1438
   940
  /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
alpar@1218
   941
  /// method of it.
alpar@1218
   942
  template<class TR>
alpar@1218
   943
  class DfsWizard : public TR
alpar@1218
   944
  {
alpar@1218
   945
    typedef TR Base;
alpar@1218
   946
alpar@1218
   947
    ///The type of the underlying graph.
alpar@1218
   948
    typedef typename TR::Graph Graph;
alpar@1218
   949
    //\e
alpar@1218
   950
    typedef typename Graph::Node Node;
alpar@1218
   951
    //\e
alpar@1218
   952
    typedef typename Graph::NodeIt NodeIt;
alpar@1218
   953
    //\e
alpar@1218
   954
    typedef typename Graph::Edge Edge;
alpar@1218
   955
    //\e
alpar@1218
   956
    typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@1218
   957
    
alpar@1218
   958
    ///\brief The type of the map that stores
alpar@1218
   959
    ///the reached nodes
alpar@1218
   960
    typedef typename TR::ReachedMap ReachedMap;
alpar@1218
   961
    ///\brief The type of the map that stores
alpar@1218
   962
    ///the processed nodes
alpar@1218
   963
    typedef typename TR::ProcessedMap ProcessedMap;
alpar@1218
   964
    ///\brief The type of the map that stores the last
alpar@1218
   965
    ///edges of the %DFS paths.
alpar@1218
   966
    typedef typename TR::PredMap PredMap;
alpar@1218
   967
//     ///\brief The type of the map that stores the last but one
alpar@1218
   968
//     ///nodes of the %DFS paths.
alpar@1218
   969
//     typedef typename TR::PredNodeMap PredNodeMap;
athos@1443
   970
    ///The type of the map that stores the distances of the nodes.
alpar@1218
   971
    typedef typename TR::DistMap DistMap;
alpar@1218
   972
alpar@1218
   973
public:
alpar@1218
   974
    /// Constructor.
alpar@1218
   975
    DfsWizard() : TR() {}
alpar@1218
   976
alpar@1218
   977
    /// Constructor that requires parameters.
alpar@1218
   978
alpar@1218
   979
    /// Constructor that requires parameters.
alpar@1218
   980
    /// These parameters will be the default values for the traits class.
alpar@1218
   981
    DfsWizard(const Graph &g, Node s=INVALID) :
alpar@1218
   982
      TR(g,s) {}
alpar@1218
   983
alpar@1218
   984
    ///Copy constructor
alpar@1218
   985
    DfsWizard(const TR &b) : TR(b) {}
alpar@1218
   986
alpar@1218
   987
    ~DfsWizard() {}
alpar@1218
   988
alpar@1218
   989
    ///Runs Dfs algorithm from a given node.
alpar@1218
   990
    
alpar@1218
   991
    ///Runs Dfs algorithm from a given node.
alpar@1218
   992
    ///The node can be given by the \ref source function.
alpar@1218
   993
    void run()
alpar@1218
   994
    {
alpar@1218
   995
      if(Base::_source==INVALID) throw UninitializedParameter();
alpar@1218
   996
      Dfs<Graph,TR> alg(*(Graph*)Base::_g);
alpar@1218
   997
      if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
alpar@1218
   998
      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
alpar@1218
   999
      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
alpar@1218
  1000
//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
alpar@1218
  1001
      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
alpar@1218
  1002
      alg.run(Base::_source);
alpar@1218
  1003
    }
alpar@1218
  1004
alpar@1218
  1005
    ///Runs Dfs algorithm from the given node.
alpar@1218
  1006
alpar@1218
  1007
    ///Runs Dfs algorithm from the given node.
alpar@1218
  1008
    ///\param s is the given source.
alpar@1218
  1009
    void run(Node s)
alpar@1218
  1010
    {
alpar@1218
  1011
      Base::_source=s;
alpar@1218
  1012
      run();
alpar@1218
  1013
    }
alpar@1218
  1014
alpar@1218
  1015
    template<class T>
alpar@1218
  1016
    struct DefPredMapBase : public Base {
alpar@1218
  1017
      typedef T PredMap;
alpar@1367
  1018
      static PredMap *createPredMap(const Graph &) { return 0; };
alpar@1236
  1019
      DefPredMapBase(const TR &b) : TR(b) {}
alpar@1218
  1020
    };
alpar@1218
  1021
    
alpar@1218
  1022
    ///\brief \ref named-templ-param "Named parameter"
alpar@1218
  1023
    ///function for setting PredMap type
alpar@1218
  1024
    ///
alpar@1218
  1025
    /// \ref named-templ-param "Named parameter"
alpar@1218
  1026
    ///function for setting PredMap type
alpar@1218
  1027
    ///
alpar@1218
  1028
    template<class T>
alpar@1218
  1029
    DfsWizard<DefPredMapBase<T> > predMap(const T &t) 
alpar@1218
  1030
    {
alpar@1218
  1031
      Base::_pred=(void *)&t;
alpar@1218
  1032
      return DfsWizard<DefPredMapBase<T> >(*this);
alpar@1218
  1033
    }
alpar@1218
  1034
    
alpar@1218
  1035
 
alpar@1218
  1036
    template<class T>
alpar@1218
  1037
    struct DefReachedMapBase : public Base {
alpar@1218
  1038
      typedef T ReachedMap;
alpar@1367
  1039
      static ReachedMap *createReachedMap(const Graph &) { return 0; };
alpar@1236
  1040
      DefReachedMapBase(const TR &b) : TR(b) {}
alpar@1218
  1041
    };
alpar@1218
  1042
    
alpar@1218
  1043
    ///\brief \ref named-templ-param "Named parameter"
alpar@1218
  1044
    ///function for setting ReachedMap
alpar@1218
  1045
    ///
alpar@1218
  1046
    /// \ref named-templ-param "Named parameter"
alpar@1218
  1047
    ///function for setting ReachedMap
alpar@1218
  1048
    ///
alpar@1218
  1049
    template<class T>
alpar@1218
  1050
    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
alpar@1218
  1051
    {
alpar@1218
  1052
      Base::_pred=(void *)&t;
alpar@1218
  1053
      return DfsWizard<DefReachedMapBase<T> >(*this);
alpar@1218
  1054
    }
alpar@1218
  1055
    
alpar@1218
  1056
alpar@1218
  1057
    template<class T>
alpar@1218
  1058
    struct DefProcessedMapBase : public Base {
alpar@1218
  1059
      typedef T ProcessedMap;
alpar@1367
  1060
      static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
alpar@1236
  1061
      DefProcessedMapBase(const TR &b) : TR(b) {}
alpar@1218
  1062
    };
alpar@1218
  1063
    
alpar@1218
  1064
    ///\brief \ref named-templ-param "Named parameter"
alpar@1218
  1065
    ///function for setting ProcessedMap
alpar@1218
  1066
    ///
alpar@1218
  1067
    /// \ref named-templ-param "Named parameter"
alpar@1218
  1068
    ///function for setting ProcessedMap
alpar@1218
  1069
    ///
alpar@1218
  1070
    template<class T>
alpar@1218
  1071
    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
alpar@1218
  1072
    {
alpar@1218
  1073
      Base::_pred=(void *)&t;
alpar@1218
  1074
      return DfsWizard<DefProcessedMapBase<T> >(*this);
alpar@1218
  1075
    }
alpar@1218
  1076
    
alpar@1218
  1077
alpar@1218
  1078
//     template<class T>
alpar@1218
  1079
//     struct DefPredNodeMapBase : public Base {
alpar@1218
  1080
//       typedef T PredNodeMap;
alpar@1218
  1081
//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
alpar@1236
  1082
//       DefPredNodeMapBase(const TR &b) : TR(b) {}
alpar@1218
  1083
//     };
alpar@1218
  1084
    
alpar@1218
  1085
//     ///\brief \ref named-templ-param "Named parameter"
alpar@1218
  1086
//     ///function for setting PredNodeMap type
alpar@1218
  1087
//     ///
alpar@1218
  1088
//     /// \ref named-templ-param "Named parameter"
alpar@1218
  1089
//     ///function for setting PredNodeMap type
alpar@1218
  1090
//     ///
alpar@1218
  1091
//     template<class T>
alpar@1218
  1092
//     DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
alpar@1218
  1093
//     {
alpar@1218
  1094
//       Base::_predNode=(void *)&t;
alpar@1218
  1095
//       return DfsWizard<DefPredNodeMapBase<T> >(*this);
alpar@1218
  1096
//     }
alpar@1218
  1097
   
alpar@1218
  1098
    template<class T>
alpar@1218
  1099
    struct DefDistMapBase : public Base {
alpar@1218
  1100
      typedef T DistMap;
alpar@1367
  1101
      static DistMap *createDistMap(const Graph &) { return 0; };
alpar@1236
  1102
      DefDistMapBase(const TR &b) : TR(b) {}
alpar@1218
  1103
    };
alpar@1218
  1104
    
alpar@1218
  1105
    ///\brief \ref named-templ-param "Named parameter"
alpar@1218
  1106
    ///function for setting DistMap type
alpar@1218
  1107
    ///
alpar@1218
  1108
    /// \ref named-templ-param "Named parameter"
alpar@1218
  1109
    ///function for setting DistMap type
alpar@1218
  1110
    ///
alpar@1218
  1111
    template<class T>
alpar@1218
  1112
    DfsWizard<DefDistMapBase<T> > distMap(const T &t) 
alpar@1218
  1113
    {
alpar@1218
  1114
      Base::_dist=(void *)&t;
alpar@1218
  1115
      return DfsWizard<DefDistMapBase<T> >(*this);
alpar@1218
  1116
    }
alpar@1218
  1117
    
alpar@1218
  1118
    /// Sets the source node, from which the Dfs algorithm runs.
alpar@1218
  1119
alpar@1218
  1120
    /// Sets the source node, from which the Dfs algorithm runs.
alpar@1218
  1121
    /// \param s is the source node.
alpar@1218
  1122
    DfsWizard<TR> &source(Node s) 
alpar@1218
  1123
    {
alpar@1218
  1124
      Base::_source=s;
alpar@1218
  1125
      return *this;
alpar@1218
  1126
    }
alpar@780
  1127
    
alpar@780
  1128
  };
alpar@780
  1129
  
alpar@1218
  1130
  ///Function type interface for Dfs algorithm.
alpar@1218
  1131
alpar@1218
  1132
  /// \ingroup flowalgs
alpar@1218
  1133
  ///Function type interface for Dfs algorithm.
alpar@1218
  1134
  ///
alpar@1218
  1135
  ///This function also has several
alpar@1218
  1136
  ///\ref named-templ-func-param "named parameters",
alpar@1218
  1137
  ///they are declared as the members of class \ref DfsWizard.
alpar@1218
  1138
  ///The following
alpar@1218
  1139
  ///example shows how to use these parameters.
alpar@1218
  1140
  ///\code
alpar@1218
  1141
  ///  dfs(g,source).predMap(preds).run();
alpar@1218
  1142
  ///\endcode
alpar@1218
  1143
  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
alpar@1218
  1144
  ///to the end of the parameter list.
alpar@1218
  1145
  ///\sa DfsWizard
alpar@1218
  1146
  ///\sa Dfs
alpar@1218
  1147
  template<class GR>
alpar@1218
  1148
  DfsWizard<DfsWizardBase<GR> >
alpar@1218
  1149
  dfs(const GR &g,typename GR::Node s=INVALID)
alpar@1218
  1150
  {
alpar@1218
  1151
    return DfsWizard<DfsWizardBase<GR> >(g,s);
alpar@1218
  1152
  }
alpar@1218
  1153
alpar@921
  1154
} //END OF NAMESPACE LEMON
alpar@780
  1155
alpar@780
  1156
#endif
alpar@780
  1157