lemon/bellman_ford.h
author deba
Sun, 30 Dec 2007 18:23:32 +0000
changeset 2550 f26368148b9c
parent 2476 059dcdda37c5
child 2553 bfced05fa852
permissions -rw-r--r--
Changing degree of tournament tree
Bug fix in union find
Small efficiency improvment in bipartite matchings
deba@1699
     1
/* -*- C++ -*-
deba@1699
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@2391
     5
 * Copyright (C) 2003-2007
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1699
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1699
     8
 *
deba@1699
     9
 * Permission to use, modify and distribute this software is granted
deba@1699
    10
 * provided that this copyright notice appears in all copies. For
deba@1699
    11
 * precise terms see the accompanying LICENSE file.
deba@1699
    12
 *
deba@1699
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@1699
    14
 * express or implied, and with no claim as to its suitability for any
deba@1699
    15
 * purpose.
deba@1699
    16
 *
deba@1699
    17
 */
deba@1699
    18
deba@1699
    19
#ifndef LEMON_BELMANN_FORD_H
deba@1699
    20
#define LEMON_BELMANN_FORD_H
deba@1699
    21
deba@2376
    22
/// \ingroup shortest_path
deba@1699
    23
/// \file
deba@1864
    24
/// \brief BellmanFord algorithm.
deba@1699
    25
///
deba@1699
    26
deba@1699
    27
#include <lemon/list_graph.h>
deba@2335
    28
#include <lemon/bits/path_dump.h>
deba@1993
    29
#include <lemon/bits/invalid.h>
deba@2394
    30
#include <lemon/graph_utils.h>
deba@1699
    31
#include <lemon/error.h>
deba@1699
    32
#include <lemon/maps.h>
deba@1699
    33
deba@1699
    34
#include <limits>
deba@1699
    35
deba@1699
    36
