Changes in / [279:6307bbbf285b:277:7abfb55f1ecc] in lemon-1.2

Files:

• lemon/bfs.h (modified) (18 diffs)
• lemon/concepts/path.h (modified) (1 diff)
• lemon/dfs.h (modified) (19 diffs)
• lemon/dijkstra.h (modified) (17 diffs)
• test/bfs_test.cc (modified) (6 diffs)
• test/dfs_test.cc (modified) (3 diffs)
• test/dijkstra_test.cc (modified) (6 diffs)

lemon/bfs.h

@@ -29 +29 @@
 #include <lemon/error.h>
 #include <lemon/maps.h>
-#include <lemon/path.h>
 
 namespace lemon {
@@ -117 +116 @@
   ///This class provides an efficient implementation of the %BFS algorithm.
   ///
-  ///There is also a \ref bfs() "function-type interface" for the BFS
+  ///There is also a \ref bfs() "function type interface" for the BFS
   ///algorithm, which is convenient in the simplier cases and it can be
   ///used easier.
@@ -843 +842 @@
     ///arcs of the shortest paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
+    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     ///Instantiates a \ref PredMap.
 
@@ -850 +849 @@
     ///\ref PredMap.
     ///\todo The digraph alone may be insufficient to initialize
+#ifdef DOXYGEN
     static PredMap *createPredMap(const Digraph &g)
-    {
-      return new PredMap(g);
+#else
+    static PredMap *createPredMap(const Digraph &)
+#endif
+    {
+      return new PredMap();
     }
 
@@ -859 +862 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \ref ProcessedMap.
@@ -894 +896 @@
     ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    typedef typename Digraph::template NodeMap<int> DistMap;
+    ///
+    typedef NullMap<typename Digraph::Node,int> DistMap;
     ///Instantiates a \ref DistMap.
 
@@ -900 +903 @@
     ///\param g is the digraph, to which we would like to define
     ///the \ref DistMap
+#ifdef DOXYGEN
     static DistMap *createDistMap(const Digraph &g)
-    {
-      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;
+#else
+    static DistMap *createDistMap(const Digraph &)
+#endif
+    {
+      return new DistMap();
+    }
   };
 
@@ -939 +940 @@
     //Pointer to the map of distances.
     void *_dist;
-    //Pointer to the shortest path to the target node.
-    void *_path;
-    //Pointer to the distance of the target node.
-    int *_di;
+    //Pointer to the source node.
+    Node _source;
 
     public:
@@ -948 +947 @@
 
     /// This constructor does not require parameters, therefore it initiates
-    /// all of the attributes to \c 0.
+    /// all of the attributes to default values (0, INVALID).
     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
-                      _dist(0), _path(0), _di(0) {}
+                      _dist(0), _source(INVALID) {}
 
     /// Constructor.
 
-    /// This constructor requires one parameter,
-    /// others are initiated to \c 0.
+    /// This constructor requires some parameters,
+    /// listed in the parameters list.
+    /// Others are initiated to 0.
     /// \param g The digraph the algorithm runs on.
-    BfsWizardBase(const GR &g) :
+    /// \param s The source node.
+    BfsWizardBase(const GR &g, Node s=INVALID) :
       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
-      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
+      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
 
   };
 
-  /// Auxiliary class for the function-type interface of BFS algorithm.
-
-  /// This auxiliary class is created to implement the
-  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
-  /// It does not have own \ref run() method, it uses the functions
-  /// and features of the plain \ref Bfs.
+  /// Auxiliary class for the function type interface of BFS algorithm.
+
+  /// This auxiliary class is created to implement the function type
+  /// interface of \ref Bfs algorithm. It uses the functions and features
+  /// of the plain \ref Bfs, but it is much simpler to use it.
+  /// It should only be used through the \ref bfs() function, which makes
+  /// it easier to use the algorithm.
   ///
-  /// This class should only be used through the \ref bfs() function,
-  /// which makes it easier to use the algorithm.
+  /// 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 Bfs
+  /// the new class with the modified type comes from
+  /// the original class by using the ::
+  /// operator. In the case of \ref BfsWizard 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 Bfs object, and calls the
+  /// \ref Bfs::run() method of it.
   template<class TR>
   class BfsWizard : public TR
@@ -994 +1007 @@
     ///\brief 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;
 
   public:
@@ -1006 +1017 @@
     /// Constructor that requires parameters.
     /// These parameters will be the default values for the traits class.
-    /// \param g The digraph the algorithm runs on.
-    BfsWizard(const Digraph &g) :
-      TR(g) {}
+    BfsWizard(const Digraph &g, Node s=INVALID) :
+      TR(g,s) {}
 
     ///Copy constructor
@@ -1015 +1025 @@
     ~BfsWizard() {}
 
-    ///Runs BFS algorithm from the given source node.
-
-    ///This method runs BFS algorithm from node \c s
-    ///in order to compute the shortest path to each node.
+    ///Runs BFS algorithm from a source node.
+
+    ///Runs BFS algorithm from a source node.
+    ///The node can be given with the \ref source() function.
+    void run()
+    {
+      if(Base::_source==INVALID) throw UninitializedParameter();
+      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
+      if(Base::_reached)
+        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
+      if(Base::_processed)
+        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
+      if(Base::_pred)
+        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
+      if(Base::_dist)
+        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
+      alg.run(Base::_source);
+    }
+
+    ///Runs BFS algorithm from the given node.
+
+    ///Runs BFS algorithm from the given node.
+    ///\param s is the given source.
     void run(Node s)
     {
-      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
-      if (Base::_pred)
-        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
-      if (Base::_dist)
-        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
-      if (Base::_reached)
-        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
-      if (Base::_processed)
-        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
-      if (s!=INVALID)
-        alg.run(s);
-      else
-        alg.run();
-    }
-
-    ///Finds the shortest path between \c s and \c t.
-
-    ///This method runs BFS 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();
-      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
-      if (Base::_pred)
-        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
-      if (Base::_dist)
-        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
-      if (Base::_reached)
-        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
-      if (Base::_processed)
-        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
-      alg.run(s,t);
-      if (Base::_path)
-        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
-      if (Base::_di)
-        *Base::_di = alg.dist(t);
-      return alg.reached(t);
-    }
-
-    ///Runs BFS algorithm to visit all nodes in the digraph.
-
-    ///This method runs BFS algorithm in order to compute
-    ///the shortest path to each node.
-    void run()
-    {
-      run(INVALID);
+      Base::_source=s;
+      run();
+    }
+
+    /// Sets the source node, from which the Bfs algorithm runs.
+
+    /// Sets the source node, from which the Bfs algorithm runs.
+    /// \param s is the source node.
+    BfsWizard<TR> &source(Node s)
+    {
+      Base::_source=s;
+      return *this;
     }
 
