LEMON/LEMON-official Changeset - r278:931190050520

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r278:931190050520

« 260:c69106

279:6307bb »

r278:931190050520

Mon, 22 Sep 2008 15:33:23

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

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.

0 7 0

default

7 files changed with 462 insertions and 312 deletions:

lemon/bfs.h

131

lemon/concepts/path.h

lemon/dfs.h

133

lemon/dijkstra.h

125

test/bfs_test.cc

test/dfs_test.cc

test/dijkstra_test.cc

↑ Collapse diff ↑

lemon/bfs.h

Show inline comments

@@ -29,4 +29,5 @@
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
@@ -116,5 +117,5 @@
 		  ///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.
@@ -842,5 +843,5 @@
 		    ///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.
@@ -849,11 +850,7 @@
 		    ///\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);
+		    }
@@ -862,4 +859,5 @@
 		    ///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.
@@ -896,6 +894,5 @@
 		    ///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,int> DistMap;
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \ref DistMap.
@@ -903,12 +900,14 @@
 		    ///\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;
 		  };
@@ -940,6 +939,8 @@
 		    //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.
 		    int *_di;
 		    public:
@@ -947,42 +948,28 @@
 		    /// 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.
 		    BfsWizardBase() : _g(0), _reached(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 one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param s The source node.
 		    BfsWizardBase(const GR &g, Node s=INVALID) :
 		    BfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
-		      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
+		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
-		  /// Auxiliary class for the function type interface of BFS algorithm.
+		  /// 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 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.
 		  ///
 		  /// 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.
+		  /// This class should only be used through the \ref bfs() function,
 		  /// which makes it easier to use the algorithm.
 		  template<class TR>
 		  class BfsWizard : public TR
@@ -1007,4 +994,6 @@
 		    ///\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:
@@ -1017,6 +1006,7 @@
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    BfsWizard(const Digraph &g, Node s=INVALID) :
 		      TR(g,s) {}
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
@@ -1025,41 +1015,59 @@
 		    ~BfsWizard() {}
-		    ///Runs BFS algorithm from a source node.
+		    ///Runs BFS algorithm from the given source node.
 		    ///Runs BFS algorithm from a source node.
 		    ///The node can be given with the \ref source() function.
-		    void run()
+		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    void run(Node s)
+		    {
 		      if(Base::_source==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));
 		      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));
-		      alg.run(Base::_source);
+		      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 from the given node.
+		    ///Runs BFS algorithm to visit all nodes in the digraph.
 		    ///Runs BFS algorithm from the given node.
 		    ///\param s is the given source.
-		    void run(Node s)
+		    ///This method runs BFS algorithm in order to compute
 		    ///the shortest path to each node.
 		    void run()
+		    {
 		      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;
 		      run(INVALID);
+		    }
@@ -1070,8 +1078,8 @@
 		      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>
@@ -1088,8 +1096,8 @@
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
-		    ///\brief \ref named-templ-param "Named parameter"
+		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    ///
-		    /// \ref named-templ-param "Named parameter"
+		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    template<class T>
@@ -1101,4 +1109,22 @@
 		    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>
 		    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
@@ -1106,8 +1132,8 @@
 		      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>
@@ -1119,35 +1145,47 @@
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    template<class T>
-		    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    BfsWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetDistMapBase<T> >(*this);
 		      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-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 BfsWizard.
 		  ///The following
 		  ///example shows how to use these parameters.
 		  ///The following examples show how to use these parameters.
 		  ///\code
-		  ///  bfs(g,source).predMap(preds).run();
+		  ///  // 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);
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
@@ -1157,7 +1195,7 @@
 		  template<class GR>
 		  BfsWizard<BfsWizardBase<GR> >
-		  bfs(const GR &g,typename GR::Node s=INVALID)
+		  bfs(const GR &digraph)
+		  {
-		    return BfsWizard<BfsWizardBase<GR> >(g,s);
+		    return BfsWizard<BfsWizardBase<GR> >(digraph);
+		  }

lemon/concepts/path.h

