COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [834:207ba6c0f2e4:835:b9b2e8abe70b] in lemon-main


Ignore:
Files:
4 added
22 edited

Legend:

Unmodified
Added
Removed

  • INSTALL

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

  • doc/CMakeLists.txt

    r744 r827  
    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
    2930    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    3031    COMMAND ${CMAKE_COMMAND} -E remove_directory html

  • doc/Makefile.am

    r744 r827  
    2929        edge_biconnected_components.eps \
    3030        node_biconnected_components.eps \
     31        planar.eps \
    3132        strongly_connected_components.eps
    3233

  • doc/groups.dox

    r771 r813  
    407407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    408408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    409  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    410    cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     410   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    411411   \ref bunnagel98efficient.
    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.
     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.
    418416
    419417In general NetworkSimplex is the most efficient implementation,

  • lemon/Makefile.am

    r799 r822  
    6363        lemon/binom_heap.h \
    6464        lemon/bucket_heap.h \
     65        lemon/capacity_scaling.h \
    6566        lemon/cbc.h \
    6667        lemon/circulation.h \
    … …  
    6970        lemon/concept_check.h \
    7071        lemon/connectivity.h \
     72        lemon/core.h \
     73        lemon/cost_scaling.h \
    7174        lemon/counter.h \
    72         lemon/core.h \
    7375        lemon/cplex.h \
     76        lemon/cycle_canceling.h \
    7477        lemon/dfs.h \
    7578        lemon/dijkstra.h \

  • lemon/bellman_ford.h

    r788 r825  
    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.
    174179#ifdef DOXYGEN
    175180  template <typename GR, typename LEN, typename TR>
    … …  
    238243        _dist = Traits::createDistMap(*_gr);
    239244      }
    240       _mask = new MaskMap(*_gr, false);
     245      if(!_mask) {
     246        _mask = new MaskMap(*_gr);
     247      }
    241248    }
    242249   
    … …  
    404411          _process.push_back(it);
    405412          _mask->set(it, true);
     413        }
     414      } else {
     415        for (NodeIt it(*_gr); it != INVALID; ++it) {
     416          _mask->set(it, false);
    406417        }
    407418      }
    … …  
    928939  /// This class should only be used through the \ref bellmanFord()
    929940  /// 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.
    930944  template<class TR>
    931945  class BellmanFordWizard : public TR {

  • lemon/bfs.h

    r788 r825  
    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.
    124129#ifdef DOXYGEN
    125130  template <typename GR,
    … …  
    958963  /// This class should only be used through the \ref bfs() function,
    959964  /// which makes it easier to use the algorithm.
     965  ///
     966  /// \tparam TR The traits class that defines various types used by the
     967  /// algorithm.
    960968  template<class TR>
    961969  class BfsWizard : public TR
    … …  
    12961304  /// does not observe the BFS events. If you want to observe the BFS
    12971305  /// events, you should implement your own visitor class.
    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.
     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.
    13031311#ifdef DOXYGEN
    13041312  template <typename GR, typename VS, typename TR>

  • lemon/bits/map_extender.h

    r718 r802  
    8585      typedef typename Map::Value Value;
    8686
    87       MapIt() {}
    88 
    89       MapIt(Invalid i) : Parent(i) { }
    90 
    91       explicit MapIt(Map& _map) : map(_map) {
    92         map.notifier()->first(*this);
     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);
    9393      }
    9494
    9595      MapIt(const Map& _map, const Item& item)
     96        : Parent(item), map(&_map) {}
     97
     98      MapIt& operator++() {
     99        map->notifier()->next(*this);
     100        return *this;
     101      }
     102
     103      typename MapTraits<Map>::ConstReturnValue operator*() const {
     104        return (*map)[*this];
     105      }
     106
     107      typename MapTraits<Map>::ReturnValue operator*() {
     108        return (*map)[*this];
     109      }
     110
     111      void set(const Value& value) {
     112        map->set(*this, value);
     113      }
     114
     115    protected:
     116      Map* map;
     117
     118    };
     119
     120    class ConstMapIt : public Item {
     121      typedef Item Parent;
     122
     123    public:
     124
     125      typedef typename Map::Value Value;
     126
     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);
     133      }
     134
     135      ConstMapIt(const Map& _map, const Item& item)
    96136        : Parent(item), map(_map) {}
    97137
    98       MapIt& operator++() {
    99         map.notifier()->next(*this);
     138      ConstMapIt& operator++() {
     139        map->notifier()->next(*this);
    100140        return *this;
    101141      }
    … …  
    105145      }
    106146
    107       typename MapTraits<Map>::ReturnValue operator*() {
    108         return map[*this];
    109       }
    110 
    111       void set(const Value& value) {
    112         map.set(*this, value);
    113       }
    114 
    115     protected:
    116       Map& map;
    117 
    118     };
    119 
    120     class ConstMapIt : public Item {
    121       typedef Item Parent;
    122 
    123     public:
    124 
    125       typedef typename Map::Value Value;
    126 
    127       ConstMapIt() {}
    128 
    129       ConstMapIt(Invalid i) : Parent(i) { }
    130 
    131       explicit ConstMapIt(Map& _map) : map(_map) {
    132         map.notifier()->first(*this);
    133       }
    134 
    135       ConstMapIt(const Map& _map, const Item& item)
    136         : Parent(item), map(_map) {}
    137 
    138       ConstMapIt& operator++() {
    139         map.notifier()->next(*this);
    140         return *this;
    141       }
    142 
    143       typename MapTraits<Map>::ConstReturnValue operator*() const {
    144         return map[*this];
    145       }
    146 
    147     protected:
    148       const Map& map;
     147    protected:
     148      const Map* map;
    149149    };
    150150
    … …  
    153153
    154154    public:
    155 
    156       ItemIt() {}
    157 
    158       ItemIt(Invalid i) : Parent(i) { }
    159 
    160       explicit ItemIt(Map& _map) : map(_map) {
    161         map.notifier()->first(*this);
     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);
    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() {}
    235 
    236       MapIt(Invalid i) : Parent(i) { }
    237 
    238       explicit MapIt(Map& _map) : map(_map) {
    239         map.graph.first(*this);
     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);
    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() {}
    275 
    276       ConstMapIt(Invalid i) : Parent(i) { }
    277 
    278       explicit ConstMapIt(Map& _map) : map(_map) {
    279         map.graph.first(*this);
     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);
    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 
    303       ItemIt() {}
    304 
    305       ItemIt(Invalid i) : Parent(i) { }
    306 
    307       explicit ItemIt(Map& _map) : map(_map) {
    308         map.graph.first(*this);
     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);
    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

    r786 r825  
    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.
    176181  */
    177182#ifdef DOXYGEN

  • lemon/concepts/heap.h

    r710 r817  
    8989      /// handle the cross references. The assigned value must be
    9090      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
     91#ifdef DOXYGEN
    9192      explicit Heap(ItemIntMap &map) {}
     93#else
     94      explicit Heap(ItemIntMap&) {}
     95#endif     
    9296
    9397      /// \brief Constructor.
    … …  
    99103      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    100104      /// \param comp The function object used for comparing the priorities.
     105#ifdef DOXYGEN
    101106      explicit Heap(ItemIntMap &map, const CMP &comp) {}
     107#else
     108      explicit Heap(ItemIntMap&, const CMP&) {}
     109#endif     
    102110
    103111      /// \brief The number of items stored in the heap.
    … …  
    127135      /// \param p The priority of the item.
    128136      /// \pre \e i must not be stored in the heap.
     137#ifdef DOXYGEN
    129138      void push(const Item &i, const Prio &p) {}
     139#else
     140      void push(const Item&, const Prio&) {}
     141#endif     
    130142
    131143      /// \brief Return the item having minimum priority.
    … …  
    133145      /// This function returns the item having minimum priority.
    134146      /// \pre The heap must be non-empty.
    135       Item top() const {}
     147      Item top() const { return Item(); }
    136148
    137149      /// \brief The minimum priority.
    … …  
    139151      /// This function returns the minimum priority.
    140152      /// \pre The heap must be non-empty.
    141       Prio prio() const {}
     153      Prio prio() const { return Prio(); }
    142154
    143155      /// \brief Remove the item having minimum priority.
    … …  
    153165      /// \param i The item to delete.
    154166      /// \pre \e i must be in the heap.
     167#ifdef DOXYGEN
    155168      void erase(const Item &i) {}
     169#else
     170      void erase(const Item&) {}
     171#endif     
    156172
    157173      /// \brief The priority of the given item.
    … …  
    160176      /// \param i The item.
    161177      /// \pre \e i must be in the heap.
     178#ifdef DOXYGEN
    162179      Prio operator[](const Item &i) const {}
     180#else
     181      Prio operator[](const Item&) const { return Prio(); }
     182#endif     
    163183
    164184      /// \brief Set the priority of an item or insert it, if it is
    … …  
    171191      /// \param i The item.
    172192      /// \param p The priority.
     193#ifdef DOXYGEN
    173194      void set(const Item &i, const Prio &p) {}
     195#else
     196      void set(const Item&, const Prio&) {}
     197#endif     
    174198
    175199      /// \brief Decrease the priority of an item to the given value.
    … …  
    179203      /// \param p The priority.
    180204      /// \pre \e i must be stored in the heap with priority at least \e p.
     205#ifdef DOXYGEN
    181206      void decrease(const Item &i, const Prio &p) {}
     207#else
     208      void decrease(const Item&, const Prio&) {}
     209#endif     
    182210
    183211      /// \brief Increase the priority of an item to the given value.
    … …  
    187215      /// \param p The priority.
    188216      /// \pre \e i must be stored in the heap with priority at most \e p.
     217#ifdef DOXYGEN
    189218      void increase(const Item &i, const Prio &p) {}
     219#else
     220      void increase(const Item&, const Prio&) {}
     221#endif     
    190222
    191223      /// \brief Return the state of an item.
    … …  
    197229      /// to the heap again.
    198230      /// \param i The item.
     231#ifdef DOXYGEN
    199232      State state(const Item &i) const {}
     233#else
     234      State state(const Item&) const { return PRE_HEAP; }
     235#endif     
    200236
    201237      /// \brief Set the state of an item in the heap.
    … …  
    206242      /// \param i The item.
    207243      /// \param st The state. It should not be \c IN_HEAP.
     244#ifdef DOXYGEN
    208245      void state(const Item& i, State st) {}
     246#else
     247      void state(const Item&, State) {}
     248#endif     
    209249
    210250

  • lemon/dfs.h

    r788 r825  
    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.
    124129#ifdef DOXYGEN
    125130  template <typename GR,
    … …  
    888893  /// This class should only be used through the \ref dfs() function,
    889894  /// which makes it easier to use the algorithm.
     895  ///
     896  /// \tparam TR The traits class that defines various types used by the
     897  /// algorithm.
    890898  template<class TR>
    891899  class DfsWizard : public TR
    … …  
    12381246  /// does not observe the DFS events. If you want to observe the DFS
    12391247  /// events, you should implement your own visitor class.
    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.
     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.
    12451253#ifdef DOXYGEN
    12461254  template <typename GR, typename VS, typename TR>

  • lemon/dijkstra.h

    r788 r825  
    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.
    195200#ifdef DOXYGEN
    196201  template <typename GR, typename LEN, typename TR>
    … …  
    10931098  /// This class should only be used through the \ref dijkstra() function,
    10941099  /// which makes it easier to use the algorithm.
     1100  ///
     1101  /// \tparam TR The traits class that defines various types used by the
     1102  /// algorithm.
    10951103  template<class TR>
    10961104  class DijkstraWizard : public TR

  • lemon/glpk.h

    r746 r833  
    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
    32 typedef struct { double _opaque_prob; } glp_prob;
    33 /* LP/MIP problem object */
    34 #endif
    35 
    3628namespace lemon {
    3729
     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  }
    3850
    3951  /// \brief Base interface for the GLPK LP and MIP solver
    … …  
    4456  protected:
    4557
    46     typedef glp_prob LPX;
    47     glp_prob* lp;
     58    _solver_bits::VoidPtr lp;
    4859
    4960    GlpkBase();
    … …  
    124135
    125136    ///Pointer to the underlying GLPK data structure.
    126     LPX *lpx() {return lp;}
     137    _solver_bits::VoidPtr lpx() {return lp;}
    127138    ///Const pointer to the underlying GLPK data structure.
    128     const LPX *lpx() const {return lp;}
     139    _solver_bits::VoidPtr lpx() const {return lp;}
    129140
    130141    ///Returns the constraint identifier understood by GLPK.

  • lemon/hartmann_orlin.h

    r795 r825  
    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.
    109114#ifdef DOXYGEN
    110115  template <typename GR, typename LEN, typename TR>
    … …  
    128133    ///
    129134    /// The large value type used for internal computations.
    130     /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
    131     /// it is \c long \c long if the \c Value type is integer,
     135    /// By default, it is \c long \c long if the \c Value type is integer,
    132136    /// otherwise it is \c double.
    133137    typedef typename TR::LargeValue LargeValue;

  • lemon/howard.h

    r771 r825  
    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.
    109114#ifdef DOXYGEN
    110115  template <typename GR, typename LEN, typename TR>
    … …  
    128133    ///
    129134    /// The large value type used for internal computations.
    130     /// Using the \ref HowardDefaultTraits "default traits class",
    131     /// it is \c long \c long if the \c Value type is integer,
     135    /// By default, it is \c long \c long if the \c Value type is integer,
    132136    /// otherwise it is \c double.
    133137    typedef typename TR::LargeValue LargeValue;

  • lemon/karp.h

    r772 r825  
    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.
    107112#ifdef DOXYGEN
    108113  template <typename GR, typename LEN, typename TR>
    … …  
    126131    ///
    127132    /// The large value type used for internal computations.
    128     /// Using the \ref KarpDefaultTraits "default traits class",
    129     /// it is \c long \c long if the \c Value type is integer,
     133    /// By default, it is \c long \c long if the \c Value type is integer,
    130134    /// otherwise it is \c double.
    131135    typedef typename TR::LargeValue LargeValue;

  • lemon/min_cost_arborescence.h

    r713 r825  
    113113  /// it is necessary. The default map type is \ref
    114114  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    115   /// \param TR Traits class to set various data types used
    116   /// by the algorithm. The default traits class is
    117   /// \ref MinCostArborescenceDefaultTraits
     115  /// \tparam TR The traits class that defines various types used by the
     116  /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits
    118117  /// "MinCostArborescenceDefaultTraits<GR, CM>".
     118  /// In most cases, this parameter should not be set directly,
     119  /// consider to use the named template parameters instead.
    119120#ifndef DOXYGEN
    120121  template <typename GR,
    … …  
    123124              MinCostArborescenceDefaultTraits<GR, CM> >
    124125#else
    125   template <typename GR, typename CM, typedef TR>
     126  template <typename GR, typename CM, typename TR>
    126127#endif
    127128  class MinCostArborescence {

  • lemon/network_simplex.h

    r788 r830  
    4444  /// \ref amo93networkflows, \ref dantzig63linearprog,
    4545  /// \ref kellyoneill91netsimplex.
    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.
     46  /// This algorithm is a highly efficient specialized version of the
     47  /// linear programming simplex method directly for the minimum cost
     48  /// flow problem.
    4949  ///
    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
     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
    5353  /// constraints. For more information, see \ref SupplyType.
    5454  ///
    … …  
    5959  ///
    6060  /// \tparam GR The digraph type the algorithm runs on.
    61   /// \tparam V The value type used for flow amounts, capacity bounds
     61  /// \tparam V The number type used for flow amounts, capacity bounds
    6262  /// and supply values in the algorithm. By default, it is \c int.
    63   /// \tparam C The value type used for costs and potentials in the
     63  /// \tparam C The number type used for costs and potentials in the
    6464  /// algorithm. By default, it is the same as \c V.
    6565  ///
    66   /// \warning Both value types must be signed and all input data must
     66  /// \warning Both number 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 according to our benchmark tests.
     129    /// test inputs.
    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<bool> BoolVector;
     167    typedef std::vector<char> CharVector;
    168168    typedef std::vector<Value> ValueVector;
    169169    typedef std::vector<Cost> CostVector;
    … …  
    195195    IntVector _source;
    196196    IntVector _target;
     197    bool _arc_mixing;
    197198
    198199    // Node and arc data
    … …  
    213214    IntVector _last_succ;
    214215    IntVector _dirty_revs;
    215     BoolVector _forward;
    216     IntVector _state;
     216    CharVector _forward;
     217    CharVector _state;
    217218    int _root;
    218219
    … …  
    222223    int stem, par_stem, new_stem;
    223224    Value delta;
     225   
     226    const Value MAX;
    224227
    225228  public:
    … …  
    243246      const IntVector  &_target;
    244247      const CostVector &_cost;
    245       const IntVector &_state;
     248      const CharVector &_state;
    246249      const CostVector &_pi;
    247250      int &_in_arc;
    … …  
    295298      const IntVector  &_target;
    296299      const CostVector &_cost;
    297       const IntVector &_state;
     300      const CharVector &_state;
    298301      const CostVector &_pi;
    299302      int &_in_arc;
    … …  
    334337      const IntVector  &_target;
    335338      const CostVector &_cost;
    336       const IntVector &_state;
     339      const CharVector &_state;
    337340      const CostVector &_pi;
    338341      int &_in_arc;
    … …  
    407410      const IntVector  &_target;
    408411      const CostVector &_cost;
    409       const IntVector &_state;
     412      const CharVector &_state;
    410413      const CostVector &_pi;
    411414      int &_in_arc;
    … …  
    510513      const IntVector  &_target;
    511514      const CostVector &_cost;
    512       const IntVector &_state;
     515      const CharVector &_state;
    513516      const CostVector &_pi;
    514517      int &_in_arc;
    … …  
    632635    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    633636      _graph(graph), _node_id(graph), _arc_id(graph),
     637      _arc_mixing(arc_mixing),
     638      MAX(std::numeric_limits<Value>::max()),
    634639      INF(std::numeric_limits<Value>::has_infinity ?
    635           std::numeric_limits<Value>::infinity() :
    636           std::numeric_limits<Value>::max())
     640          std::numeric_limits<Value>::infinity() : MAX)
    637641    {
    638       // Check the value types
     642      // Check the number types
    639643      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
    640644        "The flow type of NetworkSimplex must be signed");
    … …  
    642646        "The cost type of NetworkSimplex must be signed");
    643647       
    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
     648      // Reset data structures
    696649      reset();
    697650    }
    … …  
    728681    /// If it is not used before calling \ref run(), the upper bounds
    729682    /// will be set to \ref INF on all arcs (i.e. the flow value will be
    730     /// unbounded from above on each arc).
     683    /// unbounded from above).
    731684    ///
    732685    /// \param map An arc map storing the upper bounds.
    … …  
    841794    /// \endcode
    842795    ///
    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.
     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.
    849802    ///
    850803    /// \param pivot_rule The pivot rule that will be used during the
    … …  
    860813    ///
    861814    /// \see ProblemType, PivotRule
     815    /// \see resetParams(), reset()
    862816    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
    863817      if (!init()) return INFEASIBLE;
    … …  
    871825    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    872826    ///
    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.
     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.
    878833    ///
    879834    /// For example,
    … …  
    885840    ///     .supplyMap(sup).run();
    886841    ///
    887     ///   // Run again with modified cost map (reset() is not called,
     842    ///   // Run again with modified cost map (resetParams() is not called,
    888843    ///   // so only the cost map have to be set again)
    889844    ///   cost[e] += 100;
    890845    ///   ns.costMap(cost).run();
    891846    ///
    892     ///   // Run again from scratch using reset()
     847    ///   // Run again from scratch using resetParams()
    893848    ///   // (the lower bounds will be set to zero on all arcs)
    894     ///   ns.reset();
     849    ///   ns.resetParams();
    895850    ///   ns.upperMap(capacity).costMap(cost)
    896851    ///     .supplyMap(sup).run();
    … …  
    898853    ///
    899854    /// \return <tt>(*this)</tt>
    900     NetworkSimplex& reset() {
     855    ///
     856    /// \see reset(), run()
     857    NetworkSimplex& resetParams() {
    901858      for (int i = 0; i != _node_num; ++i) {
    902859        _supply[i] = 0;
    … …  
    912869    }
    913870
     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   
    914948    /// @}
    915949
    … …  
    10211055          Value c = _lower[i];
    10221056          if (c >= 0) {
    1023             _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
     1057            _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
    10241058          } else {
    1025             _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
     1059            _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
    10261060          }
    10271061          _supply[_source[i]] -= c;
    … …  
    12151249        e = _pred[u];
    12161250        d = _forward[u] ?
    1217           _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
     1251          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
    12181252        if (d < delta) {
    12191253          delta = d;
    … …  
    12261260        e = _pred[u];
    12271261        d = _forward[u] ?
    1228           (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
     1262          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
    12291263        if (d <= delta) {
    12301264          delta = d;
    … …  
    14251459        findJoinNode();
    14261460        bool change = findLeavingArc();
    1427         if (delta >= INF) return UNBOUNDED;
     1461        if (delta >= MAX) return UNBOUNDED;
    14281462        changeFlow(change);
    14291463        if (change) {

  • lemon/planarity.h

    r798 r828  
    519519  ///
    520520  /// This function implements the Boyer-Myrvold algorithm for
    521   /// planarity checking of an undirected graph. It is a simplified
     521  /// planarity checking of an undirected simple graph. It is a simplified
    522522  /// version of the PlanarEmbedding algorithm class because neither
    523   /// the embedding nor the kuratowski subdivisons are not computed.
     523  /// the embedding nor the Kuratowski subdivisons are 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 graph. The planar embedding is an
     535  /// embedding of an undirected simple 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 \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.
     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.
    541541  ///
    542542  /// The current implementation calculates either an embedding or a
    543   /// Kuratowski subdivision. The running time of the algorithm is
    544   /// \f$ O(n) \f$.
     543  /// Kuratowski subdivision. The running time of the algorithm is O(n).
     544  ///
     545  /// \see PlanarDrawing, checkPlanarity()
    545546  template <typename Graph>
    546547  class PlanarEmbedding {
    … …  
    592593  public:
    593594
    594     /// \brief The map for store of embedding
     595    /// \brief The map type for storing the embedding
     596    ///
     597    /// The map type for storing the embedding.
     598    /// \see embeddingMap()
    595599    typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
    596600
    597601    /// \brief Constructor
    598602    ///
    599     /// \note The graph should be simple, i.e. parallel and loop arc
    600     /// free.
     603    /// Constructor.
     604    /// \pre The graph must be simple, i.e. it should not
     605    /// contain parallel or loop arcs.
    601606    PlanarEmbedding(const Graph& graph)
    602607      : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
    603608
    604     /// \brief Runs the algorithm.
     609    /// \brief Run the algorithm.
    605610    ///
    606     /// Runs the algorithm.
    607     /// \param kuratowski If the parameter is false, then the
     611    /// This function runs the algorithm.
     612    /// \param kuratowski If this parameter is set to \c false, then the
    608613    /// algorithm does not compute a Kuratowski subdivision.
    609     ///\return %True when the graph is planar.
     614    /// \return \c true if the graph is planar.
    610615    bool run(bool kuratowski = true) {
    611616      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
    … …  
    700705    }
    701706
    702     /// \brief Gives back the successor of an arc
     707    /// \brief Give back the successor of an arc
    703708    ///
    704     /// Gives back the successor of an arc. This function makes
     709    /// This function gives back the successor of an arc. It makes
    705710    /// possible to query the cyclic order of the outgoing arcs from
    706711    /// a node.
    … …  
    709714    }
    710715
    711     /// \brief Gives back the calculated embedding map
     716    /// \brief Give back the calculated embedding map
    712717    ///
    713     /// The returned map contains the successor of each arc in the
    714     /// graph.
     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.
    715721    const EmbeddingMap& embeddingMap() const {
    716722      return _embedding;
    717723    }
    718724
    719     /// \brief Gives back true if the undirected arc is in the
    720     /// kuratowski subdivision
     725    /// \brief Give back \c true if the given edge is in the Kuratowski
     726    /// subdivision
    721727    ///
    722     /// Gives back true if the undirected arc is in the kuratowski
    723     /// subdivision
    724     /// \note The \c run() had to be called with true value.
    725     bool kuratowski(const Edge& edge) {
     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 {
    726733      return _kuratowski[edge];
    727734    }
    … …  
    20602067  ///
    20612068  /// The planar drawing algorithm calculates positions for the nodes
    2062   /// in the plane which coordinates satisfy that if the arcs are
    2063   /// represented with straight lines then they will not intersect
     2069  /// in the plane. These coordinates satisfy that if the edges are
     2070  /// represented with straight lines, then they will not intersect
    20642071  /// each other.
    20652072  ///
    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.
     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.
    20682075  /// The time complexity of the algorithm is O(n).
     2076  ///
     2077  /// \see PlanarEmbedding
    20692078  template <typename Graph>
    20702079  class PlanarDrawing {
    … …  
    20732082    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    20742083
    2075     /// \brief The point type for store coordinates
     2084    /// \brief The point type for storing coordinates
    20762085    typedef dim2::Point<int> Point;
    2077     /// \brief The map type for store coordinates
     2086    /// \brief The map type for storing the coordinates of the nodes
    20782087    typedef typename Graph::template NodeMap<Point> PointMap;
    20792088
    … …  
    20822091    ///
    20832092    /// Constructor
    2084     /// \pre The graph should be simple, i.e. loop and parallel arc free.
     2093    /// \pre The graph must be simple, i.e. it should not
     2094    /// contain parallel or loop arcs.
    20852095    PlanarDrawing(const Graph& graph)
    20862096      : _graph(graph), _point_map(graph) {}
    … …  
    23672377  public:
    23682378
    2369     /// \brief Calculates the node positions
     2379    /// \brief Calculate the node positions
    23702380    ///
    2371     /// This function calculates the node positions.
    2372     /// \return %True if the graph is planar.
     2381    /// This function calculates the node positions on the plane.
     2382    /// \return \c true if the graph is planar.
    23732383    bool run() {
    23742384      PlanarEmbedding<Graph> pe(_graph);
    … …  
    23792389    }
    23802390
    2381     /// \brief Calculates the node positions according to a
     2391    /// \brief Calculate the node positions according to a
    23822392    /// combinatorical embedding
    23832393    ///
    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.
     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.
    23872398    template <typename EmbeddingMap>
    23882399    void run(const EmbeddingMap& embedding) {
    … …  
    24242435    /// \brief The coordinate of the given node
    24252436    ///
    2426     /// The coordinate of the given node.
     2437    /// This function returns the coordinate of the given node.
    24272438    Point operator[](const Node& node) const {
    24282439      return _point_map[node];
    24292440    }
    24302441
    2431     /// \brief Returns the grid embedding in a \e NodeMap.
     2442    /// \brief Return the grid embedding in a node map
    24322443    ///
    2433     /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
     2444    /// This function returns the grid embedding in a node map of
     2445    /// \c dim2::Point<int> coordinates.
    24342446    const PointMap& coords() const {
    24352447      return _point_map;
    … …  
    24712483  ///
    24722484  /// The graph coloring problem is the coloring of the graph nodes
    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
     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
    24762488  /// time algorithm for four coloring, but it could not be used to
    2477   /// implement efficient algorithm. The five and six coloring can be
    2478   /// made in linear time, but in this class the five coloring has
     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
    24792491  /// quadratic worst case time complexity. The two coloring (if
    24802492  /// possible) is solvable with a graph search algorithm and it is
    24812493  /// implemented in \ref bipartitePartitions() function in LEMON. To
    2482   /// decide whether the planar graph is three colorable is
    2483   /// NP-complete.
     2494  /// decide whether a planar graph is three colorable is NP-complete.
    24842495  ///
    24852496  /// This class contains member functions for calculate colorings
    24862497  /// with five and six colors. The six coloring algorithm is a simple
    24872498  /// greedy coloring on the backward minimum outgoing order of nodes.
    2488   /// This order can be computed as in each phase the node with least
    2489   /// outgoing arcs to unprocessed nodes is chosen. This order
     2499  /// This order can be computed by selecting the node with least
     2500  /// outgoing arcs to unprocessed nodes in each phase. This order
    24902501  /// guarantees that when a node is chosen for coloring it has at
    24912502  /// most five already colored adjacents. The five coloring algorithm
    … …  
    25002511    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    25012512
    2502     /// \brief The map type for store color indexes
     2513    /// \brief The map type for storing color indices
    25032514    typedef typename Graph::template NodeMap<int> IndexMap;
    2504     /// \brief The map type for store colors
     2515    /// \brief The map type for storing colors
     2516    ///
     2517    /// The map type for storing colors.
     2518    /// \see Palette, Color
    25052519    typedef ComposeMap<Palette, IndexMap> ColorMap;
    25062520
    25072521    /// \brief Constructor
    25082522    ///
    2509     /// Constructor
    2510     /// \pre The graph should be simple, i.e. loop and parallel arc free.
     2523    /// Constructor.
     2524    /// \pre The graph must be simple, i.e. it should not
     2525    /// contain parallel or loop arcs.
    25112526    PlanarColoring(const Graph& graph)
    25122527      : _graph(graph), _color_map(graph), _palette(0) {
    … …  
    25192534    }
    25202535
    2521     /// \brief Returns the \e NodeMap of color indexes
     2536    /// \brief Return the node map of color indices
    25222537    ///
    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.
     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.
    25252540    IndexMap colorIndexMap() const {
    25262541      return _color_map;
    25272542    }
    25282543
    2529     /// \brief Returns the \e NodeMap of colors
     2544    /// \brief Return the node map of colors
    25302545    ///
    2531     /// Returns the \e NodeMap of colors. The values are five or six
    2532     /// distinct \ref lemon::Color "colors".
     2546    /// This function returns the node map of colors. The values are among
     2547    /// five or six distinct \ref lemon::Color "colors".
    25332548    ColorMap colorMap() const {
    25342549      return composeMap(_palette, _color_map);
    25352550    }
    25362551
    2537     /// \brief Returns the color index of the node
     2552    /// \brief Return the color index of the node
    25382553    ///
    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.
     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.
    25412556    int colorIndex(const Node& node) const {
    25422557      return _color_map[node];
    25432558    }
    25442559
    2545     /// \brief Returns the color of the node
     2560    /// \brief Return the color of the node
    25462561    ///
    2547     /// Returns the color of the node. The values are five or six
    2548     /// distinct \ref lemon::Color "colors".
     2562    /// This function returns the color of the given node. The value is among
     2563    /// five or six distinct \ref lemon::Color "colors".
    25492564    Color color(const Node& node) const {
    25502565      return _palette[_color_map[node]];
    … …  
    25522567
    25532568
    2554     /// \brief Calculates a coloring with at most six colors
     2569    /// \brief Calculate a coloring with at most six colors
    25552570    ///
    25562571    /// This function calculates a coloring with at most six colors. The time
    25572572    /// complexity of this variant is linear in the size of the graph.
    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.
     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.
    25622577    bool runSixColoring() {
    25632578
    … …  
    26612676  public:
    26622677
    2663     /// \brief Calculates a coloring with at most five colors
     2678    /// \brief Calculate a coloring with at most five colors
    26642679    ///
    26652680    /// This function calculates a coloring with at most five
    26662681    /// colors. The worst case time complexity of this variant is
    26672682    /// 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.
    26682686    template <typename EmbeddingMap>
    26692687    void runFiveColoring(const EmbeddingMap& embedding) {
    … …  
    27122730    }
    27132731
    2714     /// \brief Calculates a coloring with at most five colors
     2732    /// \brief Calculate a coloring with at most five colors
    27152733    ///
    27162734    /// This function calculates a coloring with at most five
    27172735    /// colors. The worst case time complexity of this variant is
    27182736    /// quadratic in the size of the graph.
    2719     /// \return %True when the graph is planar.
     2737    /// \return \c true if the graph is planar.
    27202738    bool runFiveColoring() {
    27212739      PlanarEmbedding<Graph> pe(_graph);

  • lemon/preflow.h

    r788 r825  
    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  ///
    116119  /// \tparam GR The type of the digraph the algorithm runs on.
    117120  /// \tparam CAP The type of the capacity map. The default map
    118121  /// 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.
    119127#ifdef DOXYGEN
    120128  template <typename GR, typename CAP, typename TR>

  • lemon/unionfind.h

    r786 r800  
    740740    void clear() {
    741741      items.clear();
    742       classes.clear;
     742      classes.clear();
    743743      firstClass = firstFreeClass = firstFreeItem = -1;
    744744    }

  • test/min_cost_flow_test.cc

    r669 r830  
    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>
    2730
    2831#include <lemon/concepts/digraph.h>
     32#include <lemon/concepts/heap.h>
    2933#include <lemon/concept_check.h>
    3034
    … …  
    3337using namespace lemon;
    3438
     39// Test networks
    3540char test_lgf[] =
    3641  "@nodes\n"
    … …  
    7782  "target 12\n";
    7883
     84char 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 
     106char 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
     117typedef ListDigraph Digraph;
     118DIGRAPH_TYPEDEFS(ListDigraph);
     119
     120Digraph gr;
     121Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
     122Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
     123ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
     124Node v, w;
     125
     126Digraph neg1_gr;
     127Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);
     128ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);
     129Digraph::NodeMap<int> neg1_s(neg1_gr);
     130
     131Digraph neg2_gr;
     132Digraph::ArcMap<int> neg2_c(neg2_gr);
     133ConstMap<Arc, int> neg2_l(0), neg2_u(1000);
     134Digraph::NodeMap<int> neg2_s(neg2_gr);
     135
    79136
    80137enum SupplyType {
    … …  
    83140  LEQ
    84141};
     142
    85143
    86144// Check the interface of an MCF algorithm
    … …  
    100158      const MCF& const_mcf = mcf;
    101159
    102       b = mcf.reset()
     160      b = mcf.reset().resetParams()
    103161             .lowerMap(me.lower)
    104162             .upperMap(me.upper)
    … …  
    269327}
    270328
     329template < typename MCF, typename Param >
     330void 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
     400template < typename MCF, typename Param >
     401void 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
    271419int main()
    272420{
    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 
     421  // Read the test networks
    295422  std::istringstream input(test_lgf);
    296423  DigraphReader<Digraph>(gr, input)
    … …  
    310437    .run();
    311438 
    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
    364   {
    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
    433   {
    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");
     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
     454  {
     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
     465  {
     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");
    447539  }
    448540
Note: See TracChangeset for help on using the changeset viewer.