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