@@ -1078 +1070 @@
       SetPredMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
+    ///\brief \ref named-templ-param "Named parameter"
     ///for setting \ref PredMap object.
     ///
-    ///\ref named-func-param "Named parameter"
+    /// \ref named-templ-param "Named parameter"
     ///for setting \ref PredMap object.
     template<class T>
@@ -1096 +1088 @@
       SetReachedMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
+    ///\brief \ref named-templ-param "Named parameter"
     ///for setting \ref ReachedMap object.
     ///
-    /// \ref named-func-param "Named parameter"
+    /// \ref named-templ-param "Named parameter"
     ///for setting \ref ReachedMap object.
     template<class T>
@@ -1106 +1098 @@
       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
       return BfsWizard<SetReachedMapBase<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"
+    ///for setting \ref ProcessedMap object.
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///for setting \ref ProcessedMap object.
+    template<class T>
+    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+    {
+      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
+      return BfsWizard<SetProcessedMapBase<T> >(*this);
     }
 
@@ -1114 +1124 @@
       SetDistMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
+    ///\brief \ref named-templ-param "Named parameter"
     ///for setting \ref DistMap object.
     ///
-    /// \ref named-func-param "Named parameter"
+    /// \ref named-templ-param "Named parameter"
     ///for setting \ref DistMap object.
     template<class T>
@@ -1126 +1136 @@
     }
 
