lemon-main: comparison lemon/dijkstra.h

equal deleted inserted replaced

-:909a8392b2ee
+:cb7f4fe8515b
 #include <lemon/bin_heap.h>
 #include <lemon/bits/path_dump.h>
 #include <lemon/core.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>
+#include <lemon/path.h>
 namespace lemon {
 /// \brief Default operation traits for the Dijkstra algorithm class.
 ///
 ///so it is easy to change it to any kind of length.
 ///The type of the length is determined by the
 ///\ref concepts::ReadMap::Value "Value" of the length map.
 ///It is also possible to change the underlying priority heap.
 ///
-///There is also a \ref dijkstra() "function type interface" for the
+///There is also a \ref dijkstra() "function-type interface" for the
 ///%Dijkstra algorithm, which is convenient in the simplier cases and
 ///it can be used easier.
 ///
 ///\tparam GR The type of the digraph the algorithm runs on.
 ///The default value is \ref ListDigraph.
 ///arcs of the shortest paths.
 ///
 ///The type of the map that stores the predecessor
 ///arcs of the shortest paths.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
+typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 ///Instantiates a \ref PredMap.
 ///This function instantiates a \ref PredMap.
 ///\param g is the digraph, to which we would like to define the
 ///\ref PredMap.
 ///\todo The digraph alone may be insufficient to initialize
-#ifdef DOXYGEN
 static PredMap *createPredMap(const Digraph &g)
-#else
+{
-static PredMap *createPredMap(const Digraph &)
+return new PredMap(g);
-#endif
-{
-return new PredMap();
 }
 ///The type of the map that indicates which nodes are processed.
 ///The type of the map that indicates which nodes are processed.
 ///The type of the map that stores the distances of the nodes.
 ///The type of the map that stores the distances of the nodes.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-typedef NullMap<typename Digraph::Node,Value> DistMap;
+typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
 ///Instantiates a \ref DistMap.
 ///This function instantiates a \ref DistMap.
 ///\param g is the digraph, to which we would like to define
 ///the \ref DistMap
-#ifdef DOXYGEN
 static DistMap *createDistMap(const Digraph &g)
-#else
+{
-static DistMap *createDistMap(const Digraph &)
+return new DistMap(g);
-#endif
+}
-{
-return new DistMap();
+///The type of the shortest paths.
-}
+///The type of the shortest paths.
+///It must meet the \ref concepts::Path "Path" concept.
+typedef lemon::Path<Digraph> Path;
 };
 /// Default traits class used by \ref DijkstraWizard
 /// To make it easier to use Dijkstra algorithm
 //The type of the nodes in the digraph.
 typedef typename Base::Digraph::Node Node;
 //Pointer to the digraph the algorithm runs on.
 void *_g;
-//Pointer to the length map
+//Pointer to the length map.
 void *_length;
 //Pointer to the map of processed nodes.
 void *_processed;
 //Pointer to the map of predecessors arcs.
 void *_pred;
 //Pointer to the map of distances.
 void *_dist;
-//Pointer to the source node.
+//Pointer to the shortest path to the target node.
-Node _source;
+void *_path;
+//Pointer to the distance of the target node.
+void *_di;
 public:
 /// Constructor.
 /// This constructor does not require parameters, therefore it initiates
-/// all of the attributes to default values (0, INVALID).
+/// all of the attributes to \c 0.
 DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
-_dist(0), _source(INVALID) {}
+_dist(0), _path(0), _di(0) {}
 /// Constructor.
-/// This constructor requires some parameters,
+/// This constructor requires two parameters,
-/// listed in the parameters list.
+/// others are initiated to \c 0.
-/// Others are initiated to 0.
 /// \param g The digraph the algorithm runs on.
 /// \param l The length map.
-/// \param s The source node.
+DijkstraWizardBase(const GR &g,const LM &l) :
-DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
-_processed(0), _pred(0), _dist(0), _source(s) {}
+_processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
 };
