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