namespace lemon {
deba@1699
    37
deba@1864
    38
  /// \brief Default OperationTraits for the BellmanFord algorithm class.
deba@1699
    39
  ///  
deba@1699
    40
  /// It defines all computational operations and constants which are
alpar@2408
    41
  /// used in the Bellman-Ford algorithm. The default implementation
deba@1699
    42
  /// is based on the numeric_limits class. If the numeric type does not
deba@1699
    43
  /// have infinity value then the maximum value is used as extremal
deba@1699
    44
  /// infinity value.
deba@1699
    45
  template <
deba@1699
    46
    typename Value, 
deba@1699
    47
    bool has_infinity = std::numeric_limits<Value>::has_infinity>
deba@1864
    48
  struct BellmanFordDefaultOperationTraits {
deba@1699
    49
    /// \brief Gives back the zero value of the type.
deba@1699
    50
    static Value zero() {
deba@1699
    51
      return static_cast<Value>(0);
deba@1699
    52
    }
deba@1699
    53
    /// \brief Gives back the positive infinity value of the type.
deba@1699
    54
    static Value infinity() {
deba@1699
    55
      return std::numeric_limits<Value>::infinity();
deba@1699
    56
    }
deba@1699
    57
    /// \brief Gives back the sum of the given two elements.
deba@1699
    58
    static Value plus(const Value& left, const Value& right) {
deba@1699
    59
      return left + right;
deba@1699
    60
    }
deba@1699
    61
    /// \brief Gives back true only if the first value less than the second.
deba@1699
    62
    static bool less(const Value& left, const Value& right) {
deba@1699
    63
      return left < right;
deba@1699
    64
    }
deba@1699
    65
  };
deba@1699
    66
deba@1699
    67
  template <typename Value>
deba@1864
    68
  struct BellmanFordDefaultOperationTraits<Value, false> {
deba@1699
    69
    static Value zero() {
deba@1699
    70
      return static_cast<Value>(0);
deba@1699
    71
    }
deba@1699
    72
    static Value infinity() {
deba@1699
    73
      return std::numeric_limits<Value>::max();
deba@1699
    74
    }
deba@1699
    75
    static Value plus(const Value& left, const Value& right) {
deba@1699
    76
      if (left == infinity() || right == infinity()) return infinity();
deba@1699
    77
      return left + right;
deba@1699
    78
    }
deba@1699
    79
    static bool less(const Value& left, const Value& right) {
deba@1699
    80
      return left < right;
deba@1699
    81
    }
deba@1699
    82
  };
deba@1699
    83
  
deba@1864
    84
  /// \brief Default traits class of BellmanFord class.
deba@1699
    85
  ///
deba@1864
    86
  /// Default traits class of BellmanFord class.
deba@1699
    87
  /// \param _Graph Graph type.
deba@1699
    88
  /// \param _LegthMap Type of length map.
deba@1699
    89
  template<class _Graph, class _LengthMap>
deba@1864
    90
  struct BellmanFordDefaultTraits {
deba@1699
    91
    /// The graph type the algorithm runs on. 
deba@1699
    92
    typedef _Graph Graph;
deba@1699
    93
deba@1699
    94
    /// \brief The type of the map that stores the edge lengths.
deba@1699
    95
    ///
deba@1699
    96
    /// The type of the map that stores the edge lengths.
alpar@2260
    97
    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
deba@1699
    98
    typedef _LengthMap LengthMap;
deba@1699
    99
deba@1699
   100
    // The type of the length of the edges.
deba@1699
   101
    typedef typename _LengthMap::Value Value;
deba@1699
   102
alpar@2408
   103
    /// \brief Operation traits for Bellman-Ford algorithm.
deba@1699
   104
    ///
deba@1699
   105
    /// It defines the infinity type on the given Value type
deba@1699
   106
    /// and the used operation.
deba@1864
   107
    /// \see BellmanFordDefaultOperationTraits
deba@1864
   108
    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
deba@1699
   109
 
deba@1699
   110
    /// \brief The type of the map that stores the last edges of the 
deba@1699
   111
    /// shortest paths.
deba@1699
   112
    /// 
deba@1699
   113
    /// The type of the map that stores the last
deba@1699
   114
    /// edges of the shortest paths.
alpar@2260
   115
    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
deba@1699
   116
    ///
deba@1699
   117
    typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
deba@1699
   118
deba@1699
   119
    /// \brief Instantiates a PredMap.
deba@1699
   120
    /// 
deba@1699
   121
    /// This function instantiates a \ref PredMap. 
deba@1858
   122
    /// \param graph is the graph, to which we would like to define the PredMap.
deba@1699
   123
    static PredMap *createPredMap(const _Graph& graph) {
deba@1699
   124
      return new PredMap(graph);
deba@1699
   125
    }
deba@1699
   126
deba@1699
   127
    /// \brief The type of the map that stores the dists of the nodes.
deba@1699
   128
    ///
deba@1699
   129
    /// The type of the map that stores the dists of the nodes.
alpar@2260
   130
    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
deba@1699
   131
    ///
deba@1699
   132
    typedef typename Graph::template NodeMap<typename _LengthMap::Value> 
deba@1699
   133
    DistMap;
deba@1699
   134
deba@1699
   135
    /// \brief Instantiates a DistMap.
deba@1699
   136
    ///
deba@1699
   137
    /// This function instantiates a \ref DistMap. 
deba@1858
   138
    /// \param graph is the graph, to which we would like to define the 
deba@1699
   139
    /// \ref DistMap
deba@1699
   140
    static DistMap *createDistMap(const _Graph& graph) {
deba@1699
   141
      return new DistMap(graph);
deba@1699
   142
    }
deba@1699
   143
deba@1699
   144
  };
deba@1699
   145
  
deba@1864
   146
  /// \brief %BellmanFord algorithm class.
deba@1699
   147
  ///
deba@2376
   148
  /// \ingroup shortest_path
deba@1864
   149
  /// This class provides an efficient implementation of \c Bellman-Ford 
deba@1699
   150
  /// algorithm. The edge lengths are passed to the algorithm using a
alpar@2260
   151
  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
deba@1699
   152
  /// kind of length.
deba@1699
   153
  ///
deba@1864
   154
  /// The Bellman-Ford algorithm solves the shortest path from one node
deba@1723
   155
  /// problem when the edges can have negative length but the graph should
deba@1754
   156
  /// not contain cycles with negative sum of length. If we can assume
deba@1723
   157
  /// that all edge is non-negative in the graph then the dijkstra algorithm
deba@1723
   158
  /// should be used rather.
deba@1723
   159
  ///
deba@2042
   160
  /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
deba@1723
   161
  ///
deba@1699
   162
  /// The type of the length is determined by the
alpar@2260
   163
  /// \ref concepts::ReadMap::Value "Value" of the length map.
deba@1699
   164
  ///
deba@1699
   165
  /// \param _Graph The graph type the algorithm runs on. The default value
deba@1699
   166
  /// is \ref ListGraph. The value of _Graph is not used directly by
deba@1864
   167
  /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
deba@1699
   168
  /// \param _LengthMap This read-only EdgeMap determines the lengths of the
alpar@2260
   169
  /// edges. The default map type is \ref concepts::Graph::EdgeMap 
deba@1699
   170
  /// "Graph::EdgeMap<int>".  The value of _LengthMap is not used directly 
deba@1864
   171
  /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.  
deba@1699
   172
  /// \param _Traits Traits class to set various data types used by the 
deba@1864
   173
  /// algorithm.  The default traits class is \ref BellmanFordDefaultTraits
deba@1864
   174
  /// "BellmanFordDefaultTraits<_Graph,_LengthMap>".  See \ref
deba@1864
   175
  /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
deba@1699
   176
  /// class.
deba@1699
   177
  ///
deba@1699
   178
  /// \author Balazs Dezso
deba@1699
   179
deba@1710
   180
#ifdef DOXYGEN
deba@1710
   181
  template <typename _Graph, typename _LengthMap, typename _Traits>
deba@1710
   182
#else
deba@1699
   183
  template <typename _Graph=ListGraph,
deba@1699
   184
	    typename _LengthMap=typename _Graph::template EdgeMap<int>,
deba@1864
   185
	    typename _Traits=BellmanFordDefaultTraits<_Graph,_LengthMap> >
deba@1710
   186
#endif
deba@1864
   187
  class BellmanFord {
deba@1699
   188
  public:
deba@1699
   189
    
deba@1699
   190
    /// \brief \ref Exception for uninitialized parameters.
deba@1699
   191
    ///
deba@1699
   192
    /// This error represents problems in the initialization
deba@1699
   193
    /// of the parameters of the algorithms.
deba@1699
   194
deba@1699
   195
    class UninitializedParameter : public lemon::UninitializedParameter {
deba@1699
   196
    public:
alpar@2151
   197
      virtual const char* what() const throw() {
deba@1864
   198
	return "lemon::BellmanFord::UninitializedParameter";
deba@1699
   199
      }
deba@1699
   200
    };
deba@1699
   201
deba@1699
   202
    typedef _Traits Traits;
deba@1699
   203
    ///The type of the underlying graph.
deba@1699
   204
    typedef typename _Traits::Graph Graph;
deba@1699
   205
deba@1699
   206
    typedef typename Graph::Node Node;
deba@1699
   207
    typedef typename Graph::NodeIt NodeIt;
deba@1699
   208
    typedef typename Graph::Edge Edge;
deba@1781
   209
    typedef typename Graph::OutEdgeIt OutEdgeIt;
deba@1699
   210
    
deba@1699
   211
    /// \brief The type of the length of the edges.
deba@1699
   212
    typedef typename _Traits::LengthMap::Value Value;
deba@1699
   213
    /// \brief The type of the map that stores the edge lengths.
deba@1699
   214
    typedef typename _Traits::LengthMap LengthMap;
deba@1699
   215
    /// \brief The type of the map that stores the last
deba@1699
   216
    /// edges of the shortest paths.
deba@1699
   217
    typedef typename _Traits::PredMap PredMap;
deba@1699
   218
    /// \brief The type of the map that stores the dists of the nodes.
deba@1699
   219
    typedef typename _Traits::DistMap DistMap;
deba@1699
   220
    /// \brief The operation traits.
deba@1699
   221
    typedef typename _Traits::OperationTraits OperationTraits;
deba@1699
   222
  private:
deba@1699
   223
    /// Pointer to the underlying graph.
deba@1699
   224
    const Graph *graph;
deba@1699
   225
    /// Pointer to the length map
deba@1699
   226
    const LengthMap *length;
deba@1699
   227
    ///Pointer to the map of predecessors edges.
deba@1699
   228
    PredMap *_pred;
deba@1699
   229
    ///Indicates if \ref _pred is locally allocated (\c true) or not.
deba@1699
   230
    bool local_pred;
deba@1699
   231
    ///Pointer to the map of distances.
deba@1699
   232
    DistMap *_dist;
deba@1699
   233
    ///Indicates if \ref _dist is locally allocated (\c true) or not.
deba@1699
   234
    bool local_dist;
deba@1699
   235
deba@1781
   236
    typedef typename Graph::template NodeMap<bool> MaskMap;
deba@1781
   237
    MaskMap *_mask;
deba@1781
   238
deba@1781
   239
    std::vector<Node> _process;
deba@1781
   240
deba@1699
   241
    /// Creates the maps if necessary.
deba@1699
   242
    void create_maps() {
deba@1699
   243
      if(!_pred) {
deba@1699
   244
	local_pred = true;
deba@1699
   245
	_pred = Traits::createPredMap(*graph);
deba@1699
   246
      }
deba@1699
   247
      if(!_dist) {
deba@1699
   248
	local_dist = true;
deba@1699
   249
	_dist = Traits::createDistMap(*graph);
deba@1699
   250
      }
deba@1781
   251
      _mask = new MaskMap(*graph, false);
deba@1699
   252
    }
deba@1699
   253
    
deba@1699
   254
  public :
deba@1699
   255
 
deba@1864
   256
    typedef BellmanFord Create;
deba@1710
   257
deba@1699
   258
    /// \name Named template parameters
deba@1699
   259
deba@1699
   260
    ///@{
deba@1699
   261
deba@1699
   262
    template <class T>
deba@1699
   263
    struct DefPredMapTraits : public Traits {
deba@1699
   264
      typedef T PredMap;
deba@1710
   265
      static PredMap *createPredMap(const Graph&) {
deba@1699
   266
	throw UninitializedParameter();
deba@1699
   267
      }
deba@1699
   268
    };
deba@1699
   269
deba@1699
   270
    /// \brief \ref named-templ-param "Named parameter" for setting PredMap 
deba@1699
   271
    /// type
deba@1699
   272
    /// \ref named-templ-param "Named parameter" for setting PredMap type
deba@1699
   273
    ///
deba@1699
   274
    template <class T>
deba@1858
   275
    struct DefPredMap 
deba@1864
   276
      : public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > {
deba@1864
   277
      typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
deba@1710
   278
    };
deba@1699
   279
    
deba@1699
   280
    template <class T>
deba@1699
   281
    struct DefDistMapTraits : public Traits {
deba@1699
   282
      typedef T DistMap;
klao@2010
   283
      static DistMap *createDistMap(const Graph&) {
deba@1699
   284
	throw UninitializedParameter();
deba@1699
   285
      }
deba@1699
   286
    };
deba@1699
   287
deba@1699
   288
    /// \brief \ref named-templ-param "Named parameter" for setting DistMap 
deba@1699
   289
    /// type
deba@1699
   290
    ///
deba@1699
   291
    /// \ref named-templ-param "Named parameter" for setting DistMap type
deba@1699
   292
    ///
deba@1699
   293
    template <class T>
deba@1710
   294
    struct DefDistMap 
deba@1864
   295
      : public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > {
deba@1864
   296
      typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
deba@1710
   297
    };
deba@1699
   298
    
deba@1699
   299
    template <class T>
deba@1699
   300
    struct DefOperationTraitsTraits : public Traits {
deba@1699
   301
      typedef T OperationTraits;
deba@1699
   302
    };
deba@1699
   303
    
deba@1699
   304
    /// \brief \ref named-templ-param "Named parameter" for setting 
deba@1699
   305
    /// OperationTraits type
deba@1699
   306
    ///
deba@1710
   307
    /// \ref named-templ-param "Named parameter" for setting OperationTraits
deba@1710
   308
    /// type
deba@1699
   309
    template <class T>
deba@1710
   310
    struct DefOperationTraits
deba@1864
   311
      : public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
deba@1864
   312
      typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
deba@1710
   313
      Create;
deba@1699
   314
    };
deba@1699
   315
    
deba@1699
   316
    ///@}
deba@1699
   317
deba@1710
   318
  protected:
deba@1710
   319
    
deba@1864
   320
    BellmanFord() {}
deba@1710
   321
deba@1699
   322
  public:      
deba@1699
   323
    
deba@1699
   324
    /// \brief Constructor.
deba@1699
   325
    ///
deba@1699
   326
    /// \param _graph the graph the algorithm will run on.
deba@1699
   327
    /// \param _length the length map used by the algorithm.
deba@1864
   328
    BellmanFord(const Graph& _graph, const LengthMap& _length) :
deba@1699
   329
      graph(&_graph), length(&_length),
deba@1699
   330
      _pred(0), local_pred(false),
deba@2074
   331
      _dist(0), local_dist(false), _mask(0) {}
deba@1699
   332
    
deba@1699
   333
    ///Destructor.
deba@1864
   334
    ~BellmanFord() {
deba@1699
   335
      if(local_pred) delete _pred;
deba@1699
   336
      if(local_dist) delete _dist;
deba@2074
   337
      if(_mask) delete _mask;
deba@1699
   338
    }
deba@1699
   339
deba@1699
   340
    /// \brief Sets the length map.
deba@1699
   341
    ///
deba@1699
   342
    /// Sets the length map.
deba@1699
   343
    /// \return \c (*this)
deba@1864
   344
    BellmanFord &lengthMap(const LengthMap &m) {
deba@1699
   345
      length = &m;
deba@1699
   346
      return *this;
deba@1699
   347
    }
deba@1699
   348
deba@1699
   349
    /// \brief Sets the map storing the predecessor edges.
deba@1699
   350
    ///
deba@1699
   351
    /// Sets the map storing the predecessor edges.
deba@1699
   352
    /// If you don't use this function before calling \ref run(),
deba@1699
   353
    /// it will allocate one. The destuctor deallocates this
deba@1699
   354
    /// automatically allocated map, of course.
deba@1699
   355
    /// \return \c (*this)
deba@1864
   356
    BellmanFord &predMap(PredMap &m) {
deba@1699
   357
      if(local_pred) {
deba@1699
   358
	delete _pred;
deba@1699
   359
	local_pred=false;
deba@1699
   360
      }
deba@1699
   361
      _pred = &m;
deba@1699
   362
      return *this;
deba@1699
   363
    }
deba@1699
   364
deba@1699
   365
    /// \brief Sets the map storing the distances calculated by the algorithm.
deba@1699
   366
    ///
deba@1699
   367
    /// Sets the map storing the distances calculated by the algorithm.
deba@1699
   368
    /// If you don't use this function before calling \ref run(),
deba@1699
   369
    /// it will allocate one. The destuctor deallocates this
deba@1699
   370
    /// automatically allocated map, of course.
deba@1699
   371
    /// \return \c (*this)
deba@1864
   372
    BellmanFord &distMap(DistMap &m) {
deba@1699
   373
      if(local_dist) {
deba@1699
   374
	delete _dist;
deba@1699
   375
	local_dist=false;
deba@1699
   376
      }
deba@1699
   377
      _dist = &m;
deba@1699
   378
      return *this;
deba@1699
   379
    }
deba@1699
   380
deba@1699
   381
    /// \name Execution control
deba@1699
   382
    /// The simplest way to execute the algorithm is to use
deba@1699
   383
    /// one of the member functions called \c run(...).
deba@1699
   384
    /// \n
deba@1699
   385
    /// If you need more control on the execution,
deba@1699
   386
    /// first you must call \ref init(), then you can add several source nodes
deba@1699
   387
    /// with \ref addSource().
deba@1699
   388
    /// Finally \ref start() will perform the actual path
deba@1699
   389
    /// computation.
deba@1699
   390
deba@1699
   391
    ///@{
deba@1699
   392
deba@1699
   393
    /// \brief Initializes the internal data structures.
deba@1699
   394
    /// 
deba@1699
   395
    /// Initializes the internal data structures.
deba@1710
   396
    void init(const Value value = OperationTraits::infinity()) {
deba@1699
   397
      create_maps();
deba@1699
   398
      for (NodeIt it(*graph); it != INVALID; ++it) {
deba@1699
   399
	_pred->set(it, INVALID);
deba@1710
   400
	_dist->set(it, value);
deba@1699
   401
      }
deba@1781
   402
      _process.clear();
deba@1781
   403
      if (OperationTraits::less(value, OperationTraits::infinity())) {
deba@1781
   404
	for (NodeIt it(*graph); it != INVALID; ++it) {
deba@1781
   405
	  _process.push_back(it);
deba@1783
   406
	  _mask->set(it, true);
deba@1781
   407
	}
deba@1781
   408
      }
deba@1699
   409
    }
deba@1699
   410
    
deba@1699
   411
    /// \brief Adds a new source node.
deba@1699
   412
    ///
alpar@2408
   413
    /// Adds a new source node. The optional second parameter is the 
alpar@2408
   414
    /// initial distance of the node. It just sets the distance of the 
alpar@2408
   415
    /// node to the given value.
deba@1699
   416
    void addSource(Node source, Value dst = OperationTraits::zero()) {
deba@1699
   417
      _dist->set(source, dst);
deba@1781
   418
      if (!(*_mask)[source]) {
deba@1781
   419
	_process.push_back(source);
deba@1781
   420
	_mask->set(source, true);
deba@1781
   421
      }
deba@1781
   422
    }
deba@1781
   423
alpar@2408
   424
    /// \brief Executes one round from the Bellman-Ford algorithm.
deba@1781
   425
    ///
deba@2059
   426
    /// If the algoritm calculated the distances in the previous round
deba@2059
   427
    /// exactly for all at most \f$ k \f$ length path lengths then it will
deba@2059
   428
    /// calculate the distances exactly for all at most \f$ k + 1 \f$
deba@2059
   429
    /// length path lengths. With \f$ k \f$ iteration this function
deba@2059
   430
    /// calculates the at most \f$ k \f$ length path lengths.
deba@2059
   431
    ///
deba@2059
   432
    /// \warning The paths with limited edge number cannot be retrieved
deba@2335
   433
    /// easily with \ref path() or \ref predEdge() functions. If you
deba@2059
   434
    /// need the shortest path and not just the distance you should store
kpeter@2476
   435
    /// after each iteration the \ref predMap() map and manually build
deba@2059
   436
    /// the path.
deba@2059
   437
    ///
kpeter@2517
   438
    /// \return \c true when the algorithm have not found more shorter
deba@2059
   439
    /// paths.
deba@1781
   440
    bool processNextRound() {
deba@2386
   441
      for (int i = 0; i < int(_process.size()); ++i) {
deba@1781
   442
	_mask->set(_process[i], false);
deba@1781
   443
      }
deba@1781
   444
      std::vector<Node> nextProcess;
deba@1781
   445
      std::vector<Value> values(_process.size());
deba@2386
   446
      for (int i = 0; i < int(_process.size()); ++i) {
klao@1857
   447
	values[i] = (*_dist)[_process[i]];
deba@1781
   448
      }
deba@2386
   449
      for (int i = 0; i < int(_process.size()); ++i) {
deba@1781
   450
	for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
deba@1781
   451
	  Node target = graph->target(it);
deba@1781
   452
	  Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
deba@1781
   453
	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
deba@1781
   454
	    _pred->set(target, it);
deba@1781
   455
	    _dist->set(target, relaxed);
deba@1781
   456
	    if (!(*_mask)[target]) {
deba@1781
   457
	      _mask->set(target, true);
deba@1781
   458
	      nextProcess.push_back(target);
deba@1781
   459
	    }
deba@1781
   460
	  }	  
deba@1781
   461
	}
deba@1781
   462
      }