-    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-func-param "Named parameter"
-    ///for setting \ref ProcessedMap object.
-    ///
-    /// \ref named-func-param "Named parameter"
-    ///for setting \ref ProcessedMap object.
-    template<class T>
-    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
-    {
-      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
-      return BfsWizard<SetProcessedMapBase<T> >(*this);
-    }
-
-    template<class T>
-    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>
-    BfsWizard<SetPathBase<T> > path(const T &t)
-    {
-      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
-      return BfsWizard<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.
-    BfsWizard dist(const int &d)
-    {
-      Base::_di=const_cast<int*>(&d);
-      return *this;
-    }
-
   };
 
-  ///Function-type interface for BFS algorithm.
+  ///Function type interface for Bfs algorithm.
 
   /// \ingroup search
-  ///Function-type interface for BFS algorithm.
+  ///Function type interface for Bfs algorithm.
   ///
-  ///This function also has several \ref named-func-param "named parameters",
+  ///This function also has several
+  ///\ref named-templ-func-param "named parameters",
   ///they are declared as the members of class \ref BfsWizard.
-  ///The following examples show how to use these parameters.
+  ///The following
+  ///example shows how to use these parameters.
   ///\code
-  ///  // Compute shortest path from node s to each node
-  ///  bfs(g).predMap(preds).distMap(dists).run(s);
-  ///
-  ///  // Compute shortest path from s to t
-  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
+  ///  bfs(g,source).predMap(preds).run();
   ///\endcode
   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
@@ -1195 +1157 @@
   template<class GR>
   BfsWizard<BfsWizardBase<GR> >
-  bfs(const GR &digraph)
+  bfs(const GR &g,typename GR::Node s=INVALID)
   {
-    return BfsWizard<BfsWizardBase<GR> >(digraph);
+    return BfsWizard<BfsWizardBase<GR> >(g,s);
   }
 

lemon/concepts/path.h

@@ -67 +67 @@
       /// \brief Template assigment
       template <typename CPath>
-      Path& operator=(const CPath& cpath) {
-        ignore_unused_variable_warning(cpath);
-        return *this;
-      }
+      Path& operator=(const CPath& cpath) {}
 
       /// Length of the path ie. the number of arcs in the path.

lemon/dfs.h

@@ -30 +30 @@
 #include <lemon/assert.h>
 #include <lemon/maps.h>
-#include <lemon/path.h>
 
 namespace lemon {
@@ -118 +117 @@
   ///This class provides an efficient implementation of the %DFS algorithm.
   ///
-  ///There is also a \ref dfs() "function-type interface" for the DFS
+  ///There is also a \ref dfs() "function type interface" for the DFS
   ///algorithm, which is convenient in the simplier cases and it can be
   ///used easier.
@@ -777 +776 @@
     ///arcs of the %DFS paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
+    ///
+    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     ///Instantiates a \ref PredMap.
 
@@ -784 +784 @@
     ///\ref PredMap.
     ///\todo The digraph alone may be insufficient to initialize
+#ifdef DOXYGEN
     static PredMap *createPredMap(const Digraph &g)
-    {
-      return new PredMap(g);
+#else
+    static PredMap *createPredMap(const Digraph &)
+#endif
+    {
+      return new PredMap();
     }
 
@@ -793 +797 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \ref ProcessedMap.
@@ -828 +831 @@
     ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    typedef typename Digraph::template NodeMap<int> DistMap;
+    ///
+    typedef NullMap<typename Digraph::Node,int> DistMap;
     ///Instantiates a \ref DistMap.
 
@@ -834 +838 @@
     ///\param g is the digraph, to which we would like to define
     ///the \ref DistMap
+#ifdef DOXYGEN
     static DistMap *createDistMap(const Digraph &g)
-    {
-      return new DistMap(g);
-    }
-
-    ///The type of the DFS paths.
-
-    ///The type of the DFS paths.
-    ///It must meet the \ref concepts::Path "Path" concept.
-    typedef lemon::Path<Digraph> Path;
+#else
+    static DistMap *createDistMap(const Digraph &)
+#endif
+    {
+      return new DistMap();
+    }
   };
 
@@ -873 +875 @@
     //Pointer to the map of distances.
     void *_dist;
-    //Pointer to the DFS path to the target node.
-    void *_path;
-    //Pointer to the distance of the target node.
-    int *_di;
+    //Pointer to the source node.
+    Node _source;
 
     public:
@@ -882 +882 @@
 
     /// This constructor does not require parameters, therefore it initiates
-    /// all of the attributes to \c 0.
+    /// all of the attributes to default values (0, INVALID).
     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
-                      _dist(0), _path(0), _di(0) {}
+                      _dist(0), _source(INVALID) {}
 
     /// Constructor.
 
-    /// This constructor requires one parameter,
-    /// others are initiated to \c 0.
+    /// This constructor requires some parameters,
+    /// listed in the parameters list.
+    /// Others are initiated to 0.
     /// \param g The digraph the algorithm runs on.
-    DfsWizardBase(const GR &g) :
+    /// \param s The source node.
+    DfsWizardBase(const GR &g, Node s=INVALID) :
       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
-      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
+      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
 
   };
 
