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