lemon/dijkstra.h
author Balazs Dezso <deba@inf.elte.hu>
Mon, 20 Oct 2008 12:36:02 +0200
changeset 335 160bf92c7cdc
parent 247 f1158744a112
child 258 0310c8984732
permissions -rw-r--r--
Improvement on grid graphs

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