Show inline comments

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

lemon/dfs.h

Show inline comments

@@ -30,4 +30,5 @@
 		#include <lemon/assert.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
@@ -117,5 +118,5 @@
 		  ///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.
@@ -776,6 +777,5 @@
 		    ///arcs of the %DFS 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.
@@ -784,11 +784,7 @@
 		    ///\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);
+		    }
@@ -797,4 +793,5 @@
 		    ///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.
@@ -831,6 +828,5 @@
 		    ///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,int> DistMap;
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \ref DistMap.
@@ -838,12 +834,14 @@
 		    ///\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 DFS paths.
 		    ///The type of the DFS paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
@@ -875,6 +873,8 @@
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the source node.
 		    Node _source;
 		    //Pointer to the DFS path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
@@ -882,42 +882,28 @@
 		    /// 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.
 		    DfsWizardBase() : _g(0), _reached(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 one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param s The source node.
 		    DfsWizardBase(const GR &g, Node s=INVALID) :
 		    DfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
-		      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
+		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
-		  /// Auxiliary class for the function type interface of DFS algorithm.
+		  /// 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 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.
 		  ///
 		  /// 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.
+		  /// This class should only be used through the \ref dfs() function,
 		  /// which makes it easier to use the algorithm.
 		  template<class TR>
 		  class DfsWizard : public TR
@@ -934,5 +920,5 @@
 		    ///\brief The type of the map that stores the predecessor
-		    ///arcs of the shortest paths.
+		    ///arcs of the DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///\brief The type of the map that stores the distances of the nodes.
@@ -942,4 +928,6 @@
 		    ///\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:
@@ -952,6 +940,7 @@
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    DfsWizard(const Digraph &g, Node s=INVALID) :
 		      TR(g,s) {}
 		    /// \param g The digraph the algorithm runs on.
 		    DfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
@@ -960,41 +949,59 @@
 		    ~DfsWizard() {}
-		    ///Runs DFS algorithm from a source node.
+		    ///Runs DFS algorithm from the given source node.
 		    ///Runs DFS algorithm from a source node.
 		    ///The node can be given with the \ref source() function.
-		    void run()
+		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
 		    void run(Node s)
+		    {
 		      if(Base::_source==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));
 		      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));
-		      alg.run(Base::_source);
+		      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 from the given node.
+		    ///Runs DFS algorithm to visit all nodes in the digraph.
 		    ///Runs DFS algorithm from the given node.
 		    ///\param s is the given source.
-		    void run(Node s)
+		    ///This method runs DFS algorithm in order to compute
 		    ///the DFS path to each node.
 		    void run()
+		    {
 		      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;
 		      run(INVALID);
+		    }
@@ -1005,8 +1012,8 @@
 		      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>
@@ -1023,8 +1030,8 @@
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
-		    ///\brief \ref named-templ-param "Named parameter"
+		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    ///
-		    /// \ref named-templ-param "Named parameter"
+		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    template<class T>
@@ -1036,4 +1043,22 @@
 		    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>
 		    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
@@ -1041,8 +1066,8 @@
 		      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>
@@ -1054,36 +1079,49 @@
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the DFS path to the target node.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the DFS path to the target node.
 		    template<class T>
-		    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    DfsWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetDistMapBase<T> >(*this);
 		      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-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 DfsWizard.
 		  ///The following
 		  ///example shows how to use these parameters.
 		  ///The following examples show how to use these parameters.
 		  ///\code
-		  ///  dfs(g,source).predMap(preds).run();
+		  ///  // 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);
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
 		  ///to the end of the parameter list.
@@ -1092,7 +1130,7 @@
 		  template<class GR>
 		  DfsWizard<DfsWizardBase<GR> >
-		  dfs(const GR &g,typename GR::Node s=INVALID)
+		  dfs(const GR &digraph)
+		  {
-		    return DfsWizard<DfsWizardBase<GR> >(g,s);
+		    return DfsWizard<DfsWizardBase<GR> >(digraph);
+		  }

lemon/dijkstra.h

