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