Index: LICENSE =================================================================== --- LICENSE (revision 107) +++ LICENSE (revision 440) @@ -2,5 +2,5 @@ copyright/license. -Copyright (C) 2003-2008 Egervary Jeno Kombinatorikus Optimalizalasi +Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport (Egervary Combinatorial Optimization Research Group, EGRES). Index: demo/arg_parser_demo.cc =================================================================== --- demo/arg_parser_demo.cc (revision 311) +++ demo/arg_parser_demo.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: demo/graph_to_eps_demo.cc =================================================================== --- demo/graph_to_eps_demo.cc (revision 313) +++ demo/graph_to_eps_demo.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -86,5 +86,5 @@ coords(coords). title("Sample .eps figure"). - copyright("(C) 2003-2008 LEMON Project"). + copyright("(C) 2003-2009 LEMON Project"). run(); @@ -93,5 +93,5 @@ coords(coords). title("Sample .eps figure"). - copyright("(C) 2003-2008 LEMON Project"). + copyright("(C) 2003-2009 LEMON Project"). absoluteNodeSizes().absoluteArcWidths(). nodeScale(2).nodeSizes(sizes). @@ -106,5 +106,5 @@ graphToEps(g,"graph_to_eps_demo_out_3_arr.eps"). title("Sample .eps figure (with arrowheads)"). - copyright("(C) 2003-2008 LEMON Project"). + copyright("(C) 2003-2009 LEMON Project"). absoluteNodeSizes().absoluteArcWidths(). nodeColors(composeMap(palette,colors)). @@ -133,5 +133,5 @@ graphToEps(g,"graph_to_eps_demo_out_4_par.eps"). title("Sample .eps figure (parallel arcs)"). - copyright("(C) 2003-2008 LEMON Project"). + copyright("(C) 2003-2009 LEMON Project"). absoluteNodeSizes().absoluteArcWidths(). nodeShapes(shapes). @@ -148,5 +148,5 @@ graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps"). title("Sample .eps figure (parallel arcs and arrowheads)"). - copyright("(C) 2003-2008 LEMON Project"). + copyright("(C) 2003-2009 LEMON Project"). absoluteNodeSizes().absoluteArcWidths(). nodeScale(2).nodeSizes(sizes). @@ -164,5 +164,5 @@ graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps"). title("Sample .eps figure (fits to A4)"). - copyright("(C) 2003-2008 LEMON Project"). + copyright("(C) 2003-2009 LEMON Project"). scaleToA4(). absoluteNodeSizes().absoluteArcWidths(). @@ -194,5 +194,5 @@ scale(60). title("Sample .eps figure (Palette demo)"). - copyright("(C) 2003-2008 LEMON Project"). + copyright("(C) 2003-2009 LEMON Project"). coords(hcoords). absoluteNodeSizes().absoluteArcWidths(). Index: demo/lgf_demo.cc =================================================================== --- demo/lgf_demo.cc (revision 294) +++ demo/lgf_demo.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: doc/coding_style.dox =================================================================== --- doc/coding_style.dox (revision 210) +++ doc/coding_style.dox (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: doc/dirs.dox =================================================================== --- doc/dirs.dox (revision 318) +++ doc/dirs.dox (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -72,5 +72,5 @@ \brief Auxiliary tools for implementation. -This directory contains some auxiliary classes for implementing graphs, +This directory contains some auxiliary classes for implementing graphs, maps and some other classes. As a user you typically don't have to deal with these files. Index: doc/groups.dox =================================================================== --- doc/groups.dox (revision 451) +++ doc/groups.dox (revision 455) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: doc/lgf.dox =================================================================== --- doc/lgf.dox (revision 313) +++ doc/lgf.dox (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: doc/license.dox =================================================================== --- doc/license.dox (revision 209) +++ doc/license.dox (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: doc/mainpage.dox =================================================================== --- doc/mainpage.dox (revision 314) +++ doc/mainpage.dox (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: doc/migration.dox =================================================================== --- doc/migration.dox (revision 343) +++ doc/migration.dox (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: doc/named-param.dox =================================================================== --- doc/named-param.dox (revision 269) +++ doc/named-param.dox (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: doc/namespaces.dox =================================================================== --- doc/namespaces.dox (revision 209) +++ doc/namespaces.dox (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: doc/template.h =================================================================== --- doc/template.h (revision 209) +++ doc/template.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/Makefile.am =================================================================== --- lemon/Makefile.am (revision 418) +++ lemon/Makefile.am (revision 445) @@ -8,8 +8,8 @@ lemon_libemon_la_SOURCES = \ - lemon/arg_parser.cc \ - lemon/base.cc \ - lemon/color.cc \ - lemon/random.cc + lemon/arg_parser.cc \ + lemon/base.cc \ + lemon/color.cc \ + lemon/random.cc #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS) @@ -18,22 +18,22 @@ lemon_HEADERS += \ lemon/adaptors.h \ - lemon/arg_parser.h \ + lemon/arg_parser.h \ lemon/assert.h \ - lemon/bfs.h \ - lemon/bin_heap.h \ - lemon/circulation.h \ - lemon/color.h \ + lemon/bfs.h \ + lemon/bin_heap.h \ + lemon/circulation.h \ + lemon/color.h \ lemon/concept_check.h \ - lemon/counter.h \ + lemon/counter.h \ lemon/core.h \ - lemon/dfs.h \ - lemon/dijkstra.h \ - lemon/dim2.h \ - lemon/dimacs.h \ + lemon/dfs.h \ + lemon/dijkstra.h \ + lemon/dim2.h \ + lemon/dimacs.h \ lemon/elevator.h \ lemon/error.h \ lemon/full_graph.h \ - lemon/graph_to_eps.h \ - lemon/grid_graph.h \ + lemon/graph_to_eps.h \ + lemon/grid_graph.h \ lemon/hypercube_graph.h \ lemon/kruskal.h \ @@ -48,9 +48,10 @@ lemon/path.h \ lemon/preflow.h \ - lemon/random.h \ + lemon/radix_sort.h \ + lemon/random.h \ lemon/smart_graph.h \ lemon/suurballe.h \ - lemon/time_measure.h \ - lemon/tolerance.h \ + lemon/time_measure.h \ + lemon/tolerance.h \ lemon/unionfind.h @@ -59,7 +60,7 @@ lemon/bits/array_map.h \ lemon/bits/base_extender.h \ - lemon/bits/bezier.h \ + lemon/bits/bezier.h \ lemon/bits/default_map.h \ - lemon/bits/enable_if.h \ + lemon/bits/enable_if.h \ lemon/bits/graph_adaptor_extender.h \ lemon/bits/graph_extender.h \ Index: lemon/arg_parser.cc =================================================================== --- lemon/arg_parser.cc (revision 311) +++ lemon/arg_parser.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/arg_parser.h =================================================================== --- lemon/arg_parser.h (revision 311) +++ lemon/arg_parser.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/assert.h =================================================================== --- lemon/assert.h (revision 290) +++ lemon/assert.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/base.cc =================================================================== --- lemon/base.cc (revision 220) +++ lemon/base.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bfs.h =================================================================== --- lemon/bfs.h (revision 405) +++ lemon/bfs.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -1742,5 +1742,5 @@ /// \pre Either \ref run(Node) "run()" or \ref init() /// must be called before using this function. - bool reached(Node v) { return (*_reached)[v]; } + bool reached(Node v) const { return (*_reached)[v]; } ///@} Index: lemon/bin_heap.h =================================================================== --- lemon/bin_heap.h (revision 209) +++ lemon/bin_heap.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/alteration_notifier.h =================================================================== --- lemon/bits/alteration_notifier.h (revision 361) +++ lemon/bits/alteration_notifier.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/array_map.h =================================================================== --- lemon/bits/array_map.h (revision 361) +++ lemon/bits/array_map.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/base_extender.h =================================================================== --- lemon/bits/base_extender.h (revision 361) +++ lemon/bits/base_extender.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/bezier.h =================================================================== --- lemon/bits/bezier.h (revision 314) +++ lemon/bits/bezier.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/default_map.h =================================================================== --- lemon/bits/default_map.h (revision 314) +++ lemon/bits/default_map.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/enable_if.h =================================================================== --- lemon/bits/enable_if.h (revision 314) +++ lemon/bits/enable_if.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/graph_adaptor_extender.h =================================================================== --- lemon/bits/graph_adaptor_extender.h (revision 453) +++ lemon/bits/graph_adaptor_extender.h (revision 455) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/graph_extender.h =================================================================== --- lemon/bits/graph_extender.h (revision 361) +++ lemon/bits/graph_extender.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/map_extender.h =================================================================== --- lemon/bits/map_extender.h (revision 314) +++ lemon/bits/map_extender.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/path_dump.h =================================================================== --- lemon/bits/path_dump.h (revision 209) +++ lemon/bits/path_dump.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/traits.h =================================================================== --- lemon/bits/traits.h (revision 360) +++ lemon/bits/traits.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/bits/variant.h =================================================================== --- lemon/bits/variant.h (revision 416) +++ lemon/bits/variant.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -22,6 +22,6 @@ #include -/// \file -/// \brief Variant types +// \file +// \brief Variant types namespace lemon { @@ -37,25 +37,25 @@ - /// \brief Simple Variant type for two types - /// - /// Simple Variant type for two types. The Variant type is a type - /// safe union. The C++ has strong limitations for using unions, by - /// example we can not store type with non default constructor or - /// destructor in an union. This class always knowns the current - /// state of the variant and it cares for the proper construction - /// and destruction. + // \brief Simple Variant type for two types + // + // Simple Variant type for two types. The Variant type is a type-safe + // union. C++ has strong limitations for using unions, for + // example you cannot store a type with non-default constructor or + // destructor in a union. This class always knowns the current + // state of the variant and it cares for the proper construction + // and destruction. template class BiVariant { public: - /// \brief The \c First type. + // \brief The \c First type. typedef _First First; - /// \brief The \c Second type. + // \brief The \c Second type. typedef _Second Second; - /// \brief Constructor - /// - /// This constructor initalizes to the default value of the \c First - /// type. + // \brief Constructor + // + // This constructor initalizes to the default value of the \c First + // type. BiVariant() { flag = true; @@ -63,8 +63,8 @@ } - /// \brief Constructor - /// - /// This constructor initalizes to the given value of the \c First - /// type. + // \brief Constructor + // + // This constructor initalizes to the given value of the \c First + // type. BiVariant(const First& f) { flag = true; @@ -72,8 +72,8 @@ } - /// \brief Constructor - /// - /// This constructor initalizes to the given value of the \c - /// Second type. + // \brief Constructor + // + // This constructor initalizes to the given value of the \c + // Second type. BiVariant(const Second& s) { flag = false; @@ -81,7 +81,7 @@ } - /// \brief Copy constructor - /// - /// Copy constructor + // \brief Copy constructor + // + // Copy constructor BiVariant(const BiVariant& bivariant) { flag = bivariant.flag; @@ -93,15 +93,15 @@ } - /// \brief Destrcutor - /// - /// Destructor + // \brief Destrcutor + // + // Destructor ~BiVariant() { destroy(); } - /// \brief Set to the default value of the \c First type. - /// - /// This function sets the variant to the default value of the \c - /// First type. + // \brief Set to the default value of the \c First type. + // + // This function sets the variant to the default value of the \c + // First type. BiVariant& setFirst() { destroy(); @@ -111,8 +111,8 @@ } - /// \brief Set to the given value of the \c First type. - /// - /// This function sets the variant to the given value of the \c - /// First type. + // \brief Set to the given value of the \c First type. + // + // This function sets the variant to the given value of the \c + // First type. BiVariant& setFirst(const First& f) { destroy(); @@ -122,8 +122,8 @@ } - /// \brief Set to the default value of the \c Second type. - /// - /// This function sets the variant to the default value of the \c - /// Second type. + // \brief Set to the default value of the \c Second type. + // + // This function sets the variant to the default value of the \c + // Second type. BiVariant& setSecond() { destroy(); @@ -133,8 +133,8 @@ } - /// \brief Set to the given value of the \c Second type. - /// - /// This function sets the variant to the given value of the \c - /// Second type. + // \brief Set to the given value of the \c Second type. + // + // This function sets the variant to the given value of the \c + // Second type. BiVariant& setSecond(const Second& s) { destroy(); @@ -144,15 +144,15 @@ } - /// \brief Operator form of the \c setFirst() + // \brief Operator form of the \c setFirst() BiVariant& operator=(const First& f) { return setFirst(f); } - /// \brief Operator form of the \c setSecond() + // \brief Operator form of the \c setSecond() BiVariant& operator=(const Second& s) { return setSecond(s); } - /// \brief Assign operator + // \brief Assign operator BiVariant& operator=(const BiVariant& bivariant) { if (this == &bivariant) return *this; @@ -167,58 +167,58 @@ } - /// \brief Reference to the value - /// - /// Reference to the value of the \c First type. - /// \pre The BiVariant should store value of \c First type. + // \brief Reference to the value + // + // Reference to the value of the \c First type. + // \pre The BiVariant should store value of \c First type. First& first() { LEMON_DEBUG(flag, "Variant wrong state"); - return *reinterpret_cast(data); - } - - /// \brief Const reference to the value - /// - /// Const reference to the value of the \c First type. - /// \pre The BiVariant should store value of \c First type. - const First& first() const { + return *reinterpret_cast(data); + } + + // \brief Const reference to the value + // + // Const reference to the value of the \c First type. + // \pre The BiVariant should store value of \c First type. + const First& first() const { LEMON_DEBUG(flag, "Variant wrong state"); - return *reinterpret_cast(data); - } - - /// \brief Operator form of the \c first() + return *reinterpret_cast(data); + } + + // \brief Operator form of the \c first() operator First&() { return first(); } - /// \brief Operator form of the const \c first() + // \brief Operator form of the const \c first() operator const First&() const { return first(); } - /// \brief Reference to the value - /// - /// Reference to the value of the \c Second type. - /// \pre The BiVariant should store value of \c Second type. - Second& second() { + // \brief Reference to the value + // + // Reference to the value of the \c Second type. + // \pre The BiVariant should store value of \c Second type. + Second& second() { LEMON_DEBUG(!flag, "Variant wrong state"); - return *reinterpret_cast(data); - } - - /// \brief Const reference to the value - /// - /// Const reference to the value of the \c Second type. - /// \pre The BiVariant should store value of \c Second type. - const Second& second() const { + return *reinterpret_cast(data); + } + + // \brief Const reference to the value + // + // Const reference to the value of the \c Second type. + // \pre The BiVariant should store value of \c Second type. + const Second& second() const { LEMON_DEBUG(!flag, "Variant wrong state"); - return *reinterpret_cast(data); - } - - /// \brief Operator form of the \c second() + return *reinterpret_cast(data); + } + + // \brief Operator form of the \c second() operator Second&() { return second(); } - /// \brief Operator form of the const \c second() + // \brief Operator form of the const \c second() operator const Second&() const { return second(); } - /// \brief %True when the variant is in the first state - /// - /// %True when the variant stores value of the \c First type. + // \brief %True when the variant is in the first state + // + // %True when the variant stores value of the \c First type. bool firstState() const { return flag; } - /// \brief %True when the variant is in the second state - /// - /// %True when the variant stores value of the \c Second type. + // \brief %True when the variant is in the second state + // + // %True when the variant stores value of the \c Second type. bool secondState() const { return !flag; } @@ -290,38 +290,38 @@ } - /// \brief Variant type - /// - /// Simple Variant type. The Variant type is a type safe union. The - /// C++ has strong limitations for using unions, for example we - /// cannot store type with non default constructor or destructor in - /// a union. This class always knowns the current state of the - /// variant and it cares for the proper construction and - /// destruction. - /// - /// \param _num The number of the types which can be stored in the - /// variant type. - /// \param _TypeMap This class describes the types of the Variant. The - /// _TypeMap::Map::Type should be a valid type for each index - /// in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper - /// class to define such type mappings up to 10 types. - /// - /// And the usage of the class: - ///\code - /// typedef Variant<3, VariantTypeMap > MyVariant; - /// MyVariant var; - /// var.set<0>(12); - /// std::cout << var.get<0>() << std::endl; - /// var.set<1>("alpha"); - /// std::cout << var.get<1>() << std::endl; - /// var.set<2>(0.75); - /// std::cout << var.get<2>() << std::endl; - ///\endcode - /// - /// The result of course: - ///\code - /// 12 - /// alpha - /// 0.75 - ///\endcode + // \brief Variant type + // + // Simple Variant type. The Variant type is a type-safe union. + // C++ has strong limitations for using unions, for example you + // cannot store type with non-default constructor or destructor in + // a union. This class always knowns the current state of the + // variant and it cares for the proper construction and + // destruction. + // + // \param _num The number of the types which can be stored in the + // variant type. + // \param _TypeMap This class describes the types of the Variant. The + // _TypeMap::Map::Type should be a valid type for each index + // in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper + // class to define such type mappings up to 10 types. + // + // And the usage of the class: + //\code + // typedef Variant<3, VariantTypeMap > MyVariant; + // MyVariant var; + // var.set<0>(12); + // std::cout << var.get<0>() << std::endl; + // var.set<1>("alpha"); + // std::cout << var.get<1>() << std::endl; + // var.set<2>(0.75); + // std::cout << var.get<2>() << std::endl; + //\endcode + // + // The result of course: + //\code + // 12 + // alpha + // 0.75 + //\endcode template class Variant { @@ -332,8 +332,8 @@ typedef _TypeMap TypeMap; - /// \brief Constructor - /// - /// This constructor initalizes to the default value of the \c type - /// with 0 index. + // \brief Constructor + // + // This constructor initalizes to the default value of the \c type + // with 0 index. Variant() { flag = 0; @@ -343,7 +343,7 @@ - /// \brief Copy constructor - /// - /// Copy constructor + // \brief Copy constructor + // + // Copy constructor Variant(const Variant& variant) { flag = variant.flag; @@ -351,7 +351,7 @@ } - /// \brief Assign operator - /// - /// Assign operator + // \brief Assign operator + // + // Assign operator Variant& operator=(const Variant& variant) { if (this == &variant) return *this; @@ -364,15 +364,15 @@ } - /// \brief Destrcutor - /// - /// Destructor + // \brief Destrcutor + // + // Destructor ~Variant() { _variant_bits::Memory::destroy(flag, data); } - /// \brief Set to the default value of the type with \c _idx index. - /// - /// This function sets the variant to the default value of the - /// type with \c _idx index. + // \brief Set to the default value of the type with \c _idx index. + // + // This function sets the variant to the default value of the + // type with \c _idx index. template Variant& set() { @@ -384,8 +384,8 @@ } - /// \brief Set to the given value of the type with \c _idx index. - /// - /// This function sets the variant to the given value of the type - /// with \c _idx index. + // \brief Set to the given value of the type with \c _idx index. + // + // This function sets the variant to the given value of the type + // with \c _idx index. template Variant& set(const typename _TypeMap::template Map<_idx>::Type& init) { @@ -397,7 +397,7 @@ } - /// \brief Gets the current value of the type with \c _idx index. - /// - /// Gets the current value of the type with \c _idx index. + // \brief Gets the current value of the type with \c _idx index. + // + // Gets the current value of the type with \c _idx index. template const typename TypeMap::template Map<_idx>::Type& get() const { @@ -407,7 +407,7 @@ } - /// \brief Gets the current value of the type with \c _idx index. - /// - /// Gets the current value of the type with \c _idx index. + // \brief Gets the current value of the type with \c _idx index. + // + // Gets the current value of the type with \c _idx index. template typename _TypeMap::template Map<_idx>::Type& get() { @@ -417,7 +417,7 @@ } - /// \brief Returns the current state of the variant. - /// - /// Returns the current state of the variant. + // \brief Returns the current state of the variant. + // + // Returns the current state of the variant. int state() const { return flag; @@ -451,5 +451,5 @@ template struct Mapper { @@ -470,13 +470,13 @@ } - /// \brief Helper class for Variant - /// - /// Helper class to define type mappings for Variant. This class - /// converts the template parameters to be mappable by integer. - /// \see Variant + // \brief Helper class for Variant + // + // Helper class to define type mappings for Variant. This class + // converts the template parameters to be mappable by integer. + // \see Variant template < typename _T0, typename _T1 = void, typename _T2 = void, typename _T3 = void, - typename _T5 = void, typename _T4 = void, typename _T6 = void, + typename _T4 = void, typename _T5 = void, typename _T6 = void, typename _T7 = void, typename _T8 = void, typename _T9 = void> struct VariantTypeMap { Index: lemon/bits/vector_map.h =================================================================== --- lemon/bits/vector_map.h (revision 361) +++ lemon/bits/vector_map.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/circulation.h =================================================================== --- lemon/circulation.h (revision 402) +++ lemon/circulation.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -420,5 +420,5 @@ /// \pre Either \ref run() or \ref init() must be called before /// using this function. - const Elevator& elevator() { + const Elevator& elevator() const { return *_level; } @@ -645,5 +645,5 @@ /// \pre Either \ref run() or \ref init() must be called before /// using this function. - const FlowMap& flowMap() { + const FlowMap& flowMap() const { return *_flow; } @@ -670,5 +670,5 @@ \sa checkBarrier() */ - bool barrier(const Node& node) + bool barrier(const Node& node) const { return (*_level)[node] >= _el; @@ -693,5 +693,5 @@ /// \sa checkBarrier() template - void barrierMap(BarrierMap &bar) + void barrierMap(BarrierMap &bar) const { for(NodeIt n(_g);n!=INVALID;++n) @@ -713,5 +713,5 @@ ///Check if the found flow is a feasible circulation, /// - bool checkFlow() { + bool checkFlow() const { for(ArcIt e(_g);e!=INVALID;++e) if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false; @@ -731,5 +731,5 @@ ///\sa barrier() ///\sa barrierMap() - bool checkBarrier() + bool checkBarrier() const { Value delta=0; Index: lemon/color.cc =================================================================== --- lemon/color.cc (revision 209) +++ lemon/color.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/color.h =================================================================== --- lemon/color.h (revision 313) +++ lemon/color.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/concept_check.h =================================================================== --- lemon/concept_check.h (revision 285) +++ lemon/concept_check.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/concepts/digraph.h =================================================================== --- lemon/concepts/digraph.h (revision 263) +++ lemon/concepts/digraph.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/concepts/graph.h =================================================================== --- lemon/concepts/graph.h (revision 263) +++ lemon/concepts/graph.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/concepts/graph_components.h =================================================================== --- lemon/concepts/graph_components.h (revision 313) +++ lemon/concepts/graph_components.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/concepts/heap.h =================================================================== --- lemon/concepts/heap.h (revision 290) +++ lemon/concepts/heap.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/concepts/maps.h =================================================================== --- lemon/concepts/maps.h (revision 314) +++ lemon/concepts/maps.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/concepts/path.h =================================================================== --- lemon/concepts/path.h (revision 281) +++ lemon/concepts/path.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/connectivity.h =================================================================== --- lemon/connectivity.h (revision 417) +++ lemon/connectivity.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -17,6 +17,6 @@ */ -#ifndef LEMON_TOPOLOGY_H -#define LEMON_TOPOLOGY_H +#ifndef LEMON_CONNECTIVITY_H +#define LEMON_CONNECTIVITY_H #include @@ -155,5 +155,5 @@ } - namespace _topology_bits { + namespace _connectivity_bits { template @@ -189,17 +189,17 @@ template - struct StronglyConnectedCutEdgesVisitor : public DfsVisitor { + struct StronglyConnectedCutArcsVisitor : public DfsVisitor { public: typedef typename Digraph::Node Node; typedef typename Digraph::Arc Arc; - StronglyConnectedCutEdgesVisitor(const Digraph& digraph, - ArcMap& cutMap, - int& cutNum) + StronglyConnectedCutArcsVisitor(const Digraph& digraph, + ArcMap& cutMap, + int& cutNum) : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum), - _compMap(digraph), _num(0) { - } - - void stop(const Node&) { + _compMap(digraph, -1), _num(-1) { + } + + void start(const Node&) { ++_num; } @@ -249,5 +249,5 @@ if (source == INVALID) return true; - using namespace _topology_bits; + using namespace _connectivity_bits; typedef DfsVisitor Visitor; @@ -266,4 +266,5 @@ typedef ReverseDigraph RDigraph; + typedef typename RDigraph::NodeIt RNodeIt; RDigraph rdigraph(digraph); @@ -276,5 +277,5 @@ rdfs.start(); - for (NodeIt it(rdigraph); it != INVALID; ++it) { + for (RNodeIt it(rdigraph); it != INVALID; ++it) { if (!rdfs.reached(it)) { return false; @@ -295,5 +296,5 @@ /// direction. /// - /// \param graph The graph. + /// \param digraph The graph. /// \return The number of components /// \note By definition, the empty graph has zero @@ -303,5 +304,5 @@ checkConcept(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef typename Digraph::Node Node; @@ -375,5 +376,5 @@ checkConcept, NodeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef std::vector Container; @@ -439,5 +440,5 @@ checkConcept, ArcMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef std::vector Container; @@ -464,5 +465,5 @@ int cutNum = 0; - typedef StronglyConnectedCutEdgesVisitor RVisitor; + typedef StronglyConnectedCutArcsVisitor RVisitor; RVisitor rvisitor(rgraph, cutMap, cutNum); @@ -479,5 +480,5 @@ } - namespace _topology_bits { + namespace _connectivity_bits { template @@ -731,5 +732,5 @@ typedef typename Graph::NodeIt NodeIt; - using namespace _topology_bits; + using namespace _connectivity_bits; typedef CountBiNodeConnectedComponentsVisitor Visitor; @@ -774,5 +775,5 @@ checkConcept, EdgeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef BiNodeConnectedComponentsVisitor Visitor; @@ -814,5 +815,5 @@ checkConcept, NodeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef BiNodeConnectedCutNodesVisitor Visitor; @@ -833,5 +834,5 @@ } - namespace _topology_bits { + namespace _connectivity_bits { template @@ -1054,5 +1055,5 @@ typedef typename Graph::NodeIt NodeIt; - using namespace _topology_bits; + using namespace _connectivity_bits; typedef CountBiEdgeConnectedComponentsVisitor Visitor; @@ -1096,5 +1097,5 @@ checkConcept, NodeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef BiEdgeConnectedComponentsVisitor Visitor; @@ -1137,5 +1138,5 @@ checkConcept, EdgeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef BiEdgeConnectedCutEdgesVisitor Visitor; @@ -1157,5 +1158,5 @@ - namespace _topology_bits { + namespace _connectivity_bits { template @@ -1194,5 +1195,5 @@ template void topologicalSort(const Digraph& graph, NodeMap& order) { - using namespace _topology_bits; + using namespace _connectivity_bits; checkConcept(); @@ -1225,5 +1226,5 @@ /// that the given graph is DAG. /// - /// \param graph The graph. It must be directed and acyclic. + /// \param digraph The graph. It must be directed and acyclic. /// \retval order A readable - writable node map. The values will be set /// from 0 to the number of the nodes in the graph minus one. Each values @@ -1235,6 +1236,6 @@ /// \see dag template - bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) { - using namespace _topology_bits; + bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { + using namespace _connectivity_bits; checkConcept(); @@ -1246,19 +1247,21 @@ typedef typename Digraph::Arc Arc; - order = constMap(); + for (NodeIt it(digraph); it != INVALID; ++it) { + order.set(it, -1); + } TopologicalSortVisitor - visitor(order, countNodes(graph)); + visitor(order, countNodes(digraph)); DfsVisit > - dfs(graph, visitor); + dfs(digraph, visitor); dfs.init(); - for (NodeIt it(graph); it != INVALID; ++it) { + for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); while (!dfs.emptyQueue()) { - Arc edge = dfs.nextArc(); - Node target = graph.target(edge); + Arc arc = dfs.nextArc(); + Node target = digraph.target(arc); if (dfs.reached(target) && order[target] == -1) { return false; @@ -1280,5 +1283,5 @@ /// \see acyclic template - bool dag(const Digraph& graph) { + bool dag(const Digraph& digraph) { checkConcept(); @@ -1291,16 +1294,16 @@ typename Dfs::template SetProcessedMap:: - Create dfs(graph); - - ProcessedMap processed(graph); + Create dfs(digraph); + + ProcessedMap processed(digraph); dfs.processedMap(processed); dfs.init(); - for (NodeIt it(graph); it != INVALID; ++it) { + for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); while (!dfs.emptyQueue()) { Arc edge = dfs.nextArc(); - Node target = graph.target(edge); + Node target = digraph.target(edge); if (dfs.reached(target) && !processed[target]) { return false; @@ -1381,5 +1384,5 @@ } - namespace _topology_bits { + namespace _connectivity_bits { template @@ -1450,5 +1453,5 @@ template inline bool bipartite(const Graph &graph){ - using namespace _topology_bits; + using namespace _connectivity_bits; checkConcept(); @@ -1490,5 +1493,5 @@ template inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ - using namespace _topology_bits; + using namespace _connectivity_bits; checkConcept(); @@ -1521,7 +1524,7 @@ /// Returns true when there are not loop edges in the graph. template - bool loopFree(const Digraph& graph) { - for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) { - if (graph.source(it) == graph.target(it)) return false; + bool loopFree(const Digraph& digraph) { + for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) { + if (digraph.source(it) == digraph.target(it)) return false; } return true; @@ -1532,13 +1535,13 @@ /// Returns true when there are not parallel edges in the graph. template - bool parallelFree(const Digraph& graph) { - typename Digraph::template NodeMap reached(graph, false); - for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) { - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { - if (reached[graph.target(e)]) return false; - reached.set(graph.target(e), true); - } - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { - reached.set(graph.target(e), false); + bool parallelFree(const Digraph& digraph) { + typename Digraph::template NodeMap reached(digraph, false); + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { + if (reached[digraph.target(a)]) return false; + reached.set(digraph.target(a), true); + } + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { + reached.set(digraph.target(a), false); } } @@ -1552,14 +1555,14 @@ /// the graph. template - bool simpleDigraph(const Digraph& graph) { - typename Digraph::template NodeMap reached(graph, false); - for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) { + bool simpleDigraph(const Digraph& digraph) { + typename Digraph::template NodeMap reached(digraph, false); + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { reached.set(n, true); - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { - if (reached[graph.target(e)]) return false; - reached.set(graph.target(e), true); - } - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { - reached.set(graph.target(e), false); + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { + if (reached[digraph.target(a)]) return false; + reached.set(digraph.target(a), true); + } + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { + reached.set(digraph.target(a), false); } reached.set(n, false); @@ -1570,3 +1573,3 @@ } //namespace lemon -#endif //LEMON_TOPOLOGY_H +#endif //LEMON_CONNECTIVITY_H Index: lemon/core.h =================================================================== --- lemon/core.h (revision 319) +++ lemon/core.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -1171,6 +1171,6 @@ /// Construct a new ConEdgeIt iterating on the edges that /// connects nodes \c u and \c v. - ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { - Parent::operator=(findEdge(_graph, u, v)); + ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) { + Parent::operator=(findEdge(_graph, _u, _v)); } @@ -1184,10 +1184,10 @@ /// It increments the iterator and gives back the next edge. ConEdgeIt& operator++() { - Parent::operator=(findEdge(_graph, _graph.u(*this), - _graph.v(*this), *this)); + Parent::operator=(findEdge(_graph, _u, _v, *this)); return *this; } private: const Graph& _graph; + Node _u, _v; }; Index: lemon/counter.h =================================================================== --- lemon/counter.h (revision 209) +++ lemon/counter.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/dfs.h =================================================================== --- lemon/dfs.h (revision 405) +++ lemon/dfs.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -1411,4 +1411,5 @@ } else { _visitor->leave(s); + _visitor->stop(s); } } @@ -1626,5 +1627,5 @@ /// \pre Either \ref run(Node) "run()" or \ref init() /// must be called before using this function. - bool reached(Node v) { return (*_reached)[v]; } + bool reached(Node v) const { return (*_reached)[v]; } ///@} Index: lemon/dijkstra.h =================================================================== --- lemon/dijkstra.h (revision 408) +++ lemon/dijkstra.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/dim2.h =================================================================== --- lemon/dim2.h (revision 314) +++ lemon/dim2.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/dimacs.h =================================================================== --- lemon/dimacs.h (revision 388) +++ lemon/dimacs.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -335,5 +335,5 @@ typedef typename Digraph::ArcIt ArcIt; - if(!comment.empty()) + if(!comment.empty()) os << "c " << comment << std::endl; os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl; Index: lemon/elevator.h =================================================================== --- lemon/elevator.h (revision 383) +++ lemon/elevator.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/error.h =================================================================== --- lemon/error.h (revision 291) +++ lemon/error.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/full_graph.h =================================================================== --- lemon/full_graph.h (revision 360) +++ lemon/full_graph.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/graph_to_eps.h =================================================================== --- lemon/graph_to_eps.h (revision 313) +++ lemon/graph_to_eps.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/grid_graph.h =================================================================== --- lemon/grid_graph.h (revision 360) +++ lemon/grid_graph.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/hao_orlin.h =================================================================== --- lemon/hao_orlin.h (revision 412) +++ lemon/hao_orlin.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -239,5 +239,5 @@ if (reached[t]) continue; _sets.push_front(std::list()); - + queue[qlast++] = t; reached.set(t, true); @@ -539,5 +539,5 @@ if (reached[t]) continue; _sets.push_front(std::list()); - + queue[qlast++] = t; reached.set(t, true); Index: lemon/hypercube_graph.h =================================================================== --- lemon/hypercube_graph.h (revision 372) +++ lemon/hypercube_graph.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/kruskal.h =================================================================== --- lemon/kruskal.h (revision 220) +++ lemon/kruskal.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/lgf_reader.h =================================================================== --- lemon/lgf_reader.h (revision 319) +++ lemon/lgf_reader.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -871,5 +871,7 @@ readLine(); } - line.putback(c); + if (readSuccess()) { + line.putback(c); + } } @@ -1700,5 +1702,7 @@ readLine(); } - line.putback(c); + if (readSuccess()) { + line.putback(c); + } } @@ -2227,5 +2231,7 @@ readLine(); } - line.putback(c); + if (readSuccess()) { + line.putback(c); + } } @@ -2568,5 +2574,7 @@ readLine(); } - line.putback(c); + if (readSuccess()) { + line.putback(c); + } } Index: lemon/lgf_writer.h =================================================================== --- lemon/lgf_writer.h (revision 319) +++ lemon/lgf_writer.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/list_graph.h =================================================================== --- lemon/list_graph.h (revision 329) +++ lemon/list_graph.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/maps.h =================================================================== --- lemon/maps.h (revision 314) +++ lemon/maps.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/math.h =================================================================== --- lemon/math.h (revision 209) +++ lemon/math.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/max_matching.h =================================================================== --- lemon/max_matching.h (revision 330) +++ lemon/max_matching.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -417,5 +417,5 @@ /// \ref init(), \ref greedyInit() or \ref matchingInit() /// functions first, then you can start the algorithm with the \ref - /// startParse() or startDense() functions. + /// startSparse() or startDense() functions. ///@{ Index: lemon/nauty_reader.h =================================================================== --- lemon/nauty_reader.h (revision 359) +++ lemon/nauty_reader.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/path.h =================================================================== --- lemon/path.h (revision 313) +++ lemon/path.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/preflow.h =================================================================== --- lemon/preflow.h (revision 393) +++ lemon/preflow.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -367,5 +367,5 @@ /// \pre Either \ref run() or \ref init() must be called before /// using this function. - const Elevator& elevator() { + const Elevator& elevator() const { return *_level; } @@ -919,5 +919,5 @@ /// \pre Either \ref run() or \ref init() must be called before /// using this function. - const FlowMap& flowMap() { + const FlowMap& flowMap() const { return *_flow; } Index: lemon/radix_sort.h =================================================================== --- lemon/radix_sort.h (revision 444) +++ lemon/radix_sort.h (revision 444) @@ -0,0 +1,487 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * 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 RADIX_SORT_H +#define RADIX_SORT_H + +/// \ingroup auxalg +/// \file +/// \brief Radix sort +/// +/// Linear time sorting algorithms + +#include +#include +#include +#include + +namespace lemon { + + namespace _radix_sort_bits { + + template + struct Identity { + const Value& operator()(const Value& val) { + return val; + } + }; + + + template + Iterator radixSortPartition(Iterator first, Iterator last, + Functor functor, Value mask) { + while (first != last && !(functor(*first) & mask)) { + ++first; + } + if (first == last) { + return first; + } + --last; + while (first != last && (functor(*last) & mask)) { + --last; + } + if (first == last) { + return first; + } + std::iter_swap(first, last); + ++first; + if (!(first < last)) { + return first; + } + while (true) { + while (!(functor(*first) & mask)) { + ++first; + } + --last; + while (functor(*last) & mask) { + --last; + } + if (!(first < last)) { + return first; + } + std::iter_swap(first, last); + ++first; + } + } + + template + Iterator radixSortSignPartition(Iterator first, Iterator last, + Functor functor) { + while (first != last && functor(*first) < 0) { + ++first; + } + if (first == last) { + return first; + } + --last; + while (first != last && functor(*last) >= 0) { + --last; + } + if (first == last) { + return first; + } + std::iter_swap(first, last); + ++first; + if (!(first < last)) { + return first; + } + while (true) { + while (functor(*first) < 0) { + ++first; + } + --last; + while (functor(*last) >= 0) { + --last; + } + if (!(first < last)) { + return first; + } + std::iter_swap(first, last); + ++first; + } + } + + template + void radixIntroSort(Iterator first, Iterator last, + Functor functor, Value mask) { + while (mask != 0 && last - first > 1) { + Iterator cut = radixSortPartition(first, last, functor, mask); + mask >>= 1; + radixIntroSort(first, cut, functor, mask); + first = cut; + } + } + + template + void radixSignedSort(Iterator first, Iterator last, Functor functor) { + + Iterator cut = radixSortSignPartition(first, last, functor); + + Value mask; + int max_digit; + Iterator it; + + mask = ~0; max_digit = 0; + for (it = first; it != cut; ++it) { + while ((mask & functor(*it)) != mask) { + ++max_digit; + mask <<= 1; + } + } + radixIntroSort(first, cut, functor, 1 << max_digit); + + mask = 0; max_digit = 0; + for (it = cut; it != last; ++it) { + while ((mask | functor(*it)) != mask) { + ++max_digit; + mask <<= 1; mask |= 1; + } + } + radixIntroSort(cut, last, functor, 1 << max_digit); + } + + template + void radixUnsignedSort(Iterator first, Iterator last, Functor functor) { + + Value mask = 0; + int max_digit = 0; + + Iterator it; + for (it = first; it != last; ++it) { + while ((mask | functor(*it)) != mask) { + ++max_digit; + mask <<= 1; mask |= 1; + } + } + radixIntroSort(first, last, functor, 1 << max_digit); + } + + + template ::is_signed > + struct RadixSortSelector { + template + static void sort(Iterator first, Iterator last, Functor functor) { + radixSignedSort(first, last, functor); + } + }; + + template + struct RadixSortSelector { + template + static void sort(Iterator first, Iterator last, Functor functor) { + radixUnsignedSort(first, last, functor); + } + }; + + } + + /// \ingroup auxalg + /// + /// \brief Sorts the STL compatible range into ascending order. + /// + /// The \c radixSort sorts an STL compatible range into ascending + /// order. The radix sort algorithm can sort items which are mapped + /// to integers with an adaptable unary function \c functor and the + /// order will be ascending according to these mapped values. + /// + /// It is also possible to use a normal function instead + /// of the functor object. If the functor is not given it will use + /// the identity function instead. + /// + /// This is a special quick sort algorithm where the pivot + /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k. + /// Therefore, the time complexity of the + /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$, + /// additional space, where \c c is the maximal value and \c n is the + /// number of the items in the container. + /// + /// \param first The begin of the given range. + /// \param last The end of the given range. + /// \param functor An adaptible unary function or a normal function + /// which maps the items to any integer type which can be either + /// signed or unsigned. + /// + /// \sa stableRadixSort() + template + void radixSort(Iterator first, Iterator last, Functor functor) { + using namespace _radix_sort_bits; + typedef typename Functor::result_type Value; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) { + using namespace _radix_sort_bits; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) { + using namespace _radix_sort_bits; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) { + using namespace _radix_sort_bits; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) { + using namespace _radix_sort_bits; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last) { + using namespace _radix_sort_bits; + typedef typename std::iterator_traits::value_type Value; + RadixSortSelector::sort(first, last, Identity()); + } + + namespace _radix_sort_bits { + + template + unsigned char valueByte(Value value, int byte) { + return value >> (std::numeric_limits::digits * byte); + } + + template + void stableRadixIntroSort(Key *first, Key *last, Key *target, + int byte, Functor functor) { + const int size = + unsigned(std::numeric_limits::max()) + 1; + std::vector counter(size); + for (int i = 0; i < size; ++i) { + counter[i] = 0; + } + Key *it = first; + while (first != last) { + ++counter[valueByte(functor(*first), byte)]; + ++first; + } + int prev, num = 0; + for (int i = 0; i < size; ++i) { + prev = num; + num += counter[i]; + counter[i] = prev; + } + while (it != last) { + target[counter[valueByte(functor(*it), byte)]++] = *it; + ++it; + } + } + + template + void signedStableRadixIntroSort(Key *first, Key *last, Key *target, + int byte, Functor functor) { + const int size = + unsigned(std::numeric_limits::max()) + 1; + std::vector counter(size); + for (int i = 0; i < size; ++i) { + counter[i] = 0; + } + Key *it = first; + while (first != last) { + counter[valueByte(functor(*first), byte)]++; + ++first; + } + int prev, num = 0; + for (int i = size / 2; i < size; ++i) { + prev = num; + num += counter[i]; + counter[i] = prev; + } + for (int i = 0; i < size / 2; ++i) { + prev = num; + num += counter[i]; + counter[i] = prev; + } + while (it != last) { + target[counter[valueByte(functor(*it), byte)]++] = *it; + ++it; + } + } + + + template + void stableRadixSignedSort(Iterator first, Iterator last, Functor functor) { + if (first == last) return; + typedef typename std::iterator_traits::value_type Key; + typedef std::allocator Allocator; + Allocator allocator; + + int length = std::distance(first, last); + Key* buffer = allocator.allocate(2 * length); + try { + bool dir = true; + std::copy(first, last, buffer); + for (int i = 0; i < int(sizeof(Value)) - 1; ++i) { + if (dir) { + stableRadixIntroSort(buffer, buffer + length, buffer + length, + i, functor); + } else { + stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer, + i, functor); + } + dir = !dir; + } + if (dir) { + signedStableRadixIntroSort(buffer, buffer + length, buffer + length, + sizeof(Value) - 1, functor); + std::copy(buffer + length, buffer + 2 * length, first); + } else { + signedStableRadixIntroSort(buffer + length, buffer + 2 * length, + buffer, sizeof(Value) - 1, functor); + std::copy(buffer, buffer + length, first); + } + } catch (...) { + allocator.deallocate(buffer, 2 * length); + throw; + } + allocator.deallocate(buffer, 2 * length); + } + + template + void stableRadixUnsignedSort(Iterator first, Iterator last, + Functor functor) { + if (first == last) return; + typedef typename std::iterator_traits::value_type Key; + typedef std::allocator Allocator; + Allocator allocator; + + int length = std::distance(first, last); + Key *buffer = allocator.allocate(2 * length); + try { + bool dir = true; + std::copy(first, last, buffer); + for (int i = 0; i < int(sizeof(Value)); ++i) { + if (dir) { + stableRadixIntroSort(buffer, buffer + length, + buffer + length, i, functor); + } else { + stableRadixIntroSort(buffer + length, buffer + 2 * length, + buffer, i, functor); + } + dir = !dir; + } + if (dir) { + std::copy(buffer, buffer + length, first); + } else { + std::copy(buffer + length, buffer + 2 * length, first); + } + } catch (...) { + allocator.deallocate(buffer, 2 * length); + throw; + } + allocator.deallocate(buffer, 2 * length); + } + + + + template ::is_signed > + struct StableRadixSortSelector { + template + static void sort(Iterator first, Iterator last, Functor functor) { + stableRadixSignedSort(first, last, functor); + } + }; + + template + struct StableRadixSortSelector { + template + static void sort(Iterator first, Iterator last, Functor functor) { + stableRadixUnsignedSort(first, last, functor); + } + }; + + } + + /// \ingroup auxalg + /// + /// \brief Sorts the STL compatible range into ascending order in a stable + /// way. + /// + /// This function sorts an STL compatible range into ascending + /// order according to an integer mapping in the same as radixSort() does. + /// + /// This sorting algorithm is stable, i.e. the order of two equal + /// elements remains the same after the sorting. + /// + /// This sort algorithm use a radix forward sort on the + /// bytes of the integer number. The algorithm sorts the items + /// byte-by-byte. First, it counts how many times a byte value occurs + /// in the container, then it copies the corresponding items to + /// another container in asceding order in \c O(n) time. + /// + /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and + /// it uses \f$ O(n) \f$, additional space, where \c c is the + /// maximal value and \c n is the number of the items in the + /// container. + /// + + /// \param first The begin of the given range. + /// \param last The end of the given range. + /// \param functor An adaptible unary function or a normal function + /// which maps the items to any integer type which can be either + /// signed or unsigned. + /// \sa radixSort() + template + void stableRadixSort(Iterator first, Iterator last, Functor functor) { + using namespace _radix_sort_bits; + typedef typename Functor::result_type Value; + StableRadixSortSelector::sort(first, last, functor); + } + + template + void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key)) { + using namespace _radix_sort_bits; + StableRadixSortSelector::sort(first, last, functor); + } + + template + void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key)) { + using namespace _radix_sort_bits; + StableRadixSortSelector::sort(first, last, functor); + } + + template + void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key&)) { + using namespace _radix_sort_bits; + StableRadixSortSelector::sort(first, last, functor); + } + + template + void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) { + using namespace _radix_sort_bits; + StableRadixSortSelector::sort(first, last, functor); + } + + template + void stableRadixSort(Iterator first, Iterator last) { + using namespace _radix_sort_bits; + typedef typename std::iterator_traits::value_type Value; + StableRadixSortSelector::sort(first, last, Identity()); + } + +} + +#endif Index: lemon/random.cc =================================================================== --- lemon/random.cc (revision 209) +++ lemon/random.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/random.h =================================================================== --- lemon/random.h (revision 378) +++ lemon/random.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/smart_graph.h =================================================================== --- lemon/smart_graph.h (revision 375) +++ lemon/smart_graph.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/suurballe.h =================================================================== --- lemon/suurballe.h (revision 346) +++ lemon/suurballe.h (revision 440) @@ -1,7 +1,7 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -52,5 +52,5 @@ /// /// \note For finding node-disjoint paths this algorithm can be used - /// with \ref SplitDigraphAdaptor. + /// with \ref SplitNodes. #ifdef DOXYGEN template @@ -77,5 +77,5 @@ private: - + /// \brief Special implementation of the Dijkstra algorithm /// for finding shortest paths in the residual network. @@ -107,5 +107,5 @@ // The processed (i.e. permanently labeled) nodes std::vector _proc_nodes; - + Node _s; Node _t; @@ -201,5 +201,5 @@ // The length map const LengthMap &_length; - + // Arc map of the current flow FlowMap *_flow; @@ -269,5 +269,5 @@ /// This function sets the potential map. /// - /// The potentials provide the dual solution of the underlying + /// The potentials provide the dual solution of the underlying /// minimum cost flow problem. /// @@ -331,5 +331,5 @@ for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; - _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, + _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred, _source, _target ); @@ -371,5 +371,5 @@ return _path_num; } - + /// \brief Compute the paths from the flow. /// Index: lemon/time_measure.h =================================================================== --- lemon/time_measure.h (revision 314) +++ lemon/time_measure.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/tolerance.h =================================================================== --- lemon/tolerance.h (revision 280) +++ lemon/tolerance.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: lemon/unionfind.h =================================================================== --- lemon/unionfind.h (revision 236) +++ lemon/unionfind.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -1178,7 +1178,8 @@ if (nodes[nodes[jd].next].size < cmax) { pushLeft(nodes[jd].next, nodes[jd].left); - if (less(nodes[jd].left, nodes[jd].next)) { - nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio; - nodes[nodes[jd].next].item = nodes[nodes[jd].left].item; + if (less(jd, nodes[jd].next) || + nodes[jd].item == nodes[pd].item) { + nodes[nodes[jd].next].prio = nodes[jd].prio; + nodes[nodes[jd].next].item = nodes[jd].item; } popLeft(pd); @@ -1189,7 +1190,8 @@ popLeft(nodes[jd].next); pushRight(jd, ld); - if (less(ld, nodes[jd].left)) { + if (less(ld, nodes[jd].left) || + nodes[ld].item == nodes[pd].item) { nodes[jd].item = nodes[ld].item; - nodes[jd].prio = nodes[jd].prio; + nodes[jd].prio = nodes[ld].prio; } if (nodes[nodes[jd].next].item == nodes[ld].item) { @@ -1220,7 +1222,8 @@ if (nodes[nodes[jd].prev].size < cmax) { pushRight(nodes[jd].prev, nodes[jd].right); - if (less(nodes[jd].right, nodes[jd].prev)) { - nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio; - nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item; + if (less(jd, nodes[jd].prev) || + nodes[jd].item == nodes[pd].item) { + nodes[nodes[jd].prev].prio = nodes[jd].prio; + nodes[nodes[jd].prev].item = nodes[jd].item; } popRight(pd); @@ -1231,7 +1234,8 @@ popRight(nodes[jd].prev); pushLeft(jd, ld); - if (less(ld, nodes[jd].right)) { + if (less(ld, nodes[jd].right) || + nodes[ld].item == nodes[pd].item) { nodes[jd].item = nodes[ld].item; - nodes[jd].prio = nodes[jd].prio; + nodes[jd].prio = nodes[ld].prio; } if (nodes[nodes[jd].prev].item == nodes[ld].item) { @@ -1251,9 +1255,4 @@ return comp(nodes[id].prio, nodes[jd].prio); } - - bool equal(int id, int jd) const { - return !less(id, jd) && !less(jd, id); - } - public: @@ -1401,5 +1400,12 @@ push(new_id, right_id); pushRight(new_id, ~(classes[r].parent)); - setPrio(new_id); + + if (less(~classes[r].parent, right_id)) { + nodes[new_id].item = nodes[~classes[r].parent].item; + nodes[new_id].prio = nodes[~classes[r].parent].prio; + } else { + nodes[new_id].item = nodes[right_id].item; + nodes[new_id].prio = nodes[right_id].prio; + } id = nodes[id].parent; @@ -1441,5 +1447,12 @@ push(new_id, left_id); pushLeft(new_id, ~(classes[l].parent)); - setPrio(new_id); + + if (less(~classes[l].parent, left_id)) { + nodes[new_id].item = nodes[~classes[l].parent].item; + nodes[new_id].prio = nodes[~classes[l].parent].prio; + } else { + nodes[new_id].item = nodes[left_id].item; + nodes[new_id].prio = nodes[left_id].prio; + } id = nodes[id].parent; Index: scripts/chg-len.py =================================================================== --- scripts/chg-len.py (revision 376) +++ scripts/chg-len.py (revision 422) @@ -4,4 +4,7 @@ from mercurial import ui, hg +from mercurial import util + +util.rcpath = lambda : [] if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]: Index: test/CMakeLists.txt =================================================================== --- test/CMakeLists.txt (revision 410) +++ test/CMakeLists.txt (revision 445) @@ -5,4 +5,5 @@ SET(TESTS bfs_test + circulation_test counter_test dfs_test @@ -11,4 +12,5 @@ dim_test error_test + graph_adaptor_test graph_copy_test graph_test @@ -19,6 +21,9 @@ maps_test max_matching_test + radix_sort_test + path_test + preflow_test random_test - path_test + suurballe_test time_measure_test unionfind_test) Index: test/Makefile.am =================================================================== --- test/Makefile.am (revision 418) +++ test/Makefile.am (revision 445) @@ -1,19 +1,17 @@ EXTRA_DIST += \ - test/CMakeLists.txt \ - test/min_cost_flow_test.lgf \ - test/preflow_graph.lgf + test/CMakeLists.txt noinst_HEADERS += \ test/graph_test.h \ - test/test_tools.h + test/test_tools.h check_PROGRAMS += \ test/bfs_test \ - test/circulation_test \ - test/counter_test \ + test/circulation_test \ + test/counter_test \ test/dfs_test \ test/digraph_test \ test/dijkstra_test \ - test/dim_test \ + test/dim_test \ test/error_test \ test/graph_adaptor_test \ @@ -21,16 +19,17 @@ test/graph_test \ test/graph_utils_test \ + test/hao_orlin_test \ test/heap_test \ test/kruskal_test \ - test/hao_orlin_test \ - test/maps_test \ + test/maps_test \ test/max_matching_test \ - test/random_test \ - test/path_test \ - test/preflow_test \ - test/suurballe_test \ - test/test_tools_fail \ - test/test_tools_pass \ - test/time_measure_test \ + test/path_test \ + test/preflow_test \ + test/radix_sort_test \ + test/random_test \ + test/suurballe_test \ + test/test_tools_fail \ + test/test_tools_pass \ + test/time_measure_test \ test/unionfind_test @@ -57,4 +56,5 @@ test_path_test_SOURCES = test/path_test.cc test_preflow_test_SOURCES = test/preflow_test.cc +test_radix_sort_test_SOURCES = test/radix_sort_test.cc test_suurballe_test_SOURCES = test/suurballe_test.cc test_random_test_SOURCES = test/random_test.cc Index: test/bfs_test.cc =================================================================== --- test/bfs_test.cc (revision 293) +++ test/bfs_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/circulation_test.cc =================================================================== --- test/circulation_test.cc (revision 403) +++ test/circulation_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/counter_test.cc =================================================================== --- test/counter_test.cc (revision 209) +++ test/counter_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/dfs_test.cc =================================================================== --- test/dfs_test.cc (revision 293) +++ test/dfs_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/digraph_test.cc =================================================================== --- test/digraph_test.cc (revision 375) +++ test/digraph_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/dijkstra_test.cc =================================================================== --- test/dijkstra_test.cc (revision 397) +++ test/dijkstra_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/dim_test.cc =================================================================== --- test/dim_test.cc (revision 253) +++ test/dim_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/error_test.cc =================================================================== --- test/error_test.cc (revision 277) +++ test/error_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/graph_adaptor_test.cc =================================================================== --- test/graph_adaptor_test.cc (revision 416) +++ test/graph_adaptor_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -104,5 +104,5 @@ node_filter[n1] = node_filter[n2] = node_filter[n3] = true; arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; - + checkGraphNodeList(adaptor, 3); checkGraphArcList(adaptor, 3); @@ -197,5 +197,5 @@ node_filter[n1] = node_filter[n2] = node_filter[n3] = true; - + checkGraphNodeList(adaptor, 3); checkGraphArcList(adaptor, 3); @@ -269,5 +269,5 @@ arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; - + checkGraphNodeList(adaptor, 3); checkGraphArcList(adaptor, 3); @@ -578,5 +578,5 @@ node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; - + checkGraphNodeList(adaptor, 4); checkGraphArcList(adaptor, 8); @@ -709,5 +709,5 @@ node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; - + checkGraphNodeList(adaptor, 4); checkGraphArcList(adaptor, 8); @@ -808,5 +808,5 @@ edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; - + checkGraphNodeList(adaptor, 4); checkGraphArcList(adaptor, 8); Index: test/graph_copy_test.cc =================================================================== --- test/graph_copy_test.cc (revision 282) +++ test/graph_copy_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/graph_test.cc =================================================================== --- test/graph_test.cc (revision 375) +++ test/graph_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/graph_test.h =================================================================== --- test/graph_test.h (revision 374) +++ test/graph_test.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/graph_utils_test.cc =================================================================== --- test/graph_utils_test.cc (revision 220) +++ test/graph_utils_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/hao_orlin_test.cc =================================================================== --- test/hao_orlin_test.cc (revision 410) +++ test/hao_orlin_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/heap_test.cc =================================================================== --- test/heap_test.cc (revision 293) +++ test/heap_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/kruskal_test.cc =================================================================== --- test/kruskal_test.cc (revision 209) +++ test/kruskal_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/maps_test.cc =================================================================== --- test/maps_test.cc (revision 210) +++ test/maps_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/max_matching_test.cc =================================================================== --- test/max_matching_test.cc (revision 327) +++ test/max_matching_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: st/min_cost_flow_test.lgf =================================================================== --- test/min_cost_flow_test.lgf (revision 345) +++ (revision ) @@ -1,44 +1,0 @@ -@nodes -label supply1 supply2 supply3 -1 0 20 27 -2 0 -4 0 -3 0 0 0 -4 0 0 0 -5 0 9 0 -6 0 -6 0 -7 0 0 0 -8 0 0 0 -9 0 3 0 -10 0 -2 0 -11 0 0 0 -12 0 -20 -27 - -@arcs - cost capacity lower1 lower2 -1 2 70 11 0 8 -1 3 150 3 0 1 -1 4 80 15 0 2 -2 8 80 12 0 0 -3 5 140 5 0 3 -4 6 60 10 0 1 -4 7 80 2 0 0 -4 8 110 3 0 0 -5 7 60 14 0 0 -5 11 120 12 0 0 -6 3 0 3 0 0 -6 9 140 4 0 0 -6 10 90 8 0 0 -7 1 30 5 0 0 -8 12 60 16 0 4 -9 12 50 6 0 0 -10 12 70 13 0 5 -10 2 100 7 0 0 -10 7 60 10 0 0 -11 10 20 14 0 6 -12 11 30 10 0 0 - -@attributes -source 1 -target 12 - -@end Index: test/path_test.cc =================================================================== --- test/path_test.cc (revision 209) +++ test/path_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: st/preflow_graph.lgf =================================================================== --- test/preflow_graph.lgf (revision 394) +++ (revision ) @@ -1,34 +1,0 @@ -@nodes -label -0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -@arcs - label capacity -0 1 0 20 -0 2 1 0 -1 1 2 3 -1 2 3 8 -1 3 4 8 -2 5 5 5 -3 2 6 5 -3 5 7 5 -3 6 8 5 -4 3 9 3 -5 7 10 3 -5 6 11 10 -5 8 12 10 -6 8 13 8 -8 9 14 20 -8 1 15 5 -9 5 16 5 -@attributes -source 1 -target 8 Index: test/preflow_test.cc =================================================================== --- test/preflow_test.cc (revision 394) +++ test/preflow_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -17,6 +17,5 @@ */ -#include -#include +#include #include "test_tools.h" @@ -29,4 +28,40 @@ using namespace lemon; + +char test_lgf[] = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "8\n" + "9\n" + "@arcs\n" + " label capacity\n" + "0 1 0 20\n" + "0 2 1 0\n" + "1 1 2 3\n" + "1 2 3 8\n" + "1 3 4 8\n" + "2 5 5 5\n" + "3 2 6 5\n" + "3 5 7 5\n" + "3 6 8 5\n" + "4 3 9 3\n" + "5 7 10 3\n" + "5 6 11 10\n" + "5 8 12 10\n" + "6 8 13 8\n" + "8 9 14 20\n" + "8 1 15 5\n" + "9 5 16 5\n" + "@attributes\n" + "source 1\n" + "target 8\n"; void checkPreflowCompile() @@ -124,18 +159,9 @@ typedef Preflow PType; - std::string f_name; - if( getenv("srcdir") ) - f_name = std::string(getenv("srcdir")); - else f_name = "."; - f_name += "/test/preflow_graph.lgf"; - - std::ifstream file(f_name.c_str()); - - check(file, "Input file '" << f_name << "' not found."); - Digraph g; Node s, t; CapMap cap(g); - DigraphReader(g,file). + std::istringstream input(test_lgf); + DigraphReader(g,input). arcMap("capacity", cap). node("source",s). Index: test/radix_sort_test.cc =================================================================== --- test/radix_sort_test.cc (revision 444) +++ test/radix_sort_test.cc (revision 444) @@ -0,0 +1,147 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * 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 +#include +#include +#include +#include + +#include "test_tools.h" + +#include +#include + +using namespace lemon; + +static const int n = 10000; + +struct Negate { + typedef int argument_type; + typedef int result_type; + int operator()(int a) { return - a; } +}; + +int negate(int a) { return - a; } + + +void generateIntSequence(int n, std::vector& data) { + int prime = 9973; + int root = 136, value = 1; + for (int i = 0; i < n; ++i) { + data.push_back(value - prime / 2); + value = (value * root) % prime; + } +} + +void generateCharSequence(int n, std::vector& data) { + int prime = 251; + int root = 3, value = root; + for (int i = 0; i < n; ++i) { + data.push_back(static_cast(value)); + value = (value * root) % prime; + } +} + +void checkRadixSort() { + { + std::vector data1; + generateIntSequence(n, data1); + + std::vector data2(data1); + std::sort(data1.begin(), data1.end()); + + radixSort(data2.begin(), data2.end()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[i], "Test failed"); + } + + radixSort(data2.begin(), data2.end(), Negate()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[n - 1 - i], "Test failed"); + } + + radixSort(data2.begin(), data2.end(), negate); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[n - 1 - i], "Test failed"); + } + + } + + { + std::vector data1(n); + generateCharSequence(n, data1); + + std::vector data2(data1); + std::sort(data1.begin(), data1.end()); + + radixSort(data2.begin(), data2.end()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[i], "Test failed"); + } + + } +} + + +void checkStableRadixSort() { + { + std::vector data1; + generateIntSequence(n, data1); + + std::vector data2(data1); + std::sort(data1.begin(), data1.end()); + + stableRadixSort(data2.begin(), data2.end()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[i], "Test failed"); + } + + stableRadixSort(data2.begin(), data2.end(), Negate()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[n - 1 - i], "Test failed"); + } + + stableRadixSort(data2.begin(), data2.end(), negate); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[n - 1 - i], "Test failed"); + } + } + + { + std::vector data1(n); + generateCharSequence(n, data1); + + std::vector data2(data1); + std::sort(data1.begin(), data1.end()); + + radixSort(data2.begin(), data2.end()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[i], "Test failed"); + } + + } +} + +int main() { + + checkRadixSort(); + checkStableRadixSort(); + + return 0; +} Index: test/random_test.cc =================================================================== --- test/random_test.cc (revision 209) +++ test/random_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/suurballe_test.cc =================================================================== --- test/suurballe_test.cc (revision 346) +++ test/suurballe_test.cc (revision 440) @@ -1,7 +1,7 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). @@ -18,5 +18,4 @@ #include -#include #include @@ -29,7 +28,50 @@ using namespace lemon; +char test_lgf[] = + "@nodes\n" + "label supply1 supply2 supply3\n" + "1 0 20 27\n" + "2 0 -4 0\n" + "3 0 0 0\n" + "4 0 0 0\n" + "5 0 9 0\n" + "6 0 -6 0\n" + "7 0 0 0\n" + "8 0 0 0\n" + "9 0 3 0\n" + "10 0 -2 0\n" + "11 0 0 0\n" + "12 0 -20 -27\n" + "@arcs\n" + " cost capacity lower1 lower2\n" + " 1 2 70 11 0 8\n" + " 1 3 150 3 0 1\n" + " 1 4 80 15 0 2\n" + " 2 8 80 12 0 0\n" + " 3 5 140 5 0 3\n" + " 4 6 60 10 0 1\n" + " 4 7 80 2 0 0\n" + " 4 8 110 3 0 0\n" + " 5 7 60 14 0 0\n" + " 5 11 120 12 0 0\n" + " 6 3 0 3 0 0\n" + " 6 9 140 4 0 0\n" + " 6 10 90 8 0 0\n" + " 7 1 30 5 0 0\n" + " 8 12 60 16 0 4\n" + " 9 12 50 6 0 0\n" + "10 12 70 13 0 5\n" + "10 2 100 7 0 0\n" + "10 7 60 10 0 0\n" + "11 10 20 14 0 6\n" + "12 11 30 10 0 0\n" + "@attributes\n" + "source 1\n" + "target 12\n" + "@end\n"; + // Check the feasibility of the flow template -bool checkFlow( const Digraph& gr, const FlowMap& flow, +bool checkFlow( const Digraph& gr, const FlowMap& flow, typename Digraph::Node s, typename Digraph::Node t, int value ) @@ -54,5 +96,5 @@ // Check the optimalitiy of the flow -template < typename Digraph, typename CostMap, +template < typename Digraph, typename CostMap, typename FlowMap, typename PotentialMap > bool checkOptimality( const Digraph& gr, const CostMap& cost, @@ -97,12 +139,5 @@ Node source, target; - std::string fname; - if(getenv("srcdir")) - fname = std::string(getenv("srcdir")); - else fname = "."; - fname += "/test/min_cost_flow_test.lgf"; - - std::ifstream input(fname.c_str()); - check(input, "Input file '" << fname << "' not found"); + std::istringstream input(test_lgf); DigraphReader(digraph, input). arcMap("cost", length). @@ -110,6 +145,5 @@ node("target", target). run(); - input.close(); - + // Find 2 paths { @@ -119,5 +153,5 @@ "The flow is not feasible"); check(suurballe.totalLength() == 510, "The flow is not optimal"); - check(checkOptimality(digraph, length, suurballe.flowMap(), + check(checkOptimality(digraph, length, suurballe.flowMap(), suurballe.potentialMap()), "Wrong potentials"); @@ -134,5 +168,5 @@ "The flow is not feasible"); check(suurballe.totalLength() == 1040, "The flow is not optimal"); - check(checkOptimality(digraph, length, suurballe.flowMap(), + check(checkOptimality(digraph, length, suurballe.flowMap(), suurballe.potentialMap()), "Wrong potentials"); @@ -149,5 +183,5 @@ "The flow is not feasible"); check(suurballe.totalLength() == 1040, "The flow is not optimal"); - check(checkOptimality(digraph, length, suurballe.flowMap(), + check(checkOptimality(digraph, length, suurballe.flowMap(), suurballe.potentialMap()), "Wrong potentials"); Index: test/test_tools.h =================================================================== --- test/test_tools.h (revision 209) +++ test/test_tools.h (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/test_tools_fail.cc =================================================================== --- test/test_tools_fail.cc (revision 209) +++ test/test_tools_fail.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/test_tools_pass.cc =================================================================== --- test/test_tools_pass.cc (revision 209) +++ test/test_tools_pass.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/time_measure_test.cc =================================================================== --- test/time_measure_test.cc (revision 209) +++ test/time_measure_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: test/unionfind_test.cc =================================================================== --- test/unionfind_test.cc (revision 209) +++ test/unionfind_test.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). Index: tools/dimacs-to-lgf.cc =================================================================== --- tools/dimacs-to-lgf.cc (revision 387) +++ tools/dimacs-to-lgf.cc (revision 440) @@ -3,5 +3,5 @@ * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES).