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

@@ -30,2 +30,3 @@
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
@@ -115,3 +116,3 @@
 		  ///
-		  ///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
@@ -840,3 +841,3 @@
 		    ///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.
@@ -846,9 +847,5 @@
 		    ///\ref PredMap.
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#endif
+		    {
 		      return new PredMap();
+		      return new PredMap(g);
+		    }
@@ -859,2 +856,3 @@
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
@@ -893,4 +891,3 @@
 		    ///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.
@@ -900,10 +897,12 @@
 		    ///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;
 		  };
@@ -937,4 +936,6 @@
 		    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;
@@ -944,5 +945,5 @@
 		    /// 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) {}
@@ -950,10 +951,8 @@
 		    /// 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) {}
@@ -961,23 +960,11 @@
-		  /// 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>
@@ -1004,2 +991,4 @@
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the shortest paths
 		    typedef typename TR::Path Path;
@@ -1014,4 +1003,5 @@
 		    /// 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) {}
@@ -1022,39 +1012,57 @@
-		    ///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);
+		    }
@@ -1067,6 +1075,6 @@
 		    };
-		    ///\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.
@@ -1085,6 +1093,6 @@
 		    };
-		    ///\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.
@@ -1098,2 +1106,20 @@
 		    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 {
@@ -1103,6 +1129,6 @@
 		    };
-		    ///\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.
@@ -1116,17 +1142,27 @@
 		    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;
+		    }
@@ -1135,14 +1171,16 @@
-		  ///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
@@ -1154,5 +1192,5 @@
 		  BfsWizard<BfsWizardBase<GR> >
-		  bfs(const GR &g,typename GR::Node s=INVALID)
+		  bfs(const GR &digraph)
+		  {
-		    return BfsWizard<BfsWizardBase<GR> >(g,s);
+		    return BfsWizard<BfsWizardBase<GR> >(digraph);
+		  }

lemon/concepts/path.h

Show inline comments

@@ -67,3 +67,6 @@
 		      template <typename CPath>
-		      Path& operator=(const CPath& cpath) {}
 		      Path& operator=(const CPath& cpath) {
 		        ignore_unused_variable_warning(cpath);
 		        return *this;
+		      }

lemon/dfs.h

Show inline comments

@@ -31,2 +31,3 @@
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
@@ -116,3 +117,3 @@
 		  ///
-		  ///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
@@ -774,4 +775,3 @@
 		    ///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.
@@ -781,9 +781,5 @@
 		    ///\ref PredMap.
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#endif
+		    {
 		      return new PredMap();
+		      return new PredMap(g);
+		    }
@@ -794,2 +790,3 @@
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
@@ -828,4 +825,3 @@
 		    ///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.
@@ -835,10 +831,12 @@
 		    ///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;
 		  };
@@ -872,4 +870,6 @@
 		    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;
@@ -879,5 +879,5 @@
 		    /// 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) {}
@@ -885,10 +885,8 @@
 		    /// 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) {}
@@ -896,23 +894,11 @@
-		  /// 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>
@@ -931,3 +917,3 @@
 		    ///\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;
@@ -939,2 +925,4 @@
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the DFS paths
 		    typedef typename TR::Path Path;
@@ -949,4 +937,5 @@
 		    /// 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) {}
@@ -957,39 +946,57 @@
-		    ///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);
+		    }
@@ -1002,6 +1009,6 @@
 		    };
-		    ///\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.
@@ -1020,6 +1027,6 @@
 		    };
-		    ///\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.
@@ -1033,2 +1040,20 @@
 		    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 {
@@ -1038,6 +1063,6 @@
 		    };
-		    ///\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.
@@ -1051,17 +1076,27 @@
 		    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;
+		    }
@@ -1070,15 +1105,18 @@
-		  ///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()"
@@ -1089,5 +1127,5 @@
 		  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

@@ -32,2 +32,3 @@
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
@@ -198,3 +199,3 @@
 		  ///
-		  ///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
@@ -984,3 +985,3 @@
 		    ///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.
@@ -990,9 +991,5 @@
 		    ///\ref PredMap.
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#endif
+		    {
 		      return new PredMap();
+		      return new PredMap(g);
+		    }
@@ -1023,3 +1020,3 @@
 		    ///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.
@@ -1029,10 +1026,12 @@
 		    ///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;
 		  };
@@ -1057,3 +1056,3 @@
 		    void *_g;
 		    //Pointer to the length map
+		    //Pointer to the length map.
 		    void *_length;
@@ -1065,4 +1064,6 @@
 		    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;
@@ -1072,5 +1073,5 @@
 		    /// 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) {}
@@ -1078,12 +1079,10 @@
 		    /// 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) {}
@@ -1091,23 +1090,11 @@
-		  /// 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>
@@ -1136,2 +1123,4 @@
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the shortest paths
 		    typedef typename TR::Path Path;
 		    ///The heap type used by the dijkstra algorithm.
@@ -1148,4 +1137,6 @@
 		    /// 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) {}
@@ -1156,39 +1147,46 @@
-		    ///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);
+		    }
@@ -1201,6 +1199,6 @@
 		    };
-		    ///\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.
@@ -1214,2 +1212,20 @@
 		    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 {
@@ -1219,6 +1235,6 @@
 		    };
-		    ///\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.
@@ -1232,17 +1248,27 @@
 		    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;
+		    }
@@ -1251,14 +1277,16 @@
-		  ///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
@@ -1270,5 +1298,5 @@
 		  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

@@ -64,3 +64,2 @@
 		  BType::PredMap p(G);
 		  //  BType::PredNodeMap pn(G);
@@ -74,5 +73,3 @@
 		  d  = bfs_test.distMap();
 		  p  = bfs_test.predMap();
 		  //  pn = bfs_test.predNodeMap();
 		  b  = bfs_test.reached(n);
@@ -90,7 +87,9 @@
 		  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>())
@@ -98,2 +97,16 @@
 		    .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();
+		}
@@ -116,3 +129,3 @@
-		  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.");
@@ -130,3 +143,3 @@
 		           (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));
+		  }
@@ -142,4 +155,3 @@
 		              "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));
+		      }
@@ -147,2 +159,7 @@
+		  }
+		  {
 		    NullMap<Node,Arc> myPredMap;
 		    bfs(G).predMap(myPredMap).run(s);
+		  }
+		}

test/dfs_test.cc

Show inline comments

@@ -22,3 +22,2 @@
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dfs.h>
@@ -90,7 +89,9 @@
 		  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>())
@@ -98,2 +99,16 @@
 		    .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();
+		}
@@ -131,3 +146,3 @@
 		              "Wrong distance. (" << dfs_test.dist(u) << "->"
-		              <<dfs_test.dist(v) << ')');
+		              << dfs_test.dist(v) << ")");
+		      }
@@ -135,2 +150,7 @@
+		  }
+		  {
 		    NullMap<Node,Arc> myPredMap;
 		    dfs(G).predMap(myPredMap).run(s);
+		  }
+		}

test/dijkstra_test.cc

Show inline comments

@@ -22,3 +22,2 @@
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dijkstra.h>
@@ -66,3 +65,2 @@
 		  DType::PredMap p(G);
 		  //  DType::PredNodeMap pn(G);
 		  LengthMap length;
@@ -78,3 +76,2 @@
 		  p  = dijkstra_test.predMap();
 		  //  pn = dijkstra_test.predNodeMap();
 		  b  = dijkstra_test.reached(n);
@@ -93,8 +90,17 @@
 		  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());
+		}
@@ -124,3 +130,3 @@
 		  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.");
@@ -134,3 +140,3 @@
 		           (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