1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/dag_shortest_path.h Fri Jan 27 08:17:25 2006 +0000
1.3 @@ -0,0 +1,1082 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/dag_shortest_path.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_DAG_SHORTEST_PATH_H
1.21 +#define LEMON_DAG_SHORTEST_PATH_H
1.22 +
1.23 +///\ingroup flowalgs
1.24 +/// \file
1.25 +/// \brief DagShortestPath algorithm.
1.26 +///
1.27 +
1.28 +#include <lemon/list_graph.h>
1.29 +#include <lemon/invalid.h>
1.30 +#include <lemon/error.h>
1.31 +#include <lemon/maps.h>
1.32 +#include <lemon/topology.h>
1.33 +
1.34 +#include <limits>
1.35 +
1.36 +namespace lemon {
1.37 +
1.38 + /// \brief Default OperationTraits for the DagShortestPath algorithm class.
1.39 + ///
1.40 + /// It defines all computational operations and constants which are
1.41 + /// used in the dag shortest path algorithm. The default implementation
1.42 + /// is based on the numeric_limits class. If the numeric type does not
1.43 + /// have infinity value then the maximum value is used as extremal
1.44 + /// infinity value.
1.45 + template <
1.46 + typename Value,
1.47 + bool has_infinity = std::numeric_limits<Value>::has_infinity>
1.48 + struct DagShortestPathDefaultOperationTraits {
1.49 + /// \brief Gives back the zero value of the type.
1.50 + static Value zero() {
1.51 + return static_cast<Value>(0);
1.52 + }
1.53 + /// \brief Gives back the positive infinity value of the type.
1.54 + static Value infinity() {
1.55 + return std::numeric_limits<Value>::infinity();
1.56 + }
1.57 + /// \brief Gives back the sum of the given two elements.
1.58 + static Value plus(const Value& left, const Value& right) {
1.59 + return left + right;
1.60 + }
1.61 + /// \brief Gives back true only if the first value less than the second.
1.62 + static bool less(const Value& left, const Value& right) {
1.63 + return left < right;
1.64 + }
1.65 + };
1.66 +
1.67 + template <typename Value>
1.68 + struct DagShortestPathDefaultOperationTraits<Value, false> {
1.69 + static Value zero() {
1.70 + return static_cast<Value>(0);
1.71 + }
1.72 + static Value infinity() {
1.73 + return std::numeric_limits<Value>::max();
1.74 + }
1.75 + static Value plus(const Value& left, const Value& right) {
1.76 + if (left == infinity() || right == infinity()) return infinity();
1.77 + return left + right;
1.78 + }
1.79 + static bool less(const Value& left, const Value& right) {
1.80 + return left < right;
1.81 + }
1.82 + };
1.83 +
1.84 + /// \brief Default traits class of DagShortestPath class.
1.85 + ///
1.86 + /// Default traits class of DagShortestPath class.
1.87 + /// \param _Graph Graph type.
1.88 + /// \param _LegthMap Type of length map.
1.89 + template<class _Graph, class _LengthMap>
1.90 + struct DagShortestPathDefaultTraits {
1.91 + /// The graph type the algorithm runs on.
1.92 + typedef _Graph Graph;
1.93 +
1.94 + /// \brief The type of the map that stores the edge lengths.
1.95 + ///
1.96 + /// The type of the map that stores the edge lengths.
1.97 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.98 + typedef _LengthMap LengthMap;
1.99 +
1.100 + // The type of the length of the edges.
1.101 + typedef typename _LengthMap::Value Value;
1.102 +
1.103 + /// \brief Operation traits for dag shortest path algorithm.
1.104 + ///
1.105 + /// It defines the infinity type on the given Value type
1.106 + /// and the used operation.
1.107 + /// \see DagShortestPathDefaultOperationTraits
1.108 + typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
1.109 +
1.110 + /// \brief The type of the map that stores the last edges of the
1.111 + /// shortest paths.
1.112 + ///
1.113 + /// The type of the map that stores the last
1.114 + /// edges of the shortest paths.
1.115 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.116 + ///
1.117 + typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
1.118 +
1.119 + /// \brief Instantiates a PredMap.
1.120 + ///
1.121 + /// This function instantiates a \ref PredMap.
1.122 + /// \param G is the graph, to which we would like to define the PredMap.
1.123 + /// \todo The graph alone may be insufficient for the initialization
1.124 + static PredMap *createPredMap(const _Graph& graph) {
1.125 + return new PredMap(graph);
1.126 + }
1.127 +
1.128 + /// \brief The type of the map that stores the dists of the nodes.
1.129 + ///
1.130 + /// The type of the map that stores the dists of the nodes.
1.131 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.132 + ///
1.133 + typedef typename Graph::template NodeMap<typename _LengthMap::Value>
1.134 + DistMap;
1.135 +
1.136 + /// \brief Instantiates a DistMap.
1.137 + ///
1.138 + /// This function instantiates a \ref DistMap.
1.139 + /// \param G is the graph, to which we would like to define the
1.140 + /// \ref DistMap
1.141 + static DistMap *createDistMap(const _Graph& graph) {
1.142 + return new DistMap(graph);
1.143 + }
1.144 +
1.145 + };
1.146 +
1.147 + /// \brief Inverse OperationTraits for the DagShortestPath algorithm class.
1.148 + ///
1.149 + /// It defines all computational operations and constants which are
1.150 + /// used in the dag shortest path algorithm. It is the inverse of
1.151 + /// \ref DagShortestPathDefaultOperationTraits, so it can be used to
1.152 + /// calculate the longest path. The default implementation
1.153 + /// is based on the numeric_limits class. If the numeric type does not
1.154 + /// have infinity value then the minimum value is used as extremal
1.155 + /// infinity value.
1.156 + template <
1.157 + typename Value,
1.158 + bool has_infinity = std::numeric_limits<Value>::has_infinity>
1.159 + struct DagLongestPathOperationTraits {
1.160 + /// \brief Gives back the zero value of the type.
1.161 + static Value zero() {
1.162 + return static_cast<Value>(0);
1.163 + }
1.164 + /// \brief Gives back the negative infinity value of the type.
1.165 + static Value infinity() {
1.166 + return -(std::numeric_limits<Value>::infinity());
1.167 + }
1.168 + /// \brief Gives back the sum of the given two elements.
1.169 + static Value plus(const Value& left, const Value& right) {
1.170 + return left + right;
1.171 + }
1.172 + /// \brief Gives back true only if the first value less than the second.
1.173 + static bool less(const Value& left, const Value& right) {
1.174 + return left > right;
1.175 + }
1.176 + };
1.177 +
1.178 + template <typename Value>
1.179 + struct DagLongestPathOperationTraits<Value, false> {
1.180 + static Value zero() {
1.181 + return static_cast<Value>(0);
1.182 + }
1.183 + static Value infinity() {
1.184 + return std::numeric_limits<Value>::min();
1.185 + }
1.186 + static Value plus(const Value& left, const Value& right) {
1.187 + if (left == infinity() || right == infinity()) return infinity();
1.188 + return left + right;
1.189 + }
1.190 + static bool less(const Value& left, const Value& right) {
1.191 + return left > right;
1.192 + }
1.193 + };
1.194 +
1.195 + /// \brief Inverse traits class of DagShortestPath class.
1.196 + ///
1.197 + /// Inverse traits class of DagShortestPath class.
1.198 + /// \param _Graph Graph type.
1.199 + /// \param _LegthMap Type of length map.
1.200 + template<class _Graph, class _LengthMap>
1.201 + struct DagLongestPathTraits {
1.202 + /// The graph type the algorithm runs on.
1.203 + typedef _Graph Graph;
1.204 +
1.205 + /// \brief The type of the map that stores the edge lengths.
1.206 + ///
1.207 + /// The type of the map that stores the edge lengths.
1.208 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.209 + typedef _LengthMap LengthMap;
1.210 +
1.211 + // The type of the length of the edges.
1.212 + typedef typename _LengthMap::Value Value;
1.213 +
1.214 + /// \brief Inverse operation traits for dag shortest path algorithm.
1.215 + ///
1.216 + /// It defines the infinity type on the given Value type
1.217 + /// and the used operation.
1.218 + /// \see DagLongestPathOperationTraits
1.219 + typedef DagLongestPathOperationTraits<Value> OperationTraits;
1.220 +
1.221 + /// \brief The type of the map that stores the last edges of the
1.222 + /// longest paths.
1.223 + ///
1.224 + /// The type of the map that stores the last
1.225 + /// edges of the longest paths.
1.226 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.227 + ///
1.228 + typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
1.229 +
1.230 + /// \brief Instantiates a PredMap.
1.231 + ///
1.232 + /// This function instantiates a \ref PredMap.
1.233 + /// \param G is the graph, to which we would like to define the PredMap.
1.234 + /// \todo The graph alone may be insufficient for the initialization
1.235 + static PredMap *createPredMap(const _Graph& graph) {
1.236 + return new PredMap(graph);
1.237 + }
1.238 +
1.239 + /// \brief The type of the map that stores the dists of the nodes.
1.240 + ///
1.241 + /// The type of the map that stores the dists of the nodes.
1.242 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.243 + ///
1.244 + typedef typename Graph::template NodeMap<typename _LengthMap::Value>
1.245 + DistMap;
1.246 +
1.247 + /// \brief Instantiates a DistMap.
1.248 + ///
1.249 + /// This function instantiates a \ref DistMap.
1.250 + /// \param G is the graph, to which we would like to define the
1.251 + /// \ref DistMap
1.252 + static DistMap *createDistMap(const _Graph& graph) {
1.253 + return new DistMap(graph);
1.254 + }
1.255 +
1.256 + };
1.257 +
1.258 +
1.259 + /// \brief %DagShortestPath algorithm class.
1.260 + ///
1.261 + /// \ingroup flowalgs
1.262 + /// This class provides an efficient implementation of a Dag sortest path
1.263 + /// searching algorithm. The edge lengths are passed to the algorithm
1.264 + /// using a \ref concept::ReadMap "ReadMap", so it is easy to change it
1.265 + /// to any kind of length.
1.266 + ///
1.267 + /// The complexity of the algorithm is O(n + e).
1.268 + ///
1.269 + /// The type of the length is determined by the
1.270 + /// \ref concept::ReadMap::Value "Value" of the length map.
1.271 + ///
1.272 + /// \param _Graph The graph type the algorithm runs on. The default value
1.273 + /// is \ref ListGraph. The value of _Graph is not used directly by
1.274 + /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
1.275 + /// \param _LengthMap This read-only EdgeMap determines the lengths of the
1.276 + /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
1.277 + /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
1.278 + /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
1.279 + /// \param _Traits Traits class to set various data types used by the
1.280 + /// algorithm. The default traits class is \ref DagShortestPathDefaultTraits
1.281 + /// "DagShortestPathDefaultTraits<_Graph,_LengthMap>". See \ref
1.282 + /// DagShortestPathDefaultTraits for the documentation of a DagShortestPath traits
1.283 + /// class.
1.284 + ///
1.285 + /// \author Balazs Attila Mihaly (based on Balazs Dezso's work)
1.286 +
1.287 +#ifdef DOXYGEN
1.288 + template <typename _Graph, typename _LengthMap, typename _Traits>
1.289 +#else
1.290 + template <typename _Graph=ListGraph,
1.291 + typename _LengthMap=typename _Graph::template EdgeMap<int>,
1.292 + typename _Traits=DagShortestPathDefaultTraits<_Graph,_LengthMap> >
1.293 +#endif
1.294 + class DagShortestPath {
1.295 + public:
1.296 +
1.297 + /// \brief \ref Exception for uninitialized parameters.
1.298 + ///
1.299 + /// This error represents problems in the initialization
1.300 + /// of the parameters of the algorithms.
1.301 +
1.302 + class UninitializedParameter : public lemon::UninitializedParameter {
1.303 + public:
1.304 + virtual const char* exceptionName() const {
1.305 + return "lemon::DagShortestPath::UninitializedParameter";
1.306 + }
1.307 + };
1.308 +
1.309 + typedef _Traits Traits;
1.310 + ///The type of the underlying graph.
1.311 + typedef typename _Traits::Graph Graph;
1.312 +
1.313 + typedef typename Graph::Node Node;
1.314 + typedef typename Graph::NodeIt NodeIt;
1.315 + typedef typename Graph::Edge Edge;
1.316 + typedef typename Graph::EdgeIt EdgeIt;
1.317 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.318 +
1.319 + /// \brief The type of the length of the edges.
1.320 + typedef typename _Traits::LengthMap::Value Value;
1.321 + /// \brief The type of the map that stores the edge lengths.
1.322 + typedef typename _Traits::LengthMap LengthMap;
1.323 + /// \brief The type of the map that stores the last
1.324 + /// edges of the shortest paths.
1.325 + typedef typename _Traits::PredMap PredMap;
1.326 + /// \brief The type of the map that stores the dists of the nodes.
1.327 + typedef typename _Traits::DistMap DistMap;
1.328 + /// \brief The operation traits.
1.329 + typedef typename _Traits::OperationTraits OperationTraits;
1.330 + /// \brief The Node weight map.
1.331 + typedef typename Graph::NodeMap<Value> WeightMap;
1.332 + private:
1.333 + /// Pointer to the underlying graph
1.334 + const Graph *graph;
1.335 + /// Pointer to the length map
1.336 + const LengthMap *length;
1.337 + ///Pointer to the map of predecessors edges
1.338 + PredMap *_pred;
1.339 + ///Indicates if \ref _pred is locally allocated (\c true) or not
1.340 + bool local_pred;
1.341 + ///Pointer to the map of distances
1.342 + DistMap *_dist;
1.343 + ///Indicates if \ref _dist is locally allocated (\c true) or not
1.344 + bool local_dist;
1.345 + ///Process step counter
1.346 + unsigned int _process_step;
1.347 +
1.348 + std::vector<Node> _node_order;
1.349 +
1.350 + /// Creates the maps if necessary.
1.351 + void create_maps() {
1.352 + if(!_pred) {
1.353 + local_pred = true;
1.354 + _pred = Traits::createPredMap(*graph);
1.355 + }
1.356 + if(!_dist) {
1.357 + local_dist = true;
1.358 + _dist = Traits::createDistMap(*graph);
1.359 + }
1.360 + }
1.361 +
1.362 + public :
1.363 +
1.364 + typedef DagShortestPath Create;
1.365 +
1.366 + /// \name Named template parameters
1.367 +
1.368 + ///@{
1.369 +
1.370 + template <class T>
1.371 + struct DefPredMapTraits : public Traits {
1.372 + typedef T PredMap;
1.373 + static PredMap *createPredMap(const Graph&) {
1.374 + throw UninitializedParameter();
1.375 + }
1.376 + };
1.377 +
1.378 + /// \brief \ref named-templ-param "Named parameter" for setting PredMap
1.379 + /// type
1.380 + /// \ref named-templ-param "Named parameter" for setting PredMap type
1.381 + ///
1.382 + template <class T>
1.383 + struct DefPredMap {
1.384 + typedef DagShortestPath< Graph, LengthMap, DefPredMapTraits<T> > Create;
1.385 + };
1.386 +
1.387 + template <class T>
1.388 + struct DefDistMapTraits : public Traits {
1.389 + typedef T DistMap;
1.390 + static DistMap *createDistMap(const Graph& graph) {
1.391 + throw UninitializedParameter();
1.392 + }
1.393 + };
1.394 +
1.395 + /// \brief \ref named-templ-param "Named parameter" for setting DistMap
1.396 + /// type
1.397 + ///
1.398 + /// \ref named-templ-param "Named parameter" for setting DistMap type
1.399 + ///
1.400 + template <class T>
1.401 + struct DefDistMap
1.402 + : public DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > {
1.403 + typedef DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > Create;
1.404 + };
1.405 +
1.406 + template <class T>
1.407 + struct DefOperationTraitsTraits : public Traits {
1.408 + typedef T OperationTraits;
1.409 + };
1.410 +
1.411 + /// \brief \ref named-templ-param "Named parameter" for setting
1.412 + /// OperationTraits type
1.413 + ///
1.414 + /// \ref named-templ-param "Named parameter" for setting OperationTraits
1.415 + /// type
1.416 + template <class T>
1.417 + struct DefOperationTraits
1.418 + : public DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> > {
1.419 + typedef DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> >
1.420 + Create;
1.421 + };
1.422 +
1.423 + ///@}
1.424 +
1.425 + protected:
1.426 +
1.427 + DagShortestPath() {}
1.428 +
1.429 + public:
1.430 +
1.431 + /// \brief Constructor.
1.432 + ///
1.433 + /// \param _graph the graph the algorithm will run on.
1.434 + /// \param _length the length map used by the algorithm.
1.435 + DagShortestPath(const Graph& _graph, const LengthMap& _length) :
1.436 + graph(&_graph), length(&_length),
1.437 + _pred(0), local_pred(false),
1.438 + _dist(0), local_dist(false){}
1.439 +
1.440 + /// \brief Constructor with node weight map.
1.441 + ///
1.442 + /// \param _graph the graph the algorithm will run on.
1.443 + /// \param _length the length map used by the algorithm.
1.444 + /// The NodeMap _length will be used as the weight map.
1.445 + /// Each edge will have the weight of its target node.
1.446 + DagShortestPath(const Graph& _graph, const WeightMap& _length) :
1.447 + graph(&_graph),
1.448 + _pred(0), local_pred(false),
1.449 + _dist(0), local_dist(false){
1.450 + length=new LengthMap(_graph);
1.451 + _dist=new DistMap(_graph);
1.452 + for(EdgeIt eit(_graph);eit!=INVALID;++eit)
1.453 + (const_cast<LengthMap*>(length))->set(eit,_length[_graph.target(eit)]);
1.454 + }
1.455 +
1.456 + ///Destructor.
1.457 + ~DagShortestPath() {
1.458 + if(local_pred) delete _pred;
1.459 + if(local_dist) delete _dist;
1.460 + }
1.461 +
1.462 + /// \brief Sets the length map.
1.463 + ///
1.464 + /// Sets the length map.
1.465 + /// \return \c (*this)
1.466 + DagShortestPath &lengthMap(const LengthMap &m) {
1.467 + length = &m;
1.468 + return *this;
1.469 + }
1.470 +
1.471 + /// \brief Sets the map storing the predecessor edges.
1.472 + ///
1.473 + /// Sets the map storing the predecessor edges.
1.474 + /// If you don't use this function before calling \ref run(),
1.475 + /// it will allocate one. The destuctor deallocates this
1.476 + /// automatically allocated map, of course.
1.477 + /// \return \c (*this)
1.478 + DagShortestPath &predMap(PredMap &m) {
1.479 + if(local_pred) {
1.480 + delete _pred;
1.481 + local_pred=false;
1.482 + }
1.483 + _pred = &m;
1.484 + return *this;
1.485 + }
1.486 +
1.487 + /// \brief Sets the map storing the distances calculated by the algorithm.
1.488 + ///
1.489 + /// Sets the map storing the distances calculated by the algorithm.
1.490 + /// If you don't use this function before calling \ref run(),
1.491 + /// it will allocate one. The destuctor deallocates this
1.492 + /// automatically allocated map, of course.
1.493 + /// \return \c (*this)
1.494 + DagShortestPath &distMap(DistMap &m) {
1.495 + if(local_dist) {
1.496 + delete _dist;
1.497 + local_dist=false;
1.498 + }
1.499 + _dist = &m;
1.500 + return *this;
1.501 + }
1.502 +
1.503 + /// \name Execution control
1.504 + /// The simplest way to execute the algorithm is to use
1.505 + /// one of the member functions called \c run(...)
1.506 + /// \n
1.507 + /// If you need more control on the execution,
1.508 + /// first you must call \ref init(...), then you can add several source
1.509 + /// nodes with \ref addSource().
1.510 + /// Finally \ref start() will perform the actual path computation.
1.511 + /// Some functions have an alternative form (\ref checkedInit(...),
1.512 + /// \ref checkedRun(...)) which also verifies if the graph given in the
1.513 + /// constructor is a dag.
1.514 +
1.515 + ///@{
1.516 +
1.517 + /// \brief Initializes the internal data structures.
1.518 + ///
1.519 + /// Initializes the internal data structures.
1.520 + void init(const Value value = OperationTraits::infinity()) {
1.521 + typedef typename Graph::template NodeMap<int> NodeOrderMap;
1.522 + _process_step=0;
1.523 + NodeOrderMap node_order(*graph);
1.524 + topologicalSort(*graph,node_order);
1.525 + _node_order.resize(countNodes(*graph),INVALID);
1.526 + create_maps();
1.527 + for (NodeIt it(*graph); it != INVALID; ++it) {
1.528 + _node_order[node_order[it]]=it;
1.529 + _pred->set(it, INVALID);
1.530 + _dist->set(it, value);
1.531 + }
1.532 + }
1.533 +
1.534 + /// \brief Initializes the internal data structures
1.535 + /// with a given topological sort (NodeMap).
1.536 + ///
1.537 + /// Initializes the internal data structures
1.538 + /// with a given topological sort (NodeMap).
1.539 + void init(const typename Graph::template NodeMap<int>& node_order,
1.540 + const Value value = OperationTraits::infinity()) {
1.541 + _process_step=0;
1.542 + _node_order.resize(countNodes(*graph),INVALID);
1.543 + create_maps();
1.544 + for (NodeIt it(*graph); it != INVALID; ++it) {
1.545 + _node_order[node_order[it]]=it;
1.546 + _pred->set(it, INVALID);
1.547 + _dist->set(it, value);
1.548 + }
1.549 + }
1.550 +
1.551 + /// \brief Initializes the internal data structures
1.552 + /// with a given topological sort (std::vector).
1.553 + ///
1.554 + /// Initializes the internal data structures
1.555 + /// with a given topological sort (std::vector).
1.556 + void init(const std::vector<Node>& node_order,
1.557 + const Value value = OperationTraits::infinity()) {
1.558 + _process_step=0;
1.559 + _node_order=node_order;
1.560 + create_maps();
1.561 + for (NodeIt it(*graph); it != INVALID; ++it) {
1.562 + _pred->set(it, INVALID);
1.563 + _dist->set(it, value);
1.564 + }
1.565 + }
1.566 +
1.567 + /// \brief Initializes the internal data structures. It also checks if the graph is dag.
1.568 + ///
1.569 + /// Initializes the internal data structures. It also checks if the graph is dag.
1.570 + /// \return true if the graph (given in the constructor) is dag, false otherwise.
1.571 + bool checkedInit(const Value value = OperationTraits::infinity()) {
1.572 + typedef typename Graph::template NodeMap<int> NodeOrderMap;
1.573 + NodeOrderMap node_order(*graph);
1.574 + if(!checkedTopologicalSort(*graph,node_order))return false;
1.575 + init(node_order,value);
1.576 + return true;
1.577 + }
1.578 +
1.579 + /// \brief Initializes the internal data structures with a given
1.580 + /// topological sort (NodeMap). It also checks if the graph is dag.
1.581 + ///
1.582 + /// Initializes the internal data structures with a given
1.583 + /// topological sort (NodeMap). It also checks if the graph is dag.
1.584 + /// \return true if the graph (given in the constructor) is dag, false otherwise.
1.585 + bool checkedInit(const typename Graph::template NodeMap<int>& node_order,
1.586 + const Value value = OperationTraits::infinity()) {
1.587 + for(NodeIt it(*graph);it!=INVALID;++it){
1.588 + for(OutEdgeIt oeit(*graph,it);oeit!=INVALID;++oeit){
1.589 + if(node_order[graph->target(oeit)]<node_order[it])return false;
1.590 + }
1.591 + }
1.592 + init(node_order,value);
1.593 + return true;
1.594 + }
1.595 +
1.596 + /// \brief Initializes the internal data structures with a given
1.597 + /// topological sort (std::vector). It also checks if the graph is dag.
1.598 + ///
1.599 + /// Initializes the internal data structures with a given
1.600 + /// topological sort (std::vector). It also checks if the graph is dag.
1.601 + /// \return true if the graph (given in the constructor) is dag, false otherwise.
1.602 + bool checkedInit(const std::vector<Node>& node_order,
1.603 + const Value value = OperationTraits::infinity()) {
1.604 + typedef typename Graph::template NodeMap<bool> BoolNodeMap;
1.605 + BoolNodeMap _processed(*graph,false);
1.606 + for(unsigned int i=0;i<_node_order.size();++i){
1.607 + _processed[node_order[i]]=true;
1.608 + for(OutEdgeIt oeit(*graph,node_order[i]);oeit!=INVALID;++oeit){
1.609 + if(_processed[graph->target(oeit)])return false;
1.610 + }
1.611 + }
1.612 + init(node_order,value);
1.613 + return true;
1.614 + }
1.615 +
1.616 + /// \brief Adds a new source node.
1.617 + ///
1.618 + /// The optional second parameter is the initial distance of the node.
1.619 + /// It just sets the distance of the node to the given value.
1.620 + void addSource(Node source, Value dst = OperationTraits::zero()) {
1.621 + if((*_dist)[source] != dst){
1.622 + _dist->set(source, dst);
1.623 + }
1.624 + }
1.625 +
1.626 + /// \brief Executes one step from the dag shortest path algorithm.
1.627 + ///
1.628 + /// If the algoritm calculated the distances in the previous step
1.629 + /// strictly for all at most k length paths then it will calculate the
1.630 + /// distances strictly for all at most k + 1 length paths. With k
1.631 + /// iteration this function calculates the at most k length paths.
1.632 + ///\pre the queue is not empty
1.633 + ///\return the currently processed node
1.634 + Node processNextNode() {
1.635 + if(reached(_node_order[_process_step])){
1.636 + for (OutEdgeIt it(*graph, _node_order[_process_step]); it != INVALID; ++it) {
1.637 + Node target = graph->target(it);
1.638 + Value relaxed =
1.639 + OperationTraits::plus((*_dist)[_node_order[_process_step]], (*length)[it]);
1.640 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.641 + _pred->set(target, it);
1.642 + _dist->set(target, relaxed);
1.643 + }
1.644 + }
1.645 + }
1.646 + ++_process_step;
1.647 + return _node_order[_process_step-1];
1.648 + }
1.649 +
1.650 + ///\brief Returns \c false if there are nodes
1.651 + ///to be processed in the queue
1.652 + ///
1.653 + ///Returns \c false if there are nodes
1.654 + ///to be processed in the queue
1.655 + bool emptyQueue() { return _node_order.size()-1==_process_step; }
1.656 +
1.657 + ///\brief Returns the number of the nodes to be processed.
1.658 + ///
1.659 + ///Returns the number of the nodes to be processed in the queue.
1.660 + int queueSize() { return _node_order.size()-1-_process_step; }
1.661 +
1.662 + /// \brief Executes the algorithm.
1.663 + ///
1.664 + /// \pre init() must be called and at least one node should be added
1.665 + /// with addSource() before using this function.
1.666 + ///
1.667 + /// This method runs the %DagShortestPath algorithm from the root node(s)
1.668 + /// in order to compute the shortest path to each node. The algorithm
1.669 + /// computes
1.670 + /// - The shortest path tree.
1.671 + /// - The distance of each node from the root(s).
1.672 + void start() {
1.673 + while(!emptyQueue()) {
1.674 + processNextNode();
1.675 + }
1.676 + }
1.677 +
1.678 + /// \brief Runs %DagShortestPath algorithm from node \c s.
1.679 + ///
1.680 + /// This method runs the %DagShortestPath algorithm from a root node \c s
1.681 + /// in order to compute the shortest path to each node. The algorithm
1.682 + /// computes
1.683 + /// - The shortest path tree.
1.684 + /// - The distance of each node from the root.
1.685 + ///
1.686 + /// \note d.run(s) is just a shortcut of the following code.
1.687 + /// \code
1.688 + /// d.init();
1.689 + /// d.addSource(s);
1.690 + /// d.start();
1.691 + /// \endcode
1.692 + void run(Node s) {
1.693 + init();
1.694 + addSource(s);
1.695 + start();
1.696 + }
1.697 +
1.698 + /// \brief Runs %DagShortestPath algorithm from node \c s.
1.699 + /// It also checks if the graph is a dag.
1.700 + ///
1.701 + /// This method runs the %DagShortestPath algorithm from a root node \c s
1.702 + /// in order to compute the shortest path to each node. The algorithm
1.703 + /// computes
1.704 + /// - The shortest path tree.
1.705 + /// - The distance of each node from the root.
1.706 + /// The algorithm checks if the graph given int the constructor is a dag.
1.707 + bool checkedRun(Node s) {
1.708 + if(!checkedInit())return false;
1.709 + addSource(s);
1.710 + start();
1.711 + return true;
1.712 + }
1.713 +
1.714 + ///@}
1.715 +
1.716 + /// \name Query Functions
1.717 + /// The result of the %DagShortestPath algorithm can be obtained using these
1.718 + /// functions.\n
1.719 + /// Before the use of these functions,
1.720 + /// either run() or start() must be called.
1.721 +
1.722 + ///@{
1.723 +
1.724 + /// \brief Copies the shortest path to \c t into \c p
1.725 + ///
1.726 + /// This function copies the shortest path to \c t into \c p.
1.727 + /// If it \c t is a source itself or unreachable, then it does not
1.728 + /// alter \c p.
1.729 + ///
1.730 + /// \return Returns \c true if a path to \c t was actually copied to \c p,
1.731 + /// \c false otherwise.
1.732 + /// \sa DirPath
1.733 + template <typename Path>
1.734 + bool getPath(Path &p, Node t) {
1.735 + if(reached(t)) {
1.736 + p.clear();
1.737 + typename Path::Builder b(p);
1.738 + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
1.739 + b.pushFront(predEdge(t));
1.740 + b.commit();
1.741 + return true;
1.742 + }
1.743 + return false;
1.744 + }
1.745 +
1.746 + /// \brief The distance of a node from the root.
1.747 + ///
1.748 + /// Returns the distance of a node from the root.
1.749 + /// \pre \ref run() must be called before using this function.
1.750 + /// \warning If node \c v in unreachable from the root the return value
1.751 + /// of this funcion is undefined.
1.752 + Value dist(Node v) const { return (*_dist)[v]; }
1.753 +
1.754 + /// \brief Returns the 'previous edge' of the shortest path tree.
1.755 + ///
1.756 + /// For a node \c v it returns the 'previous edge' of the shortest path
1.757 + /// tree, i.e. it returns the last edge of a shortest path from the root
1.758 + /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
1.759 + /// if \c v=s. The shortest path tree used here is equal to the shortest
1.760 + /// path tree used in \ref predNode().
1.761 + /// \pre \ref run() must be called before using
1.762 + /// this function.
1.763 + Edge predEdge(Node v) const { return (*_pred)[v]; }
1.764 +
1.765 + /// \brief Returns the 'previous node' of the shortest path tree.
1.766 + ///
1.767 + /// For a node \c v it returns the 'previous node' of the shortest path
1.768 + /// tree, i.e. it returns the last but one node from a shortest path from
1.769 + /// the root to \c /v. It is INVALID if \c v is unreachable from the root
1.770 + /// or if \c v=s. The shortest path tree used here is equal to the
1.771 + /// shortest path tree used in \ref predEdge(). \pre \ref run() must be
1.772 + /// called before using this function.
1.773 + Node predNode(Node v) const {
1.774 + return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
1.775 + }
1.776 +
1.777 + /// \brief Returns a reference to the NodeMap of distances.
1.778 + ///
1.779 + /// Returns a reference to the NodeMap of distances. \pre \ref run() must
1.780 + /// be called before using this function.
1.781 + const DistMap &distMap() const { return *_dist;}
1.782 +
1.783 + /// \brief Returns a reference to the shortest path tree map.
1.784 + ///
1.785 + /// Returns a reference to the NodeMap of the edges of the
1.786 + /// shortest path tree.
1.787 + /// \pre \ref run() must be called before using this function.
1.788 + const PredMap &predMap() const { return *_pred; }
1.789 +
1.790 + /// \brief Checks if a node is reachable from the root.
1.791 + ///
1.792 + /// Returns \c true if \c v is reachable from the root.
1.793 + /// \pre \ref run() must be called before using this function.
1.794 + ///
1.795 + bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
1.796 +
1.797 + ///@}
1.798 + };
1.799 +
1.800 + /// \brief Default traits class of DagShortestPath function.
1.801 + ///
1.802 + /// Default traits class of DagShortestPath function.
1.803 + /// \param _Graph Graph type.
1.804 + /// \param _LengthMap Type of length map.
1.805 + template <typename _Graph, typename _LengthMap>
1.806 + struct DagShortestPathWizardDefaultTraits {
1.807 + /// \brief The graph type the algorithm runs on.
1.808 + typedef _Graph Graph;
1.809 +
1.810 + /// \brief The type of the map that stores the edge lengths.
1.811 + ///
1.812 + /// The type of the map that stores the edge lengths.
1.813 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.814 + typedef _LengthMap LengthMap;
1.815 +
1.816 + /// \brief The value type of the length map.
1.817 + typedef typename _LengthMap::Value Value;
1.818 +
1.819 + /// \brief Operation traits for dag shortest path algorithm.
1.820 + ///
1.821 + /// It defines the infinity type on the given Value type
1.822 + /// and the used operation.
1.823 + /// \see DagShortestPathDefaultOperationTraits
1.824 + typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
1.825 +
1.826 + /// \brief The type of the map that stores the last
1.827 + /// edges of the shortest paths.
1.828 + ///
1.829 + /// The type of the map that stores the last
1.830 + /// edges of the shortest paths.
1.831 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.832 + typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
1.833 +
1.834 + /// \brief Instantiates a PredMap.
1.835 + ///
1.836 + /// This function instantiates a \ref PredMap.
1.837 + static PredMap *createPredMap(const _Graph &) {
1.838 + return new PredMap();
1.839 + }
1.840 + /// \brief The type of the map that stores the dists of the nodes.
1.841 + ///
1.842 + /// The type of the map that stores the dists of the nodes.
1.843 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.844 + typedef NullMap<typename Graph::Node, Value> DistMap;
1.845 + /// \brief Instantiates a DistMap.
1.846 + ///
1.847 + /// This function instantiates a \ref DistMap.
1.848 + static DistMap *createDistMap(const _Graph &) {
1.849 + return new DistMap();
1.850 + }
1.851 + };
1.852 +
1.853 + /// \brief Default traits used by \ref DagShortestPathWizard
1.854 + ///
1.855 + /// To make it easier to use DagShortestPath algorithm
1.856 + /// we have created a wizard class.
1.857 + /// This \ref DagShortestPathWizard class needs default traits,
1.858 + /// as well as the \ref DagShortestPath class.
1.859 + /// The \ref DagShortestPathWizardBase is a class to be the default traits of the
1.860 + /// \ref DagShortestPathWizard class.
1.861 + /// \todo More named parameters are required...
1.862 + template<class _Graph,class _LengthMap>
1.863 + class DagShortestPathWizardBase
1.864 + : public DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> {
1.865 +
1.866 + typedef DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> Base;
1.867 + protected:
1.868 + /// Type of the nodes in the graph.
1.869 + typedef typename Base::Graph::Node Node;
1.870 +
1.871 + /// Pointer to the underlying graph.
1.872 + void *_graph;
1.873 + /// Pointer to the length map
1.874 + void *_length;
1.875 + ///Pointer to the map of predecessors edges.
1.876 + void *_pred;
1.877 + ///Pointer to the map of distances.
1.878 + void *_dist;
1.879 + ///Pointer to the source node.
1.880 + Node _source;
1.881 +
1.882 + public:
1.883 + /// Constructor.
1.884 +
1.885 + /// This constructor does not require parameters, therefore it initiates
1.886 + /// all of the attributes to default values (0, INVALID).
1.887 + DagShortestPathWizardBase() : _graph(0), _length(0), _pred(0),
1.888 + _dist(0), _source(INVALID) {}
1.889 +
1.890 + /// Constructor.
1.891 +
1.892 + /// This constructor requires some parameters,
1.893 + /// listed in the parameters list.
1.894 + /// Others are initiated to 0.
1.895 + /// \param graph is the initial value of \ref _graph
1.896 + /// \param length is the initial value of \ref _length
1.897 + /// \param source is the initial value of \ref _source
1.898 + DagShortestPathWizardBase(const _Graph& graph,
1.899 + const _LengthMap& length,
1.900 + Node source = INVALID) :
1.901 + _graph((void *)&graph), _length((void *)&length), _pred(0),
1.902 + _dist(0), _source(source) {}
1.903 +
1.904 + };
1.905 +
1.906 + /// A class to make the usage of DagShortestPath algorithm easier
1.907 +
1.908 + /// This class is created to make it easier to use DagShortestPath algorithm.
1.909 + /// It uses the functions and features of the plain \ref DagShortestPath,
1.910 + /// but it is much simpler to use it.
1.911 + ///
1.912 + /// Simplicity means that the way to change the types defined
1.913 + /// in the traits class is based on functions that returns the new class
1.914 + /// and not on templatable built-in classes.
1.915 + /// When using the plain \ref DagShortestPath
1.916 + /// the new class with the modified type comes from
1.917 + /// the original class by using the ::
1.918 + /// operator. In the case of \ref DagShortestPathWizard only
1.919 + /// a function have to be called and it will
1.920 + /// return the needed class.
1.921 + ///
1.922 + /// It does not have own \ref run method. When its \ref run method is called
1.923 + /// it initiates a plain \ref DagShortestPath class, and calls the \ref
1.924 + /// DagShortestPath::run() method of it.
1.925 + template<class _Traits>
1.926 + class DagShortestPathWizard : public _Traits {
1.927 + typedef _Traits Base;
1.928 +
1.929 + ///The type of the underlying graph.
1.930 + typedef typename _Traits::Graph Graph;
1.931 +
1.932 + typedef typename Graph::Node Node;
1.933 + typedef typename Graph::NodeIt NodeIt;
1.934 + typedef typename Graph::Edge Edge;
1.935 + typedef typename Graph::OutEdgeIt EdgeIt;
1.936 +
1.937 + ///The type of the map that stores the edge lengths.
1.938 + typedef typename _Traits::LengthMap LengthMap;
1.939 +
1.940 + ///The type of the length of the edges.
1.941 + typedef typename LengthMap::Value Value;
1.942 +
1.943 + ///\brief The type of the map that stores the last
1.944 + ///edges of the shortest paths.
1.945 + typedef typename _Traits::PredMap PredMap;
1.946 +
1.947 + ///The type of the map that stores the dists of the nodes.
1.948 + typedef typename _Traits::DistMap DistMap;
1.949 +
1.950 + public:
1.951 + /// Constructor.
1.952 + DagShortestPathWizard() : _Traits() {}
1.953 +
1.954 + /// \brief Constructor that requires parameters.
1.955 + ///
1.956 + /// Constructor that requires parameters.
1.957 + /// These parameters will be the default values for the traits class.
1.958 + DagShortestPathWizard(const Graph& graph, const LengthMap& length,
1.959 + Node source = INVALID)
1.960 + : _Traits(graph, length, source) {}
1.961 +
1.962 + /// \brief Copy constructor
1.963 + DagShortestPathWizard(const _Traits &b) : _Traits(b) {}
1.964 +
1.965 + ~DagShortestPathWizard() {}
1.966 +
1.967 + /// \brief Runs DagShortestPath algorithm from a given node.
1.968 + ///
1.969 + /// Runs DagShortestPath algorithm from a given node.
1.970 + /// The node can be given by the \ref source function.
1.971 + void run() {
1.972 + if(Base::_source == INVALID) throw UninitializedParameter();
1.973 + DagShortestPath<Graph,LengthMap,_Traits>
1.974 + bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
1.975 + if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
1.976 + if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
1.977 + bf.run(Base::_source);
1.978 + }
1.979 +
1.980 + /// \brief Runs DagShortestPath algorithm from the given node.
1.981 + ///
1.982 + /// Runs DagShortestPath algorithm from the given node.
1.983 + /// \param s is the given source.
1.984 + void run(Node source) {
1.985 + Base::_source = source;
1.986 + run();
1.987 + }
1.988 +
1.989 + template<class T>
1.990 + struct DefPredMapBase : public Base {
1.991 + typedef T PredMap;
1.992 + static PredMap *createPredMap(const Graph &) { return 0; };
1.993 + DefPredMapBase(const _Traits &b) : _Traits(b) {}
1.994 + };
1.995 +
1.996 + ///\brief \ref named-templ-param "Named parameter"
1.997 + ///function for setting PredMap type
1.998 + ///
1.999 + /// \ref named-templ-param "Named parameter"
1.1000 + ///function for setting PredMap type
1.1001 + ///
1.1002 + template<class T>
1.1003 + DagShortestPathWizard<DefPredMapBase<T> > predMap(const T &t)
1.1004 + {
1.1005 + Base::_pred=(void *)&t;
1.1006 + return DagShortestPathWizard<DefPredMapBase<T> >(*this);
1.1007 + }
1.1008 +
1.1009 + template<class T>
1.1010 + struct DefDistMapBase : public Base {
1.1011 + typedef T DistMap;
1.1012 + static DistMap *createDistMap(const Graph &) { return 0; };
1.1013 + DefDistMapBase(const _Traits &b) : _Traits(b) {}
1.1014 + };
1.1015 +
1.1016 + ///\brief \ref named-templ-param "Named parameter"
1.1017 + ///function for setting DistMap type
1.1018 + ///
1.1019 + /// \ref named-templ-param "Named parameter"
1.1020 + ///function for setting DistMap type
1.1021 + ///
1.1022 + template<class T>
1.1023 + DagShortestPathWizard<DefDistMapBase<T> > distMap(const T &t) {
1.1024 + Base::_dist=(void *)&t;
1.1025 + return DagShortestPathWizard<DefDistMapBase<T> >(*this);
1.1026 + }
1.1027 +
1.1028 + template<class T>
1.1029 + struct DefOperationTraitsBase : public Base {
1.1030 + typedef T OperationTraits;
1.1031 + DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
1.1032 + };
1.1033 +
1.1034 + ///\brief \ref named-templ-param "Named parameter"
1.1035 + ///function for setting OperationTraits type
1.1036 + ///
1.1037 + /// \ref named-templ-param "Named parameter"
1.1038 + ///function for setting OperationTraits type
1.1039 + ///
1.1040 + template<class T>
1.1041 + DagShortestPathWizard<DefOperationTraitsBase<T> > distMap() {
1.1042 + return DagShortestPathWizard<DefDistMapBase<T> >(*this);
1.1043 + }
1.1044 +
1.1045 + /// \brief Sets the source node, from which the DagShortestPath algorithm runs.
1.1046 + ///
1.1047 + /// Sets the source node, from which the DagShortestPath algorithm runs.
1.1048 + /// \param s is the source node.
1.1049 + DagShortestPathWizard<_Traits>& source(Node source) {
1.1050 + Base::_source = source;
1.1051 + return *this;
1.1052 + }
1.1053 +
1.1054 + };
1.1055 +
1.1056 + /// \brief Function type interface for DagShortestPath algorithm.
1.1057 + ///
1.1058 + /// \ingroup flowalgs
1.1059 + /// Function type interface for DagShortestPath algorithm.
1.1060 + ///
1.1061 + /// This function also has several \ref named-templ-func-param
1.1062 + /// "named parameters", they are declared as the members of class
1.1063 + /// \ref DagShortestPathWizard.
1.1064 + /// The following
1.1065 + /// example shows how to use these parameters.
1.1066 + /// \code
1.1067 + /// dagShortestPath(g,length,source).predMap(preds).run();
1.1068 + /// \endcode
1.1069 + /// \warning Don't forget to put the \ref DagShortestPathWizard::run() "run()"
1.1070 + /// to the end of the parameter list.
1.1071 + /// \sa DagShortestPathWizard
1.1072 + /// \sa DagShortestPath
1.1073 + template<class _Graph, class _LengthMap>
1.1074 + DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
1.1075 + dagShortestPath(const _Graph& graph,
1.1076 + const _LengthMap& length,
1.1077 + typename _Graph::Node source = INVALID) {
1.1078 + return DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
1.1079 + (graph, length, source);
1.1080 + }
1.1081 +
1.1082 +} //END OF NAMESPACE LEMON
1.1083 +
1.1084 +#endif
1.1085 +