deba@1781
   463
      _process.swap(nextProcess);
deba@1781
   464
      return _process.empty();
deba@1781
   465
    }
deba@1781
   466
alpar@2408
   467
    /// \brief Executes one weak round from the Bellman-Ford algorithm.
deba@1781
   468
    ///
deba@1781
   469
    /// If the algorithm calculated the distances in the
alpar@1816
   470
    /// previous round at least for all at most k length paths then it will
alpar@1816
   471
    /// calculate the distances at least for all at most k + 1 length paths.
alpar@1816
   472
    /// This function does not make it possible to calculate strictly the
alpar@1816
   473
    /// at most k length minimal paths, this is why it is
alpar@1816
   474
    /// called just weak round.
kpeter@2517
   475
    /// \return \c true when the algorithm have not found more shorter paths.
deba@1781
   476
    bool processNextWeakRound() {
deba@2386
   477
      for (int i = 0; i < int(_process.size()); ++i) {
deba@1781
   478
	_mask->set(_process[i], false);
deba@1781
   479
      }
deba@1781
   480
      std::vector<Node> nextProcess;
deba@2386
   481
      for (int i = 0; i < int(_process.size()); ++i) {
deba@1781
   482
	for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
deba@1781
   483
	  Node target = graph->target(it);
deba@1781
   484
	  Value relaxed = 
deba@1781
   485
	    OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
deba@1781
   486
	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
deba@1781
   487
	    _pred->set(target, it);
deba@1781
   488
	    _dist->set(target, relaxed);
deba@1781
   489
	    if (!(*_mask)[target]) {
deba@1781
   490
	      _mask->set(target, true);
deba@1781
   491
	      nextProcess.push_back(target);
deba@1781
   492
	    }
deba@1781
   493
	  }	  
deba@1781
   494
	}
