Changeset 278:931190050520 in lemon for lemon/dijkstra.h

Timestamp:

09/22/08 15:33:23 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)

• BfsWizard? and DfsWizard? have run(s), run(s,t), and run() functions, DijkstraWizard? has run(s) and run(s,t) functions.
• Set NodeMap?<T> instead of NullMap? as PredMap? and DistMap? in the default traits classes for the function-type interface.
• Modify the related test files.
• Doc improvements.
• Bug fix in concepts/path.h.

File:

• lemon/dijkstra.h (modified) (17 diffs)

lemon/dijkstra.h

@@ -31 +31 @@
 #include <lemon/error.h>
 #include <lemon/maps.h>
+#include <lemon/path.h>
 
 namespace lemon {
@@ -200 +201 @@
   ///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.
@@ -988 +989 @@
     ///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.
 
@@ -995 +996 @@
     ///\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 &)
-#endif
-    {
-      return new PredMap();
+    {
+      return new PredMap(g);
     }
 
@@ -1031 +1028 @@
     ///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.
 
@@ -1037 +1034 @@
     ///\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 &)
-#endif
-    {
-      return new DistMap();
-    }
+    {
+      return new DistMap(g);
+    }
+
+    ///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;
   };
 
@@ -1066 +1065 @@
     //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.
@@ -1074 +1073 @@
     //Pointer to the map of distances.
     void *_dist;
-    //Pointer to the source node.
-    Node _source;
+    //Pointer to the shortest path to the target node.
+    void *_path;
+    //Pointer to the distance of the target node.
+    void *_di;
 
   public:
@@ -1081 +1082 @@
 
     /// 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,
-    /// listed in the parameters list.
-    /// Others are initiated to 0.
+    /// This constructor requires two parameters,
+    /// others are initiated to \c 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, Node s=INVALID) :
+    DijkstraWizardBase(const GR &g,const LM &l) :
       _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.
-
-  /// This auxiliary class is created to implement the function type
-  /// interface of \ref Dijkstra algorithm. It uses the functions and features
-  /// of the plain \ref Dijkstra, but it is much simpler to use it.
-  /// It should only be used through the \ref dijkstra() function, which makes
-  /// it easier to use the algorithm.
+  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
+
+  /// This auxiliary class is created to implement the
+  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
+  /// It does not have own \ref run() method, it uses the functions
+  /// and features of the plain \ref Dijkstra.
   ///
-  /// 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 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.
+  /// This class should only be used through the \ref dijkstra() function,
+  /// which makes it easier to use the algorithm.
   template<class TR>
   class DijkstraWizard : public TR
@@ -1145 +1132 @@
     ///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;
@@ -1157 +1146 @@
     /// 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) :
-      TR(g,l,s) {}
+    /// \param g The digraph the algorithm runs on.
+    /// \param l The length map.
+    DijkstraWizard(const Digraph &g, const LengthMap &l) :
+      TR(g,l) {}
 
     ///Copy constructor
@@ -1165 +1156 @@
     ~DijkstraWizard() {}
 
-    ///Runs Dijkstra algorithm from a source node.
-
-    ///Runs Dijkstra algorithm from a source node.
-    ///The node can be given with the \ref source() function.
-    void run()
-    {
-      if(Base::_source==INVALID) throw UninitializedParameter();
+    ///Runs Dijkstra algorithm from the given source node.
+
+    ///This method runs %Dijkstra algorithm from the given source node
+    ///in order to compute the shortest path to each node.
+    void run(Node s)
+    {
+      if (s==INVALID) throw UninitializedParameter();
       Dijkstra<Digraph,LengthMap,TR>
-        dij(*reinterpret_cast<const Digraph*>(Base::_g),
-            *reinterpret_cast<const LengthMap*>(Base::_length));
-      if(Base::_processed)
-        dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
-      if(Base::_pred)
-        dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
-      if(Base::_dist)
-        dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
-      dij.run(Base::_source);
-    }
-
-    ///Runs Dijkstra algorithm from the given node.
-
-    ///Runs Dijkstra algorithm from the given node.
-    ///\param s is the given source.
-    void run(Node s)
-    {
-      Base::_source=s;
-      run();
-    }
-
-    /// Sets the source node, from which the Dijkstra algorithm runs.
-
-    /// Sets the source node, from which the Dijkstra algorithm runs.
-    /// \param s is the source node.
-    DijkstraWizard<TR> &source(Node s)
-    {
-      Base::_source=s;
-      return *this;
+        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
+             *reinterpret_cast<const LengthMap*>(Base::_length));
+      if (Base::_pred)
+        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
+      if (Base::_dist)
+        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
+      if (Base::_processed)
+        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
+      dijk.run(s);
+    }
+
+    ///Finds the shortest path between \c s and \c t.
+
+    ///This method runs the %Dijkstra algorithm from node \c s
+    ///in order to compute the shortest path to node \c t
+    ///(it stops searching when \c t is processed).
+    ///
+    ///\return \c true if \c t is reachable form \c s.
+    bool run(Node s, Node t)
+    {
+      if (s==INVALID || t==INVALID) throw UninitializedParameter();
+      Dijkstra<Digraph,LengthMap,TR>
+        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
+             *reinterpret_cast<const LengthMap*>(Base::_length));
+      if (Base::_pred)
+        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
+      if (Base::_dist)
+        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
+      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);
     }
 
@@ -1210 +1208 @@
       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>
@@ -1220 +1218 @@
       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);
     }
 
@@ -1228 +1244 @@
       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>
@@ -1241 +1257 @@
 
     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-templ-param "Named parameter"
-    ///for setting \ref DistMap object.
-    ///
-    ///\ref named-templ-param "Named parameter"
-    ///for setting \ref DistMap object.
+    struct SetPathBase : public Base {
+      typedef T Path;
+      SetPathBase(const TR &b) : TR(b) {}
+    };
+    ///\brief \ref named-func-param "Named parameter"
+    ///for getting the shortest path to the target node.
+    ///
+    ///\ref named-func-param "Named parameter"
+    ///for getting the shortest path to the target node.
     template<class T>
-    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
-    {
-      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
-      return DijkstraWizard<SetDistMapBase<T> >(*this);
+    DijkstraWizard<SetPathBase<T> > path(const T &t)
+    {
+      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
+      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
-  ///\ref named-templ-func-param "named parameters",
+  ///This function also has several \ref named-func-param "named parameters",
   ///they are declared as the members of class \ref DijkstraWizard.
-  ///The following
-  ///example shows how to use these parameters.
+  ///The following examples show 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()"
@@ -1279 +1307 @@
   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);
   }