-  /// Auxiliary class for the function-type interface of DFS algorithm.
-
-  /// This auxiliary class is created to implement the
-  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
-  /// It does not have own \ref run() method, it uses the functions
-  /// and features of the plain \ref Dfs.
+  /// Auxiliary class for the function type interface of DFS algorithm.
+
+  /// This auxiliary class is created to implement the function type
+  /// interface of \ref Dfs algorithm. It uses the functions and features
+  /// of the plain \ref Dfs, but it is much simpler to use it.
+  /// It should only be used through the \ref dfs() function, which makes
+  /// it easier to use the algorithm.
   ///
-  /// This class should only be used through the \ref dfs() function,
-  /// which makes it easier to use the algorithm.
+  /// 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 Dfs
+  /// the new class with the modified type comes from
+  /// the original class by using the ::
+  /// operator. In the case of \ref DfsWizard 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 Dfs object, and calls the
+  /// \ref Dfs::run() method of it.
   template<class TR>
   class DfsWizard : public TR
@@ -920 +934 @@
 
     ///\brief The type of the map that stores the predecessor
-    ///arcs of the DFS paths.
+    ///arcs of the shortest paths.
     typedef typename TR::PredMap PredMap;
     ///\brief The type of the map that stores the distances of the nodes.
@@ -928 +942 @@
     ///\brief The type of the map that indicates which nodes are processed.
     typedef typename TR::ProcessedMap ProcessedMap;
-    ///The type of the DFS paths
-    typedef typename TR::Path Path;
 
   public:
@@ -940 +952 @@
     /// Constructor that requires parameters.
     /// These parameters will be the default values for the traits class.
-    /// \param g The digraph the algorithm runs on.
-    DfsWizard(const Digraph &g) :
-      TR(g) {}
+    DfsWizard(const Digraph &g, Node s=INVALID) :
+      TR(g,s) {}
 
     ///Copy constructor
@@ -949 +960 @@
     ~DfsWizard() {}
 
-    ///Runs DFS algorithm from the given source node.
-
-    ///This method runs DFS algorithm from node \c s
-    ///in order to compute the DFS path to each node.
+    ///Runs DFS algorithm from a source node.
+
+    ///Runs DFS algorithm from a source node.
+    ///The node can be given with the \ref source() function.
+    void run()
+    {
+      if(Base::_source==INVALID) throw UninitializedParameter();
+      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
+      if(Base::_reached)
+        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
+      if(Base::_processed)
+        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
+      if(Base::_pred)
+        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
+      if(Base::_dist)
+        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
+      alg.run(Base::_source);
+    }
+
+    ///Runs DFS algorithm from the given node.
+
+    ///Runs DFS algorithm from the given node.
+    ///\param s is the given source.
     void run(Node s)
     {
-      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
-      if (Base::_pred)
-        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
-      if (Base::_dist)
-        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
-      if (Base::_reached)
-        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
-      if (Base::_processed)
-        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
-      if (s!=INVALID)
-        alg.run(s);
-      else
-        alg.run();
-    }
-
-    ///Finds the DFS path between \c s and \c t.
-
-    ///This method runs DFS algorithm from node \c s
-    ///in order to compute the DFS 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();
-      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
-      if (Base::_pred)
-        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
-      if (Base::_dist)
-        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
-      if (Base::_reached)
-        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
-      if (Base::_processed)
-        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
-      alg.run(s,t);
-      if (Base::_path)
-        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
-      if (Base::_di)
-        *Base::_di = alg.dist(t);
-      return alg.reached(t);
-      }
-
-    ///Runs DFS algorithm to visit all nodes in the digraph.
-
-    ///This method runs DFS algorithm in order to compute
-    ///the DFS path to each node.
-    void run()
-    {
-      run(INVALID);
+      Base::_source=s;
+      run();
+    }
+
+    /// Sets the source node, from which the Dfs algorithm runs.
+
+    /// Sets the source node, from which the Dfs algorithm runs.
+    /// \param s is the source node.
+    DfsWizard<TR> &source(Node s)
+    {
+      Base::_source=s;
+      return *this;
     }
 