deba@1781
   495
      }
deba@1781
   496
      _process.swap(nextProcess);
deba@1781
   497
      return _process.empty();
deba@1699
   498
    }
deba@1699
   499
deba@1699
   500
    /// \brief Executes the algorithm.
deba@1699
   501
    ///
deba@1699
   502
    /// \pre init() must be called and at least one node should be added
deba@1699
   503
    /// with addSource() before using this function.
deba@1699
   504
    ///
deba@1864
   505
    /// This method runs the %BellmanFord algorithm from the root node(s)
deba@1699
   506
    /// in order to compute the shortest path to each node. The algorithm 
deba@1699
   507
    /// computes 
deba@1699
   508
    /// - The shortest path tree.
deba@1699
   509
    /// - The distance of each node from the root(s).
deba@1699
   510
    void start() {
deba@1723
   511
      int num = countNodes(*graph) - 1;
deba@1723
   512
      for (int i = 0; i < num; ++i) {
deba@1781
   513
	if (processNextWeakRound()) break;
deba@1699
   514
      }
deba@1699
   515
    }
deba@1723
   516
deba@1754
   517
    /// \brief Executes the algorithm and checks the negative cycles.
deba@1723
   518
    ///
deba@1723
   519
    /// \pre init() must be called and at least one node should be added
kpeter@2517
   520
    /// with addSource() before using this function. 
deba@1723
   521
    ///
deba@1864
   522
    /// This method runs the %BellmanFord algorithm from the root node(s)
deba@1723
   523
    /// in order to compute the shortest path to each node. The algorithm 
deba@1723
   524
    /// computes 
deba@1723
   525
    /// - The shortest path tree.
deba@1723
   526
    /// - The distance of each node from the root(s).
kpeter@2517
   527
    /// 
kpeter@2517
   528
    /// \return \c false if there is a negative cycle in the graph.
