LEMON/LEMON-official Changeset - r99:dbaa96cc1013

Repositories » LEMON » LEMON-official

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

Changeset - r99:dbaa96cc1013

« 67:9de02a
« 98:c4582f

100:4f754b »

r99:dbaa96cc1013

Thu, 07 Feb 2008 22:28:39

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 6 2

merge default

2 files changed with 832 insertions and 4 deletions:

lemon/error.h

675

test/error_test.cc

configure.ac

lemon/Makefile.am

lemon/concepts/digraph.h

lemon/concepts/graph.h

lemon/random.h

test/Makefile.am

↑ Collapse diff ↑

lemon/error.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_ERROR_H
 		#define LEMON_ERROR_H
 		/// \ingroup exceptions
 		/// \file
 		/// \brief Basic exception classes and error handling.
 		#include <exception>
 		#include <string>
 		#include <sstream>
 		#include <iostream>
 		#include <cstdlib>
 		#include <memory>
 		namespace lemon {
 		  /// \addtogroup exceptions
 		  /// @{
 		  /// \brief Exception safe wrapper class.
 		  ///
 		  /// Exception safe wrapper class to implement the members of exceptions.
 		  template <typename _Type>
 		  class ExceptionMember {
 		  public:
 		    typedef _Type Type;
 		    ExceptionMember() throw() {
 		      try {
 			ptr.reset(new Type());
 		      } catch (...) {}
+		    }
 		    ExceptionMember(const Type& type) throw() {
 		      try {
 			ptr.reset(new Type());
 			if (ptr.get() == 0) return;
 			*ptr = type;
 		      } catch (...) {}
+		    }
 		    ExceptionMember(const ExceptionMember& copy) throw() {
 		      try {
 			if (!copy.valid()) return;
 			ptr.reset(new Type());
 			if (ptr.get() == 0) return;
 			*ptr = copy.get();
 		      } catch (...) {}
+		    }
 		    ExceptionMember& operator=(const ExceptionMember& copy) throw() {
 		      if (ptr.get() == 0) return;
 		      try {
 			if (!copy.valid()) return;
 		 	*ptr = copy.get();
 		      } catch (...) {}
+		    }
 		    void set(const Type& type) throw() {
 		      if (ptr.get() == 0) return;
 		      try {
 			*ptr = type;
 		      } catch (...) {}
+		    }
 		    const Type& get() const {
 		      return *ptr;
+		    }
 		    bool valid() const throw() {
 		      return ptr.get() != 0;
+		    }
 		  private:
 		    std::auto_ptr<_Type> ptr;
 		  };
 		  /// Exception-safe convenient "error message" class.
 		  /// Helper class which provides a convenient ostream-like (operator <<
 		  /// based) interface to create a string message. Mostly useful in
 		  /// exception classes (therefore the name).
 		  class ErrorMessage {
 		  protected:
 		    ///\e
 		    ///\todo The good solution is boost::shared_ptr...
 		    ///
 		    mutable std::auto_ptr<std::ostringstream> buf;
 		    ///\e
 		    bool init() throw() {
 		      try {
 			buf.reset(new std::ostringstream);
+		      }
 		      catch(...) {
 			buf.reset();
+		      }
 		      return buf.get();
+		    }
 		  public:
 		    ///\e
 		    ErrorMessage() throw() { init(); }
 		    ErrorMessage(const ErrorMessage& em) throw() : buf(em.buf) { }
 		    ///\e
 		    ErrorMessage(const char *msg) throw() {
 		      init();
 		      *this << msg;
+		    }
 		    ///\e
 		    ErrorMessage(const std::string &msg) throw() {
 		      init();
 		      *this << msg;
+		    }
 		    ///\e
 		    template <typename T>
 		    ErrorMessage& operator<<(const T &t) throw() {
 		      if( ! buf.get() ) return *this;
 		      try {
 			*buf << t;
+		      }
 		      catch(...) {
 			buf.reset();
+		      }
 		      return *this;
+		    }
 		    ///\e
 		    const char* message() throw() {
 		      if( ! buf.get() ) return 0;
 		      const char* mes = 0;
 		      try {
 			mes = buf->str().c_str();
+		      }
 		      catch(...) {}
 		      return mes;
+		    }
 		  };
 		  /// Generic exception class.
 		  /// Base class for exceptions used in LEMON.
 		  ///
 		  class Exception : public std::exception {
 		  public:
 		    ///\e
 		    Exception() {}
 		    ///\e
 		    virtual ~Exception() throw() {}
 		    ///\e
 		    virtual const char* what() const throw() {
 		      return "lemon::Exception";
+		    }
 		  };
 		  /// One of the two main subclasses of \ref Exception.
 		  /// Logic errors represent problems in the internal logic of a program;
 		  /// in theory, these are preventable, and even detectable before the
 		  /// program runs (e.g. violations of class invariants).
 		  ///
 		  /// A typical example for this is \ref UninitializedParameter.
 		  class LogicError : public Exception {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::LogicError";
+		    }
 		  };
 		  /// \ref Exception for uninitialized parameters.
 		  /// This error represents problems in the initialization
 		  /// of the parameters of the algorithms.
 		  class UninitializedParameter : public LogicError {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::UninitializedParameter";
+		    }
 		  };
 		  /// One of the two main subclasses of \ref Exception.
 		  /// Runtime errors represent problems outside the scope of a program;
 		  /// they cannot be easily predicted and can generally only be caught
 		  /// as the program executes.
 		  class RuntimeError : public Exception {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::RuntimeError";
+		    }
 		  };
 		  ///\e
 		  class RangeError : public RuntimeError {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::RangeError";
+		    }
 		  };
 		  ///\e
 		  class IoError : public RuntimeError {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::IoError";
+		    }
 		  };
 		  ///\e
 		  class DataFormatError : public IoError {
 		  protected:
 		    ExceptionMember<std::string> _message;
 		    ExceptionMember<std::string> _file;
 		    int _line;
 		    mutable ExceptionMember<std::string> _message_holder;
 		  public:
 		    DataFormatError(const DataFormatError &dfe) :
 		      IoError(dfe), _message(dfe._message), _file(dfe._file),
 		      _line(dfe._line) {}
 		    ///\e
 		    explicit DataFormatError(const char *the_message)
 		      : _message(the_message), _line(0) {}
 		    ///\e
 		    DataFormatError(const std::string &file_name, int line_num,
 				    const char *the_message)
 		      : _message(the_message), _line(line_num) { file(file_name); }
 		    ///\e
 		    void line(int ln) { _line = ln; }
 		    ///\e
 		    void message(const std::string& msg) { _message.set(msg); }
 		    ///\e
 		    void file(const std::string &fl) { _file.set(fl); }
 		    ///\e
 		    int line() const { return _line; }
 		    ///\e
 		    const char* message() const {
 		      if (_message.valid() && !_message.get().empty()) {
 			return _message.get().c_str();
 		      } else {
 			return 0;
+		      }
+		    }
 		    /// \brief Returns the filename.
 		    ///
 		    /// Returns \e null if the filename was not specified.
 		    const char* file() const {
 		      if (_file.valid() && !_file.get().empty()) {
 			return _file.get().c_str();
 		      } else {
 			return 0;
+		      }
+		    }
 		    ///\e
 		    virtual const char* what() const throw() {
 		      try {
 			std::ostringstream ostr;
 			ostr << "lemon:DataFormatError" << ": ";
 			if (message()) ostr << message();
 			if( file() || line() != 0 ) {
 			  ostr << " (";
 			  if( file() ) ostr << "in file '" << file() << "'";
 			  if( file() && line() != 0 ) ostr << " ";
 			  if( line() != 0 ) ostr << "at line " << line();
 			  ostr << ")";
+			}
 			_message_holder.set(ostr.str());
+		      }
 		      catch (...) {}
 		      if( _message_holder.valid()) return _message_holder.get().c_str();
 		      return "lemon:DataFormatError";
+		    }
 		    virtual ~DataFormatError() throw() {}
 		  };
 		  ///\e
 		  class FileOpenError : public IoError {
 		  protected:
 		    ExceptionMember<std::string> _file;
 		    mutable ExceptionMember<std::string> _message_holder;
 		  public:
 		    FileOpenError(const FileOpenError &foe) :
 		      IoError(foe), _file(foe._file) {}
 		    ///\e
 		    explicit FileOpenError(const std::string& fl)
 		      : _file(fl) {}
 		    ///\e
 		    void file(const std::string &fl) { _file.set(fl); }
 		    /// \brief Returns the filename.
 		    ///
 		    /// Returns \e null if the filename was not specified.
 		    const char* file() const {
 		      if (_file.valid() && !_file.get().empty()) {
 			return _file.get().c_str();
 		      } else {
 			return 0;
+		      }
+		    }
 		    ///\e
 		    virtual const char* what() const throw() {
 		      try {
 			std::ostringstream ostr;
 			ostr << "lemon::FileOpenError" << ": ";
 			ostr << "Cannot open file - " << file();
 			_message_holder.set(ostr.str());
+		      }
 		      catch (...) {}
 		      if( _message_holder.valid()) return _message_holder.get().c_str();
 		      return "lemon::FileOpenError";
+		    }
 		    virtual ~FileOpenError() throw() {}
 		  };
 		  class IoParameterError : public IoError {
 		  protected:
 		    ExceptionMember<std::string> _message;
 		    ExceptionMember<std::string> _file;
 		    mutable ExceptionMember<std::string> _message_holder;
 		  public:
 		    IoParameterError(const IoParameterError &ile) :
 		      IoError(ile), _message(ile._message), _file(ile._file) {}
 		    ///\e
 		    explicit IoParameterError(const char *the_message)
 		      : _message(the_message) {}
 		    ///\e
 		    IoParameterError(const char *file_name, const char *the_message)
 		      : _message(the_message), _file(file_name) {}
 		     ///\e
 		    void message(const std::string& msg) { _message.set(msg); }
 		    ///\e
 		    void file(const std::string &fl) { _file.set(fl); }
 		     ///\e
 		    const char* message() const {
 		      if (_message.valid()) {
 			return _message.get().c_str();
 		      } else {
 			return 0;
+		      }
+		    }
 		    /// \brief Returns the filename.
 		    ///
 		    /// Returns \c 0 if the filename was not specified.
 		    const char* file() const {
 		      if (_file.valid()) {
 			return _file.get().c_str();
 		      } else {
 			return 0;
+		      }
+		    }
 		    ///\e
 		    virtual const char* what() const throw() {
 		      try {
 			std::ostringstream ostr;
 			if (message()) ostr << message();
 			if (file()) ostr << "(when reading file '" << file() << "')";
 			_message_holder.set(ostr.str());
+		      }
 		      catch (...) {}
 		      if( _message_holder.valid() ) return _message_holder.get().c_str();
 		      return "lemon:IoParameterError";
+		    }
 		    virtual ~IoParameterError() throw() {}
 		  };
 		  ///\e
 		  class AssertionFailedError : public LogicError {
 		  protected:
 		    const char *assertion;
 		    const char *file;
 		    int line;
 		    const char *function;
 		    const char *message;
 		    mutable ExceptionMember<std::string> _message_holder;
 		  public:
 		    ///\e
 		    AssertionFailedError(const char *_file, int _line, const char *func,
 					 const char *msg, const char *_assertion = 0) :
 		      assertion(_assertion), file(_file), line(_line), function(func),
 		      message(msg) {}
 		    ///\e
 		    const char* get_assertion() const { return assertion; }
 		    ///\e
 		    const char* get_message() const { return message; }
 		    ///\e
 		    const char* get_file() const { return file; }
 		    ///\e
 		    const char* get_function() const { return function; }
 		    ///\e
 		    int get_line() const { return line; }
 		    virtual const char* what() const throw() {
 		      try {
 			std::ostringstream ostr;
 			ostr << file << ":" << line << ": ";
 			if( function )
 			  ostr << function << ": ";
 			ostr << message;
 			if( assertion )
 			   ostr << " (assertion '" << assertion << "' failed)";
 			_message_holder.set(ostr.str());
 			return ostr.str().c_str();
+		      }
 		      catch(...) {}
 		      if( _message_holder.valid() ) return _message_holder.get().c_str();
 		      return "lemon::AssertionFailedError";
+		    }
 		   virtual ~AssertionFailedError() throw() {}
 		  };
 		  /****************  Macros  ****************/
 		  template <typename Exception>
 		  inline void assert_fail(const char *file, int line,
 		                          const char *func,
 		                          Exception exception,
 		                          const char *assertion = 0,
 		                          bool do_abort=true)
