# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1222090403 -7200
# Node ID 93119005052016a1a5c54056a2e8cfb9769ab935
# Parent c691064dfd4f2e3d4e230a1fd9845a1d96de2a5d
Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)
- BfsWizard and DfsWizard have run(s), run(s,t), and run() functions,
DijkstraWizard has run(s) and run(s,t) functions.
- Set NodeMap<T> instead of NullMap as PredMap and DistMap in the default
traits classes for the function-type interface.
- Modify the related test files.
- Doc improvements.
- Bug fix in concepts/path.h.
diff -r c691064dfd4f -r 931190050520 lemon/bfs.h
--- a/lemon/bfs.h Thu Sep 11 11:10:44 2008 +0100
+++ b/lemon/bfs.h Mon Sep 22 15:33:23 2008 +0200
@@ -28,6 +28,7 @@
#include <lemon/core.h>
#include <lemon/error.h>
#include <lemon/maps.h>
+#include <lemon/path.h>
namespace lemon {
@@ -115,7 +116,7 @@
///\ingroup search
///This class provides an efficient implementation of the %BFS algorithm.
///
- ///There is also a \ref bfs() "function type interface" for the BFS
+ ///There is also a \ref bfs() "function-type interface" for the BFS
///algorithm, which is convenient in the simplier cases and it can be
///used easier.
///
@@ -841,26 +842,23 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
+ typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
///Instantiates a \ref PredMap.
///This function instantiates a \ref PredMap.
///\param g is the digraph, to which we would like to define the
///\ref PredMap.
///\todo The digraph alone may be insufficient to initialize
-#ifdef DOXYGEN
static PredMap *createPredMap(const Digraph &g)
-#else
- static PredMap *createPredMap(const Digraph &)
-#endif
{
- return new PredMap();
+ return new PredMap(g);
}
///The type of the map that indicates which nodes are processed.
///The type of the map that indicates which nodes are processed.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default it is a NullMap.
typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
///Instantiates a \ref ProcessedMap.
@@ -895,21 +893,22 @@
///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
- typedef NullMap<typename Digraph::Node,int> DistMap;
+ typedef typename Digraph::template NodeMap<int> DistMap;
///Instantiates a \ref DistMap.
///This function instantiates a \ref DistMap.
///\param g is the digraph, to which we would like to define
///the \ref DistMap
-#ifdef DOXYGEN
static DistMap *createDistMap(const Digraph &g)
-#else
- static DistMap *createDistMap(const Digraph &)
-#endif
{
- return new DistMap();
+ return new DistMap(g);
}
+
+ ///The type of the shortest paths.
+
+ ///The type of the shortest paths.
+ ///It must meet the \ref concepts::Path "Path" concept.
+ typedef lemon::Path<Digraph> Path;
};
/// Default traits class used by \ref BfsWizard
@@ -939,51 +938,39 @@
void *_pred;
//Pointer to the map of distances.
void *_dist;
- //Pointer to the source node.
- Node _source;
+ //Pointer to the shortest path to the target node.
+ void *_path;
+ //Pointer to the distance of the target node.
+ int *_di;
public:
/// Constructor.
/// This constructor does not require parameters, therefore it initiates
- /// all of the attributes to default values (0, INVALID).
+ /// all of the attributes to \c 0.
BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
- _dist(0), _source(INVALID) {}
+ _dist(0), _path(0), _di(0) {}
/// Constructor.
- /// This constructor requires some parameters,
- /// listed in the parameters list.
- /// Others are initiated to 0.
+ /// This constructor requires one parameter,
+ /// others are initiated to \c 0.
/// \param g The digraph the algorithm runs on.
- /// \param s The source node.
- BfsWizardBase(const GR &g, Node s=INVALID) :
+ BfsWizardBase(const GR &g) :
_g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
- _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
+ _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
};
- /// Auxiliary class for the function type interface of BFS algorithm.
+ /// Auxiliary class for the function-type interface of BFS algorithm.
- /// This auxiliary class is created to implement the function type
- /// interface of \ref Bfs algorithm. It uses the functions and features
- /// of the plain \ref Bfs, but it is much simpler to use it.
- /// It should only be used through the \ref bfs() function, which makes
- /// it easier to use the algorithm.
+ /// This auxiliary class is created to implement the
+ /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
+ /// It does not have own \ref run() method, it uses the functions
+ /// and features of the plain \ref Bfs.
///
- /// Simplicity means that the way to change the types defined
- /// in the traits class is based on functions that returns the new class
- /// and not on templatable built-in classes.
- /// When using the plain \ref Bfs
- /// the new class with the modified type comes from
- /// the original class by using the ::
- /// operator. In the case of \ref BfsWizard only
- /// a function have to be called, and it will
- /// return the needed class.
- ///
- /// It does not have own \ref run() method. When its \ref run() method
- /// is called, it initiates a plain \ref Bfs object, and calls the
- /// \ref Bfs::run() method of it.
+ /// This class should only be used through the \ref bfs() function,
+ /// which makes it easier to use the algorithm.
template<class TR>
class BfsWizard : public TR
{
@@ -1006,6 +993,8 @@
typedef typename TR::ReachedMap ReachedMap;
///\brief The type of the map that indicates which nodes are processed.
typedef typename TR::ProcessedMap ProcessedMap;
+ ///The type of the shortest paths
+ typedef typename TR::Path Path;
public:
@@ -1016,51 +1005,70 @@
/// Constructor that requires parameters.
/// These parameters will be the default values for the traits class.
- BfsWizard(const Digraph &g, Node s=INVALID) :
- TR(g,s) {}
+ /// \param g The digraph the algorithm runs on.
+ BfsWizard(const Digraph &g) :
+ TR(g) {}
///Copy constructor
BfsWizard(const TR &b) : TR(b) {}
~BfsWizard() {}
- ///Runs BFS algorithm from a source node.
+ ///Runs BFS algorithm from the given source node.
- ///Runs BFS algorithm from a source node.
- ///The node can be given with the \ref source() function.
+ ///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);
}
template<class T>
@@ -1069,10 +1077,10 @@
static PredMap *createPredMap(const Digraph &) { return 0; };
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref PredMap object.
///
- /// \ref named-templ-param "Named parameter"
+ ///\ref named-func-param "Named parameter"
///for setting \ref PredMap object.
template<class T>
BfsWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1087,10 +1095,10 @@
static ReachedMap *createReachedMap(const Digraph &) { return 0; };
SetReachedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ReachedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ReachedMap object.
template<class T>
BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
@@ -1100,15 +1108,33 @@
}
template<class T>
+ struct SetDistMapBase : public Base {
+ typedef T DistMap;
+ static DistMap *createDistMap(const Digraph &) { return 0; };
+ SetDistMapBase(const TR &b) : TR(b) {}
+ };
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting \ref DistMap object.
+ ///
+ /// \ref named-func-param "Named parameter"
+ ///for setting \ref DistMap object.
+ template<class T>
+ BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+ {
+ Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
+ return BfsWizard<SetDistMapBase<T> >(*this);
+ }
+
+ template<class T>
struct SetProcessedMapBase : public Base {
typedef T ProcessedMap;
static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
template<class T>
BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1118,37 +1144,49 @@
}
template<class T>
- struct SetDistMapBase : public Base {
- typedef T DistMap;
- static DistMap *createDistMap(const Digraph &) { return 0; };
- SetDistMapBase(const TR &b) : TR(b) {}
+ struct SetPathBase : public Base {
+ typedef T Path;
+ SetPathBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
///
- /// \ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
+ ///\ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
template<class T>
- BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+ BfsWizard<SetPathBase<T> > path(const T &t)
{
- Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
- return BfsWizard<SetDistMapBase<T> >(*this);
+ Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
+ return BfsWizard<SetPathBase<T> >(*this);
+ }
+
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the distance of the target node.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for getting the distance of the target node.
+ BfsWizard dist(const int &d)
+ {
+ Base::_di=const_cast<int*>(&d);
+ return *this;
}
};
- ///Function type interface for Bfs algorithm.
+ ///Function-type interface for BFS algorithm.
/// \ingroup search
- ///Function type interface for Bfs algorithm.
+ ///Function-type interface for BFS algorithm.
///
- ///This function also has several
- ///\ref named-templ-func-param "named parameters",
+ ///This function also has several \ref named-func-param "named parameters",
///they are declared as the members of class \ref BfsWizard.
- ///The following
- ///example shows how to use these parameters.
+ ///The following examples show how to use these parameters.
///\code
- /// bfs(g,source).predMap(preds).run();
+ /// // Compute shortest path from node s to each node
+ /// bfs(g).predMap(preds).distMap(dists).run(s);
+ ///
+ /// // Compute shortest path from s to t
+ /// bool reached = bfs(g).path(p).dist(d).run(s,t);
///\endcode
///\warning Don't forget to put the \ref BfsWizard::run() "run()"
///to the end of the parameter list.
@@ -1156,9 +1194,9 @@
///\sa Bfs
template<class GR>
BfsWizard<BfsWizardBase<GR> >
- bfs(const GR &g,typename GR::Node s=INVALID)
+ bfs(const GR &digraph)
{
- return BfsWizard<BfsWizardBase<GR> >(g,s);
+ return BfsWizard<BfsWizardBase<GR> >(digraph);
}
#ifdef DOXYGEN
diff -r c691064dfd4f -r 931190050520 lemon/concepts/path.h
--- a/lemon/concepts/path.h Thu Sep 11 11:10:44 2008 +0100
+++ b/lemon/concepts/path.h Mon Sep 22 15:33:23 2008 +0200
@@ -66,7 +66,10 @@
/// \brief Template assigment
template <typename CPath>
- Path& operator=(const CPath& cpath) {}
+ Path& operator=(const CPath& cpath) {
+ ignore_unused_variable_warning(cpath);
+ return *this;
+ }
/// Length of the path ie. the number of arcs in the path.
int length() const { return 0;}
diff -r c691064dfd4f -r 931190050520 lemon/dfs.h
--- a/lemon/dfs.h Thu Sep 11 11:10:44 2008 +0100
+++ b/lemon/dfs.h Mon Sep 22 15:33:23 2008 +0200
@@ -29,6 +29,7 @@
#include <lemon/error.h>
#include <lemon/assert.h>
#include <lemon/maps.h>
+#include <lemon/path.h>
namespace lemon {
@@ -116,7 +117,7 @@
///\ingroup search
///This class provides an efficient implementation of the %DFS algorithm.
///
- ///There is also a \ref dfs() "function type interface" for the DFS
+ ///There is also a \ref dfs() "function-type interface" for the DFS
///algorithm, which is convenient in the simplier cases and it can be
///used easier.
///
@@ -775,27 +776,23 @@
///The type of the map that stores the predecessor
///arcs of the %DFS paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
- typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
+ typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
///Instantiates a \ref PredMap.
///This function instantiates a \ref PredMap.
///\param g is the digraph, to which we would like to define the
///\ref PredMap.
///\todo The digraph alone may be insufficient to initialize
-#ifdef DOXYGEN
static PredMap *createPredMap(const Digraph &g)
-#else
- static PredMap *createPredMap(const Digraph &)
-#endif
{
- return new PredMap();
+ return new PredMap(g);
}
///The type of the map that indicates which nodes are processed.
///The type of the map that indicates which nodes are processed.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default it is a NullMap.
typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
///Instantiates a \ref ProcessedMap.
@@ -830,21 +827,22 @@
///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
- typedef NullMap<typename Digraph::Node,int> DistMap;
+ typedef typename Digraph::template NodeMap<int> DistMap;
///Instantiates a \ref DistMap.
///This function instantiates a \ref DistMap.
///\param g is the digraph, to which we would like to define
///the \ref DistMap
-#ifdef DOXYGEN
static DistMap *createDistMap(const Digraph &g)
-#else
- static DistMap *createDistMap(const Digraph &)
-#endif
{
- return new DistMap();
+ return new DistMap(g);
}
+
+ ///The type of the DFS paths.
+
+ ///The type of the DFS paths.
+ ///It must meet the \ref concepts::Path "Path" concept.
+ typedef lemon::Path<Digraph> Path;
};
/// Default traits class used by \ref DfsWizard
@@ -874,51 +872,39 @@
void *_pred;
//Pointer to the map of distances.
void *_dist;
- //Pointer to the source node.
- Node _source;
+ //Pointer to the DFS path to the target node.
+ void *_path;
+ //Pointer to the distance of the target node.
+ int *_di;
public:
/// Constructor.
/// This constructor does not require parameters, therefore it initiates
- /// all of the attributes to default values (0, INVALID).
+ /// all of the attributes to \c 0.
DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
- _dist(0), _source(INVALID) {}
+ _dist(0), _path(0), _di(0) {}
/// Constructor.
- /// This constructor requires some parameters,
- /// listed in the parameters list.
- /// Others are initiated to 0.
+ /// This constructor requires one parameter,
+ /// others are initiated to \c 0.
/// \param g The digraph the algorithm runs on.
- /// \param s The source node.
- DfsWizardBase(const GR &g, Node s=INVALID) :
+ DfsWizardBase(const GR &g) :
_g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
- _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
+ _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
};
- /// Auxiliary class for the function type interface of DFS algorithm.
+ /// Auxiliary class for the function-type interface of DFS algorithm.
- /// This auxiliary class is created to implement the function type
- /// interface of \ref Dfs algorithm. It uses the functions and features
- /// of the plain \ref Dfs, but it is much simpler to use it.
- /// It should only be used through the \ref dfs() function, which makes
- /// it easier to use the algorithm.
+ /// This auxiliary class is created to implement the
+ /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
+ /// It does not have own \ref run() method, it uses the functions
+ /// and features of the plain \ref Dfs.
///
- /// Simplicity means that the way to change the types defined
- /// in the traits class is based on functions that returns the new class
- /// and not on templatable built-in classes.
- /// When using the plain \ref Dfs
- /// the new class with the modified type comes from
- /// the original class by using the ::
- /// operator. In the case of \ref DfsWizard only
- /// a function have to be called, and it will
- /// return the needed class.
- ///
- /// It does not have own \ref run() method. When its \ref run() method
- /// is called, it initiates a plain \ref Dfs object, and calls the
- /// \ref Dfs::run() method of it.
+ /// This class should only be used through the \ref dfs() function,
+ /// which makes it easier to use the algorithm.
template<class TR>
class DfsWizard : public TR
{
@@ -933,7 +919,7 @@
typedef typename Digraph::OutArcIt OutArcIt;
///\brief The type of the map that stores the predecessor
- ///arcs of the shortest paths.
+ ///arcs of the DFS paths.
typedef typename TR::PredMap PredMap;
///\brief The type of the map that stores the distances of the nodes.
typedef typename TR::DistMap DistMap;
@@ -941,6 +927,8 @@
typedef typename TR::ReachedMap ReachedMap;
///\brief The type of the map that indicates which nodes are processed.
typedef typename TR::ProcessedMap ProcessedMap;
+ ///The type of the DFS paths
+ typedef typename TR::Path Path;
public:
@@ -951,51 +939,70 @@
/// Constructor that requires parameters.
/// These parameters will be the default values for the traits class.
- DfsWizard(const Digraph &g, Node s=INVALID) :
- TR(g,s) {}
+ /// \param g The digraph the algorithm runs on.
+ DfsWizard(const Digraph &g) :
+ TR(g) {}
///Copy constructor
DfsWizard(const TR &b) : TR(b) {}
~DfsWizard() {}
- ///Runs DFS algorithm from a source node.
+ ///Runs DFS algorithm from the given source node.
- ///Runs DFS algorithm from a source node.
- ///The node can be given with the \ref source() function.
+ ///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);
}
template<class T>
@@ -1004,10 +1011,10 @@
static PredMap *createPredMap(const Digraph &) { return 0; };
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref PredMap object.
///
- ///\ref named-templ-param "Named parameter"
+ ///\ref named-func-param "Named parameter"
///for setting \ref PredMap object.
template<class T>
DfsWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1022,10 +1029,10 @@
static ReachedMap *createReachedMap(const Digraph &) { return 0; };
SetReachedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ReachedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ReachedMap object.
template<class T>
DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
@@ -1035,15 +1042,33 @@
}
template<class T>
+ struct SetDistMapBase : public Base {
+ typedef T DistMap;
+ static DistMap *createDistMap(const Digraph &) { return 0; };
+ SetDistMapBase(const TR &b) : TR(b) {}
+ };
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting \ref DistMap object.
+ ///
+ /// \ref named-func-param "Named parameter"
+ ///for setting \ref DistMap object.
+ template<class T>
+ DfsWizard<SetDistMapBase<T> > distMap(const T &t)
+ {
+ Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
+ return DfsWizard<SetDistMapBase<T> >(*this);
+ }
+
+ template<class T>
struct SetProcessedMapBase : public Base {
typedef T ProcessedMap;
static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
template<class T>
DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1053,47 +1078,60 @@
}
template<class T>
- struct SetDistMapBase : public Base {
- typedef T DistMap;
- static DistMap *createDistMap(const Digraph &) { return 0; };
- SetDistMapBase(const TR &b) : TR(b) {}
+ struct SetPathBase : public Base {
+ typedef T Path;
+ SetPathBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the DFS path to the target node.
///
- ///\ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
+ ///\ref named-func-param "Named parameter"
+ ///for getting the DFS path to the target node.
template<class T>
- DfsWizard<SetDistMapBase<T> > distMap(const T &t)
+ DfsWizard<SetPathBase<T> > path(const T &t)
{
- Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
- return DfsWizard<SetDistMapBase<T> >(*this);
+ Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
+ return DfsWizard<SetPathBase<T> >(*this);
+ }
+
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the distance of the target node.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for getting the distance of the target node.
+ DfsWizard dist(const int &d)
+ {
+ Base::_di=const_cast<int*>(&d);
+ return *this;
}
};
- ///Function type interface for Dfs algorithm.
+ ///Function-type interface for DFS algorithm.
///\ingroup search
- ///Function type interface for Dfs algorithm.
+ ///Function-type interface for DFS algorithm.
///
- ///This function also has several
- ///\ref named-templ-func-param "named parameters",
+ ///This function also has several \ref named-func-param "named parameters",
///they are declared as the members of class \ref DfsWizard.
- ///The following
- ///example shows how to use these parameters.
+ ///The following examples show how to use these parameters.
///\code
- /// dfs(g,source).predMap(preds).run();
+ /// // Compute the DFS tree
+ /// dfs(g).predMap(preds).distMap(dists).run(s);
+ ///
+ /// // Compute the DFS path from s to t
+ /// bool reached = dfs(g).path(p).dist(d).run(s,t);
///\endcode
+
///\warning Don't forget to put the \ref DfsWizard::run() "run()"
///to the end of the parameter list.
///\sa DfsWizard
///\sa Dfs
template<class GR>
DfsWizard<DfsWizardBase<GR> >
- dfs(const GR &g,typename GR::Node s=INVALID)
+ dfs(const GR &digraph)
{
- return DfsWizard<DfsWizardBase<GR> >(g,s);
+ return DfsWizard<DfsWizardBase<GR> >(digraph);
}
#ifdef DOXYGEN
diff -r c691064dfd4f -r 931190050520 lemon/dijkstra.h
--- a/lemon/dijkstra.h Thu Sep 11 11:10:44 2008 +0100
+++ b/lemon/dijkstra.h Mon Sep 22 15:33:23 2008 +0200
@@ -30,6 +30,7 @@
#include <lemon/core.h>
#include <lemon/error.h>
#include <lemon/maps.h>
+#include <lemon/path.h>
namespace lemon {
@@ -199,7 +200,7 @@
///\ref concepts::ReadMap::Value "Value" of the length map.
///It is also possible to change the underlying priority heap.
///
- ///There is also a \ref dijkstra() "function type interface" for the
+ ///There is also a \ref dijkstra() "function-type interface" for the
///%Dijkstra algorithm, which is convenient in the simplier cases and
///it can be used easier.
///
@@ -987,20 +988,16 @@
///The type of the map that stores the predecessor
///arcs of the shortest paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
+ typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
///Instantiates a \ref PredMap.
///This function instantiates a \ref PredMap.
///\param g is the digraph, to which we would like to define the
///\ref PredMap.
///\todo The digraph alone may be insufficient to initialize
-#ifdef DOXYGEN
static PredMap *createPredMap(const Digraph &g)
-#else
- static PredMap *createPredMap(const Digraph &)
-#endif
{
- return new PredMap();
+ return new PredMap(g);
}
///The type of the map that indicates which nodes are processed.
@@ -1030,20 +1027,22 @@
///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- typedef NullMap<typename Digraph::Node,Value> DistMap;
+ typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
///Instantiates a \ref DistMap.
///This function instantiates a \ref DistMap.
///\param g is the digraph, to which we would like to define
///the \ref DistMap
-#ifdef DOXYGEN
static DistMap *createDistMap(const Digraph &g)
-#else
- static DistMap *createDistMap(const Digraph &)
-#endif
{
- return new DistMap();
+ return new DistMap(g);
}
+
+ ///The type of the shortest paths.
+
+ ///The type of the shortest paths.
+ ///It must meet the \ref concepts::Path "Path" concept.
+ typedef lemon::Path<Digraph> Path;
};
/// Default traits class used by \ref DijkstraWizard
@@ -1065,7 +1064,7 @@
//Pointer to the digraph the algorithm runs on.
void *_g;
- //Pointer to the length map
+ //Pointer to the length map.
void *_length;
//Pointer to the map of processed nodes.
void *_processed;
@@ -1073,53 +1072,41 @@
void *_pred;
//Pointer to the map of distances.
void *_dist;
- //Pointer to the source node.
- Node _source;
+ //Pointer to the shortest path to the target node.
+ void *_path;
+ //Pointer to the distance of the target node.
+ void *_di;
public:
/// Constructor.
/// This constructor does not require parameters, therefore it initiates
- /// all of the attributes to default values (0, INVALID).
+ /// all of the attributes to \c 0.
DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
- _dist(0), _source(INVALID) {}
+ _dist(0), _path(0), _di(0) {}
/// Constructor.
- /// This constructor requires some parameters,
- /// listed in the parameters list.
- /// Others are initiated to 0.
+ /// This constructor requires two parameters,
+ /// others are initiated to \c 0.
/// \param g The digraph the algorithm runs on.
/// \param l The length map.
- /// \param s The source node.
- DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
+ DijkstraWizardBase(const GR &g,const LM &l) :
_g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
_length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
- _processed(0), _pred(0), _dist(0), _source(s) {}
+ _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
};
- /// Auxiliary class for the function type interface of Dijkstra algorithm.
+ /// Auxiliary class for the function-type interface of Dijkstra algorithm.
- /// This auxiliary class is created to implement the function type
- /// interface of \ref Dijkstra algorithm. It uses the functions and features
- /// of the plain \ref Dijkstra, but it is much simpler to use it.
- /// It should only be used through the \ref dijkstra() function, which makes
- /// it easier to use the algorithm.
+ /// This auxiliary class is created to implement the
+ /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
+ /// It does not have own \ref run() method, it uses the functions
+ /// and features of the plain \ref Dijkstra.
///
- /// Simplicity means that the way to change the types defined
- /// in the traits class is based on functions that returns the new class
- /// and not on templatable built-in classes.
- /// When using the plain \ref Dijkstra
- /// the new class with the modified type comes from
- /// the original class by using the ::
- /// operator. In the case of \ref DijkstraWizard only
- /// a function have to be called, and it will
- /// return the needed class.
- ///
- /// It does not have own \ref run() method. When its \ref run() method
- /// is called, it initiates a plain \ref Dijkstra object, and calls the
- /// \ref Dijkstra::run() method of it.
+ /// This class should only be used through the \ref dijkstra() function,
+ /// which makes it easier to use the algorithm.
template<class TR>
class DijkstraWizard : public TR
{
@@ -1144,6 +1131,8 @@
typedef typename TR::DistMap DistMap;
///The type of the map that indicates which nodes are processed.
typedef typename TR::ProcessedMap ProcessedMap;
+ ///The type of the shortest paths
+ typedef typename TR::Path Path;
///The heap type used by the dijkstra algorithm.
typedef typename TR::Heap Heap;
@@ -1156,51 +1145,60 @@
/// Constructor that requires parameters.
/// These parameters will be the default values for the traits class.
- DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
- TR(g,l,s) {}
+ /// \param g The digraph the algorithm runs on.
+ /// \param l The length map.
+ DijkstraWizard(const Digraph &g, const LengthMap &l) :
+ TR(g,l) {}
///Copy constructor
DijkstraWizard(const TR &b) : TR(b) {}
~DijkstraWizard() {}
- ///Runs Dijkstra algorithm from a source node.
+ ///Runs Dijkstra algorithm from the given source node.
- ///Runs Dijkstra algorithm from a source node.
- ///The node can be given with the \ref source() function.
- void run()
+ ///This method runs %Dijkstra algorithm from the given source node
+ ///in order to compute the shortest path to each node.
+ void run(Node s)
{
- if(Base::_source==INVALID) throw UninitializedParameter();
+ if (s==INVALID) throw UninitializedParameter();
Dijkstra<Digraph,LengthMap,TR>
- dij(*reinterpret_cast<const Digraph*>(Base::_g),
- *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);
}
template<class T>
@@ -1209,10 +1207,10 @@
static PredMap *createPredMap(const Digraph &) { return 0; };
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref PredMap object.
///
- ///\ref named-templ-param "Named parameter"
+ ///\ref named-func-param "Named parameter"
///for setting \ref PredMap object.
template<class T>
DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1222,15 +1220,33 @@
}
template<class T>
+ struct SetDistMapBase : public Base {
+ typedef T DistMap;
+ static DistMap *createDistMap(const Digraph &) { return 0; };
+ SetDistMapBase(const TR &b) : TR(b) {}
+ };
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting \ref DistMap object.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for setting \ref DistMap object.
+ template<class T>
+ DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
+ {
+ Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
+ return DijkstraWizard<SetDistMapBase<T> >(*this);
+ }
+
+ template<class T>
struct SetProcessedMapBase : public Base {
typedef T ProcessedMap;
static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
template<class T>
DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1240,37 +1256,49 @@
}
template<class T>
- struct SetDistMapBase : public Base {
- typedef T DistMap;
- static DistMap *createDistMap(const Digraph &) { return 0; };
- SetDistMapBase(const TR &b) : TR(b) {}
+ struct SetPathBase : public Base {
+ typedef T Path;
+ SetPathBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
///
- ///\ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
+ ///\ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
template<class T>
- DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
+ DijkstraWizard<SetPathBase<T> > path(const T &t)
{
- Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
- return DijkstraWizard<SetDistMapBase<T> >(*this);
+ Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
+ return DijkstraWizard<SetPathBase<T> >(*this);
+ }
+
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the distance of the target node.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for getting the distance of the target node.
+ DijkstraWizard dist(const Value &d)
+ {
+ Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
+ return *this;
}
};
- ///Function type interface for Dijkstra algorithm.
+ ///Function-type interface for Dijkstra algorithm.
/// \ingroup shortest_path
- ///Function type interface for Dijkstra algorithm.
+ ///Function-type interface for Dijkstra algorithm.
///
- ///This function also has several
- ///\ref named-templ-func-param "named parameters",
+ ///This function also has several \ref named-func-param "named parameters",
///they are declared as the members of class \ref DijkstraWizard.
- ///The following
- ///example shows how to use these parameters.
+ ///The following examples show how to use these parameters.
///\code
- /// dijkstra(g,length,source).predMap(preds).run();
+ /// // Compute shortest path from node s to each node
+ /// dijkstra(g,length).predMap(preds).distMap(dists).run(s);
+ ///
+ /// // Compute shortest path from s to t
+ /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
///\endcode
///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
///to the end of the parameter list.
@@ -1278,9 +1306,9 @@
///\sa Dijkstra
template<class GR, class LM>
DijkstraWizard<DijkstraWizardBase<GR,LM> >
- dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
+ dijkstra(const GR &digraph, const LM &length)
{
- return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
+ return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
}
} //END OF NAMESPACE LEMON
diff -r c691064dfd4f -r 931190050520 test/bfs_test.cc
--- a/test/bfs_test.cc Thu Sep 11 11:10:44 2008 +0100
+++ b/test/bfs_test.cc Mon Sep 22 15:33:23 2008 +0200
@@ -62,7 +62,6 @@
bool b;
BType::DistMap d(G);
BType::PredMap p(G);
- // BType::PredNodeMap pn(G);
BType bfs_test(G);
@@ -72,9 +71,7 @@
e = bfs_test.predArc(n);
n = bfs_test.predNode(n);
d = bfs_test.distMap();
-
p = bfs_test.predMap();
- // pn = bfs_test.predNodeMap();
b = bfs_test.reached(n);
Path<Digraph> pp = bfs_test.path(n);
@@ -88,14 +85,30 @@
typedef Digraph::Node Node;
Digraph g;
- bfs(g,Node()).run();
- bfs(g).source(Node()).run();
+ bool b;
+ bfs(g).run(Node());
+ b=bfs(g).run(Node(),Node());
+ bfs(g).run();
bfs(g)
- .predMap(concepts::WriteMap<Node,Arc>())
- .distMap(concepts::WriteMap<Node,VType>())
+ .predMap(concepts::ReadWriteMap<Node,Arc>())
+ .distMap(concepts::ReadWriteMap<Node,VType>())
.reachedMap(concepts::ReadWriteMap<Node,bool>())
.processedMap(concepts::WriteMap<Node,bool>())
.run(Node());
+ b=bfs(g)
+ .predMap(concepts::ReadWriteMap<Node,Arc>())
+ .distMap(concepts::ReadWriteMap<Node,VType>())
+ .reachedMap(concepts::ReadWriteMap<Node,bool>())
+ .processedMap(concepts::WriteMap<Node,bool>())
+ .path(concepts::Path<Digraph>())
+ .dist(VType())
+ .run(Node(),Node());
+ bfs(g)
+ .predMap(concepts::ReadWriteMap<Node,Arc>())
+ .distMap(concepts::ReadWriteMap<Node,VType>())
+ .reachedMap(concepts::ReadWriteMap<Node,bool>())
+ .processedMap(concepts::WriteMap<Node,bool>())
+ .run();
}
template <class Digraph>
@@ -114,7 +127,7 @@
Bfs<Digraph> bfs_test(G);
bfs_test.run(s);
- check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
+ check(bfs_test.dist(t)==2,"Bfs found a wrong path.");
Path<Digraph> p = bfs_test.path(t);
check(p.length()==2,"path() found a wrong path.");
@@ -128,7 +141,7 @@
Node v=G.target(a);
check( !bfs_test.reached(u) ||
(bfs_test.dist(v) <= bfs_test.dist(u)+1),
- "Wrong output." << G.id(v) << ' ' << G.id(u));
+ "Wrong output. " << G.id(u) << "->" << G.id(v));
}
for(NodeIt v(G); v!=INVALID; ++v) {
@@ -140,11 +153,15 @@
check(u==bfs_test.predNode(v),"Wrong tree.");
check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
"Wrong distance. Difference: "
- << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
- - 1));
+ << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1));
}
}
}
+
+ {
+ NullMap<Node,Arc> myPredMap;
+ bfs(G).predMap(myPredMap).run(s);
+ }
}
int main()
diff -r c691064dfd4f -r 931190050520 test/dfs_test.cc
--- a/test/dfs_test.cc Thu Sep 11 11:10:44 2008 +0100
+++ b/test/dfs_test.cc Mon Sep 22 15:33:23 2008 +0200
@@ -20,7 +20,6 @@
#include <lemon/smart_graph.h>
#include <lemon/list_graph.h>
#include <lemon/lgf_reader.h>
-
#include <lemon/dfs.h>
#include <lemon/path.h>
@@ -88,14 +87,30 @@
typedef Digraph::Node Node;
Digraph g;
- dfs(g,Node()).run();
- dfs(g).source(Node()).run();
+ bool b;
+ dfs(g).run(Node());
+ b=dfs(g).run(Node(),Node());
+ dfs(g).run();
dfs(g)
- .predMap(concepts::WriteMap<Node,Arc>())
- .distMap(concepts::WriteMap<Node,VType>())
+ .predMap(concepts::ReadWriteMap<Node,Arc>())
+ .distMap(concepts::ReadWriteMap<Node,VType>())
.reachedMap(concepts::ReadWriteMap<Node,bool>())
.processedMap(concepts::WriteMap<Node,bool>())
.run(Node());
+ b=dfs(g)
+ .predMap(concepts::ReadWriteMap<Node,Arc>())
+ .distMap(concepts::ReadWriteMap<Node,VType>())
+ .reachedMap(concepts::ReadWriteMap<Node,bool>())
+ .processedMap(concepts::WriteMap<Node,bool>())
+ .path(concepts::Path<Digraph>())
+ .dist(VType())
+ .run(Node(),Node());
+ dfs(g)
+ .predMap(concepts::ReadWriteMap<Node,Arc>())
+ .distMap(concepts::ReadWriteMap<Node,VType>())
+ .reachedMap(concepts::ReadWriteMap<Node,bool>())
+ .processedMap(concepts::WriteMap<Node,bool>())
+ .run();
}
template <class Digraph>
@@ -129,10 +144,15 @@
check(u==dfs_test.predNode(v),"Wrong tree.");
check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
"Wrong distance. (" << dfs_test.dist(u) << "->"
- <<dfs_test.dist(v) << ')');
+ << dfs_test.dist(v) << ")");
}
}
}
+
+ {
+ NullMap<Node,Arc> myPredMap;
+ dfs(G).predMap(myPredMap).run(s);
+ }
}
int main()
diff -r c691064dfd4f -r 931190050520 test/dijkstra_test.cc
--- a/test/dijkstra_test.cc Thu Sep 11 11:10:44 2008 +0100
+++ b/test/dijkstra_test.cc Mon Sep 22 15:33:23 2008 +0200
@@ -20,7 +20,6 @@
#include <lemon/smart_graph.h>
#include <lemon/list_graph.h>
#include <lemon/lgf_reader.h>
-
#include <lemon/dijkstra.h>
#include <lemon/path.h>
@@ -64,7 +63,6 @@
bool b;
DType::DistMap d(G);
DType::PredMap p(G);
- // DType::PredNodeMap pn(G);
LengthMap length;
DType dijkstra_test(G,length);
@@ -76,7 +74,6 @@
n = dijkstra_test.predNode(n);
d = dijkstra_test.distMap();
p = dijkstra_test.predMap();
- // pn = dijkstra_test.predNodeMap();
b = dijkstra_test.reached(n);
Path<Digraph> pp = dijkstra_test.path(n);
@@ -91,12 +88,21 @@
typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
Digraph g;
- dijkstra(g,LengthMap(),Node()).run();
- dijkstra(g,LengthMap()).source(Node()).run();
+ bool b;
+ dijkstra(g,LengthMap()).run(Node());
+ b=dijkstra(g,LengthMap()).run(Node(),Node());
dijkstra(g,LengthMap())
- .predMap(concepts::WriteMap<Node,Arc>())
- .distMap(concepts::WriteMap<Node,VType>())
+ .predMap(concepts::ReadWriteMap<Node,Arc>())
+ .distMap(concepts::ReadWriteMap<Node,VType>())
+ .processedMap(concepts::WriteMap<Node,bool>())
.run(Node());
+ b=dijkstra(g,LengthMap())
+ .predMap(concepts::ReadWriteMap<Node,Arc>())
+ .distMap(concepts::ReadWriteMap<Node,VType>())
+ .processedMap(concepts::WriteMap<Node,bool>())
+ .path(concepts::Path<Digraph>())
+ .dist(VType())
+ .run(Node(),Node());
}
template <class Digraph>
@@ -122,7 +128,7 @@
check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
Path<Digraph> p = dijkstra_test.path(t);
- check(p.length()==3,"getPath() found a wrong path.");
+ check(p.length()==3,"path() found a wrong path.");
check(checkPath(G, p),"path() found a wrong path.");
check(pathSource(G, p) == s,"path() found a wrong path.");
check(pathTarget(G, p) == t,"path() found a wrong path.");
@@ -132,7 +138,7 @@
Node v=G.target(e);
check( !dijkstra_test.reached(u) ||
(dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
- "dist(target)-dist(source)-arc_length= " <<
+ "Wrong output. dist(target)-dist(source)-arc_length=" <<
dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
}