deba@1723
   529
    bool checkedStart() {
deba@2393
   530
      int num = countNodes(*graph);
deba@1723
   531
      for (int i = 0; i < num; ++i) {
deba@1781
   532
	if (processNextWeakRound()) return true;
deba@1723
   533
      }
deba@2362
   534
      return _process.empty();
deba@1723
   535
    }
deba@1781
   536
deba@1781
   537
    /// \brief Executes the algorithm with path length limit.
deba@1781
   538
    ///
deba@1781
   539
    /// \pre init() must be called and at least one node should be added
deba@1781
   540
    /// with addSource() before using this function.
deba@1781
   541
    ///
deba@2059
   542
    /// This method runs the %BellmanFord algorithm from the root
deba@2059
   543
    /// node(s) in order to compute the shortest path lengths with at
deba@2059
   544
    /// most \c num edge.
deba@2059
   545
    ///
deba@2059
   546
    /// \warning The paths with limited edge number cannot be retrieved
deba@2335
   547
    /// easily with \ref path() or \ref predEdge() functions. If you
deba@2059
   548
    /// need the shortest path and not just the distance you should store
kpeter@2476
   549
    /// after each iteration the \ref predMap() map and manually build
deba@2059
   550
    /// the path.
deba@2059
   551
    ///
deba@2059
   552
    /// The algorithm computes
deba@2059
   553
    /// - The predecessor edge from each node.
deba@1781
   554
    /// - The limited distance of each node from the root(s).
deba@2059
   555
    void limitedStart(int num) {
deba@2059
   556
      for (int i = 0; i < num; ++i) {
deba@1781
   557
	if (processNextRound()) break;
deba@1781
   558
      }
deba@1781
   559
    }
deba@1699
   560
    
deba@1864
   561
    /// \brief Runs %BellmanFord algorithm from node \c s.
deba@1699
   562
    ///    
deba@1864
   563
    /// This method runs the %BellmanFord algorithm from a root node \c s
deba@1699
   564
    /// in order to compute the shortest path to each node. The algorithm 
deba@1699
   565
    /// computes
deba@1699
   566
    /// - The shortest path tree.
deba@1699
   567
    /// - The distance of each node from the root.
deba@1699
   568
    ///
deba@1699
   569
    /// \note d.run(s) is just a shortcut of the following code.
alpar@1946
   570
    ///\code
deba@1699
   571
    ///  d.init();
deba@1699
   572
    ///  d.addSource(s);
deba@1699
   573
    ///  d.start();
alpar@1946
   574
    ///\endcode
deba@1699
   575
    void run(Node s) {
deba@1699
   576
      init();
deba@1699
   577
      addSource(s);
deba@1699
   578
      start();
deba@1699
   579
    }
deba@1699
   580
    
deba@1864
   581
    /// \brief Runs %BellmanFord algorithm with limited path length 
klao@1857
   582
    /// from node \c s.
klao@1857
   583
    ///    
deba@1864
   584
    /// This method runs the %BellmanFord algorithm from a root node \c s
klao@1857
   585
    /// in order to compute the shortest path with at most \c len edges 
klao@1857
   586
    /// to each node. The algorithm computes
klao@1857
   587
    /// - The shortest path tree.
klao@1857
   588
    /// - The distance of each node from the root.
klao@1857
   589
    ///
deba@2362
   590
    /// \note d.run(s, num) is just a shortcut of the following code.
alpar@1946
   591
    ///\code
klao@1857
   592
    ///  d.init();
klao@1857
   593
    ///  d.addSource(s);
deba@2362
   594
    ///  d.limitedStart(num);
alpar@1946
   595
    ///\endcode
deba@2362
   596
    void run(Node s, int num) {
klao@1857
   597
      init();
klao@1857
   598
      addSource(s);
deba@2362
   599
      limitedStart(num);
klao@1857
   600
    }
klao@1857
   601
    
deba@1699
   602
    ///@}
deba@1699
   603
deba@1699
   604
    /// \name Query Functions
deba@1864
   605
    /// The result of the %BellmanFord algorithm can be obtained using these
deba@1699
   606
    /// functions.\n
deba@1699
   607
    /// Before the use of these functions,
deba@1699
   608
    /// either run() or start() must be called.
deba@1699
   609
    
deba@1699
   610
    ///@{
deba@1699
   611
alpar@2408
   612
    /// \brief Lemon iterator for get the active nodes.
deba@2070
   613
    ///
deba@2362
   614
    /// Lemon iterator for get the active nodes. This class provides a
deba@2070
   615
    /// common style lemon iterator which gives back a subset of the
deba@2070
   616
    /// nodes. The iterated nodes are active in the algorithm after
deba@2070
   617
    /// the last phase so these should be checked in the next phase to
deba@2070
   618
    /// find augmenting edges from these.
deba@2070
   619
    class ActiveIt {
deba@2070
   620
    public:
deba@2070
   621
deba@2070
   622
      /// \brief Constructor.
deba@2070
   623
      ///
deba@2070
   624
      /// Constructor for get the nodeset of the variable. 
deba@2070
   625
      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
deba@2070
   626
      {
deba@2070
   627
        _index = _algorithm->_process.size() - 1;
deba@2070
   628
      }
deba@2070
   629
deba@2070
   630
      /// \brief Invalid constructor.
deba@2070
   631
      ///
deba@2070
   632
      /// Invalid constructor.
deba@2070
   633
      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
deba@2070
   634
deba@2070
   635
      /// \brief Conversion to node.
deba@2070
   636
      ///
deba@2070
   637
      /// Conversion to node.
deba@2070
   638
      operator Node() const { 
deba@2070
   639
        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
deba@2070
   640
      }
deba@2070
   641
deba@2070
   642
      /// \brief Increment operator.
deba@2070
   643
      ///
deba@2070
   644
      /// Increment operator.
deba@2070
   645
      ActiveIt& operator++() {
deba@2070
   646
        --_index;
deba@2070
   647
        return *this; 
deba@2070
   648
      }
deba@2070
   649
deba@2070
   650
      bool operator==(const ActiveIt& it) const { 
deba@2386
   651
        return static_cast<Node>(*this) == static_cast<Node>(it); 
deba@2070
   652
      }
deba@2070
   653
      bool operator!=(const ActiveIt& it) const { 
deba@2386
   654
        return static_cast<Node>(*this) != static_cast<Node>(it); 
deba@2070
   655
      }
deba@2070
   656
      bool operator<(const ActiveIt& it) const { 
deba@2386
   657
        return static_cast<Node>(*this) < static_cast<Node>(it); 
deba@2070
   658
      }
deba@2070
   659
      
deba@2070
   660
    private:
deba@2070
   661
      const BellmanFord* _algorithm;
deba@2070
   662
      int _index;
deba@2070
   663
    };
deba@2070
   664
deba@2335
   665
    typedef PredMapPath<Graph, PredMap> Path;
deba@2335
   666
deba@2335
   667
    /// \brief Gives back the shortest path.
deba@1699
   668
    ///    