@@ -1012 +1005 @@
       SetPredMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
+    ///\brief \ref named-templ-param "Named parameter"
     ///for setting \ref PredMap object.
     ///
-    ///\ref named-func-param "Named parameter"
+    ///\ref named-templ-param "Named parameter"
     ///for setting \ref PredMap object.
     template<class T>
@@ -1030 +1023 @@
       SetReachedMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
+    ///\brief \ref named-templ-param "Named parameter"
     ///for setting \ref ReachedMap object.
     ///
-    /// \ref named-func-param "Named parameter"
+    /// \ref named-templ-param "Named parameter"
     ///for setting \ref ReachedMap object.
     template<class T>
@@ -1040 +1033 @@
       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
       return DfsWizard<SetReachedMapBase<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"
+    ///for setting \ref ProcessedMap object.
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///for setting \ref ProcessedMap object.
+    template<class T>
+    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+    {
+      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
+      return DfsWizard<SetProcessedMapBase<T> >(*this);
     }
 
@@ -1048 +1059 @@
       SetDistMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
+    ///\brief \ref named-templ-param "Named parameter"
     ///for setting \ref DistMap object.
     ///
-    /// \ref named-func-param "Named parameter"
+    ///\ref named-templ-param "Named parameter"
     ///for setting \ref DistMap object.
     template<class T>
@@ -1060 +1071 @@
     }
 
-    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-func-param "Named parameter"
-    ///for setting \ref ProcessedMap object.
-    ///
-    /// \ref named-func-param "Named parameter"
-    ///for setting \ref ProcessedMap object.
-    template<class T>
-    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
-    {
-      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
-      return DfsWizard<SetProcessedMapBase<T> >(*this);
-    }
-
-    template<class T>
-    struct SetPathBase : public Base {
-      typedef T Path;
-      SetPathBase(const TR &b) : TR(b) {}
-    };
-    ///\brief \ref named-func-param "Named parameter"
-    ///for getting the DFS path to the target node.
-    ///
-    ///\ref named-func-param "Named parameter"
-    ///for getting the DFS path to the target node.
-    template<class T>
-    DfsWizard<SetPathBase<T> > path(const T &t)
-    {
-      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
-      return DfsWizard<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.
-    DfsWizard dist(const int &d)
-    {
-      Base::_di=const_cast<int*>(&d);
-      return *this;
-    }
-
   };
 
-  ///Function-type interface for DFS algorithm.
+  ///Function type interface for Dfs algorithm.
 
   ///\ingroup search
-  ///Function-type interface for DFS algorithm.
+  ///Function type interface for Dfs algorithm.
   ///
-  ///This function also has several \ref named-func-param "named parameters",
+  ///This function also has several
+  ///\ref named-templ-func-param "named parameters",
   ///they are declared as the members of class \ref DfsWizard.
-  ///The following examples show how to use these parameters.
+  ///The following
+  ///example shows how to use these parameters.
   ///\code
-  ///  // Compute the DFS tree
-  ///  dfs(g).predMap(preds).distMap(dists).run(s);
-  ///
-  ///  // Compute the DFS path from s to t
-  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
+  ///  dfs(g,source).predMap(preds).run();
   ///\endcode
-
   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
   ///to the end of the parameter list.
@@ -1130 +1092 @@
   template<class GR>
   DfsWizard<DfsWizardBase<GR> >
