Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt (revision 274)
+++ CMakeLists.txt (revision 236)
@@ -1,6 +1,15 @@
CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
+#EXECUTE_PROCESS(
+# COMMAND hg id -i
+# OUTPUT_VARIABLE HG_REVISION
+# OUTPUT_STRIP_TRAILING_WHITESPACE)
+
SET(PROJECT_NAME "LEMON")
-SET(PROJECT_VERSION "hg-tip" CACHE STRING "The version string.")
+SET(PROJECT_VERSION_MAJOR "0")
+SET(PROJECT_VERSION_MINOR "99")
+SET(PROJECT_VERSION_PATCH "0")
+SET(PROJECT_VERSION
+ "${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")
PROJECT(${PROJECT_NAME})
@@ -31,10 +40,13 @@
SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
+ SET(CPACK_PACKAGE_VERSION_MAJOR ${PROJECT_VERSION_MAJOR})
+ SET(CPACK_PACKAGE_VERSION_MINOR ${PROJECT_VERSION_MINOR})
+ SET(CPACK_PACKAGE_VERSION_PATCH ${PROJECT_VERSION_PATCH})
SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
SET(CPACK_PACKAGE_INSTALL_DIRECTORY
- "${PROJECT_NAME} ${PROJECT_VERSION}")
+ "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}")
SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
- "${PROJECT_NAME} ${PROJECT_VERSION}")
+ "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")
# Variables to generate a component-based installer.
Index: NEWS
===================================================================
--- NEWS (revision 262)
+++ NEWS (revision 5)
@@ -1,49 +1,0 @@
-20XX-XX-XX Version 1.0 released
-
- This is the first stable release of LEMON. Compared to the 0.x
- release series, it features a considerably smaller but more
- matured set of tools. The API has also completely revised and
- changed in several places.
-
- * The major name changes compared to the 0.x series
- * Graph -> Digraph, UGraph -> Graph
- * Edge -> Arc, UEdge -> Edge
- * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
- * Other improvements
- * Better documentation
- * Reviewed and cleaned up codebase
- * CMake based build system (along with the autotools based one)
- * Contents of the library (ported from 0.x)
- * Algorithms
- * breadth-first search (bfs.h)
- * depth-first search (dfs.h)
- * Dijkstra's algorithm (dijkstra.h)
- * Kruskal's algorithm (kruskal.h)
- * Data structures
- * graph data structures (list_graph.h, smart_graph.h)
- * path data structures (path.h)
- * binary heap data structure (bin_heap.h)
- * union-find data structures (unionfind.h)
- * miscellaneous property maps (maps.h)
- * two dimensional vector and bounding box (dim2.h)
- * Concepts
- * graph structure concepts (concepts/digraph.h, concepts/graph.h,
- concepts/graph_components.h)
- * concepts for other structures (concepts/heap.h, concepts/maps.h,
- concepts/path.h)
- * Tools
- * Mersenne twister random number generator (random.h)
- * tools for measuring cpu and wall clock time (time_measure.h)
- * tools for counting steps and events (counter.h)
- * tool for parsing command line arguments (arg_parser.h)
- * tool for visualizing graphs (graph_to_eps.h)
- * tools for reading and writing data in LEMON Graph Format
- (lgf_reader.h, lgf_writer.h)
- * tools to handle the anomalies of calculations with
- floating point numbers (tolerance.h)
- * tools to manage RGB colors (color.h)
- * Infrastructure
- * extended assertion handling (assert.h)
- * exception classes and error handling (error.h)
- * concept checking (concept_check.h)
- * commonly used mathematical constants (math.h)
Index: configure.ac
===================================================================
--- configure.ac (revision 273)
+++ configure.ac (revision 259)
@@ -2,13 +2,7 @@
dnl Version information.
-m4_define([lemon_version_number],
- [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
-dnl m4_define([lemon_version_number], [])
-m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
+m4_define([lemon_version_number], [])
m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
-m4_define([lemon_version], [ifelse(lemon_version_number(),
- [],
- [lemon_hg_path().lemon_hg_revision()],
- [lemon_version_number()])])
+m4_define([lemon_version], [ifelse(lemon_version_number(), [], [lemon_hg_revision()], [lemon_version_number()])])
AC_PREREQ([2.59])
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 270)
+++ doc/Makefile.am (revision 227)
@@ -7,5 +7,4 @@
doc/license.dox \
doc/mainpage.dox \
- doc/named-param.dox \
doc/namespaces.dox \
doc/html \
Index: c/named-param.dox
===================================================================
--- doc/named-param.dox (revision 269)
+++ (revision )
@@ -1,119 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2008
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-/*!
-
-\page named-param Named Parameters
-
-\section named-func-param Named Function Parameters
-
-Several modern languages provide a convenient way to refer the
-function parameters by name also when you call the function. It is
-especially comfortable in case of a function having tons of parameters
-with natural default values. Sadly, C++ lack this amenity.
-
-However, with a crafty trick and with some little
-inconvenience, it is possible to emulate is.
-The example below shows how to do it.
-
-\code
-class namedFn
-{
- int _id;
- double _val;
- int _dim;
-
- public:
- namedFn() : _id(0), _val(1), _dim(2) {}
- namedFn& id(int p) { _id = p ; return *this; }
- namedFn& val(double p) { _val = p ; return *this; }
- namedFn& dim(int p) { _dim = p ; return *this; }
-
- run() {
- std::cout << "Here comes the function itself\n" <<
- << "With parameters "
- << _id << ", " << _val << ", " << _dim << std::endl;
- }
-};
-\endcode
-
-Then you can use it like this.
-
-\code
-namedFn().id(3).val(2).run();
-\endcode
-
-The trick is obvious, each "named parameter" changes one component of
-the underlying class, then gives back a reference to it. Finally,
-run() executes the algorithm itself.
-
-\note Although it is a class, namedFn is used pretty much like as it were
-a function. That it why we called it namedFn instead of \c NamedFn.
-
-\note In fact, the final .run() could be made unnecessary,
-because the algorithm could also be implemented in the destructor of
-\c namedFn instead. This however would make it impossible to implement
-functions with return values, and would also cause serious problems when
-implementing \ref named-templ-func-param "named template parameters".
-Therefore, by convention, .run() must be used
-explicitly to execute a function having named parameters
-everywhere in LEMON.
-
-\section named-templ-func-param Named Function Template Parameters
-
-A named parameter can also be a template function. The usage is
-exactly the same, but the implementation behind is a kind of black
-magic and they are the dirtiest part of the LEMON code.
-
-You will probably never need to know how it works, but if you really
-committed, have a look at \ref lemon/graph_to_eps.h for an example.
-
-\section traits-classes Traits Classes
-
-A similar game can also be played when defining classes. In this case
-the type of the class attributes can be changed. Initially we have to
-define a special class called Traits Class defining the
-default type of the attributes. Then the types of these attributes can
-be changed in the same way as described in the next section.
-
-See \ref lemon::DijkstraDefaultTraits for an
-example how a traits class implementation looks like.
-
-\section named-templ-param Named Class Template Parameters
-
-If we would like to change the type of an attribute in a class that
-was instantiated by using a traits class as a template parameter, and
-the class contains named parameters, we do not have to instantiate again
-the class with new traits class, but instead adaptor classes can
-be used as shown in the following example.
-
-\code
-Dijkstra<>::SetPredMap >::Create
-\endcode
-
-It can also be used in conjunction with other named template
-parameters in arbitrary order.
-
-\code
-Dijkstra<>::SetDistMap::SetPredMap >::Create
-\endcode
-
-The result will be an instantiated Dijkstra class, in which the
-DistMap and the PredMap is modified.
-
-*/
Index: lemon/arg_parser.h
===================================================================
--- lemon/arg_parser.h (revision 261)
+++ lemon/arg_parser.h (revision 214)
@@ -17,6 +17,6 @@
*/
-#ifndef LEMON_ARG_PARSER_H
-#define LEMON_ARG_PARSER_H
+#ifndef LEMON_ARG_PARSER
+#define LEMON_ARG_PARSER
#include
@@ -383,3 +383,3 @@
}
-#endif // LEMON_ARG_PARSER_H
+#endif // LEMON_ARG_PARSER
Index: lemon/assert.h
===================================================================
--- lemon/assert.h (revision 277)
+++ lemon/assert.h (revision 218)
@@ -28,7 +28,6 @@
namespace lemon {
- inline void assert_fail_abort(const char *file, int line,
- const char *function, const char* message,
- const char *assertion)
+ inline void assert_fail_log(const char *file, int line, const char *function,
+ const char *message, const char *assertion)
{
std::cerr << file << ":" << line << ": ";
@@ -39,4 +38,11 @@
std::cerr << " (assertion '" << assertion << "' failed)";
std::cerr << std::endl;
+ }
+
+ inline void assert_fail_abort(const char *file, int line,
+ const char *function, const char* message,
+ const char *assertion)
+ {
+ assert_fail_log(file, line, function, message, assertion);
std::abort();
}
@@ -58,12 +64,15 @@
#undef LEMON_ASSERT
+#undef LEMON_FIXME
#undef LEMON_DEBUG
-#if (defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \
+#if (defined(LEMON_ASSERT_LOG) ? 1 : 0) + \
+ (defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1
#error "LEMON assertion system is not set properly"
#endif
-#if ((defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \
+#if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) + \
+ (defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 || \
defined(LEMON_ENABLE_ASSERTS)) && \
@@ -74,5 +83,8 @@
-#if defined LEMON_ASSERT_ABORT
+#if defined LEMON_ASSERT_LOG
+# undef LEMON_ASSERT_HANDLER
+# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log
+#elif defined LEMON_ASSERT_ABORT
# undef LEMON_ASSERT_HANDLER
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort
@@ -96,8 +108,6 @@
# elif defined _MSC_VER
# define LEMON_FUNCTION_NAME (__FUNCSIG__)
-# elif __STDC_VERSION__ >= 199901L
+# else
# define LEMON_FUNCTION_NAME (__func__)
-# else
-# define LEMON_FUNCTION_NAME ("")
# endif
#endif
@@ -109,10 +119,10 @@
/// \brief Macro for assertion with customizable message
///
-/// Macro for assertion with customizable message.
-/// \param exp An expression that must be convertible to \c bool. If it is \c
-/// false, then an assertion is raised. The concrete behaviour depends on the
-/// settings of the assertion system.
-/// \param msg A const char* parameter, which can be used to provide
-/// information about the circumstances of the failed assertion.
+/// Macro for assertion with customizable message. \param exp An
+/// expression that must be convertible to \c bool. If it is \c
+/// false, then an assertion is raised. The concrete behaviour depends
+/// on the settings of the assertion system. \param msg A const
+/// char* parameter, which can be used to provide information
+/// about the circumstances of the failed assertion.
///
/// The assertions are enabled in the default behaviour.
@@ -128,10 +138,15 @@
/// The checking is also disabled when the standard macro \c NDEBUG is defined.
///
-/// As a default behaviour the failed assertion prints a short log message to
-/// the standard error and aborts the execution.
-///
-/// However, the following modes can be used in the assertion system:
-/// - \c LEMON_ASSERT_ABORT The failed assertion prints a short log message to
-/// the standard error and aborts the program. It is the default behaviour.
+/// The LEMON assertion system has a wide range of customization
+/// properties. As a default behaviour the failed assertion prints a
+/// short log message to the standard error and aborts the execution.
+///
+/// The following modes can be used in the assertion system:
+///
+/// - \c LEMON_ASSERT_LOG The failed assertion prints a short log
+/// message to the standard error and continues the execution.
+/// - \c LEMON_ASSERT_ABORT This mode is similar to the \c
+/// LEMON_ASSERT_LOG, but it aborts the program. It is the default
+/// behaviour.
/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler
/// function.
@@ -161,4 +176,20 @@
/// \ingroup exceptions
///
+/// \brief Macro for mark not yet implemented features.
+///
+/// Macro for mark not yet implemented features and outstanding bugs.
+/// It is close to be the shortcut of the following code:
+/// \code
+/// LEMON_ASSERT(false, msg);
+/// \endcode
+///
+/// \see LEMON_ASSERT
+# define LEMON_FIXME(msg) \
+ (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME, \
+ ::lemon::_assert_bits::cstringify(msg), \
+ static_cast(0)))
+
+/// \ingroup exceptions
+///
/// \brief Macro for internal assertions
///
@@ -192,4 +223,5 @@
# ifndef LEMON_ASSERT_HANDLER
# define LEMON_ASSERT(exp, msg) (static_cast(0))
+# define LEMON_FIXME(msg) (static_cast(0))
# define LEMON_DEBUG(exp, msg) (static_cast(0))
# else
@@ -200,4 +232,9 @@
::lemon::_assert_bits::cstringify(msg), \
#exp), 0)))
+# define LEMON_FIXME(msg) \
+ (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME, \
+ ::lemon::_assert_bits::cstringify(msg), \
+ static_cast(0)))
+
# if LEMON_ENABLE_DEBUG
# define LEMON_DEBUG(exp, msg) \
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 258)
+++ lemon/bfs.h (revision 278)
@@ -29,4 +29,5 @@
#include
#include
+#include
namespace lemon {
@@ -116,5 +117,5 @@
///This class provides an efficient implementation of the %BFS algorithm.
///
- ///There is also a \ref bfs() "function type interface" for the BFS
+ ///There is also a \ref bfs() "function-type interface" for the BFS
///algorithm, which is convenient in the simplier cases and it can be
///used easier.
@@ -842,5 +843,5 @@
///arcs of the shortest paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- typedef NullMap PredMap;
+ typedef typename Digraph::template NodeMap PredMap;
///Instantiates a \ref PredMap.
@@ -849,11 +850,7 @@
///\ref PredMap.
///\todo The digraph alone may be insufficient to initialize
-#ifdef DOXYGEN
static PredMap *createPredMap(const Digraph &g)
-#else
- static PredMap *createPredMap(const Digraph &)
-#endif
- {
- return new PredMap();
+ {
+ return new PredMap(g);
}
@@ -862,4 +859,5 @@
///The type of the map that indicates which nodes are processed.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a \ref ProcessedMap.
@@ -896,6 +894,5 @@
///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
- typedef NullMap DistMap;
+ typedef typename Digraph::template NodeMap DistMap;
///Instantiates a \ref DistMap.
@@ -903,12 +900,14 @@
///\param g is the digraph, to which we would like to define
///the \ref DistMap
-#ifdef DOXYGEN
static DistMap *createDistMap(const Digraph &g)
-#else
- static DistMap *createDistMap(const Digraph &)
-#endif
- {
- return new DistMap();
- }
+ {
+ return new DistMap(g);
+ }
+
+ ///The type of the shortest paths.
+
+ ///The type of the shortest paths.
+ ///It must meet the \ref concepts::Path "Path" concept.
+ typedef lemon::Path Path;
};
@@ -940,6 +939,8 @@
//Pointer to the map of distances.
void *_dist;
- //Pointer to the source node.
- Node _source;
+ //Pointer to the shortest path to the target node.
+ void *_path;
+ //Pointer to the distance of the target node.
+ int *_di;
public:
@@ -947,42 +948,28 @@
/// This constructor does not require parameters, therefore it initiates
- /// all of the attributes to default values (0, INVALID).
+ /// all of the attributes to \c 0.
BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
- _dist(0), _source(INVALID) {}
+ _dist(0), _path(0), _di(0) {}
/// Constructor.
- /// This constructor requires some parameters,
- /// listed in the parameters list.
- /// Others are initiated to 0.
+ /// This constructor requires one parameter,
+ /// others are initiated to \c 0.
/// \param g The digraph the algorithm runs on.
- /// \param s The source node.
- BfsWizardBase(const GR &g, Node s=INVALID) :
+ BfsWizardBase(const GR &g) :
_g(reinterpret_cast(const_cast(&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.
-
- /// 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.
+ /// Auxiliary class for the function-type interface of BFS 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 BfsWizard : public TR
@@ -1007,4 +994,6 @@
///\brief The type of the map that indicates which nodes are processed.
typedef typename TR::ProcessedMap ProcessedMap;
+ ///The type of the shortest paths
+ typedef typename TR::Path Path;
public:
@@ -1017,6 +1006,7 @@
/// Constructor that requires parameters.
/// These parameters will be the default values for the traits class.
- BfsWizard(const Digraph &g, Node s=INVALID) :
- TR(g,s) {}
+ /// \param g The digraph the algorithm runs on.
+ BfsWizard(const Digraph &g) :
+ TR(g) {}
///Copy constructor
@@ -1025,41 +1015,59 @@
~BfsWizard() {}
- ///Runs BFS algorithm from a source node.
-
- ///Runs BFS algorithm from a source node.
- ///The node can be given with the \ref source() function.
+ ///Runs BFS algorithm from the given source node.
+
+ ///This method runs BFS algorithm from node \c s
+ ///in order to compute the shortest path to each node.
+ void run(Node s)
+ {
+ Bfs alg(*reinterpret_cast(Base::_g));
+ if (Base::_pred)
+ alg.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist)
+ alg.distMap(*reinterpret_cast(Base::_dist));
+ if (Base::_reached)
+ alg.reachedMap(*reinterpret_cast(Base::_reached));
+ if (Base::_processed)
+ alg.processedMap(*reinterpret_cast(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 alg(*reinterpret_cast(Base::_g));
+ if (Base::_pred)
+ alg.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist)
+ alg.distMap(*reinterpret_cast(Base::_dist));
+ if (Base::_reached)
+ alg.reachedMap(*reinterpret_cast(Base::_reached));
+ if (Base::_processed)
+ alg.processedMap(*reinterpret_cast(Base::_processed));
+ alg.run(s,t);
+ if (Base::_path)
+ *reinterpret_cast(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 alg(*reinterpret_cast(Base::_g));
- if(Base::_reached)
- alg.reachedMap(*reinterpret_cast(Base::_reached));
- if(Base::_processed)
- alg.processedMap(*reinterpret_cast(Base::_processed));
- if(Base::_pred)
- alg.predMap(*reinterpret_cast(Base::_pred));
- if(Base::_dist)
- alg.distMap(*reinterpret_cast(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 &source(Node s)
- {
- Base::_source=s;
- return *this;
+ run(INVALID);
}
@@ -1070,8 +1078,8 @@
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref PredMap object.
///
- /// \ref named-templ-param "Named parameter"
+ ///\ref named-func-param "Named parameter"
///for setting \ref PredMap object.
template
@@ -1088,8 +1096,8 @@
SetReachedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ReachedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ReachedMap object.
template
@@ -1098,4 +1106,22 @@
Base::_reached=reinterpret_cast(const_cast(&t));
return BfsWizard >(*this);
+ }
+
+ template
+ 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
+ BfsWizard > distMap(const T &t)
+ {
+ Base::_dist=reinterpret_cast(const_cast(&t));
+ return BfsWizard >(*this);
}
@@ -1106,8 +1132,8 @@
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
template
@@ -1119,35 +1145,47 @@
template
- struct SetDistMapBase : public Base {
- typedef T DistMap;
- static DistMap *createDistMap(const Digraph &) { return 0; };
- SetDistMapBase(const TR &b) : TR(b) {}
- };
- ///\brief \ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
- ///
- /// \ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
+ struct SetPathBase : public Base {
+ typedef T Path;
+ SetPathBase(const TR &b) : TR(b) {}
+ };
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
template
- BfsWizard > distMap(const T &t)
- {
- Base::_dist=reinterpret_cast(const_cast(&t));
- return BfsWizard >(*this);
+ BfsWizard > path(const T &t)
+ {
+ Base::_path=reinterpret_cast(const_cast(&t));
+ return BfsWizard >(*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(&d);
+ return *this;
}
};
- ///Function type interface for Bfs algorithm.
+ ///Function-type interface for BFS algorithm.
/// \ingroup search
- ///Function type interface for Bfs algorithm.
+ ///Function-type interface for BFS algorithm.
///
- ///This function also has several
- ///\ref named-templ-func-param "named parameters",
+ ///This function also has several \ref named-func-param "named parameters",
///they are declared as the members of class \ref BfsWizard.
- ///The following
- ///example shows how to use these parameters.
+ ///The following examples show how to use these parameters.
///\code
- /// bfs(g,source).predMap(preds).run();
+ /// // Compute shortest path from node s to each node
+ /// bfs(g).predMap(preds).distMap(dists).run(s);
+ ///
+ /// // Compute shortest path from s to t
+ /// bool reached = bfs(g).path(p).dist(d).run(s,t);
///\endcode
///\warning Don't forget to put the \ref BfsWizard::run() "run()"
@@ -1157,7 +1195,7 @@
template
BfsWizard >
- bfs(const GR &g,typename GR::Node s=INVALID)
+ bfs(const GR &digraph)
{
- return BfsWizard >(g,s);
+ return BfsWizard >(digraph);
}
Index: lemon/bits/array_map.h
===================================================================
--- lemon/bits/array_map.h (revision 263)
+++ lemon/bits/array_map.h (revision 209)
@@ -104,5 +104,4 @@
}
- private:
/// \brief Constructor to copy a map of the same map type.
///
@@ -152,5 +151,4 @@
}
- public:
/// \brief The destructor of the map.
///
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h (revision 263)
+++ lemon/bits/graph_extender.h (revision 220)
@@ -228,5 +228,4 @@
: Parent(digraph, value) {}
- private:
NodeMap& operator=(const NodeMap& cmap) {
return operator=(cmap);
@@ -253,5 +252,4 @@
: Parent(digraph, value) {}
- private:
ArcMap& operator=(const ArcMap& cmap) {
return operator=(cmap);
@@ -611,5 +609,4 @@
: Parent(graph, value) {}
- private:
NodeMap& operator=(const NodeMap& cmap) {
return operator=(cmap);
@@ -636,5 +633,4 @@
: Parent(graph, value) {}
- private:
ArcMap& operator=(const ArcMap& cmap) {
return operator=(cmap);
@@ -662,5 +658,4 @@
: Parent(graph, value) {}
- private:
EdgeMap& operator=(const EdgeMap& cmap) {
return operator=(cmap);
Index: lemon/bits/map_extender.h
===================================================================
--- lemon/bits/map_extender.h (revision 263)
+++ lemon/bits/map_extender.h (revision 209)
@@ -63,5 +63,4 @@
: Parent(graph, value) {}
- private:
MapExtender& operator=(const MapExtender& cmap) {
return operator=(cmap);
@@ -74,5 +73,4 @@
}
- public:
class MapIt : public Item {
public:
@@ -203,5 +201,4 @@
: Parent(_graph, _value), graph(_graph) {}
- private:
SubMapExtender& operator=(const SubMapExtender& cmap) {
return operator=(cmap);
@@ -218,5 +215,4 @@
}
- public:
class MapIt : public Item {
public:
Index: lemon/bits/vector_map.h
===================================================================
--- lemon/bits/vector_map.h (revision 263)
+++ lemon/bits/vector_map.h (revision 220)
@@ -101,5 +101,4 @@
}
- private:
/// \brief Copy constructor
///
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h (revision 263)
+++ lemon/concepts/digraph.h (revision 220)
@@ -435,5 +435,4 @@
NodeMap(const Digraph&, T) { }
- private:
///Copy constructor
NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
@@ -458,5 +457,4 @@
///\e
ArcMap(const Digraph&, T) { }
- private:
///Copy constructor
ArcMap(const ArcMap& em) : ReadWriteMap(em) { }
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h (revision 263)
+++ lemon/concepts/graph.h (revision 220)
@@ -513,5 +513,4 @@
NodeMap(const Graph&, T) { }
- private:
///Copy constructor
NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
@@ -537,5 +536,4 @@
///\e
ArcMap(const Graph&, T) { }
- private:
///Copy constructor
ArcMap(const ArcMap& em) : ReadWriteMap(em) { }
@@ -561,5 +559,4 @@
///\e
EdgeMap(const Graph&, T) { }
- private:
///Copy constructor
EdgeMap(const EdgeMap& em) : ReadWriteMap(em) {}
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h (revision 263)
+++ lemon/concepts/graph_components.h (revision 220)
@@ -1006,6 +1006,4 @@
/// Construct a new map for the graph and initalise the values.
GraphMap(const Graph&, const Value&) {}
-
- private:
/// \brief Copy constructor.
///
@@ -1024,5 +1022,4 @@
}
- public:
template
struct Constraints {
@@ -1034,12 +1031,11 @@
_Map a2(g,t);
// Copy constructor.
- // _Map b(c);
-
- // ReadMap cmap;
- // b = cmap;
-
- ignore_unused_variable_warning(a);
+ _Map b(c);
+
+ ReadMap cmap;
+ b = cmap;
+
ignore_unused_variable_warning(a2);
- // ignore_unused_variable_warning(b);
+ ignore_unused_variable_warning(b);
}
@@ -1087,5 +1083,4 @@
: Parent(digraph, value) {}
- private:
/// \brief Copy constructor.
///
@@ -1125,5 +1120,4 @@
: Parent(digraph, value) {}
- private:
/// \brief Copy constructor.
///
@@ -1222,5 +1216,4 @@
: Parent(graph, value) {}
- private:
/// \brief Copy constructor.
///
Index: lemon/concepts/path.h
===================================================================
--- lemon/concepts/path.h (revision 236)
+++ lemon/concepts/path.h (revision 278)
@@ -67,5 +67,8 @@
/// \brief Template assigment
template
- 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.
Index: lemon/dfs.h
===================================================================
--- lemon/dfs.h (revision 258)
+++ lemon/dfs.h (revision 278)
@@ -30,4 +30,5 @@
#include
#include
+#include
namespace lemon {
@@ -117,5 +118,5 @@
///This class provides an efficient implementation of the %DFS algorithm.
///
- ///There is also a \ref dfs() "function type interface" for the DFS
+ ///There is also a \ref dfs() "function-type interface" for the DFS
///algorithm, which is convenient in the simplier cases and it can be
///used easier.
@@ -776,6 +777,5 @@
///arcs of the %DFS paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
- typedef NullMap PredMap;
+ typedef typename Digraph::template NodeMap PredMap;
///Instantiates a \ref PredMap.
@@ -784,11 +784,7 @@
///\ref PredMap.
///\todo The digraph alone may be insufficient to initialize
-#ifdef DOXYGEN
static PredMap *createPredMap(const Digraph &g)
-#else
- static PredMap *createPredMap(const Digraph &)
-#endif
- {
- return new PredMap();
+ {
+ return new PredMap(g);
}
@@ -797,4 +793,5 @@
///The type of the map that indicates which nodes are processed.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+ ///By default it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a \ref ProcessedMap.
@@ -831,6 +828,5 @@
///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
- typedef NullMap DistMap;
+ typedef typename Digraph::template NodeMap DistMap;
///Instantiates a \ref DistMap.
@@ -838,12 +834,14 @@
///\param g is the digraph, to which we would like to define
///the \ref DistMap
-#ifdef DOXYGEN
static DistMap *createDistMap(const Digraph &g)
-#else
- static DistMap *createDistMap(const Digraph &)
-#endif
- {
- return new DistMap();
- }
+ {
+ return new DistMap(g);
+ }
+
+ ///The type of the DFS paths.
+
+ ///The type of the DFS paths.
+ ///It must meet the \ref concepts::Path "Path" concept.
+ typedef lemon::Path Path;
};
@@ -875,6 +873,8 @@
//Pointer to the map of distances.
void *_dist;
- //Pointer to the source node.
- Node _source;
+ //Pointer to the DFS path to the target node.
+ void *_path;
+ //Pointer to the distance of the target node.
+ int *_di;
public:
@@ -882,42 +882,28 @@
/// This constructor does not require parameters, therefore it initiates
- /// all of the attributes to default values (0, INVALID).
+ /// all of the attributes to \c 0.
DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
- _dist(0), _source(INVALID) {}
+ _dist(0), _path(0), _di(0) {}
/// Constructor.
- /// This constructor requires some parameters,
- /// listed in the parameters list.
- /// Others are initiated to 0.
+ /// This constructor requires one parameter,
+ /// others are initiated to \c 0.
/// \param g The digraph the algorithm runs on.
- /// \param s The source node.
- DfsWizardBase(const GR &g, Node s=INVALID) :
+ DfsWizardBase(const GR &g) :
_g(reinterpret_cast(const_cast(&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.
-
- /// 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.
+ /// Auxiliary class for the function-type interface of DFS 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 DfsWizard : public TR
@@ -934,5 +920,5 @@
///\brief The type of the map that stores the predecessor
- ///arcs of the shortest paths.
+ ///arcs of the DFS paths.
typedef typename TR::PredMap PredMap;
///\brief The type of the map that stores the distances of the nodes.
@@ -942,4 +928,6 @@
///\brief The type of the map that indicates which nodes are processed.
typedef typename TR::ProcessedMap ProcessedMap;
+ ///The type of the DFS paths
+ typedef typename TR::Path Path;
public:
@@ -952,6 +940,7 @@
/// Constructor that requires parameters.
/// These parameters will be the default values for the traits class.
- DfsWizard(const Digraph &g, Node s=INVALID) :
- TR(g,s) {}
+ /// \param g The digraph the algorithm runs on.
+ DfsWizard(const Digraph &g) :
+ TR(g) {}
///Copy constructor
@@ -960,41 +949,59 @@
~DfsWizard() {}
- ///Runs DFS algorithm from a source node.
-
- ///Runs DFS algorithm from a source node.
- ///The node can be given with the \ref source() function.
+ ///Runs DFS algorithm from the given source node.
+
+ ///This method runs DFS algorithm from node \c s
+ ///in order to compute the DFS path to each node.
+ void run(Node s)
+ {
+ Dfs alg(*reinterpret_cast(Base::_g));
+ if (Base::_pred)
+ alg.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist)
+ alg.distMap(*reinterpret_cast(Base::_dist));
+ if (Base::_reached)
+ alg.reachedMap(*reinterpret_cast(Base::_reached));
+ if (Base::_processed)
+ alg.processedMap(*reinterpret_cast(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 alg(*reinterpret_cast(Base::_g));
+ if (Base::_pred)
+ alg.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist)
+ alg.distMap(*reinterpret_cast(Base::_dist));
+ if (Base::_reached)
+ alg.reachedMap(*reinterpret_cast(Base::_reached));
+ if (Base::_processed)
+ alg.processedMap(*reinterpret_cast(Base::_processed));
+ alg.run(s,t);
+ if (Base::_path)
+ *reinterpret_cast(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 alg(*reinterpret_cast(Base::_g));
- if(Base::_reached)
- alg.reachedMap(*reinterpret_cast(Base::_reached));
- if(Base::_processed)
- alg.processedMap(*reinterpret_cast(Base::_processed));
- if(Base::_pred)
- alg.predMap(*reinterpret_cast(Base::_pred));
- if(Base::_dist)
- alg.distMap(*reinterpret_cast(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 &source(Node s)
- {
- Base::_source=s;
- return *this;
+ run(INVALID);
}
@@ -1005,8 +1012,8 @@
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref PredMap object.
///
- ///\ref named-templ-param "Named parameter"
+ ///\ref named-func-param "Named parameter"
///for setting \ref PredMap object.
template
@@ -1023,8 +1030,8 @@
SetReachedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ReachedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ReachedMap object.
template
@@ -1033,4 +1040,22 @@
Base::_reached=reinterpret_cast(const_cast(&t));
return DfsWizard >(*this);
+ }
+
+ template
+ 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
+ DfsWizard > distMap(const T &t)
+ {
+ Base::_dist=reinterpret_cast(const_cast(&t));
+ return DfsWizard >(*this);
}
@@ -1041,8 +1066,8 @@
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
template
@@ -1054,36 +1079,49 @@
template
- struct SetDistMapBase : public Base {
- typedef T DistMap;
- static DistMap *createDistMap(const Digraph &) { return 0; };
- SetDistMapBase(const TR &b) : TR(b) {}
- };
- ///\brief \ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
- ///
- ///\ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
+ struct SetPathBase : public Base {
+ typedef T Path;
+ SetPathBase(const TR &b) : TR(b) {}
+ };
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the DFS path to the target node.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for getting the DFS path to the target node.
template
- DfsWizard > distMap(const T &t)
- {
- Base::_dist=reinterpret_cast(const_cast(&t));
- return DfsWizard >(*this);
+ DfsWizard > path(const T &t)
+ {
+ Base::_path=reinterpret_cast(const_cast(&t));
+ return DfsWizard >(*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(&d);
+ return *this;
}
};
- ///Function type interface for Dfs algorithm.
+ ///Function-type interface for DFS algorithm.
///\ingroup search
- ///Function type interface for Dfs algorithm.
+ ///Function-type interface for DFS algorithm.
///
- ///This function also has several
- ///\ref named-templ-func-param "named parameters",
+ ///This function also has several \ref named-func-param "named parameters",
///they are declared as the members of class \ref DfsWizard.
- ///The following
- ///example shows how to use these parameters.
+ ///The following examples show how to use these parameters.
///\code
- /// dfs(g,source).predMap(preds).run();
+ /// // Compute the DFS tree
+ /// dfs(g).predMap(preds).distMap(dists).run(s);
+ ///
+ /// // Compute the DFS path from s to t
+ /// bool reached = dfs(g).path(p).dist(d).run(s,t);
///\endcode
+
///\warning Don't forget to put the \ref DfsWizard::run() "run()"
///to the end of the parameter list.
@@ -1092,7 +1130,7 @@
template
DfsWizard >
- dfs(const GR &g,typename GR::Node s=INVALID)
+ dfs(const GR &digraph)
{
- return DfsWizard >(g,s);
+ return DfsWizard >(digraph);
}
Index: lemon/dijkstra.h
===================================================================
--- lemon/dijkstra.h (revision 258)
+++ lemon/dijkstra.h (revision 278)
@@ -31,4 +31,5 @@
#include
#include
+#include
namespace lemon {
@@ -200,5 +201,5 @@
///It is also possible to change the underlying priority heap.
///
- ///There is also a \ref dijkstra() "function type interface" for the
+ ///There is also a \ref dijkstra() "function-type interface" for the
///%Dijkstra algorithm, which is convenient in the simplier cases and
///it can be used easier.
@@ -988,5 +989,5 @@
///arcs of the shortest paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- typedef NullMap PredMap;
+ typedef typename Digraph::template NodeMap PredMap;
///Instantiates a \ref PredMap.
@@ -995,11 +996,7 @@
///\ref PredMap.
///\todo The digraph alone may be insufficient to initialize
-#ifdef DOXYGEN
static PredMap *createPredMap(const Digraph &g)
-#else
- static PredMap *createPredMap(const Digraph &)
-#endif
- {
- return new PredMap();
+ {
+ return new PredMap(g);
}
@@ -1031,5 +1028,5 @@
///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- typedef NullMap DistMap;
+ typedef typename Digraph::template NodeMap DistMap;
///Instantiates a \ref DistMap.
@@ -1037,12 +1034,14 @@
///\param g is the digraph, to which we would like to define
///the \ref DistMap
-#ifdef DOXYGEN
static DistMap *createDistMap(const Digraph &g)
-#else
- static DistMap *createDistMap(const Digraph &)
-#endif
- {
- return new DistMap();
- }
+ {
+ return new DistMap(g);
+ }
+
+ ///The type of the shortest paths.
+
+ ///The type of the shortest paths.
+ ///It must meet the \ref concepts::Path "Path" concept.
+ typedef lemon::Path Path;
};
@@ -1066,5 +1065,5 @@
//Pointer to the digraph the algorithm runs on.
void *_g;
- //Pointer to the length map
+ //Pointer to the length map.
void *_length;
//Pointer to the map of processed nodes.
@@ -1074,6 +1073,8 @@
//Pointer to the map of distances.
void *_dist;
- //Pointer to the source node.
- Node _source;
+ //Pointer to the shortest path to the target node.
+ void *_path;
+ //Pointer to the distance of the target node.
+ void *_di;
public:
@@ -1081,44 +1082,30 @@
/// This constructor does not require parameters, therefore it initiates
- /// all of the attributes to default values (0, INVALID).
+ /// all of the attributes to \c 0.
DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
- _dist(0), _source(INVALID) {}
+ _dist(0), _path(0), _di(0) {}
/// Constructor.
- /// This constructor requires some parameters,
- /// listed in the parameters list.
- /// Others are initiated to 0.
+ /// This constructor requires two parameters,
+ /// others are initiated to \c 0.
/// \param g The digraph the algorithm runs on.
/// \param l The length map.
- /// \param s The source node.
- DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
+ DijkstraWizardBase(const GR &g,const LM &l) :
_g(reinterpret_cast(const_cast(&g))),
_length(reinterpret_cast(const_cast(&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.
-
- /// 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.
+ /// Auxiliary class for the function-type interface of Dijkstra 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 DijkstraWizard : public TR
@@ -1145,4 +1132,6 @@
///The type of the map that indicates which nodes are processed.
typedef typename TR::ProcessedMap ProcessedMap;
+ ///The type of the shortest paths
+ typedef typename TR::Path Path;
///The heap type used by the dijkstra algorithm.
typedef typename TR::Heap Heap;
@@ -1157,6 +1146,8 @@
/// Constructor that requires parameters.
/// These parameters will be the default values for the traits class.
- DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
- TR(g,l,s) {}
+ /// \param g The digraph the algorithm runs on.
+ /// \param l The length map.
+ DijkstraWizard(const Digraph &g, const LengthMap &l) :
+ TR(g,l) {}
///Copy constructor
@@ -1165,41 +1156,48 @@
~DijkstraWizard() {}
- ///Runs Dijkstra algorithm from a source node.
-
- ///Runs Dijkstra algorithm from a source node.
- ///The node can be given with the \ref source() function.
- void run()
- {
- if(Base::_source==INVALID) throw UninitializedParameter();
+ ///Runs Dijkstra algorithm from the given source node.
+
+ ///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 (s==INVALID) throw UninitializedParameter();
Dijkstra
- dij(*reinterpret_cast(Base::_g),
- *reinterpret_cast(Base::_length));
- if(Base::_processed)
- dij.processedMap(*reinterpret_cast(Base::_processed));
- if(Base::_pred)
- dij.predMap(*reinterpret_cast(Base::_pred));
- if(Base::_dist)
- dij.distMap(*reinterpret_cast(Base::_dist));
- dij.run(Base::_source);
- }
-
- ///Runs Dijkstra algorithm from the given node.
-
- ///Runs Dijkstra 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 Dijkstra algorithm runs.
-
- /// Sets the source node, from which the Dijkstra algorithm runs.
- /// \param s is the source node.
- DijkstraWizard &source(Node s)
- {
- Base::_source=s;
- return *this;
+ dijk(*reinterpret_cast(Base::_g),
+ *reinterpret_cast(Base::_length));
+ if (Base::_pred)
+ dijk.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist)
+ dijk.distMap(*reinterpret_cast(Base::_dist));
+ if (Base::_processed)
+ dijk.processedMap(*reinterpret_cast(Base::_processed));
+ dijk.run(s);
+ }
+
+ ///Finds the shortest path between \c s and \c t.
+
+ ///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)
+ {
+ if (s==INVALID || t==INVALID) throw UninitializedParameter();
+ Dijkstra
+ dijk(*reinterpret_cast(Base::_g),
+ *reinterpret_cast(Base::_length));
+ if (Base::_pred)
+ dijk.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist)
+ dijk.distMap(*reinterpret_cast(Base::_dist));
+ if (Base::_processed)
+ dijk.processedMap(*reinterpret_cast(Base::_processed));
+ dijk.run(s,t);
+ if (Base::_path)
+ *reinterpret_cast(Base::_path) = dijk.path(t);
+ if (Base::_di)
+ *reinterpret_cast(Base::_di) = dijk.dist(t);
+ return dijk.reached(t);
}
@@ -1210,8 +1208,8 @@
SetPredMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref PredMap object.
///
- ///\ref named-templ-param "Named parameter"
+ ///\ref named-func-param "Named parameter"
///for setting \ref PredMap object.
template
@@ -1220,4 +1218,22 @@
Base::_pred=reinterpret_cast(const_cast(&t));
return DijkstraWizard >(*this);
+ }
+
+ template
+ 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
+ DijkstraWizard > distMap(const T &t)
+ {
+ Base::_dist=reinterpret_cast(const_cast(&t));
+ return DijkstraWizard >(*this);
}
@@ -1228,8 +1244,8 @@
SetProcessedMapBase(const TR &b) : TR(b) {}
};
- ///\brief \ref named-templ-param "Named parameter"
+ ///\brief \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
///
- /// \ref named-templ-param "Named parameter"
+ /// \ref named-func-param "Named parameter"
///for setting \ref ProcessedMap object.
template
@@ -1241,35 +1257,47 @@
template
- struct SetDistMapBase : public Base {
- typedef T DistMap;
- static DistMap *createDistMap(const Digraph &) { return 0; };
- SetDistMapBase(const TR &b) : TR(b) {}
- };
- ///\brief \ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
- ///
- ///\ref named-templ-param "Named parameter"
- ///for setting \ref DistMap object.
+ struct SetPathBase : public Base {
+ typedef T Path;
+ SetPathBase(const TR &b) : TR(b) {}
+ };
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
template
- DijkstraWizard > distMap(const T &t)
- {
- Base::_dist=reinterpret_cast(const_cast(&t));
- return DijkstraWizard >(*this);
+ DijkstraWizard > path(const T &t)
+ {
+ Base::_path=reinterpret_cast(const_cast(&t));
+ return DijkstraWizard >(*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(const_cast(&d));
+ return *this;
}
};
- ///Function type interface for Dijkstra algorithm.
+ ///Function-type interface for Dijkstra algorithm.
/// \ingroup shortest_path
- ///Function type interface for Dijkstra algorithm.
+ ///Function-type interface for Dijkstra algorithm.
///
- ///This function also has several
- ///\ref named-templ-func-param "named parameters",
+ ///This function also has several \ref named-func-param "named parameters",
///they are declared as the members of class \ref DijkstraWizard.
- ///The following
- ///example shows how to use these parameters.
+ ///The following examples show how to use these parameters.
///\code
- /// dijkstra(g,length,source).predMap(preds).run();
+ /// // Compute shortest path from node s to each node
+ /// dijkstra(g,length).predMap(preds).distMap(dists).run(s);
+ ///
+ /// // Compute shortest path from s to t
+ /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
///\endcode
///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
@@ -1279,7 +1307,7 @@
template
DijkstraWizard >
- dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
+ dijkstra(const GR &digraph, const LM &length)
{
- return DijkstraWizard >(g,l,s);
+ return DijkstraWizard >(digraph,length);
}
Index: ripts/chg-len.py
===================================================================
--- scripts/chg-len.py (revision 272)
+++ (revision )
@@ -1,39 +1,0 @@
-#! /usr/bin/env python
-
-import sys
-import os
-
-if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]:
- print """
-This utility just prints the length of the longest path
-in the revision graph from revison 0 to the current one.
-"""
- exit(0)
-plist = os.popen("hg parents --template='{rev}\n'").readlines()
-if len(plist)>1:
- print "You are in the process of merging"
- exit(1)
-PAR = int(plist[0])
-
-f = os.popen("hg log -r 0:tip --template='{rev} {parents}\n'").readlines()
-REV = -1
-lengths=[]
-for l in f:
- REV+=1
- s = l.split()
- rev = int(s[0])
- if REV != rev:
- print "Something is seriously wrong"
- exit(1)
- if len(s) == 1:
- par1 = par2 = rev - 1
- elif len(s) == 2:
- par1 = par2 = int(s[1].split(":")[0])
- else:
- par1 = int(s[1].split(":")[0])
- par2 = int(s[2].split(":")[0])
- if rev == 0:
- lengths.append(0)
- else:
- lengths.append(max(lengths[par1],lengths[par2])+1)
-print lengths[PAR]
Index: test/bfs_test.cc
===================================================================
--- test/bfs_test.cc (revision 228)
+++ test/bfs_test.cc (revision 278)
@@ -63,5 +63,4 @@
BType::DistMap d(G);
BType::PredMap p(G);
- // BType::PredNodeMap pn(G);
BType bfs_test(G);
@@ -73,7 +72,5 @@
n = bfs_test.predNode(n);
d = bfs_test.distMap();
-
p = bfs_test.predMap();
- // pn = bfs_test.predNodeMap();
b = bfs_test.reached(n);
@@ -89,12 +86,28 @@
Digraph g;
- bfs(g,Node()).run();
- bfs(g).source(Node()).run();
+ bool b;
+ bfs(g).run(Node());
+ b=bfs(g).run(Node(),Node());
+ bfs(g).run();
bfs(g)
- .predMap(concepts::WriteMap())
- .distMap(concepts::WriteMap())
+ .predMap(concepts::ReadWriteMap())
+ .distMap(concepts::ReadWriteMap())
.reachedMap(concepts::ReadWriteMap())
.processedMap(concepts::WriteMap())
.run(Node());
+ b=bfs(g)
+ .predMap(concepts::ReadWriteMap())
+ .distMap(concepts::ReadWriteMap())
+ .reachedMap(concepts::ReadWriteMap())
+ .processedMap(concepts::WriteMap())
+ .path(concepts::Path())
+ .dist(VType())
+ .run(Node(),Node());
+ bfs(g)
+ .predMap(concepts::ReadWriteMap())
+ .distMap(concepts::ReadWriteMap())
+ .reachedMap(concepts::ReadWriteMap())
+ .processedMap(concepts::WriteMap())
+ .run();
}
@@ -115,5 +128,5 @@
bfs_test.run(s);
- check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
+ check(bfs_test.dist(t)==2,"Bfs found a wrong path.");
Path p = bfs_test.path(t);
@@ -129,5 +142,5 @@
check( !bfs_test.reached(u) ||
(bfs_test.dist(v) <= bfs_test.dist(u)+1),
- "Wrong output." << G.id(v) << ' ' << G.id(u));
+ "Wrong output. " << G.id(u) << "->" << G.id(v));
}
@@ -141,8 +154,12 @@
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 myPredMap;
+ bfs(G).predMap(myPredMap).run(s);
}
}
Index: test/dfs_test.cc
===================================================================
--- test/dfs_test.cc (revision 228)
+++ test/dfs_test.cc (revision 278)
@@ -21,5 +21,4 @@
#include
#include
-
#include
#include
@@ -89,12 +88,28 @@
Digraph g;
- dfs(g,Node()).run();
- dfs(g).source(Node()).run();
+ bool b;
+ dfs(g).run(Node());
+ b=dfs(g).run(Node(),Node());
+ dfs(g).run();
dfs(g)
- .predMap(concepts::WriteMap())
- .distMap(concepts::WriteMap())
+ .predMap(concepts::ReadWriteMap())
+ .distMap(concepts::ReadWriteMap())
.reachedMap(concepts::ReadWriteMap())
.processedMap(concepts::WriteMap())
.run(Node());
+ b=dfs(g)
+ .predMap(concepts::ReadWriteMap())
+ .distMap(concepts::ReadWriteMap())
+ .reachedMap(concepts::ReadWriteMap())
+ .processedMap(concepts::WriteMap())
+ .path(concepts::Path())
+ .dist(VType())
+ .run(Node(),Node());
+ dfs(g)
+ .predMap(concepts::ReadWriteMap())
+ .distMap(concepts::ReadWriteMap())
+ .reachedMap(concepts::ReadWriteMap())
+ .processedMap(concepts::WriteMap())
+ .run();
}
@@ -130,7 +145,12 @@
check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
"Wrong distance. (" << dfs_test.dist(u) << "->"
- < myPredMap;
+ dfs(G).predMap(myPredMap).run(s);
}
}
Index: test/dijkstra_test.cc
===================================================================
--- test/dijkstra_test.cc (revision 228)
+++ test/dijkstra_test.cc (revision 278)
@@ -21,5 +21,4 @@
#include
#include
-
#include
#include
@@ -65,5 +64,4 @@
DType::DistMap d(G);
DType::PredMap p(G);
- // DType::PredNodeMap pn(G);
LengthMap length;
@@ -77,5 +75,4 @@
d = dijkstra_test.distMap();
p = dijkstra_test.predMap();
- // pn = dijkstra_test.predNodeMap();
b = dijkstra_test.reached(n);
@@ -92,10 +89,19 @@
Digraph g;
- dijkstra(g,LengthMap(),Node()).run();
- dijkstra(g,LengthMap()).source(Node()).run();
+ bool b;
+ dijkstra(g,LengthMap()).run(Node());
+ b=dijkstra(g,LengthMap()).run(Node(),Node());
dijkstra(g,LengthMap())
- .predMap(concepts::WriteMap())
- .distMap(concepts::WriteMap())
+ .predMap(concepts::ReadWriteMap())
+ .distMap(concepts::ReadWriteMap())
+ .processedMap(concepts::WriteMap())
.run(Node());
+ b=dijkstra(g,LengthMap())
+ .predMap(concepts::ReadWriteMap())
+ .distMap(concepts::ReadWriteMap())
+ .processedMap(concepts::WriteMap())
+ .path(concepts::Path())
+ .dist(VType())
+ .run(Node(),Node());
}
@@ -123,5 +129,5 @@
Path p = dijkstra_test.path(t);
- check(p.length()==3,"getPath() found a wrong path.");
+ check(p.length()==3,"path() found a wrong path.");
check(checkPath(G, p),"path() found a wrong path.");
check(pathSource(G, p) == s,"path() found a wrong path.");
@@ -133,5 +139,5 @@
check( !dijkstra_test.reached(u) ||
(dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
- "dist(target)-dist(source)-arc_length= " <<
+ "Wrong output. dist(target)-dist(source)-arc_length=" <<
dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
}
Index: test/error_test.cc
===================================================================
--- test/error_test.cc (revision 277)
+++ test/error_test.cc (revision 223)
@@ -48,7 +48,12 @@
}
+void fixme_disable() {
+ LEMON_FIXME("fixme_disable() is fixme!");
+}
+
void check_assertion_disable() {
no_assertion_text_disable();
assertion_text_disable();
+ fixme_disable();
}
#undef LEMON_DISABLE_ASSERTS
@@ -74,8 +79,13 @@
}
+void fixme_custom() {
+ LEMON_FIXME("fixme_custom() is fixme!");
+}
+
void check_assertion_custom() {
no_assertion_text_custom();
assertion_text_custom();
- check(cnt == 1, "The custom assert handler does not work");
+ fixme_custom();
+ check(cnt == 2, "The custom assert handler does not work");
}
Index: test/graph_test.h
===================================================================
--- test/graph_test.h (revision 263)
+++ test/graph_test.h (revision 228)
@@ -213,8 +213,8 @@
check(s == 0, "Wrong sum.");
- // map = constMap(12);
- // for (NodeIt it(G); it != INVALID; ++it) {
- // check(map[it] == 12, "Wrong operator[].");
- // }
+ map = constMap