COIN-OR::LEMON - Graph Library

Ignore:
Files:
4 deleted
22 edited

Legend:

Unmodified
Added
Removed
  • INSTALL

    r890 r615  
    174174
    175175   Disable COIN-OR support.
    176 
    177 
    178 Makefile Variables
    179 ==================
    180 
    181 Some Makefile variables are reserved by the GNU Coding Standards for
    182 the use of the "user" - the person building the package. For instance,
    183 CXX and CXXFLAGS are such variables, and have the same meaning as
    184 explained in the previous section. These variables can be set on the
    185 command line when invoking `make' like this:
    186 `make [VARIABLE=VALUE]...'
    187 
    188 WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
    189 to hold several compiler flags related to warnings. Its default value
    190 can be overridden when invoking `make'. For example to disable all
    191 warning flags use `make WARNINGCXXFLAGS='.
    192 
    193 In order to turn off a single flag from the default set of warning
    194 flags, you can use the CXXFLAGS variable, since this is passed after
    195 WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
    196 used by default when g++ is detected) you can use
    197 `make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.
  • doc/CMakeLists.txt

    r895 r791  
    2727    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    2828    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    29     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    3029    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    3130    COMMAND ${CMAKE_COMMAND} -E remove_directory html
  • doc/Makefile.am

    r895 r791  
    2929        edge_biconnected_components.eps \
    3030        node_biconnected_components.eps \
    31         planar.eps \
    3231        strongly_connected_components.eps
    3332
  • doc/groups.dox

    r879 r818  
    407407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    408408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    409  - \ref CostScaling Cost Scaling algorithm based on push/augment and
    410    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
    411411   \ref bunnagel98efficient.
    412  - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    413    shortest path method \ref edmondskarp72theoretical.
    414  - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    415    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
     413   capacity scaling \ref edmondskarp72theoretical.
     414 - \ref CancelAndTighten The Cancel and Tighten algorithm
     415   \ref goldberg89cyclecanceling.
     416 - \ref CycleCanceling Cycle-Canceling algorithms
     417   \ref klein67primal, \ref goldberg89cyclecanceling.
    416418
    417419In general NetworkSimplex is the most efficient implementation,
  • lemon/Makefile.am

    r888 r863  
    6363        lemon/binom_heap.h \
    6464        lemon/bucket_heap.h \
    65         lemon/capacity_scaling.h \
    6665        lemon/cbc.h \
    6766        lemon/circulation.h \
     
    7069        lemon/concept_check.h \
    7170        lemon/connectivity.h \
     71        lemon/counter.h \
    7272        lemon/core.h \
    73         lemon/cost_scaling.h \
    74         lemon/counter.h \
    7573        lemon/cplex.h \
    76         lemon/cycle_canceling.h \
    7774        lemon/dfs.h \
    7875        lemon/dijkstra.h \
  • lemon/bellman_ford.h

    r891 r835  
    172172  /// the lengths of the arcs. The default map type is
    173173  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    174   /// \tparam TR The traits class that defines various types used by the
    175   /// algorithm. By default, it is \ref BellmanFordDefaultTraits
    176   /// "BellmanFordDefaultTraits<GR, LEN>".
    177   /// In most cases, this parameter should not be set directly,
    178   /// consider to use the named template parameters instead.
    179174#ifdef DOXYGEN
    180175  template <typename GR, typename LEN, typename TR>
     
    243238        _dist = Traits::createDistMap(*_gr);
    244239      }
    245       if(!_mask) {
    246         _mask = new MaskMap(*_gr);
    247       }
     240      _mask = new MaskMap(*_gr, false);
    248241    }
    249242   
     
    411404          _process.push_back(it);
    412405          _mask->set(it, true);
    413         }
    414       } else {
    415         for (NodeIt it(*_gr); it != INVALID; ++it) {
    416           _mask->set(it, false);
    417406        }
    418407      }
     
    939928  /// This class should only be used through the \ref bellmanFord()
    940929  /// function, which makes it easier to use the algorithm.
    941   ///
    942   /// \tparam TR The traits class that defines various types used by the
    943   /// algorithm.
    944930  template<class TR>
    945931  class BellmanFordWizard : public TR {
  • lemon/bfs.h

    r891 r835  
    122122  ///\tparam GR The type of the digraph the algorithm runs on.
    123123  ///The default type is \ref ListDigraph.
    124   ///\tparam TR The traits class that defines various types used by the
    125   ///algorithm. By default, it is \ref BfsDefaultTraits
    126   ///"BfsDefaultTraits<GR>".
    127   ///In most cases, this parameter should not be set directly,
    128   ///consider to use the named template parameters instead.
    129124#ifdef DOXYGEN
    130125  template <typename GR,
     
    963958  /// This class should only be used through the \ref bfs() function,
    964959  /// which makes it easier to use the algorithm.
    965   ///
    966   /// \tparam TR The traits class that defines various types used by the
    967   /// algorithm.
    968960  template<class TR>
    969961  class BfsWizard : public TR
     
    13041296  /// does not observe the BFS events. If you want to observe the BFS
    13051297  /// events, you should implement your own visitor class.
    1306   /// \tparam TR The traits class that defines various types used by the
    1307   /// algorithm. By default, it is \ref BfsVisitDefaultTraits
    1308   /// "BfsVisitDefaultTraits<GR>".
    1309   /// In most cases, this parameter should not be set directly,
    1310   /// consider to use the named template parameters instead.
     1298  /// \tparam TR Traits class to set various data types used by the
     1299  /// algorithm. The default traits class is
     1300  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
     1301  /// See \ref BfsVisitDefaultTraits for the documentation of
     1302  /// a BFS visit traits class.
    13111303#ifdef DOXYGEN
    13121304  template <typename GR, typename VS, typename TR>
  • lemon/bits/map_extender.h

    r867 r765  
    8585      typedef typename Map::Value Value;
    8686
    87       MapIt() : map(NULL) {}
    88 
    89       MapIt(Invalid i) : Parent(i), map(NULL) {}
    90 
    91       explicit MapIt(Map& _map) : map(&_map) {
    92         map->notifier()->first(*this);
     87      MapIt() {}
     88
     89      MapIt(Invalid i) : Parent(i) { }
     90
     91      explicit MapIt(Map& _map) : map(_map) {
     92        map.notifier()->first(*this);
    9393      }
    9494
    9595      MapIt(const Map& _map, const Item& item)
    96         : Parent(item), map(&_map) {}
     96        : Parent(item), map(_map) {}
    9797
    9898      MapIt& operator++() {
    99         map->notifier()->next(*this);
     99        map.notifier()->next(*this);
    100100        return *this;
    101101      }
    102102
    103103      typename MapTraits<Map>::ConstReturnValue operator*() const {
    104         return (*map)[*this];
     104        return map[*this];
    105105      }
    106106
    107107      typename MapTraits<Map>::ReturnValue operator*() {
    108         return (*map)[*this];
     108        return map[*this];
    109109      }
    110110
    111111      void set(const Value& value) {
    112         map->set(*this, value);
    113       }
    114 
    115     protected:
    116       Map* map;
     112        map.set(*this, value);
     113      }
     114
     115    protected:
     116      Map& map;
    117117
    118118    };
     
    125125      typedef typename Map::Value Value;
    126126
    127       ConstMapIt() : map(NULL) {}
    128 
    129       ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
    130 
    131       explicit ConstMapIt(Map& _map) : map(&_map) {
    132         map->notifier()->first(*this);
     127      ConstMapIt() {}
     128
     129      ConstMapIt(Invalid i) : Parent(i) { }
     130
     131      explicit ConstMapIt(Map& _map) : map(_map) {
     132        map.notifier()->first(*this);
    133133      }
    134134
     
    137137
    138138      ConstMapIt& operator++() {
    139         map->notifier()->next(*this);
     139        map.notifier()->next(*this);
    140140        return *this;
    141141      }
     
    146146
    147147    protected:
    148       const Map* map;
     148      const Map& map;
    149149    };
    150150
     
    153153
    154154    public:
    155       ItemIt() : map(NULL) {}
    156 
    157 
    158       ItemIt(Invalid i) : Parent(i), map(NULL) {}
    159 
    160       explicit ItemIt(Map& _map) : map(&_map) {
    161         map->notifier()->first(*this);
     155
     156      ItemIt() {}
     157
     158      ItemIt(Invalid i) : Parent(i) { }
     159
     160      explicit ItemIt(Map& _map) : map(_map) {
     161        map.notifier()->first(*this);
    162162      }
    163163
    164164      ItemIt(const Map& _map, const Item& item)
    165         : Parent(item), map(&_map) {}
     165        : Parent(item), map(_map) {}
    166166
    167167      ItemIt& operator++() {
    168         map->notifier()->next(*this);
    169         return *this;
    170       }
    171 
    172     protected:
    173       const Map* map;
     168        map.notifier()->next(*this);
     169        return *this;
     170      }
     171
     172    protected:
     173      const Map& map;
    174174
    175175    };
     
    232232      typedef typename Map::Value Value;
    233233
    234       MapIt() : map(NULL) {}
    235 
    236       MapIt(Invalid i) : Parent(i), map(NULL) { }
    237 
    238       explicit MapIt(Map& _map) : map(&_map) {
    239         map->graph.first(*this);
     234      MapIt() {}
     235
     236      MapIt(Invalid i) : Parent(i) { }
     237
     238      explicit MapIt(Map& _map) : map(_map) {
     239        map.graph.first(*this);
    240240      }
    241241
    242242      MapIt(const Map& _map, const Item& item)
    243         : Parent(item), map(&_map) {}
     243        : Parent(item), map(_map) {}
    244244
    245245      MapIt& operator++() {
    246         map->graph.next(*this);
     246        map.graph.next(*this);
    247247        return *this;
    248248      }
    249249
    250250      typename MapTraits<Map>::ConstReturnValue operator*() const {
    251         return (*map)[*this];
     251        return map[*this];
    252252      }
    253253
    254254      typename MapTraits<Map>::ReturnValue operator*() {
    255         return (*map)[*this];
     255        return map[*this];
    256256      }
    257257
    258258      void set(const Value& value) {
    259         map->set(*this, value);
    260       }
    261 
    262     protected:
    263       Map* map;
     259        map.set(*this, value);
     260      }
     261
     262    protected:
     263      Map& map;
    264264
    265265    };
     
    272272      typedef typename Map::Value Value;
    273273
    274       ConstMapIt() : map(NULL) {}
    275 
    276       ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
    277 
    278       explicit ConstMapIt(Map& _map) : map(&_map) {
    279         map->graph.first(*this);
     274      ConstMapIt() {}
     275
     276      ConstMapIt(Invalid i) : Parent(i) { }
     277
     278      explicit ConstMapIt(Map& _map) : map(_map) {
     279        map.graph.first(*this);
    280280      }
    281281
    282282      ConstMapIt(const Map& _map, const Item& item)
    283         : Parent(item), map(&_map) {}
     283        : Parent(item), map(_map) {}
    284284
    285285      ConstMapIt& operator++() {
    286         map->graph.next(*this);
     286        map.graph.next(*this);
    287287        return *this;
    288288      }
    289289
    290290      typename MapTraits<Map>::ConstReturnValue operator*() const {
    291         return (*map)[*this];
    292       }
    293 
    294     protected:
    295       const Map* map;
     291        return map[*this];
     292      }
     293
     294    protected:
     295      const Map& map;
    296296    };
    297297
     
    300300
    301301    public:
    302       ItemIt() : map(NULL) {}
    303 
    304 
    305       ItemIt(Invalid i) : Parent(i), map(NULL) { }
    306 
    307       explicit ItemIt(Map& _map) : map(&_map) {
    308         map->graph.first(*this);
     302
     303      ItemIt() {}
     304
     305      ItemIt(Invalid i) : Parent(i) { }
     306
     307      explicit ItemIt(Map& _map) : map(_map) {
     308        map.graph.first(*this);
    309309      }
    310310
    311311      ItemIt(const Map& _map, const Item& item)
    312         : Parent(item), map(&_map) {}
     312        : Parent(item), map(_map) {}
    313313
    314314      ItemIt& operator++() {
    315         map->graph.next(*this);
    316         return *this;
    317       }
    318 
    319     protected:
    320       const Map* map;
     315        map.graph.next(*this);
     316        return *this;
     317      }
     318
     319    protected:
     320      const Map& map;
    321321
    322322    };
  • lemon/circulation.h

    r891 r833  
    174174     \tparam SM The type of the supply map. The default map type is
    175175     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
    176      \tparam TR The traits class that defines various types used by the
    177      algorithm. By default, it is \ref CirculationDefaultTraits
    178      "CirculationDefaultTraits<GR, LM, UM, SM>".
    179      In most cases, this parameter should not be set directly,
    180      consider to use the named template parameters instead.
    181176  */
    182177#ifdef DOXYGEN
  • lemon/concepts/heap.h

    r883 r757  
    8989      /// handle the cross references. The assigned value must be
    9090      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    91 #ifdef DOXYGEN
    9291      explicit Heap(ItemIntMap &map) {}
    93 #else
    94       explicit Heap(ItemIntMap&) {}
    95 #endif     
    9692
    9793      /// \brief Constructor.
     
    10399      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    104100      /// \param comp The function object used for comparing the priorities.
    105 #ifdef DOXYGEN
    106101      explicit Heap(ItemIntMap &map, const CMP &comp) {}
    107 #else
    108       explicit Heap(ItemIntMap&, const CMP&) {}
    109 #endif     
    110102
    111103      /// \brief The number of items stored in the heap.
     
    135127      /// \param p The priority of the item.
    136128      /// \pre \e i must not be stored in the heap.
    137 #ifdef DOXYGEN
    138129      void push(const Item &i, const Prio &p) {}
    139 #else
    140       void push(const Item&, const Prio&) {}
    141 #endif     
    142130
    143131      /// \brief Return the item having minimum priority.
     
    145133      /// This function returns the item having minimum priority.
    146134      /// \pre The heap must be non-empty.
    147       Item top() const { return Item(); }
     135      Item top() const {}
    148136
    149137      /// \brief The minimum priority.
     
    151139      /// This function returns the minimum priority.
    152140      /// \pre The heap must be non-empty.
    153       Prio prio() const { return Prio(); }
     141      Prio prio() const {}
    154142
    155143      /// \brief Remove the item having minimum priority.
     
    165153      /// \param i The item to delete.
    166154      /// \pre \e i must be in the heap.
    167 #ifdef DOXYGEN
    168155      void erase(const Item &i) {}
    169 #else
    170       void erase(const Item&) {}
    171 #endif     
    172156
    173157      /// \brief The priority of the given item.
     
    176160      /// \param i The item.
    177161      /// \pre \e i must be in the heap.
    178 #ifdef DOXYGEN
    179162      Prio operator[](const Item &i) const {}
    180 #else
    181       Prio operator[](const Item&) const { return Prio(); }
    182 #endif     
    183163
    184164      /// \brief Set the priority of an item or insert it, if it is
     
    191171      /// \param i The item.
    192172      /// \param p The priority.
    193 #ifdef DOXYGEN
    194173      void set(const Item &i, const Prio &p) {}
    195 #else
    196       void set(const Item&, const Prio&) {}
    197 #endif     
    198174
    199175      /// \brief Decrease the priority of an item to the given value.
     
    203179      /// \param p The priority.
    204180      /// \pre \e i must be stored in the heap with priority at least \e p.
    205 #ifdef DOXYGEN
    206181      void decrease(const Item &i, const Prio &p) {}
    207 #else
    208       void decrease(const Item&, const Prio&) {}
    209 #endif     
    210182
    211183      /// \brief Increase the priority of an item to the given value.
     
    215187      /// \param p The priority.
    216188      /// \pre \e i must be stored in the heap with priority at most \e p.
    217 #ifdef DOXYGEN
    218189      void increase(const Item &i, const Prio &p) {}
    219 #else
    220       void increase(const Item&, const Prio&) {}
    221 #endif     
    222190
    223191      /// \brief Return the state of an item.
     
    229197      /// to the heap again.
    230198      /// \param i The item.
    231 #ifdef DOXYGEN
    232199      State state(const Item &i) const {}
    233 #else
    234       State state(const Item&) const { return PRE_HEAP; }
    235 #endif     
    236200
    237201      /// \brief Set the state of an item in the heap.
     
    242206      /// \param i The item.
    243207      /// \param st The state. It should not be \c IN_HEAP.
    244 #ifdef DOXYGEN
    245208      void state(const Item& i, State st) {}
    246 #else
    247       void state(const Item&, State) {}
    248 #endif     
    249209
    250210
  • lemon/dfs.h

    r891 r835  
    122122  ///\tparam GR The type of the digraph the algorithm runs on.
    123123  ///The default type is \ref ListDigraph.
    124   ///\tparam TR The traits class that defines various types used by the
    125   ///algorithm. By default, it is \ref DfsDefaultTraits
    126   ///"DfsDefaultTraits<GR>".
    127   ///In most cases, this parameter should not be set directly,
    128   ///consider to use the named template parameters instead.
    129124#ifdef DOXYGEN
    130125  template <typename GR,
     
    893888  /// This class should only be used through the \ref dfs() function,
    894889  /// which makes it easier to use the algorithm.
    895   ///
    896   /// \tparam TR The traits class that defines various types used by the
    897   /// algorithm.
    898890  template<class TR>
    899891  class DfsWizard : public TR
     
    12461238  /// does not observe the DFS events. If you want to observe the DFS
    12471239  /// events, you should implement your own visitor class.
    1248   /// \tparam TR The traits class that defines various types used by the
    1249   /// algorithm. By default, it is \ref DfsVisitDefaultTraits
    1250   /// "DfsVisitDefaultTraits<GR>".
    1251   /// In most cases, this parameter should not be set directly,
    1252   /// consider to use the named template parameters instead.
     1240  /// \tparam TR Traits class to set various data types used by the
     1241  /// algorithm. The default traits class is
     1242  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
     1243  /// See \ref DfsVisitDefaultTraits for the documentation of
     1244  /// a DFS visit traits class.
    12531245#ifdef DOXYGEN
    12541246  template <typename GR, typename VS, typename TR>
  • lemon/dijkstra.h

    r891 r835  
    193193  ///it is necessary. The default map type is \ref
    194194  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    195   ///\tparam TR The traits class that defines various types used by the
    196   ///algorithm. By default, it is \ref DijkstraDefaultTraits
    197   ///"DijkstraDefaultTraits<GR, LEN>".
    198   ///In most cases, this parameter should not be set directly,
    199   ///consider to use the named template parameters instead.
    200195#ifdef DOXYGEN
    201196  template <typename GR, typename LEN, typename TR>
     
    10981093  /// This class should only be used through the \ref dijkstra() function,
    10991094  /// which makes it easier to use the algorithm.
    1100   ///
    1101   /// \tparam TR The traits class that defines various types used by the
    1102   /// algorithm.
    11031095  template<class TR>
    11041096  class DijkstraWizard : public TR
  • lemon/glpk.h

    r902 r793  
    2626#include <lemon/lp_base.h>
    2727
     28// forward declaration
     29#if !defined _GLP_PROB && !defined GLP_PROB
     30#define _GLP_PROB
     31#define GLP_PROB
     32typedef struct { double _opaque_prob; } glp_prob;
     33/* LP/MIP problem object */
     34#endif
     35
    2836namespace lemon {
    2937
    30   namespace _solver_bits {
    31     class VoidPtr {
    32     private:
    33       void *_ptr;     
    34     public:
    35       VoidPtr() : _ptr(0) {}
    36 
    37       template <typename T>
    38       VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
    39 
    40       template <typename T>
    41       VoidPtr& operator=(T* ptr) {
    42         _ptr = reinterpret_cast<void*>(ptr);
    43         return *this;
    44       }
    45 
    46       template <typename T>
    47       operator T*() const { return reinterpret_cast<T*>(_ptr); }
    48     };
    49   }
    5038
    5139  /// \brief Base interface for the GLPK LP and MIP solver
     
    5644  protected:
    5745
    58     _solver_bits::VoidPtr lp;
     46    typedef glp_prob LPX;
     47    glp_prob* lp;
    5948
    6049    GlpkBase();
     
    135124
    136125    ///Pointer to the underlying GLPK data structure.
    137     _solver_bits::VoidPtr lpx() {return lp;}
     126    LPX *lpx() {return lp;}
    138127    ///Const pointer to the underlying GLPK data structure.
    139     _solver_bits::VoidPtr lpx() const {return lp;}
     128    const LPX *lpx() const {return lp;}
    140129
    141130    ///Returns the constraint identifier understood by GLPK.
  • lemon/hartmann_orlin.h

    r891 r859  
    107107  /// \tparam LEN The type of the length map. The default
    108108  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    109   /// \tparam TR The traits class that defines various types used by the
    110   /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits
    111   /// "HartmannOrlinDefaultTraits<GR, LEN>".
    112   /// In most cases, this parameter should not be set directly,
    113   /// consider to use the named template parameters instead.
    114109#ifdef DOXYGEN
    115110  template <typename GR, typename LEN, typename TR>
     
    133128    ///
    134129    /// The large value type used for internal computations.
    135     /// By default, it is \c long \c long if the \c Value type is integer,
     130    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
     131    /// it is \c long \c long if the \c Value type is integer,
    136132    /// otherwise it is \c double.
    137133    typedef typename TR::LargeValue LargeValue;
  • lemon/howard.h

    r891 r818  
    107107  /// \tparam LEN The type of the length map. The default
    108108  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    109   /// \tparam TR The traits class that defines various types used by the
    110   /// algorithm. By default, it is \ref HowardDefaultTraits
    111   /// "HowardDefaultTraits<GR, LEN>".
    112   /// In most cases, this parameter should not be set directly,
    113   /// consider to use the named template parameters instead.
    114109#ifdef DOXYGEN
    115110  template <typename GR, typename LEN, typename TR>
     
    133128    ///
    134129    /// The large value type used for internal computations.
    135     /// By default, it is \c long \c long if the \c Value type is integer,
     130    /// Using the \ref HowardDefaultTraits "default traits class",
     131    /// it is \c long \c long if the \c Value type is integer,
    136132    /// otherwise it is \c double.
    137133    typedef typename TR::LargeValue LargeValue;
  • lemon/karp.h

    r891 r819  
    105105  /// \tparam LEN The type of the length map. The default
    106106  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    107   /// \tparam TR The traits class that defines various types used by the
    108   /// algorithm. By default, it is \ref KarpDefaultTraits
    109   /// "KarpDefaultTraits<GR, LEN>".
    110   /// In most cases, this parameter should not be set directly,
    111   /// consider to use the named template parameters instead.
    112107#ifdef DOXYGEN
    113108  template <typename GR, typename LEN, typename TR>
     
    131126    ///
    132127    /// The large value type used for internal computations.
    133     /// By default, it is \c long \c long if the \c Value type is integer,
     128    /// Using the \ref KarpDefaultTraits "default traits class",
     129    /// it is \c long \c long if the \c Value type is integer,
    134130    /// otherwise it is \c double.
    135131    typedef typename TR::LargeValue LargeValue;
  • lemon/min_cost_arborescence.h

    r891 r760  
    113113  /// it is necessary. The default map type is \ref
    114114  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    115   /// \tparam TR The traits class that defines various types used by the
    116   /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits
     115  /// \param TR Traits class to set various data types used
     116  /// by the algorithm. The default traits class is
     117  /// \ref MinCostArborescenceDefaultTraits
    117118  /// "MinCostArborescenceDefaultTraits<GR, CM>".
    118   /// In most cases, this parameter should not be set directly,
    119   /// consider to use the named template parameters instead.
    120119#ifndef DOXYGEN
    121120  template <typename GR,
     
    124123              MinCostArborescenceDefaultTraits<GR, CM> >
    125124#else
    126   template <typename GR, typename CM, typename TR>
     125  template <typename GR, typename CM, typedef TR>
    127126#endif
    128127  class MinCostArborescence {
  • lemon/network_simplex.h

    r898 r835  
    4444  /// \ref amo93networkflows, \ref dantzig63linearprog,
    4545  /// \ref kellyoneill91netsimplex.
    46   /// This algorithm is a highly efficient specialized version of the
    47   /// linear programming simplex method directly for the minimum cost
    48   /// flow problem.
     46  /// This algorithm is a specialized version of the linear programming
     47  /// simplex method directly for the minimum cost flow problem.
     48  /// It is one of the most efficient solution methods.
    4949  ///
    50   /// In general, %NetworkSimplex is the fastest implementation available
    51   /// in LEMON for this problem.
    52   /// Moreover, it supports both directions of the supply/demand inequality
     50  /// In general this class is the fastest implementation available
     51  /// in LEMON for the minimum cost flow problem.
     52  /// Moreover it supports both directions of the supply/demand inequality
    5353  /// constraints. For more information, see \ref SupplyType.
    5454  ///
     
    5959  ///
    6060  /// \tparam GR The digraph type the algorithm runs on.
    61   /// \tparam V The number type used for flow amounts, capacity bounds
     61  /// \tparam V The value type used for flow amounts, capacity bounds
    6262  /// and supply values in the algorithm. By default, it is \c int.
    63   /// \tparam C The number type used for costs and potentials in the
     63  /// \tparam C The value type used for costs and potentials in the
    6464  /// algorithm. By default, it is the same as \c V.
    6565  ///
    66   /// \warning Both number types must be signed and all input data must
     66  /// \warning Both value types must be signed and all input data must
    6767  /// be integer.
    6868  ///
     
    127127    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    128128    /// proved to be the most efficient and the most robust on various
    129     /// test inputs.
     129    /// test inputs according to our benchmark tests.
    130130    /// However, another pivot rule can be selected using the \ref run()
    131131    /// function with the proper parameter.
     
    165165
    166166    typedef std::vector<int> IntVector;
    167     typedef std::vector<char> CharVector;
     167    typedef std::vector<bool> BoolVector;
    168168    typedef std::vector<Value> ValueVector;
    169169    typedef std::vector<Cost> CostVector;
     
    195195    IntVector _source;
    196196    IntVector _target;
    197     bool _arc_mixing;
    198197
    199198    // Node and arc data
     
    214213    IntVector _last_succ;
    215214    IntVector _dirty_revs;
    216     CharVector _forward;
    217     CharVector _state;
     215    BoolVector _forward;
     216    IntVector _state;
    218217    int _root;
    219218
     
    223222    int stem, par_stem, new_stem;
    224223    Value delta;
    225    
    226     const Value MAX;
    227224
    228225  public:
     
    246243      const IntVector  &_target;
    247244      const CostVector &_cost;
    248       const CharVector &_state;
     245      const IntVector &_state;
    249246      const CostVector &_pi;
    250247      int &_in_arc;
     
    298295      const IntVector  &_target;
    299296      const CostVector &_cost;
    300       const CharVector &_state;
     297      const IntVector &_state;
    301298      const CostVector &_pi;
    302299      int &_in_arc;
     
    337334      const IntVector  &_target;
    338335      const CostVector &_cost;
    339       const CharVector &_state;
     336      const IntVector &_state;
    340337      const CostVector &_pi;
    341338      int &_in_arc;
     
    410407      const IntVector  &_target;
    411408      const CostVector &_cost;
    412       const CharVector &_state;
     409      const IntVector &_state;
    413410      const CostVector &_pi;
    414411      int &_in_arc;
     
    513510      const IntVector  &_target;
    514511      const CostVector &_cost;
    515       const CharVector &_state;
     512      const IntVector &_state;
    516513      const CostVector &_pi;
    517514      int &_in_arc;
     
    635632    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    636633      _graph(graph), _node_id(graph), _arc_id(graph),
    637       _arc_mixing(arc_mixing),
    638       MAX(std::numeric_limits<Value>::max()),
    639634      INF(std::numeric_limits<Value>::has_infinity ?
    640           std::numeric_limits<Value>::infinity() : MAX)
     635          std::numeric_limits<Value>::infinity() :
     636          std::numeric_limits<Value>::max())
    641637    {
    642       // Check the number types
     638      // Check the value types
    643639      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
    644640        "The flow type of NetworkSimplex must be signed");
     
    646642        "The cost type of NetworkSimplex must be signed");
    647643       
    648       // Reset data structures
     644      // Resize vectors
     645      _node_num = countNodes(_graph);
     646      _arc_num = countArcs(_graph);
     647      int all_node_num = _node_num + 1;
     648      int max_arc_num = _arc_num + 2 * _node_num;
     649
     650      _source.resize(max_arc_num);
     651      _target.resize(max_arc_num);
     652
     653      _lower.resize(_arc_num);
     654      _upper.resize(_arc_num);
     655      _cap.resize(max_arc_num);
     656      _cost.resize(max_arc_num);
     657      _supply.resize(all_node_num);
     658      _flow.resize(max_arc_num);
     659      _pi.resize(all_node_num);
     660
     661      _parent.resize(all_node_num);
     662      _pred.resize(all_node_num);
     663      _forward.resize(all_node_num);
     664      _thread.resize(all_node_num);
     665      _rev_thread.resize(all_node_num);
     666      _succ_num.resize(all_node_num);
     667      _last_succ.resize(all_node_num);
     668      _state.resize(max_arc_num);
     669
     670      // Copy the graph
     671      int i = 0;
     672      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     673        _node_id[n] = i;
     674      }
     675      if (arc_mixing) {
     676        // Store the arcs in a mixed order
     677        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     678        int i = 0, j = 0;
     679        for (ArcIt a(_graph); a != INVALID; ++a) {
     680          _arc_id[a] = i;
     681          _source[i] = _node_id[_graph.source(a)];
     682          _target[i] = _node_id[_graph.target(a)];
     683          if ((i += k) >= _arc_num) i = ++j;
     684        }
     685      } else {
     686        // Store the arcs in the original order
     687        int i = 0;
     688        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
     689          _arc_id[a] = i;
     690          _source[i] = _node_id[_graph.source(a)];
     691          _target[i] = _node_id[_graph.target(a)];
     692        }
     693      }
     694     
     695      // Reset parameters
    649696      reset();
    650697    }
     
    681728    /// If it is not used before calling \ref run(), the upper bounds
    682729    /// will be set to \ref INF on all arcs (i.e. the flow value will be
    683     /// unbounded from above).
     730    /// unbounded from above on each arc).
    684731    ///
    685732    /// \param map An arc map storing the upper bounds.
     
    794841    /// \endcode
    795842    ///
    796     /// This function can be called more than once. All the given parameters
    797     /// are kept for the next call, unless \ref resetParams() or \ref reset()
    798     /// is used, thus only the modified parameters have to be set again.
    799     /// If the underlying digraph was also modified after the construction
    800     /// of the class (or the last \ref reset() call), then the \ref reset()
    801     /// function must be called.
     843    /// This function can be called more than once. All the parameters
     844    /// that have been given are kept for the next call, unless
     845    /// \ref reset() is called, thus only the modified parameters
     846    /// have to be set again. See \ref reset() for examples.
     847    /// However, the underlying digraph must not be modified after this
     848    /// class have been constructed, since it copies and extends the graph.
    802849    ///
    803850    /// \param pivot_rule The pivot rule that will be used during the
     
    813860    ///
    814861    /// \see ProblemType, PivotRule
    815     /// \see resetParams(), reset()
    816862    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
    817863      if (!init()) return INFEASIBLE;
     
    825871    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    826872    ///
    827     /// It is useful for multiple \ref run() calls. Basically, all the given
    828     /// parameters are kept for the next \ref run() call, unless
    829     /// \ref resetParams() or \ref reset() is used.
    830     /// If the underlying digraph was also modified after the construction
    831     /// of the class or the last \ref reset() call, then the \ref reset()
    832     /// function must be used, otherwise \ref resetParams() is sufficient.
     873    /// It is useful for multiple run() calls. If this function is not
     874    /// used, all the parameters given before are kept for the next
     875    /// \ref run() call.
     876    /// However, the underlying digraph must not be modified after this
     877    /// class have been constructed, since it copies and extends the graph.
    833878    ///
    834879    /// For example,
     
    840885    ///     .supplyMap(sup).run();
    841886    ///
    842     ///   // Run again with modified cost map (resetParams() is not called,
     887    ///   // Run again with modified cost map (reset() is not called,
    843888    ///   // so only the cost map have to be set again)
    844889    ///   cost[e] += 100;
    845890    ///   ns.costMap(cost).run();
    846891    ///
    847     ///   // Run again from scratch using resetParams()
     892    ///   // Run again from scratch using reset()
    848893    ///   // (the lower bounds will be set to zero on all arcs)
    849     ///   ns.resetParams();
     894    ///   ns.reset();
    850895    ///   ns.upperMap(capacity).costMap(cost)
    851896    ///     .supplyMap(sup).run();
     
    853898    ///
    854899    /// \return <tt>(*this)</tt>
    855     ///
    856     /// \see reset(), run()
    857     NetworkSimplex& resetParams() {
     900    NetworkSimplex& reset() {
    858901      for (int i = 0; i != _node_num; ++i) {
    859902        _supply[i] = 0;
     
    869912    }
    870913
    871     /// \brief Reset the internal data structures and all the parameters
    872     /// that have been given before.
    873     ///
    874     /// This function resets the internal data structures and all the
    875     /// paramaters that have been given before using functions \ref lowerMap(),
    876     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
    877     /// \ref supplyType().
    878     ///
    879     /// It is useful for multiple \ref run() calls. Basically, all the given
    880     /// parameters are kept for the next \ref run() call, unless
    881     /// \ref resetParams() or \ref reset() is used.
    882     /// If the underlying digraph was also modified after the construction
    883     /// of the class or the last \ref reset() call, then the \ref reset()
    884     /// function must be used, otherwise \ref resetParams() is sufficient.
    885     ///
    886     /// See \ref resetParams() for examples.
    887     ///
    888     /// \return <tt>(*this)</tt>
    889     ///
    890     /// \see resetParams(), run()
    891     NetworkSimplex& reset() {
    892       // Resize vectors
    893       _node_num = countNodes(_graph);
    894       _arc_num = countArcs(_graph);
    895       int all_node_num = _node_num + 1;
    896       int max_arc_num = _arc_num + 2 * _node_num;
    897 
    898       _source.resize(max_arc_num);
    899       _target.resize(max_arc_num);
    900 
    901       _lower.resize(_arc_num);
    902       _upper.resize(_arc_num);
    903       _cap.resize(max_arc_num);
    904       _cost.resize(max_arc_num);
    905       _supply.resize(all_node_num);
    906       _flow.resize(max_arc_num);
    907       _pi.resize(all_node_num);
    908 
    909       _parent.resize(all_node_num);
    910       _pred.resize(all_node_num);
    911       _forward.resize(all_node_num);
    912       _thread.resize(all_node_num);
    913       _rev_thread.resize(all_node_num);
    914       _succ_num.resize(all_node_num);
    915       _last_succ.resize(all_node_num);
    916       _state.resize(max_arc_num);
    917 
    918       // Copy the graph
    919       int i = 0;
    920       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    921         _node_id[n] = i;
    922       }
    923       if (_arc_mixing) {
    924         // Store the arcs in a mixed order
    925         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    926         int i = 0, j = 0;
    927         for (ArcIt a(_graph); a != INVALID; ++a) {
    928           _arc_id[a] = i;
    929           _source[i] = _node_id[_graph.source(a)];
    930           _target[i] = _node_id[_graph.target(a)];
    931           if ((i += k) >= _arc_num) i = ++j;
    932         }
    933       } else {
    934         // Store the arcs in the original order
    935         int i = 0;
    936         for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
    937           _arc_id[a] = i;
    938           _source[i] = _node_id[_graph.source(a)];
    939           _target[i] = _node_id[_graph.target(a)];
    940         }
    941       }
    942      
    943       // Reset parameters
    944       resetParams();
    945       return *this;
    946     }
    947    
    948914    /// @}
    949915
     
    10551021          Value c = _lower[i];
    10561022          if (c >= 0) {
    1057             _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
     1023            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
    10581024          } else {
    1059             _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
     1025            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
    10601026          }
    10611027          _supply[_source[i]] -= c;
     
    12491215        e = _pred[u];
    12501216        d = _forward[u] ?
    1251           _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
     1217          _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
    12521218        if (d < delta) {
    12531219          delta = d;
     
    12601226        e = _pred[u];
    12611227        d = _forward[u] ?
    1262           (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
     1228          (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
    12631229        if (d <= delta) {
    12641230          delta = d;
     
    14591425        findJoinNode();
    14601426        bool change = findLeavingArc();
    1461         if (delta >= MAX) return UNBOUNDED;
     1427        if (delta >= INF) return UNBOUNDED;
    14621428        changeFlow(change);
    14631429        if (change) {
  • lemon/planarity.h

    r896 r862  
    519519  ///
    520520  /// This function implements the Boyer-Myrvold algorithm for
    521   /// planarity checking of an undirected simple graph. It is a simplified
     521  /// planarity checking of an undirected graph. It is a simplified
    522522  /// version of the PlanarEmbedding algorithm class because neither
    523   /// the embedding nor the Kuratowski subdivisons are computed.
     523  /// the embedding nor the kuratowski subdivisons are not computed.
    524524  template <typename GR>
    525525  bool checkPlanarity(const GR& graph) {
     
    533533  ///
    534534  /// This class implements the Boyer-Myrvold algorithm for planar
    535   /// embedding of an undirected simple graph. The planar embedding is an
     535  /// embedding of an undirected graph. The planar embedding is an
    536536  /// ordering of the outgoing edges of the nodes, which is a possible
    537537  /// configuration to draw the graph in the plane. If there is not
    538   /// such ordering then the graph contains a K<sub>5</sub> (full graph
    539   /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
    540   /// 3 Red and 3 Blue nodes) subdivision.
     538  /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
     539  /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on
     540  /// 3 ANode and 3 BNode) subdivision.
    541541  ///
    542542  /// The current implementation calculates either an embedding or a
    543   /// Kuratowski subdivision. The running time of the algorithm is O(n).
    544   ///
    545   /// \see PlanarDrawing, checkPlanarity()
     543  /// Kuratowski subdivision. The running time of the algorithm is
     544  /// \f$ O(n) \f$.
    546545  template <typename Graph>
    547546  class PlanarEmbedding {
     
    593592  public:
    594593
    595     /// \brief The map type for storing the embedding
    596     ///
    597     /// The map type for storing the embedding.
    598     /// \see embeddingMap()
     594    /// \brief The map for store of embedding
    599595    typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
    600596
    601597    /// \brief Constructor
    602598    ///
    603     /// Constructor.
    604     /// \pre The graph must be simple, i.e. it should not
    605     /// contain parallel or loop arcs.
     599    /// \note The graph should be simple, i.e. parallel and loop arc
     600    /// free.
    606601    PlanarEmbedding(const Graph& graph)
    607602      : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
    608603
    609     /// \brief Run the algorithm.
     604    /// \brief Runs the algorithm.
    610605    ///
    611     /// This function runs the algorithm.
    612     /// \param kuratowski If this parameter is set to \c false, then the
     606    /// Runs the algorithm.
     607    /// \param kuratowski If the parameter is false, then the
    613608    /// algorithm does not compute a Kuratowski subdivision.
    614     /// \return \c true if the graph is planar.
     609    ///\return %True when the graph is planar.
    615610    bool run(bool kuratowski = true) {
    616611      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
     
    705700    }
    706701
    707     /// \brief Give back the successor of an arc
     702    /// \brief Gives back the successor of an arc
    708703    ///
    709     /// This function gives back the successor of an arc. It makes
     704    /// Gives back the successor of an arc. This function makes
    710705    /// possible to query the cyclic order of the outgoing arcs from
    711706    /// a node.
     
    714709    }
    715710
    716     /// \brief Give back the calculated embedding map
     711    /// \brief Gives back the calculated embedding map
    717712    ///
    718     /// This function gives back the calculated embedding map, which
    719     /// contains the successor of each arc in the cyclic order of the
    720     /// outgoing arcs of its source node.
     713    /// The returned map contains the successor of each arc in the
     714    /// graph.
    721715    const EmbeddingMap& embeddingMap() const {
    722716      return _embedding;
    723717    }
    724718
    725     /// \brief Give back \c true if the given edge is in the Kuratowski
     719    /// \brief Gives back true if the undirected arc is in the
     720    /// kuratowski subdivision
     721    ///
     722    /// Gives back true if the undirected arc is in the kuratowski
    726723    /// subdivision
    727     ///
    728     /// This function gives back \c true if the given edge is in the found
    729     /// Kuratowski subdivision.
    730     /// \pre The \c run() function must be called with \c true parameter
    731     /// before using this function.
    732     bool kuratowski(const Edge& edge) const {
     724    /// \note The \c run() had to be called with true value.
     725    bool kuratowski(const Edge& edge) {
    733726      return _kuratowski[edge];
    734727    }
     
    20672060  ///
    20682061  /// The planar drawing algorithm calculates positions for the nodes
    2069   /// in the plane. These coordinates satisfy that if the edges are
    2070   /// represented with straight lines, then they will not intersect
     2062  /// in the plane which coordinates satisfy that if the arcs are
     2063  /// represented with straight lines then they will not intersect
    20712064  /// each other.
    20722065  ///
    2073   /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
    2074   /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
     2066  /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
     2067  /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square.
    20752068  /// The time complexity of the algorithm is O(n).
    2076   ///
    2077   /// \see PlanarEmbedding
    20782069  template <typename Graph>
    20792070  class PlanarDrawing {
     
    20822073    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    20832074
    2084     /// \brief The point type for storing coordinates
     2075    /// \brief The point type for store coordinates
    20852076    typedef dim2::Point<int> Point;
    2086     /// \brief The map type for storing the coordinates of the nodes
     2077    /// \brief The map type for store coordinates
    20872078    typedef typename Graph::template NodeMap<Point> PointMap;
    20882079
     
    20912082    ///
    20922083    /// Constructor
    2093     /// \pre The graph must be simple, i.e. it should not
    2094     /// contain parallel or loop arcs.
     2084    /// \pre The graph should be simple, i.e. loop and parallel arc free.
    20952085    PlanarDrawing(const Graph& graph)
    20962086      : _graph(graph), _point_map(graph) {}
     
    23772367  public:
    23782368
    2379     /// \brief Calculate the node positions
     2369    /// \brief Calculates the node positions
    23802370    ///
    2381     /// This function calculates the node positions on the plane.
    2382     /// \return \c true if the graph is planar.
     2371    /// This function calculates the node positions.
     2372    /// \return %True if the graph is planar.
    23832373    bool run() {
    23842374      PlanarEmbedding<Graph> pe(_graph);
     
    23892379    }
    23902380
    2391     /// \brief Calculate the node positions according to a
     2381    /// \brief Calculates the node positions according to a
    23922382    /// combinatorical embedding
    23932383    ///
    2394     /// This function calculates the node positions on the plane.
    2395     /// The given \c embedding map should contain a valid combinatorical
    2396     /// embedding, i.e. a valid cyclic order of the arcs.
    2397     /// It can be computed using PlanarEmbedding.
     2384    /// This function calculates the node locations. The \c embedding
     2385    /// parameter should contain a valid combinatorical embedding, i.e.
     2386    /// a valid cyclic order of the arcs.
    23982387    template <typename EmbeddingMap>
    23992388    void run(const EmbeddingMap& embedding) {
     
    24352424    /// \brief The coordinate of the given node
    24362425    ///
    2437     /// This function returns the coordinate of the given node.
     2426    /// The coordinate of the given node.
    24382427    Point operator[](const Node& node) const {
    24392428      return _point_map[node];
    24402429    }
    24412430
    2442     /// \brief Return the grid embedding in a node map
     2431    /// \brief Returns the grid embedding in a \e NodeMap.
    24432432    ///
    2444     /// This function returns the grid embedding in a node map of
    2445     /// \c dim2::Point<int> coordinates.
     2433    /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
    24462434    const PointMap& coords() const {
    24472435      return _point_map;
     
    24832471  ///
    24842472  /// The graph coloring problem is the coloring of the graph nodes
    2485   /// so that there are no adjacent nodes with the same color. The
    2486   /// planar graphs can always be colored with four colors, which is
    2487   /// proved by Appel and Haken. Their proofs provide a quadratic
     2473  /// that there are not adjacent nodes with the same color. The
     2474  /// planar graphs can be always colored with four colors, it is
     2475  /// proved by Appel and Haken and their proofs provide a quadratic
    24882476  /// time algorithm for four coloring, but it could not be used to
    2489   /// implement an efficient algorithm. The five and six coloring can be
    2490   /// made in linear time, but in this class, the five coloring has
     2477  /// implement efficient algorithm. The five and six coloring can be
     2478  /// made in linear time, but in this class the five coloring has
    24912479  /// quadratic worst case time complexity. The two coloring (if
    24922480  /// possible) is solvable with a graph search algorithm and it is
    24932481  /// implemented in \ref bipartitePartitions() function in LEMON. To
    2494   /// decide whether a planar graph is three colorable is NP-complete.
     2482  /// decide whether the planar graph is three colorable is
     2483  /// NP-complete.
    24952484  ///
    24962485  /// This class contains member functions for calculate colorings
    24972486  /// with five and six colors. The six coloring algorithm is a simple
    24982487  /// greedy coloring on the backward minimum outgoing order of nodes.
    2499   /// This order can be computed by selecting the node with least
    2500   /// outgoing arcs to unprocessed nodes in each phase. This order
     2488  /// This order can be computed as in each phase the node with least
     2489  /// outgoing arcs to unprocessed nodes is chosen. This order
    25012490  /// guarantees that when a node is chosen for coloring it has at
    25022491  /// most five already colored adjacents. The five coloring algorithm
     
    25112500    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    25122501
    2513     /// \brief The map type for storing color indices
     2502    /// \brief The map type for store color indexes
    25142503    typedef typename Graph::template NodeMap<int> IndexMap;
    2515     /// \brief The map type for storing colors
    2516     ///
    2517     /// The map type for storing colors.
    2518     /// \see Palette, Color
     2504    /// \brief The map type for store colors
    25192505    typedef ComposeMap<Palette, IndexMap> ColorMap;
    25202506
    25212507    /// \brief Constructor
    25222508    ///
    2523     /// Constructor.
    2524     /// \pre The graph must be simple, i.e. it should not
    2525     /// contain parallel or loop arcs.
     2509    /// Constructor
     2510    /// \pre The graph should be simple, i.e. loop and parallel arc free.
    25262511    PlanarColoring(const Graph& graph)
    25272512      : _graph(graph), _color_map(graph), _palette(0) {
     
    25342519    }
    25352520
    2536     /// \brief Return the node map of color indices
     2521    /// \brief Returns the \e NodeMap of color indexes
    25372522    ///
    2538     /// This function returns the node map of color indices. The values are
    2539     /// in the range \c [0..4] or \c [0..5] according to the coloring method.
     2523    /// Returns the \e NodeMap of color indexes. The values are in the
     2524    /// range \c [0..4] or \c [0..5] according to the coloring method.
    25402525    IndexMap colorIndexMap() const {
    25412526      return _color_map;
    25422527    }
    25432528
    2544     /// \brief Return the node map of colors
     2529    /// \brief Returns the \e NodeMap of colors
    25452530    ///
    2546     /// This function returns the node map of colors. The values are among
    2547     /// five or six distinct \ref lemon::Color "colors".
     2531    /// Returns the \e NodeMap of colors. The values are five or six
     2532    /// distinct \ref lemon::Color "colors".
    25482533    ColorMap colorMap() const {
    25492534      return composeMap(_palette, _color_map);
    25502535    }
    25512536
    2552     /// \brief Return the color index of the node
     2537    /// \brief Returns the color index of the node
    25532538    ///
    2554     /// This function returns the color index of the given node. The value is
    2555     /// in the range \c [0..4] or \c [0..5] according to the coloring method.
     2539    /// Returns the color index of the node. The values are in the
     2540    /// range \c [0..4] or \c [0..5] according to the coloring method.
    25562541    int colorIndex(const Node& node) const {
    25572542      return _color_map[node];
    25582543    }
    25592544
    2560     /// \brief Return the color of the node
     2545    /// \brief Returns the color of the node
    25612546    ///
    2562     /// This function returns the color of the given node. The value is among
    2563     /// five or six distinct \ref lemon::Color "colors".
     2547    /// Returns the color of the node. The values are five or six
     2548    /// distinct \ref lemon::Color "colors".
    25642549    Color color(const Node& node) const {
    25652550      return _palette[_color_map[node]];
     
    25672552
    25682553
    2569     /// \brief Calculate a coloring with at most six colors
     2554    /// \brief Calculates a coloring with at most six colors
    25702555    ///
    25712556    /// This function calculates a coloring with at most six colors. The time
    25722557    /// complexity of this variant is linear in the size of the graph.
    2573     /// \return \c true if the algorithm could color the graph with six colors.
    2574     /// If the algorithm fails, then the graph is not planar.
    2575     /// \note This function can return \c true if the graph is not
    2576     /// planar, but it can be colored with at most six colors.
     2558    /// \return %True when the algorithm could color the graph with six color.
     2559    /// If the algorithm fails, then the graph could not be planar.
     2560    /// \note This function can return true if the graph is not
     2561    /// planar but it can be colored with 6 colors.
    25772562    bool runSixColoring() {
    25782563
     
    26762661  public:
    26772662
    2678     /// \brief Calculate a coloring with at most five colors
     2663    /// \brief Calculates a coloring with at most five colors
    26792664    ///
    26802665    /// This function calculates a coloring with at most five
    26812666    /// colors. The worst case time complexity of this variant is
    26822667    /// quadratic in the size of the graph.
    2683     /// \param embedding This map should contain a valid combinatorical
    2684     /// embedding, i.e. a valid cyclic order of the arcs.
    2685     /// It can be computed using PlanarEmbedding.
    26862668    template <typename EmbeddingMap>
    26872669    void runFiveColoring(const EmbeddingMap& embedding) {
     
    27302712    }
    27312713
    2732     /// \brief Calculate a coloring with at most five colors
     2714    /// \brief Calculates a coloring with at most five colors
    27332715    ///
    27342716    /// This function calculates a coloring with at most five
    27352717    /// colors. The worst case time complexity of this variant is
    27362718    /// quadratic in the size of the graph.
    2737     /// \return \c true if the graph is planar.
     2719    /// \return %True when the graph is planar.
    27382720    bool runFiveColoring() {
    27392721      PlanarEmbedding<Graph> pe(_graph);
  • lemon/preflow.h

    r891 r835  
    114114  /// second phase constructs a feasible maximum flow on each arc.
    115115  ///
    116   /// \warning This implementation cannot handle infinite or very large
    117   /// capacities (e.g. the maximum value of \c CAP::Value).
    118   ///
    119116  /// \tparam GR The type of the digraph the algorithm runs on.
    120117  /// \tparam CAP The type of the capacity map. The default map
    121118  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    122   /// \tparam TR The traits class that defines various types used by the
    123   /// algorithm. By default, it is \ref PreflowDefaultTraits
    124   /// "PreflowDefaultTraits<GR, CAP>".
    125   /// In most cases, this parameter should not be set directly,
    126   /// consider to use the named template parameters instead.
    127119#ifdef DOXYGEN
    128120  template <typename GR, typename CAP, typename TR>
  • lemon/unionfind.h

    r864 r833  
    740740    void clear() {
    741741      items.clear();
    742       classes.clear();
     742      classes.clear;
    743743      firstClass = firstFreeClass = firstFreeItem = -1;
    744744    }
  • test/min_cost_flow_test.cc

    r898 r716  
    2525
    2626#include <lemon/network_simplex.h>
    27 #include <lemon/capacity_scaling.h>
    28 #include <lemon/cost_scaling.h>
    29 #include <lemon/cycle_canceling.h>
    3027
    3128#include <lemon/concepts/digraph.h>
    32 #include <lemon/concepts/heap.h>
    3329#include <lemon/concept_check.h>
    3430
     
    3733using namespace lemon;
    3834
    39 // Test networks
    4035char test_lgf[] =
    4136  "@nodes\n"
     
    8277  "target 12\n";
    8378
    84 char test_neg1_lgf[] =
    85   "@nodes\n"
    86   "label   sup\n"
    87   "    1   100\n"
    88   "    2     0\n"
    89   "    3     0\n"
    90   "    4  -100\n"
    91   "    5     0\n"
    92   "    6     0\n"
    93   "    7     0\n"
    94   "@arcs\n"
    95   "      cost   low1   low2\n"
    96   "1 2    100      0      0\n"
    97   "1 3     30      0      0\n"
    98   "2 4     20      0      0\n"
    99   "3 4     80      0      0\n"
    100   "3 2     50      0      0\n"
    101   "5 3     10      0      0\n"
    102   "5 6     80      0   1000\n"
    103   "6 7     30      0  -1000\n"
    104   "7 5   -120      0      0\n";
    105  
    106 char test_neg2_lgf[] =
    107   "@nodes\n"
    108   "label   sup\n"
    109   "    1   100\n"
    110   "    2  -300\n"
    111   "@arcs\n"
    112   "      cost\n"
    113   "1 2     -1\n";
    114 
    115 
    116 // Test data
    117 typedef ListDigraph Digraph;
    118 DIGRAPH_TYPEDEFS(ListDigraph);
    119 
    120 Digraph gr;
    121 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
    122 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
    123 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
    124 Node v, w;
    125 
    126 Digraph neg1_gr;
    127 Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);
    128 ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);
    129 Digraph::NodeMap<int> neg1_s(neg1_gr);
    130 
    131 Digraph neg2_gr;
    132 Digraph::ArcMap<int> neg2_c(neg2_gr);
    133 ConstMap<Arc, int> neg2_l(0), neg2_u(1000);
    134 Digraph::NodeMap<int> neg2_s(neg2_gr);
    135 
    13679
    13780enum SupplyType {
     
    14083  LEQ
    14184};
    142 
    14385
    14486// Check the interface of an MCF algorithm
     
    158100      const MCF& const_mcf = mcf;
    159101
    160       b = mcf.reset().resetParams()
     102      b = mcf.reset()
    161103             .lowerMap(me.lower)
    162104             .upperMap(me.upper)
     
    327269}
    328270
    329 template < typename MCF, typename Param >
    330 void runMcfGeqTests( Param param,
    331                      const std::string &test_str = "",
    332                      bool full_neg_cost_support = false )
    333 {
    334   MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr);
    335  
    336   // Basic tests
    337   mcf1.upperMap(u).costMap(c).supplyMap(s1);
    338   checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1,
    339            mcf1.OPTIMAL, true,     5240, test_str + "-1");
    340   mcf1.stSupply(v, w, 27);
    341   checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2,
    342            mcf1.OPTIMAL, true,     7620, test_str + "-2");
    343   mcf1.lowerMap(l2).supplyMap(s1);
    344   checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1,
    345            mcf1.OPTIMAL, true,     5970, test_str + "-3");
    346   mcf1.stSupply(v, w, 27);
    347   checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
    348            mcf1.OPTIMAL, true,     8010, test_str + "-4");
    349   mcf1.resetParams().supplyMap(s1);
    350   checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
    351            mcf1.OPTIMAL, true,       74, test_str + "-5");
    352   mcf1.lowerMap(l2).stSupply(v, w, 27);
    353   checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2,
    354            mcf1.OPTIMAL, true,       94, test_str + "-6");
    355   mcf1.reset();
    356   checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3,
    357            mcf1.OPTIMAL, true,        0, test_str + "-7");
    358   mcf1.lowerMap(l2).upperMap(u);
    359   checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3,
    360            mcf1.INFEASIBLE, false,    0, test_str + "-8");
    361   mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
    362   checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4,
    363            mcf1.OPTIMAL, true,     6360, test_str + "-9");
    364 
    365   // Tests for the GEQ form
    366   mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5);
    367   checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
    368            mcf1.OPTIMAL, true,     3530, test_str + "-10", GEQ);
    369   mcf1.lowerMap(l2);
    370   checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
    371            mcf1.OPTIMAL, true,     4540, test_str + "-11", GEQ);
    372   mcf1.supplyMap(s6);
    373   checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
    374            mcf1.INFEASIBLE, false,    0, test_str + "-12", GEQ);
    375 
    376   // Tests with negative costs
    377   mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s);
    378   checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s,
    379            mcf2.UNBOUNDED, false,     0, test_str + "-13");
    380   mcf2.upperMap(neg1_u2);
    381   checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
    382            mcf2.OPTIMAL, true,   -40000, test_str + "-14");
    383   mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
    384   checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
    385            mcf2.UNBOUNDED, false,     0, test_str + "-15");
    386 
    387   mcf3.costMap(neg2_c).supplyMap(neg2_s);
    388   if (full_neg_cost_support) {
    389     checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
    390              mcf3.OPTIMAL, true,   -300, test_str + "-16", GEQ);
    391   } else {
    392     checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
    393              mcf3.UNBOUNDED, false,   0, test_str + "-17", GEQ);
    394   }
    395   mcf3.upperMap(neg2_u);
    396   checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
    397            mcf3.OPTIMAL, true,     -300, test_str + "-18", GEQ);
    398 }
    399 
    400 template < typename MCF, typename Param >
    401 void runMcfLeqTests( Param param,
    402                      const std::string &test_str = "" )
    403 {
    404   // Tests for the LEQ form
    405   MCF mcf1(gr);
    406   mcf1.supplyType(mcf1.LEQ);
    407   mcf1.upperMap(u).costMap(c).supplyMap(s6);
    408   checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6,
    409            mcf1.OPTIMAL, true,   5080, test_str + "-19", LEQ);
    410   mcf1.lowerMap(l2);
    411   checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
    412            mcf1.OPTIMAL, true,   5930, test_str + "-20", LEQ);
    413   mcf1.supplyMap(s5);
    414   checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
    415            mcf1.INFEASIBLE, false,  0, test_str + "-21", LEQ);
    416 }
    417 
    418 
    419271int main()
    420272{
    421   // Read the test networks
     273  // Check the interfaces
     274  {
     275    typedef concepts::Digraph GR;
     276    checkConcept< McfClassConcept<GR, int, int>,
     277                  NetworkSimplex<GR> >();
     278    checkConcept< McfClassConcept<GR, double, double>,
     279                  NetworkSimplex<GR, double> >();
     280    checkConcept< McfClassConcept<GR, int, double>,
     281                  NetworkSimplex<GR, int, double> >();
     282  }
     283
     284  // Run various MCF tests
     285  typedef ListDigraph Digraph;
     286  DIGRAPH_TYPEDEFS(ListDigraph);
     287
     288  // Read the test digraph
     289  Digraph gr;
     290  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
     291  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
     292  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
     293  Node v, w;
     294
    422295  std::istringstream input(test_lgf);
    423296  DigraphReader<Digraph>(gr, input)
     
    437310    .run();
    438311 
    439   std::istringstream neg_inp1(test_neg1_lgf);
    440   DigraphReader<Digraph>(neg1_gr, neg_inp1)
    441     .arcMap("cost", neg1_c)
    442     .arcMap("low1", neg1_l1)
    443     .arcMap("low2", neg1_l2)
    444     .nodeMap("sup", neg1_s)
    445     .run();
    446  
    447   std::istringstream neg_inp2(test_neg2_lgf);
    448   DigraphReader<Digraph>(neg2_gr, neg_inp2)
    449     .arcMap("cost", neg2_c)
    450     .nodeMap("sup", neg2_s)
    451     .run();
    452  
    453   // Check the interface of NetworkSimplex
     312  // Build test digraphs with negative costs
     313  Digraph neg_gr;
     314  Node n1 = neg_gr.addNode();
     315  Node n2 = neg_gr.addNode();
     316  Node n3 = neg_gr.addNode();
     317  Node n4 = neg_gr.addNode();
     318  Node n5 = neg_gr.addNode();
     319  Node n6 = neg_gr.addNode();
     320  Node n7 = neg_gr.addNode();
     321 
     322  Arc a1 = neg_gr.addArc(n1, n2);
     323  Arc a2 = neg_gr.addArc(n1, n3);
     324  Arc a3 = neg_gr.addArc(n2, n4);
     325  Arc a4 = neg_gr.addArc(n3, n4);
     326  Arc a5 = neg_gr.addArc(n3, n2);
     327  Arc a6 = neg_gr.addArc(n5, n3);
     328  Arc a7 = neg_gr.addArc(n5, n6);
     329  Arc a8 = neg_gr.addArc(n6, n7);
     330  Arc a9 = neg_gr.addArc(n7, n5);
     331 
     332  Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
     333  ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
     334  Digraph::NodeMap<int> neg_s(neg_gr, 0);
     335 
     336  neg_l2[a7] =  1000;
     337  neg_l2[a8] = -1000;
     338 
     339  neg_s[n1] =  100;
     340  neg_s[n4] = -100;
     341 
     342  neg_c[a1] =  100;
     343  neg_c[a2] =   30;
     344  neg_c[a3] =   20;
     345  neg_c[a4] =   80;
     346  neg_c[a5] =   50;
     347  neg_c[a6] =   10;
     348  neg_c[a7] =   80;
     349  neg_c[a8] =   30;
     350  neg_c[a9] = -120;
     351
     352  Digraph negs_gr;
     353  Digraph::NodeMap<int> negs_s(negs_gr);
     354  Digraph::ArcMap<int> negs_c(negs_gr);
     355  ConstMap<Arc, int> negs_l(0), negs_u(1000);
     356  n1 = negs_gr.addNode();
     357  n2 = negs_gr.addNode();
     358  negs_s[n1] = 100;
     359  negs_s[n2] = -300;
     360  negs_c[negs_gr.addArc(n1, n2)] = -1;
     361
     362
     363  // A. Test NetworkSimplex with the default pivot rule
    454364  {
    455     typedef concepts::Digraph GR;
    456     checkConcept< McfClassConcept<GR, int, int>,
    457                   NetworkSimplex<GR> >();
    458     checkConcept< McfClassConcept<GR, double, double>,
    459                   NetworkSimplex<GR, double> >();
    460     checkConcept< McfClassConcept<GR, int, double>,
    461                   NetworkSimplex<GR, int, double> >();
    462   }
    463 
    464   // Check the interface of CapacityScaling
     365    NetworkSimplex<Digraph> mcf(gr);
     366
     367    // Check the equality form
     368    mcf.upperMap(u).costMap(c);
     369    checkMcf(mcf, mcf.supplyMap(s1).run(),
     370             gr, l1, u, c, s1, mcf.OPTIMAL, true,   5240, "#A1");
     371    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
     372             gr, l1, u, c, s2, mcf.OPTIMAL, true,   7620, "#A2");
     373    mcf.lowerMap(l2);
     374    checkMcf(mcf, mcf.supplyMap(s1).run(),
     375             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#A3");
     376    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
     377             gr, l2, u, c, s2, mcf.OPTIMAL, true,   8010, "#A4");
     378    mcf.reset();
     379    checkMcf(mcf, mcf.supplyMap(s1).run(),
     380             gr, l1, cu, cc, s1, mcf.OPTIMAL, true,   74, "#A5");
     381    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
     382             gr, l2, cu, cc, s2, mcf.OPTIMAL, true,   94, "#A6");
     383    mcf.reset();
     384    checkMcf(mcf, mcf.run(),
     385             gr, l1, cu, cc, s3, mcf.OPTIMAL, true,    0, "#A7");
     386    checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
     387             gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
     388    mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
     389    checkMcf(mcf, mcf.run(),
     390             gr, l3, u, c, s4, mcf.OPTIMAL, true,   6360, "#A9");
     391
     392    // Check the GEQ form
     393    mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
     394    checkMcf(mcf, mcf.run(),
     395             gr, l1, u, c, s5, mcf.OPTIMAL, true,   3530, "#A10", GEQ);
     396    mcf.supplyType(mcf.GEQ);
     397    checkMcf(mcf, mcf.lowerMap(l2).run(),
     398             gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);
     399    mcf.supplyMap(s6);
     400    checkMcf(mcf, mcf.run(),
     401             gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);
     402
     403    // Check the LEQ form
     404    mcf.reset().supplyType(mcf.LEQ);
     405    mcf.upperMap(u).costMap(c).supplyMap(s6);
     406    checkMcf(mcf, mcf.run(),
     407             gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);
     408    checkMcf(mcf, mcf.lowerMap(l2).run(),
     409             gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);
     410    mcf.supplyMap(s5);
     411    checkMcf(mcf, mcf.run(),
     412             gr, l2, u, c, s5, mcf.INFEASIBLE, false,  0, "#A15", LEQ);
     413
     414    // Check negative costs
     415    NetworkSimplex<Digraph> neg_mcf(neg_gr);
     416    neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);
     417    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
     418      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A16");
     419    neg_mcf.upperMap(neg_u2);
     420    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
     421      neg_c, neg_s, neg_mcf.OPTIMAL, true,  -40000, "#A17");
     422    neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
     423    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
     424      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A18");
     425     
     426    NetworkSimplex<Digraph> negs_mcf(negs_gr);
     427    negs_mcf.costMap(negs_c).supplyMap(negs_s);
     428    checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
     429      negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
     430  }
     431
     432  // B. Test NetworkSimplex with each pivot rule
    465433  {
    466     typedef concepts::Digraph GR;
    467     checkConcept< McfClassConcept<GR, int, int>,
    468                   CapacityScaling<GR> >();
    469     checkConcept< McfClassConcept<GR, double, double>,
    470                   CapacityScaling<GR, double> >();
    471     checkConcept< McfClassConcept<GR, int, double>,
    472                   CapacityScaling<GR, int, double> >();
    473     typedef CapacityScaling<GR>::
    474       SetHeap<concepts::Heap<int, RangeMap<int> > >::Create CAS;
    475     checkConcept< McfClassConcept<GR, int, int>, CAS >();
    476   }
    477 
    478   // Check the interface of CostScaling
    479   {
    480     typedef concepts::Digraph GR;
    481     checkConcept< McfClassConcept<GR, int, int>,
    482                   CostScaling<GR> >();
    483     checkConcept< McfClassConcept<GR, double, double>,
    484                   CostScaling<GR, double> >();
    485     checkConcept< McfClassConcept<GR, int, double>,
    486                   CostScaling<GR, int, double> >();
    487     typedef CostScaling<GR>::
    488       SetLargeCost<double>::Create COS;
    489     checkConcept< McfClassConcept<GR, int, int>, COS >();
    490   }
    491 
    492   // Check the interface of CycleCanceling
    493   {
    494     typedef concepts::Digraph GR;
    495     checkConcept< McfClassConcept<GR, int, int>,
    496                   CycleCanceling<GR> >();
    497     checkConcept< McfClassConcept<GR, double, double>,
    498                   CycleCanceling<GR, double> >();
    499     checkConcept< McfClassConcept<GR, int, double>,
    500                   CycleCanceling<GR, int, double> >();
    501   }
    502 
    503   // Test NetworkSimplex
    504   {
    505     typedef NetworkSimplex<Digraph> MCF;
    506     runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);
    507     runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");
    508     runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE", true);
    509     runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE");
    510     runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS", true);
    511     runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS");
    512     runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true);
    513     runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL");
    514     runMcfGeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL", true);
    515     runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");
    516   }
    517  
    518   // Test CapacityScaling
    519   {
    520     typedef CapacityScaling<Digraph> MCF;
    521     runMcfGeqTests<MCF>(0, "SSP");
    522     runMcfGeqTests<MCF>(2, "CAS");
    523   }
    524 
    525   // Test CostScaling
    526   {
    527     typedef CostScaling<Digraph> MCF;
    528     runMcfGeqTests<MCF>(MCF::PUSH, "COS-PR");
    529     runMcfGeqTests<MCF>(MCF::AUGMENT, "COS-AR");
    530     runMcfGeqTests<MCF>(MCF::PARTIAL_AUGMENT, "COS-PAR");
    531   }
    532 
    533   // Test CycleCanceling
    534   {
    535     typedef CycleCanceling<Digraph> MCF;
    536     runMcfGeqTests<MCF>(MCF::SIMPLE_CYCLE_CANCELING, "SCC");
    537     runMcfGeqTests<MCF>(MCF::MINIMUM_MEAN_CYCLE_CANCELING, "MMCC");
    538     runMcfGeqTests<MCF>(MCF::CANCEL_AND_TIGHTEN, "CAT");
     434    NetworkSimplex<Digraph> mcf(gr);
     435    mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
     436
     437    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
     438             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B1");
     439    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
     440             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B2");
     441    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
     442             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B3");
     443    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
     444             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B4");
     445    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
     446             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B5");
    539447  }
    540448
Note: See TracChangeset for help on using the changeset viewer.