deba@2335
   669
    /// Gives back the shortest path.
deba@2335
   670
    /// \pre The \c t should be reachable from the source.
deba@2335
   671
    Path path(Node t) 
deba@2335
   672
    {
deba@2335
   673
      return Path(*graph, *_pred, t);
deba@1699
   674
    }
deba@2070
   675
deba@2335
   676
deba@2335
   677
    // TODO : implement negative cycle
deba@2335
   678
//     /// \brief Gives back a negative cycle.
deba@2335
   679
//     ///    
deba@2335
   680
//     /// This function gives back a negative cycle.
deba@2335
   681
//     /// If the algorithm have not found yet negative cycle it will give back
deba@2335
   682
//     /// an empty path.
deba@2335
   683
//     Path negativeCycle() {
deba@2335
   684
//       typename Graph::template NodeMap<int> state(*graph, 0);
deba@2335
   685
//       for (ActiveIt it(*this); it != INVALID; ++it) {
deba@2335
   686
//         if (state[it] == 0) {
deba@2335
   687
//           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
deba@2335
   688
//             if (state[t] == 0) {
deba@2335
   689
//               state[t] = 1;
deba@2335
   690
//             } else if (state[t] == 2) {
deba@2335
   691
//               break;
deba@2335
   692
//             } else {
deba@2335
   693
//               p.clear();
deba@2335
   694
//               typename Path::Builder b(p);
deba@2335
   695
//               b.setStartNode(t);
deba@2335
   696
//               b.pushFront(predEdge(t));
deba@2335
   697
//               for(Node s = predNode(t); s != t; s = predNode(s)) {
deba@2335
   698
//                 b.pushFront(predEdge(s));
deba@2335
   699
//               }
deba@2335
   700
//               b.commit();
deba@2335
   701
//               return true;
deba@2335
   702
//             }
deba@2335
   703
//           }
deba@2335
   704
//           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
deba@2335
   705
//             if (state[t] == 1) {
deba@2335
   706
//               state[t] = 2;
deba@2335
   707
//             } else {
deba@2335
   708
//               break;
deba@2335
   709
//             }
deba@2335
   710
//           }
deba@2335
   711
//         }
deba@2335
   712
//       }
deba@2335
   713
//       return false;
deba@2335
   714
//     }
deba@1699
   715
	  
deba@1699
   716
    /// \brief The distance of a node from the root.
deba@1699
   717
    ///
deba@1699
   718
    /// Returns the distance of a node from the root.
deba@1699
   719
    /// \pre \ref run() must be called before using this function.
deba@1699
   720
    /// \warning If node \c v in unreachable from the root the return value
deba@1699
   721
    /// of this funcion is undefined.
deba@1699
   722
    Value dist(Node v) const { return (*_dist)[v]; }
deba@1699
   723
deba@1699
   724
    /// \brief Returns the 'previous edge' of the shortest path tree.
deba@1699
   725
    ///
deba@1699
   726
    /// For a node \c v it returns the 'previous edge' of the shortest path 
deba@1699
   727
    /// tree, i.e. it returns the last edge of a shortest path from the root 
deba@1699
   728
    /// to \c v. It is \ref INVALID if \c v is unreachable from the root or 
deba@1699
   729
    /// if \c v=s. The shortest path tree used here is equal to the shortest 
deba@1699
   730
    /// path tree used in \ref predNode(). 
deba@1699
   731
    /// \pre \ref run() must be called before using
deba@1699
   732
    /// this function.
deba@1763
   733
    Edge predEdge(Node v) const { return (*_pred)[v]; }
deba@1699
   734
deba@1699
   735
    /// \brief Returns the 'previous node' of the shortest path tree.
deba@1699
   736
    ///
deba@1699
   737
    /// For a node \c v it returns the 'previous node' of the shortest path 
deba@1699
   738
    /// tree, i.e. it returns the last but one node from a shortest path from 
deba@1699
   739
    /// the root to \c /v. It is INVALID if \c v is unreachable from the root 
deba@1699
   740
    /// or if \c v=s. The shortest path tree used here is equal to the 
deba@1763
   741
    /// shortest path tree used in \ref predEdge().  \pre \ref run() must be 
deba@1699
   742
    /// called before using this function.
deba@1699
   743
    Node predNode(Node v) const { 
deba@1699
   744
      return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]); 
deba@1699
   745
    }
deba@1699
   746
    
deba@1699
   747
    /// \brief Returns a reference to the NodeMap of distances.
deba@1699
   748
    ///
deba@1699
   749
    /// Returns a reference to the NodeMap of distances. \pre \ref run() must
deba@1699
   750
    /// be called before using this function.
deba@1699
   751
    const DistMap &distMap() const { return *_dist;}
deba@1699
   752
 
deba@1699
   753
    /// \brief Returns a reference to the shortest path tree map.
deba@1699
   754
    ///
deba@1699
   755
    /// Returns a reference to the NodeMap of the edges of the
deba@1699
   756
    /// shortest path tree.
deba@1699
   757
    /// \pre \ref run() must be called before using this function.
deba@1699
   758
    const PredMap &predMap() const { return *_pred; }
deba@1699
   759
 
deba@1699
   760
    /// \brief Checks if a node is reachable from the root.
deba@1699
   761
    ///
deba@1699
   762
    /// Returns \c true if \c v is reachable from the root.
deba@1699
   763
    /// \pre \ref run() must be called before using this function.
deba@1699
   764
    ///
deba@1699
   765
    bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
deba@1699
   766
    
deba@1699
   767
    ///@}
deba@1699
   768
  };
deba@1699
   769
 
deba@1864
   770
  /// \brief Default traits class of BellmanFord function.
deba@1699
   771
  ///
deba@1864
   772
  /// Default traits class of BellmanFord function.
deba@1699
   773
  /// \param _Graph Graph type.
deba@1699
   774
  /// \param _LengthMap Type of length map.
deba@1699
   775
  template <typename _Graph, typename _LengthMap>