-/// Auxiliary class for the function type interface of Dijkstra algorithm.
+/// Auxiliary class for the function-type interface of Dijkstra algorithm.
-/// This auxiliary class is created to implement the function type
+/// This auxiliary class is created to implement the
-/// interface of \ref Dijkstra algorithm. It uses the functions and features
+/// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
-/// of the plain \ref Dijkstra, but it is much simpler to use it.
+/// It does not have own \ref run() method, it uses the functions
-/// It should only be used through the \ref dijkstra() function, which makes
+/// and features of the plain \ref Dijkstra.
-/// it easier to use the algorithm.
 ///
-/// Simplicity means that the way to change the types defined
+/// This class should only be used through the \ref dijkstra() function,
-/// in the traits class is based on functions that returns the new class
+/// which makes it easier to use the algorithm.
-/// and not on templatable built-in classes.
-/// When using the plain \ref Dijkstra
-/// the new class with the modified type comes from
-/// the original class by using the ::
-/// operator. In the case of \ref DijkstraWizard 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 Dijkstra object, and calls the
-/// \ref Dijkstra::run() method of it.
 template<class TR>
 class DijkstraWizard : public TR
 {
 typedef TR Base;
 typedef typename TR::PredMap PredMap;
 ///The type of the map that stores the distances of the nodes.
 typedef typename TR::DistMap DistMap;
 ///The type of the map that indicates which nodes are processed.
 typedef typename TR::ProcessedMap ProcessedMap;
+///The type of the shortest paths
+typedef typename TR::Path Path;
 ///The heap type used by the dijkstra algorithm.
 typedef typename TR::Heap Heap;
 public:
 /// Constructor that requires parameters.
 /// Constructor that requires parameters.
 /// These parameters will be the default values for the traits class.
-DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
+/// \param g The digraph the algorithm runs on.
-TR(g,l,s) {}
+/// \param l The length map.
+DijkstraWizard(const Digraph &g, const LengthMap &l) :
+TR(g,l) {}
 ///Copy constructor
 DijkstraWizard(const TR &b) : TR(b) {}
 ~DijkstraWizard() {}
-///Runs Dijkstra algorithm from a source node.
+///Runs Dijkstra algorithm from the given source node.
-///Runs Dijkstra algorithm from a source node.
+///This method runs %Dijkstra algorithm from the given source node
-///The node can be given with the \ref source() function.
+///in order to compute the shortest path to each node.
-void run()
+void run(Node s)
 {
-if(Base::_source==INVALID) throw UninitializedParameter();
+if (s==INVALID) throw UninitializedParameter();
 Dijkstra<Digraph,LengthMap,TR>
-dij(*reinterpret_cast<const Digraph*>(Base::_g),
+dijk(*reinterpret_cast<const Digraph*>(Base::_g),
 *reinterpret_cast<const LengthMap*>(Base::_length));
-if(Base::_processed)
+if (Base::_pred)
-dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
+dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
-if(Base::_pred)
+if (Base::_dist)
-dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
+dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
-if(Base::_dist)
+if (Base::_processed)
-dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
+dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
-dij.run(Base::_source);
+dijk.run(s);
 }
-///Runs Dijkstra algorithm from the given node.
+///Finds the shortest path between \c s and \c t.
-///Runs Dijkstra algorithm from the given node.
+///This method runs the %Dijkstra algorithm from node \c s
-///\param s is the given source.
+///in order to compute the shortest path to node \c t
-void run(Node s)
+///(it stops searching when \c t is processed).
-{
+///
-Base::_source=s;
+///\return \c true if \c t is reachable form \c s.
-run();
+bool run(Node s, Node t)
-}
+{
+if (s==INVALID || t==INVALID) throw UninitializedParameter();
-/// Sets the source node, from which the Dijkstra algorithm runs.
+Dijkstra<Digraph,LengthMap,TR>
+dijk(*reinterpret_cast<const Digraph*>(Base::_g),
-/// Sets the source node, from which the Dijkstra algorithm runs.
+*reinterpret_cast<const LengthMap*>(Base::_length));
-/// \param s is the source node.
+if (Base::_pred)
-DijkstraWizard<TR> &source(Node s)
+dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
-{
+if (Base::_dist)
-Base::_source=s;
+dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
-return *this;
+if (Base::_processed)
+dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
+dijk.run(s,t);
+if (Base::_path)
+*reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
+if (Base::_di)
+*reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
+return dijk.reached(t);
 }
 template<class T>
 struct SetPredMapBase : public Base {
 typedef T PredMap;
 static PredMap *createPredMap(const Digraph &) { return 0; };
 SetPredMapBase(const TR &b) : TR(b) {}
 };
-///\brief \ref named-templ-param "Named parameter"
+///\brief \ref named-func-param "Named parameter"
 ///for setting \ref PredMap object.
 ///
-///\ref named-templ-param "Named parameter"
+///\ref named-func-param "Named parameter"
 ///for setting \ref PredMap object.
 template<class T>
 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
 {
 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 return DijkstraWizard<SetPredMapBase<T> >(*this);
+}
+template<class T>
+struct SetDistMapBase : public Base {
+typedef T DistMap;
+static DistMap *createDistMap(const Digraph &) { return 0; };
+SetDistMapBase(const TR &b) : TR(b) {}
+};
+///\brief \ref named-func-param "Named parameter"
+///for setting \ref DistMap object.
+///
+///\ref named-func-param "Named parameter"
+///for setting \ref DistMap object.
+template<class T>
+DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
+{
+Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
+return DijkstraWizard<SetDistMapBase<T> >(*this);
 }
 template<class T>
 struct SetProcessedMapBase : public Base {
 typedef T ProcessedMap;
 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 SetProcessedMapBase(const TR &b) : TR(b) {}
 };
-///\brief \ref named-templ-param "Named parameter"
+///\brief \ref named-func-param "Named parameter"
 ///for setting \ref ProcessedMap object.
 ///
-/// \ref named-templ-param "Named parameter"
+/// \ref named-func-param "Named parameter"
 ///for setting \ref ProcessedMap object.
 template<class T>
 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
 {
 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 return DijkstraWizard<SetProcessedMapBase<T> >(*this);
 }
 template<class T>
-struct SetDistMapBase : public Base {
+struct SetPathBase : public Base {
-typedef T DistMap;
+typedef T Path;
-static DistMap *createDistMap(const Digraph &) { return 0; };
+SetPathBase(const TR &b) : TR(b) {}
-SetDistMapBase(const TR &b) : TR(b) {}
+};
-};
+///\brief \ref named-func-param "Named parameter"
-///\brief \ref named-templ-param "Named parameter"
+///for getting the shortest path to the target node.
-///for setting \ref DistMap object.
+///
-///
+///\ref named-func-param "Named parameter"
-///\ref named-templ-param "Named parameter"
+///for getting the shortest path to the target node.
-///for setting \ref DistMap object.
 template<class T>
-DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
+DijkstraWizard<SetPathBase<T> > path(const T &t)
 {
-Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
+Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
-return DijkstraWizard<SetDistMapBase<T> >(*this);
+return DijkstraWizard<SetPathBase<T> >(*this);
+}
+///\brief \ref named-func-param "Named parameter"
+///for getting the distance of the target node.
+///
+///\ref named-func-param "Named parameter"
+///for getting the distance of the target node.
+DijkstraWizard dist(const Value &d)
+{
+Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
+return *this;
 }
 };
-///Function type interface for Dijkstra algorithm.
+///Function-type interface for Dijkstra algorithm.
 /// \ingroup shortest_path
-///Function type interface for Dijkstra algorithm.
+///Function-type interface for Dijkstra algorithm.
 ///
-///This function also has several
+///This function also has several \ref named-func-param "named parameters",
-///\ref named-templ-func-param "named parameters",
 ///they are declared as the members of class \ref DijkstraWizard.
-///The following
+///The following examples show how to use these parameters.
-///example shows how to use these parameters.
 ///\code
-///  dijkstra(g,length,source).predMap(preds).run();
+///  // Compute shortest path from node s to each node
+///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
+///
+///  // Compute shortest path from s to t
+///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
 ///\endcode
 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
 ///to the end of the parameter list.
 ///\sa DijkstraWizard
 ///\sa Dijkstra
 template<class GR, class LM>
 DijkstraWizard<DijkstraWizardBase<GR,LM> >
-dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
+dijkstra(const GR &digraph, const LM &length)
 {
-return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
+return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
 }
 } //END OF NAMESPACE LEMON
 #endif

changeset 279	6307bbbf285b
parent 258	0310c8984732
child 281	e9b4fbe163f5
child 286	da414906fe21