-  dfs(const GR &digraph)
+  dfs(const GR &g,typename GR::Node s=INVALID)
   {
-    return DfsWizard<DfsWizardBase<GR> >(digraph);
+    return DfsWizard<DfsWizardBase<GR> >(g,s);
   }
 

lemon/dijkstra.h

@@ -31 +31 @@
 #include <lemon/error.h>
 #include <lemon/maps.h>
-#include <lemon/path.h>
 
 namespace lemon {
@@ -201 +200 @@
   ///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.
@@ -989 +988 @@
     ///arcs of the shortest paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
+    typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
     ///Instantiates a \ref PredMap.
 
@@ -996 +995 @@
     ///\ref PredMap.
     ///\todo The digraph alone may be insufficient to initialize
+#ifdef DOXYGEN
     static PredMap *createPredMap(const Digraph &g)
-    {
-      return new PredMap(g);
+#else
+    static PredMap *createPredMap(const Digraph &)
+#endif
+    {
+      return new PredMap();
     }
 
@@ -1028 +1031 @@
     ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
+    typedef NullMap<typename Digraph::Node,Value> DistMap;
     ///Instantiates a \ref DistMap.
 
@@ -1034 +1037 @@
     ///\param g is the digraph, to which we would like to define
     ///the \ref DistMap
+#ifdef DOXYGEN
     static DistMap *createDistMap(const Digraph &g)
-    {
-      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;
+#else
+    static DistMap *createDistMap(const Digraph &)
+#endif
+    {
+      return new DistMap();
+    }
   };
 
@@ -1065 +1066 @@
     //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.
@@ -1073 +1074 @@
     //Pointer to the map of distances.
     void *_dist;
-    //Pointer to the shortest path to the target node.
-    void *_path;
-    //Pointer to the distance of the target node.
-    void *_di;
+    //Pointer to the source node.
+    Node _source;
 
   public:
@@ -1082 +1081 @@
 
     /// This constructor does not require parameters, therefore it initiates
-    /// all of the attributes to \c 0.
+    /// all of the attributes to default values (0, INVALID).
     DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
-                           _dist(0), _path(0), _di(0) {}
+                           _dist(0), _source(INVALID) {}
 
     /// Constructor.
 
-    /// This constructor requires two parameters,
-    /// others are initiated to \c 0.
+    /// This constructor requires some parameters,
+    /// listed in the parameters list.
+    /// Others are initiated to 0.
     /// \param g The digraph the algorithm runs on.
     /// \param l The length map.
-    DijkstraWizardBase(const GR &g,const LM &l) :
+    /// \param s The source node.
+    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), _path(0), _di(0) {}
+      _processed(0), _pred(0), _dist(0), _source(s) {}
 
   };
 
-  /// 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.
+  /// 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.
   ///
-  /// This class should only be used through the \ref dijkstra() function,
-  /// which makes it easier to use the algorithm.
+  /// 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.
   template<class TR>
   class DijkstraWizard : public TR
@@ -1132 +1145 @@
     ///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;
@@ -1146 +1157 @@
     /// Constructor that requires parameters.
     /// These parameters will be the default values for the traits class.
-    /// \param g The digraph the algorithm runs on.
-    /// \param l The length map.
-    DijkstraWizard(const Digraph &g, const LengthMap &l) :
-      TR(g,l) {}
+    DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
+      TR(g,l,s) {}
 
     ///Copy constructor
@@ -1156 +1165 @@
     ~DijkstraWizard() {}
 
-    ///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.
+    ///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();
+      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)
     {
-      if (s==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);
-    }
-
-    ///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);
+      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;
     }
 
@@ -1208 +1210 @@
       SetPredMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
+    ///\brief \ref named-templ-param "Named parameter"
     ///for setting \ref PredMap object.
     ///
-    ///\ref named-func-param "Named parameter"
+    ///\ref named-templ-param "Named parameter"
     ///for setting \ref PredMap object.
     template<class T>
@@ -1218 +1220 @@
       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
       return DijkstraWizard<SetPredMapBase<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"
+    ///for setting \ref ProcessedMap object.
+    ///
+    /// \ref named-templ-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);
     }
 
@@ -1226 +1246 @@
       SetDistMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
+    ///\brief \ref named-templ-param "Named parameter"
     ///for setting \ref DistMap object.
     ///
-    ///\ref named-func-param "Named parameter"
+    ///\ref named-templ-param "Named parameter"
     ///for setting \ref DistMap object.
     template<class T>
@@ -1238 +1258 @@
     }
 
-    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-func-param "Named parameter"
-    ///for setting \ref ProcessedMap object.
-    ///
-    /// \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 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<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-func-param "named parameters",
+  ///This function also has several
+  ///\ref named-templ-func-param "named parameters",
   ///they are declared as the members of class \ref DijkstraWizard.
-  ///The following examples show how to use these parameters.
+  ///The following
+  ///example shows how to use these parameters.
   ///\code
-  ///  // 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);
+  ///  dijkstra(g,length,source).predMap(preds).run();
   ///\endcode
   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
@@ -1307 +1279 @@
   template<class GR, class LM>
   DijkstraWizard<DijkstraWizardBase<GR,LM> >
-  dijkstra(const GR &digraph, const LM &length)
+  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
   {
-    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
+    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
   }
 

test/bfs_test.cc

@@ -63 +63 @@
   BType::DistMap d(G);
   BType::PredMap p(G);
+  //  BType::PredNodeMap pn(G);
 
   BType bfs_test(G);
@@ -72 +73 @@
   n  = bfs_test.predNode(n);
   d  = bfs_test.distMap();
+
   p  = bfs_test.predMap();
+  //  pn = bfs_test.predNodeMap();
   b  = bfs_test.reached(n);
 
@@ -86 +89 @@
 
   Digraph g;
-  bool b;
-  bfs(g).run(Node());
-  b=bfs(g).run(Node(),Node());
-  bfs(g).run();
+  bfs(g,Node()).run();
+  bfs(g).source(Node()).run();
   bfs(g)
-    .predMap(concepts::ReadWriteMap<Node,Arc>())
-    .distMap(concepts::ReadWriteMap<Node,VType>())
+    .predMap(concepts::WriteMap<Node,Arc>())
+    .distMap(concepts::WriteMap<Node,VType>())
     .reachedMap(concepts::ReadWriteMap<Node,bool>())
     .processedMap(concepts::WriteMap<Node,bool>())
     .run(Node());
-  b=bfs(g)
-    .predMap(concepts::ReadWriteMap<Node,Arc>())
-    .distMap(concepts::ReadWriteMap<Node,VType>())
-    .reachedMap(concepts::ReadWriteMap<Node,bool>())
-    .processedMap(concepts::WriteMap<Node,bool>())
-    .path(concepts::Path<Digraph>())
-    .dist(VType())
-    .run(Node(),Node());
-  bfs(g)
-    .predMap(concepts::ReadWriteMap<Node,Arc>())
-    .distMap(concepts::ReadWriteMap<Node,VType>())
-    .reachedMap(concepts::ReadWriteMap<Node,bool>())
-    .processedMap(concepts::WriteMap<Node,bool>())
-    .run();
 }
 
@@ -128 +115 @@
   bfs_test.run(s);
 
-  check(bfs_test.dist(t)==2,"Bfs found a wrong path.");
+  check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
 
   Path<Digraph> p = bfs_test.path(t);
@@ -142 +129 @@
     check( !bfs_test.reached(u) ||
            (bfs_test.dist(v) <= bfs_test.dist(u)+1),
-           "Wrong output. " << G.id(u) << "->" << G.id(v));
+           "Wrong output." << G.id(v) << ' ' << G.id(u));
   }
 
@@ -154 +141 @@
         check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
               "Wrong distance. Difference: "
-              << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1));
+              << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
+                          - 1));
       }
     }
-  }
-
-  {
-    NullMap<Node,Arc> myPredMap;
-    bfs(G).predMap(myPredMap).run(s);
   }
 }

test/dfs_test.cc

@@ -21 +21 @@
 #include <lemon/list_graph.h>
 #include <lemon/lgf_reader.h>
+
 #include <lemon/dfs.h>
 #include <lemon/path.h>
