LEMON/LEMON-official Changeset - r281:e9b4fbe163f5

Repositories » LEMON » LEMON-official

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

Changeset - r281:e9b4fbe163f5

« 279:6307bb
« 280:e7f864

283:66bb22 »

r281:e9b4fbe163f5

Fri, 26 Sep 2008 09:52:28

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 7 0

merge default

4 files changed with 488 insertions and 338 deletions:

lemon/bfs.h

143

105

lemon/concepts/path.h

lemon/dfs.h

145

107

lemon/dijkstra.h

127

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 {
@@ -114,5 +115,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.
@@ -839,5 +840,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.
@@ -845,11 +846,7 @@
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#endif
+		    {
 		      return new PredMap();
+		      return new PredMap(g);
+		    }
@@ -858,4 +855,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.
@@ -892,6 +890,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.
@@ -899,12 +896,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;
 		  };
@@ -936,6 +935,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:
@@ -943,42 +944,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
@@ -1003,4 +990,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:
@@ -1013,6 +1002,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
@@ -1021,41 +1011,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.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    void run(Node s)
+		    {
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      if (s==INVALID || t==INVALID) throw UninitializedParameter();
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
 		      if (Base::_di)
 		        *Base::_di = alg.dist(t);
 		      return alg.reached(t);
+		    }
 		    ///Runs BFS algorithm to visit all nodes in the digraph.
 		    ///This method runs BFS algorithm in order to compute
 		    ///the shortest path to each node.
 		    void run()
+		    {
 		      if(Base::_source==INVALID) throw UninitializedParameter();
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if(Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if(Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if(Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if(Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      alg.run(Base::_source);
+		    }
 		    ///Runs BFS algorithm from the given node.
 		    ///Runs BFS algorithm from the given node.
 		    ///\param s is the given source.
 		    void run(Node s)
+		    {
 		      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);
+		    }
@@ -1066,8 +1074,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>
@@ -1084,8 +1092,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>
@@ -1097,4 +1105,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;
@@ -1102,8 +1128,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>
@@ -1115,35 +1141,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()"
@@ -1153,7 +1191,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

@@ -66,5 +66,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 {
@@ -115,5 +116,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.
@@ -773,6 +774,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.
@@ -780,11 +780,7 @@
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#endif
+		    {
 		      return new PredMap();
+		      return new PredMap(g);
+		    }
@@ -793,4 +789,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.
@@ -827,6 +824,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.
@@ -834,12 +830,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;
 		  };
@@ -871,6 +869,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:
@@ -878,42 +878,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
@@ -930,5 +916,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.
@@ -938,4 +924,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:
@@ -948,6 +936,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
@@ -956,41 +945,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.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
 		    void run(Node s)
+		    {
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the DFS path between \c s and \c t.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      if (s==INVALID || t==INVALID) throw UninitializedParameter();
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
 		      if (Base::_di)
 		        *Base::_di = alg.dist(t);
 		      return alg.reached(t);
+		      }
 		    ///Runs DFS algorithm to visit all nodes in the digraph.
 		    ///This method runs DFS algorithm in order to compute
 		    ///the DFS path to each node.
 		    void run()
+		    {
 		      if(Base::_source==INVALID) throw UninitializedParameter();
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if(Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if(Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if(Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if(Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      alg.run(Base::_source);
+		    }
 		    ///Runs DFS algorithm from the given node.
 		    ///Runs DFS algorithm from the given node.
 		    ///\param s is the given source.
 		    void run(Node s)
+		    {
 		      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);
+		    }
@@ -1001,8 +1008,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>
@@ -1019,8 +1026,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>
@@ -1032,4 +1039,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;
@@ -1037,8 +1062,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>
@@ -1050,36 +1075,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.
@@ -1088,7 +1126,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 {
@@ -197,5 +198,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.
@@ -983,5 +984,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.
@@ -989,11 +990,7 @@
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#endif
+		    {
 		      return new PredMap();
+		      return new PredMap(g);
+		    }
@@ -1022,5 +1019,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.
@@ -1028,12 +1025,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;
 		  };
@@ -1056,5 +1055,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.
@@ -1064,6 +1063,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:
@@ -1071,44 +1072,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
@@ -1135,4 +1122,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;
@@ -1147,6 +1136,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
@@ -1155,41 +1146,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),
 		            *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if(Base::_processed)
 		        dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if(Base::_pred)
 		        dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if(Base::_dist)
 		        dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
-		      dij.run(Base::_source);
+		        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);
+		    }
-		    ///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);
+		    }
@@ -1200,8 +1198,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>
@@ -1213,4 +1211,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;
@@ -1218,8 +1234,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>
@@ -1231,35 +1247,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()"
@@ -1269,7 +1297,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