+		  {
 		    using namespace std;
 		    cerr << file << ":" << line << ": ";
 		    if (func)
 		      cerr << func << ": ";
 		    cerr << exception.what();
 		    if (assertion)
 		      cerr << " (assertion '" << assertion << "' failed)";
 		    cerr << endl;
 		    if (do_abort)
 		      abort();
+		  }
 		  template <>
 		  inline void assert_fail<const char *>(const char *file, int line,
 		                                        const char *func,
 		                                        const char *message,
 		                                        const char *assertion,
 		                                        bool do_abort)
+		  {
 		    using namespace std;
 		    cerr << file << ":" << line << ": ";
 		    if (func)
 		      cerr << func << ": ";
 		    cerr << message;
 		    if (assertion)
 		      cerr << " (assertion '" << assertion << "' failed)";
 		    cerr << endl;
 		    if (do_abort)
 		      abort();
+		  }
 		  template <>
 		  inline void assert_fail<std::string>(const char *file, int line,
 		                                       const char *func,
 		                                       std::string message,
 		                                       const char *assertion,
 		                                       bool do_abort)
+		  {
 		    assert_fail(file, line, func, message.c_str(), assertion, do_abort);
+		  }
 		  template <typename Exception>
 		  inline void assert_fail_failure(const char *file, int line, const char *func,
 					   Exception exception,
 					   const char *assertion = 0,
 					   bool = true)
+		  {
 		    throw AssertionFailedError(file, line, func, exception.what(), assertion);
+		  }
 		  template <>
 		  inline void assert_fail_failure<const char *>(const char *file, int line,
 		                                                const char *func,
 		                                                const char *message,
 		                                                const char *assertion,
 		                                                bool)
+		  {
 		    throw AssertionFailedError(file, line, func, message, assertion);
+		  }
 		  template <>
 		  inline void assert_fail_failure<std::string>(const char *file, int line,
 		                                               const char *func,
 		                                               std::string message,
 		                                               const char *assertion,
 		                                               bool)
+		  {
 		    assert_fail_failure(file, line, func, message.c_str(), assertion, true);
+		  }
 		  template <typename Exception>
 		  inline void assert_fail_exception(const char *file, int line, const char *func,
 					     Exception exception,
 					     const char *assertion = 0, bool = true)
+		  {
 		    throw exception;
+		  }
 		  template <>
 		  inline void assert_fail_exception<const char *>(const char *file, int line,
 							   const char *func,
 							   const char *message,
 							   const char *assertion,
 							   bool)
+		  {
 		    throw AssertionFailedError(file, line, func, message, assertion);
+		  }
 		  template <>
 		  inline void assert_fail_exception<std::string>(const char *file, int line,
 		                                                 const char *func,
 		                                                 std::string message,
 		                                                 const char *assertion,
 		                                                 bool)
+		  {
 		    assert_fail_exception(file, line, func, message.c_str(), assertion, true);
+		  }
 		/// @}
+		}
 		#endif // LEMON_ERROR_H
 		#undef LEMON_ASSERT
 		#undef LEMON_FIXME
 		#ifdef LEMON_ENABLE_ASSERTS
 		#  define LEMON_ASSERT_ABORT
 		#endif
 		#ifndef LEMON_ASSERT_DO_ABORT
 		#  define LEMON_ASSERT_DO_ABORT 1
 		#endif
 		#ifndef LEMON_ASSERT_HANDLER
 		#  if defined LEMON_ASSERT_EXCEPTION
 		#    define LEMON_ASSERT_HANDLER ::lemon::assert_fail_exception
 		#  elif defined LEMON_ASSERT_FAILURE
 		#    define LEMON_ASSERT_HANDLER ::lemon::assert_fail_failure
 		#  elif defined LEMON_ASSERT_ABORT
 		#    define LEMON_ASSERT_HANDLER ::lemon::assert_fail
 		#  else
 		#    define LEMON_DISABLE_ASSERTS
 		#  endif
 		#endif
 		#ifdef DOXYGEN
 		/// \brief Macro for assertions with customizable message
 		///
 		/// Macro for assertions with customizable message.
 		///
 		/// The assertions are disabled in the default behaviour. You can
 		/// enable the assertions with the
 		/// \code
 		/// #define LEMON_ENABLE_ASSERTS
 		/// \endcode
 		/// Then an assert
 		/// provides a log on the standard error about the assertion and aborts
 		/// the program if LEMON_ASSERT_DO_ABORT is also defined (otherwise the
 		/// program keeps on running).
 		/// By defining LEMON_ASSERT_FAILURE or
 		/// LEMON_ASSERT_EXCEPTION, you can set other behaviour to the
 		/// assertions. In case LEMON_ASSERT_FAILURE is given, LEMON_ASSERT
 		/// will always throw an \c AssertionFailedError exception with
 		/// the \c msg error message. By using
 		/// LEMON_ASSERT_EXCEPTION, one can define an arbitrary exception to be thrown.
 		///
 		/// The LEMON_ASSERT macro should be called with the \c exp parameter
 		/// which should be an expression convertible to bool. If the given
 		/// parameter is false the assertion is raised and one of the assertion
 		/// behaviour will be activated. The \c msg should be either a const
 		/// char* message or an exception. When the \c msg is an exception the
 		/// \ref lemon::Exception::what() "what()" function is called to retrieve and
 		/// display the error message.
 		///
 		/// \todo We should provide some way to reset to the default behaviour,
 		/// shouldn't we?
 		///
 		/// \todo This whole 'assert' business should be placed in a separate
 		/// include file. The boost assert is not guarded by header sentries
 		/// which may help to change the behaviour of the assertions in
 		/// the files.
 		///
 		/// \todo __PRETTY_FUNCTION__ should be replaced by something
 		/// compiler-independent, like BOOST_CURRENT_FUNCTION
 		#  define LEMON_ASSERT(exp, msg)                 \
 		     (static_cast<void> (!!(exp) ? 0 : (         \
 		       LEMON_ASSERT_HANDLER(__FILE__, __LINE__,  \
 		                            __PRETTY_FUNCTION__, \
 		                            msg, #exp, LEMON_ASSERT_DO_ABORT), 0)))
 		#else
 		#  if defined LEMON_DISABLE_ASSERTS
 		#    define LEMON_ASSERT(exp, msg)  (static_cast<void> (0))
 		#  else
 		#    define LEMON_ASSERT(exp, msg)                 \
 		       (static_cast<void> (!!(exp) ? 0 : (         \
 		         LEMON_ASSERT_HANDLER(__FILE__, __LINE__,  \
 		                              __PRETTY_FUNCTION__, \
 		                              msg, #exp, LEMON_ASSERT_DO_ABORT), 0)))
 		#  endif
 		#endif
 		/**
 		 * \brief Macro for mark not yet implemented features.
+		 *
 		 * \todo Is this the right place for this? It should be used only in
 		 * modules under development.
+		 *
 		 * \todo __PRETTY_FUNCTION__ should be replaced by something
 		 * compiler-independent, like BOOST_CURRENT_FUNCTION
 		 */
 		#define LEMON_FIXME(msg) \
 		    (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, __PRETTY_FUNCTION__, \
 					  "FIXME: " msg))

test/error_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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.
+		 *
 		 */
 		#include <iostream>
 		#include <lemon/error.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using std::cout;
 		using std::endl;
 		void faulty_fn() {
 		  fault("This is a fault message");
+		}
 		void exception_fn() {
 		  throw Exception("This is a function throwing exception with some args: ")
 		    << 5 << ", " << 18;
+		}
 		void unfinished_fn() {
 		  LEMON_FIXME("unfinished_fn() is unfinished!");
+		}
 		int main() {
 		  try {
 		    faulty_fn();
 		    check(false, "A faulty function did not fail.");
+		  }
 		  catch(const Exception &e) {
 		    cout << "Exeption = \"" << e.what() << "\" (Right behaviour)" << endl;
+		  }
 		  try {
 		    exception_fn();
 		    check(false, "The function did not throw Exception.");
+		  }
 		  catch(const Exception &e) {
 		    cout << "Exeption = \"" << e.what() << "\" (Right behaviour)" << endl;
+		  }
 		  try {
 		    unfinished_fn();
 		    check(false, "FIXME macro does not work.");
+		  }
 		  catch(const Exception &e) {
 		    cout << "Exeption = \"" << e.what() << "\" (Right behaviour)" << endl;
+		  }
 		  return 0;
+		}

configure.ac

Show inline comments

 		dnl Process this file with autoconf to produce a configure script.
 		dnl Version information.
 		m4_define([lemon_version_major], [0])
 		m4_define([lemon_version_minor], [99])
 		m4_define([lemon_version_micro], [])
 		m4_define([lemon_version_nano], [])
 		m4_define([lemon_version_tag], [hg])
 		m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
 		m4_define([lemon_version], [lemon_version_major().lemon_version_minor()ifelse(lemon_version_micro(), [], [], [.lemon_version_micro()])ifelse(lemon_version_nano(), [], [], [.lemon_version_nano()])ifelse(lemon_version_tag(), [], [], lemon_version_tag(), [hg], [[_]lemon_version_tag()[_]lemon_hg_revision()], [[_]lemon_version_tag()])])
 		AC_PREREQ([2.59])
 		AC_INIT([LEMON], [lemon_version()], [etik-ol@cs.elte.hu], [lemon])
 		AC_CONFIG_AUX_DIR([build-aux])
 		AC_CONFIG_MACRO_DIR([m4])
 		AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects])
+		AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
 		AC_CONFIG_SRCDIR([lemon/list_graph.h])
 		AC_CONFIG_HEADERS([config.h lemon/config.h])
 		lx_cmdline_cxxflags_set=${CXXFLAGS+set}
 		dnl Checks for programs.
 		AC_PROG_CXX
 		AC_PROG_CXXCPP
 		AC_PROG_INSTALL
 		AC_DISABLE_SHARED
 		AC_PROG_LIBTOOL
 		AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
 		if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then
 		  CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
 		fi
 		dnl Checks for libraries.
 		LX_CHECK_GLPK
 		LX_CHECK_CPLEX
 		LX_CHECK_SOPLEX
 		dnl Disable/enable building the demo programs
 		AC_ARG_ENABLE([demo],
 		AS_HELP_STRING([--enable-demo], [build the demo programs])
 		AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
 		              [], [enable_demo=no])
 		AC_MSG_CHECKING([whether to build the demo programs])
 		if test x"$enable_demo" != x"no"; then
 		  AC_MSG_RESULT([yes])
 		else
 		  AC_MSG_RESULT([no])
 		fi
 		AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
 		dnl Disable/enable building the binary tools
 		AC_ARG_ENABLE([tools],
 		AS_HELP_STRING([--enable-tools], [build additional tools @<:@default@:>@])
 		AS_HELP_STRING([--disable-tools], [do not build additional tools]),
 		              [], [enable_tools=yes])
 		AC_MSG_CHECKING([whether to build the additional tools])
 		if test x"$enable_tools" != x"no"; then
 		  AC_MSG_RESULT([yes])
 		else
 		  AC_MSG_RESULT([no])
 		fi
 		AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
 		dnl Disable/enable building the benchmarks
 		AC_ARG_ENABLE([benchmark],
 		AS_HELP_STRING([--enable-benchmark], [build the benchmarks])
 		AS_HELP_STRING([--disable-benchmark], [do not build the benchmarks @<:@default@:>@]),
 		              [], [enable_benchmark=no])
 		AC_MSG_CHECKING([whether to build the benchmarks])
 		if test x"$enable_benchmark" != x"no"; then
 		  AC_MSG_RESULT([yes])
 		else
 		  AC_MSG_RESULT([no])
 		fi
 		AM_CONDITIONAL([WANT_BENCHMARK], [test x"$enable_benchmark" != x"no"])
 		dnl Checks for header files.
 		AC_CHECK_HEADERS(limits.h sys/time.h sys/times.h unistd.h)
 		dnl Checks for typedefs, structures, and compiler characteristics.
 		AC_C_CONST
 		AC_C_INLINE
 		AC_TYPE_SIZE_T
 		AC_HEADER_TIME
 		AC_STRUCT_TM
 		dnl Checks for library functions.
 		AC_HEADER_STDC
 		AC_CHECK_FUNCS(gettimeofday times ctime_r)
 		AC_CONFIG_FILES([
 		Makefile
 		doc/Doxyfile
 		lemon/lemon.pc
 		])
 		AC_OUTPUT
 		echo
 		echo '****************************** SUMMARY ******************************'
 		echo
 		echo Package version............... : $PACKAGE-$VERSION
 		echo
 		echo C++ compiler.................. : $CXX
 		echo C++ compiles flags............ : $CXXFLAGS
 		echo
 		echo GLPK support.................. : $lx_glpk_found
 		echo CPLEX support................. : $lx_cplex_found
 		echo SOPLEX support................ : $lx_soplex_found
 		echo
 		echo Build benchmarks.............. : $enable_benchmark
 		echo Build demo programs........... : $enable_demo
 		echo Build additional tools........ : $enable_tools
 		echo
 		echo The packace will be installed in
 		echo -n '  '
 		echo $prefix.
 		echo
 		echo '*********************************************************************'
 		echo
 		echo Configure complete, now type \'make\' and then \'make install\'.
 		echo

lemon/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			lemon/Makefile \
 			lemon/lemon.pc.in
 		pkgconfig_DATA += lemon/lemon.pc
 		lib_LTLIBRARIES += lemon/libemon.la
 		lemon_libemon_la_SOURCES = \
 		        lemon/base.cc \
 		        lemon/random.cc
 		lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
 		lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
 		lemon_HEADERS += \
 		        lemon/concept_check.h \
 		        lemon/dim2.h \
 			lemon/error.h \
 			lemon/list_graph.h \
 			lemon/maps.h \
 			lemon/path.h \
 		        lemon/random.h \
 			lemon/list_graph.h \
 		        lemon/tolerance.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \
 			lemon/bits/array_map.h \
 			lemon/bits/base_extender.h \
 			lemon/bits/default_map.h \
 			lemon/bits/graph_extender.h \
 		        lemon/bits/invalid.h \
 			lemon/bits/map_extender.h \
 			lemon/bits/traits.h \
 		        lemon/bits/utility.h \
 			lemon/bits/vector_map.h
 		concept_HEADERS += \
 			lemon/concept_check.h \
 			lemon/concepts/digraph.h \
 			lemon/concepts/graph.h \
 			lemon/concepts/maps.h \
 			lemon/concepts/path.h \
 			lemon/concepts/graph_components.h

lemon/concepts/digraph.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2007
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_CONCEPT_DIGRAPH_H
 		#define LEMON_CONCEPT_DIGRAPH_H
 		///\ingroup graph_concepts
 		///\file
 		///\brief The concept of directed graphs.
 		#include <lemon/bits/invalid.h>
 		#include <lemon/bits/utility.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/graph_components.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \ingroup graph_concepts
 		    ///
 		    /// \brief Class describing the concept of directed graphs.
 		    ///
 		    /// This class describes the \ref concept "concept" of the
 		    /// immutable directed digraphs.
 		    ///
 		    /// Note that actual digraph implementation like @ref ListDigraph or
 		    /// @ref SmartDigraph may have several additional functionality.
 		    ///
 		    /// \sa concept
 		    class Digraph {
 		    private:
 		      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
 		      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
 		      ///
 		      Digraph(const Digraph &) {};
 		      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
 		      ///\e not allowed. Use DigraphCopy() instead.
 		      ///Assignment of \ref Digraph "Digraph"s to another ones are
 		      ///\e not allowed.  Use DigraphCopy() instead.
 		      void operator=(const Digraph &) {}
 		    public:
 		      ///\e
 		      /// Defalult constructor.
 		      /// Defalult constructor.
 		      ///
 		      Digraph() { }
 		      /// Class for identifying a node of the digraph
 		      /// This class identifies a node of the digraph. It also serves
 		      /// as a base class of the node iterators,
 		      /// thus they will convert to this type.
 		      class Node {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        Node() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Node(const Node&) { }
 		        /// Invalid constructor \& conversion.
 		        /// This constructor initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        Node(Invalid) { }
 		        /// Equality operator
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are invalid.
 		        bool operator==(Node) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Node n)
 		        ///
 		        bool operator!=(Node) const { return true; }
 			/// Artificial ordering operator.
 			/// To allow the use of digraph descriptors as key type in std::map or
 			/// similar associative container we require this.
 			///
 			/// \note This operator only have to define some strict ordering of
 			/// the items; this order has nothing to do with the iteration
 			/// ordering of the items.
 			bool operator<(Node) const { return false; }
 		      };
 		      /// This iterator goes through each node.
 		      /// This iterator goes through each node.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of nodes in digraph \c g of type \c Digraph like this:
 		      ///\code
 		      /// int count=0;
 		      /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
 		      ///\endcode
 		      class NodeIt : public Node {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        NodeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        NodeIt(const NodeIt& n) : Node(n) { }
 		        /// Invalid constructor \& conversion.
 		        /// Initialize the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        NodeIt(Invalid) { }
 		        /// Sets the iterator to the first node.
 		        /// Sets the iterator to the first node of \c g.
 		        ///
 		        NodeIt(const Digraph&) { }
 		        /// Node -> NodeIt conversion.
 		        /// Sets the iterator to the node of \c the digraph pointed by
 			/// the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        NodeIt(const Digraph&, const Node&) { }
 		        /// Next node.
 		        /// Assign the iterator to the next node.
 		        ///
 		        NodeIt& operator++() { return *this; }
 		      };
 		      /// Class for identifying an arc of the digraph
 		      /// This class identifies an arc of the digraph. It also serves
 		      /// as a base class of the arc iterators,
 		      /// thus they will convert to this type.
 		      class Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        Arc() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Arc(const Arc&) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        Arc(Invalid) { }
 		        /// Equality operator
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are invalid.
 		        bool operator==(Arc) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Arc n)
 		        ///
 		        bool operator!=(Arc) const { return true; }
 			/// Artificial ordering operator.
 			/// To allow the use of digraph descriptors as key type in std::map or
 			/// similar associative container we require this.
 			///
 			/// \note This operator only have to define some strict ordering of
 			/// the items; this order has nothing to do with the iteration
 			/// ordering of the items.
 			bool operator<(Arc) const { return false; }
 		      };
 		      /// This iterator goes trough the outgoing arcs of a node.
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in digraph \c g of type \c Digraph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class OutArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        OutArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        OutArcIt(const OutArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        OutArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first outgoing arc.
 		        /// This constructor sets the iterator to the first outgoing arc of
 		        /// the node.
 		        OutArcIt(const Digraph&, const Node&) { }
 		        /// Arc -> OutArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator.
 			/// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        OutArcIt(const Digraph&, const Arc&) { }
 		        ///Next outgoing arc
 		        /// Assign the iterator to the next
 		        /// outgoing arc of the corresponding node.
 		        OutArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes trough the incoming arcs of a node.
 		      /// This iterator goes trough the \e incoming arcs of a certain node
 		      /// of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in digraph \c g of type \c Digraph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class InArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        InArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        InArcIt(const InArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        InArcIt(Invalid) { }
 		        /// This constructor sets the iterator to first incoming arc.
 		        /// This constructor set the iterator to the first incoming arc of
 		        /// the node.
 		        InArcIt(const Digraph&, const Node&) { }
 		        /// Arc -> InArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        InArcIt(const Digraph&, const Arc&) { }
 		        /// Next incoming arc
 		        /// Assign the iterator to the next inarc of the corresponding node.
 		        ///
 		        InArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes through each arc.
 		      /// This iterator goes through each arc of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of arcs in a digraph \c g of type \c Digraph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class ArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        ArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        ArcIt(const ArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        ArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first arc.
 		        /// This constructor sets the iterator to the first arc of \c g.
 		        ///@param g the digraph
 		        ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
 		        /// Arc -> ArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        ArcIt(const Digraph&, const Arc&) { }
 		        ///Next arc
 		        /// Assign the iterator to the next arc.
 		        ArcIt& operator++() { return *this; }
 		      };
 		      ///Gives back the target node of an arc.
 		      ///Gives back the target node of an arc.
 		      ///
 		      Node target(Arc) const { return INVALID; }
 		      ///Gives back the source node of an arc.
 		      ///Gives back the source node of an arc.
 		      ///
 		      Node source(Arc) const { return INVALID; }
 		      /// \brief Returns the ID of the node.
 		      int id(Node) const { return -1; }
 		      /// \brief Returns the ID of the arc.
 		      int id(Arc) const { return -1; }
 		      /// \brief Returns the node with the given ID.
 		      ///
 		      /// \pre The argument should be a valid node ID in the graph.
 		      Node nodeFromId(int) const { return INVALID; }
 		      /// \brief Returns the arc with the given ID.
 		      ///
 		      /// \pre The argument should be a valid arc ID in the graph.
 		      Arc arcFromId(int) const { return INVALID; }
 		      /// \brief Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
 		      /// \brief Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      void first(Node&) const {}
 		      void next(Node&) const {}
 		      void first(Arc&) const {}
 		      void next(Arc&) const {}
 		      void firstIn(Arc&, const Node&) const {}
 		      void nextIn(Arc&) const {}
 		      void firstOut(Arc&, const Node&) const {}
 		      void nextOut(Arc&) const {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Gives back the base node of the iterator.
 		      /// It is always the target of the pointed arc.
 		      Node baseNode(const InArcIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Gives back the running node of the iterator.
 		      /// It is always the source of the pointed arc.
 		      Node runningNode(const InArcIt&) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Gives back the base node of the iterator.
 		      /// It is always the source of the pointed arc.
 		      Node baseNode(const OutArcIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Gives back the running node of the iterator.
 		      /// It is always the target of the pointed arc.
 		      Node runningNode(const OutArcIt&) const { return INVALID; }
 		      /// \brief The opposite node on the given arc.
 		      ///
 		      /// Gives back the opposite node on the given arc.
 		      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
 		      /// \brief Read write map of the nodes to type \c T.
 		      ///
 		      /// ReadWrite map of the nodes to type \c T.
 		      /// \sa Reference
 		      template<class T>
 		      class NodeMap : public ReadWriteMap< Node, T > {
 		      public:
 		        ///\e
 		        NodeMap(const Digraph&) { }
 		        ///\e
 		        NodeMap(const Digraph&, T) { }
 		        ///Copy constructor
 		        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief Read write map of the arcs to type \c T.
 		      ///
 		      /// Reference map of the arcs to type \c T.
 		      /// \sa Reference
 		      template<class T>
 		      class ArcMap : public ReadWriteMap<Arc,T> {
 		      public:
 		        ///\e
 		        ArcMap(const Digraph&) { }
 		        ///\e
 		        ArcMap(const Digraph&, T) { }
 		        ///Copy constructor
 		        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      template <typename RDigraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<IterableDigraphComponent<>, Digraph>();
 			  checkConcept<IDableDigraphComponent<>, Digraph>();
 		          checkConcept<MappableDigraphComponent<>, Digraph>();
+		        }
 		      };
 		    };
 		  } //namespace concepts
 		} //namespace lemon
 		#endif // LEMON_CONCEPT_DIGRAPH_H

lemon/concepts/graph.h

Show inline comments

@@ -243,460 +243,507 @@
 		        /// This constructor sets the iterator to the first edge.
 		        /// This constructor sets the iterator to the first edge.
 		        EdgeIt(const Graph&) { }
 		        /// Edge -> EdgeIt conversion
 		        /// Sets the iterator to the value of the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the edge-set, the iteration order is the
 			/// same.
 		        EdgeIt(const Graph&, const Edge&) { }
 		        /// Next edge
 		        /// Assign the iterator to the next edge.
 		        EdgeIt& operator++() { return *this; }
 		      };
 		      /// \brief This iterator goes trough the incident undirected
 		      /// arcs of a node.
 		      ///
 		      /// This iterator goes trough the incident edges
 		      /// of a certain node of a graph. You should assume that the
 		      /// loop arcs will be iterated twice.
 		      ///
 		      /// Its usage is quite simple, for example you can compute the
 		      /// degree (i.e. count the number of incident arcs of a node \c n
 		      /// in graph \c g of type \c Graph as follows.
 		      ///
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::IncArcIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class IncArcIt : public Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        IncArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        IncArcIt(const IncArcIt& e) : Edge(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        IncArcIt(Invalid) { }
 		        /// This constructor sets the iterator to first incident arc.
 		        /// This constructor set the iterator to the first incident arc of
 		        /// the node.
 		        IncArcIt(const Graph&, const Node&) { }
 		        /// Edge -> IncArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        IncArcIt(const Graph&, const Edge&) { }
 		        /// Next incident arc
 		        /// Assign the iterator to the next incident arc
 			/// of the corresponding node.
 		        IncArcIt& operator++() { return *this; }
 		      };
 		      /// The directed arc type.
 		      /// The directed arc type. It can be converted to the
 		      /// edge or it should be inherited from the undirected
 		      /// arc.
 		      class Arc : public Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        Arc() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Arc(const Arc& e) : Edge(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        Arc(Invalid) { }
 		        /// Equality operator
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are invalid.
 		        bool operator==(Arc) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Arc n)
 		        ///
 		        bool operator!=(Arc) const { return true; }
 			/// Artificial ordering operator.
 			/// To allow the use of graph descriptors as key type in std::map or
 			/// similar associative container we require this.
 			///
 			/// \note This operator only have to define some strict ordering of
 			/// the items; this order has nothing to do with the iteration
 			/// ordering of the items.
 			bool operator<(Arc) const { return false; }
 		      };
 		      /// This iterator goes through each directed arc.
 		      /// This iterator goes through each arc of a graph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of arcs in a graph \c g of type \c Graph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class ArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        ArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        ArcIt(const ArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        ArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first arc.
 		        /// This constructor sets the iterator to the first arc of \c g.
 		        ///@param g the graph
 		        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
 		        /// Arc -> ArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        ArcIt(const Graph&, const Arc&) { }
 		        ///Next arc
 		        /// Assign the iterator to the next arc.
 		        ArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes trough the outgoing directed arcs of a node.
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a graph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in graph \c g of type \c Graph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class OutArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        OutArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        OutArcIt(const OutArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        OutArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first outgoing arc.
 		        /// This constructor sets the iterator to the first outgoing arc of
 		        /// the node.
 		        ///@param n the node
 		        ///@param g the graph
 		        OutArcIt(const Graph& n, const Node& g) {
 			  ignore_unused_variable_warning(n);
 			  ignore_unused_variable_warning(g);
+			}
 		        /// Arc -> OutArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator.
 			/// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        OutArcIt(const Graph&, const Arc&) { }
 		        ///Next outgoing arc
 		        /// Assign the iterator to the next
 		        /// outgoing arc of the corresponding node.
 		        OutArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes trough the incoming directed arcs of a node.
 		      /// This iterator goes trough the \e incoming arcs of a certain node
 		      /// of a graph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in graph \c g of type \c Graph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class InArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        InArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        InArcIt(const InArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        InArcIt(Invalid) { }
 		        /// This constructor sets the iterator to first incoming arc.
 		        /// This constructor set the iterator to the first incoming arc of
 		        /// the node.
 		        ///@param n the node
 		        ///@param g the graph
 		        InArcIt(const Graph& g, const Node& n) {
 			  ignore_unused_variable_warning(n);
 			  ignore_unused_variable_warning(g);
+			}
 		        /// Arc -> InArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        InArcIt(const Graph&, const Arc&) { }
 		        /// Next incoming arc
 		        /// Assign the iterator to the next inarc of the corresponding node.
 		        ///
 		        InArcIt& operator++() { return *this; }
 		      };
 		      /// \brief Read write map of the nodes to type \c T.
 		      ///
 		      /// ReadWrite map of the nodes to type \c T.
 		      /// \sa Reference
 		      template<class T>
 		      class NodeMap : public ReadWriteMap< Node, T >
+		      {
 		      public:
 		        ///\e
 		        NodeMap(const Graph&) { }
 		        ///\e
 		        NodeMap(const Graph&, T) { }
 		        ///Copy constructor
 		        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief Read write map of the directed arcs to type \c T.
 		      ///
 		      /// Reference map of the directed arcs to type \c T.
 		      /// \sa Reference
 		      template<class T>
 		      class ArcMap : public ReadWriteMap<Arc,T>
+		      {
 		      public:
 		        ///\e
 		        ArcMap(const Graph&) { }
 		        ///\e
 		        ArcMap(const Graph&, T) { }
 		        ///Copy constructor
 		        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// Read write map of the edges to type \c T.
 		      /// Reference map of the arcs to type \c T.
 		      /// \sa Reference
 		      template<class T>
 		      class EdgeMap : public ReadWriteMap<Edge,T>
+		      {
 		      public:
 		        ///\e
 		        EdgeMap(const Graph&) { }
 		        ///\e
 		        EdgeMap(const Graph&, T) { }
 		        ///Copy constructor
 		        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
 		        ///Assignment operator
 		        template <typename CMap>
 		        EdgeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Edge, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief Direct the given edge.
 		      ///
 		      /// Direct the given edge. The returned arc source
 		      /// will be the given node.
 		      Arc direct(const Edge&, const Node&) const {
 			return INVALID;
+		      }
 		      /// \brief Direct the given edge.
 		      ///
 		      /// Direct the given edge. The returned arc
 		      /// represents the given edge and the direction comes
 		      /// from the bool parameter. The source of the edge and
 		      /// the directed arc is the same when the given bool is true.
 		      Arc direct(const Edge&, bool) const {
 			return INVALID;
+		      }
 		      /// \brief Returns true if the arc has default orientation.
 		      ///
 		      /// Returns whether the given directed arc is same orientation as
 		      /// the corresponding edge's default orientation.
 		      bool direction(Arc) const { return true; }
 		      /// \brief Returns the opposite directed arc.
 		      ///
 		      /// Returns the opposite directed arc.
 		      Arc oppositeArc(Arc) const { return INVALID; }
 		      /// \brief Opposite node on an arc
 		      ///
 		      /// \return the opposite of the given Node on the given Edge
 		      Node oppositeNode(Node, Edge) const { return INVALID; }
 		      /// \brief First node of the edge.
 		      ///
 		      /// \return the first node of the given Edge.
 		      ///
 		      /// Naturally edges don't have direction and thus
 		      /// don't have source and target node. But we use these two methods
 		      /// to query the two nodes of the arc. The direction of the arc
 		      /// which arises this way is called the inherent direction of the
 		      /// edge, and is used to define the "default" direction
 		      /// of the directed versions of the arcs.
 		      /// \sa direction
 		      Node u(Edge) const { return INVALID; }
 		      /// \brief Second node of the edge.
 		      Node v(Edge) const { return INVALID; }
 		      /// \brief Source node of the directed arc.
 		      Node source(Arc) const { return INVALID; }
 		      /// \brief Target node of the directed arc.
 		      Node target(Arc) const { return INVALID; }
 		      /// \brief Returns the id of the node.
 		      int id(Node) const { return -1; }
 		      /// \brief Returns the id of the edge.
 		      int id(Edge) const { return -1; }
 		      /// \brief Returns the id of the arc.
 		      int id(Arc) const { return -1; }
 		      /// \brief Returns the node with the given id.
 		      ///
 		      /// \pre The argument should be a valid node id in the graph.
 		      Node nodeFromId(int) const { return INVALID; }
 		      /// \brief Returns the edge with the given id.
 		      ///
 		      /// \pre The argument should be a valid edge id in the graph.
 		      Edge edgeFromId(int) const { return INVALID; }
 		      /// \brief Returns the arc with the given id.
 		      ///
 		      /// \pre The argument should be a valid arc id in the graph.
 		      Arc arcFromId(int) const { return INVALID; }
 		      /// \brief Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
 		      /// \brief Returns an upper bound on the edge IDs.
 		      int maxEdgeId() const { return -1; }
 		      /// \brief Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      void first(Node&) const {}
 		      void next(Node&) const {}
 		      void first(Edge&) const {}
 		      void next(Edge&) const {}
 		      void first(Arc&) const {}
 		      void next(Arc&) const {}
 		      void firstOut(Arc&, Node) const {}
 		      void nextOut(Arc&) const {}
 		      void firstIn(Arc&, Node) const {}
 		      void nextIn(Arc&) const {}
 		      void firstInc(Edge &, bool &, const Node &) const {}
 		      void nextInc(Edge &, bool &) const {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Edge fromId(int, Edge) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Edge) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
 		      /// \brief Base node of the iterator
 		      ///
 		      /// Returns the base node (the source in this case) of the iterator
 		      Node baseNode(OutArcIt e) const {
 			return source(e);
+		      }
 		      /// \brief Running node of the iterator
 		      ///
 		      /// Returns the running node (the target in this case) of the
 		      /// iterator
 		      Node runningNode(OutArcIt e) const {
 			return target(e);
+		      }
 		      /// \brief Base node of the iterator
 		      ///
 		      /// Returns the base node (the target in this case) of the iterator
 		      Node baseNode(InArcIt e) const {
 			return target(e);
+		      }
 		      /// \brief Running node of the iterator
 		      ///
 		      /// Returns the running node (the source in this case) of the
 		      /// iterator
 		      Node runningNode(InArcIt e) const {
 			return source(e);
+		      }
 		      /// \brief Base node of the iterator
 		      ///
 		      /// Returns the base node of the iterator
 		      Node baseNode(IncArcIt) const {
 			return INVALID;
+		      }
 		      /// \brief Running node of the iterator
 		      ///
 		      /// Returns the running node of the iterator
 		      Node runningNode(IncArcIt) const {
 			return INVALID;
+		      }
 		      template <typename Graph>
 		      struct Constraints {
 			void constraints() {
 			  checkConcept<IterableGraphComponent<>, Graph>();
 			  checkConcept<IDableGraphComponent<>, Graph>();
 			  checkConcept<MappableGraphComponent<>, Graph>();
+			}
 		      };
 		    };
+		  }
+		}
 		#endif

lemon/random.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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.
+		 *
 		 */
 		/*
 		 * This file contains the reimplemented version of the Mersenne Twister
 		 * Generator of Matsumoto and Nishimura.
+		 *
 		 * See the appropriate copyright notice below.
+		 *
 		 * Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
 		 * All rights reserved.
+		 *
 		 * Redistribution and use in source and binary forms, with or without
 		 * modification, are permitted provided that the following conditions
 		 * are met:
+		 *
 		 * 1. Redistributions of source code must retain the above copyright
 		 *    notice, this list of conditions and the following disclaimer.
+		 *
 		 * 2. Redistributions in binary form must reproduce the above copyright
 		 *    notice, this list of conditions and the following disclaimer in the
 		 *    documentation and/or other materials provided with the distribution.
+		 *
 		 * 3. The names of its contributors may not be used to endorse or promote
 		 *    products derived from this software without specific prior written
 		 *    permission.
+		 *
 		 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 		 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 		 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 		 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
 		 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 		 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 		 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 		 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 		 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 		 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 		 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 		 * OF THE POSSIBILITY OF SUCH DAMAGE.
+		 *
+		 *
 		 * Any feedback is very welcome.
 		 * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
 		 * email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
 		 */
 		#ifndef LEMON_RANDOM_H
 		#define LEMON_RANDOM_H
 		#include <algorithm>
 		#include <iterator>
 		#include <vector>
 		#include <ctime>
 		#include <cmath>
 		#include <lemon/dim2.h>
 		///\ingroup misc
 		///\file
 		///\brief Mersenne Twister random number generator
 		namespace lemon {
 		  namespace _random_bits {
 		    template <typename _Word, int _bits = std::numeric_limits<_Word>::digits>
 		    struct RandomTraits {};
 		    template <typename _Word>
 		    struct RandomTraits<_Word, 32> {
 		      typedef _Word Word;
 		      static const int bits = 32;
 		      static const int length = 624;
 		      static const int shift = 397;
 		      static const Word mul = 0x6c078965u;
 		      static const Word arrayInit = 0x012BD6AAu;
 		      static const Word arrayMul1 = 0x0019660Du;
 		      static const Word arrayMul2 = 0x5D588B65u;
 		      static const Word mask = 0x9908B0DFu;
 		      static const Word loMask = (1u << 31) - 1;
 		      static const Word hiMask = ~loMask;
 		      static Word tempering(Word rnd) {
 		        rnd ^= (rnd >> 11);
 		        rnd ^= (rnd << 7) & 0x9D2C5680u;
 		        rnd ^= (rnd << 15) & 0xEFC60000u;
 		        rnd ^= (rnd >> 18);
 		        return rnd;
+		      }
 		    };
 		    template <typename _Word>
 		    struct RandomTraits<_Word, 64> {
 		      typedef _Word Word;
 		      static const int bits = 64;
 		      static const int length = 312;
 		      static const int shift = 156;
 		      static const Word mul = Word(0x5851F42Du) << 32 | Word(0x4C957F2Du);
 		      static const Word arrayInit = Word(0x00000000u) << 32 |Word(0x012BD6AAu);
 		      static const Word arrayMul1 = Word(0x369DEA0Fu) << 32 |Word(0x31A53F85u);
 		      static const Word arrayMul2 = Word(0x27BB2EE6u) << 32 |Word(0x87B0B0FDu);
 		      static const Word mask = Word(0xB5026F5Au) << 32 | Word(0xA96619E9u);
 		      static const Word loMask = (Word(1u) << 31) - 1;
 		      static const Word hiMask = ~loMask;
 		      static Word tempering(Word rnd) {
 		        rnd ^= (rnd >> 29) & (Word(0x55555555u) << 32 | Word(0x55555555u));
 		        rnd ^= (rnd << 17) & (Word(0x71D67FFFu) << 32 | Word(0xEDA60000u));
 		        rnd ^= (rnd << 37) & (Word(0xFFF7EEE0u) << 32 | Word(0x00000000u));
 		        rnd ^= (rnd >> 43);
 		        return rnd;
+		      }
 		    };
 		    template <typename _Word>
 		    class RandomCore {
 		    public:
 		      typedef _Word Word;
 		    private:
 		      static const int bits = RandomTraits<Word>::bits;
 		      static const int length = RandomTraits<Word>::length;
 		      static const int shift = RandomTraits<Word>::shift;
 		    public:
 		      void initState() {
 		        static const Word seedArray[4] = {
 x12345u, 0x23456u, 0x34567u, 0x45678u
 		        };
 		        initState(seedArray, seedArray + 4);
+		      }
 		      void initState(Word seed) {
 		        static const Word mul = RandomTraits<Word>::mul;
 		        current = state;
 		        Word *curr = state + length - 1;
 		        curr[0] = seed; --curr;
 		        for (int i = 1; i < length; ++i) {
 		          curr[0] = (mul * ( curr[1] ^ (curr[1] >> (bits - 2)) ) + i);
 		          --curr;
+		        }
+		      }
 		      template <typename Iterator>
 		      void initState(Iterator begin, Iterator end) {
 		        static const Word init = RandomTraits<Word>::arrayInit;
 		        static const Word mul1 = RandomTraits<Word>::arrayMul1;
 		        static const Word mul2 = RandomTraits<Word>::arrayMul2;
 		        Word *curr = state + length - 1; --curr;
 		        Iterator it = begin; int cnt = 0;
 		        int num;
 		        initState(init);
 		        num = length > end - begin ? length : end - begin;
 		        while (num--) {
 		          curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul1))
 		            + *it + cnt;
 		          ++it; ++cnt;
 		          if (it == end) {
 		            it = begin; cnt = 0;
+		          }
 		          if (curr == state) {
 		            curr = state + length - 1; curr[0] = state[0];
+		          }
 		          --curr;
+		        }
 		        num = length - 1; cnt = length - (curr - state) - 1;
 		        while (num--) {
 		          curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul2))
 		            - cnt;
 		          --curr; ++cnt;
 		          if (curr == state) {
 		            curr = state + length - 1; curr[0] = state[0]; --curr;
 		            cnt = 1;
+		          }
+		        }
 		        state[length - 1] = Word(1) << (bits - 1);
+		      }
 		      void copyState(const RandomCore& other) {
 		        std::copy(other.state, other.state + length, state);
 		        current = state + (other.current - other.state);
+		      }
 		      Word operator()() {
 		        if (current == state) fillState();
 		        --current;
 		        Word rnd = *current;
 		        return RandomTraits<Word>::tempering(rnd);
+		      }
 		    private:
 		      void fillState() {
 		        static const Word mask[2] = { 0x0ul, RandomTraits<Word>::mask };
 		        static const Word loMask = RandomTraits<Word>::loMask;
 		        static const Word hiMask = RandomTraits<Word>::hiMask;
 		        current = state + length;
 		        register Word *curr = state + length - 1;
 		        register long num;
 		        num = length - shift;
 		        while (num--) {
 		          curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
 		            curr[- shift] ^ mask[curr[-1] & 1ul];
 		          --curr;
+		        }
 		        num = shift - 1;
 		        while (num--) {
 		          curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
 		            curr[length - shift] ^ mask[curr[-1] & 1ul];
 		          --curr;
+		        }
-		        curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
+		        state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
 		          curr[length - shift] ^ mask[curr[length - 1] & 1ul];
+		      }
 		      Word *current;
 		      Word state[length];
 		    };
 		    template <typename Result,
 		              int shift = (std::numeric_limits<Result>::digits + 1) / 2>
 		    struct Masker {
 		      static Result mask(const Result& result) {
 		        return Masker<Result, (shift + 1) / 2>::
 		          mask(static_cast<Result>(result | (result >> shift)));
+		      }
 		    };
 		    template <typename Result>
 		    struct Masker<Result, 1> {
 		      static Result mask(const Result& result) {
 		        return static_cast<Result>(result | (result >> 1));
+		      }
 		    };
 		    template <typename Result, typename Word,
 		              int rest = std::numeric_limits<Result>::digits, int shift = 0,
 		              bool last = rest <= std::numeric_limits<Word>::digits>
 		    struct IntConversion {
 		      static const int bits = std::numeric_limits<Word>::digits;
 		      static Result convert(RandomCore<Word>& rnd) {
 		        return static_cast<Result>(rnd() >> (bits - rest)) << shift;
+		      }
 		    };
 		    template <typename Result, typename Word, int rest, int shift>
 		    struct IntConversion<Result, Word, rest, shift, false> {
 		      static const int bits = std::numeric_limits<Word>::digits;
 		      static Result convert(RandomCore<Word>& rnd) {
 		        return (static_cast<Result>(rnd()) << shift) |
 		          IntConversion<Result, Word, rest - bits, shift + bits>::convert(rnd);
+		      }
 		    };
 		    template <typename Result, typename Word,
 		              bool one_word = (std::numeric_limits<Word>::digits <
 					       std::numeric_limits<Result>::digits) >
 		    struct Mapping {
 		      static Result map(RandomCore<Word>& rnd, const Result& bound) {
 		        Word max = Word(bound - 1);
 		        Result mask = Masker<Result>::mask(bound - 1);
 		        Result num;
 		        do {
 		          num = IntConversion<Result, Word>::convert(rnd) & mask;
 		        } while (num > max);
 		        return num;
+		      }
 		    };
 		    template <typename Result, typename Word>
 		    struct Mapping<Result, Word, false> {
 		      static Result map(RandomCore<Word>& rnd, const Result& bound) {
 		        Word max = Word(bound - 1);
 		        Word mask = Masker<Word, (std::numeric_limits<Result>::digits + 1) / 2>
 		          ::mask(max);
 		        Word num;
 		        do {
 		          num = rnd() & mask;
 		        } while (num > max);
 		        return num;
+		      }
 		    };
 		    template <typename Result, int exp, bool pos = (exp >= 0)>
 		    struct ShiftMultiplier {
 		      static const Result multiplier() {
 		        Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
 		        res *= res;
 		        if ((exp & 1) == 1) res *= static_cast<Result>(2.0);
 		        return res;
+		      }
 		    };
 		    template <typename Result, int exp>
 		    struct ShiftMultiplier<Result, exp, false> {
 		      static const Result multiplier() {
 		        Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
 		        res *= res;
 		        if ((exp & 1) == 1) res *= static_cast<Result>(0.5);
 		        return res;
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, 0, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0);
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, -20, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0/1048576.0);
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, -32, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0/424967296.0);
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, -53, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0/9007199254740992.0);
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, -64, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0/18446744073709551616.0);
+		      }
 		    };
 		    template <typename Result, int exp>
 		    struct Shifting {
 		      static Result shift(const Result& result) {
 		        return result * ShiftMultiplier<Result, exp>::multiplier();
+		      }
 		    };
 		    template <typename Result, typename Word,
 		              int rest = std::numeric_limits<Result>::digits, int shift = 0,
 		              bool last = rest <= std::numeric_limits<Word>::digits>
 		    struct RealConversion{
 		      static const int bits = std::numeric_limits<Word>::digits;
 		      static Result convert(RandomCore<Word>& rnd) {
 		        return Shifting<Result, - shift - rest>::
 		          shift(static_cast<Result>(rnd() >> (bits - rest)));
+		      }
 		    };
 		    template <typename Result, typename Word, int rest, int shift>
 		    struct RealConversion<Result, Word, rest, shift, false> {
 		      static const int bits = std::numeric_limits<Word>::digits;
 		      static Result convert(RandomCore<Word>& rnd) {
 		        return Shifting<Result, - shift - bits>::
 		          shift(static_cast<Result>(rnd())) +
 		          RealConversion<Result, Word, rest-bits, shift + bits>::
 		          convert(rnd);
+		      }
 		    };
 		    template <typename Result, typename Word>
 		    struct Initializer {
 		      template <typename Iterator>
 		      static void init(RandomCore<Word>& rnd, Iterator begin, Iterator end) {
 		        std::vector<Word> ws;
 		        for (Iterator it = begin; it != end; ++it) {
 		          ws.push_back(Word(*it));
+		        }
 		        rnd.initState(ws.begin(), ws.end());
+		      }
 		      static void init(RandomCore<Word>& rnd, Result seed) {
 		        rnd.initState(seed);
+		      }
 		    };
 		    template <typename Word>
 		    struct BoolConversion {
 		      static bool convert(RandomCore<Word>& rnd) {
 		        return (rnd() & 1) == 1;
+		      }
 		    };
 		    template <typename Word>
 		    struct BoolProducer {
 		      Word buffer;
 		      int num;
 		      BoolProducer() : num(0) {}
 		      bool convert(RandomCore<Word>& rnd) {
 		        if (num == 0) {
 		          buffer = rnd();
 		          num = RandomTraits<Word>::bits;
+		        }
 		        bool r = (buffer & 1);
 		        buffer >>= 1;
 		        --num;
 		        return r;
+		      }
 		    };