@@ -88 +89 @@
 
   Digraph g;
-  bool b;
-  dfs(g).run(Node());
-  b=dfs(g).run(Node(),Node());
-  dfs(g).run();
+  dfs(g,Node()).run();
+  dfs(g).source(Node()).run();
   dfs(g)
-    .predMap(concepts::ReadWriteMap<Node,Arc>())
-    .distMap(concepts::ReadWriteMap<Node,VType>())
+    .predMap(concepts::WriteMap<Node,Arc>())
+    .distMap(concepts::WriteMap<Node,VType>())
     .reachedMap(concepts::ReadWriteMap<Node,bool>())
     .processedMap(concepts::WriteMap<Node,bool>())
     .run(Node());
-  b=dfs(g)
-    .predMap(concepts::ReadWriteMap<Node,Arc>())
-    .distMap(concepts::ReadWriteMap<Node,VType>())
-    .reachedMap(concepts::ReadWriteMap<Node,bool>())
-    .processedMap(concepts::WriteMap<Node,bool>())
-    .path(concepts::Path<Digraph>())
-    .dist(VType())
-    .run(Node(),Node());
-  dfs(g)
-    .predMap(concepts::ReadWriteMap<Node,Arc>())
-    .distMap(concepts::ReadWriteMap<Node,VType>())
-    .reachedMap(concepts::ReadWriteMap<Node,bool>())
-    .processedMap(concepts::WriteMap<Node,bool>())
-    .run();
 }
 
@@ -145 +130 @@
         check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
               "Wrong distance. (" << dfs_test.dist(u) << "->"
-              << dfs_test.dist(v) << ")");
+              <<dfs_test.dist(v) << ')');
       }
     }
-  }
-
-  {
-    NullMap<Node,Arc> myPredMap;
-    dfs(G).predMap(myPredMap).run(s);
   }
 }

test/dijkstra_test.cc

@@ -21 +21 @@
 #include <lemon/list_graph.h>
 #include <lemon/lgf_reader.h>
+
 #include <lemon/dijkstra.h>
 #include <lemon/path.h>
@@ -64 +65 @@
   DType::DistMap d(G);
   DType::PredMap p(G);
+  //  DType::PredNodeMap pn(G);
   LengthMap length;
 
@@ -75 +77 @@
   d  = dijkstra_test.distMap();
   p  = dijkstra_test.predMap();
+  //  pn = dijkstra_test.predNodeMap();
   b  = dijkstra_test.reached(n);
 
@@ -89 +92 @@
 
   Digraph g;
-  bool b;
-  dijkstra(g,LengthMap()).run(Node());
-  b=dijkstra(g,LengthMap()).run(Node(),Node());
+  dijkstra(g,LengthMap(),Node()).run();
+  dijkstra(g,LengthMap()).source(Node()).run();
   dijkstra(g,LengthMap())
-    .predMap(concepts::ReadWriteMap<Node,Arc>())
-    .distMap(concepts::ReadWriteMap<Node,VType>())
-    .processedMap(concepts::WriteMap<Node,bool>())
+    .predMap(concepts::WriteMap<Node,Arc>())
+    .distMap(concepts::WriteMap<Node,VType>())
     .run(Node());
-  b=dijkstra(g,LengthMap())
-    .predMap(concepts::ReadWriteMap<Node,Arc>())
-    .distMap(concepts::ReadWriteMap<Node,VType>())
-    .processedMap(concepts::WriteMap<Node,bool>())
-    .path(concepts::Path<Digraph>())
-    .dist(VType())
-    .run(Node(),Node());
 }
 
@@ -129 +123 @@
 
   Path<Digraph> p = dijkstra_test.path(t);
-  check(p.length()==3,"path() found a wrong path.");
+  check(p.length()==3,"getPath() found a wrong path.");
   check(checkPath(G, p),"path() found a wrong path.");
   check(pathSource(G, p) == s,"path() found a wrong path.");
@@ -139 +133 @@
     check( !dijkstra_test.reached(u) ||
            (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
-           "Wrong output. dist(target)-dist(source)-arc_length=" <<
+           "dist(target)-dist(source)-arc_length= " <<
            dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
   }