LEMON/LEMON-main Changeset - r278:931190050520

Repositories » LEMON » LEMON-main

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

@@ -28,6 +28,7 @@
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
@@ -115,7 +116,7 @@
 		  ///\ingroup search
 		  ///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.
 		  ///
@@ -841,26 +842,23 @@
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-		    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
+		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#endif
+		    {
 		      return new PredMap();
+		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///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.
@@ -895,21 +893,22 @@
 		    ///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.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const Digraph &g)
 		#else
 		    static DistMap *createDistMap(const Digraph &)
 		#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;
 		  };
 		  /// Default traits class used by \ref BfsWizard
@@ -939,51 +938,39 @@
 		    void *_pred;
 		    //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:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
-		    /// all of the attributes to default values (0, INVALID).
+		    /// all of the attributes to \c 0.
 		    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
+		  {
@@ -1006,6 +993,8 @@
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\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:
@@ -1016,51 +1005,70 @@
 		    /// 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
 		    BfsWizard(const TR &b) : TR(b) {}
 		    ~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);
+		    }
 		    template<class T>
@@ -1069,10 +1077,10 @@
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
-		    ///\brief \ref named-templ-param "Named parameter"
+		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    ///
-		    /// \ref named-templ-param "Named parameter"
+		    ///\ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    template<class T>
 		    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1087,10 +1095,10 @@
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      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>
 		    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
@@ -1100,15 +1108,33 @@
+		    }
 		    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;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
-		    ///\brief \ref named-templ-param "Named parameter"
+		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    ///
-		    /// \ref named-templ-param "Named parameter"
+		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    template<class T>
 		    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1118,37 +1144,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 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()"
 		  ///to the end of the parameter list.
@@ -1156,9 +1194,9 @@
 		  ///\sa Bfs
 		  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);
+		  }
 		#ifdef DOXYGEN

lemon/concepts/path.h

Show inline comments

@@ -66,7 +66,10 @@
 		      /// \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.
 		      int length() const { return 0;}

lemon/dfs.h

Show inline comments

@@ -29,6 +29,7 @@
 		#include <lemon/error.h>
 		#include <lemon/assert.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
@@ -116,7 +117,7 @@
 		  ///\ingroup search
 		  ///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.
 		  ///
@@ -775,27 +776,23 @@
 		    ///The type of the map that stores the predecessor
 		    ///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.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#endif
+		    {
 		      return new PredMap();
+		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///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.
@@ -830,21 +827,22 @@
 		    ///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.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const Digraph &g)
 		#else
 		    static DistMap *createDistMap(const Digraph &)
 		#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;
 		  };
 		  /// Default traits class used by \ref DfsWizard
@@ -874,51 +872,39 @@
 		    void *_pred;
 		    //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:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
-		    /// all of the attributes to default values (0, INVALID).
+		    /// all of the attributes to \c 0.
 		    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
+		  {
@@ -933,7 +919,7 @@
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\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.
 		    typedef typename TR::DistMap DistMap;
@@ -941,6 +927,8 @@
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\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:
@@ -951,51 +939,70 @@
 		    /// 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
 		    DfsWizard(const TR &b) : TR(b) {}
 		    ~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);
+		    }
 		    template<class T>
@@ -1004,10 +1011,10 @@
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
-		    ///\brief \ref named-templ-param "Named parameter"
+		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    ///
-		    ///\ref named-templ-param "Named parameter"
+		    ///\ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    template<class T>
 		    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1022,10 +1029,10 @@
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      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>
 		    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
@@ -1035,15 +1042,33 @@
+		    }
 		    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;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
-		    ///\brief \ref named-templ-param "Named parameter"
+		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    ///
-		    /// \ref named-templ-param "Named parameter"
+		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    template<class T>
 		    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1053,47 +1078,60 @@
+		    }
 		    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.
 		  ///\sa DfsWizard
 		  ///\sa Dfs
 		  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);
+		  }
 		#ifdef DOXYGEN

lemon/dijkstra.h

Show inline comments

@@ -30,6 +30,7 @@
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
@@ -199,7 +200,7 @@
 		  ///\ref concepts::ReadMap::Value "Value" of the length map.
 		  ///It is also possible to change the underlying priority heap.
 		  ///
-		  ///There is also a \ref dijkstra() "function type interface" for the
+		  ///There is also a \ref dijkstra() "function-type interface" for the
 		  ///%Dijkstra algorithm, which is convenient in the simplier cases and
 		  ///it can be used easier.
 		  ///
@@ -987,20 +988,16 @@
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-		    typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
+		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#endif
+		    {
 		      return new PredMap();
+		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
@@ -1030,20 +1027,22 @@
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-		    typedef NullMap<typename Digraph::Node,Value> DistMap;
+		    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const Digraph &g)
 		#else
 		    static DistMap *createDistMap(const Digraph &)
 		#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;
 		  };
 		  /// Default traits class used by \ref DijkstraWizard