+		  }
 		  /// \ingroup misc
 		  ///
 		  /// \brief Mersenne Twister random number generator
 		  ///
 		  /// The Mersenne Twister is a twisted generalized feedback
 		  /// shift-register generator of Matsumoto and Nishimura. The period
 		  /// of this generator is \f$ 2^{19937} - 1 \f$ and it is
 		  /// equi-distributed in 623 dimensions for 32-bit numbers. The time
 		  /// performance of this generator is comparable to the commonly used
 		  /// generators.
 		  ///
 		  /// This implementation is specialized for both 32-bit and 64-bit
 		  /// architectures. The generators differ sligthly in the
 		  /// initialization and generation phase so they produce two
 		  /// completly different sequences.
 		  ///
 		  /// The generator gives back random numbers of serveral types. To
 		  /// get a random number from a range of a floating point type you
 		  /// can use one form of the \c operator() or the \c real() member
 		  /// function. If you want to get random number from the {0, 1, ...,
 		  /// n-1} integer range use the \c operator[] or the \c integer()
 		  /// method. And to get random number from the whole range of an
 		  /// integer type you can use the argumentless \c integer() or \c
 		  /// uinteger() functions. After all you can get random bool with
 		  /// equal chance of true and false or given probability of true
 		  /// result with the \c boolean() member functions.
 		  ///
 		  ///\code
 		  /// // The commented code is identical to the other
 		  /// double a = rnd();                     // [0.0, 1.0)
 		  /// // double a = rnd.real();             // [0.0, 1.0)
 		  /// double b = rnd(100.0);                // [0.0, 100.0)
 		  /// // double b = rnd.real(100.0);        // [0.0, 100.0)
 		  /// double c = rnd(1.0, 2.0);             // [1.0, 2.0)
 		  /// // double c = rnd.real(1.0, 2.0);     // [1.0, 2.0)
 		  /// int d = rnd[100000];                  // 0..99999
 		  /// // int d = rnd.integer(100000);       // 0..99999
 		  /// int e = rnd[6] + 1;                   // 1..6
 		  /// // int e = rnd.integer(1, 1 + 6);     // 1..6
 		  /// int b = rnd.uinteger<int>();          // 0 .. 2^31 - 1
 		  /// int c = rnd.integer<int>();           // - 2^31 .. 2^31 - 1
 		  /// bool g = rnd.boolean();               // P(g = true) = 0.5
 		  /// bool h = rnd.boolean(0.8);            // P(h = true) = 0.8
 		  ///\endcode
 		  ///
 		  /// LEMON provides a global instance of the random number
 		  /// generator which name is \ref lemon::rnd "rnd". Usually it is a
 		  /// good programming convenience to use this global generator to get
 		  /// random numbers.
 		  class Random {
 		  private:
 		    // Architecture word
 		    typedef unsigned long Word;
 		    _random_bits::RandomCore<Word> core;
 		    _random_bits::BoolProducer<Word> bool_producer;
 		  public:
 		    /// \brief Default constructor
 		    ///
 		    /// Constructor with constant seeding.
 		    Random() { core.initState(); }
 		    /// \brief Constructor with seed
 		    ///
 		    /// Constructor with seed. The current number type will be converted
 		    /// to the architecture word type.
 		    template <typename Number>
 		    Random(Number seed) {
 		      _random_bits::Initializer<Number, Word>::init(core, seed);
+		    }
 		    /// \brief Constructor with array seeding
 		    ///
 		    /// Constructor with array seeding. The given range should contain
 		    /// any number type and the numbers will be converted to the
 		    /// architecture word type.
 		    template <typename Iterator>
 		    Random(Iterator begin, Iterator end) {
 		      typedef typename std::iterator_traits<Iterator>::value_type Number;
 		      _random_bits::Initializer<Number, Word>::init(core, begin, end);
+		    }
 		    /// \brief Copy constructor
 		    ///
 		    /// Copy constructor. The generated sequence will be identical to
 		    /// the other sequence. It can be used to save the current state
 		    /// of the generator and later use it to generate the same
 		    /// sequence.
 		    Random(const Random& other) {
 		      core.copyState(other.core);
+		    }
 		    /// \brief Assign operator
 		    ///
 		    /// Assign operator. The generated sequence will be identical to
 		    /// the other sequence. It can be used to save the current state
 		    /// of the generator and later use it to generate the same
 		    /// sequence.
 		    Random& operator=(const Random& other) {
 		      if (&other != this) {
 		        core.copyState(other.core);
+		      }
 		      return *this;
+		    }
 		    /// \brief Returns a random real number from the range [0, 1)
 		    ///
 		    /// It returns a random real number from the range [0, 1). The
 		    /// default Number type is \c double.
 		    template <typename Number>
 		    Number real() {
 		      return _random_bits::RealConversion<Number, Word>::convert(core);
+		    }
 		    double real() {
 		      return real<double>();
+		    }
 		    /// \brief Returns a random real number the range [0, b)
 		    ///
 		    /// It returns a random real number from the range [0, b).
 		    template <typename Number>
 		    Number real(Number b) {
 		      return real<Number>() * b;
+		    }
 		    /// \brief Returns a random real number from the range [a, b)
 		    ///
 		    /// It returns a random real number from the range [a, b).
 		    template <typename Number>
 		    Number real(Number a, Number b) {
 		      return real<Number>() * (b - a) + a;
+		    }
 		    /// \brief Returns a random real number from the range [0, 1)
 		    ///
 		    /// It returns a random double from the range [0, 1).
 		    double operator()() {
 		      return real<double>();
+		    }
 		    /// \brief Returns a random real number from the range [0, b)
 		    ///
 		    /// It returns a random real number from the range [0, b).
 		    template <typename Number>
 		    Number operator()(Number b) {
 		      return real<Number>() * b;
+		    }
 		    /// \brief Returns a random real number from the range [a, b)
 		    ///
 		    /// It returns a random real number from the range [a, b).
 		    template <typename Number>
 		    Number operator()(Number a, Number b) {
 		      return real<Number>() * (b - a) + a;
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {0, 1, ..., b - 1}.
 		    template <typename Number>
 		    Number integer(Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b);
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {a, a + 1, ..., b - 1}.
 		    template <typename Number>
 		    Number integer(Number a, Number b) {

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/Makefile
 		noinst_HEADERS += \
 			test/digraph_test.h \
 			test/map_test.h \
 		        test/test_tools.h
 		check_PROGRAMS += \
 			test/digraph_test \
 		        test/dim_test \
 			test/graph_test \
 		        test/maps_test \
 		        test/random_test \
 		        test/path_test \
 		        test/test_tools_fail \
 		        test/test_tools_pass
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		#test_error_test_SOURCES = test/error_test.cc
 		test_graph_test_SOURCES = test/graph_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_path_test_SOURCES = test/path_test.cc
 		test_random_test_SOURCES = test/random_test.cc
 		test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 		test_test_tools_pass_SOURCES = test/test_tools_pass.cc

0 comments (0 inline)

RhodeCode

Login to your account