Show inline comments

@@ -31,4 +31,5 @@
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
@@ -200,5 +201,5 @@
 		  ///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,5 +989,5 @@
 		    ///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,11 +996,7 @@
 		    ///\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,5 +1028,5 @@
 		    ///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,12 +1034,14 @@
 		    ///\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,5 +1065,5 @@
 		    //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,6 +1073,8 @@
 		    //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,44 +1082,30 @@
 		    /// 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.
+		  /// 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 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,4 +1132,6 @@
 		    ///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,6 +1146,8 @@
 		    /// 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,41 +1156,48 @@
 		    ~DijkstraWizard() {}
-		    ///Runs Dijkstra algorithm from a source node.
+		    ///Runs Dijkstra algorithm from the given source node.
 		    ///Runs Dijkstra algorithm from a source node.
 		    ///The node can be given with the \ref source() function.
-		    void run()
+		    ///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(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::_pred)
 		        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      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);
 		        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      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.
 		    ///\param s is the given source.
-		    void run(Node s)
+		    ///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)
+		    {
 		      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;
 		      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,8 +1208,8 @@
 		      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>
@@ -1223,4 +1221,22 @@
 		    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;
@@ -1228,8 +1244,8 @@
 		      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,35 +1257,47 @@
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///\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)
+		    DijkstraWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DijkstraWizard<SetDistMapBase<T> >(*this);
 		      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,7 +1307,7 @@
 		  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);
+		  }

test/bfs_test.cc

Show inline comments

@@ -63,5 +63,4 @@
 		  BType::DistMap d(G);
 		  BType::PredMap p(G);
 		  //  BType::PredNodeMap pn(G);
 		  BType bfs_test(G);
@@ -73,7 +72,5 @@
 		  n  = bfs_test.predNode(n);
 		  d  = bfs_test.distMap();
 		  p  = bfs_test.predMap();
 		  //  pn = bfs_test.predNodeMap();
 		  b  = bfs_test.reached(n);
@@ -89,12 +86,28 @@
 		  Digraph g;
 		  bfs(g,Node()).run();
 		  bfs(g).source(Node()).run();
 		  bool b;
 		  bfs(g).run(Node());
 		  b=bfs(g).run(Node(),Node());
 		  bfs(g).run();
 		  bfs(g)
 		    .predMap(concepts::WriteMap<Node,Arc>())
 		    .distMap(concepts::WriteMap<Node,VType>())
 		    .predMap(concepts::ReadWriteMap<Node,Arc>())
 		    .distMap(concepts::ReadWriteMap<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();
+		}
@@ -115,5 +128,5 @@
 		  bfs_test.run(s);
-		  check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
 		  check(bfs_test.dist(t)==2,"Bfs found a wrong path.");
 		  Path<Digraph> p = bfs_test.path(t);
@@ -129,5 +142,5 @@
 		    check( !bfs_test.reached(u) ||
 		           (bfs_test.dist(v) <= bfs_test.dist(u)+1),
-		           "Wrong output." << G.id(v) << ' ' << G.id(u));
+		           "Wrong output. " << G.id(u) << "->" << G.id(v));
+		  }
@@ -141,9 +154,13 @@
 		        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

Show inline comments

@@ -21,5 +21,4 @@
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dfs.h>
 		#include <lemon/path.h>
@@ -89,12 +88,28 @@
 		  Digraph g;
 		  dfs(g,Node()).run();
 		  dfs(g).source(Node()).run();
 		  bool b;
 		  dfs(g).run(Node());
 		  b=dfs(g).run(Node(),Node());
 		  dfs(g).run();
 		  dfs(g)
 		    .predMap(concepts::WriteMap<Node,Arc>())
 		    .distMap(concepts::WriteMap<Node,VType>())
 		    .predMap(concepts::ReadWriteMap<Node,Arc>())
 		    .distMap(concepts::ReadWriteMap<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();
+		}
@@ -130,8 +145,13 @@
 		        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

Show inline comments

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

0 comments (0 inline)

RhodeCode

Login to your account