@@ -1065,7 +1064,7 @@
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the length map
+		    //Pointer to the length map.
 		    void *_length;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
@@ -1073,53 +1072,41 @@
 		    void *_pred;
 		    //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:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
-		    /// all of the attributes to default values (0, INVALID).
+		    /// all of the attributes to \c 0.
 		    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
-		                           _dist(0), _source(INVALID) {}
+		                           _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// 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
+		  {
@@ -1144,6 +1131,8 @@
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the shortest paths
 		    typedef typename TR::Path Path;
 		    ///The heap type used by the dijkstra algorithm.
 		    typedef typename TR::Heap Heap;
@@ -1156,51 +1145,60 @@
 		    /// 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
 		    DijkstraWizard(const TR &b) : TR(b) {}
 		    ~DijkstraWizard() {}
-		    ///Runs Dijkstra algorithm from a source node.
+		    ///Runs Dijkstra algorithm from the given source node.
 		    ///Runs Dijkstra algorithm from a source node.
 		    ///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);
+		    }
 		    template<class T>
@@ -1209,10 +1207,10 @@
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
-		    ///\brief \ref named-templ-param "Named parameter"
+		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    ///
-		    ///\ref named-templ-param "Named parameter"
+		    ///\ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    template<class T>
 		    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1222,15 +1220,33 @@
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    template<class T>
 		    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DijkstraWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
-		    ///\brief \ref named-templ-param "Named parameter"
+		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    ///
-		    /// \ref named-templ-param "Named parameter"
+		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    template<class T>
 		    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1240,37 +1256,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 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()"
 		  ///to the end of the parameter list.
@@ -1278,9 +1306,9 @@
 		  ///\sa Dijkstra
 		  template<class GR, class LM>
 		  DijkstraWizard<DijkstraWizardBase<GR,LM> >
-		  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
+		  dijkstra(const GR &digraph, const LM &length)
+		  {
-		    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
+		    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
+		  }
 		} //END OF NAMESPACE LEMON

test/bfs_test.cc

Show inline comments

@@ -62,7 +62,6 @@
 		  bool b;
 		  BType::DistMap d(G);
 		  BType::PredMap p(G);
 		  //  BType::PredNodeMap pn(G);
 		  BType bfs_test(G);
@@ -72,9 +71,7 @@
 		  e  = bfs_test.predArc(n);
 		  n  = bfs_test.predNode(n);
 		  d  = bfs_test.distMap();
 		  p  = bfs_test.predMap();
 		  //  pn = bfs_test.predNodeMap();
 		  b  = bfs_test.reached(n);
 		  Path<Digraph> pp = bfs_test.path(n);
@@ -88,14 +85,30 @@
 		  typedef Digraph::Node Node;
 		  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();
+		}
 		template <class Digraph>
@@ -114,7 +127,7 @@
 		  Bfs<Digraph> bfs_test(G);
 		  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);
 		  check(p.length()==2,"path() found a wrong path.");
@@ -128,7 +141,7 @@
 		    Node v=G.target(a);
 		    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));
+		  }
 		  for(NodeIt v(G); v!=INVALID; ++v) {
@@ -140,11 +153,15 @@
 		        check(u==bfs_test.predNode(v),"Wrong tree.");
 		        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);
+		  }
+		}
 		int main()

test/dfs_test.cc

Show inline comments

@@ -20,7 +20,6 @@
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dfs.h>
 		#include <lemon/path.h>
@@ -88,14 +87,30 @@
 		  typedef Digraph::Node Node;
 		  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();
+		}
 		template <class Digraph>
@@ -129,10 +144,15 @@
 		        check(u==dfs_test.predNode(v),"Wrong tree.");
 		        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);
+		  }
+		}
 		int main()

test/dijkstra_test.cc

Show inline comments

@@ -20,7 +20,6 @@
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/path.h>
@@ -64,7 +63,6 @@
 		  bool b;
 		  DType::DistMap d(G);
 		  DType::PredMap p(G);
 		  //  DType::PredNodeMap pn(G);
 		  LengthMap length;
 		  DType dijkstra_test(G,length);
@@ -76,7 +74,6 @@
 		  n  = dijkstra_test.predNode(n);
 		  d  = dijkstra_test.distMap();
 		  p  = dijkstra_test.predMap();
 		  //  pn = dijkstra_test.predNodeMap();
 		  b  = dijkstra_test.reached(n);
 		  Path<Digraph> pp = dijkstra_test.path(n);
@@ -91,12 +88,21 @@
 		  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
 		  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());
+		}
 		template <class Digraph>
@@ -122,7 +128,7 @@
 		  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
 		  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.");
 		  check(pathTarget(G, p) == t,"path() found a wrong path.");
@@ -132,7 +138,7 @@
 		    Node v=G.target(e);
 		    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