deba@1864
   776
  struct BellmanFordWizardDefaultTraits {
deba@1699
   777
    /// \brief The graph type the algorithm runs on. 
deba@1699
   778
    typedef _Graph Graph;
deba@1699
   779
deba@1699
   780
    /// \brief The type of the map that stores the edge lengths.
deba@1699
   781
    ///
deba@1699
   782
    /// The type of the map that stores the edge lengths.
alpar@2260
   783
    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
deba@1699
   784
    typedef _LengthMap LengthMap;
deba@1699
   785
deba@1699
   786
    /// \brief The value type of the length map.
deba@1699
   787
    typedef typename _LengthMap::Value Value;
deba@1699
   788
alpar@2408
   789
    /// \brief Operation traits for Bellman-Ford algorithm.
deba@1699
   790
    ///
deba@1699
   791
    /// It defines the infinity type on the given Value type
deba@1699
   792
    /// and the used operation.
deba@1864
   793
    /// \see BellmanFordDefaultOperationTraits
deba@1864
   794
    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
deba@1699
   795
deba@1699
   796
    /// \brief The type of the map that stores the last
deba@1699
   797
    /// edges of the shortest paths.
deba@1699
   798
    /// 
deba@1699
   799
    /// The type of the map that stores the last
deba@1699
   800
    /// edges of the shortest paths.
alpar@2260
   801
    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
deba@1699
   802
    typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
deba@1699
   803
deba@1699
   804
    /// \brief Instantiates a PredMap.
deba@1699
   805
    /// 
deba@1699
   806
    /// This function instantiates a \ref PredMap. 
deba@1699
   807
    static PredMap *createPredMap(const _Graph &) {
deba@1699
   808
      return new PredMap();
deba@1699
   809
    }
deba@1699
   810
    /// \brief The type of the map that stores the dists of the nodes.
deba@1699
   811
    ///
deba@1699
   812
    /// The type of the map that stores the dists of the nodes.
alpar@2260
   813
    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
deba@1699
   814
    typedef NullMap<typename Graph::Node, Value> DistMap;
deba@1699
   815
    /// \brief Instantiates a DistMap.
deba@1699
   816
    ///
deba@1699
   817
    /// This function instantiates a \ref DistMap. 
deba@1699
   818
    static DistMap *createDistMap(const _Graph &) {
deba@1699
   819
      return new DistMap();
deba@1699
   820
    }
deba@1699
   821
  };
deba@1699
   822
  
deba@1864
   823
  /// \brief Default traits used by \ref BellmanFordWizard
deba@1699
   824
  ///
deba@1864
   825
  /// To make it easier to use BellmanFord algorithm
deba@1699
   826
  /// we have created a wizard class.
deba@1864
   827
  /// This \ref BellmanFordWizard class needs default traits,
deba@1864
   828
  /// as well as the \ref BellmanFord class.
deba@1864
   829
  /// The \ref BellmanFordWizardBase is a class to be the default traits of the
deba@1864
   830
  /// \ref BellmanFordWizard class.
deba@1699
   831
  /// \todo More named parameters are required...
deba@1699
   832
  template<class _Graph,class _LengthMap>
deba@1864
   833
  class BellmanFordWizardBase 
deba@1864
   834
    : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
deba@1699
   835
deba@1864
   836
    typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
deba@1699
   837
  protected:
deba@1699
   838
    /// Type of the nodes in the graph.
deba@1699
   839
    typedef typename Base::Graph::Node Node;
deba@1699
   840
deba@1699
   841
    /// Pointer to the underlying graph.
deba@1699
   842
    void *_graph;
deba@1699
   843
    /// Pointer to the length map
deba@1699
   844
    void *_length;
deba@1699
   845
    ///Pointer to the map of predecessors edges.
deba@1699
   846
    void *_pred;
deba@1699
   847
    ///Pointer to the map of distances.
deba@1699
   848
    void *_dist;
deba@1699
   849
    ///Pointer to the source node.
deba@1699
   850
    Node _source;
deba@1699
   851
deba@1699
   852
    public:
deba@1699
   853
    /// Constructor.
deba@1699
   854
    
deba@1699
   855
    /// This constructor does not require parameters, therefore it initiates
deba@1699
   856
    /// all of the attributes to default values (0, INVALID).
deba@1864
   857
    BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
deba@1699
   858
			   _dist(0), _source(INVALID) {}
deba@1699
   859
deba@1699
   860
    /// Constructor.
deba@1699
   861
    
deba@1699
   862
    /// This constructor requires some parameters,
deba@1699
   863
    /// listed in the parameters list.
deba@1699
   864
    /// Others are initiated to 0.
deba@1699
   865
    /// \param graph is the initial value of  \ref _graph
deba@1699
   866
    /// \param length is the initial value of  \ref _length
deba@1699
   867
    /// \param source is the initial value of  \ref _source
deba@1864
   868
    BellmanFordWizardBase(const _Graph& graph, 
deba@1699
   869
			  const _LengthMap& length, 
deba@1699
   870
			  Node source = INVALID) :
deba@2386
   871
      _graph(reinterpret_cast<void*>(const_cast<_Graph*>(&graph))), 
deba@2386
   872
      _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))), 
deba@2386
   873
      _pred(0), _dist(0), _source(source) {}
deba@1699
   874
deba@1699
   875
  };
deba@1699
   876
  
deba@1864
   877
  /// A class to make the usage of BellmanFord algorithm easier
deba@1699
   878
deba@1864
   879
  /// This class is created to make it easier to use BellmanFord algorithm.
deba@1864
   880
  /// It uses the functions and features of the plain \ref BellmanFord,
deba@1699
   881
  /// but it is much simpler to use it.
deba@1699
   882
  ///
deba@1699
   883
  /// Simplicity means that the way to change the types defined
deba@1699
   884
  /// in the traits class is based on functions that returns the new class
deba@1699
   885
  /// and not on templatable built-in classes.
deba@1864
   886
  /// When using the plain \ref BellmanFord
deba@1699
   887
  /// the new class with the modified type comes from
deba@1699
   888
  /// the original class by using the ::
deba@1864
   889
  /// operator. In the case of \ref BellmanFordWizard only
deba@1699
   890
  /// a function have to be called and it will
deba@1699
   891
  /// return the needed class.
deba@1699
   892
  ///
deba@1699
   893
  /// It does not have own \ref run method. When its \ref run method is called
deba@1864
   894
  /// it initiates a plain \ref BellmanFord class, and calls the \ref 
deba@1864
   895
  /// BellmanFord::run method of it.
deba@1699
   896
  template<class _Traits>
