lemon-1.2: comparison lemon/cost

equal deleted inserted replaced

-:aae7c88f84b3
+:d3a0ae8775d5
 ///
 /// \warning Both value types must be signed and all input data must
 /// be integer.
 /// \warning This algorithm does not support negative costs for such
 /// arcs that have infinite upper bound.
+///
+/// \note %CostScaling provides three different internal methods,
+/// from which the most efficient one is used by default.
+/// For more information, see \ref Method.
 #ifdef DOXYGEN
 template <typename GR, typename V, typename C, typename TR>
 #else
 template < typename GR, typename V = int, typename C = V,
 typename TR = CostScalingDefaultTraits<GR, V, C> >
 /// over the feasible flows, but this algroithm cannot handle
 /// these cases.
 UNBOUNDED
 };
+/// \brief Constants for selecting the internal method.
+///
+/// Enum type containing constants for selecting the internal method
+/// for the \ref run() function.
+///
+/// \ref CostScaling provides three internal methods that differ mainly
+/// in their base operations, which are used in conjunction with the
+/// relabel operation.
+/// By default, the so called \ref PARTIAL_AUGMENT
+/// "Partial Augment-Relabel" method is used, which proved to be
+/// the most efficient and the most robust on various test inputs.
+/// However, the other methods can be selected using the \ref run()
+/// function with the proper parameter.
+enum Method {
+/// Local push operations are used, i.e. flow is moved only on one
+/// admissible arc at once.
+PUSH,
+/// Augment operations are used, i.e. flow is moved on admissible
+/// paths from a node with excess to a node with deficit.
+AUGMENT,
+/// Partial augment operations are used, i.e. flow is moved on
+/// admissible paths started from a node with excess, but the
+/// lengths of these paths are limited. This method can be viewed
+/// as a combined version of the previous two operations.
+PARTIAL_AUGMENT
+};
 private:
 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 typedef std::vector<int> IntVector;
 ///
 /// This function can be called more than once. All the parameters
 /// that have been given are kept for the next call, unless
 /// \ref reset() is called, thus only the modified parameters
 /// have to be set again. See \ref reset() for examples.
-/// However the underlying digraph must not be modified after this
+/// However, the underlying digraph must not be modified after this
-/// class have been constructed, since it copies the digraph.
+/// class have been constructed, since it copies and extends the graph.
 ///
-/// \param partial_augment By default the algorithm performs
+/// \param method The internal method that will be used in the
-/// partial augment and relabel operations in the cost scaling
+/// algorithm. For more information, see \ref Method.
-/// phases. Set this parameter to \c false for using local push and
+/// \param factor The cost scaling factor. It must be larger than one.
-/// relabel operations instead.
 ///
 /// \return \c INFEASIBLE if no feasible flow exists,
 /// \n \c OPTIMAL if the problem has optimal solution
 /// (i.e. it is feasible and bounded), and the algorithm has found
 /// optimal flow and node potentials (primal and dual solutions),
 /// and infinite upper bound. It means that the objective function
 /// is unbounded on that arc, however note that it could actually be
 /// bounded over the feasible flows, but this algroithm cannot handle
 /// these cases.
 ///
-/// \see ProblemType
+/// \see ProblemType, Method
-ProblemType run(bool partial_augment = true) {
+ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
+_alpha = factor;
 ProblemType pt = init();
 if (pt != OPTIMAL) return pt;
-start(partial_augment);
+start(method);
 return OPTIMAL;
 }
 /// \brief Reset all the parameters that have been given before.
 ///
 private:
 // Initialize the algorithm
 ProblemType init() {
 if (_res_node_num == 0) return INFEASIBLE;
-// Scaling factor
-_alpha = 8;
 // Check the sum of supply values
 _sum_supply = 0;
 for (int i = 0; i != _root; ++i) {
 _sum_supply += _supply[i];
 return OPTIMAL;
 }
 // Execute the algorithm and transform the results
-void start(bool partial_augment) {
+void start(Method method) {
+// Maximum path length for partial augment
+const int MAX_PATH_LENGTH = 4;
 // Execute the algorithm
-if (partial_augment) {
+switch (method) {
-startPartialAugment();
+case PUSH:
-} else {
+startPush();
-startPushRelabel();
+break;
+case AUGMENT:
+startAugment();
+break;
+case PARTIAL_AUGMENT:
+startAugment(MAX_PATH_LENGTH);
+break;
 }
 // Compute node potentials for the original costs
 _arc_vec.clear();
 _cost_vec.clear();
 if (!_forward[j]) _res_cap[j] += _lower[j];
 }
 }
 }
-/// Execute the algorithm performing partial augmentation and
+/// Execute the algorithm performing augment and relabel operations
-/// relabel operations
+void startAugment(int max_length = std::numeric_limits<int>::max()) {
-void startPartialAugment() {
 // Paramters for heuristics
 const int BF_HEURISTIC_EPSILON_BOUND = 1000;
 const int BF_HEURISTIC_BOUND_FACTOR  = 3;
-// Maximum augment path length
-const int MAX_PATH_LENGTH = 4;
 // Perform cost scaling phases
 IntVector pred_arc(_res_node_num);
 std::vector<int> path_nodes;
 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
 path_nodes.push_back(start);
 // Find an augmenting path from the start node
 int tip = start;
 while (_excess[tip] >= 0 &&
-int(path_nodes.size()) <= MAX_PATH_LENGTH) {
+int(path_nodes.size()) <= max_length) {
 int u;
 LargeCost min_red_cost, rc;
 int last_out = _sum_supply < 0 ?
 _first_out[tip+1] : _first_out[tip+1] - 1;
 for (int a = _next_out[tip]; a != last_out; ++a) {
 }
 }
 }
 /// Execute the algorithm performing push and relabel operations
-void startPushRelabel() {
+void startPush() {
 // Paramters for heuristics
 const int BF_HEURISTIC_EPSILON_BOUND = 1000;
 const int BF_HEURISTIC_BOUND_FACTOR  = 3;
 // Perform cost scaling phases

changeset 810	3b53491bf643
parent 809	22bb98ca0101
child 812	4b1b378823dc