lemon-1.3: comparison lemon/network

equal deleted inserted replaced

-:e2acf237e0e0
+:7d65283874b3
 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2009
+* Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 /// The objective function of the problem is unbounded, i.e.
 /// there is a directed cycle having negative total cost and
 /// infinite upper bound.
 UNBOUNDED
 };
 /// \brief Constants for selecting the type of the supply constraints.
 ///
 /// Enum type containing constants for selecting the supply type,
 /// i.e. the direction of the inequalities in the supply/demand
 /// constraints of the \ref min_cost_flow "minimum cost flow problem".
 GEQ,
 /// This option means that there are <em>"less or equal"</em>
 /// supply/demand constraints in the definition of the problem.
 LEQ
 };
 /// \brief Constants for selecting the pivot rule.
 ///
 /// Enum type containing constants for selecting the pivot rule for
 /// the \ref run() function.
 ///
 /// It is a modified version of the Candidate List method.
 /// It keeps only the several best eligible arcs from the former
 /// candidate list and extends this list in every iteration.
 ALTERING_LIST
 };
 private:
 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 typedef std::vector<int> IntVector;
 // Temporary data used in the current pivot iteration
 int in_arc, join, u_in, v_in, u_out, v_out;
 int first, second, right, last;
 int stem, par_stem, new_stem;
 Value delta;
 const Value MAX;
 public:
 /// \brief Constant for infinite upper bounds (capacities).
 ///
 /// Constant for infinite upper bounds (capacities).
 /// It is \c std::numeric_limits<Value>::infinity() if available,
 /// \c std::numeric_limits<Value>::max() otherwise.
 }
 if (_curr_length == _list_length) goto search_end;
 }
 }
 if (_curr_length == 0) return false;
 search_end:
 _minor_count = 1;
 _next_arc = e;
 return true;
 }
 limit = 0;
 cnt = _block_size;
 }
 }
 if (_curr_length == 0) return false;
 search_end:
 // Make heap of the candidate list (approximating a partial sort)
 make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 _sort_func );
 ///
 /// The constructor of the class.
 ///
 /// \param graph The digraph the algorithm runs on.
 /// \param arc_mixing Indicate if the arcs have to be stored in a
 /// mixed order in the internal data structure.
 /// In special cases, it could lead to better overall performance,
 /// but it is usually slower. Therefore it is disabled by default.
 NetworkSimplex(const GR& graph, bool arc_mixing = false) :
 _graph(graph), _node_id(graph), _arc_id(graph),
 _arc_mixing(arc_mixing),
 // Check the number types
 LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 "The flow type of NetworkSimplex must be signed");
 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 "The cost type of NetworkSimplex must be signed");
 // Reset data structures
 reset();
 }
 /// \name Parameters
 }
 _supply[_node_id[s]] =  k;
 _supply[_node_id[t]] = -k;
 return *this;
 }
 /// \brief Set the type of the supply constraints.
 ///
 /// This function sets the type of the supply/demand constraints.
 /// If it is not used before calling \ref run(), the \ref GEQ supply
 /// type will be used.
 /// \brief Run the algorithm.
 ///
 /// This function runs the algorithm.
 /// The paramters can be specified using functions \ref lowerMap(),
 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
 /// \ref supplyType().
 /// For example,
 /// \code
 ///   NetworkSimplex<ListDigraph> ns(graph);
 ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
 _arc_id[a] = i;
 _source[i] = _node_id[_graph.source(a)];
 _target[i] = _node_id[_graph.target(a)];
 }
 }
 // Reset parameters
 resetParams();
 return *this;
 }
 /// @}
 /// \name Query Functions
 /// The results of the algorithm can be obtained using these
 /// functions.\n
 // Initialize arc maps
 for (int i = 0; i != _arc_num; ++i) {
 _flow[i] = 0;
 _state[i] = STATE_LOWER;
 }
 // Set data for the artificial root node
 _root = _node_num;
 _parent[_root] = -1;
 _pred[_root] = -1;
 _thread[_root] = 0;
 }
 }
 // Search the cycle along the path form the second node to the root
 for (int u = second; u != join; u = _parent[u]) {
 e = _pred[u];
 d = _forward[u] ?
 (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
 if (d <= delta) {
 delta = d;
 u_out = u;
 result = 2;
 if (change) {
 updateTreeStructure();
 updatePotential();
 }
 }
 // Check feasibility
 for (int e = _search_arc_num; e != _all_arc_num; ++e) {
 if (_flow[e] != 0) return INFEASIBLE;
 }
 _supply[_source[i]] += c;
 _supply[_target[i]] -= c;
 }
 }
 }
 // Shift potentials to meet the requirements of the GEQ/LEQ type
 // optimality conditions
 if (_sum_supply == 0) {
 if (_stype == GEQ) {
 Cost max_pot = std::numeric_limits<Cost>::min();

changeset 877	141f9c0db4a3
parent 862	b6f76c95992e
child 889	0bca98cbebbb