deba@1864
   897
  class BellmanFordWizard : public _Traits {
deba@1699
   898
    typedef _Traits Base;
deba@1699
   899
deba@1699
   900
    ///The type of the underlying graph.
deba@1699
   901
    typedef typename _Traits::Graph Graph;
deba@1699
   902
deba@1699
   903
    typedef typename Graph::Node Node;
deba@1699
   904
    typedef typename Graph::NodeIt NodeIt;
deba@1699
   905
    typedef typename Graph::Edge Edge;
deba@1699
   906
    typedef typename Graph::OutEdgeIt EdgeIt;
deba@1699
   907
    
deba@1699
   908
    ///The type of the map that stores the edge lengths.
deba@1699
   909
    typedef typename _Traits::LengthMap LengthMap;
deba@1699
   910
deba@1699
   911
    ///The type of the length of the edges.
deba@1699
   912
    typedef typename LengthMap::Value Value;
deba@1699
   913
deba@1699
   914
    ///\brief The type of the map that stores the last
deba@1699
   915
    ///edges of the shortest paths.
deba@1699
   916
    typedef typename _Traits::PredMap PredMap;
deba@1699
   917
deba@1699
   918
    ///The type of the map that stores the dists of the nodes.
deba@1699
   919
    typedef typename _Traits::DistMap DistMap;
deba@1699
   920
deba@1699
   921
  public:
deba@1699
   922
    /// Constructor.
deba@1864
   923
    BellmanFordWizard() : _Traits() {}
deba@1699
   924
deba@1699
   925
    /// \brief Constructor that requires parameters.
deba@1699
   926
    ///
deba@1699
   927
    /// Constructor that requires parameters.
deba@1699
   928
    /// These parameters will be the default values for the traits class.
deba@1864
   929
    BellmanFordWizard(const Graph& graph, const LengthMap& length, 
deba@2386
   930
		      Node src = INVALID) 
deba@2386
   931
      : _Traits(graph, length, src) {}
deba@1699
   932
deba@1699
   933
    /// \brief Copy constructor
deba@1864
   934
    BellmanFordWizard(const _Traits &b) : _Traits(b) {}
deba@1699
   935
deba@1864
   936
    ~BellmanFordWizard() {}
deba@1699
   937
deba@1864
   938
    /// \brief Runs BellmanFord algorithm from a given node.
deba@1699
   939
    ///    
deba@1864
   940
    /// Runs BellmanFord algorithm from a given node.
deba@1699
   941
    /// The node can be given by the \ref source function.
deba@1699
   942
    void run() {
deba@1699
   943
      if(Base::_source == INVALID) throw UninitializedParameter();
deba@1864
   944
      BellmanFord<Graph,LengthMap,_Traits> 
deba@2386
   945
	bf(*reinterpret_cast<const Graph*>(Base::_graph), 
deba@2386
   946
           *reinterpret_cast<const LengthMap*>(Base::_length));
deba@2386
   947
      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
deba@2386
   948
      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
deba@1699
   949
      bf.run(Base::_source);
deba@1699
   950
    }
deba@1699
   951
deba@1864
   952
    /// \brief Runs BellmanFord algorithm from the given node.
deba@1699
   953
    ///
deba@1864
   954
    /// Runs BellmanFord algorithm from the given node.
kpeter@2476
   955
    /// \param src is the given source.
deba@2386
   956
    void run(Node src) {
deba@2386
   957
      Base::_source = src;
deba@1699
   958
      run();
deba@1699
   959
    }
deba@1699
   960
deba@1699
   961
    template<class T>
deba@1699
   962
    struct DefPredMapBase : public Base {
deba@1699
   963
      typedef T PredMap;
deba@1699
   964
      static PredMap *createPredMap(const Graph &) { return 0; };
deba@1699
   965
      DefPredMapBase(const _Traits &b) : _Traits(b) {}
deba@1699
   966
    };
deba@1699
   967
    
deba@1699
   968
    ///\brief \ref named-templ-param "Named parameter"
deba@1699
   969
    ///function for setting PredMap type
deba@1699
   970
    ///
deba@1699
   971
    /// \ref named-templ-param "Named parameter"
deba@1699
   972
    ///function for setting PredMap type
deba@1699
   973
    ///
deba@1699
   974
    template<class T>
deba@1864
   975
    BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) 
deba@1699
   976
    {
deba@2386
   977
      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
deba@1864
   978
      return BellmanFordWizard<DefPredMapBase<T> >(*this);
deba@1699
   979
    }
deba@1699
   980
    
deba@1699
   981
    template<class T>
deba@1699
   982
    struct DefDistMapBase : public Base {
deba@1699
   983
      typedef T DistMap;
deba@1699
   984
      static DistMap *createDistMap(const Graph &) { return 0; };
deba@1699
   985
      DefDistMapBase(const _Traits &b) : _Traits(b) {}
deba@1699
   986
    };
deba@1699
   987
    
deba@1699
   988
    ///\brief \ref named-templ-param "Named parameter"
deba@1699
   989
    ///function for setting DistMap type
deba@1699
   990
    ///
deba@1699
   991
    /// \ref named-templ-param "Named parameter"
deba@1699
   992
    ///function for setting DistMap type
deba@1699
   993
    ///
deba@1699
   994
    template<class T>
deba@1864
   995
    BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
deba@2386
   996
      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
deba@1864
   997
      return BellmanFordWizard<DefDistMapBase<T> >(*this);
deba@1699
   998
    }
deba@1710
   999
deba@1710
  1000
    template<class T>
deba@1710
  1001
    struct DefOperationTraitsBase : public Base {
deba@1710
  1002
      typedef T OperationTraits;
deba@1710
  1003
      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
deba@1710
  1004
    };
deba@1710
  1005
    
deba@1710
  1006
    ///\brief \ref named-templ-param "Named parameter"
deba@1710
  1007
    ///function for setting OperationTraits type
deba@1710
  1008
    ///
deba@1710
  1009
    /// \ref named-templ-param "Named parameter"
deba@1710
  1010
    ///function for setting OperationTraits type
deba@1710
  1011
    ///
deba@1710
  1012
    template<class T>
deba@1864
  1013
    BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
deba@1864
  1014
      return BellmanFordWizard<DefDistMapBase<T> >(*this);
deba@1710
  1015
    }
deba@1699
  1016
    
deba@1864
  1017
    /// \brief Sets the source node, from which the BellmanFord algorithm runs.
deba@1699
  1018
    ///
deba@1864
  1019
    /// Sets the source node, from which the BellmanFord algorithm runs.
kpeter@2476
  1020
    /// \param src is the source node.
deba@2386
  1021
    BellmanFordWizard<_Traits>& source(Node src) {
deba@2386
  1022
      Base::_source = src;
deba@1699
  1023
      return *this;
deba@1699
  1024
    }
deba@1699
  1025
    
deba@1699
  1026
  };
deba@1699
  1027
  
deba@1864
  1028
  /// \brief Function type interface for BellmanFord algorithm.
deba@1699
  1029
  ///
deba@2376
  1030
  /// \ingroup shortest_path
deba@1864
  1031
  /// Function type interface for BellmanFord algorithm.
deba@1699
  1032
  ///
deba@1699
  1033
  /// This function also has several \ref named-templ-func-param 
deba@1699
  1034
  /// "named parameters", they are declared as the members of class 
deba@1864
  1035
  /// \ref BellmanFordWizard.
deba@1699
  1036
  /// The following
deba@1699
  1037
  /// example shows how to use these parameters.
alpar@1946
  1038
  ///\code
deba@1864
  1039
  /// bellmanford(g,length,source).predMap(preds).run();
alpar@1946
  1040
  ///\endcode
deba@1864
  1041
  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
deba@1699
  1042
  /// to the end of the parameter list.
deba@1864
  1043
  /// \sa BellmanFordWizard
deba@1864
  1044
  /// \sa BellmanFord
deba@1699
  1045
  template<class _Graph, class _LengthMap>
deba@1864
  1046
  BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
deba@1864
  1047
  bellmanFord(const _Graph& graph,
deba@1699
  1048
	      const _LengthMap& length, 
deba@1699
  1049
	      typename _Graph::Node source = INVALID) {
deba@1864
  1050
    return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
deba@1699
  1051
      (graph, length, source);
deba@1699
  1052
  }
deba@1699
  1053
deba@1699
  1054
} //END OF NAMESPACE LEMON
deba@1699
  1055
deba@1699
  1056
#endif
deba@1699
  1057