# HG changeset patch # User deba # Date 1128334856 0 # Node ID 29428f7b8b6630f0f397563442d0c74ed2cce65e # Parent 755cdc461ddd3bf6134e5ab3f71aaf8c37aa288d Some shortest path algorithms All-pair-shortest path algorithms without function interface we may need it diff -r 755cdc461ddd -r 29428f7b8b66 lemon/belmann_ford.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/belmann_ford.h Mon Oct 03 10:20:56 2005 +0000 @@ -0,0 +1,784 @@ +/* -*- C++ -*- + * lemon/belmann_ford.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_BELMANN_FORD_H +#define LEMON_BELMANN_FORD_H + +///\ingroup flowalgs +/// \file +/// \brief BelmannFord algorithm. +/// +/// \todo getPath() should be implemented! (also for BFS and DFS) + +#include +#include +#include +#include + +#include + +namespace lemon { + + /// \brief Default OperationTraits for the BelmannFord algorithm class. + /// + /// It defines all computational operations and constants which are + /// used in the belmann ford algorithm. The default implementation + /// is based on the numeric_limits class. If the numeric type does not + /// have infinity value then the maximum value is used as extremal + /// infinity value. + template < + typename Value, + bool has_infinity = std::numeric_limits::has_infinity> + struct BelmannFordDefaultOperationTraits { + /// \brief Gives back the zero value of the type. + static Value zero() { + return static_cast(0); + } + /// \brief Gives back the positive infinity value of the type. + static Value infinity() { + return std::numeric_limits::infinity(); + } + /// \brief Gives back the sum of the given two elements. + static Value plus(const Value& left, const Value& right) { + return left + right; + } + /// \brief Gives back true only if the first value less than the second. + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + template + struct BelmannFordDefaultOperationTraits { + static Value zero() { + return static_cast(0); + } + static Value infinity() { + return std::numeric_limits::max(); + } + static Value plus(const Value& left, const Value& right) { + if (left == infinity() || right == infinity()) return infinity(); + return left + right; + } + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + /// \brief Default traits class of BelmannFord class. + /// + /// Default traits class of BelmannFord class. + /// \param _Graph Graph type. + /// \param _LegthMap Type of length map. + template + struct BelmannFordDefaultTraits { + /// The graph type the algorithm runs on. + typedef _Graph Graph; + + /// \brief The type of the map that stores the edge lengths. + /// + /// The type of the map that stores the edge lengths. + /// It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef _LengthMap LengthMap; + + // The type of the length of the edges. + typedef typename _LengthMap::Value Value; + + /// \brief Operation traits for belmann-ford algorithm. + /// + /// It defines the infinity type on the given Value type + /// and the used operation. + /// \see BelmannFordDefaultOperationTraits + typedef BelmannFordDefaultOperationTraits OperationTraits; + + /// \brief The type of the map that stores the last edges of the + /// shortest paths. + /// + /// The type of the map that stores the last + /// edges of the shortest paths. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap PredMap; + + /// \brief Instantiates a PredMap. + /// + /// This function instantiates a \ref PredMap. + /// \param G is the graph, to which we would like to define the PredMap. + /// \todo The graph alone may be insufficient for the initialization + static PredMap *createPredMap(const _Graph& graph) { + return new PredMap(graph); + } + + /// \brief The type of the map that stores the dists of the nodes. + /// + /// The type of the map that stores the dists of the nodes. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap + DistMap; + + /// \brief Instantiates a DistMap. + /// + /// This function instantiates a \ref DistMap. + /// \param G is the graph, to which we would like to define the + /// \ref DistMap + static DistMap *createDistMap(const _Graph& graph) { + return new DistMap(graph); + } + + }; + + /// \brief BelmannFord algorithm class. + /// + /// \ingroup flowalgs + /// This class provides an efficient implementation of \c BelmannFord + /// algorithm. The edge lengths are passed to the algorithm using a + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any + /// kind of length. + /// + /// The type of the length is determined by the + /// \ref concept::ReadMap::Value "Value" of the length map. + /// + /// \param _Graph The graph type the algorithm runs on. The default value + /// is \ref ListGraph. The value of _Graph is not used directly by + /// BelmannFord, it is only passed to \ref BelmannFordDefaultTraits. + /// \param _LengthMap This read-only EdgeMap determines the lengths of the + /// edges. The default map type is \ref concept::StaticGraph::EdgeMap + /// "Graph::EdgeMap". The value of _LengthMap is not used directly + /// by BelmannFord, it is only passed to \ref BelmannFordDefaultTraits. + /// \param _Traits Traits class to set various data types used by the + /// algorithm. The default traits class is \ref BelmannFordDefaultTraits + /// "BelmannFordDefaultTraits<_Graph,_LengthMap>". See \ref + /// BelmannFordDefaultTraits for the documentation of a BelmannFord traits + /// class. + /// + /// \author Balazs Dezso + + template , + typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> > + class BelmannFord { + public: + + /// \brief \ref Exception for uninitialized parameters. + /// + /// This error represents problems in the initialization + /// of the parameters of the algorithms. + + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::BelmannFord::UninitializedParameter"; + } + }; + + typedef _Traits Traits; + ///The type of the underlying graph. + typedef typename _Traits::Graph Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + + /// \brief The type of the length of the edges. + typedef typename _Traits::LengthMap::Value Value; + /// \brief The type of the map that stores the edge lengths. + typedef typename _Traits::LengthMap LengthMap; + /// \brief The type of the map that stores the last + /// edges of the shortest paths. + typedef typename _Traits::PredMap PredMap; + /// \brief The type of the map that stores the dists of the nodes. + typedef typename _Traits::DistMap DistMap; + /// \brief The operation traits. + typedef typename _Traits::OperationTraits OperationTraits; + private: + /// Pointer to the underlying graph. + const Graph *graph; + /// Pointer to the length map + const LengthMap *length; + ///Pointer to the map of predecessors edges. + PredMap *_pred; + ///Indicates if \ref _pred is locally allocated (\c true) or not. + bool local_pred; + ///Pointer to the map of distances. + DistMap *_dist; + ///Indicates if \ref _dist is locally allocated (\c true) or not. + bool local_dist; + + /// Creates the maps if necessary. + void create_maps() { + if(!_pred) { + local_pred = true; + _pred = Traits::createPredMap(*graph); + } + if(!_dist) { + local_dist = true; + _dist = Traits::createDistMap(*graph); + } + } + + public : + + /// \name Named template parameters + + ///@{ + + template + struct DefPredMapTraits : public Traits { + typedef T PredMap; + static PredMap *createPredMap(const Graph& graph) { + throw UninitializedParameter(); + } + }; + + /// \brief \ref named-templ-param "Named parameter" for setting PredMap + /// type + /// \ref named-templ-param "Named parameter" for setting PredMap type + /// + template + class DefPredMap + : public BelmannFord< Graph, LengthMap, DefPredMapTraits > {}; + + template + struct DefDistMapTraits : public Traits { + typedef T DistMap; + static DistMap *createDistMap(const Graph& graph) { + throw UninitializedParameter(); + } + }; + + /// \brief \ref named-templ-param "Named parameter" for setting DistMap + /// type + /// + /// \ref named-templ-param "Named parameter" for setting DistMap type + /// + template + class DefDistMap + : public BelmannFord< Graph, LengthMap, DefDistMapTraits > {}; + + template + struct DefOperationTraitsTraits : public Traits { + typedef T OperationTraits; + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// OperationTraits type + /// + /// \ref named-templ-param "Named parameter" for setting PredMap type + template + class DefOperationTraits + : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits > { + public: + typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits > + BelmannFord; + }; + + ///@} + + public: + + /// \brief Constructor. + /// + /// \param _graph the graph the algorithm will run on. + /// \param _length the length map used by the algorithm. + BelmannFord(const Graph& _graph, const LengthMap& _length) : + graph(&_graph), length(&_length), + _pred(0), local_pred(false), + _dist(0), local_dist(false) {} + + ///Destructor. + ~BelmannFord() { + if(local_pred) delete _pred; + if(local_dist) delete _dist; + } + + /// \brief Sets the length map. + /// + /// Sets the length map. + /// \return \c (*this) + BelmannFord &lengthMap(const LengthMap &m) { + length = &m; + return *this; + } + + /// \brief Sets the map storing the predecessor edges. + /// + /// Sets the map storing the predecessor edges. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return \c (*this) + BelmannFord &predMap(PredMap &m) { + if(local_pred) { + delete _pred; + local_pred=false; + } + _pred = &m; + return *this; + } + + /// \brief Sets the map storing the distances calculated by the algorithm. + /// + /// Sets the map storing the distances calculated by the algorithm. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return \c (*this) + BelmannFord &distMap(DistMap &m) { + if(local_dist) { + delete _dist; + local_dist=false; + } + _dist = &m; + return *this; + } + + /// \name Execution control + /// The simplest way to execute the algorithm is to use + /// one of the member functions called \c run(...). + /// \n + /// If you need more control on the execution, + /// first you must call \ref init(), then you can add several source nodes + /// with \ref addSource(). + /// Finally \ref start() will perform the actual path + /// computation. + + ///@{ + + /// \brief Initializes the internal data structures. + /// + /// Initializes the internal data structures. + void init() { + create_maps(); + for (NodeIt it(*graph); it != INVALID; ++it) { + _pred->set(it, INVALID); + _dist->set(it, OperationTraits::infinity()); + } + } + + /// \brief Adds a new source node. + /// + /// The optional second parameter is the initial distance of the node. + /// It just sets the distance of the node to the given value. + void addSource(Node source, Value dst = OperationTraits::zero()) { + _dist->set(source, dst); + } + + /// \brief Executes the algorithm. + /// + /// \pre init() must be called and at least one node should be added + /// with addSource() before using this function. + /// + /// This method runs the %BelmannFord algorithm from the root node(s) + /// in order to compute the shortest path to each node. The algorithm + /// computes + /// - The shortest path tree. + /// - The distance of each node from the root(s). + void start() { + bool ready = false; + while (!ready) { + ready = true; + for (EdgeIt it(*graph); it != INVALID; ++it) { + Node source = graph->source(it); + Node target = graph->target(it); + Value relaxed = + OperationTraits::plus((*_dist)[source], (*length)[it]); + if (OperationTraits::less(relaxed, (*_dist)[target])) { + _pred->set(target, it); + _dist->set(target, relaxed); + ready = false; + } + } + } + } + + /// \brief Runs %BelmannFord algorithm from node \c s. + /// + /// This method runs the %BelmannFord algorithm from a root node \c s + /// in order to compute the shortest path to each node. The algorithm + /// computes + /// - The shortest path tree. + /// - The distance of each node from the root. + /// + /// \note d.run(s) is just a shortcut of the following code. + /// \code + /// d.init(); + /// d.addSource(s); + /// d.start(); + /// \endcode + void run(Node s) { + init(); + addSource(s); + start(); + } + + ///@} + + /// \name Query Functions + /// The result of the %BelmannFord algorithm can be obtained using these + /// functions.\n + /// Before the use of these functions, + /// either run() or start() must be called. + + ///@{ + + /// \brief Copies the shortest path to \c t into \c p + /// + /// This function copies the shortest path to \c t into \c p. + /// If it \c t is a source itself or unreachable, then it does not + /// alter \c p. + /// \todo Is it the right way to handle unreachable nodes? + /// \return Returns \c true if a path to \c t was actually copied to \c p, + /// \c false otherwise. + /// \sa DirPath + template + bool getPath(Path &p, Node t) { + if(reached(t)) { + p.clear(); + typename Path::Builder b(p); + for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) + b.pushFront(pred(t)); + b.commit(); + return true; + } + return false; + } + + /// \brief The distance of a node from the root. + /// + /// Returns the distance of a node from the root. + /// \pre \ref run() must be called before using this function. + /// \warning If node \c v in unreachable from the root the return value + /// of this funcion is undefined. + Value dist(Node v) const { return (*_dist)[v]; } + + /// \brief Returns the 'previous edge' of the shortest path tree. + /// + /// For a node \c v it returns the 'previous edge' of the shortest path + /// tree, i.e. it returns the last edge of a shortest path from the root + /// to \c v. It is \ref INVALID if \c v is unreachable from the root or + /// if \c v=s. The shortest path tree used here is equal to the shortest + /// path tree used in \ref predNode(). + /// \pre \ref run() must be called before using + /// this function. + /// \todo predEdge could be a better name. + Edge pred(Node v) const { return (*_pred)[v]; } + + /// \brief Returns the 'previous node' of the shortest path tree. + /// + /// For a node \c v it returns the 'previous node' of the shortest path + /// tree, i.e. it returns the last but one node from a shortest path from + /// the root to \c /v. It is INVALID if \c v is unreachable from the root + /// or if \c v=s. The shortest path tree used here is equal to the + /// shortest path tree used in \ref pred(). \pre \ref run() must be + /// called before using this function. + Node predNode(Node v) const { + return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]); + } + + /// \brief Returns a reference to the NodeMap of distances. + /// + /// Returns a reference to the NodeMap of distances. \pre \ref run() must + /// be called before using this function. + const DistMap &distMap() const { return *_dist;} + + /// \brief Returns a reference to the shortest path tree map. + /// + /// Returns a reference to the NodeMap of the edges of the + /// shortest path tree. + /// \pre \ref run() must be called before using this function. + const PredMap &predMap() const { return *_pred; } + + /// \brief Checks if a node is reachable from the root. + /// + /// Returns \c true if \c v is reachable from the root. + /// \pre \ref run() must be called before using this function. + /// + bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); } + + ///@} + }; + + /// \brief Default traits class of BelmannFord function. + /// + /// Default traits class of BelmannFord function. + /// \param _Graph Graph type. + /// \param _LengthMap Type of length map. + template + struct BelmannFordWizardDefaultTraits { + /// \brief The graph type the algorithm runs on. + typedef _Graph Graph; + + /// \brief The type of the map that stores the edge lengths. + /// + /// The type of the map that stores the edge lengths. + /// It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef _LengthMap LengthMap; + + /// \brief The value type of the length map. + typedef typename _LengthMap::Value Value; + + /// \brief Operation traits for belmann-ford algorithm. + /// + /// It defines the infinity type on the given Value type + /// and the used operation. + /// \see BelmannFordDefaultOperationTraits + typedef BelmannFordDefaultOperationTraits OperationTraits; + + /// \brief The type of the map that stores the last + /// edges of the shortest paths. + /// + /// The type of the map that stores the last + /// edges of the shortest paths. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + typedef NullMap PredMap; + + /// \brief Instantiates a PredMap. + /// + /// This function instantiates a \ref PredMap. + static PredMap *createPredMap(const _Graph &) { + return new PredMap(); + } + /// \brief The type of the map that stores the dists of the nodes. + /// + /// The type of the map that stores the dists of the nodes. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + typedef NullMap DistMap; + /// \brief Instantiates a DistMap. + /// + /// This function instantiates a \ref DistMap. + static DistMap *createDistMap(const _Graph &) { + return new DistMap(); + } + }; + + /// \brief Default traits used by \ref BelmannFordWizard + /// + /// To make it easier to use BelmannFord algorithm + /// we have created a wizard class. + /// This \ref BelmannFordWizard class needs default traits, + /// as well as the \ref BelmannFord class. + /// The \ref BelmannFordWizardBase is a class to be the default traits of the + /// \ref BelmannFordWizard class. + /// \todo More named parameters are required... + template + class BelmannFordWizardBase + : public BelmannFordWizardDefaultTraits<_Graph,_LengthMap> { + + typedef BelmannFordWizardDefaultTraits<_Graph,_LengthMap> Base; + protected: + /// Type of the nodes in the graph. + typedef typename Base::Graph::Node Node; + + /// Pointer to the underlying graph. + void *_graph; + /// Pointer to the length map + void *_length; + ///Pointer to the map of predecessors edges. + void *_pred; + ///Pointer to the map of distances. + void *_dist; + ///Pointer to the source node. + Node _source; + + public: + /// Constructor. + + /// This constructor does not require parameters, therefore it initiates + /// all of the attributes to default values (0, INVALID). + BelmannFordWizardBase() : _graph(0), _length(0), _pred(0), + _dist(0), _source(INVALID) {} + + /// Constructor. + + /// This constructor requires some parameters, + /// listed in the parameters list. + /// Others are initiated to 0. + /// \param graph is the initial value of \ref _graph + /// \param length is the initial value of \ref _length + /// \param source is the initial value of \ref _source + BelmannFordWizardBase(const _Graph& graph, + const _LengthMap& length, + Node source = INVALID) : + _graph((void *)&graph), _length((void *)&length), _pred(0), + _dist(0), _source(source) {} + + }; + + /// A class to make the usage of BelmannFord algorithm easier + + /// This class is created to make it easier to use BelmannFord algorithm. + /// It uses the functions and features of the plain \ref BelmannFord, + /// but it is much simpler to use it. + /// + /// Simplicity means that the way to change the types defined + /// in the traits class is based on functions that returns the new class + /// and not on templatable built-in classes. + /// When using the plain \ref BelmannFord + /// the new class with the modified type comes from + /// the original class by using the :: + /// operator. In the case of \ref BelmannFordWizard only + /// a function have to be called and it will + /// return the needed class. + /// + /// It does not have own \ref run method. When its \ref run method is called + /// it initiates a plain \ref BelmannFord class, and calls the \ref + /// BelmannFord::run method of it. + template + class BelmannFordWizard : public _Traits { + typedef _Traits Base; + + ///The type of the underlying graph. + typedef typename _Traits::Graph Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::OutEdgeIt EdgeIt; + + ///The type of the map that stores the edge lengths. + typedef typename _Traits::LengthMap LengthMap; + + ///The type of the length of the edges. + typedef typename LengthMap::Value Value; + + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + typedef typename _Traits::PredMap PredMap; + + ///The type of the map that stores the dists of the nodes. + typedef typename _Traits::DistMap DistMap; + + public: + /// Constructor. + BelmannFordWizard() : _Traits() {} + + /// \brief Constructor that requires parameters. + /// + /// Constructor that requires parameters. + /// These parameters will be the default values for the traits class. + BelmannFordWizard(const Graph& graph, const LengthMap& length, + Node source = INVALID) + : _Traits(graph, length, source) {} + + /// \brief Copy constructor + BelmannFordWizard(const _Traits &b) : _Traits(b) {} + + ~BelmannFordWizard() {} + + /// \brief Runs BelmannFord algorithm from a given node. + /// + /// Runs BelmannFord algorithm from a given node. + /// The node can be given by the \ref source function. + void run() { + if(Base::_source == INVALID) throw UninitializedParameter(); + BelmannFord + bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length); + if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred); + if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist); + bf.run(Base::_source); + } + + /// \brief Runs BelmannFord algorithm from the given node. + /// + /// Runs BelmannFord algorithm from the given node. + /// \param s is the given source. + void run(Node source) { + Base::_source = source; + run(); + } + + template + struct DefPredMapBase : public Base { + typedef T PredMap; + static PredMap *createPredMap(const Graph &) { return 0; }; + DefPredMapBase(const _Traits &b) : _Traits(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting PredMap type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting PredMap type + /// + template + BelmannFordWizard > predMap(const T &t) + { + Base::_pred=(void *)&t; + return BelmannFordWizard >(*this); + } + + template + struct DefDistMapBase : public Base { + typedef T DistMap; + static DistMap *createDistMap(const Graph &) { return 0; }; + DefDistMapBase(const _Traits &b) : _Traits(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + template + BelmannFordWizard > distMap(const T &t) { + Base::_dist=(void *)&t; + return BelmannFordWizard >(*this); + } + + /// \brief Sets the source node, from which the BelmannFord algorithm runs. + /// + /// Sets the source node, from which the BelmannFord algorithm runs. + /// \param s is the source node. + BelmannFordWizard<_Traits>& source(Node source) { + Base::_source = source; + return *this; + } + + }; + + /// \brief Function type interface for BelmannFord algorithm. + /// + /// \ingroup flowalgs + /// Function type interface for BelmannFord algorithm. + /// + /// This function also has several \ref named-templ-func-param + /// "named parameters", they are declared as the members of class + /// \ref BelmannFordWizard. + /// The following + /// example shows how to use these parameters. + /// \code + /// belmannford(g,length,source).predMap(preds).run(); + /// \endcode + /// \warning Don't forget to put the \ref BelmannFordWizard::run() "run()" + /// to the end of the parameter list. + /// \sa BelmannFordWizard + /// \sa BelmannFord + template + BelmannFordWizard > + belmannFord(const _Graph& graph, + const _LengthMap& length, + typename _Graph::Node source = INVALID) { + return BelmannFordWizard > + (graph, length, source); + } + +} //END OF NAMESPACE LEMON + +#endif + diff -r 755cdc461ddd -r 29428f7b8b66 lemon/floyd_warshall.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/floyd_warshall.h Mon Oct 03 10:20:56 2005 +0000 @@ -0,0 +1,525 @@ +/* -*- C++ -*- + * lemon/floyd_warshall.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_FLOYD_WARSHALL_H +#define LEMON_FLOYD_WARSHALL_H + +///\ingroup flowalgs +/// \file +/// \brief FloydWarshall algorithm. +/// +/// \todo getPath() should be implemented! (also for BFS and DFS) + +#include +#include +#include +#include +#include + +#include + +namespace lemon { + + /// \brief Default OperationTraits for the FloydWarshall algorithm class. + /// + /// It defines all computational operations and constants which are + /// used in the Floyd-Warshall algorithm. The default implementation + /// is based on the numeric_limits class. If the numeric type does not + /// have infinity value then the maximum value is used as extremal + /// infinity value. + template < + typename Value, + bool has_infinity = std::numeric_limits::has_infinity> + struct FloydWarshallDefaultOperationTraits { + /// \brief Gives back the zero value of the type. + static Value zero() { + return static_cast(0); + } + /// \brief Gives back the positive infinity value of the type. + static Value infinity() { + return std::numeric_limits::infinity(); + } + /// \brief Gives back the sum of the given two elements. + static Value plus(const Value& left, const Value& right) { + return left + right; + } + /// \brief Gives back true only if the first value less than the second. + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + template + struct FloydWarshallDefaultOperationTraits { + static Value zero() { + return static_cast(0); + } + static Value infinity() { + return std::numeric_limits::max(); + } + static Value plus(const Value& left, const Value& right) { + if (left == infinity() || right == infinity()) return infinity(); + return left + right; + } + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + /// \brief Default traits class of FloydWarshall class. + /// + /// Default traits class of FloydWarshall class. + /// \param _Graph Graph type. + /// \param _LegthMap Type of length map. + template + struct FloydWarshallDefaultTraits { + /// The graph type the algorithm runs on. + typedef _Graph Graph; + + /// \brief The type of the map that stores the edge lengths. + /// + /// The type of the map that stores the edge lengths. + /// It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef _LengthMap LengthMap; + + // The type of the length of the edges. + typedef typename _LengthMap::Value Value; + + /// \brief Operation traits for belmann-ford algorithm. + /// + /// It defines the infinity type on the given Value type + /// and the used operation. + /// \see FloydWarshallDefaultOperationTraits + typedef FloydWarshallDefaultOperationTraits OperationTraits; + + /// \brief The type of the map that stores the last edges of the + /// shortest paths. + /// + /// The type of the map that stores the last + /// edges of the shortest paths. + /// It must be a matrix map with \c Graph::Edge value type. + /// + typedef NodeMatrixMap PredMap; + + /// \brief Instantiates a PredMap. + /// + /// This function instantiates a \ref PredMap. + /// \param G is the graph, to which we would like to define the PredMap. + /// \todo The graph alone may be insufficient for the initialization + static PredMap *createPredMap(const _Graph& graph) { + return new PredMap(graph); + } + + /// \brief The type of the map that stores the dists of the nodes. + /// + /// The type of the map that stores the dists of the nodes. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef NodeMatrixMap DistMap; + + /// \brief Instantiates a DistMap. + /// + /// This function instantiates a \ref DistMap. + /// \param G is the graph, to which we would like to define the + /// \ref DistMap + static DistMap *createDistMap(const _Graph& graph) { + return new DistMap(graph); + } + + }; + + /// \brief FloydWarshall algorithm class. + /// + /// \ingroup flowalgs + /// This class provides an efficient implementation of \c FloydWarshall + /// algorithm. The edge lengths are passed to the algorithm using a + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any + /// kind of length. + /// + /// The type of the length is determined by the + /// \ref concept::ReadMap::Value "Value" of the length map. + /// + /// \param _Graph The graph type the algorithm runs on. The default value + /// is \ref ListGraph. The value of _Graph is not used directly by + /// FloydWarshall, it is only passed to \ref FloydWarshallDefaultTraits. + /// \param _LengthMap This read-only EdgeMap determines the lengths of the + /// edges. It is read once for each edge, so the map may involve in + /// relatively time consuming process to compute the edge length if + /// it is necessary. The default map type is \ref + /// concept::StaticGraph::EdgeMap "Graph::EdgeMap". The value + /// of _LengthMap is not used directly by FloydWarshall, it is only passed + /// to \ref FloydWarshallDefaultTraits. \param _Traits Traits class to set + /// various data types used by the algorithm. The default traits + /// class is \ref FloydWarshallDefaultTraits + /// "FloydWarshallDefaultTraits<_Graph,_LengthMap>". See \ref + /// FloydWarshallDefaultTraits for the documentation of a FloydWarshall + /// traits class. + /// + /// \author Balazs Dezso + + + template , + typename _Traits=FloydWarshallDefaultTraits<_Graph,_LengthMap> > + class FloydWarshall { + public: + + /// \brief \ref Exception for uninitialized parameters. + /// + /// This error represents problems in the initialization + /// of the parameters of the algorithms. + + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::FloydWarshall::UninitializedParameter"; + } + }; + + typedef _Traits Traits; + ///The type of the underlying graph. + typedef typename _Traits::Graph Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + + /// \brief The type of the length of the edges. + typedef typename _Traits::LengthMap::Value Value; + /// \brief The type of the map that stores the edge lengths. + typedef typename _Traits::LengthMap LengthMap; + /// \brief The type of the map that stores the last + /// edges of the shortest paths. The type of the PredMap + /// is a matrix map for Edges + typedef typename _Traits::PredMap PredMap; + /// \brief The type of the map that stores the dists of the nodes. + /// The type of the DistMap is a matrix map for Values + typedef typename _Traits::DistMap DistMap; + /// \brief The operation traits. + typedef typename _Traits::OperationTraits OperationTraits; + private: + /// Pointer to the underlying graph. + const Graph *graph; + /// Pointer to the length map + const LengthMap *length; + ///Pointer to the map of predecessors edges. + PredMap *_pred; + ///Indicates if \ref _pred is locally allocated (\c true) or not. + bool local_pred; + ///Pointer to the map of distances. + DistMap *_dist; + ///Indicates if \ref _dist is locally allocated (\c true) or not. + bool local_dist; + + /// Creates the maps if necessary. + void create_maps() { + if(!_pred) { + local_pred = true; + _pred = Traits::createPredMap(*graph); + } + if(!_dist) { + local_dist = true; + _dist = Traits::createDistMap(*graph); + } + } + + public : + + /// \name Named template parameters + + ///@{ + + template + struct DefPredMapTraits : public Traits { + typedef T PredMap; + static PredMap *createPredMap(const Graph& graph) { + throw UninitializedParameter(); + } + }; + + /// \brief \ref named-templ-param "Named parameter" for setting PredMap + /// type + /// \ref named-templ-param "Named parameter" for setting PredMap type + /// + template + class DefPredMap + : public FloydWarshall< Graph, LengthMap, DefPredMapTraits > {}; + + template + struct DefDistMapTraits : public Traits { + typedef T DistMap; + static DistMap *createDistMap(const Graph& graph) { + throw UninitializedParameter(); + } + }; + /// \brief \ref named-templ-param "Named parameter" for setting DistMap + /// type + /// + /// \ref named-templ-param "Named parameter" for setting DistMap type + /// + template + class DefDistMap + : public FloydWarshall< Graph, LengthMap, DefDistMapTraits > {}; + + template + struct DefOperationTraitsTraits : public Traits { + typedef T OperationTraits; + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// OperationTraits type + /// + /// \ref named-templ-param "Named parameter" for setting PredMap type + template + class DefOperationTraits + : public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits > { + }; + + ///@} + + public: + + /// \brief Constructor. + /// + /// \param _graph the graph the algorithm will run on. + /// \param _length the length map used by the algorithm. + FloydWarshall(const Graph& _graph, const LengthMap& _length) : + graph(&_graph), length(&_length), + _pred(0), local_pred(false), + _dist(0), local_dist(false) {} + + ///Destructor. + ~FloydWarshall() { + if(local_pred) delete _pred; + if(local_dist) delete _dist; + } + + /// \brief Sets the length map. + /// + /// Sets the length map. + /// \return \c (*this) + FloydWarshall &lengthMap(const LengthMap &m) { + length = &m; + return *this; + } + + /// \brief Sets the map storing the predecessor edges. + /// + /// Sets the map storing the predecessor edges. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return \c (*this) + FloydWarshall &predMap(PredMap &m) { + if(local_pred) { + delete _pred; + local_pred=false; + } + _pred = &m; + return *this; + } + + /// \brief Sets the map storing the distances calculated by the algorithm. + /// + /// Sets the map storing the distances calculated by the algorithm. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return \c (*this) + FloydWarshall &distMap(DistMap &m) { + if(local_dist) { + delete _dist; + local_dist=false; + } + _dist = &m; + return *this; + } + + ///\name Execution control + /// The simplest way to execute the algorithm is to use + /// one of the member functions called \c run(...). + /// \n + /// If you need more control on the execution, + /// Finally \ref start() will perform the actual path + /// computation. + + ///@{ + + /// \brief Initializes the internal data structures. + /// + /// Initializes the internal data structures. + void init() { + create_maps(); + for (NodeIt it(*graph); it != INVALID; ++it) { + for (NodeIt jt(*graph); jt != INVALID; ++jt) { + _pred->set(it, jt, INVALID); + _dist->set(it, jt, it == jt ? + OperationTraits::zero() : OperationTraits::infinity()); + } + } + for (EdgeIt it(*graph); it != INVALID; ++it) { + Node source = graph->source(it); + Node target = graph->target(it); + if (OperationTraits::less((*length)[it], (*_dist)(source, target))) { + _dist->set(source, target, (*length)[it]); + _pred->set(source, target, it); + } + } + } + + /// \brief Executes the algorithm. + /// + /// This method runs the %FloydWarshall algorithm in order to compute + /// the shortest path to each node pairs. The algorithm + /// computes + /// - The shortest path tree for each node. + /// - The distance between each node pairs. + void start() { + for (NodeIt kt(*graph); kt != INVALID; ++kt) { + for (NodeIt it(*graph); it != INVALID; ++it) { + for (NodeIt jt(*graph); jt != INVALID; ++jt) { + Value relaxed = OperationTraits::plus((*_dist)(it, kt), + (*_dist)(kt, jt)); + if (OperationTraits::less(relaxed, (*_dist)(it, jt))) { + _dist->set(it, jt, relaxed); + _pred->set(it, jt, (*_pred)(kt, jt)); + } + } + } + } + } + + /// \brief Runs %FloydWarshall algorithm. + /// + /// This method runs the %FloydWarshall algorithm from a each node + /// in order to compute the shortest path to each node pairs. + /// The algorithm computes + /// - The shortest path tree for each node. + /// - The distance between each node pairs. + /// + /// \note d.run(s) is just a shortcut of the following code. + /// \code + /// d.init(); + /// d.start(); + /// \endcode + void run() { + init(); + start(); + } + + ///@} + + /// \name Query Functions + /// The result of the %FloydWarshall algorithm can be obtained using these + /// functions.\n + /// Before the use of these functions, + /// either run() or start() must be called. + + ///@{ + + /// \brief Copies the shortest path to \c t into \c p + /// + /// This function copies the shortest path to \c t into \c p. + /// If it \c t is a source itself or unreachable, then it does not + /// alter \c p. + /// \todo Is it the right way to handle unreachable nodes? + /// \return Returns \c true if a path to \c t was actually copied to \c p, + /// \c false otherwise. + /// \sa DirPath + template + bool getPath(Path &p, Node source, Node target) { + if (connected(source, target)) { + p.clear(); + typename Path::Builder b(target); + for(b.setStartNode(target); pred(source, target) != INVALID; + target = predNode(target)) { + b.pushFront(pred(source, target)); + } + b.commit(); + return true; + } + return false; + } + + /// \brief The distance between two nodes. + /// + /// Returns the distance between two nodes. + /// \pre \ref run() must be called before using this function. + /// \warning If node \c v in unreachable from the root the return value + /// of this funcion is undefined. + Value dist(Node source, Node target) const { + return (*_dist)(source, target); + } + + /// \brief Returns the 'previous edge' of the shortest path tree. + /// + /// For the node \c node it returns the 'previous edge' of the shortest + /// path tree to direction of the node \c root + /// i.e. it returns the last edge of a shortest path from the node \c root + /// to \c node. It is \ref INVALID if \c node is unreachable from the root + /// or if \c node=root. The shortest path tree used here is equal to the + /// shortest path tree used in \ref predNode(). + /// \pre \ref run() must be called before using this function. + /// \todo predEdge could be a better name. + Edge pred(Node root, Node node) const { + return (*_pred)(root, node); + } + + /// \brief Returns the 'previous node' of the shortest path tree. + /// + /// For a node \c node it returns the 'previous node' of the shortest path + /// tree to direction of the node \c root, i.e. it returns the last but + /// one node from a shortest path from the \c root to \c node. It is + /// INVALID if \c node is unreachable from the root or if \c node=root. + /// The shortest path tree used here is equal to the + /// shortest path tree used in \ref pred(). + /// \pre \ref run() must be called before using this function. + Node predNode(Node root, Node node) const { + return (*_pred)(root, node) == INVALID ? + INVALID : graph->source((*_pred)(root, node)); + } + + /// \brief Returns a reference to the matrix node map of distances. + /// + /// Returns a reference to the matrix node map of distances. + /// + /// \pre \ref run() must be called before using this function. + const DistMap &distMap() const { return *_dist;} + + /// \brief Returns a reference to the shortest path tree map. + /// + /// Returns a reference to the matrix node map of the edges of the + /// shortest path tree. + /// \pre \ref run() must be called before using this function. + const PredMap &predMap() const { return *_pred;} + + /// \brief Checks if a node is reachable from the root. + /// + /// Returns \c true if \c v is reachable from the root. + /// \pre \ref run() must be called before using this function. + /// + bool connected(Node source, Node target) { + return (*_dist)(source, target) != OperationTraits::infinity(); + } + + ///@} + }; + +} //END OF NAMESPACE LEMON + +#endif + diff -r 755cdc461ddd -r 29428f7b8b66 lemon/johnson.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/johnson.h Mon Oct 03 10:20:56 2005 +0000 @@ -0,0 +1,547 @@ +/* -*- C++ -*- + * lemon/johnson.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_JOHNSON_H +#define LEMON_JOHNSON_H + +///\ingroup flowalgs +/// \file +/// \brief Johnson algorithm. +/// + +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +namespace lemon { + + /// \brief Default OperationTraits for the Johnson algorithm class. + /// + /// It defines all computational operations and constants which are + /// used in the Floyd-Warshall algorithm. The default implementation + /// is based on the numeric_limits class. If the numeric type does not + /// have infinity value then the maximum value is used as extremal + /// infinity value. + template < + typename Value, + bool has_infinity = std::numeric_limits::has_infinity> + struct JohnsonDefaultOperationTraits { + /// \brief Gives back the zero value of the type. + static Value zero() { + return static_cast(0); + } + /// \brief Gives back the positive infinity value of the type. + static Value infinity() { + return std::numeric_limits::infinity(); + } + /// \brief Gives back the sum of the given two elements. + static Value plus(const Value& left, const Value& right) { + return left + right; + } + /// \brief Gives back true only if the first value less than the second. + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + template + struct JohnsonDefaultOperationTraits { + static Value zero() { + return static_cast(0); + } + static Value infinity() { + return std::numeric_limits::max(); + } + static Value plus(const Value& left, const Value& right) { + if (left == infinity() || right == infinity()) return infinity(); + return left + right; + } + static bool less(const Value& left, const Value& right) { + return left < right; + } + }; + + /// \brief Default traits class of Johnson class. + /// + /// Default traits class of Johnson class. + /// \param _Graph Graph type. + /// \param _LegthMap Type of length map. + template + struct JohnsonDefaultTraits { + /// The graph type the algorithm runs on. + typedef _Graph Graph; + + /// \brief The type of the map that stores the edge lengths. + /// + /// The type of the map that stores the edge lengths. + /// It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef _LengthMap LengthMap; + + // The type of the length of the edges. + typedef typename _LengthMap::Value Value; + + /// \brief Operation traits for belmann-ford algorithm. + /// + /// It defines the infinity type on the given Value type + /// and the used operation. + /// \see JohnsonDefaultOperationTraits + typedef JohnsonDefaultOperationTraits OperationTraits; + + /// \brief The type of the map that stores the last edges of the + /// shortest paths. + /// + /// The type of the map that stores the last + /// edges of the shortest paths. + /// It must be a matrix map with \c Graph::Edge value type. + /// + typedef NodeMatrixMap PredMap; + + /// \brief Instantiates a PredMap. + /// + /// This function instantiates a \ref PredMap. + /// \param G is the graph, to which we would like to define the PredMap. + /// \todo The graph alone may be insufficient for the initialization + static PredMap *createPredMap(const _Graph& graph) { + return new PredMap(graph); + } + + /// \brief The type of the map that stores the dists of the nodes. + /// + /// The type of the map that stores the dists of the nodes. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef NodeMatrixMap DistMap; + + /// \brief Instantiates a DistMap. + /// + /// This function instantiates a \ref DistMap. + /// \param G is the graph, to which we would like to define the + /// \ref DistMap + static DistMap *createDistMap(const _Graph& graph) { + return new DistMap(graph); + } + + }; + + /// \brief Johnson algorithm class. + /// + /// \ingroup flowalgs + /// This class provides an efficient implementation of \c Johnson + /// algorithm. The edge lengths are passed to the algorithm using a + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any + /// kind of length. + /// + /// The type of the length is determined by the + /// \ref concept::ReadMap::Value "Value" of the length map. + /// + /// \param _Graph The graph type the algorithm runs on. The default value + /// is \ref ListGraph. The value of _Graph is not used directly by + /// Johnson, it is only passed to \ref JohnsonDefaultTraits. + /// \param _LengthMap This read-only EdgeMap determines the lengths of the + /// edges. It is read once for each edge, so the map may involve in + /// relatively time consuming process to compute the edge length if + /// it is necessary. The default map type is \ref + /// concept::StaticGraph::EdgeMap "Graph::EdgeMap". The value + /// of _LengthMap is not used directly by Johnson, it is only passed + /// to \ref JohnsonDefaultTraits. \param _Traits Traits class to set + /// various data types used by the algorithm. The default traits + /// class is \ref JohnsonDefaultTraits + /// "JohnsonDefaultTraits<_Graph,_LengthMap>". See \ref + /// JohnsonDefaultTraits for the documentation of a Johnson traits + /// class. + /// + /// \author Balazs Dezso + + template , + typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> > + class Johnson { + public: + + /// \brief \ref Exception for uninitialized parameters. + /// + /// This error represents problems in the initialization + /// of the parameters of the algorithms. + + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::Johnson::UninitializedParameter"; + } + }; + + typedef _Traits Traits; + ///The type of the underlying graph. + typedef typename _Traits::Graph Graph; + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + + /// \brief The type of the length of the edges. + typedef typename _Traits::LengthMap::Value Value; + /// \brief The type of the map that stores the edge lengths. + typedef typename _Traits::LengthMap LengthMap; + /// \brief The type of the map that stores the last + /// edges of the shortest paths. The type of the PredMap + /// is a matrix map for Edges + typedef typename _Traits::PredMap PredMap; + /// \brief The type of the map that stores the dists of the nodes. + /// The type of the DistMap is a matrix map for Values + typedef typename _Traits::DistMap DistMap; + /// \brief The operation traits. + typedef typename _Traits::OperationTraits OperationTraits; + private: + /// Pointer to the underlying graph. + const Graph *graph; + /// Pointer to the length map + const LengthMap *length; + ///Pointer to the map of predecessors edges. + PredMap *_pred; + ///Indicates if \ref _pred is locally allocated (\c true) or not. + bool local_pred; + ///Pointer to the map of distances. + DistMap *_dist; + ///Indicates if \ref _dist is locally allocated (\c true) or not. + bool local_dist; + + /// Creates the maps if necessary. + void create_maps() { + if(!_pred) { + local_pred = true; + _pred = Traits::createPredMap(*graph); + } + if(!_dist) { + local_dist = true; + _dist = Traits::createDistMap(*graph); + } + } + + public : + + /// \name Named template parameters + + ///@{ + + template + struct DefPredMapTraits : public Traits { + typedef T PredMap; + static PredMap *createPredMap(const Graph& graph) { + throw UninitializedParameter(); + } + }; + + /// \brief \ref named-templ-param "Named parameter" for setting PredMap + /// type + /// \ref named-templ-param "Named parameter" for setting PredMap type + /// + template + class DefPredMap + : public Johnson< Graph, LengthMap, DefPredMapTraits > {}; + + template + struct DefDistMapTraits : public Traits { + typedef T DistMap; + static DistMap *createDistMap(const Graph& graph) { + throw UninitializedParameter(); + } + }; + /// \brief \ref named-templ-param "Named parameter" for setting DistMap + /// type + /// + /// \ref named-templ-param "Named parameter" for setting DistMap type + /// + template + class DefDistMap + : public Johnson< Graph, LengthMap, DefDistMapTraits > {}; + + template + struct DefOperationTraitsTraits : public Traits { + typedef T OperationTraits; + }; + + /// \brief \ref named-templ-param "Named parameter" for setting + /// OperationTraits type + /// + /// \ref named-templ-param "Named parameter" for setting PredMap type + template + class DefOperationTraits + : public Johnson< Graph, LengthMap, DefOperationTraitsTraits > {}; + + ///@} + + public: + + /// \brief Constructor. + /// + /// \param _graph the graph the algorithm will run on. + /// \param _length the length map used by the algorithm. + Johnson(const Graph& _graph, const LengthMap& _length) : + graph(&_graph), length(&_length), + _pred(0), local_pred(false), + _dist(0), local_dist(false) {} + + ///Destructor. + ~Johnson() { + if(local_pred) delete _pred; + if(local_dist) delete _dist; + } + + /// \brief Sets the length map. + /// + /// Sets the length map. + /// \return \c (*this) + Johnson &lengthMap(const LengthMap &m) { + length = &m; + return *this; + } + + /// \brief Sets the map storing the predecessor edges. + /// + /// Sets the map storing the predecessor edges. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return \c (*this) + Johnson &predMap(PredMap &m) { + if(local_pred) { + delete _pred; + local_pred=false; + } + _pred = &m; + return *this; + } + + /// \brief Sets the map storing the distances calculated by the algorithm. + /// + /// Sets the map storing the distances calculated by the algorithm. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return \c (*this) + Johnson &distMap(DistMap &m) { + if(local_dist) { + delete _dist; + local_dist=false; + } + _dist = &m; + return *this; + } + + ///\name Execution control + /// The simplest way to execute the algorithm is to use + /// one of the member functions called \c run(...). + /// \n + /// If you need more control on the execution, + /// Finally \ref start() will perform the actual path + /// computation. + + ///@{ + + /// \brief Initializes the internal data structures. + /// + /// Initializes the internal data structures. + void init() { + create_maps(); + } + + /// \brief Executes the algorithm. + /// + /// This method runs the %Johnson algorithm in order to compute + /// the shortest path to each node pairs. The algorithm + /// computes + /// - The shortest path tree for each node. + /// - The distance between each node pairs. + void start() { + typename BelmannFord:: + template DefOperationTraits:: + BelmannFord belmannford(*graph, *length); + + belmannford.init(); + + typename Graph::template NodeMap initial(*graph, false); + + { + Dfs dfs(*graph); + + dfs.init(); + for (NodeIt it(*graph); it != INVALID; ++it) { + if (!dfs.reached(it)) { + dfs.addSource(it); + while (!dfs.emptyQueue()) { + Edge edge = dfs.processNextEdge(); + initial.set(graph->target(edge), false); + } + initial.set(it, true); + } + } + for (NodeIt it(*graph); it != INVALID; ++it) { + if (initial[it]) { + belmannford.addSource(it); + } + } + } + + belmannford.start(); + + for (NodeIt it(*graph); it != INVALID; ++it) { + typedef PotentialDifferenceMap::DistMap> PotDiffMap; + PotDiffMap potdiff(*graph, belmannford.distMap()); + typedef SubMap ShiftLengthMap; + ShiftLengthMap shiftlen(*length, potdiff); + Dijkstra dijkstra(*graph, shiftlen); + dijkstra.run(it); + for (NodeIt jt(*graph); jt != INVALID; ++jt) { + if (dijkstra.reached(jt)) { + _dist->set(it, jt, dijkstra.dist(jt) + + belmannford.dist(jt) - belmannford.dist(it)); + _pred->set(it, jt, dijkstra.pred(jt)); + } else { + _dist->set(it, jt, OperationTraits::infinity()); + _pred->set(it, jt, INVALID); + } + } + } + } + + /// \brief Runs %Johnson algorithm. + /// + /// This method runs the %Johnson algorithm from a each node + /// in order to compute the shortest path to each node pairs. + /// The algorithm computes + /// - The shortest path tree for each node. + /// - The distance between each node pairs. + /// + /// \note d.run(s) is just a shortcut of the following code. + /// \code + /// d.init(); + /// d.start(); + /// \endcode + void run() { + init(); + start(); + } + + ///@} + + /// \name Query Functions + /// The result of the %Johnson algorithm can be obtained using these + /// functions.\n + /// Before the use of these functions, + /// either run() or start() must be called. + + ///@{ + + /// \brief Copies the shortest path to \c t into \c p + /// + /// This function copies the shortest path to \c t into \c p. + /// If it \c t is a source itself or unreachable, then it does not + /// alter \c p. + /// \todo Is it the right way to handle unreachable nodes? + /// \return Returns \c true if a path to \c t was actually copied to \c p, + /// \c false otherwise. + /// \sa DirPath + template + bool getPath(Path &p, Node source, Node target) { + if (connected(source, target)) { + p.clear(); + typename Path::Builder b(target); + for(b.setStartNode(target); pred(source, target) != INVALID; + target = predNode(target)) { + b.pushFront(pred(source, target)); + } + b.commit(); + return true; + } + return false; + } + + /// \brief The distance between two nodes. + /// + /// Returns the distance between two nodes. + /// \pre \ref run() must be called before using this function. + /// \warning If node \c v in unreachable from the root the return value + /// of this funcion is undefined. + Value dist(Node source, Node target) const { + return (*_dist)(source, target); + } + + /// \brief Returns the 'previous edge' of the shortest path tree. + /// + /// For the node \c node it returns the 'previous edge' of the shortest + /// path tree to direction of the node \c root + /// i.e. it returns the last edge of a shortest path from the node \c root + /// to \c node. It is \ref INVALID if \c node is unreachable from the root + /// or if \c node=root. The shortest path tree used here is equal to the + /// shortest path tree used in \ref predNode(). + /// \pre \ref run() must be called before using this function. + /// \todo predEdge could be a better name. + Edge pred(Node root, Node node) const { + return (*_pred)(root, node); + } + + /// \brief Returns the 'previous node' of the shortest path tree. + /// + /// For a node \c node it returns the 'previous node' of the shortest path + /// tree to direction of the node \c root, i.e. it returns the last but + /// one node from a shortest path from the \c root to \c node. It is + /// INVALID if \c node is unreachable from the root or if \c node=root. + /// The shortest path tree used here is equal to the + /// shortest path tree used in \ref pred(). + /// \pre \ref run() must be called before using this function. + Node predNode(Node root, Node node) const { + return (*_pred)(root, node) == INVALID ? + INVALID : graph->source((*_pred)(root, node)); + } + + /// \brief Returns a reference to the matrix node map of distances. + /// + /// Returns a reference to the matrix node map of distances. + /// + /// \pre \ref run() must be called before using this function. + const DistMap &distMap() const { return *_dist;} + + /// \brief Returns a reference to the shortest path tree map. + /// + /// Returns a reference to the matrix node map of the edges of the + /// shortest path tree. + /// \pre \ref run() must be called before using this function. + const PredMap &predMap() const { return *_pred;} + + /// \brief Checks if a node is reachable from the root. + /// + /// Returns \c true if \c v is reachable from the root. + /// \pre \ref run() must be called before using this function. + /// + bool connected(Node source, Node target) { + return (*_dist)(source, target) != OperationTraits::infinity(); + } + + ///@} + }; + +} //END OF NAMESPACE LEMON + +#endif