Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
22 //! \ingroup exceptions
24 //! \brief Basic exception classes and error handling.
35 /// \addtogroup exceptions
38 /// \brief Exception safe wrapper class.
40 /// Exception safe wrapper class to implement the members of exceptions.
41 template <typename _Type>
42 class ExceptionMember {
46 ExceptionMember() throw () {
48 ptr.reset(new Type());
52 ExceptionMember(const Type& type) throw () {
54 ptr.reset(new Type());
55 if (ptr.get() == 0) return;
60 ExceptionMember(const ExceptionMember& copy) throw() {
62 if (!copy.valid()) return;
63 ptr.reset(new Type());
64 if (ptr.get() == 0) return;
69 ExceptionMember& operator=(const ExceptionMember& copy) {
70 if (ptr.get() == 0) return;
72 if (!copy.valid()) return;
77 void set(const Type& type) {
78 if (ptr.get() == 0) return;
84 const Type& get() const {
89 return ptr.get() != 0;
93 std::auto_ptr<_Type> ptr;
96 /// Exception-safe convenient "error message" class.
98 /// Helper class which provides a convenient ostream-like (operator <<
99 /// based) interface to create a string message. Mostly useful in
100 /// exception classes (therefore the name).
105 ///\todo The good solution is boost::shared_ptr...
108 std::auto_ptr<std::ostringstream> buf;
111 bool init() throw() {
113 buf.reset(new std::ostringstream);
124 ErrorMessage() throw() { init(); }
126 ErrorMessage(const ErrorMessage& em) throw() : buf(em.buf) { }
129 ErrorMessage(const char *msg) throw() {
135 ErrorMessage(const std::string &msg) throw() {
141 template <typename T>
142 ErrorMessage& operator<<(const T &t) throw() {
143 if( ! buf.get() ) return *this;
155 const char* message() throw() {
156 if( ! buf.get() ) return 0;
160 mes = buf->str().c_str();
169 * \brief Generic exception class.
171 * Base class for exceptions used in LEMON.
173 class Exception : public std::exception {
178 virtual ~Exception() throw() {}
180 virtual const char* what() const throw() {
181 return "lemon::Exception";
186 * \brief One of the two main subclasses of \ref Exception.
188 * Logic errors represent problems in the internal logic of a program;
189 * in theory, these are preventable, and even detectable before the
190 * program runs (e.g., violations of class invariants).
192 * A typical example for this is \ref UninitializedParameter.
194 class LogicError : public Exception {
196 virtual const char* what() const throw() {
197 return "lemon::LogicError";
202 * \brief \ref Exception for uninitialized parameters.
204 * This error represents problems in the initialization
205 * of the parameters of the algorithms.
207 class UninitializedParameter : public LogicError {
209 virtual const char* what() const throw() {
210 return "lemon::UninitializedParameter";
216 * \brief One of the two main subclasses of \ref Exception.
218 * Runtime errors represent problems outside the scope of a program;
219 * they cannot be easily predicted and can generally only be caught as
220 * the program executes.
222 class RuntimeError : public Exception {
224 virtual const char* what() const throw() {
225 return "lemon::RuntimeError";
230 class RangeError : public RuntimeError {
232 virtual const char* what() const throw() {
233 return "lemon::RangeError";
238 class IoError : public RuntimeError {
240 virtual const char* what() const throw() {
241 return "lemon::IoError";
246 class DataFormatError : public IoError {
248 ExceptionMember<std::string> _message;
249 ExceptionMember<std::string> _file;
252 mutable ExceptionMember<std::string> _message_holder;
255 DataFormatError(const DataFormatError &dfe) :
256 IoError(dfe), _message(dfe._message), _file(dfe._file),
260 explicit DataFormatError(const char *the_message)
261 : _message(the_message), _line(0) {}
264 DataFormatError(const std::string &file_name, int line_num,
265 const char *the_message)
266 : _message(the_message), _line(line_num) { file(file_name); }
269 void line(int ln) { _line = ln; }
271 void message(const std::string& msg) { _message.set(msg); }
273 void file(const std::string &fl) { _file.set(fl); }
276 int line() const { return _line; }
278 const char* message() const {
279 if (_message.valid() && !_message.get().empty()) {
280 return _message.get().c_str();
286 /// \brief Returns the filename.
288 /// Returns \e null if the filename was not specified.
289 const char* file() const {
290 if (_file.valid() && !_file.get().empty()) {
291 return _file.get().c_str();
298 virtual const char* what() const throw() {
300 std::ostringstream ostr;
301 ostr << "lemon:DataFormatError" << ": ";
302 if (message()) ostr << message();
303 if( file() || line() != 0 ) {
305 if( file() ) ostr << "in file '" << file() << "'";
306 if( file() && line() != 0 ) ostr << " ";
307 if( line() != 0 ) ostr << "at line " << line();
310 _message_holder.set(ostr.str());
313 if( _message_holder.valid()) return _message_holder.get().c_str();
314 return "lemon:DataFormatError";
317 virtual ~DataFormatError() throw() {}
321 class FileOpenError : public IoError {
323 ExceptionMember<std::string> _file;
325 mutable ExceptionMember<std::string> _message_holder;
328 FileOpenError(const FileOpenError &foe) :
329 IoError(foe), _file(foe._file) {}
332 explicit FileOpenError(const std::string& fl)
337 void file(const std::string &fl) { _file.set(fl); }
339 /// \brief Returns the filename.
341 /// Returns \e null if the filename was not specified.
342 const char* file() const {
343 if (_file.valid() && !_file.get().empty()) {
344 return _file.get().c_str();
351 virtual const char* what() const throw() {
353 std::ostringstream ostr;
354 ostr << "lemon::FileOpenError" << ": ";
355 ostr << "Cannot open file - " << file();
356 _message_holder.set(ostr.str());
359 if( _message_holder.valid()) return _message_holder.get().c_str();
360 return "lemon::FileOpenError";
362 virtual ~FileOpenError() throw() {}
365 class IoParameterError : public IoError {
367 ExceptionMember<std::string> _message;
368 ExceptionMember<std::string> _file;
370 mutable ExceptionMember<std::string> _message_holder;
373 IoParameterError(const IoParameterError &ile) :
374 IoError(ile), _message(ile._message), _file(ile._file) {}
377 explicit IoParameterError(const char *the_message)
378 : _message(the_message) {}
381 IoParameterError(const char *file_name, const char *the_message)
382 : _message(the_message), _file(file_name) {}
385 void message(const std::string& msg) { _message.set(msg); }
387 void file(const std::string &fl) { _file.set(fl); }
390 const char* message() const {
391 if (_message.valid()) {
392 return _message.get().c_str();
398 /// \brief Returns the filename.
400 /// Returns \e null if the filename was not specified.
401 const char* file() const {
403 return _file.get().c_str();
410 virtual const char* what() const throw() {
412 std::ostringstream ostr;
413 if (message()) ostr << message();
414 if (file()) ostr << "(when reading file '" << file() << "')";
415 _message_holder.set(ostr.str());
418 if( _message_holder.valid() ) return _message_holder.get().c_str();
419 return "lemon:IoParameterError";
421 virtual ~IoParameterError() throw() {}
426 class AssertionFailedError : public LogicError {
428 const char *assertion;
431 const char *function;
434 mutable ExceptionMember<std::string> _message_holder;
437 AssertionFailedError(const char *_file, int _line, const char *func,
438 const char *msg, const char *_assertion = 0) :
439 assertion(_assertion), file(_file), line(_line), function(func),
443 const char* get_assertion() const { return assertion; }
445 const char* get_message() const { return message; }
447 const char* get_file() const { return file; }
449 const char* get_function() const { return function; }
451 int get_line() const { return line; }
454 virtual const char* what() const throw() {
456 std::ostringstream ostr;
457 ostr << file << ":" << line << ": ";
459 ostr << function << ": ";
462 ostr << " (assertion '" << assertion << "' failed)";
463 _message_holder.set(ostr.str());
464 return ostr.str().c_str();
467 if( _message_holder.valid() ) return _message_holder.get().c_str();
468 return "lemon::AssertionFailedError";
470 virtual ~AssertionFailedError() throw() {}
474 /**************** Macros ****************/
477 template <typename Exception>
478 inline void assert_fail(const char *file, int line,
481 const char *assertion = 0,
485 cerr << file << ":" << line << ": ";
487 cerr << func << ": ";
488 cerr << exception.what();
490 cerr << " (assertion '" << assertion << "' failed)";
497 inline void assert_fail<const char *>(const char *file, int line,
500 const char *assertion,
504 cerr << file << ":" << line << ": ";
506 cerr << func << ": ";
509 cerr << " (assertion '" << assertion << "' failed)";
516 inline void assert_fail<std::string>(const char *file, int line,
519 const char *assertion,
522 assert_fail(file, line, func, message.c_str(), assertion, do_abort);
525 template <typename Exception>
526 inline void assert_fail_failure(const char *file, int line, const char *func,
528 const char *assertion = 0,
531 throw AssertionFailedError(file, line, func, exception.what(), assertion);
535 inline void assert_fail_failure<const char *>(const char *file, int line,
538 const char *assertion,
541 throw AssertionFailedError(file, line, func, message, assertion);
545 inline void assert_fail_failure<std::string>(const char *file, int line,
548 const char *assertion,
551 assert_fail_failure(file, line, func, message.c_str(), assertion, true);
554 template <typename Exception>
555 inline void assert_fail_exception(const char *file, int line, const char *func,
557 const char *assertion = 0, bool = true)
563 inline void assert_fail_exception<const char *>(const char *file, int line,
566 const char *assertion,
569 throw AssertionFailedError(file, line, func, message, assertion);
573 inline void assert_fail_exception<std::string>(const char *file, int line,
576 const char *assertion,
579 assert_fail_exception(file, line, func, message.c_str(), assertion, true);
585 #endif // LEMON_ERROR_H
590 #ifdef LEMON_ENABLE_ASSERTS
591 # define LEMON_ASSERT_ABORT
594 #ifndef LEMON_ASSERT_DO_ABORT
595 # define LEMON_ASSERT_DO_ABORT 1
598 #ifndef LEMON_ASSERT_HANDLER
599 # if defined LEMON_ASSERT_EXCEPTION
600 # define LEMON_ASSERT_HANDLER ::lemon::assert_fail_exception
601 # elif defined LEMON_ASSERT_FAILURE
602 # define LEMON_ASSERT_HANDLER ::lemon::assert_fail_failure
603 # elif defined LEMON_ASSERT_ABORT
604 # define LEMON_ASSERT_HANDLER ::lemon::assert_fail
606 # define LEMON_DISABLE_ASSERTS
612 /// \brief Macro for assertions with customizable message
614 /// Macro for assertions with customizable message.
616 /// The assertions are disabled in the default behaviour. You can
617 /// enable the assertions with the
619 /// #define LEMON_ENABLE_ASSERTS
622 /// provides a log on the standard error about the assertion and aborts
623 /// the program if LEMON_ASSERT_DO_ABORT is also defined (otherwise the
624 /// program keeps on running).
625 /// By defining LEMON_ASSERT_FAILURE or
626 /// LEMON_ASSERT_EXCEPTION, you can set other behaviour to the
627 /// assertions. In case LEMON_ASSERT_FAILURE is given, LEMON_ASSERT
628 /// will always throw an \c AssertionFailedError exception with
629 /// the \c msg error message. By using
630 /// LEMON_ASSERT_EXCEPTION, one can define an arbitrary exception to be thrown.
632 /// The LEMON_ASSERT macro should be called with the \c exp parameter
633 /// which should be an expression convertible to bool. If the given
634 /// parameter is false the assertion is raised and one of the assertion
635 /// behaviour will be activated. The \c msg should be either a const
636 /// char* message or an exception. When the \c msg is an exception the
637 /// \ref lemon::Exception::what() "what()" function is called to retrieve and
638 /// display the error message.
640 /// \todo We should provide some way to reset to the default behaviour,
643 /// \todo This whole 'assert' business should be placed in a separate
644 /// include file. The boost assert is not guarded by header sentries
645 /// which may help to change the behaviour of the assertions in
648 /// \todo __PRETTY_FUNCTION__ should be replaced by something
649 /// compiler-independent, like BOOST_CURRENT_FUNCTION
651 # define LEMON_ASSERT(exp, msg) \
652 (static_cast<void> (!!(exp) ? 0 : ( \
653 LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \
654 __PRETTY_FUNCTION__, \
655 msg, #exp, LEMON_ASSERT_DO_ABORT), 0)))
658 # if defined LEMON_DISABLE_ASSERTS
660 # define LEMON_ASSERT(exp, msg) (static_cast<void> (0))
663 # define LEMON_ASSERT(exp, msg) \
664 (static_cast<void> (!!(exp) ? 0 : ( \
665 LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \
666 __PRETTY_FUNCTION__, \
667 msg, #exp, LEMON_ASSERT_DO_ABORT), 0)))
672 * \brief Macro for mark not yet implemented features.
674 * \todo Is this the right place for this? It should be used only in
675 * modules under development.
677 * \todo __PRETTY_FUNCTION__ should be replaced by something
678 * compiler-independent, like BOOST_CURRENT_FUNCTION
681 # define LEMON_FIXME(msg) \
682 (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, __PRETTY_FUNCTION__, \