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