COIN-OR::LEMON - Graph Library

Changes in / [848:e05b2b48515a:849:1b8db382910c] in lemon-1.2


Ignore:
Files:
1 added
28 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"'.
  • demo/arg_parser_demo.cc

    r440 r842  
    6666    .other("...");
    6767
     68  // Throw an exception when problems occurs. The default behavior is to
     69  // exit(1) on these cases, but this makes Valgrind falsely warn
     70  // about memory leaks.
     71  ap.throwOnProblems();
     72 
    6873  // Perform the parsing process
    6974  // (in case of any error it terminates the program)
    70   ap.parse();
     75  // The try {} construct is necessary only if the ap.trowOnProblems()
     76  // setting is in use.
     77  try {
     78    ap.parse();
     79  } catch (ArgParserException &) { return 1; }
    7180
    7281  // Check each option if it has been given and print its value
  • 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
  • lemon/arg_parser.cc

    r440 r842  
    2121namespace lemon {
    2222
     23  void ArgParser::_terminate(ArgParserException::Reason reason) const
     24  {
     25    if(_exit_on_problems)
     26      exit(1);
     27    else throw(ArgParserException(reason));
     28  }
     29 
     30 
    2331  void ArgParser::_showHelp(void *p)
    2432  {
    2533    (static_cast<ArgParser*>(p))->showHelp();
    26     exit(1);
     34    (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
    2735  }
    2836
    2937  ArgParser::ArgParser(int argc, const char * const *argv)
    30     :_argc(argc), _argv(argv), _command_name(argv[0]) {
     38    :_argc(argc), _argv(argv), _command_name(argv[0]),
     39    _exit_on_problems(true) {
    3140    funcOption("-help","Print a short help message",_showHelp,this);
    3241    synonym("help","-help");
     
    343352        i!=_others_help.end();++i) showHelp(i);
    344353    for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
    345     exit(1);
     354    _terminate(ArgParserException::HELP);
    346355  }
    347356
     
    352361    std::cerr << "\nType '" << _command_name <<
    353362      " --help' to obtain a short summary on the usage.\n\n";
    354     exit(1);
     363    _terminate(ArgParserException::UNKNOWN_OPT);
    355364  }
    356365
     
    415424      std::cerr << "\nType '" << _command_name <<
    416425        " --help' to obtain a short summary on the usage.\n\n";
    417       exit(1);
     426      _terminate(ArgParserException::INVALID_OPT);
    418427    }
    419428  }
  • lemon/arg_parser.h

    r440 r842  
    3535namespace lemon {
    3636
     37  ///Exception used by ArgParser
     38  class ArgParserException : public Exception {
     39  public:
     40    enum Reason {
     41      HELP,         /// <tt>--help</tt> option was given
     42      UNKNOWN_OPT,  /// Unknown option was given
     43      INVALID_OPT   /// Invalid combination of options
     44    };
     45   
     46  private:
     47    Reason _reason;
     48   
     49  public:
     50    ///Constructor
     51    ArgParserException(Reason r) throw() : _reason(r) {}
     52    ///Virtual destructor
     53    virtual ~ArgParserException() throw() {}
     54    ///A short description of the exception
     55    virtual const char* what() const throw() {
     56      switch(_reason)
     57        {
     58        case HELP:
     59          return "lemon::ArgParseException: ask for help";
     60          break;
     61        case UNKNOWN_OPT:
     62          return "lemon::ArgParseException: unknown option";
     63          break;
     64        case INVALID_OPT:
     65          return "lemon::ArgParseException: invalid combination of options";
     66          break;
     67        }
     68      return "";
     69    }
     70    ///Return the reason for the failure
     71    Reason reason() const {return _reason; }
     72  };
     73
     74
    3775  ///Command line arguments parser
    3876
     
    104142    std::string _command_name;
    105143
    106 
     144   
    107145  private:
    108146    //Bind a function to an option.
     
    116154                    const std::string &help,
    117155                    void (*func)(void *),void *data);
     156
     157    bool _exit_on_problems;
     158   
     159    void _terminate(ArgParserException::Reason reason) const;
    118160
    119161  public:
     
    381423    const std::vector<std::string> &files() const { return _file_args; }
    382424
     425    ///Throw instead of exit in case of problems
     426    void throwOnProblems()
     427    {
     428      _exit_on_problems=false;
     429    }
    383430  };
    384431}
  • lemon/bellman_ford.h

    r804 r844  
    2929#include <lemon/error.h>
    3030#include <lemon/maps.h>
     31#include <lemon/tolerance.h>
    3132#include <lemon/path.h>
    3233
     
    3536namespace lemon {
    3637
    37   /// \brief Default OperationTraits for the BellmanFord algorithm class.
     38  /// \brief Default operation traits for the BellmanFord algorithm class.
    3839  /// 
    3940  /// This operation traits class defines all computational operations
     
    4243  /// If the numeric type does not have infinity value, then the maximum
    4344  /// value is used as extremal infinity value.
     45  ///
     46  /// \see BellmanFordToleranceOperationTraits
    4447  template <
    4548    typename V,
    4649    bool has_inf = std::numeric_limits<V>::has_infinity>
    4750  struct BellmanFordDefaultOperationTraits {
    48     /// \e
     51    /// \brief Value type for the algorithm.
    4952    typedef V Value;
    5053    /// \brief Gives back the zero value of the type.
     
    8588  };
    8689 
     90  /// \brief Operation traits for the BellmanFord algorithm class
     91  /// using tolerance.
     92  ///
     93  /// This operation traits class defines all computational operations
     94  /// and constants that are used in the Bellman-Ford algorithm.
     95  /// The only difference between this implementation and
     96  /// \ref BellmanFordDefaultOperationTraits is that this class uses
     97  /// the \ref Tolerance "tolerance technique" in its \ref less()
     98  /// function.
     99  ///
     100  /// \tparam V The value type.
     101  /// \tparam eps The epsilon value for the \ref less() function.
     102  /// By default, it is the epsilon value used by \ref Tolerance
     103  /// "Tolerance<V>".
     104  ///
     105  /// \see BellmanFordDefaultOperationTraits
     106#ifdef DOXYGEN
     107  template <typename V, V eps>
     108#else
     109  template <
     110    typename V,
     111    V eps = Tolerance<V>::def_epsilon>
     112#endif
     113  struct BellmanFordToleranceOperationTraits {
     114    /// \brief Value type for the algorithm.
     115    typedef V Value;
     116    /// \brief Gives back the zero value of the type.
     117    static Value zero() {
     118      return static_cast<Value>(0);
     119    }
     120    /// \brief Gives back the positive infinity value of the type.
     121    static Value infinity() {
     122      return std::numeric_limits<Value>::infinity();
     123    }
     124    /// \brief Gives back the sum of the given two elements.
     125    static Value plus(const Value& left, const Value& right) {
     126      return left + right;
     127    }
     128    /// \brief Gives back \c true only if the first value is less than
     129    /// the second.
     130    static bool less(const Value& left, const Value& right) {
     131      return left + eps < right;
     132    }
     133  };
     134
    87135  /// \brief Default traits class of BellmanFord class.
    88136  ///
     
    108156    /// It defines the used operations and the infinity value for the
    109157    /// given \c Value type.
    110     /// \see BellmanFordDefaultOperationTraits
     158    /// \see BellmanFordDefaultOperationTraits,
     159    /// BellmanFordToleranceOperationTraits
    111160    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    112161 
     
    172221  /// the lengths of the arcs. The default map type is
    173222  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     223  /// \tparam TR The traits class that defines various types used by the
     224  /// algorithm. By default, it is \ref BellmanFordDefaultTraits
     225  /// "BellmanFordDefaultTraits<GR, LEN>".
     226  /// In most cases, this parameter should not be set directly,
     227  /// consider to use the named template parameters instead.
    174228#ifdef DOXYGEN
    175229  template <typename GR, typename LEN, typename TR>
     
    833887    /// It defines the used operations and the infinity value for the
    834888    /// given \c Value type.
    835     /// \see BellmanFordDefaultOperationTraits
     889    /// \see BellmanFordDefaultOperationTraits,
     890    /// BellmanFordToleranceOperationTraits
    836891    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    837892
     
    934989  /// This class should only be used through the \ref bellmanFord()
    935990  /// function, which makes it easier to use the algorithm.
     991  ///
     992  /// \tparam TR The traits class that defines various types used by the
     993  /// algorithm.
    936994  template<class TR>
    937995  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/capacity_scaling.h

    r821 r840  
    7878  /// \tparam GR The digraph type the algorithm runs on.
    7979  /// \tparam V The number type used for flow amounts, capacity bounds
    80   /// and supply values in the algorithm. By default it is \c int.
     80  /// and supply values in the algorithm. By default, it is \c int.
    8181  /// \tparam C The number type used for costs and potentials in the
    82   /// algorithm. By default it is the same as \c V.
     82  /// algorithm. By default, it is the same as \c V.
     83  /// \tparam TR The traits class that defines various types used by the
     84  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
     85  /// "CapacityScalingDefaultTraits<GR, V, C>".
     86  /// In most cases, this parameter should not be set directly,
     87  /// consider to use the named template parameters instead.
    8388  ///
    8489  /// \warning Both number types must be signed and all input data must
     
    135140
    136141    typedef std::vector<int> IntVector;
    137     typedef std::vector<char> BoolVector;
    138142    typedef std::vector<Value> ValueVector;
    139143    typedef std::vector<Cost> CostVector;
     144    typedef std::vector<char> BoolVector;
     145    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    140146
    141147  private:
     
    315321        "The cost type of CapacityScaling must be signed");
    316322
     323      // Reset data structures
     324      reset();
     325    }
     326
     327    /// \name Parameters
     328    /// The parameters of the algorithm can be specified using these
     329    /// functions.
     330
     331    /// @{
     332
     333    /// \brief Set the lower bounds on the arcs.
     334    ///
     335    /// This function sets the lower bounds on the arcs.
     336    /// If it is not used before calling \ref run(), the lower bounds
     337    /// will be set to zero on all arcs.
     338    ///
     339    /// \param map An arc map storing the lower bounds.
     340    /// Its \c Value type must be convertible to the \c Value type
     341    /// of the algorithm.
     342    ///
     343    /// \return <tt>(*this)</tt>
     344    template <typename LowerMap>
     345    CapacityScaling& lowerMap(const LowerMap& map) {
     346      _have_lower = true;
     347      for (ArcIt a(_graph); a != INVALID; ++a) {
     348        _lower[_arc_idf[a]] = map[a];
     349        _lower[_arc_idb[a]] = map[a];
     350      }
     351      return *this;
     352    }
     353
     354    /// \brief Set the upper bounds (capacities) on the arcs.
     355    ///
     356    /// This function sets the upper bounds (capacities) on the arcs.
     357    /// If it is not used before calling \ref run(), the upper bounds
     358    /// will be set to \ref INF on all arcs (i.e. the flow value will be
     359    /// unbounded from above).
     360    ///
     361    /// \param map An arc map storing the upper bounds.
     362    /// Its \c Value type must be convertible to the \c Value type
     363    /// of the algorithm.
     364    ///
     365    /// \return <tt>(*this)</tt>
     366    template<typename UpperMap>
     367    CapacityScaling& upperMap(const UpperMap& map) {
     368      for (ArcIt a(_graph); a != INVALID; ++a) {
     369        _upper[_arc_idf[a]] = map[a];
     370      }
     371      return *this;
     372    }
     373
     374    /// \brief Set the costs of the arcs.
     375    ///
     376    /// This function sets the costs of the arcs.
     377    /// If it is not used before calling \ref run(), the costs
     378    /// will be set to \c 1 on all arcs.
     379    ///
     380    /// \param map An arc map storing the costs.
     381    /// Its \c Value type must be convertible to the \c Cost type
     382    /// of the algorithm.
     383    ///
     384    /// \return <tt>(*this)</tt>
     385    template<typename CostMap>
     386    CapacityScaling& costMap(const CostMap& map) {
     387      for (ArcIt a(_graph); a != INVALID; ++a) {
     388        _cost[_arc_idf[a]] =  map[a];
     389        _cost[_arc_idb[a]] = -map[a];
     390      }
     391      return *this;
     392    }
     393
     394    /// \brief Set the supply values of the nodes.
     395    ///
     396    /// This function sets the supply values of the nodes.
     397    /// If neither this function nor \ref stSupply() is used before
     398    /// calling \ref run(), the supply of each node will be set to zero.
     399    ///
     400    /// \param map A node map storing the supply values.
     401    /// Its \c Value type must be convertible to the \c Value type
     402    /// of the algorithm.
     403    ///
     404    /// \return <tt>(*this)</tt>
     405    template<typename SupplyMap>
     406    CapacityScaling& supplyMap(const SupplyMap& map) {
     407      for (NodeIt n(_graph); n != INVALID; ++n) {
     408        _supply[_node_id[n]] = map[n];
     409      }
     410      return *this;
     411    }
     412
     413    /// \brief Set single source and target nodes and a supply value.
     414    ///
     415    /// This function sets a single source node and a single target node
     416    /// and the required flow value.
     417    /// If neither this function nor \ref supplyMap() is used before
     418    /// calling \ref run(), the supply of each node will be set to zero.
     419    ///
     420    /// Using this function has the same effect as using \ref supplyMap()
     421    /// with such a map in which \c k is assigned to \c s, \c -k is
     422    /// assigned to \c t and all other nodes have zero supply value.
     423    ///
     424    /// \param s The source node.
     425    /// \param t The target node.
     426    /// \param k The required amount of flow from node \c s to node \c t
     427    /// (i.e. the supply of \c s and the demand of \c t).
     428    ///
     429    /// \return <tt>(*this)</tt>
     430    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
     431      for (int i = 0; i != _node_num; ++i) {
     432        _supply[i] = 0;
     433      }
     434      _supply[_node_id[s]] =  k;
     435      _supply[_node_id[t]] = -k;
     436      return *this;
     437    }
     438   
     439    /// @}
     440
     441    /// \name Execution control
     442    /// The algorithm can be executed using \ref run().
     443
     444    /// @{
     445
     446    /// \brief Run the algorithm.
     447    ///
     448    /// This function runs the algorithm.
     449    /// The paramters can be specified using functions \ref lowerMap(),
     450    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     451    /// For example,
     452    /// \code
     453    ///   CapacityScaling<ListDigraph> cs(graph);
     454    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
     455    ///     .supplyMap(sup).run();
     456    /// \endcode
     457    ///
     458    /// This function can be called more than once. All the given parameters
     459    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     460    /// is used, thus only the modified parameters have to be set again.
     461    /// If the underlying digraph was also modified after the construction
     462    /// of the class (or the last \ref reset() call), then the \ref reset()
     463    /// function must be called.
     464    ///
     465    /// \param factor The capacity scaling factor. It must be larger than
     466    /// one to use scaling. If it is less or equal to one, then scaling
     467    /// will be disabled.
     468    ///
     469    /// \return \c INFEASIBLE if no feasible flow exists,
     470    /// \n \c OPTIMAL if the problem has optimal solution
     471    /// (i.e. it is feasible and bounded), and the algorithm has found
     472    /// optimal flow and node potentials (primal and dual solutions),
     473    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
     474    /// and infinite upper bound. It means that the objective function
     475    /// is unbounded on that arc, however, note that it could actually be
     476    /// bounded over the feasible flows, but this algroithm cannot handle
     477    /// these cases.
     478    ///
     479    /// \see ProblemType
     480    /// \see resetParams(), reset()
     481    ProblemType run(int factor = 4) {
     482      _factor = factor;
     483      ProblemType pt = init();
     484      if (pt != OPTIMAL) return pt;
     485      return start();
     486    }
     487
     488    /// \brief Reset all the parameters that have been given before.
     489    ///
     490    /// This function resets all the paramaters that have been given
     491    /// before using functions \ref lowerMap(), \ref upperMap(),
     492    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
     493    ///
     494    /// It is useful for multiple \ref run() calls. Basically, all the given
     495    /// parameters are kept for the next \ref run() call, unless
     496    /// \ref resetParams() or \ref reset() is used.
     497    /// If the underlying digraph was also modified after the construction
     498    /// of the class or the last \ref reset() call, then the \ref reset()
     499    /// function must be used, otherwise \ref resetParams() is sufficient.
     500    ///
     501    /// For example,
     502    /// \code
     503    ///   CapacityScaling<ListDigraph> cs(graph);
     504    ///
     505    ///   // First run
     506    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
     507    ///     .supplyMap(sup).run();
     508    ///
     509    ///   // Run again with modified cost map (resetParams() is not called,
     510    ///   // so only the cost map have to be set again)
     511    ///   cost[e] += 100;
     512    ///   cs.costMap(cost).run();
     513    ///
     514    ///   // Run again from scratch using resetParams()
     515    ///   // (the lower bounds will be set to zero on all arcs)
     516    ///   cs.resetParams();
     517    ///   cs.upperMap(capacity).costMap(cost)
     518    ///     .supplyMap(sup).run();
     519    /// \endcode
     520    ///
     521    /// \return <tt>(*this)</tt>
     522    ///
     523    /// \see reset(), run()
     524    CapacityScaling& resetParams() {
     525      for (int i = 0; i != _node_num; ++i) {
     526        _supply[i] = 0;
     527      }
     528      for (int j = 0; j != _res_arc_num; ++j) {
     529        _lower[j] = 0;
     530        _upper[j] = INF;
     531        _cost[j] = _forward[j] ? 1 : -1;
     532      }
     533      _have_lower = false;
     534      return *this;
     535    }
     536
     537    /// \brief Reset the internal data structures and all the parameters
     538    /// that have been given before.
     539    ///
     540    /// This function resets the internal data structures and all the
     541    /// paramaters that have been given before using functions \ref lowerMap(),
     542    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     543    ///
     544    /// It is useful for multiple \ref run() calls. Basically, all the given
     545    /// parameters are kept for the next \ref run() call, unless
     546    /// \ref resetParams() or \ref reset() is used.
     547    /// If the underlying digraph was also modified after the construction
     548    /// of the class or the last \ref reset() call, then the \ref reset()
     549    /// function must be used, otherwise \ref resetParams() is sufficient.
     550    ///
     551    /// See \ref resetParams() for examples.
     552    ///
     553    /// \return <tt>(*this)</tt>
     554    ///
     555    /// \see resetParams(), run()
     556    CapacityScaling& reset() {
    317557      // Resize vectors
    318558      _node_num = countNodes(_graph);
     
    378618     
    379619      // Reset parameters
    380       reset();
    381     }
    382 
    383     /// \name Parameters
    384     /// The parameters of the algorithm can be specified using these
    385     /// functions.
    386 
    387     /// @{
    388 
    389     /// \brief Set the lower bounds on the arcs.
    390     ///
    391     /// This function sets the lower bounds on the arcs.
    392     /// If it is not used before calling \ref run(), the lower bounds
    393     /// will be set to zero on all arcs.
    394     ///
    395     /// \param map An arc map storing the lower bounds.
    396     /// Its \c Value type must be convertible to the \c Value type
    397     /// of the algorithm.
    398     ///
    399     /// \return <tt>(*this)</tt>
    400     template <typename LowerMap>
    401     CapacityScaling& lowerMap(const LowerMap& map) {
    402       _have_lower = true;
    403       for (ArcIt a(_graph); a != INVALID; ++a) {
    404         _lower[_arc_idf[a]] = map[a];
    405         _lower[_arc_idb[a]] = map[a];
    406       }
    407       return *this;
    408     }
    409 
    410     /// \brief Set the upper bounds (capacities) on the arcs.
    411     ///
    412     /// This function sets the upper bounds (capacities) on the arcs.
    413     /// If it is not used before calling \ref run(), the upper bounds
    414     /// will be set to \ref INF on all arcs (i.e. the flow value will be
    415     /// unbounded from above).
    416     ///
    417     /// \param map An arc map storing the upper bounds.
    418     /// Its \c Value type must be convertible to the \c Value type
    419     /// of the algorithm.
    420     ///
    421     /// \return <tt>(*this)</tt>
    422     template<typename UpperMap>
    423     CapacityScaling& upperMap(const UpperMap& map) {
    424       for (ArcIt a(_graph); a != INVALID; ++a) {
    425         _upper[_arc_idf[a]] = map[a];
    426       }
    427       return *this;
    428     }
    429 
    430     /// \brief Set the costs of the arcs.
    431     ///
    432     /// This function sets the costs of the arcs.
    433     /// If it is not used before calling \ref run(), the costs
    434     /// will be set to \c 1 on all arcs.
    435     ///
    436     /// \param map An arc map storing the costs.
    437     /// Its \c Value type must be convertible to the \c Cost type
    438     /// of the algorithm.
    439     ///
    440     /// \return <tt>(*this)</tt>
    441     template<typename CostMap>
    442     CapacityScaling& costMap(const CostMap& map) {
    443       for (ArcIt a(_graph); a != INVALID; ++a) {
    444         _cost[_arc_idf[a]] =  map[a];
    445         _cost[_arc_idb[a]] = -map[a];
    446       }
    447       return *this;
    448     }
    449 
    450     /// \brief Set the supply values of the nodes.
    451     ///
    452     /// This function sets the supply values of the nodes.
    453     /// If neither this function nor \ref stSupply() is used before
    454     /// calling \ref run(), the supply of each node will be set to zero.
    455     ///
    456     /// \param map A node map storing the supply values.
    457     /// Its \c Value type must be convertible to the \c Value type
    458     /// of the algorithm.
    459     ///
    460     /// \return <tt>(*this)</tt>
    461     template<typename SupplyMap>
    462     CapacityScaling& supplyMap(const SupplyMap& map) {
    463       for (NodeIt n(_graph); n != INVALID; ++n) {
    464         _supply[_node_id[n]] = map[n];
    465       }
    466       return *this;
    467     }
    468 
    469     /// \brief Set single source and target nodes and a supply value.
    470     ///
    471     /// This function sets a single source node and a single target node
    472     /// and the required flow value.
    473     /// If neither this function nor \ref supplyMap() is used before
    474     /// calling \ref run(), the supply of each node will be set to zero.
    475     ///
    476     /// Using this function has the same effect as using \ref supplyMap()
    477     /// with such a map in which \c k is assigned to \c s, \c -k is
    478     /// assigned to \c t and all other nodes have zero supply value.
    479     ///
    480     /// \param s The source node.
    481     /// \param t The target node.
    482     /// \param k The required amount of flow from node \c s to node \c t
    483     /// (i.e. the supply of \c s and the demand of \c t).
    484     ///
    485     /// \return <tt>(*this)</tt>
    486     CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
    487       for (int i = 0; i != _node_num; ++i) {
    488         _supply[i] = 0;
    489       }
    490       _supply[_node_id[s]] =  k;
    491       _supply[_node_id[t]] = -k;
    492       return *this;
    493     }
    494    
    495     /// @}
    496 
    497     /// \name Execution control
    498     /// The algorithm can be executed using \ref run().
    499 
    500     /// @{
    501 
    502     /// \brief Run the algorithm.
    503     ///
    504     /// This function runs the algorithm.
    505     /// The paramters can be specified using functions \ref lowerMap(),
    506     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
    507     /// For example,
    508     /// \code
    509     ///   CapacityScaling<ListDigraph> cs(graph);
    510     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
    511     ///     .supplyMap(sup).run();
    512     /// \endcode
    513     ///
    514     /// This function can be called more than once. All the parameters
    515     /// that have been given are kept for the next call, unless
    516     /// \ref reset() is called, thus only the modified parameters
    517     /// have to be set again. See \ref reset() for examples.
    518     /// However, the underlying digraph must not be modified after this
    519     /// class have been constructed, since it copies and extends the graph.
    520     ///
    521     /// \param factor The capacity scaling factor. It must be larger than
    522     /// one to use scaling. If it is less or equal to one, then scaling
    523     /// will be disabled.
    524     ///
    525     /// \return \c INFEASIBLE if no feasible flow exists,
    526     /// \n \c OPTIMAL if the problem has optimal solution
    527     /// (i.e. it is feasible and bounded), and the algorithm has found
    528     /// optimal flow and node potentials (primal and dual solutions),
    529     /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
    530     /// and infinite upper bound. It means that the objective function
    531     /// is unbounded on that arc, however, note that it could actually be
    532     /// bounded over the feasible flows, but this algroithm cannot handle
    533     /// these cases.
    534     ///
    535     /// \see ProblemType
    536     ProblemType run(int factor = 4) {
    537       _factor = factor;
    538       ProblemType pt = init();
    539       if (pt != OPTIMAL) return pt;
    540       return start();
    541     }
    542 
    543     /// \brief Reset all the parameters that have been given before.
    544     ///
    545     /// This function resets all the paramaters that have been given
    546     /// before using functions \ref lowerMap(), \ref upperMap(),
    547     /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    548     ///
    549     /// It is useful for multiple run() calls. If this function is not
    550     /// used, all the parameters given before are kept for the next
    551     /// \ref run() call.
    552     /// However, the underlying digraph must not be modified after this
    553     /// class have been constructed, since it copies and extends the graph.
    554     ///
    555     /// For example,
    556     /// \code
    557     ///   CapacityScaling<ListDigraph> cs(graph);
    558     ///
    559     ///   // First run
    560     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
    561     ///     .supplyMap(sup).run();
    562     ///
    563     ///   // Run again with modified cost map (reset() is not called,
    564     ///   // so only the cost map have to be set again)
    565     ///   cost[e] += 100;
    566     ///   cs.costMap(cost).run();
    567     ///
    568     ///   // Run again from scratch using reset()
    569     ///   // (the lower bounds will be set to zero on all arcs)
    570     ///   cs.reset();
    571     ///   cs.upperMap(capacity).costMap(cost)
    572     ///     .supplyMap(sup).run();
    573     /// \endcode
    574     ///
    575     /// \return <tt>(*this)</tt>
    576     CapacityScaling& reset() {
    577       for (int i = 0; i != _node_num; ++i) {
    578         _supply[i] = 0;
    579       }
    580       for (int j = 0; j != _res_arc_num; ++j) {
    581         _lower[j] = 0;
    582         _upper[j] = INF;
    583         _cost[j] = _forward[j] ? 1 : -1;
    584       }
    585       _have_lower = false;
     620      resetParams();
    586621      return *this;
    587622    }
     
    765800      if (_factor > 1) {
    766801        // With scaling
    767         Value max_sup = 0, max_dem = 0;
    768         for (int i = 0; i != _node_num; ++i) {
     802        Value max_sup = 0, max_dem = 0, max_cap = 0;
     803        for (int i = 0; i != _root; ++i) {
    769804          Value ex = _excess[i];
    770805          if ( ex > max_sup) max_sup =  ex;
    771806          if (-ex > max_dem) max_dem = -ex;
    772         }
    773         Value max_cap = 0;
    774         for (int j = 0; j != _res_arc_num; ++j) {
    775           if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     807          int last_out = _first_out[i+1] - 1;
     808          for (int j = _first_out[i]; j != last_out; ++j) {
     809            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     810          }
    776811        }
    777812        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
  • 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/cost_scaling.h

    r821 r840  
    105105  /// \tparam GR The digraph type the algorithm runs on.
    106106  /// \tparam V The number type used for flow amounts, capacity bounds
    107   /// and supply values in the algorithm. By default it is \c int.
     107  /// and supply values in the algorithm. By default, it is \c int.
    108108  /// \tparam C The number type used for costs and potentials in the
    109   /// algorithm. By default it is the same as \c V.
     109  /// algorithm. By default, it is the same as \c V.
     110  /// \tparam TR The traits class that defines various types used by the
     111  /// algorithm. By default, it is \ref CostScalingDefaultTraits
     112  /// "CostScalingDefaultTraits<GR, V, C>".
     113  /// In most cases, this parameter should not be set directly,
     114  /// consider to use the named template parameters instead.
    110115  ///
    111116  /// \warning Both number types must be signed and all input data must
     
    137142    ///
    138143    /// The large cost type used for internal computations.
    139     /// Using the \ref CostScalingDefaultTraits "default traits class",
    140     /// it is \c long \c long if the \c Cost type is integer,
     144    /// By default, it is \c long \c long if the \c Cost type is integer,
    141145    /// otherwise it is \c double.
    142146    typedef typename TR::LargeCost LargeCost;
     
    198202
    199203    typedef std::vector<int> IntVector;
    200     typedef std::vector<char> BoolVector;
    201204    typedef std::vector<Value> ValueVector;
    202205    typedef std::vector<Cost> CostVector;
    203206    typedef std::vector<LargeCost> LargeCostVector;
     207    typedef std::vector<char> BoolVector;
     208    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    204209
    205210  private:
     
    245250    bool _have_lower;
    246251    Value _sum_supply;
     252    int _sup_node_num;
    247253
    248254    // Data structures for storing the digraph
     
    273279    int _alpha;
    274280
     281    IntVector _buckets;
     282    IntVector _bucket_next;
     283    IntVector _bucket_prev;
     284    IntVector _rank;
     285    int _max_rank;
     286 
    275287    // Data for a StaticDigraph structure
    276288    typedef std::pair<int, int> IntPair;
     
    333345      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
    334346        "The cost type of CostScaling must be signed");
    335 
     347     
     348      // Reset data structures
     349      reset();
     350    }
     351
     352    /// \name Parameters
     353    /// The parameters of the algorithm can be specified using these
     354    /// functions.
     355
     356    /// @{
     357
     358    /// \brief Set the lower bounds on the arcs.
     359    ///
     360    /// This function sets the lower bounds on the arcs.
     361    /// If it is not used before calling \ref run(), the lower bounds
     362    /// will be set to zero on all arcs.
     363    ///
     364    /// \param map An arc map storing the lower bounds.
     365    /// Its \c Value type must be convertible to the \c Value type
     366    /// of the algorithm.
     367    ///
     368    /// \return <tt>(*this)</tt>
     369    template <typename LowerMap>
     370    CostScaling& lowerMap(const LowerMap& map) {
     371      _have_lower = true;
     372      for (ArcIt a(_graph); a != INVALID; ++a) {
     373        _lower[_arc_idf[a]] = map[a];
     374        _lower[_arc_idb[a]] = map[a];
     375      }
     376      return *this;
     377    }
     378
     379    /// \brief Set the upper bounds (capacities) on the arcs.
     380    ///
     381    /// This function sets the upper bounds (capacities) on the arcs.
     382    /// If it is not used before calling \ref run(), the upper bounds
     383    /// will be set to \ref INF on all arcs (i.e. the flow value will be
     384    /// unbounded from above).
     385    ///
     386    /// \param map An arc map storing the upper bounds.
     387    /// Its \c Value type must be convertible to the \c Value type
     388    /// of the algorithm.
     389    ///
     390    /// \return <tt>(*this)</tt>
     391    template<typename UpperMap>
     392    CostScaling& upperMap(const UpperMap& map) {
     393      for (ArcIt a(_graph); a != INVALID; ++a) {
     394        _upper[_arc_idf[a]] = map[a];
     395      }
     396      return *this;
     397    }
     398
     399    /// \brief Set the costs of the arcs.
     400    ///
     401    /// This function sets the costs of the arcs.
     402    /// If it is not used before calling \ref run(), the costs
     403    /// will be set to \c 1 on all arcs.
     404    ///
     405    /// \param map An arc map storing the costs.
     406    /// Its \c Value type must be convertible to the \c Cost type
     407    /// of the algorithm.
     408    ///
     409    /// \return <tt>(*this)</tt>
     410    template<typename CostMap>
     411    CostScaling& costMap(const CostMap& map) {
     412      for (ArcIt a(_graph); a != INVALID; ++a) {
     413        _scost[_arc_idf[a]] =  map[a];
     414        _scost[_arc_idb[a]] = -map[a];
     415      }
     416      return *this;
     417    }
     418
     419    /// \brief Set the supply values of the nodes.
     420    ///
     421    /// This function sets the supply values of the nodes.
     422    /// If neither this function nor \ref stSupply() is used before
     423    /// calling \ref run(), the supply of each node will be set to zero.
     424    ///
     425    /// \param map A node map storing the supply values.
     426    /// Its \c Value type must be convertible to the \c Value type
     427    /// of the algorithm.
     428    ///
     429    /// \return <tt>(*this)</tt>
     430    template<typename SupplyMap>
     431    CostScaling& supplyMap(const SupplyMap& map) {
     432      for (NodeIt n(_graph); n != INVALID; ++n) {
     433        _supply[_node_id[n]] = map[n];
     434      }
     435      return *this;
     436    }
     437
     438    /// \brief Set single source and target nodes and a supply value.
     439    ///
     440    /// This function sets a single source node and a single target node
     441    /// and the required flow value.
     442    /// If neither this function nor \ref supplyMap() is used before
     443    /// calling \ref run(), the supply of each node will be set to zero.
     444    ///
     445    /// Using this function has the same effect as using \ref supplyMap()
     446    /// with such a map in which \c k is assigned to \c s, \c -k is
     447    /// assigned to \c t and all other nodes have zero supply value.
     448    ///
     449    /// \param s The source node.
     450    /// \param t The target node.
     451    /// \param k The required amount of flow from node \c s to node \c t
     452    /// (i.e. the supply of \c s and the demand of \c t).
     453    ///
     454    /// \return <tt>(*this)</tt>
     455    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
     456      for (int i = 0; i != _res_node_num; ++i) {
     457        _supply[i] = 0;
     458      }
     459      _supply[_node_id[s]] =  k;
     460      _supply[_node_id[t]] = -k;
     461      return *this;
     462    }
     463   
     464    /// @}
     465
     466    /// \name Execution control
     467    /// The algorithm can be executed using \ref run().
     468
     469    /// @{
     470
     471    /// \brief Run the algorithm.
     472    ///
     473    /// This function runs the algorithm.
     474    /// The paramters can be specified using functions \ref lowerMap(),
     475    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     476    /// For example,
     477    /// \code
     478    ///   CostScaling<ListDigraph> cs(graph);
     479    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
     480    ///     .supplyMap(sup).run();
     481    /// \endcode
     482    ///
     483    /// This function can be called more than once. All the given parameters
     484    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     485    /// is used, thus only the modified parameters have to be set again.
     486    /// If the underlying digraph was also modified after the construction
     487    /// of the class (or the last \ref reset() call), then the \ref reset()
     488    /// function must be called.
     489    ///
     490    /// \param method The internal method that will be used in the
     491    /// algorithm. For more information, see \ref Method.
     492    /// \param factor The cost scaling factor. It must be larger than one.
     493    ///
     494    /// \return \c INFEASIBLE if no feasible flow exists,
     495    /// \n \c OPTIMAL if the problem has optimal solution
     496    /// (i.e. it is feasible and bounded), and the algorithm has found
     497    /// optimal flow and node potentials (primal and dual solutions),
     498    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
     499    /// and infinite upper bound. It means that the objective function
     500    /// is unbounded on that arc, however, note that it could actually be
     501    /// bounded over the feasible flows, but this algroithm cannot handle
     502    /// these cases.
     503    ///
     504    /// \see ProblemType, Method
     505    /// \see resetParams(), reset()
     506    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
     507      _alpha = factor;
     508      ProblemType pt = init();
     509      if (pt != OPTIMAL) return pt;
     510      start(method);
     511      return OPTIMAL;
     512    }
     513
     514    /// \brief Reset all the parameters that have been given before.
     515    ///
     516    /// This function resets all the paramaters that have been given
     517    /// before using functions \ref lowerMap(), \ref upperMap(),
     518    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
     519    ///
     520    /// It is useful for multiple \ref run() calls. Basically, all the given
     521    /// parameters are kept for the next \ref run() call, unless
     522    /// \ref resetParams() or \ref reset() is used.
     523    /// If the underlying digraph was also modified after the construction
     524    /// of the class or the last \ref reset() call, then the \ref reset()
     525    /// function must be used, otherwise \ref resetParams() is sufficient.
     526    ///
     527    /// For example,
     528    /// \code
     529    ///   CostScaling<ListDigraph> cs(graph);
     530    ///
     531    ///   // First run
     532    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
     533    ///     .supplyMap(sup).run();
     534    ///
     535    ///   // Run again with modified cost map (resetParams() is not called,
     536    ///   // so only the cost map have to be set again)
     537    ///   cost[e] += 100;
     538    ///   cs.costMap(cost).run();
     539    ///
     540    ///   // Run again from scratch using resetParams()
     541    ///   // (the lower bounds will be set to zero on all arcs)
     542    ///   cs.resetParams();
     543    ///   cs.upperMap(capacity).costMap(cost)
     544    ///     .supplyMap(sup).run();
     545    /// \endcode
     546    ///
     547    /// \return <tt>(*this)</tt>
     548    ///
     549    /// \see reset(), run()
     550    CostScaling& resetParams() {
     551      for (int i = 0; i != _res_node_num; ++i) {
     552        _supply[i] = 0;
     553      }
     554      int limit = _first_out[_root];
     555      for (int j = 0; j != limit; ++j) {
     556        _lower[j] = 0;
     557        _upper[j] = INF;
     558        _scost[j] = _forward[j] ? 1 : -1;
     559      }
     560      for (int j = limit; j != _res_arc_num; ++j) {
     561        _lower[j] = 0;
     562        _upper[j] = INF;
     563        _scost[j] = 0;
     564        _scost[_reverse[j]] = 0;
     565      }     
     566      _have_lower = false;
     567      return *this;
     568    }
     569
     570    /// \brief Reset all the parameters that have been given before.
     571    ///
     572    /// This function resets all the paramaters that have been given
     573    /// before using functions \ref lowerMap(), \ref upperMap(),
     574    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
     575    ///
     576    /// It is useful for multiple run() calls. If this function is not
     577    /// used, all the parameters given before are kept for the next
     578    /// \ref run() call.
     579    /// However, the underlying digraph must not be modified after this
     580    /// class have been constructed, since it copies and extends the graph.
     581    /// \return <tt>(*this)</tt>
     582    CostScaling& reset() {
    336583      // Resize vectors
    337584      _node_num = countNodes(_graph);
     
    401648     
    402649      // Reset parameters
    403       reset();
    404     }
    405 
    406     /// \name Parameters
    407     /// The parameters of the algorithm can be specified using these
    408     /// functions.
    409 
    410     /// @{
    411 
    412     /// \brief Set the lower bounds on the arcs.
    413     ///
    414     /// This function sets the lower bounds on the arcs.
    415     /// If it is not used before calling \ref run(), the lower bounds
    416     /// will be set to zero on all arcs.
    417     ///
    418     /// \param map An arc map storing the lower bounds.
    419     /// Its \c Value type must be convertible to the \c Value type
    420     /// of the algorithm.
    421     ///
    422     /// \return <tt>(*this)</tt>
    423     template <typename LowerMap>
    424     CostScaling& lowerMap(const LowerMap& map) {
    425       _have_lower = true;
    426       for (ArcIt a(_graph); a != INVALID; ++a) {
    427         _lower[_arc_idf[a]] = map[a];
    428         _lower[_arc_idb[a]] = map[a];
    429       }
    430       return *this;
    431     }
    432 
    433     /// \brief Set the upper bounds (capacities) on the arcs.
    434     ///
    435     /// This function sets the upper bounds (capacities) on the arcs.
    436     /// If it is not used before calling \ref run(), the upper bounds
    437     /// will be set to \ref INF on all arcs (i.e. the flow value will be
    438     /// unbounded from above).
    439     ///
    440     /// \param map An arc map storing the upper bounds.
    441     /// Its \c Value type must be convertible to the \c Value type
    442     /// of the algorithm.
    443     ///
    444     /// \return <tt>(*this)</tt>
    445     template<typename UpperMap>
    446     CostScaling& upperMap(const UpperMap& map) {
    447       for (ArcIt a(_graph); a != INVALID; ++a) {
    448         _upper[_arc_idf[a]] = map[a];
    449       }
    450       return *this;
    451     }
    452 
    453     /// \brief Set the costs of the arcs.
    454     ///
    455     /// This function sets the costs of the arcs.
    456     /// If it is not used before calling \ref run(), the costs
    457     /// will be set to \c 1 on all arcs.
    458     ///
    459     /// \param map An arc map storing the costs.
    460     /// Its \c Value type must be convertible to the \c Cost type
    461     /// of the algorithm.
    462     ///
    463     /// \return <tt>(*this)</tt>
    464     template<typename CostMap>
    465     CostScaling& costMap(const CostMap& map) {
    466       for (ArcIt a(_graph); a != INVALID; ++a) {
    467         _scost[_arc_idf[a]] =  map[a];
    468         _scost[_arc_idb[a]] = -map[a];
    469       }
    470       return *this;
    471     }
    472 
    473     /// \brief Set the supply values of the nodes.
    474     ///
    475     /// This function sets the supply values of the nodes.
    476     /// If neither this function nor \ref stSupply() is used before
    477     /// calling \ref run(), the supply of each node will be set to zero.
    478     ///
    479     /// \param map A node map storing the supply values.
    480     /// Its \c Value type must be convertible to the \c Value type
    481     /// of the algorithm.
    482     ///
    483     /// \return <tt>(*this)</tt>
    484     template<typename SupplyMap>
    485     CostScaling& supplyMap(const SupplyMap& map) {
    486       for (NodeIt n(_graph); n != INVALID; ++n) {
    487         _supply[_node_id[n]] = map[n];
    488       }
    489       return *this;
    490     }
    491 
    492     /// \brief Set single source and target nodes and a supply value.
    493     ///
    494     /// This function sets a single source node and a single target node
    495     /// and the required flow value.
    496     /// If neither this function nor \ref supplyMap() is used before
    497     /// calling \ref run(), the supply of each node will be set to zero.
    498     ///
    499     /// Using this function has the same effect as using \ref supplyMap()
    500     /// with such a map in which \c k is assigned to \c s, \c -k is
    501     /// assigned to \c t and all other nodes have zero supply value.
    502     ///
    503     /// \param s The source node.
    504     /// \param t The target node.
    505     /// \param k The required amount of flow from node \c s to node \c t
    506     /// (i.e. the supply of \c s and the demand of \c t).
    507     ///
    508     /// \return <tt>(*this)</tt>
    509     CostScaling& stSupply(const Node& s, const Node& t, Value k) {
    510       for (int i = 0; i != _res_node_num; ++i) {
    511         _supply[i] = 0;
    512       }
    513       _supply[_node_id[s]] =  k;
    514       _supply[_node_id[t]] = -k;
    515       return *this;
    516     }
    517    
    518     /// @}
    519 
    520     /// \name Execution control
    521     /// The algorithm can be executed using \ref run().
    522 
    523     /// @{
    524 
    525     /// \brief Run the algorithm.
    526     ///
    527     /// This function runs the algorithm.
    528     /// The paramters can be specified using functions \ref lowerMap(),
    529     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
    530     /// For example,
    531     /// \code
    532     ///   CostScaling<ListDigraph> cs(graph);
    533     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
    534     ///     .supplyMap(sup).run();
    535     /// \endcode
    536     ///
    537     /// This function can be called more than once. All the parameters
    538     /// that have been given are kept for the next call, unless
    539     /// \ref reset() is called, thus only the modified parameters
    540     /// have to be set again. See \ref reset() for examples.
    541     /// However, the underlying digraph must not be modified after this
    542     /// class have been constructed, since it copies and extends the graph.
    543     ///
    544     /// \param method The internal method that will be used in the
    545     /// algorithm. For more information, see \ref Method.
    546     /// \param factor The cost scaling factor. It must be larger than one.
    547     ///
    548     /// \return \c INFEASIBLE if no feasible flow exists,
    549     /// \n \c OPTIMAL if the problem has optimal solution
    550     /// (i.e. it is feasible and bounded), and the algorithm has found
    551     /// optimal flow and node potentials (primal and dual solutions),
    552     /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
    553     /// and infinite upper bound. It means that the objective function
    554     /// is unbounded on that arc, however, note that it could actually be
    555     /// bounded over the feasible flows, but this algroithm cannot handle
    556     /// these cases.
    557     ///
    558     /// \see ProblemType, Method
    559     ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
    560       _alpha = factor;
    561       ProblemType pt = init();
    562       if (pt != OPTIMAL) return pt;
    563       start(method);
    564       return OPTIMAL;
    565     }
    566 
    567     /// \brief Reset all the parameters that have been given before.
    568     ///
    569     /// This function resets all the paramaters that have been given
    570     /// before using functions \ref lowerMap(), \ref upperMap(),
    571     /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    572     ///
    573     /// It is useful for multiple run() calls. If this function is not
    574     /// used, all the parameters given before are kept for the next
    575     /// \ref run() call.
    576     /// However, the underlying digraph must not be modified after this
    577     /// class have been constructed, since it copies and extends the graph.
    578     ///
    579     /// For example,
    580     /// \code
    581     ///   CostScaling<ListDigraph> cs(graph);
    582     ///
    583     ///   // First run
    584     ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
    585     ///     .supplyMap(sup).run();
    586     ///
    587     ///   // Run again with modified cost map (reset() is not called,
    588     ///   // so only the cost map have to be set again)
    589     ///   cost[e] += 100;
    590     ///   cs.costMap(cost).run();
    591     ///
    592     ///   // Run again from scratch using reset()
    593     ///   // (the lower bounds will be set to zero on all arcs)
    594     ///   cs.reset();
    595     ///   cs.upperMap(capacity).costMap(cost)
    596     ///     .supplyMap(sup).run();
    597     /// \endcode
    598     ///
    599     /// \return <tt>(*this)</tt>
    600     CostScaling& reset() {
    601       for (int i = 0; i != _res_node_num; ++i) {
    602         _supply[i] = 0;
    603       }
    604       int limit = _first_out[_root];
    605       for (int j = 0; j != limit; ++j) {
    606         _lower[j] = 0;
    607         _upper[j] = INF;
    608         _scost[j] = _forward[j] ? 1 : -1;
    609       }
    610       for (int j = limit; j != _res_arc_num; ++j) {
    611         _lower[j] = 0;
    612         _upper[j] = INF;
    613         _scost[j] = 0;
    614         _scost[_reverse[j]] = 0;
    615       }     
    616       _have_lower = false;
     650      resetParams();
    617651      return *this;
    618652    }
     
    803837      }
    804838
     839      _sup_node_num = 0;
     840      for (NodeIt n(_graph); n != INVALID; ++n) {
     841        if (sup[n] > 0) ++_sup_node_num;
     842      }
     843
    805844      // Find a feasible flow using Circulation
    806845      Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap>
     
    837876        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
    838877          int ra = _reverse[a];
    839           _res_cap[a] = 1;
     878          _res_cap[a] = 0;
    840879          _res_cap[ra] = 0;
    841880          _cost[a] = 0;
     
    851890      // Maximum path length for partial augment
    852891      const int MAX_PATH_LENGTH = 4;
    853      
     892
     893      // Initialize data structures for buckets     
     894      _max_rank = _alpha * _res_node_num;
     895      _buckets.resize(_max_rank);
     896      _bucket_next.resize(_res_node_num + 1);
     897      _bucket_prev.resize(_res_node_num + 1);
     898      _rank.resize(_res_node_num + 1);
     899 
    854900      // Execute the algorithm
    855901      switch (method) {
     
    890936      }
    891937    }
     938   
     939    // Initialize a cost scaling phase
     940    void initPhase() {
     941      // Saturate arcs not satisfying the optimality condition
     942      for (int u = 0; u != _res_node_num; ++u) {
     943        int last_out = _first_out[u+1];
     944        LargeCost pi_u = _pi[u];
     945        for (int a = _first_out[u]; a != last_out; ++a) {
     946          int v = _target[a];
     947          if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
     948            Value delta = _res_cap[a];
     949            _excess[u] -= delta;
     950            _excess[v] += delta;
     951            _res_cap[a] = 0;
     952            _res_cap[_reverse[a]] += delta;
     953          }
     954        }
     955      }
     956     
     957      // Find active nodes (i.e. nodes with positive excess)
     958      for (int u = 0; u != _res_node_num; ++u) {
     959        if (_excess[u] > 0) _active_nodes.push_back(u);
     960      }
     961
     962      // Initialize the next arcs
     963      for (int u = 0; u != _res_node_num; ++u) {
     964        _next_out[u] = _first_out[u];
     965      }
     966    }
     967   
     968    // Early termination heuristic
     969    bool earlyTermination() {
     970      const double EARLY_TERM_FACTOR = 3.0;
     971
     972      // Build a static residual graph
     973      _arc_vec.clear();
     974      _cost_vec.clear();
     975      for (int j = 0; j != _res_arc_num; ++j) {
     976        if (_res_cap[j] > 0) {
     977          _arc_vec.push_back(IntPair(_source[j], _target[j]));
     978          _cost_vec.push_back(_cost[j] + 1);
     979        }
     980      }
     981      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
     982
     983      // Run Bellman-Ford algorithm to check if the current flow is optimal
     984      BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
     985      bf.init(0);
     986      bool done = false;
     987      int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
     988      for (int i = 0; i < K && !done; ++i) {
     989        done = bf.processNextWeakRound();
     990      }
     991      return done;
     992    }
     993
     994    // Global potential update heuristic
     995    void globalUpdate() {
     996      int bucket_end = _root + 1;
     997   
     998      // Initialize buckets
     999      for (int r = 0; r != _max_rank; ++r) {
     1000        _buckets[r] = bucket_end;
     1001      }
     1002      Value total_excess = 0;
     1003      for (int i = 0; i != _res_node_num; ++i) {
     1004        if (_excess[i] < 0) {
     1005          _rank[i] = 0;
     1006          _bucket_next[i] = _buckets[0];
     1007          _bucket_prev[_buckets[0]] = i;
     1008          _buckets[0] = i;
     1009        } else {
     1010          total_excess += _excess[i];
     1011          _rank[i] = _max_rank;
     1012        }
     1013      }
     1014      if (total_excess == 0) return;
     1015
     1016      // Search the buckets
     1017      int r = 0;
     1018      for ( ; r != _max_rank; ++r) {
     1019        while (_buckets[r] != bucket_end) {
     1020          // Remove the first node from the current bucket
     1021          int u = _buckets[r];
     1022          _buckets[r] = _bucket_next[u];
     1023         
     1024          // Search the incomming arcs of u
     1025          LargeCost pi_u = _pi[u];
     1026          int last_out = _first_out[u+1];
     1027          for (int a = _first_out[u]; a != last_out; ++a) {
     1028            int ra = _reverse[a];
     1029            if (_res_cap[ra] > 0) {
     1030              int v = _source[ra];
     1031              int old_rank_v = _rank[v];
     1032              if (r < old_rank_v) {
     1033                // Compute the new rank of v
     1034                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
     1035                int new_rank_v = old_rank_v;
     1036                if (nrc < LargeCost(_max_rank))
     1037                  new_rank_v = r + 1 + int(nrc);
     1038                 
     1039                // Change the rank of v
     1040                if (new_rank_v < old_rank_v) {
     1041                  _rank[v] = new_rank_v;
     1042                  _next_out[v] = _first_out[v];
     1043                 
     1044                  // Remove v from its old bucket
     1045                  if (old_rank_v < _max_rank) {
     1046                    if (_buckets[old_rank_v] == v) {
     1047                      _buckets[old_rank_v] = _bucket_next[v];
     1048                    } else {
     1049                      _bucket_next[_bucket_prev[v]] = _bucket_next[v];
     1050                      _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
     1051                    }
     1052                  }
     1053                 
     1054                  // Insert v to its new bucket
     1055                  _bucket_next[v] = _buckets[new_rank_v];
     1056                  _bucket_prev[_buckets[new_rank_v]] = v;
     1057                  _buckets[new_rank_v] = v;
     1058                }
     1059              }
     1060            }
     1061          }
     1062
     1063          // Finish search if there are no more active nodes
     1064          if (_excess[u] > 0) {
     1065            total_excess -= _excess[u];
     1066            if (total_excess <= 0) break;
     1067          }
     1068        }
     1069        if (total_excess <= 0) break;
     1070      }
     1071     
     1072      // Relabel nodes
     1073      for (int u = 0; u != _res_node_num; ++u) {
     1074        int k = std::min(_rank[u], r);
     1075        if (k > 0) {
     1076          _pi[u] -= _epsilon * k;
     1077          _next_out[u] = _first_out[u];
     1078        }
     1079      }
     1080    }
    8921081
    8931082    /// Execute the algorithm performing augment and relabel operations
    8941083    void startAugment(int max_length = std::numeric_limits<int>::max()) {
    8951084      // Paramters for heuristics
    896       const int BF_HEURISTIC_EPSILON_BOUND = 1000;
    897       const int BF_HEURISTIC_BOUND_FACTOR  = 3;
    898 
     1085      const int EARLY_TERM_EPSILON_LIMIT = 1000;
     1086      const double GLOBAL_UPDATE_FACTOR = 3.0;
     1087
     1088      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1089        (_res_node_num + _sup_node_num * _sup_node_num));
     1090      int next_update_limit = global_update_freq;
     1091     
     1092      int relabel_cnt = 0;
     1093     
    8991094      // Perform cost scaling phases
    900       IntVector pred_arc(_res_node_num);
    901       std::vector<int> path_nodes;
     1095      std::vector<int> path;
    9021096      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    9031097                                        1 : _epsilon / _alpha )
    9041098      {
    905         // "Early Termination" heuristic: use Bellman-Ford algorithm
    906         // to check if the current flow is optimal
    907         if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
    908           _arc_vec.clear();
    909           _cost_vec.clear();
    910           for (int j = 0; j != _res_arc_num; ++j) {
    911             if (_res_cap[j] > 0) {
    912               _arc_vec.push_back(IntPair(_source[j], _target[j]));
    913               _cost_vec.push_back(_cost[j] + 1);
    914             }
    915           }
    916           _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
    917 
    918           BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
    919           bf.init(0);
    920           bool done = false;
    921           int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
    922           for (int i = 0; i < K && !done; ++i)
    923             done = bf.processNextWeakRound();
    924           if (done) break;
    925         }
    926 
    927         // Saturate arcs not satisfying the optimality condition
    928         for (int a = 0; a != _res_arc_num; ++a) {
    929           if (_res_cap[a] > 0 &&
    930               _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
    931             Value delta = _res_cap[a];
    932             _excess[_source[a]] -= delta;
    933             _excess[_target[a]] += delta;
    934             _res_cap[a] = 0;
    935             _res_cap[_reverse[a]] += delta;
    936           }
     1099        // Early termination heuristic
     1100        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
     1101          if (earlyTermination()) break;
    9371102        }
    9381103       
    939         // Find active nodes (i.e. nodes with positive excess)
    940         for (int u = 0; u != _res_node_num; ++u) {
    941           if (_excess[u] > 0) _active_nodes.push_back(u);
    942         }
    943 
    944         // Initialize the next arcs
    945         for (int u = 0; u != _res_node_num; ++u) {
    946           _next_out[u] = _first_out[u];
    947         }
    948 
     1104        // Initialize current phase
     1105        initPhase();
     1106       
    9491107        // Perform partial augment and relabel operations
    9501108        while (true) {
     
    9561114          if (_active_nodes.size() == 0) break;
    9571115          int start = _active_nodes.front();
    958           path_nodes.clear();
    959           path_nodes.push_back(start);
    9601116
    9611117          // Find an augmenting path from the start node
     1118          path.clear();
    9621119          int tip = start;
    963           while (_excess[tip] >= 0 &&
    964                  int(path_nodes.size()) <= max_length) {
     1120          while (_excess[tip] >= 0 && int(path.size()) < max_length) {
    9651121            int u;
    966             LargeCost min_red_cost, rc;
    967             int last_out = _sum_supply < 0 ?
    968               _first_out[tip+1] : _first_out[tip+1] - 1;
     1122            LargeCost min_red_cost, rc, pi_tip = _pi[tip];
     1123            int last_out = _first_out[tip+1];
    9691124            for (int a = _next_out[tip]; a != last_out; ++a) {
    970               if (_res_cap[a] > 0 &&
    971                   _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
    972                 u = _target[a];
    973                 pred_arc[u] = a;
     1125              u = _target[a];
     1126              if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
     1127                path.push_back(a);
    9741128                _next_out[tip] = a;
    9751129                tip = u;
    976                 path_nodes.push_back(tip);
    9771130                goto next_step;
    9781131              }
     
    9801133
    9811134            // Relabel tip node
    982             min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
     1135            min_red_cost = std::numeric_limits<LargeCost>::max();
     1136            if (tip != start) {
     1137              int ra = _reverse[path.back()];
     1138              min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
     1139            }
    9831140            for (int a = _first_out[tip]; a != last_out; ++a) {
    984               rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
     1141              rc = _cost[a] + pi_tip - _pi[_target[a]];
    9851142              if (_res_cap[a] > 0 && rc < min_red_cost) {
    9861143                min_red_cost = rc;
     
    9881145            }
    9891146            _pi[tip] -= min_red_cost + _epsilon;
    990 
    991             // Reset the next arc of tip
    9921147            _next_out[tip] = _first_out[tip];
     1148            ++relabel_cnt;
    9931149
    9941150            // Step back
    9951151            if (tip != start) {
    996               path_nodes.pop_back();
    997               tip = path_nodes.back();
     1152              tip = _source[path.back()];
     1153              path.pop_back();
    9981154            }
    9991155
     
    10031159          // Augment along the found path (as much flow as possible)
    10041160          Value delta;
    1005           int u, v = path_nodes.front(), pa;
    1006           for (int i = 1; i < int(path_nodes.size()); ++i) {
     1161          int pa, u, v = start;
     1162          for (int i = 0; i != int(path.size()); ++i) {
     1163            pa = path[i];
    10071164            u = v;
    1008             v = path_nodes[i];
    1009             pa = pred_arc[v];
     1165            v = _target[pa];
    10101166            delta = std::min(_res_cap[pa], _excess[u]);
    10111167            _res_cap[pa] -= delta;
     
    10161172              _active_nodes.push_back(v);
    10171173          }
     1174
     1175          // Global update heuristic
     1176          if (relabel_cnt >= next_update_limit) {
     1177            globalUpdate();
     1178            next_update_limit += global_update_freq;
     1179          }
    10181180        }
    10191181      }
     
    10231185    void startPush() {
    10241186      // Paramters for heuristics
    1025       const int BF_HEURISTIC_EPSILON_BOUND = 1000;
    1026       const int BF_HEURISTIC_BOUND_FACTOR  = 3;
    1027 
     1187      const int EARLY_TERM_EPSILON_LIMIT = 1000;
     1188      const double GLOBAL_UPDATE_FACTOR = 2.0;
     1189
     1190      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1191        (_res_node_num + _sup_node_num * _sup_node_num));
     1192      int next_update_limit = global_update_freq;
     1193
     1194      int relabel_cnt = 0;
     1195     
    10281196      // Perform cost scaling phases
    10291197      BoolVector hyper(_res_node_num, false);
     1198      LargeCostVector hyper_cost(_res_node_num);
    10301199      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    10311200                                        1 : _epsilon / _alpha )
    10321201      {
    1033         // "Early Termination" heuristic: use Bellman-Ford algorithm
    1034         // to check if the current flow is optimal
    1035         if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
    1036           _arc_vec.clear();
    1037           _cost_vec.clear();
    1038           for (int j = 0; j != _res_arc_num; ++j) {
    1039             if (_res_cap[j] > 0) {
    1040               _arc_vec.push_back(IntPair(_source[j], _target[j]));
    1041               _cost_vec.push_back(_cost[j] + 1);
    1042             }
    1043           }
    1044           _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
    1045 
    1046           BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
    1047           bf.init(0);
    1048           bool done = false;
    1049           int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
    1050           for (int i = 0; i < K && !done; ++i)
    1051             done = bf.processNextWeakRound();
    1052           if (done) break;
    1053         }
    1054 
    1055         // Saturate arcs not satisfying the optimality condition
    1056         for (int a = 0; a != _res_arc_num; ++a) {
    1057           if (_res_cap[a] > 0 &&
    1058               _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
    1059             Value delta = _res_cap[a];
    1060             _excess[_source[a]] -= delta;
    1061             _excess[_target[a]] += delta;
    1062             _res_cap[a] = 0;
    1063             _res_cap[_reverse[a]] += delta;
    1064           }
    1065         }
    1066 
    1067         // Find active nodes (i.e. nodes with positive excess)
    1068         for (int u = 0; u != _res_node_num; ++u) {
    1069           if (_excess[u] > 0) _active_nodes.push_back(u);
    1070         }
    1071 
    1072         // Initialize the next arcs
    1073         for (int u = 0; u != _res_node_num; ++u) {
    1074           _next_out[u] = _first_out[u];
    1075         }
     1202        // Early termination heuristic
     1203        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
     1204          if (earlyTermination()) break;
     1205        }
     1206       
     1207        // Initialize current phase
     1208        initPhase();
    10761209
    10771210        // Perform push and relabel operations
    10781211        while (_active_nodes.size() > 0) {
    1079           LargeCost min_red_cost, rc;
     1212          LargeCost min_red_cost, rc, pi_n;
    10801213          Value delta;
    10811214          int n, t, a, last_out = _res_arc_num;
    10821215
     1216        next_node:
    10831217          // Select an active node (FIFO selection)
    1084         next_node:
    10851218          n = _active_nodes.front();
    1086           last_out = _sum_supply < 0 ?
    1087             _first_out[n+1] : _first_out[n+1] - 1;
    1088 
     1219          last_out = _first_out[n+1];
     1220          pi_n = _pi[n];
     1221         
    10891222          // Perform push operations if there are admissible arcs
    10901223          if (_excess[n] > 0) {
    10911224            for (a = _next_out[n]; a != last_out; ++a) {
    10921225              if (_res_cap[a] > 0 &&
    1093                   _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
     1226                  _cost[a] + pi_n - _pi[_target[a]] < 0) {
    10941227                delta = std::min(_res_cap[a], _excess[n]);
    10951228                t = _target[a];
     
    10971230                // Push-look-ahead heuristic
    10981231                Value ahead = -_excess[t];
    1099                 int last_out_t = _sum_supply < 0 ?
    1100                   _first_out[t+1] : _first_out[t+1] - 1;
     1232                int last_out_t = _first_out[t+1];
     1233                LargeCost pi_t = _pi[t];
    11011234                for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
    11021235                  if (_res_cap[ta] > 0 &&
    1103                       _cost[ta] + _pi[_source[ta]] - _pi[_target[ta]] < 0)
     1236                      _cost[ta] + pi_t - _pi[_target[ta]] < 0)
    11041237                    ahead += _res_cap[ta];
    11051238                  if (ahead >= delta) break;
     
    11081241
    11091242                // Push flow along the arc
    1110                 if (ahead < delta) {
     1243                if (ahead < delta && !hyper[t]) {
    11111244                  _res_cap[a] -= ahead;
    11121245                  _res_cap[_reverse[a]] += ahead;
     
    11151248                  _active_nodes.push_front(t);
    11161249                  hyper[t] = true;
     1250                  hyper_cost[t] = _cost[a] + pi_n - pi_t;
    11171251                  _next_out[n] = a;
    11181252                  goto next_node;
     
    11371271          // Relabel the node if it is still active (or hyper)
    11381272          if (_excess[n] > 0 || hyper[n]) {
    1139             min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
     1273             min_red_cost = hyper[n] ? -hyper_cost[n] :
     1274               std::numeric_limits<LargeCost>::max();
    11401275            for (int a = _first_out[n]; a != last_out; ++a) {
    1141               rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
     1276              rc = _cost[a] + pi_n - _pi[_target[a]];
    11421277              if (_res_cap[a] > 0 && rc < min_red_cost) {
    11431278                min_red_cost = rc;
     
    11451280            }
    11461281            _pi[n] -= min_red_cost + _epsilon;
     1282            _next_out[n] = _first_out[n];
    11471283            hyper[n] = false;
    1148 
    1149             // Reset the next arc
    1150             _next_out[n] = _first_out[n];
     1284            ++relabel_cnt;
    11511285          }
    11521286       
     
    11581292            _active_nodes.pop_front();
    11591293          }
     1294         
     1295          // Global update heuristic
     1296          if (relabel_cnt >= next_update_limit) {
     1297            globalUpdate();
     1298            for (int u = 0; u != _res_node_num; ++u)
     1299              hyper[u] = false;
     1300            next_update_limit += global_update_freq;
     1301          }
    11601302        }
    11611303      }
  • lemon/cycle_canceling.h

    r820 r840  
    145145   
    146146    typedef std::vector<int> IntVector;
    147     typedef std::vector<char> CharVector;
    148147    typedef std::vector<double> DoubleVector;
    149148    typedef std::vector<Value> ValueVector;
    150149    typedef std::vector<Cost> CostVector;
     150    typedef std::vector<char> BoolVector;
     151    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    151152
    152153  private:
     
    199200    IntArcMap _arc_idb;
    200201    IntVector _first_out;
    201     CharVector _forward;
     202    BoolVector _forward;
    202203    IntVector _source;
    203204    IntVector _target;
     
    251252        "The cost type of CycleCanceling must be signed");
    252253
     254      // Reset data structures
     255      reset();
     256    }
     257
     258    /// \name Parameters
     259    /// The parameters of the algorithm can be specified using these
     260    /// functions.
     261
     262    /// @{
     263
     264    /// \brief Set the lower bounds on the arcs.
     265    ///
     266    /// This function sets the lower bounds on the arcs.
     267    /// If it is not used before calling \ref run(), the lower bounds
     268    /// will be set to zero on all arcs.
     269    ///
     270    /// \param map An arc map storing the lower bounds.
     271    /// Its \c Value type must be convertible to the \c Value type
     272    /// of the algorithm.
     273    ///
     274    /// \return <tt>(*this)</tt>
     275    template <typename LowerMap>
     276    CycleCanceling& lowerMap(const LowerMap& map) {
     277      _have_lower = true;
     278      for (ArcIt a(_graph); a != INVALID; ++a) {
     279        _lower[_arc_idf[a]] = map[a];
     280        _lower[_arc_idb[a]] = map[a];
     281      }
     282      return *this;
     283    }
     284
     285    /// \brief Set the upper bounds (capacities) on the arcs.
     286    ///
     287    /// This function sets the upper bounds (capacities) on the arcs.
     288    /// If it is not used before calling \ref run(), the upper bounds
     289    /// will be set to \ref INF on all arcs (i.e. the flow value will be
     290    /// unbounded from above).
     291    ///
     292    /// \param map An arc map storing the upper bounds.
     293    /// Its \c Value type must be convertible to the \c Value type
     294    /// of the algorithm.
     295    ///
     296    /// \return <tt>(*this)</tt>
     297    template<typename UpperMap>
     298    CycleCanceling& upperMap(const UpperMap& map) {
     299      for (ArcIt a(_graph); a != INVALID; ++a) {
     300        _upper[_arc_idf[a]] = map[a];
     301      }
     302      return *this;
     303    }
     304
     305    /// \brief Set the costs of the arcs.
     306    ///
     307    /// This function sets the costs of the arcs.
     308    /// If it is not used before calling \ref run(), the costs
     309    /// will be set to \c 1 on all arcs.
     310    ///
     311    /// \param map An arc map storing the costs.
     312    /// Its \c Value type must be convertible to the \c Cost type
     313    /// of the algorithm.
     314    ///
     315    /// \return <tt>(*this)</tt>
     316    template<typename CostMap>
     317    CycleCanceling& costMap(const CostMap& map) {
     318      for (ArcIt a(_graph); a != INVALID; ++a) {
     319        _cost[_arc_idf[a]] =  map[a];
     320        _cost[_arc_idb[a]] = -map[a];
     321      }
     322      return *this;
     323    }
     324
     325    /// \brief Set the supply values of the nodes.
     326    ///
     327    /// This function sets the supply values of the nodes.
     328    /// If neither this function nor \ref stSupply() is used before
     329    /// calling \ref run(), the supply of each node will be set to zero.
     330    ///
     331    /// \param map A node map storing the supply values.
     332    /// Its \c Value type must be convertible to the \c Value type
     333    /// of the algorithm.
     334    ///
     335    /// \return <tt>(*this)</tt>
     336    template<typename SupplyMap>
     337    CycleCanceling& supplyMap(const SupplyMap& map) {
     338      for (NodeIt n(_graph); n != INVALID; ++n) {
     339        _supply[_node_id[n]] = map[n];
     340      }
     341      return *this;
     342    }
     343
     344    /// \brief Set single source and target nodes and a supply value.
     345    ///
     346    /// This function sets a single source node and a single target node
     347    /// and the required flow value.
     348    /// If neither this function nor \ref supplyMap() is used before
     349    /// calling \ref run(), the supply of each node will be set to zero.
     350    ///
     351    /// Using this function has the same effect as using \ref supplyMap()
     352    /// with such a map in which \c k is assigned to \c s, \c -k is
     353    /// assigned to \c t and all other nodes have zero supply value.
     354    ///
     355    /// \param s The source node.
     356    /// \param t The target node.
     357    /// \param k The required amount of flow from node \c s to node \c t
     358    /// (i.e. the supply of \c s and the demand of \c t).
     359    ///
     360    /// \return <tt>(*this)</tt>
     361    CycleCanceling& stSupply(const Node& s, const Node& t, Value k) {
     362      for (int i = 0; i != _res_node_num; ++i) {
     363        _supply[i] = 0;
     364      }
     365      _supply[_node_id[s]] =  k;
     366      _supply[_node_id[t]] = -k;
     367      return *this;
     368    }
     369   
     370    /// @}
     371
     372    /// \name Execution control
     373    /// The algorithm can be executed using \ref run().
     374
     375    /// @{
     376
     377    /// \brief Run the algorithm.
     378    ///
     379    /// This function runs the algorithm.
     380    /// The paramters can be specified using functions \ref lowerMap(),
     381    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     382    /// For example,
     383    /// \code
     384    ///   CycleCanceling<ListDigraph> cc(graph);
     385    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
     386    ///     .supplyMap(sup).run();
     387    /// \endcode
     388    ///
     389    /// This function can be called more than once. All the given parameters
     390    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     391    /// is used, thus only the modified parameters have to be set again.
     392    /// If the underlying digraph was also modified after the construction
     393    /// of the class (or the last \ref reset() call), then the \ref reset()
     394    /// function must be called.
     395    ///
     396    /// \param method The cycle-canceling method that will be used.
     397    /// For more information, see \ref Method.
     398    ///
     399    /// \return \c INFEASIBLE if no feasible flow exists,
     400    /// \n \c OPTIMAL if the problem has optimal solution
     401    /// (i.e. it is feasible and bounded), and the algorithm has found
     402    /// optimal flow and node potentials (primal and dual solutions),
     403    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
     404    /// and infinite upper bound. It means that the objective function
     405    /// is unbounded on that arc, however, note that it could actually be
     406    /// bounded over the feasible flows, but this algroithm cannot handle
     407    /// these cases.
     408    ///
     409    /// \see ProblemType, Method
     410    /// \see resetParams(), reset()
     411    ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
     412      ProblemType pt = init();
     413      if (pt != OPTIMAL) return pt;
     414      start(method);
     415      return OPTIMAL;
     416    }
     417
     418    /// \brief Reset all the parameters that have been given before.
     419    ///
     420    /// This function resets all the paramaters that have been given
     421    /// before using functions \ref lowerMap(), \ref upperMap(),
     422    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
     423    ///
     424    /// It is useful for multiple \ref run() calls. Basically, all the given
     425    /// parameters are kept for the next \ref run() call, unless
     426    /// \ref resetParams() or \ref reset() is used.
     427    /// If the underlying digraph was also modified after the construction
     428    /// of the class or the last \ref reset() call, then the \ref reset()
     429    /// function must be used, otherwise \ref resetParams() is sufficient.
     430    ///
     431    /// For example,
     432    /// \code
     433    ///   CycleCanceling<ListDigraph> cs(graph);
     434    ///
     435    ///   // First run
     436    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
     437    ///     .supplyMap(sup).run();
     438    ///
     439    ///   // Run again with modified cost map (resetParams() is not called,
     440    ///   // so only the cost map have to be set again)
     441    ///   cost[e] += 100;
     442    ///   cc.costMap(cost).run();
     443    ///
     444    ///   // Run again from scratch using resetParams()
     445    ///   // (the lower bounds will be set to zero on all arcs)
     446    ///   cc.resetParams();
     447    ///   cc.upperMap(capacity).costMap(cost)
     448    ///     .supplyMap(sup).run();
     449    /// \endcode
     450    ///
     451    /// \return <tt>(*this)</tt>
     452    ///
     453    /// \see reset(), run()
     454    CycleCanceling& resetParams() {
     455      for (int i = 0; i != _res_node_num; ++i) {
     456        _supply[i] = 0;
     457      }
     458      int limit = _first_out[_root];
     459      for (int j = 0; j != limit; ++j) {
     460        _lower[j] = 0;
     461        _upper[j] = INF;
     462        _cost[j] = _forward[j] ? 1 : -1;
     463      }
     464      for (int j = limit; j != _res_arc_num; ++j) {
     465        _lower[j] = 0;
     466        _upper[j] = INF;
     467        _cost[j] = 0;
     468        _cost[_reverse[j]] = 0;
     469      }     
     470      _have_lower = false;
     471      return *this;
     472    }
     473
     474    /// \brief Reset the internal data structures and all the parameters
     475    /// that have been given before.
     476    ///
     477    /// This function resets the internal data structures and all the
     478    /// paramaters that have been given before using functions \ref lowerMap(),
     479    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     480    ///
     481    /// It is useful for multiple \ref run() calls. Basically, all the given
     482    /// parameters are kept for the next \ref run() call, unless
     483    /// \ref resetParams() or \ref reset() is used.
     484    /// If the underlying digraph was also modified after the construction
     485    /// of the class or the last \ref reset() call, then the \ref reset()
     486    /// function must be used, otherwise \ref resetParams() is sufficient.
     487    ///
     488    /// See \ref resetParams() for examples.
     489    ///
     490    /// \return <tt>(*this)</tt>
     491    ///
     492    /// \see resetParams(), run()
     493    CycleCanceling& reset() {
    253494      // Resize vectors
    254495      _node_num = countNodes(_graph);
     
    316557     
    317558      // Reset parameters
    318       reset();
    319     }
    320 
    321     /// \name Parameters
    322     /// The parameters of the algorithm can be specified using these
    323     /// functions.
    324 
    325     /// @{
    326 
    327     /// \brief Set the lower bounds on the arcs.
    328     ///
    329     /// This function sets the lower bounds on the arcs.
    330     /// If it is not used before calling \ref run(), the lower bounds
    331     /// will be set to zero on all arcs.
    332     ///
    333     /// \param map An arc map storing the lower bounds.
    334     /// Its \c Value type must be convertible to the \c Value type
    335     /// of the algorithm.
    336     ///
    337     /// \return <tt>(*this)</tt>
    338     template <typename LowerMap>
    339     CycleCanceling& lowerMap(const LowerMap& map) {
    340       _have_lower = true;
    341       for (ArcIt a(_graph); a != INVALID; ++a) {
    342         _lower[_arc_idf[a]] = map[a];
    343         _lower[_arc_idb[a]] = map[a];
    344       }
    345       return *this;
    346     }
    347 
    348     /// \brief Set the upper bounds (capacities) on the arcs.
    349     ///
    350     /// This function sets the upper bounds (capacities) on the arcs.
    351     /// If it is not used before calling \ref run(), the upper bounds
    352     /// will be set to \ref INF on all arcs (i.e. the flow value will be
    353     /// unbounded from above).
    354     ///
    355     /// \param map An arc map storing the upper bounds.
    356     /// Its \c Value type must be convertible to the \c Value type
    357     /// of the algorithm.
    358     ///
    359     /// \return <tt>(*this)</tt>
    360     template<typename UpperMap>
    361     CycleCanceling& upperMap(const UpperMap& map) {
    362       for (ArcIt a(_graph); a != INVALID; ++a) {
    363         _upper[_arc_idf[a]] = map[a];
    364       }
    365       return *this;
    366     }
    367 
    368     /// \brief Set the costs of the arcs.
    369     ///
    370     /// This function sets the costs of the arcs.
    371     /// If it is not used before calling \ref run(), the costs
    372     /// will be set to \c 1 on all arcs.
    373     ///
    374     /// \param map An arc map storing the costs.
    375     /// Its \c Value type must be convertible to the \c Cost type
    376     /// of the algorithm.
    377     ///
    378     /// \return <tt>(*this)</tt>
    379     template<typename CostMap>
    380     CycleCanceling& costMap(const CostMap& map) {
    381       for (ArcIt a(_graph); a != INVALID; ++a) {
    382         _cost[_arc_idf[a]] =  map[a];
    383         _cost[_arc_idb[a]] = -map[a];
    384       }
    385       return *this;
    386     }
    387 
    388     /// \brief Set the supply values of the nodes.
    389     ///
    390     /// This function sets the supply values of the nodes.
    391     /// If neither this function nor \ref stSupply() is used before
    392     /// calling \ref run(), the supply of each node will be set to zero.
    393     ///
    394     /// \param map A node map storing the supply values.
    395     /// Its \c Value type must be convertible to the \c Value type
    396     /// of the algorithm.
    397     ///
    398     /// \return <tt>(*this)</tt>
    399     template<typename SupplyMap>
    400     CycleCanceling& supplyMap(const SupplyMap& map) {
    401       for (NodeIt n(_graph); n != INVALID; ++n) {
    402         _supply[_node_id[n]] = map[n];
    403       }
    404       return *this;
    405     }
    406 
    407     /// \brief Set single source and target nodes and a supply value.
    408     ///
    409     /// This function sets a single source node and a single target node
    410     /// and the required flow value.
    411     /// If neither this function nor \ref supplyMap() is used before
    412     /// calling \ref run(), the supply of each node will be set to zero.
    413     ///
    414     /// Using this function has the same effect as using \ref supplyMap()
    415     /// with such a map in which \c k is assigned to \c s, \c -k is
    416     /// assigned to \c t and all other nodes have zero supply value.
    417     ///
    418     /// \param s The source node.
    419     /// \param t The target node.
    420     /// \param k The required amount of flow from node \c s to node \c t
    421     /// (i.e. the supply of \c s and the demand of \c t).
    422     ///
    423     /// \return <tt>(*this)</tt>
    424     CycleCanceling& stSupply(const Node& s, const Node& t, Value k) {
    425       for (int i = 0; i != _res_node_num; ++i) {
    426         _supply[i] = 0;
    427       }
    428       _supply[_node_id[s]] =  k;
    429       _supply[_node_id[t]] = -k;
    430       return *this;
    431     }
    432    
    433     /// @}
    434 
    435     /// \name Execution control
    436     /// The algorithm can be executed using \ref run().
    437 
    438     /// @{
    439 
    440     /// \brief Run the algorithm.
    441     ///
    442     /// This function runs the algorithm.
    443     /// The paramters can be specified using functions \ref lowerMap(),
    444     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
    445     /// For example,
    446     /// \code
    447     ///   CycleCanceling<ListDigraph> cc(graph);
    448     ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
    449     ///     .supplyMap(sup).run();
    450     /// \endcode
    451     ///
    452     /// This function can be called more than once. All the parameters
    453     /// that have been given are kept for the next call, unless
    454     /// \ref reset() is called, thus only the modified parameters
    455     /// have to be set again. See \ref reset() for examples.
    456     /// However, the underlying digraph must not be modified after this
    457     /// class have been constructed, since it copies and extends the graph.
    458     ///
    459     /// \param method The cycle-canceling method that will be used.
    460     /// For more information, see \ref Method.
    461     ///
    462     /// \return \c INFEASIBLE if no feasible flow exists,
    463     /// \n \c OPTIMAL if the problem has optimal solution
    464     /// (i.e. it is feasible and bounded), and the algorithm has found
    465     /// optimal flow and node potentials (primal and dual solutions),
    466     /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
    467     /// and infinite upper bound. It means that the objective function
    468     /// is unbounded on that arc, however, note that it could actually be
    469     /// bounded over the feasible flows, but this algroithm cannot handle
    470     /// these cases.
    471     ///
    472     /// \see ProblemType, Method
    473     ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
    474       ProblemType pt = init();
    475       if (pt != OPTIMAL) return pt;
    476       start(method);
    477       return OPTIMAL;
    478     }
    479 
    480     /// \brief Reset all the parameters that have been given before.
    481     ///
    482     /// This function resets all the paramaters that have been given
    483     /// before using functions \ref lowerMap(), \ref upperMap(),
    484     /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    485     ///
    486     /// It is useful for multiple run() calls. If this function is not
    487     /// used, all the parameters given before are kept for the next
    488     /// \ref run() call.
    489     /// However, the underlying digraph must not be modified after this
    490     /// class have been constructed, since it copies and extends the graph.
    491     ///
    492     /// For example,
    493     /// \code
    494     ///   CycleCanceling<ListDigraph> cs(graph);
    495     ///
    496     ///   // First run
    497     ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
    498     ///     .supplyMap(sup).run();
    499     ///
    500     ///   // Run again with modified cost map (reset() is not called,
    501     ///   // so only the cost map have to be set again)
    502     ///   cost[e] += 100;
    503     ///   cc.costMap(cost).run();
    504     ///
    505     ///   // Run again from scratch using reset()
    506     ///   // (the lower bounds will be set to zero on all arcs)
    507     ///   cc.reset();
    508     ///   cc.upperMap(capacity).costMap(cost)
    509     ///     .supplyMap(sup).run();
    510     /// \endcode
    511     ///
    512     /// \return <tt>(*this)</tt>
    513     CycleCanceling& reset() {
    514       for (int i = 0; i != _res_node_num; ++i) {
    515         _supply[i] = 0;
    516       }
    517       int limit = _first_out[_root];
    518       for (int j = 0; j != limit; ++j) {
    519         _lower[j] = 0;
    520         _upper[j] = INF;
    521         _cost[j] = _forward[j] ? 1 : -1;
    522       }
    523       for (int j = limit; j != _res_arc_num; ++j) {
    524         _lower[j] = 0;
    525         _upper[j] = INF;
    526         _cost[j] = 0;
    527         _cost[_reverse[j]] = 0;
    528       }     
    529       _have_lower = false;
     559      resetParams();
    530560      return *this;
    531561    }
     
    934964      DoubleVector pi(_res_node_num, 0.0);
    935965      IntVector level(_res_node_num);
    936       CharVector reached(_res_node_num);
    937       CharVector processed(_res_node_num);
     966      BoolVector reached(_res_node_num);
     967      BoolVector processed(_res_node_num);
    938968      IntVector pred_node(_res_node_num);
    939969      IntVector pred_arc(_res_node_num);
  • 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/graph_to_eps.h

    r786 r838  
    685685#else
    686686      os << bits::getWinFormattedDate();
     687      os << std::endl;
    687688#endif
    688689    }
    689     os << std::endl;
    690690
    691691    if (_autoArcWidthScale) {
  • lemon/hartmann_orlin.h

    r795 r841  
    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;
     
    402406    /// \pre \ref run() or \ref findMinMean() must be called before
    403407    /// using this function.
    404     LargeValue cycleLength() const {
    405       return _best_length;
     408    Value cycleLength() const {
     409      return static_cast<Value>(_best_length);
    406410    }
    407411
  • lemon/howard.h

    r771 r841  
    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;
     
    381385    /// \pre \ref run() or \ref findMinMean() must be called before
    382386    /// using this function.
    383     LargeValue cycleLength() const {
    384       return _best_length;
     387    Value cycleLength() const {
     388      return static_cast<Value>(_best_length);
    385389    }
    386390
  • lemon/karp.h

    r772 r841  
    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;
     
    389393    /// \pre \ref run() or \ref findMinMean() must be called before
    390394    /// using this function.
    391     LargeValue cycleLength() const {
    392       return _cycle_length;
     395    Value cycleLength() const {
     396      return static_cast<Value>(_cycle_length);
    393397    }
    394398
  • lemon/lp_base.h

    r786 r834  
    12301230      Row r;
    12311231      c.expr().simplify();
    1232       r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound():-INF,
     1232      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
    12331233                                ExprIterator(c.expr().comps.begin(), cols),
    12341234                                ExprIterator(c.expr().comps.end(), cols),
    1235                                 c.upperBounded()?c.upperBound():INF));
     1235                                c.upperBounded()?c.upperBound()-*c.expr():INF));
    12361236      return r;
    12371237    }
  • 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

    r812 r840  
    165165
    166166    typedef std::vector<int> IntVector;
    167     typedef std::vector<char> CharVector;
    168167    typedef std::vector<Value> ValueVector;
    169168    typedef std::vector<Cost> CostVector;
     169    typedef std::vector<char> BoolVector;
     170    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    170171
    171172    // State constants for arcs
     
    195196    IntVector _source;
    196197    IntVector _target;
     198    bool _arc_mixing;
    197199
    198200    // Node and arc data
     
    213215    IntVector _last_succ;
    214216    IntVector _dirty_revs;
    215     CharVector _forward;
    216     CharVector _state;
     217    BoolVector _forward;
     218    BoolVector _state;
    217219    int _root;
    218220
     
    245247      const IntVector  &_target;
    246248      const CostVector &_cost;
    247       const CharVector &_state;
     249      const BoolVector &_state;
    248250      const CostVector &_pi;
    249251      int &_in_arc;
     
    266268      bool findEnteringArc() {
    267269        Cost c;
    268         for (int e = _next_arc; e < _search_arc_num; ++e) {
     270        for (int e = _next_arc; e != _search_arc_num; ++e) {
    269271          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    270272          if (c < 0) {
     
    274276          }
    275277        }
    276         for (int e = 0; e < _next_arc; ++e) {
     278        for (int e = 0; e != _next_arc; ++e) {
    277279          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    278280          if (c < 0) {
     
    297299      const IntVector  &_target;
    298300      const CostVector &_cost;
    299       const CharVector &_state;
     301      const BoolVector &_state;
    300302      const CostVector &_pi;
    301303      int &_in_arc;
     
    314316      bool findEnteringArc() {
    315317        Cost c, min = 0;
    316         for (int e = 0; e < _search_arc_num; ++e) {
     318        for (int e = 0; e != _search_arc_num; ++e) {
    317319          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    318320          if (c < min) {
     
    336338      const IntVector  &_target;
    337339      const CostVector &_cost;
    338       const CharVector &_state;
     340      const BoolVector &_state;
    339341      const CostVector &_pi;
    340342      int &_in_arc;
     
    355357      {
    356358        // The main parameters of the pivot rule
    357         const double BLOCK_SIZE_FACTOR = 0.5;
     359        const double BLOCK_SIZE_FACTOR = 1.0;
    358360        const int MIN_BLOCK_SIZE = 10;
    359361
     
    368370        int cnt = _block_size;
    369371        int e;
    370         for (e = _next_arc; e < _search_arc_num; ++e) {
     372        for (e = _next_arc; e != _search_arc_num; ++e) {
    371373          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    372374          if (c < min) {
     
    379381          }
    380382        }
    381         for (e = 0; e < _next_arc; ++e) {
     383        for (e = 0; e != _next_arc; ++e) {
    382384          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    383385          if (c < min) {
     
    409411      const IntVector  &_target;
    410412      const CostVector &_cost;
    411       const CharVector &_state;
     413      const BoolVector &_state;
    412414      const CostVector &_pi;
    413415      int &_in_arc;
     
    470472        min = 0;
    471473        _curr_length = 0;
    472         for (e = _next_arc; e < _search_arc_num; ++e) {
     474        for (e = _next_arc; e != _search_arc_num; ++e) {
    473475          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    474476          if (c < 0) {
     
    481483          }
    482484        }
    483         for (e = 0; e < _next_arc; ++e) {
     485        for (e = 0; e != _next_arc; ++e) {
    484486          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    485487          if (c < 0) {
     
    512514      const IntVector  &_target;
    513515      const CostVector &_cost;
    514       const CharVector &_state;
     516      const BoolVector &_state;
    515517      const CostVector &_pi;
    516518      int &_in_arc;
     
    565567        // Check the current candidate list
    566568        int e;
    567         for (int i = 0; i < _curr_length; ++i) {
     569        for (int i = 0; i != _curr_length; ++i) {
    568570          e = _candidates[i];
    569571          _cand_cost[e] = _state[e] *
     
    578580        int limit = _head_length;
    579581
    580         for (e = _next_arc; e < _search_arc_num; ++e) {
     582        for (e = _next_arc; e != _search_arc_num; ++e) {
    581583          _cand_cost[e] = _state[e] *
    582584            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     
    590592          }
    591593        }
    592         for (e = 0; e < _next_arc; ++e) {
     594        for (e = 0; e != _next_arc; ++e) {
    593595          _cand_cost[e] = _state[e] *
    594596            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     
    634636    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    635637      _graph(graph), _node_id(graph), _arc_id(graph),
     638      _arc_mixing(arc_mixing),
    636639      MAX(std::numeric_limits<Value>::max()),
    637640      INF(std::numeric_limits<Value>::has_infinity ?
     
    644647        "The cost type of NetworkSimplex must be signed");
    645648       
    646       // Resize vectors
    647       _node_num = countNodes(_graph);
    648       _arc_num = countArcs(_graph);
    649       int all_node_num = _node_num + 1;
    650       int max_arc_num = _arc_num + 2 * _node_num;
    651 
    652       _source.resize(max_arc_num);
    653       _target.resize(max_arc_num);
    654 
    655       _lower.resize(_arc_num);
    656       _upper.resize(_arc_num);
    657       _cap.resize(max_arc_num);
    658       _cost.resize(max_arc_num);
    659       _supply.resize(all_node_num);
    660       _flow.resize(max_arc_num);
    661       _pi.resize(all_node_num);
    662 
    663       _parent.resize(all_node_num);
    664       _pred.resize(all_node_num);
    665       _forward.resize(all_node_num);
    666       _thread.resize(all_node_num);
    667       _rev_thread.resize(all_node_num);
    668       _succ_num.resize(all_node_num);
    669       _last_succ.resize(all_node_num);
    670       _state.resize(max_arc_num);
    671 
    672       // Copy the graph
    673       int i = 0;
    674       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    675         _node_id[n] = i;
    676       }
    677       if (arc_mixing) {
    678         // Store the arcs in a mixed order
    679         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    680         int i = 0, j = 0;
    681         for (ArcIt a(_graph); a != INVALID; ++a) {
    682           _arc_id[a] = i;
    683           _source[i] = _node_id[_graph.source(a)];
    684           _target[i] = _node_id[_graph.target(a)];
    685           if ((i += k) >= _arc_num) i = ++j;
    686         }
    687       } else {
    688         // Store the arcs in the original order
    689         int i = 0;
    690         for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
    691           _arc_id[a] = i;
    692           _source[i] = _node_id[_graph.source(a)];
    693           _target[i] = _node_id[_graph.target(a)];
    694         }
    695       }
    696      
    697       // Reset parameters
     649      // Reset data structures
    698650      reset();
    699651    }
     
    843795    /// \endcode
    844796    ///
    845     /// This function can be called more than once. All the parameters
    846     /// that have been given are kept for the next call, unless
    847     /// \ref reset() is called, thus only the modified parameters
    848     /// have to be set again. See \ref reset() for examples.
    849     /// However, the underlying digraph must not be modified after this
    850     /// class have been constructed, since it copies and extends the graph.
     797    /// This function can be called more than once. All the given parameters
     798    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     799    /// is used, thus only the modified parameters have to be set again.
     800    /// If the underlying digraph was also modified after the construction
     801    /// of the class (or the last \ref reset() call), then the \ref reset()
     802    /// function must be called.
    851803    ///
    852804    /// \param pivot_rule The pivot rule that will be used during the
     
    862814    ///
    863815    /// \see ProblemType, PivotRule
     816    /// \see resetParams(), reset()
    864817    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
    865818      if (!init()) return INFEASIBLE;
     
    873826    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    874827    ///
    875     /// It is useful for multiple run() calls. If this function is not
    876     /// used, all the parameters given before are kept for the next
    877     /// \ref run() call.
    878     /// However, the underlying digraph must not be modified after this
    879     /// class have been constructed, since it copies and extends the graph.
     828    /// It is useful for multiple \ref run() calls. Basically, all the given
     829    /// parameters are kept for the next \ref run() call, unless
     830    /// \ref resetParams() or \ref reset() is used.
     831    /// If the underlying digraph was also modified after the construction
     832    /// of the class or the last \ref reset() call, then the \ref reset()
     833    /// function must be used, otherwise \ref resetParams() is sufficient.
    880834    ///
    881835    /// For example,
     
    887841    ///     .supplyMap(sup).run();
    888842    ///
    889     ///   // Run again with modified cost map (reset() is not called,
     843    ///   // Run again with modified cost map (resetParams() is not called,
    890844    ///   // so only the cost map have to be set again)
    891845    ///   cost[e] += 100;
    892846    ///   ns.costMap(cost).run();
    893847    ///
    894     ///   // Run again from scratch using reset()
     848    ///   // Run again from scratch using resetParams()
    895849    ///   // (the lower bounds will be set to zero on all arcs)
    896     ///   ns.reset();
     850    ///   ns.resetParams();
    897851    ///   ns.upperMap(capacity).costMap(cost)
    898852    ///     .supplyMap(sup).run();
     
    900854    ///
    901855    /// \return <tt>(*this)</tt>
    902     NetworkSimplex& reset() {
     856    ///
     857    /// \see reset(), run()
     858    NetworkSimplex& resetParams() {
    903859      for (int i = 0; i != _node_num; ++i) {
    904860        _supply[i] = 0;
     
    914870    }
    915871
     872    /// \brief Reset the internal data structures and all the parameters
     873    /// that have been given before.
     874    ///
     875    /// This function resets the internal data structures and all the
     876    /// paramaters that have been given before using functions \ref lowerMap(),
     877    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
     878    /// \ref supplyType().
     879    ///
     880    /// It is useful for multiple \ref run() calls. Basically, all the given
     881    /// parameters are kept for the next \ref run() call, unless
     882    /// \ref resetParams() or \ref reset() is used.
     883    /// If the underlying digraph was also modified after the construction
     884    /// of the class or the last \ref reset() call, then the \ref reset()
     885    /// function must be used, otherwise \ref resetParams() is sufficient.
     886    ///
     887    /// See \ref resetParams() for examples.
     888    ///
     889    /// \return <tt>(*this)</tt>
     890    ///
     891    /// \see resetParams(), run()
     892    NetworkSimplex& reset() {
     893      // Resize vectors
     894      _node_num = countNodes(_graph);
     895      _arc_num = countArcs(_graph);
     896      int all_node_num = _node_num + 1;
     897      int max_arc_num = _arc_num + 2 * _node_num;
     898
     899      _source.resize(max_arc_num);
     900      _target.resize(max_arc_num);
     901
     902      _lower.resize(_arc_num);
     903      _upper.resize(_arc_num);
     904      _cap.resize(max_arc_num);
     905      _cost.resize(max_arc_num);
     906      _supply.resize(all_node_num);
     907      _flow.resize(max_arc_num);
     908      _pi.resize(all_node_num);
     909
     910      _parent.resize(all_node_num);
     911      _pred.resize(all_node_num);
     912      _forward.resize(all_node_num);
     913      _thread.resize(all_node_num);
     914      _rev_thread.resize(all_node_num);
     915      _succ_num.resize(all_node_num);
     916      _last_succ.resize(all_node_num);
     917      _state.resize(max_arc_num);
     918
     919      // Copy the graph
     920      int i = 0;
     921      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     922        _node_id[n] = i;
     923      }
     924      if (_arc_mixing) {
     925        // Store the arcs in a mixed order
     926        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     927        int i = 0, j = 0;
     928        for (ArcIt a(_graph); a != INVALID; ++a) {
     929          _arc_id[a] = i;
     930          _source[i] = _node_id[_graph.source(a)];
     931          _target[i] = _node_id[_graph.target(a)];
     932          if ((i += k) >= _arc_num) i = ++j;
     933        }
     934      } else {
     935        // Store the arcs in the original order
     936        int i = 0;
     937        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
     938          _arc_id[a] = i;
     939          _source[i] = _node_id[_graph.source(a)];
     940          _target[i] = _node_id[_graph.target(a)];
     941        }
     942      }
     943     
     944      // Reset parameters
     945      resetParams();
     946      return *this;
     947    }
     948   
    916949    /// @}
    917950
     
    13291362
    13301363      // Update _rev_thread using the new _thread values
    1331       for (int i = 0; i < int(_dirty_revs.size()); ++i) {
     1364      for (int i = 0; i != int(_dirty_revs.size()); ++i) {
    13321365        u = _dirty_revs[i];
    13331366        _rev_thread[_thread[u]] = u;
     
    13991432        _pi[u] += sigma;
    14001433      }
     1434    }
     1435
     1436    // Heuristic initial pivots
     1437    bool initialPivots() {
     1438      Value curr, total = 0;
     1439      std::vector<Node> supply_nodes, demand_nodes;
     1440      for (NodeIt u(_graph); u != INVALID; ++u) {
     1441        curr = _supply[_node_id[u]];
     1442        if (curr > 0) {
     1443          total += curr;
     1444          supply_nodes.push_back(u);
     1445        }
     1446        else if (curr < 0) {
     1447          demand_nodes.push_back(u);
     1448        }
     1449      }
     1450      if (_sum_supply > 0) total -= _sum_supply;
     1451      if (total <= 0) return true;
     1452
     1453      IntVector arc_vector;
     1454      if (_sum_supply >= 0) {
     1455        if (supply_nodes.size() == 1 && demand_nodes.size() == 1) {
     1456          // Perform a reverse graph search from the sink to the source
     1457          typename GR::template NodeMap<bool> reached(_graph, false);
     1458          Node s = supply_nodes[0], t = demand_nodes[0];
     1459          std::vector<Node> stack;
     1460          reached[t] = true;
     1461          stack.push_back(t);
     1462          while (!stack.empty()) {
     1463            Node u, v = stack.back();
     1464            stack.pop_back();
     1465            if (v == s) break;
     1466            for (InArcIt a(_graph, v); a != INVALID; ++a) {
     1467              if (reached[u = _graph.source(a)]) continue;
     1468              int j = _arc_id[a];
     1469              if (_cap[j] >= total) {
     1470                arc_vector.push_back(j);
     1471                reached[u] = true;
     1472                stack.push_back(u);
     1473              }
     1474            }
     1475          }
     1476        } else {
     1477          // Find the min. cost incomming arc for each demand node
     1478          for (int i = 0; i != int(demand_nodes.size()); ++i) {
     1479            Node v = demand_nodes[i];
     1480            Cost c, min_cost = std::numeric_limits<Cost>::max();
     1481            Arc min_arc = INVALID;
     1482            for (InArcIt a(_graph, v); a != INVALID; ++a) {
     1483              c = _cost[_arc_id[a]];
     1484              if (c < min_cost) {
     1485                min_cost = c;
     1486                min_arc = a;
     1487              }
     1488            }
     1489            if (min_arc != INVALID) {
     1490              arc_vector.push_back(_arc_id[min_arc]);
     1491            }
     1492          }
     1493        }
     1494      } else {
     1495        // Find the min. cost outgoing arc for each supply node
     1496        for (int i = 0; i != int(supply_nodes.size()); ++i) {
     1497          Node u = supply_nodes[i];
     1498          Cost c, min_cost = std::numeric_limits<Cost>::max();
     1499          Arc min_arc = INVALID;
     1500          for (OutArcIt a(_graph, u); a != INVALID; ++a) {
     1501            c = _cost[_arc_id[a]];
     1502            if (c < min_cost) {
     1503              min_cost = c;
     1504              min_arc = a;
     1505            }
     1506          }
     1507          if (min_arc != INVALID) {
     1508            arc_vector.push_back(_arc_id[min_arc]);
     1509          }
     1510        }
     1511      }
     1512
     1513      // Perform heuristic initial pivots
     1514      for (int i = 0; i != int(arc_vector.size()); ++i) {
     1515        in_arc = arc_vector[i];
     1516        if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] -
     1517            _pi[_target[in_arc]]) >= 0) continue;
     1518        findJoinNode();
     1519        bool change = findLeavingArc();
     1520        if (delta >= MAX) return false;
     1521        changeFlow(change);
     1522        if (change) {
     1523          updateTreeStructure();
     1524          updatePotential();
     1525        }
     1526      }
     1527      return true;
    14011528    }
    14021529
     
    14231550      PivotRuleImpl pivot(*this);
    14241551
     1552      // Perform heuristic initial pivots
     1553      if (!initialPivots()) return UNBOUNDED;
     1554
    14251555      // Execute the Network Simplex algorithm
    14261556      while (pivot.findEnteringArc()) {
  • 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>
  • scripts/bib2dox.py

    r754 r836  
    1 #!/usr/bin/env /usr/local/Python/bin/python2.1
     1#! /usr/bin/env python
    22"""
    33  BibTeX to Doxygen converter
    44  Usage: python bib2dox.py bibfile.bib > bibfile.dox
    55
     6  This file is a part of LEMON, a generic C++ optimization library.
     7
     8  **********************************************************************
     9
    610  This code is the modification of the BibTeX to XML converter
    7   by Vidar Bronken Gundersen et al. See the original copyright notices below.
     11  by Vidar Bronken Gundersen et al.
     12  See the original copyright notices below.
    813
    914  **********************************************************************
  • test/bellman_ford_test.cc

    r791 r844  
    105105      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
    106106      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
     107      ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
    107108      ::Create bf_test(gr,length);
    108109
  • test/min_cost_flow_test.cc

    r819 r830  
    158158      const MCF& const_mcf = mcf;
    159159
    160       b = mcf.reset()
     160      b = mcf.reset().resetParams()
    161161             .lowerMap(me.lower)
    162162             .upperMap(me.upper)
     
    347347  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
    348348           mcf1.OPTIMAL, true,     8010, test_str + "-4");
    349   mcf1.reset().supplyMap(s1);
     349  mcf1.resetParams().supplyMap(s1);
    350350  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
    351351           mcf1.OPTIMAL, true,       74, test_str + "-5");
     
    364364
    365365  // Tests for the GEQ form
    366   mcf1.reset().upperMap(u).costMap(c).supplyMap(s5);
     366  mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5);
    367367  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
    368368           mcf1.OPTIMAL, true,     3530, test_str + "-10", GEQ);
     
    381381  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
    382382           mcf2.OPTIMAL, true,   -40000, test_str + "-14");
    383   mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
     383  mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
    384384  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
    385385           mcf2.UNBOUNDED, false,     0, test_str + "-15");
  • tools/dimacs-solver.cc

    r644 r846  
    9292}
    9393
    94 template<class Value>
     94template<class Value, class LargeValue>
    9595void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
    9696               Value infty, DimacsDescriptor &desc)
     
    128128    std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
    129129    std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
    130     if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
     130    if (res) std::cerr << "Min flow cost: "
     131                       << ns.template totalCost<LargeValue>() << '\n';
    131132  }
    132133}
     
    152153
    153154
    154 template<class Value>
     155template<class Value, class LargeValue>
    155156void solve(ArgParser &ap, std::istream &is, std::ostream &os,
    156157           DimacsDescriptor &desc)
     
    170171    {
    171172    case DimacsDescriptor::MIN:
    172       solve_min<Value>(ap,is,os,infty,desc);
     173      solve_min<Value, LargeValue>(ap,is,os,infty,desc);
    173174      break;
    174175    case DimacsDescriptor::MAX:
     
    265266   
    266267  if(ap.given("double"))
    267     solve<double>(ap,is,os,desc);
     268    solve<double, double>(ap,is,os,desc);
    268269  else if(ap.given("ldouble"))
    269     solve<long double>(ap,is,os,desc);
     270    solve<long double, long double>(ap,is,os,desc);
    270271#ifdef LEMON_HAVE_LONG_LONG
    271272  else if(ap.given("long"))
    272     solve<long long>(ap,is,os,desc);
     273    solve<long long, long long>(ap,is,os,desc);
     274  else solve<int, long long>(ap,is,os,desc);
     275#else
     276  else solve<int, long>(ap,is,os,desc);
    273277#endif
    274   else solve<int>(ap,is,os,desc);
    275278
    276279  return 0;
Note: See TracChangeset for help on using the changeset viewer.