LEMON/LEMON-official Changeset - r955:a93f1a27d831

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r955:a93f1a27d831

« 952:b6f76c

956:d3ea19 »

r955:a93f1a27d831

Mon, 08 Mar 2010 08:33:41

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Fix gcc 3.3 compilation error (#354) gcc 3.3 requires that a class has a default constructor if it has template named parameters. (That constructor can be protected.)

0 6 0

default

6 files changed with 24 insertions and 0 deletions:

lemon/capacity_scaling.h

lemon/cost_scaling.h

lemon/hartmann_orlin.h

lemon/howard.h

lemon/karp.h

lemon/suurballe.h

↑ Collapse diff ↑

lemon/capacity_scaling.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CAPACITY_SCALING_H
 		#define LEMON_CAPACITY_SCALING_H
 		/// \ingroup min_cost_flow_algs
 		///
 		/// \file
 		/// \brief Capacity Scaling algorithm for finding a minimum cost flow.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/bin_heap.h>
 		namespace lemon {
 		  /// \brief Default traits class of CapacityScaling algorithm.
 		  ///
 		  /// Default traits class of CapacityScaling algorithm.
 		  /// \tparam GR Digraph type.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values. By default it is \c int.
 		  /// \tparam C The number type used for costs and potentials.
 		  /// By default it is the same as \c V.
 		  template <typename GR, typename V = int, typename C = V>
 		  struct CapacityScalingDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		    /// \brief The type of the heap used for internal Dijkstra computations.
 		    ///
 		    /// The type of the heap used for internal Dijkstra computations.
 		    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
 		    /// its priority type must be \c Cost and its cross reference type
 		    /// must be \ref RangeMap "RangeMap<int>".
 		    typedef BinHeap<Cost, RangeMap<int> > Heap;
 		  };
 		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of the Capacity Scaling algorithm for
 		  /// finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref CapacityScaling implements the capacity scaling version
 		  /// of the successive shortest path algorithm for finding a
 		  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
 		  /// \ref edmondskarp72theoretical. It is an efficient dual
 		  /// solution method.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The number type used for costs and potentials in the
 		  /// algorithm. By default, it is the same as \c V.
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
 		  /// "CapacityScalingDefaultTraits<GR, V, C>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		  ///
 		  /// \warning Both number 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.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V, typename C, typename TR>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             typename TR = CapacityScalingDefaultTraits<GR, V, C> >
 		#endif
 		  class CapacityScaling
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef typename TR::Value Value;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
 		    /// The type of the heap used for internal Dijkstra computations
 		    typedef typename TR::Heap Heap;
 		    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// 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).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost 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.
 		      UNBOUNDED
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_idf;
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
 		    BoolVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    CostVector _pi;
 		    ValueVector _excess;
 		    IntVector _excess_nodes;
 		    IntVector _deficit_nodes;
 		    Value _delta;
 		    int _factor;
 		    IntVector _pred;
 		  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.
 		    const Value INF;
 		  private:
 		    // Special implementation of the Dijkstra algorithm for finding
 		    // shortest paths in the residual network of the digraph with
 		    // respect to the reduced arc costs and modifying the node
 		    // potentials according to the found distance labels.
 		    class ResidualDijkstra
+		    {
 		    private:
 		      int _node_num;
 		      bool _geq;
 		      const IntVector &_first_out;
 		      const IntVector &_target;
 		      const CostVector &_cost;
 		      const ValueVector &_res_cap;
 		      const ValueVector &_excess;
 		      CostVector &_pi;
 		      IntVector &_pred;
 		      IntVector _proc_nodes;
 		      CostVector _dist;
 		    public:
 		      ResidualDijkstra(CapacityScaling& cs) :
 		        _node_num(cs._node_num), _geq(cs._sum_supply < 0),
 		        _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),
 		        _res_cap(cs._res_cap), _excess(cs._excess), _pi(cs._pi),
 		        _pred(cs._pred), _dist(cs._node_num)
 		      {}
 		      int run(int s, Value delta = 1) {
 		        RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP);
 		        Heap heap(heap_cross_ref);
 		        heap.push(s, 0);
 		        _pred[s] = -1;
 		        _proc_nodes.clear();
 		        // Process nodes
 		        while (!heap.empty() && _excess[heap.top()] > -delta) {
 		          int u = heap.top(), v;
 		          Cost d = heap.prio() + _pi[u], dn;
 		          _dist[u] = heap.prio();
 		          _proc_nodes.push_back(u);
 		          heap.pop();
 		          // Traverse outgoing residual arcs
 		          int last_out = _geq ? _first_out[u+1] : _first_out[u+1] - 1;
 		          for (int a = _first_out[u]; a != last_out; ++a) {
 		            if (_res_cap[a] < delta) continue;
 		            v = _target[a];
 		            switch (heap.state(v)) {
 		              case Heap::PRE_HEAP:
 		                heap.push(v, d + _cost[a] - _pi[v]);
 		                _pred[v] = a;
 		                break;
 		              case Heap::IN_HEAP:
 		                dn = d + _cost[a] - _pi[v];
 		                if (dn < heap[v]) {
 		                  heap.decrease(v, dn);
 		                  _pred[v] = a;
+		                }
 		                break;
 		              case Heap::POST_HEAP:
 		                break;
+		            }
+		          }
+		        }
 		        if (heap.empty()) return -1;
 		        // Update potentials of processed nodes
 		        int t = heap.top();
 		        Cost dt = heap.prio();
 		        for (int i = 0; i < int(_proc_nodes.size()); ++i) {
 		          _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - dt;
+		        }
 		        return t;
+		      }
 		    }; //class ResidualDijkstra
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetHeapTraits : public Traits {
 		      typedef T Heap;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c Heap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c Heap
 		    /// type, which is used for internal Dijkstra computations.
 		    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
 		    /// its priority type must be \c Cost and its cross reference type
 		    /// must be \ref RangeMap "RangeMap<int>".
 		    template <typename T>
 		    struct SetHeap
 		      : public CapacityScaling<GR, V, C, SetHeapTraits<T> > {
 		      typedef  CapacityScaling<GR, V, C, SetHeapTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    CapacityScaling() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    CapacityScaling(const GR& graph) :
 		      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() :
 		          std::numeric_limits<Value>::max())
+		    {
 		      // Check the number types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of CapacityScaling must be signed");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 		        "The cost type of CapacityScaling must be signed");
 		      // Reset data structures
 		      reset();
+		    }
 		    /// \name Parameters
 		    /// The parameters of the algorithm can be specified using these
 		    /// functions.
 		    /// @{
 		    /// \brief Set the lower bounds on the arcs.
 		    ///
 		    /// This function sets the lower bounds on the arcs.
 		    /// If it is not used before calling \ref run(), the lower bounds
 		    /// will be set to zero on all arcs.
 		    ///
 		    /// \param map An arc map storing the lower bounds.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template <typename LowerMap>
 		    CapacityScaling& lowerMap(const LowerMap& map) {
 		      _have_lower = true;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _lower[_arc_idf[a]] = map[a];
 		        _lower[_arc_idb[a]] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the upper bounds (capacities) on the arcs.
 		    ///
 		    /// This function sets the upper bounds (capacities) on the arcs.
 		    /// If it is not used before calling \ref run(), the upper bounds
 		    /// will be set to \ref INF on all arcs (i.e. the flow value will be
 		    /// unbounded from above).
 		    ///
 		    /// \param map An arc map storing the upper bounds.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename UpperMap>
 		    CapacityScaling& upperMap(const UpperMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _upper[_arc_idf[a]] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    CapacityScaling& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _cost[_arc_idf[a]] =  map[a];
 		        _cost[_arc_idb[a]] = -map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    CapacityScaling& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
 		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \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().
 		    /// For example,
 		    /// \code
 		    ///   CapacityScaling<ListDigraph> cs(graph);
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the given parameters
 		    /// are kept for the next call, unless \ref resetParams() or \ref reset()
 		    /// is used, thus only the modified parameters have to be set again.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class (or the last \ref reset() call), then the \ref reset()
 		    /// function must be called.
 		    ///
 		    /// \param factor The capacity scaling factor. It must be larger than
 		    /// one to use scaling. If it is less or equal to one, then scaling
 		    /// will be disabled.
 		    ///
 		    /// \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),
 		    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
 		    /// 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 resetParams(), reset()
 		    ProblemType run(int factor = 4) {
 		      _factor = factor;
 		      ProblemType pt = init();
 		      if (pt != OPTIMAL) return pt;
 		      return start();
+		    }
 		    /// \brief Reset all the parameters that have been given before.
 		    ///
 		    /// This function resets all the paramaters that have been given
 		    /// before using functions \ref lowerMap(), \ref upperMap(),
 		    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    ///
 		    /// It is useful for multiple \ref run() calls. Basically, all the given
 		    /// parameters are kept for the next \ref run() call, unless
 		    /// \ref resetParams() or \ref reset() is used.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class or the last \ref reset() call, then the \ref reset()
 		    /// function must be used, otherwise \ref resetParams() is sufficient.
 		    ///
 		    /// For example,
 		    /// \code
 		    ///   CapacityScaling<ListDigraph> cs(graph);
 		    ///
 		    ///   // First run
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    ///
 		    ///   // Run again with modified cost map (resetParams() is not called,
 		    ///   // so only the cost map have to be set again)
 		    ///   cost[e] += 100;
 		    ///   cs.costMap(cost).run();
 		    ///
 		    ///   // Run again from scratch using resetParams()
 		    ///   // (the lower bounds will be set to zero on all arcs)
 		    ///   cs.resetParams();
 		    ///   cs.upperMap(capacity).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \see reset(), run()
 		    CapacityScaling& resetParams() {
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      for (int j = 0; j != _res_arc_num; ++j) {
 		        _lower[j] = 0;
 		        _upper[j] = INF;
 		        _cost[j] = _forward[j] ? 1 : -1;
+		      }
 		      _have_lower = false;
 		      return *this;
+		    }
 		    /// \brief Reset the internal data structures and all the parameters
 		    /// that have been given before.
 		    ///
 		    /// This function resets the internal data structures and all the
 		    /// paramaters that have been given before using functions \ref lowerMap(),
 		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    ///
 		    /// It is useful for multiple \ref run() calls. Basically, all the given
 		    /// parameters are kept for the next \ref run() call, unless
 		    /// \ref resetParams() or \ref reset() is used.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class or the last \ref reset() call, then the \ref reset()
 		    /// function must be used, otherwise \ref resetParams() is sufficient.
 		    ///
 		    /// See \ref resetParams() for examples.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \see resetParams(), run()
 		    CapacityScaling& reset() {
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      ++_node_num;
 		      _first_out.resize(_node_num + 1);
 		      _forward.resize(_res_arc_num);
 		      _source.resize(_res_arc_num);
 		      _target.resize(_res_arc_num);
 		      _reverse.resize(_res_arc_num);
 		      _lower.resize(_res_arc_num);
 		      _upper.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _supply.resize(_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _pi.resize(_node_num);
 		      _excess.resize(_node_num);
 		      _pred.resize(_node_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _first_out[i] = j;
 		        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idf[a] = j;
 		          _forward[j] = true;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idb[a] = j;
 		          _forward[j] = false;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        _forward[j] = false;
 		        _source[j] = i;
 		        _target[j] = _root;
 		        _reverse[j] = k;
 		        _forward[k] = true;
 		        _source[k] = _root;
 		        _target[k] = i;
 		        _reverse[k] = j;
 		        ++j; ++k;
+		      }
 		      _first_out[i] = j;
 		      _first_out[_node_num] = k;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int fi = _arc_idf[a];
 		        int bi = _arc_idb[a];
 		        _reverse[fi] = bi;
 		        _reverse[bi] = fi;
+		      }
 		      // Reset parameters
 		      resetParams();
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The \ref run() function must be called before using them.
 		    /// @{
 		    /// \brief Return the total cost of the found flow.
 		    ///
 		    /// This function returns the total cost of the found flow.
 		    /// Its complexity is O(e).
 		    ///
 		    /// \note The return type of the function can be specified as a
 		    /// template parameter. For example,
 		    /// \code
 		    ///   cs.totalCost<double>();
 		    /// \endcode
 		    /// It is useful if the total cost cannot be stored in the \c Cost
 		    /// type of the algorithm, which is the default return type of the
 		    /// function.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename Number>
 		    Number totalCost() const {
 		      Number c = 0;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int i = _arc_idb[a];
 		        c += static_cast<Number>(_res_cap[i]) *
 		             (-static_cast<Number>(_cost[i]));
+		      }
 		      return c;
+		    }
 		#ifndef DOXYGEN
 		    Cost totalCost() const {
 		      return totalCost<Cost>();
+		    }
 		#endif
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value flow(const Arc& a) const {
 		      return _res_cap[_arc_idb[a]];
+		    }
 		    /// \brief Return the flow map (the primal solution).
 		    ///
 		    /// This function copies the flow value on each arc into the given
 		    /// map. The \c Value type of the algorithm must be convertible to
 		    /// the \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename FlowMap>
 		    void flowMap(FlowMap &map) const {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        map.set(a, _res_cap[_arc_idb[a]]);
+		      }
+		    }

lemon/cost_scaling.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_COST_SCALING_H
 		#define LEMON_COST_SCALING_H
 		/// \ingroup min_cost_flow_algs
 		/// \file
 		/// \brief Cost scaling algorithm for finding a minimum cost flow.
 		#include <vector>
 		#include <deque>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/math.h>
 		#include <lemon/static_graph.h>
 		#include <lemon/circulation.h>
 		#include <lemon/bellman_ford.h>
 		namespace lemon {
 		  /// \brief Default traits class of CostScaling algorithm.
 		  ///
 		  /// Default traits class of CostScaling algorithm.
 		  /// \tparam GR Digraph type.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values. By default it is \c int.
 		  /// \tparam C The number type used for costs and potentials.
 		  /// By default it is the same as \c V.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V = int, typename C = V>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             bool integer = std::numeric_limits<C>::is_integer >
 		#endif
 		  struct CostScalingDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		    /// \brief The large cost type used for internal computations
 		    ///
 		    /// The large cost type used for internal computations.
 		    /// It is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Cost must be convertible to \c LargeCost.
 		    typedef double LargeCost;
 		  };
 		  // Default traits class for integer cost types
 		  template <typename GR, typename V, typename C>
 		  struct CostScalingDefaultTraits<GR, V, C, true>
+		  {
 		    typedef GR Digraph;
 		    typedef V Value;
 		    typedef C Cost;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeCost;
 		#else
 		    typedef long LargeCost;
 		#endif
 		  };
 		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of the Cost Scaling algorithm for
 		  /// finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref CostScaling implements a cost scaling algorithm that performs
 		  /// push/augment and relabel operations for finding a \ref min_cost_flow
 		  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
 		  /// \ref goldberg97efficient, \ref bunnagel98efficient.
 		  /// It is a highly efficient primal-dual solution method, which
 		  /// can be viewed as the generalization of the \ref Preflow
 		  /// "preflow push-relabel" algorithm for the maximum flow problem.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The number type used for costs and potentials in the
 		  /// algorithm. By default, it is the same as \c V.
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref CostScalingDefaultTraits
 		  /// "CostScalingDefaultTraits<GR, V, C>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		  ///
 		  /// \warning Both number 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> >
 		#endif
 		  class CostScaling
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef typename TR::Value Value;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
 		    /// \brief The large cost type
 		    ///
 		    /// The large cost type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeCost LargeCost;
 		    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// 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).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost 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.
 		      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;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<LargeCost> LargeCostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		  private:
 		    template <typename KT, typename VT>
 		    class StaticVectorMap {
 		    public:
 		      typedef KT Key;
 		      typedef VT Value;
 		      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
 		      const Value& operator[](const Key& key) const {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      Value& operator[](const Key& key) {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      void set(const Key& key, const Value& val) {
 		        _v[StaticDigraph::id(key)] = val;
+		      }
 		    private:
 		      std::vector<Value>& _v;
 		    };
 		    typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
 		    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _res_node_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    int _sup_node_num;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_idf;
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
 		    BoolVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _scost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    LargeCostVector _cost;
 		    LargeCostVector _pi;
 		    ValueVector _excess;
 		    IntVector _next_out;
 		    std::deque<int> _active_nodes;
 		    // Data for scaling
 		    LargeCost _epsilon;
 		    int _alpha;
 		    IntVector _buckets;
 		    IntVector _bucket_next;
 		    IntVector _bucket_prev;
 		    IntVector _rank;
 		    int _max_rank;
 		    // Data for a StaticDigraph structure
 		    typedef std::pair<int, int> IntPair;
 		    StaticDigraph _sgr;
 		    std::vector<IntPair> _arc_vec;
 		    std::vector<LargeCost> _cost_vec;
 		    LargeCostArcMap _cost_map;
 		    LargeCostNodeMap _pi_map;
 		  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.
 		    const Value INF;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeCostTraits : public Traits {
 		      typedef T LargeCost;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeCost type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
 		    /// type, which is used for internal computations in the algorithm.
 		    /// \c Cost must be convertible to \c LargeCost.
 		    template <typename T>
 		    struct SetLargeCost
 		      : public CostScaling<GR, V, C, SetLargeCostTraits<T> > {
 		      typedef  CostScaling<GR, V, C, SetLargeCostTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    CostScaling() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    CostScaling(const GR& graph) :
 		      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
 		      _cost_map(_cost_vec), _pi_map(_pi),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() :
 		          std::numeric_limits<Value>::max())
+		    {
 		      // Check the number types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of CostScaling must be signed");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 		        "The cost type of CostScaling must be signed");
 		      // Reset data structures
 		      reset();
+		    }
 		    /// \name Parameters
 		    /// The parameters of the algorithm can be specified using these
 		    /// functions.
 		    /// @{
 		    /// \brief Set the lower bounds on the arcs.
 		    ///
 		    /// This function sets the lower bounds on the arcs.
 		    /// If it is not used before calling \ref run(), the lower bounds
 		    /// will be set to zero on all arcs.
 		    ///
 		    /// \param map An arc map storing the lower bounds.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template <typename LowerMap>
 		    CostScaling& lowerMap(const LowerMap& map) {
 		      _have_lower = true;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _lower[_arc_idf[a]] = map[a];
 		        _lower[_arc_idb[a]] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the upper bounds (capacities) on the arcs.
 		    ///
 		    /// This function sets the upper bounds (capacities) on the arcs.
 		    /// If it is not used before calling \ref run(), the upper bounds
 		    /// will be set to \ref INF on all arcs (i.e. the flow value will be
 		    /// unbounded from above).
 		    ///
 		    /// \param map An arc map storing the upper bounds.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename UpperMap>
 		    CostScaling& upperMap(const UpperMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _upper[_arc_idf[a]] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    CostScaling& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _scost[_arc_idf[a]] =  map[a];
 		        _scost[_arc_idb[a]] = -map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    CostScaling& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
 		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \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().
 		    /// For example,
 		    /// \code
 		    ///   CostScaling<ListDigraph> cs(graph);
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the given parameters
 		    /// are kept for the next call, unless \ref resetParams() or \ref reset()
 		    /// is used, thus only the modified parameters have to be set again.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class (or the last \ref reset() call), then the \ref reset()
 		    /// function must be called.
 		    ///
 		    /// \param method The internal method that will be used in the
 		    /// algorithm. For more information, see \ref Method.
 		    /// \param factor The cost scaling factor. It must be larger than one.
 		    ///
 		    /// \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),
 		    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
 		    /// 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, Method
 		    /// \see resetParams(), reset()
 		    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
 		      _alpha = factor;
 		      ProblemType pt = init();
 		      if (pt != OPTIMAL) return pt;
 		      start(method);
 		      return OPTIMAL;
+		    }
 		    /// \brief Reset all the parameters that have been given before.
 		    ///
 		    /// This function resets all the paramaters that have been given
 		    /// before using functions \ref lowerMap(), \ref upperMap(),
 		    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    ///
 		    /// It is useful for multiple \ref run() calls. Basically, all the given
 		    /// parameters are kept for the next \ref run() call, unless
 		    /// \ref resetParams() or \ref reset() is used.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class or the last \ref reset() call, then the \ref reset()
 		    /// function must be used, otherwise \ref resetParams() is sufficient.
 		    ///
 		    /// For example,
 		    /// \code
 		    ///   CostScaling<ListDigraph> cs(graph);
 		    ///
 		    ///   // First run
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    ///
 		    ///   // Run again with modified cost map (resetParams() is not called,
 		    ///   // so only the cost map have to be set again)
 		    ///   cost[e] += 100;
 		    ///   cs.costMap(cost).run();
 		    ///
 		    ///   // Run again from scratch using resetParams()
 		    ///   // (the lower bounds will be set to zero on all arcs)
 		    ///   cs.resetParams();
 		    ///   cs.upperMap(capacity).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \see reset(), run()
 		    CostScaling& resetParams() {
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      int limit = _first_out[_root];
 		      for (int j = 0; j != limit; ++j) {
 		        _lower[j] = 0;
 		        _upper[j] = INF;
 		        _scost[j] = _forward[j] ? 1 : -1;
+		      }
 		      for (int j = limit; j != _res_arc_num; ++j) {
 		        _lower[j] = 0;
 		        _upper[j] = INF;
 		        _scost[j] = 0;
 		        _scost[_reverse[j]] = 0;
+		      }
 		      _have_lower = false;
 		      return *this;
+		    }
 		    /// \brief Reset all the parameters that have been given before.
 		    ///
 		    /// This function resets all the paramaters that have been given
 		    /// before using functions \ref lowerMap(), \ref upperMap(),
 		    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    ///
 		    /// It is useful for multiple run() calls. If this function is not
 		    /// used, all the parameters given before are kept for the next
 		    /// \ref run() call.
 		    /// However, the underlying digraph must not be modified after this
 		    /// class have been constructed, since it copies and extends the graph.
 		    /// \return <tt>(*this)</tt>
 		    CostScaling& reset() {
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      _res_node_num = _node_num + 1;
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      _first_out.resize(_res_node_num + 1);
 		      _forward.resize(_res_arc_num);
 		      _source.resize(_res_arc_num);
 		      _target.resize(_res_arc_num);
 		      _reverse.resize(_res_arc_num);
 		      _lower.resize(_res_arc_num);
 		      _upper.resize(_res_arc_num);
 		      _scost.resize(_res_arc_num);
 		      _supply.resize(_res_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _pi.resize(_res_node_num);
 		      _excess.resize(_res_node_num);
 		      _next_out.resize(_res_node_num);
 		      _arc_vec.reserve(_res_arc_num);
 		      _cost_vec.reserve(_res_arc_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _first_out[i] = j;
 		        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idf[a] = j;
 		          _forward[j] = true;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idb[a] = j;
 		          _forward[j] = false;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        _forward[j] = false;
 		        _source[j] = i;
 		        _target[j] = _root;
 		        _reverse[j] = k;
 		        _forward[k] = true;
 		        _source[k] = _root;
 		        _target[k] = i;
 		        _reverse[k] = j;
 		        ++j; ++k;
+		      }
 		      _first_out[i] = j;
 		      _first_out[_res_node_num] = k;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int fi = _arc_idf[a];
 		        int bi = _arc_idb[a];
 		        _reverse[fi] = bi;
 		        _reverse[bi] = fi;
+		      }
 		      // Reset parameters
 		      resetParams();
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The \ref run() function must be called before using them.
 		    /// @{
 		    /// \brief Return the total cost of the found flow.
 		    ///
 		    /// This function returns the total cost of the found flow.
 		    /// Its complexity is O(e).
 		    ///
 		    /// \note The return type of the function can be specified as a
 		    /// template parameter. For example,
 		    /// \code
 		    ///   cs.totalCost<double>();
 		    /// \endcode
 		    /// It is useful if the total cost cannot be stored in the \c Cost
 		    /// type of the algorithm, which is the default return type of the
 		    /// function.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename Number>
 		    Number totalCost() const {
 		      Number c = 0;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int i = _arc_idb[a];
 		        c += static_cast<Number>(_res_cap[i]) *
 		             (-static_cast<Number>(_scost[i]));
+		      }
 		      return c;
+		    }
 		#ifndef DOXYGEN
 		    Cost totalCost() const {
 		      return totalCost<Cost>();
+		    }
 		#endif
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value flow(const Arc& a) const {
 		      return _res_cap[_arc_idb[a]];
+		    }
 		    /// \brief Return the flow map (the primal solution).
 		    ///
 		    /// This function copies the flow value on each arc into the given
 		    /// map. The \c Value type of the algorithm must be convertible to
 		    /// the \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename FlowMap>

lemon/hartmann_orlin.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_HARTMANN_ORLIN_H
 		#define LEMON_HARTMANN_ORLIN_H
 		/// \ingroup min_mean_cycle
 		///
 		/// \file
 		/// \brief Hartmann-Orlin's algorithm for finding a minimum mean cycle.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
 		  /// \brief Default traits class of HartmannOrlin algorithm.
 		  ///
 		  /// Default traits class of HartmannOrlin algorithm.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		#endif
 		  struct HartmannOrlinDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// \brief The large value type used for internal computations
 		    ///
 		    /// The large value type used for internal computations.
 		    /// It is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// The tolerance type used for internal computations
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addFront() function.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
 		  struct HartmannOrlinDefaultTraits<GR, LEN, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \addtogroup min_mean_cycle
 		  /// @{
 		  /// \brief Implementation of the Hartmann-Orlin algorithm for finding
 		  /// a minimum mean cycle.
 		  ///
 		  /// This class implements the Hartmann-Orlin algorithm for finding
 		  /// a directed cycle of minimum mean length (cost) in a digraph
 		  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
 		  /// It is an improved version of \ref Karp "Karp"'s original algorithm,
 		  /// it applies an efficient early termination scheme.
 		  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam LEN The type of the length map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits
 		  /// "HartmannOrlinDefaultTraits<GR, LEN>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = HartmannOrlinDefaultTraits<GR, LEN> >
 		#endif
 		  class HartmannOrlin
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename TR::Value Value;
 		    /// \brief The large value type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeValue LargeValue;
 		    /// The tolerance type
 		    typedef typename TR::Tolerance Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
 		    typedef typename TR::Path Path;
 		    /// The \ref HartmannOrlinDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    // Data sturcture for path data
 		    struct PathData
+		    {
 		      LargeValue dist;
 		      Arc pred;
 		      PathData(LargeValue d, Arc p = INVALID) :
 		        dist(d), pred(p) {}
 		    };
 		    typedef typename Digraph::template NodeMap<std::vector<PathData> >
 		      PathDataNodeMap;
 		  private:
 		    // The digraph the algorithm runs on
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // Data for storing the strongly connected components
 		    int _comp_num;
 		    typename Digraph::template NodeMap<int> _comp;
 		    std::vector<std::vector<Node> > _comp_nodes;
 		    std::vector<Node>* _nodes;
 		    typename Digraph::template NodeMap<std::vector<Arc> > _out_arcs;
 		    // Data for the found cycles
 		    bool _curr_found, _best_found;
 		    LargeValue _curr_length, _best_length;
 		    int _curr_size, _best_size;
 		    Node _curr_node, _best_node;
 		    int _curr_level, _best_level;
 		    Path *_cycle_path;
 		    bool _local_path;
 		    // Node map for storing path data
 		    PathDataNodeMap _data;
 		    // The processed nodes in the last round
 		    std::vector<Node> _process;
 		    Tolerance _tolerance;
 		    // Infinite constant
 		    const LargeValue INF;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		      typedef lemon::Tolerance<T> Tolerance;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeValue type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > {
 		      typedef HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPathTraits : public Traits {
 		      typedef T Path;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c %Path type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting the \c %Path
 		    /// type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addFront() function.
 		    template <typename T>
 		    struct SetPath
 		      : public HartmannOrlin<GR, LEN, SetPathTraits<T> > {
 		      typedef HartmannOrlin<GR, LEN, SetPathTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    HartmannOrlin() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param length The lengths (costs) of the arcs.
 		    HartmannOrlin( const Digraph &digraph,
 		                   const LengthMap &length ) :
 		      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
 		      _best_found(false), _best_length(0), _best_size(1),
 		      _cycle_path(NULL), _local_path(false), _data(digraph),
 		      INF(std::numeric_limits<LargeValue>::has_infinity ?
 		          std::numeric_limits<LargeValue>::infinity() :
 		          std::numeric_limits<LargeValue>::max())
 		    {}
 		    /// Destructor.
 		    ~HartmannOrlin() {
 		      if (_local_path) delete _cycle_path;
+		    }
 		    /// \brief Set the path structure for storing the found cycle.
 		    ///
 		    /// This function sets an external path structure for storing the
 		    /// found cycle.
 		    ///
 		    /// If you don't call this function before calling \ref run() or
 		    /// \ref findMinMean(), it will allocate a local \ref Path "path"
 		    /// structure. The destuctor deallocates this automatically
 		    /// allocated object, of course.
 		    ///
 		    /// \note The algorithm calls only the \ref lemon::Path::addFront()
 		    /// "addFront()" function of the given path structure.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    HartmannOrlin& cycle(Path &path) {
 		      if (_local_path) {
 		        delete _cycle_path;
 		        _local_path = false;
+		      }
 		      _cycle_path = &path;
 		      return *this;
+		    }
 		    /// \brief Set the tolerance used by the algorithm.
 		    ///
 		    /// This function sets the tolerance object used by the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    HartmannOrlin& tolerance(const Tolerance& tolerance) {
 		      _tolerance = tolerance;
 		      return *this;
+		    }
 		    /// \brief Return a const reference to the tolerance.
 		    ///
 		    /// This function returns a const reference to the tolerance object
 		    /// used by the algorithm.
 		    const Tolerance& tolerance() const {
 		      return _tolerance;
+		    }
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to call the \ref run()
 		    /// function.\n
 		    /// If you only need the minimum mean length, you may call
 		    /// \ref findMinMean().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// It can be called more than once (e.g. if the underlying digraph
 		    /// and/or the arc lengths have been modified).
 		    ///
 		    /// \return \c true if a directed cycle exists in the digraph.
 		    ///
 		    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   return mmc.findMinMean() && mmc.findCycle();
 		    /// \endcode
 		    bool run() {
 		      return findMinMean() && findCycle();
+		    }
 		    /// \brief Find the minimum cycle mean.
 		    ///
 		    /// This function finds the minimum mean length of the directed
 		    /// cycles in the digraph.
 		    ///
 		    /// \return \c true if a directed cycle exists in the digraph.
 		    bool findMinMean() {
 		      // Initialization and find strongly connected components
 		      init();
 		      findComponents();
 		      // Find the minimum cycle mean in the components
 		      for (int comp = 0; comp < _comp_num; ++comp) {
 		        if (!initComponent(comp)) continue;
 		        processRounds();
 		        // Update the best cycle (global minimum mean cycle)
 		        if ( _curr_found && (!_best_found ||
 		             _curr_length * _best_size < _best_length * _curr_size) ) {
 		          _best_found = true;
 		          _best_length = _curr_length;
 		          _best_size = _curr_size;
 		          _best_node = _curr_node;
 		          _best_level = _curr_level;
+		        }
+		      }
 		      return _best_found;
+		    }
 		    /// \brief Find a minimum mean directed cycle.
 		    ///
 		    /// This function finds a directed cycle of minimum mean length
 		    /// in the digraph using the data computed by findMinMean().
 		    ///
 		    /// \return \c true if a directed cycle exists in the digraph.
 		    ///
 		    /// \pre \ref findMinMean() must be called before using this function.
 		    bool findCycle() {
 		      if (!_best_found) return false;
 		      IntNodeMap reached(_gr, -1);
 		      int r = _best_level + 1;
 		      Node u = _best_node;
 		      while (reached[u] < 0) {
 		        reached[u] = --r;
 		        u = _gr.source(_data[u][r].pred);
+		      }
 		      r = reached[u];
 		      Arc e = _data[u][r].pred;
 		      _cycle_path->addFront(e);
 		      _best_length = _length[e];
 		      _best_size = 1;
 		      Node v;
 		      while ((v = _gr.source(e)) != u) {
 		        e = _data[v][--r].pred;
 		        _cycle_path->addFront(e);
 		        _best_length += _length[e];
 		        ++_best_size;
+		      }
 		      return true;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The algorithm should be executed before using them.
 		    /// @{
 		    /// \brief Return the total length of the found cycle.
 		    ///
 		    /// This function returns the total length of the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
 		    Value cycleLength() const {
 		      return static_cast<Value>(_best_length);
+		    }
 		    /// \brief Return the number of arcs on the found cycle.
 		    ///
 		    /// This function returns the number of arcs on the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
 		    int cycleArcNum() const {
 		      return _best_size;
+		    }
 		    /// \brief Return the mean length of the found cycle.
 		    ///
 		    /// This function returns the mean length of the found cycle.
 		    ///
 		    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
 		    /// following code.
 		    /// \code
 		    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
 		    /// \endcode
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
 		    double cycleMean() const {
 		      return static_cast<double>(_best_length) / _best_size;
+		    }
 		    /// \brief Return the found cycle.
 		    ///
 		    /// This function returns a const reference to the path structure
 		    /// storing the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findCycle() must be called before using
 		    /// this function.
 		    const Path& cycle() const {
 		      return *_cycle_path;
+		    }
 		    ///@}
 		  private:
 		    // Initialization
 		    void init() {
 		      if (!_cycle_path) {
 		        _local_path = true;
 		        _cycle_path = new Path;
+		      }
 		      _cycle_path->clear();
 		      _best_found = false;
 		      _best_length = 0;
 		      _best_size = 1;
 		      _cycle_path->clear();
 		      for (NodeIt u(_gr); u != INVALID; ++u)
 		        _data[u].clear();
+		    }
 		    // Find strongly connected components and initialize _comp_nodes
 		    // and _out_arcs
 		    void findComponents() {
 		      _comp_num = stronglyConnectedComponents(_gr, _comp);
 		      _comp_nodes.resize(_comp_num);
 		      if (_comp_num == 1) {
 		        _comp_nodes[0].clear();
 		        for (NodeIt n(_gr); n != INVALID; ++n) {
 		          _comp_nodes[0].push_back(n);
 		          _out_arcs[n].clear();
 		          for (OutArcIt a(_gr, n); a != INVALID; ++a) {
 		            _out_arcs[n].push_back(a);
+		          }
+		        }
 		      } else {
 		        for (int i = 0; i < _comp_num; ++i)
 		          _comp_nodes[i].clear();
 		        for (NodeIt n(_gr); n != INVALID; ++n) {
 		          int k = _comp[n];
 		          _comp_nodes[k].push_back(n);
 		          _out_arcs[n].clear();
 		          for (OutArcIt a(_gr, n); a != INVALID; ++a) {
 		            if (_comp[_gr.target(a)] == k) _out_arcs[n].push_back(a);
+		          }
+		        }
+		      }
+		    }
 		    // Initialize path data for the current component
 		    bool initComponent(int comp) {
 		      _nodes = &(_comp_nodes[comp]);
 		      int n = _nodes->size();
 		      if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
 		        return false;
+		      }
 		      for (int i = 0; i < n; ++i) {
 		        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
+		      }
 		      return true;
+		    }
 		    // Process all rounds of computing path data for the current component.
 		    // _data[v][k] is the length of a shortest directed walk from the root
 		    // node to node v containing exactly k arcs.
 		    void processRounds() {
 		      Node start = (*_nodes)[0];
 		      _data[start][0] = PathData(0);
 		      _process.clear();
 		      _process.push_back(start);
 		      int k, n = _nodes->size();
 		      int next_check = 4;
 		      bool terminate = false;
 		      for (k = 1; k <= n && int(_process.size()) < n && !terminate; ++k) {
 		        processNextBuildRound(k);
 		        if (k == next_check || k == n) {
 		          terminate = checkTermination(k);
 		          next_check = next_check * 3 / 2;
+		        }
+		      }
 		      for ( ; k <= n && !terminate; ++k) {
 		        processNextFullRound(k);
 		        if (k == next_check || k == n) {
 		          terminate = checkTermination(k);
 		          next_check = next_check * 3 / 2;
+		        }
+		      }
+		    }
 		    // Process one round and rebuild _process
 		    void processNextBuildRound(int k) {
 		      std::vector<Node> next;
 		      Node u, v;
 		      Arc e;
 		      LargeValue d;
 		      for (int i = 0; i < int(_process.size()); ++i) {
 		        u = _process[i];
 		        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
 		          e = _out_arcs[u][j];
 		          v = _gr.target(e);
 		          d = _data[u][k-1].dist + _length[e];
 		          if (_tolerance.less(d, _data[v][k].dist)) {
 		            if (_data[v][k].dist == INF) next.push_back(v);
 		            _data[v][k] = PathData(d, e);
+		          }
+		        }
+		      }
 		      _process.swap(next);
+		    }
 		    // Process one round using _nodes instead of _process
 		    void processNextFullRound(int k) {
 		      Node u, v;
 		      Arc e;
 		      LargeValue d;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        u = (*_nodes)[i];
 		        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
 		          e = _out_arcs[u][j];
 		          v = _gr.target(e);
 		          d = _data[u][k-1].dist + _length[e];
 		          if (_tolerance.less(d, _data[v][k].dist)) {
 		            _data[v][k] = PathData(d, e);
+		          }
+		        }
+		      }
+		    }
 		    // Check early termination
 		    bool checkTermination(int k) {
 		      typedef std::pair<int, int> Pair;
 		      typename GR::template NodeMap<Pair> level(_gr, Pair(-1, 0));
 		      typename GR::template NodeMap<LargeValue> pi(_gr);
 		      int n = _nodes->size();
 		      LargeValue length;
 		      int size;
 		      Node u;
 		      // Search for cycles that are already found
 		      _curr_found = false;
 		      for (int i = 0; i < n; ++i) {
 		        u = (*_nodes)[i];
 		        if (_data[u][k].dist == INF) continue;
 		        for (int j = k; j >= 0; --j) {
 		          if (level[u].first == i && level[u].second > 0) {
 		            // A cycle is found
 		            length = _data[u][level[u].second].dist - _data[u][j].dist;
 		            size = level[u].second - j;
 		            if (!_curr_found || length * _curr_size < _curr_length * size) {
 		              _curr_length = length;
 		              _curr_size = size;
 		              _curr_node = u;
 		              _curr_level = level[u].second;
 		              _curr_found = true;
+		            }
+		          }
 		          level[u] = Pair(i, j);
 		          if (j != 0) {
 			    u = _gr.source(_data[u][j].pred);
+			  }
+		        }
+		      }
 		      // If at least one cycle is found, check the optimality condition
 		      LargeValue d;
 		      if (_curr_found && k < n) {
 		        // Find node potentials
 		        for (int i = 0; i < n; ++i) {
 		          u = (*_nodes)[i];
 		          pi[u] = INF;
 		          for (int j = 0; j <= k; ++j) {
 		            if (_data[u][j].dist < INF) {
 		              d = _data[u][j].dist * _curr_size - j * _curr_length;
 		              if (_tolerance.less(d, pi[u])) pi[u] = d;
+		            }
+		          }
+		        }
 		        // Check the optimality condition for all arcs
 		        bool done = true;

lemon/howard.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_HOWARD_H
 		#define LEMON_HOWARD_H
 		/// \ingroup min_mean_cycle
 		///
 		/// \file
 		/// \brief Howard's algorithm for finding a minimum mean cycle.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
 		  /// \brief Default traits class of Howard class.
 		  ///
 		  /// Default traits class of Howard class.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		#endif
 		  struct HowardDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// \brief The large value type used for internal computations
 		    ///
 		    /// The large value type used for internal computations.
 		    /// It is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// The tolerance type used for internal computations
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
 		  struct HowardDefaultTraits<GR, LEN, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \addtogroup min_mean_cycle
 		  /// @{
 		  /// \brief Implementation of Howard's algorithm for finding a minimum
 		  /// mean cycle.
 		  ///
 		  /// This class implements Howard's policy iteration algorithm for finding
 		  /// a directed cycle of minimum mean length (cost) in a digraph
 		  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
 		  /// This class provides the most efficient algorithm for the
 		  /// minimum mean cycle problem, though the best known theoretical
 		  /// bound on its running time is exponential.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam LEN The type of the length map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref HowardDefaultTraits
 		  /// "HowardDefaultTraits<GR, LEN>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = HowardDefaultTraits<GR, LEN> >
 		#endif
 		  class Howard
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename TR::Value Value;
 		    /// \brief The large value type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeValue LargeValue;
 		    /// The tolerance type
 		    typedef typename TR::Tolerance Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// Using the \ref HowardDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
 		    typedef typename TR::Path Path;
 		    /// The \ref HowardDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    // The digraph the algorithm runs on
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // Data for the found cycles
 		    bool _curr_found, _best_found;
 		    LargeValue _curr_length, _best_length;
 		    int _curr_size, _best_size;
 		    Node _curr_node, _best_node;
 		    Path *_cycle_path;
 		    bool _local_path;
 		    // Internal data used by the algorithm
 		    typename Digraph::template NodeMap<Arc> _policy;
 		    typename Digraph::template NodeMap<bool> _reached;
 		    typename Digraph::template NodeMap<int> _level;
 		    typename Digraph::template NodeMap<LargeValue> _dist;
 		    // Data for storing the strongly connected components
 		    int _comp_num;
 		    typename Digraph::template NodeMap<int> _comp;
 		    std::vector<std::vector<Node> > _comp_nodes;
 		    std::vector<Node>* _nodes;
 		    typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
 		    // Queue used for BFS search
 		    std::vector<Node> _queue;
 		    int _qfront, _qback;
 		    Tolerance _tolerance;
 		    // Infinite constant
 		    const LargeValue INF;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		      typedef lemon::Tolerance<T> Tolerance;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeValue type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public Howard<GR, LEN, SetLargeValueTraits<T> > {
 		      typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPathTraits : public Traits {
 		      typedef T Path;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c %Path type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting the \c %Path
 		    /// type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    template <typename T>
 		    struct SetPath
 		      : public Howard<GR, LEN, SetPathTraits<T> > {
 		      typedef Howard<GR, LEN, SetPathTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Howard() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param length The lengths (costs) of the arcs.
 		    Howard( const Digraph &digraph,
 		            const LengthMap &length ) :
 		      _gr(digraph), _length(length), _best_found(false),
 		      _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false),
 		      _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
 		      _comp(digraph), _in_arcs(digraph),
 		      INF(std::numeric_limits<LargeValue>::has_infinity ?
 		          std::numeric_limits<LargeValue>::infinity() :
 		          std::numeric_limits<LargeValue>::max())
 		    {}
 		    /// Destructor.
 		    ~Howard() {
 		      if (_local_path) delete _cycle_path;
+		    }
 		    /// \brief Set the path structure for storing the found cycle.
 		    ///
 		    /// This function sets an external path structure for storing the
 		    /// found cycle.
 		    ///
 		    /// If you don't call this function before calling \ref run() or
 		    /// \ref findMinMean(), it will allocate a local \ref Path "path"
 		    /// structure. The destuctor deallocates this automatically
 		    /// allocated object, of course.
 		    ///
 		    /// \note The algorithm calls only the \ref lemon::Path::addBack()
 		    /// "addBack()" function of the given path structure.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    Howard& cycle(Path &path) {
 		      if (_local_path) {
 		        delete _cycle_path;
 		        _local_path = false;
+		      }
 		      _cycle_path = &path;
 		      return *this;
+		    }
 		    /// \brief Set the tolerance used by the algorithm.
 		    ///
 		    /// This function sets the tolerance object used by the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    Howard& tolerance(const Tolerance& tolerance) {
 		      _tolerance = tolerance;
 		      return *this;
+		    }
 		    /// \brief Return a const reference to the tolerance.
 		    ///
 		    /// This function returns a const reference to the tolerance object
 		    /// used by the algorithm.
 		    const Tolerance& tolerance() const {
 		      return _tolerance;
+		    }
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to call the \ref run()
 		    /// function.\n
 		    /// If you only need the minimum mean length, you may call
 		    /// \ref findMinMean().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// It can be called more than once (e.g. if the underlying digraph
 		    /// and/or the arc lengths have been modified).
 		    ///
 		    /// \return \c true if a directed cycle exists in the digraph.
 		    ///
 		    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   return mmc.findMinMean() && mmc.findCycle();
 		    /// \endcode
 		    bool run() {
 		      return findMinMean() && findCycle();
+		    }
 		    /// \brief Find the minimum cycle mean.
 		    ///
 		    /// This function finds the minimum mean length of the directed
 		    /// cycles in the digraph.
 		    ///
 		    /// \return \c true if a directed cycle exists in the digraph.
 		    bool findMinMean() {
 		      // Initialize and find strongly connected components
 		      init();
 		      findComponents();
 		      // Find the minimum cycle mean in the components
 		      for (int comp = 0; comp < _comp_num; ++comp) {
 		        // Find the minimum mean cycle in the current component
 		        if (!buildPolicyGraph(comp)) continue;
 		        while (true) {
 		          findPolicyCycle();
 		          if (!computeNodeDistances()) break;
+		        }
 		        // Update the best cycle (global minimum mean cycle)
 		        if ( _curr_found && (!_best_found ||
 		             _curr_length * _best_size < _best_length * _curr_size) ) {
 		          _best_found = true;
 		          _best_length = _curr_length;
 		          _best_size = _curr_size;
 		          _best_node = _curr_node;
+		        }
+		      }
 		      return _best_found;
+		    }
 		    /// \brief Find a minimum mean directed cycle.
 		    ///
 		    /// This function finds a directed cycle of minimum mean length
 		    /// in the digraph using the data computed by findMinMean().
 		    ///
 		    /// \return \c true if a directed cycle exists in the digraph.
 		    ///
 		    /// \pre \ref findMinMean() must be called before using this function.
 		    bool findCycle() {
 		      if (!_best_found) return false;
 		      _cycle_path->addBack(_policy[_best_node]);
 		      for ( Node v = _best_node;
 		            (v = _gr.target(_policy[v])) != _best_node; ) {
 		        _cycle_path->addBack(_policy[v]);
+		      }
 		      return true;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The algorithm should be executed before using them.
 		    /// @{
 		    /// \brief Return the total length of the found cycle.
 		    ///
 		    /// This function returns the total length of the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
 		    Value cycleLength() const {
 		      return static_cast<Value>(_best_length);
+		    }
 		    /// \brief Return the number of arcs on the found cycle.
 		    ///
 		    /// This function returns the number of arcs on the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
 		    int cycleArcNum() const {
 		      return _best_size;
+		    }
 		    /// \brief Return the mean length of the found cycle.
 		    ///
 		    /// This function returns the mean length of the found cycle.
 		    ///
 		    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
 		    /// following code.
 		    /// \code
 		    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
 		    /// \endcode
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
 		    double cycleMean() const {
 		      return static_cast<double>(_best_length) / _best_size;
+		    }
 		    /// \brief Return the found cycle.
 		    ///
 		    /// This function returns a const reference to the path structure
 		    /// storing the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findCycle() must be called before using
 		    /// this function.
 		    const Path& cycle() const {
 		      return *_cycle_path;
+		    }
 		    ///@}
 		  private:
 		    // Initialize
 		    void init() {
 		      if (!_cycle_path) {
 		        _local_path = true;
 		        _cycle_path = new Path;
+		      }
 		      _queue.resize(countNodes(_gr));
 		      _best_found = false;
 		      _best_length = 0;
 		      _best_size = 1;
 		      _cycle_path->clear();
+		    }
 		    // Find strongly connected components and initialize _comp_nodes
 		    // and _in_arcs
 		    void findComponents() {
 		      _comp_num = stronglyConnectedComponents(_gr, _comp);
 		      _comp_nodes.resize(_comp_num);
 		      if (_comp_num == 1) {
 		        _comp_nodes[0].clear();
 		        for (NodeIt n(_gr); n != INVALID; ++n) {
 		          _comp_nodes[0].push_back(n);
 		          _in_arcs[n].clear();
 		          for (InArcIt a(_gr, n); a != INVALID; ++a) {
 		            _in_arcs[n].push_back(a);
+		          }
+		        }
 		      } else {
 		        for (int i = 0; i < _comp_num; ++i)
 		          _comp_nodes[i].clear();
 		        for (NodeIt n(_gr); n != INVALID; ++n) {
 		          int k = _comp[n];
 		          _comp_nodes[k].push_back(n);
 		          _in_arcs[n].clear();
 		          for (InArcIt a(_gr, n); a != INVALID; ++a) {
 		            if (_comp[_gr.source(a)] == k) _in_arcs[n].push_back(a);
+		          }
+		        }
+		      }
+		    }
 		    // Build the policy graph in the given strongly connected component
 		    // (the out-degree of every node is 1)
 		    bool buildPolicyGraph(int comp) {
 		      _nodes = &(_comp_nodes[comp]);
 		      if (_nodes->size() < 1 ||
 		          (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
 		        return false;
+		      }
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        _dist[(*_nodes)[i]] = INF;
+		      }
 		      Node u, v;
 		      Arc e;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        v = (*_nodes)[i];
 		        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
 		          e = _in_arcs[v][j];
 		          u = _gr.source(e);
 		          if (_length[e] < _dist[u]) {
 		            _dist[u] = _length[e];
 		            _policy[u] = e;
+		          }
+		        }
+		      }
 		      return true;
+		    }
 		    // Find the minimum mean cycle in the policy graph
 		    void findPolicyCycle() {
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        _level[(*_nodes)[i]] = -1;
+		      }
 		      LargeValue clength;
 		      int csize;
 		      Node u, v;
 		      _curr_found = false;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        u = (*_nodes)[i];
 		        if (_level[u] >= 0) continue;
 		        for (; _level[u] < 0; u = _gr.target(_policy[u])) {
 		          _level[u] = i;
+		        }
 		        if (_level[u] == i) {
 		          // A cycle is found
 		          clength = _length[_policy[u]];
 		          csize = 1;
 		          for (v = u; (v = _gr.target(_policy[v])) != u; ) {
 		            clength += _length[_policy[v]];
 		            ++csize;
+		          }
 		          if ( !_curr_found ||
 		               (clength * _curr_size < _curr_length * csize) ) {
 		            _curr_found = true;
 		            _curr_length = clength;
 		            _curr_size = csize;
 		            _curr_node = u;
+		          }
+		        }
+		      }
+		    }
 		    // Contract the policy graph and compute node distances
 		    bool computeNodeDistances() {
 		      // Find the component of the main cycle and compute node distances
 		      // using reverse BFS
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        _reached[(*_nodes)[i]] = false;
+		      }
 		      _qfront = _qback = 0;
 		      _queue[0] = _curr_node;
 		      _reached[_curr_node] = true;
 		      _dist[_curr_node] = 0;
 		      Node u, v;
 		      Arc e;
 		      while (_qfront <= _qback) {
 		        v = _queue[_qfront++];
 		        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
 		          e = _in_arcs[v][j];
 		          u = _gr.source(e);
 		          if (_policy[u] == e && !_reached[u]) {
 		            _reached[u] = true;
 		            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
 		            _queue[++_qback] = u;
+		          }
+		        }
+		      }
 		      // Connect all other nodes to this component and compute node
 		      // distances using reverse BFS
 		      _qfront = 0;
 		      while (_qback < int(_nodes->size())-1) {
 		        v = _queue[_qfront++];
 		        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
 		          e = _in_arcs[v][j];
 		          u = _gr.source(e);
 		          if (!_reached[u]) {
 		            _reached[u] = true;
 		            _policy[u] = e;
 		            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
 		            _queue[++_qback] = u;
+		          }
+		        }
+		      }
 		      // Improve node distances
 		      bool improved = false;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        v = (*_nodes)[i];
 		        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
 		          e = _in_arcs[v][j];
 		          u = _gr.source(e);
 		          LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
 		          if (_tolerance.less(delta, _dist[u])) {
 		            _dist[u] = delta;
 		            _policy[u] = e;
 		            improved = true;
+		          }
+		        }
+		      }
 		      return improved;
+		    }
 		  }; //class Howard
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_HOWARD_H

lemon/karp.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_KARP_H
 		#define LEMON_KARP_H
 		/// \ingroup min_mean_cycle
 		///
 		/// \file
 		/// \brief Karp's algorithm for finding a minimum mean cycle.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
 		  /// \brief Default traits class of Karp algorithm.
 		  ///
 		  /// Default traits class of Karp algorithm.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		#endif
 		  struct KarpDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// \brief The large value type used for internal computations
 		    ///
 		    /// The large value type used for internal computations.
 		    /// It is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// The tolerance type used for internal computations
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addFront() function.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
 		  struct KarpDefaultTraits<GR, LEN, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \addtogroup min_mean_cycle
 		  /// @{
 		  /// \brief Implementation of Karp's algorithm for finding a minimum
 		  /// mean cycle.
 		  ///
 		  /// This class implements Karp's algorithm for finding a directed
 		  /// cycle of minimum mean length (cost) in a digraph
 		  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
 		  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam LEN The type of the length map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref KarpDefaultTraits
 		  /// "KarpDefaultTraits<GR, LEN>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = KarpDefaultTraits<GR, LEN> >
 		#endif
 		  class Karp
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename TR::Value Value;
 		    /// \brief The large value type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeValue LargeValue;
 		    /// The tolerance type
 		    typedef typename TR::Tolerance Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// Using the \ref KarpDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
 		    typedef typename TR::Path Path;
 		    /// The \ref KarpDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    // Data sturcture for path data
 		    struct PathData
+		    {
 		      LargeValue dist;
 		      Arc pred;
 		      PathData(LargeValue d, Arc p = INVALID) :
 		        dist(d), pred(p) {}
 		    };
 		    typedef typename Digraph::template NodeMap<std::vector<PathData> >
 		      PathDataNodeMap;
 		  private:
 		    // The digraph the algorithm runs on
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // Data for storing the strongly connected components
 		    int _comp_num;
 		    typename Digraph::template NodeMap<int> _comp;
 		    std::vector<std::vector<Node> > _comp_nodes;
 		    std::vector<Node>* _nodes;
 		    typename Digraph::template NodeMap<std::vector<Arc> > _out_arcs;
 		    // Data for the found cycle
 		    LargeValue _cycle_length;
 		    int _cycle_size;
 		    Node _cycle_node;
 		    Path *_cycle_path;
 		    bool _local_path;
 		    // Node map for storing path data
 		    PathDataNodeMap _data;
 		    // The processed nodes in the last round
 		    std::vector<Node> _process;
 		    Tolerance _tolerance;
 		    // Infinite constant
 		    const LargeValue INF;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		      typedef lemon::Tolerance<T> Tolerance;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeValue type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public Karp<GR, LEN, SetLargeValueTraits<T> > {
 		      typedef Karp<GR, LEN, SetLargeValueTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPathTraits : public Traits {
 		      typedef T Path;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c %Path type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting the \c %Path
 		    /// type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addFront() function.
 		    template <typename T>
 		    struct SetPath
 		      : public Karp<GR, LEN, SetPathTraits<T> > {
 		      typedef Karp<GR, LEN, SetPathTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Karp() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param length The lengths (costs) of the arcs.
 		    Karp( const Digraph &digraph,
 		          const LengthMap &length ) :
 		      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
 		      _cycle_length(0), _cycle_size(1), _cycle_node(INVALID),
 		      _cycle_path(NULL), _local_path(false), _data(digraph),
 		      INF(std::numeric_limits<LargeValue>::has_infinity ?
 		          std::numeric_limits<LargeValue>::infinity() :
 		          std::numeric_limits<LargeValue>::max())
 		    {}
 		    /// Destructor.
 		    ~Karp() {
 		      if (_local_path) delete _cycle_path;
+		    }
 		    /// \brief Set the path structure for storing the found cycle.
 		    ///
 		    /// This function sets an external path structure for storing the
 		    /// found cycle.
 		    ///
 		    /// If you don't call this function before calling \ref run() or
 		    /// \ref findMinMean(), it will allocate a local \ref Path "path"
 		    /// structure. The destuctor deallocates this automatically
 		    /// allocated object, of course.
 		    ///
 		    /// \note The algorithm calls only the \ref lemon::Path::addFront()
 		    /// "addFront()" function of the given path structure.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    Karp& cycle(Path &path) {
 		      if (_local_path) {
 		        delete _cycle_path;
 		        _local_path = false;
+		      }
 		      _cycle_path = &path;
 		      return *this;
+		    }
 		    /// \brief Set the tolerance used by the algorithm.
 		    ///
 		    /// This function sets the tolerance object used by the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    Karp& tolerance(const Tolerance& tolerance) {
 		      _tolerance = tolerance;
 		      return *this;
+		    }
 		    /// \brief Return a const reference to the tolerance.
 		    ///
 		    /// This function returns a const reference to the tolerance object
 		    /// used by the algorithm.
 		    const Tolerance& tolerance() const {
 		      return _tolerance;
+		    }
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to call the \ref run()
 		    /// function.\n
 		    /// If you only need the minimum mean length, you may call
 		    /// \ref findMinMean().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// It can be called more than once (e.g. if the underlying digraph
 		    /// and/or the arc lengths have been modified).
 		    ///
 		    /// \return \c true if a directed cycle exists in the digraph.
 		    ///
 		    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   return mmc.findMinMean() && mmc.findCycle();
 		    /// \endcode
 		    bool run() {
 		      return findMinMean() && findCycle();
+		    }
 		    /// \brief Find the minimum cycle mean.
 		    ///
 		    /// This function finds the minimum mean length of the directed
 		    /// cycles in the digraph.
 		    ///
 		    /// \return \c true if a directed cycle exists in the digraph.
 		    bool findMinMean() {
 		      // Initialization and find strongly connected components
 		      init();
 		      findComponents();
 		      // Find the minimum cycle mean in the components
 		      for (int comp = 0; comp < _comp_num; ++comp) {
 		        if (!initComponent(comp)) continue;
 		        processRounds();
 		        updateMinMean();
+		      }
 		      return (_cycle_node != INVALID);
+		    }
 		    /// \brief Find a minimum mean directed cycle.
 		    ///
 		    /// This function finds a directed cycle of minimum mean length
 		    /// in the digraph using the data computed by findMinMean().
 		    ///
 		    /// \return \c true if a directed cycle exists in the digraph.
 		    ///
 		    /// \pre \ref findMinMean() must be called before using this function.
 		    bool findCycle() {
 		      if (_cycle_node == INVALID) return false;
 		      IntNodeMap reached(_gr, -1);
 		      int r = _data[_cycle_node].size();
 		      Node u = _cycle_node;
 		      while (reached[u] < 0) {
 		        reached[u] = --r;
 		        u = _gr.source(_data[u][r].pred);
+		      }
 		      r = reached[u];
 		      Arc e = _data[u][r].pred;
 		      _cycle_path->addFront(e);
 		      _cycle_length = _length[e];
 		      _cycle_size = 1;
 		      Node v;
 		      while ((v = _gr.source(e)) != u) {
 		        e = _data[v][--r].pred;
 		        _cycle_path->addFront(e);
 		        _cycle_length += _length[e];
 		        ++_cycle_size;
+		      }
 		      return true;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The algorithm should be executed before using them.
 		    /// @{
 		    /// \brief Return the total length of the found cycle.
 		    ///
 		    /// This function returns the total length of the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
 		    Value cycleLength() const {
 		      return static_cast<Value>(_cycle_length);
+		    }
 		    /// \brief Return the number of arcs on the found cycle.
 		    ///
 		    /// This function returns the number of arcs on the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
 		    int cycleArcNum() const {
 		      return _cycle_size;
+		    }
 		    /// \brief Return the mean length of the found cycle.
 		    ///
 		    /// This function returns the mean length of the found cycle.
 		    ///
 		    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
 		    /// following code.
 		    /// \code
 		    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
 		    /// \endcode
 		    ///
 		    /// \pre \ref run() or \ref findMinMean() must be called before
 		    /// using this function.
 		    double cycleMean() const {
 		      return static_cast<double>(_cycle_length) / _cycle_size;
+		    }
 		    /// \brief Return the found cycle.
 		    ///
 		    /// This function returns a const reference to the path structure
 		    /// storing the found cycle.
 		    ///
 		    /// \pre \ref run() or \ref findCycle() must be called before using
 		    /// this function.
 		    const Path& cycle() const {
 		      return *_cycle_path;
+		    }
 		    ///@}
 		  private:
 		    // Initialization
 		    void init() {
 		      if (!_cycle_path) {
 		        _local_path = true;
 		        _cycle_path = new Path;
+		      }
 		      _cycle_path->clear();
 		      _cycle_length = 0;
 		      _cycle_size = 1;
 		      _cycle_node = INVALID;
 		      for (NodeIt u(_gr); u != INVALID; ++u)
 		        _data[u].clear();
+		    }
 		    // Find strongly connected components and initialize _comp_nodes
 		    // and _out_arcs
 		    void findComponents() {
 		      _comp_num = stronglyConnectedComponents(_gr, _comp);
 		      _comp_nodes.resize(_comp_num);
 		      if (_comp_num == 1) {
 		        _comp_nodes[0].clear();
 		        for (NodeIt n(_gr); n != INVALID; ++n) {
 		          _comp_nodes[0].push_back(n);
 		          _out_arcs[n].clear();
 		          for (OutArcIt a(_gr, n); a != INVALID; ++a) {
 		            _out_arcs[n].push_back(a);
+		          }
+		        }
 		      } else {
 		        for (int i = 0; i < _comp_num; ++i)
 		          _comp_nodes[i].clear();
 		        for (NodeIt n(_gr); n != INVALID; ++n) {
 		          int k = _comp[n];
 		          _comp_nodes[k].push_back(n);
 		          _out_arcs[n].clear();
 		          for (OutArcIt a(_gr, n); a != INVALID; ++a) {
 		            if (_comp[_gr.target(a)] == k) _out_arcs[n].push_back(a);
+		          }
+		        }
+		      }
+		    }
 		    // Initialize path data for the current component
 		    bool initComponent(int comp) {
 		      _nodes = &(_comp_nodes[comp]);
 		      int n = _nodes->size();
 		      if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
 		        return false;
+		      }
 		      for (int i = 0; i < n; ++i) {
 		        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
+		      }
 		      return true;
+		    }
 		    // Process all rounds of computing path data for the current component.
 		    // _data[v][k] is the length of a shortest directed walk from the root
 		    // node to node v containing exactly k arcs.
 		    void processRounds() {
 		      Node start = (*_nodes)[0];
 		      _data[start][0] = PathData(0);
 		      _process.clear();
 		      _process.push_back(start);
 		      int k, n = _nodes->size();
 		      for (k = 1; k <= n && int(_process.size()) < n; ++k) {
 		        processNextBuildRound(k);
+		      }
 		      for ( ; k <= n; ++k) {
 		        processNextFullRound(k);
+		      }
+		    }
 		    // Process one round and rebuild _process
 		    void processNextBuildRound(int k) {
 		      std::vector<Node> next;
 		      Node u, v;
 		      Arc e;
 		      LargeValue d;
 		      for (int i = 0; i < int(_process.size()); ++i) {
 		        u = _process[i];
 		        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
 		          e = _out_arcs[u][j];
 		          v = _gr.target(e);
 		          d = _data[u][k-1].dist + _length[e];
 		          if (_tolerance.less(d, _data[v][k].dist)) {
 		            if (_data[v][k].dist == INF) next.push_back(v);
 		            _data[v][k] = PathData(d, e);
+		          }
+		        }
+		      }
 		      _process.swap(next);
+		    }
 		    // Process one round using _nodes instead of _process
 		    void processNextFullRound(int k) {
 		      Node u, v;
 		      Arc e;
 		      LargeValue d;
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
 		        u = (*_nodes)[i];
 		        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
 		          e = _out_arcs[u][j];
 		          v = _gr.target(e);
 		          d = _data[u][k-1].dist + _length[e];
 		          if (_tolerance.less(d, _data[v][k].dist)) {
 		            _data[v][k] = PathData(d, e);
+		          }
+		        }
+		      }
+		    }
 		    // Update the minimum cycle mean
 		    void updateMinMean() {
 		      int n = _nodes->size();
 		      for (int i = 0; i < n; ++i) {
 		        Node u = (*_nodes)[i];
 		        if (_data[u][n].dist == INF) continue;
 		        LargeValue length, max_length = 0;
 		        int size, max_size = 1;
 		        bool found_curr = false;
 		        for (int k = 0; k < n; ++k) {
 		          if (_data[u][k].dist == INF) continue;
 		          length = _data[u][n].dist - _data[u][k].dist;
 		          size = n - k;
 		          if (!found_curr || length * max_size > max_length * size) {
 		            found_curr = true;
 		            max_length = length;
 		            max_size = size;
+		          }
+		        }
 		        if ( found_curr && (_cycle_node == INVALID ||
 		             max_length * _cycle_size < _cycle_length * max_size) ) {
 		          _cycle_length = max_length;
 		          _cycle_size = max_size;
 		          _cycle_node = u;
+		        }
+		      }
+		    }
 		  }; //class Karp
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_KARP_H

lemon/suurballe.h

Show inline comments

@@ -22,751 +22,755 @@
 		///\ingroup shortest_path
 		///\file
 		///\brief An algorithm for finding arc-disjoint paths between two
 		/// nodes having minimum total length.
 		#include <vector>
 		#include <limits>
 		#include <lemon/bin_heap.h>
 		#include <lemon/path.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  /// \brief Default traits class of Suurballe algorithm.
 		  ///
 		  /// Default traits class of Suurballe algorithm.
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam LEN The type of the length map.
 		  /// The default value is <tt>GR::ArcMap<int></tt>.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int> >
 		#endif
 		  struct SuurballeDefaultTraits
+		  {
 		    /// The type of the digraph.
 		    typedef GR Digraph;
 		    /// The type of the length map.
 		    typedef LEN LengthMap;
 		    /// The type of the lengths.
 		    typedef typename LEN::Value Length;
 		    /// The type of the flow map.
 		    typedef typename GR::template ArcMap<int> FlowMap;
 		    /// The type of the potential map.
 		    typedef typename GR::template NodeMap<Length> PotentialMap;
 		    /// \brief The path type
 		    ///
 		    /// The type used for storing the found arc-disjoint paths.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    typedef lemon::Path<Digraph> Path;
 		    /// The cross reference type used for the heap.
 		    typedef typename GR::template NodeMap<int> HeapCrossRef;
 		    /// \brief The heap type used for internal Dijkstra computations.
 		    ///
 		    /// The type of the heap used for internal Dijkstra computations.
 		    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept
 		    /// and its priority type must be \c Length.
 		    typedef BinHeap<Length, HeapCrossRef> Heap;
 		  };
 		  /// \addtogroup shortest_path
 		  /// @{
 		  /// \brief Algorithm for finding arc-disjoint paths between two nodes
 		  /// having minimum total length.
 		  ///
 		  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
 		  /// finding arc-disjoint paths having minimum total length (cost)
 		  /// from a given source node to a given target node in a digraph.
 		  ///
 		  /// Note that this problem is a special case of the \ref min_cost_flow
 		  /// "minimum cost flow problem". This implementation is actually an
 		  /// efficient specialized version of the \ref CapacityScaling
 		  /// "successive shortest path" algorithm directly for this problem.
 		  /// Therefore this class provides query functions for flow values and
 		  /// node potentials (the dual solution) just like the minimum cost flow
 		  /// algorithms.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam LEN The type of the length map.
 		  /// The default value is <tt>GR::ArcMap<int></tt>.
 		  ///
 		  /// \warning Length values should be \e non-negative.
 		  ///
 		  /// \note For finding \e node-disjoint paths, this algorithm can be used
 		  /// along with the \ref SplitNodes adaptor.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = SuurballeDefaultTraits<GR, LEN> >
 		#endif
 		  class Suurballe
+		  {
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef ConstMap<Arc, int> ConstArcMap;
 		    typedef typename GR::template NodeMap<Arc> PredMap;
 		  public:
 		    /// The type of the digraph.
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map.
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the lengths.
 		    typedef typename TR::Length Length;
 		    /// The type of the flow map.
 		    typedef typename TR::FlowMap FlowMap;
 		    /// The type of the potential map.
 		    typedef typename TR::PotentialMap PotentialMap;
 		    /// The type of the path structures.
 		    typedef typename TR::Path Path;
 		    /// The cross reference type used for the heap.
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    /// The heap type used for internal Dijkstra computations.
 		    typedef typename TR::Heap Heap;
 		    /// The \ref SuurballeDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    // ResidualDijkstra is a special implementation of the
 		    // Dijkstra algorithm for finding shortest paths in the
 		    // residual network with respect to the reduced arc lengths
 		    // and modifying the node potentials according to the
 		    // distance of the nodes.
 		    class ResidualDijkstra
+		    {
 		    private:
 		      const Digraph &_graph;
 		      const LengthMap &_length;
 		      const FlowMap &_flow;
 		      PotentialMap &_pi;
 		      PredMap &_pred;
 		      Node _s;
 		      Node _t;
 		      PotentialMap _dist;
 		      std::vector<Node> _proc_nodes;
 		    public:
 		      // Constructor
 		      ResidualDijkstra(Suurballe &srb) :
 		        _graph(srb._graph), _length(srb._length),
 		        _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred),
 		        _s(srb._s), _t(srb._t), _dist(_graph) {}
 		      // Run the algorithm and return true if a path is found
 		      // from the source node to the target node.
 		      bool run(int cnt) {
 		        return cnt == 0 ? startFirst() : start();
+		      }
 		    private:
 		      // Execute the algorithm for the first time (the flow and potential
 		      // functions have to be identically zero).
 		      bool startFirst() {
 		        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
 		        Heap heap(heap_cross_ref);
 		        heap.push(_s, 0);
 		        _pred[_s] = INVALID;
 		        _proc_nodes.clear();
 		        // Process nodes
 		        while (!heap.empty() && heap.top() != _t) {
 		          Node u = heap.top(), v;
 		          Length d = heap.prio(), dn;
 		          _dist[u] = heap.prio();
 		          _proc_nodes.push_back(u);
 		          heap.pop();
 		          // Traverse outgoing arcs
 		          for (OutArcIt e(_graph, u); e != INVALID; ++e) {
 		            v = _graph.target(e);
 		            switch(heap.state(v)) {
 		              case Heap::PRE_HEAP:
 		                heap.push(v, d + _length[e]);
 		                _pred[v] = e;
 		                break;
 		              case Heap::IN_HEAP:
 		                dn = d + _length[e];
 		                if (dn < heap[v]) {
 		                  heap.decrease(v, dn);
 		                  _pred[v] = e;
+		                }
 		                break;
 		              case Heap::POST_HEAP:
 		                break;
+		            }
+		          }
+		        }
 		        if (heap.empty()) return false;
 		        // Update potentials of processed nodes
 		        Length t_dist = heap.prio();
 		        for (int i = 0; i < int(_proc_nodes.size()); ++i)
 		          _pi[_proc_nodes[i]] = _dist[_proc_nodes[i]] - t_dist;
 		        return true;
+		      }
 		      // Execute the algorithm.
 		      bool start() {
 		        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
 		        Heap heap(heap_cross_ref);
 		        heap.push(_s, 0);
 		        _pred[_s] = INVALID;
 		        _proc_nodes.clear();
 		        // Process nodes
 		        while (!heap.empty() && heap.top() != _t) {
 		          Node u = heap.top(), v;
 		          Length d = heap.prio() + _pi[u], dn;
 		          _dist[u] = heap.prio();
 		          _proc_nodes.push_back(u);
 		          heap.pop();
 		          // Traverse outgoing arcs
 		          for (OutArcIt e(_graph, u); e != INVALID; ++e) {
 		            if (_flow[e] == 0) {
 		              v = _graph.target(e);
 		              switch(heap.state(v)) {
 		                case Heap::PRE_HEAP:
 		                  heap.push(v, d + _length[e] - _pi[v]);
 		                  _pred[v] = e;
 		                  break;
 		                case Heap::IN_HEAP:
 		                  dn = d + _length[e] - _pi[v];
 		                  if (dn < heap[v]) {
 		                    heap.decrease(v, dn);
 		                    _pred[v] = e;
+		                  }
 		                  break;
 		                case Heap::POST_HEAP:
 		                  break;
+		              }
+		            }
+		          }
 		          // Traverse incoming arcs
 		          for (InArcIt e(_graph, u); e != INVALID; ++e) {
 		            if (_flow[e] == 1) {
 		              v = _graph.source(e);
 		              switch(heap.state(v)) {
 		                case Heap::PRE_HEAP:
 		                  heap.push(v, d - _length[e] - _pi[v]);
 		                  _pred[v] = e;
 		                  break;
 		                case Heap::IN_HEAP:
 		                  dn = d - _length[e] - _pi[v];
 		                  if (dn < heap[v]) {
 		                    heap.decrease(v, dn);
 		                    _pred[v] = e;
+		                  }
 		                  break;
 		                case Heap::POST_HEAP:
 		                  break;
+		              }
+		            }
+		          }
+		        }
 		        if (heap.empty()) return false;
 		        // Update potentials of processed nodes
 		        Length t_dist = heap.prio();
 		        for (int i = 0; i < int(_proc_nodes.size()); ++i)
 		          _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
 		        return true;
+		      }
 		    }; //class ResidualDijkstra
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c FlowMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c FlowMap type.
 		    template <typename T>
 		    struct SetFlowMap
 		      : public Suurballe<GR, LEN, SetFlowMapTraits<T> > {
 		      typedef Suurballe<GR, LEN, SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPotentialMapTraits : public Traits {
 		      typedef T PotentialMap;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c PotentialMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c PotentialMap type.
 		    template <typename T>
 		    struct SetPotentialMap
 		      : public Suurballe<GR, LEN, SetPotentialMapTraits<T> > {
 		      typedef Suurballe<GR, LEN, SetPotentialMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPathTraits : public Traits {
 		      typedef T Path;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c %Path type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c %Path type.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    template <typename T>
 		    struct SetPath
 		      : public Suurballe<GR, LEN, SetPathTraits<T> > {
 		      typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;
 		    };
 		    template <typename H, typename CR>
 		    struct SetHeapTraits : public Traits {
 		      typedef H Heap;
 		      typedef CR HeapCrossRef;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c Heap and \c HeapCrossRef types.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c Heap
 		    /// and \c HeapCrossRef types with automatic allocation.
 		    /// They will be used for internal Dijkstra computations.
 		    /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"
 		    /// concept and its priority type must be \c Length.
 		    template <typename H,
 		              typename CR = typename Digraph::template NodeMap<int> >
 		    struct SetHeap
 		      : public Suurballe<GR, LEN, SetHeapTraits<H, CR> > {
 		      typedef Suurballe<GR, LEN, SetHeapTraits<H, CR> > Create;
 		    };
 		    /// @}
 		  private:
 		    // The digraph the algorithm runs on
 		    const Digraph &_graph;
 		    // The length map
 		    const LengthMap &_length;
 		    // Arc map of the current flow
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    // Node map of the current potentials
 		    PotentialMap *_potential;
 		    bool _local_potential;
 		    // The source node
 		    Node _s;
 		    // The target node
 		    Node _t;
 		    // Container to store the found paths
 		    std::vector<Path> _paths;
 		    int _path_num;
 		    // The pred arc map
 		    PredMap _pred;
 		    // Data for full init
 		    PotentialMap *_init_dist;
 		    PredMap *_init_pred;
 		    bool _full_init;
 		  protected:
 		    Suurballe() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    /// \param length The length (cost) values of the arcs.
 		    Suurballe( const Digraph &graph,
 		               const LengthMap &length ) :
 		      _graph(graph), _length(length), _flow(0), _local_flow(false),
 		      _potential(0), _local_potential(false), _pred(graph),
 		      _init_dist(0), _init_pred(0)
 		    {}
 		    /// Destructor.
 		    ~Suurballe() {
 		      if (_local_flow) delete _flow;
 		      if (_local_potential) delete _potential;
 		      delete _init_dist;
 		      delete _init_pred;
+		    }
 		    /// \brief Set the flow map.
 		    ///
 		    /// This function sets the flow map.
 		    /// If it is not used before calling \ref run() or \ref init(),
 		    /// an instance will be allocated automatically. The destructor
 		    /// deallocates this automatically allocated map, of course.
 		    ///
 		    /// The found flow contains only 0 and 1 values, since it is the
 		    /// union of the found arc-disjoint paths.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    Suurballe& flowMap(FlowMap &map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Set the potential map.
 		    ///
 		    /// This function sets the potential map.
 		    /// If it is not used before calling \ref run() or \ref init(),
 		    /// an instance will be allocated automatically. The destructor
 		    /// deallocates this automatically allocated map, of course.
 		    ///
 		    /// The node potentials provide the dual solution of the underlying
 		    /// \ref min_cost_flow "minimum cost flow problem".
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    Suurballe& potentialMap(PotentialMap &map) {
 		      if (_local_potential) {
 		        delete _potential;
 		        _local_potential = false;
+		      }
 		      _potential = &map;
 		      return *this;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to call the run()
 		    /// function.\n
 		    /// If you need to execute the algorithm many times using the same
 		    /// source node, then you may call fullInit() once and start()
 		    /// for each target node.\n
 		    /// If you only need the flow that is the union of the found
 		    /// arc-disjoint paths, then you may call findFlow() instead of
 		    /// start().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The number of paths to be found.
 		    ///
 		    /// \return \c k if there are at least \c k arc-disjoint paths from
 		    /// \c s to \c t in the digraph. Otherwise it returns the number of
 		    /// arc-disjoint paths found.
 		    ///
 		    /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is
 		    /// just a shortcut of the following code.
 		    /// \code
 		    ///   s.init(s);
 		    ///   s.start(t, k);
 		    /// \endcode
 		    int run(const Node& s, const Node& t, int k = 2) {
 		      init(s);
 		      start(t, k);
 		      return _path_num;
+		    }
 		    /// \brief Initialize the algorithm.
 		    ///
 		    /// This function initializes the algorithm with the given source node.
 		    ///
 		    /// \param s The source node.
 		    void init(const Node& s) {
 		      _s = s;
 		      // Initialize maps
 		      if (!_flow) {
 		        _flow = new FlowMap(_graph);
 		        _local_flow = true;
+		      }
 		      if (!_potential) {
 		        _potential = new PotentialMap(_graph);
 		        _local_potential = true;
+		      }
 		      _full_init = false;
+		    }
 		    /// \brief Initialize the algorithm and perform Dijkstra.
 		    ///
 		    /// This function initializes the algorithm and performs a full
 		    /// Dijkstra search from the given source node. It makes consecutive
 		    /// executions of \ref start() "start(t, k)" faster, since they
 		    /// have to perform %Dijkstra only k-1 times.
 		    ///
 		    /// This initialization is usually worth using instead of \ref init()
 		    /// if the algorithm is executed many times using the same source node.
 		    ///
 		    /// \param s The source node.
 		    void fullInit(const Node& s) {
 		      // Initialize maps
 		      init(s);
 		      if (!_init_dist) {
 		        _init_dist = new PotentialMap(_graph);
+		      }
 		      if (!_init_pred) {
 		        _init_pred = new PredMap(_graph);
+		      }
 		      // Run a full Dijkstra
 		      typename Dijkstra<Digraph, LengthMap>
 		        ::template SetStandardHeap<Heap>
 		        ::template SetDistMap<PotentialMap>
 		        ::template SetPredMap<PredMap>
 		        ::Create dijk(_graph, _length);
 		      dijk.distMap(*_init_dist).predMap(*_init_pred);
 		      dijk.run(s);
 		      _full_init = true;
+		    }
 		    /// \brief Execute the algorithm.
 		    ///
 		    /// This function executes the algorithm.
 		    ///
 		    /// \param t The target node.
 		    /// \param k The number of paths to be found.
 		    ///
 		    /// \return \c k if there are at least \c k arc-disjoint paths from
 		    /// \c s to \c t in the digraph. Otherwise it returns the number of
 		    /// arc-disjoint paths found.
 		    ///
 		    /// \note Apart from the return value, <tt>s.start(t, k)</tt> is
 		    /// just a shortcut of the following code.
 		    /// \code
 		    ///   s.findFlow(t, k);
 		    ///   s.findPaths();
 		    /// \endcode
 		    int start(const Node& t, int k = 2) {
 		      findFlow(t, k);
 		      findPaths();
 		      return _path_num;
+		    }
 		    /// \brief Execute the algorithm to find an optimal flow.
 		    ///
 		    /// This function executes the successive shortest path algorithm to
 		    /// find a minimum cost flow, which is the union of \c k (or less)
 		    /// arc-disjoint paths.
 		    ///
 		    /// \param t The target node.
 		    /// \param k The number of paths to be found.
 		    ///
 		    /// \return \c k if there are at least \c k arc-disjoint paths from
 		    /// the source node to the given node \c t in the digraph.
 		    /// Otherwise it returns the number of arc-disjoint paths found.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    int findFlow(const Node& t, int k = 2) {
 		      _t = t;
 		      ResidualDijkstra dijkstra(*this);
 		      // Initialization
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        (*_flow)[e] = 0;
+		      }
 		      if (_full_init) {
 		        for (NodeIt n(_graph); n != INVALID; ++n) {
 		          (*_potential)[n] = (*_init_dist)[n];
+		        }
 		        Node u = _t;
 		        Arc e;
 		        while ((e = (*_init_pred)[u]) != INVALID) {
 		          (*_flow)[e] = 1;
 		          u = _graph.source(e);
+		        }
 		        _path_num = 1;
 		      } else {
 		        for (NodeIt n(_graph); n != INVALID; ++n) {
 		          (*_potential)[n] = 0;
+		        }
 		        _path_num = 0;
+		      }
 		      // Find shortest paths
 		      while (_path_num < k) {
 		        // Run Dijkstra
 		        if (!dijkstra.run(_path_num)) break;
 		        ++_path_num;
 		        // Set the flow along the found shortest path
 		        Node u = _t;
 		        Arc e;
 		        while ((e = _pred[u]) != INVALID) {
 		          if (u == _graph.target(e)) {
 		            (*_flow)[e] = 1;
 		            u = _graph.source(e);
 		          } else {
 		            (*_flow)[e] = 0;
 		            u = _graph.target(e);
+		          }
+		        }
+		      }
 		      return _path_num;
+		    }
 		    /// \brief Compute the paths from the flow.
 		    ///
 		    /// This function computes arc-disjoint paths from the found minimum
 		    /// cost flow, which is the union of them.
 		    ///
 		    /// \pre \ref init() and \ref findFlow() must be called before using
 		    /// this function.
 		    void findPaths() {
 		      FlowMap res_flow(_graph);
 		      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
 		      _paths.clear();
 		      _paths.resize(_path_num);
 		      for (int i = 0; i < _path_num; ++i) {
 		        Node n = _s;
 		        while (n != _t) {
 		          OutArcIt e(_graph, n);
 		          for ( ; res_flow[e] == 0; ++e) ;
 		          n = _graph.target(e);
 		          _paths[i].addBack(e);
 		          res_flow[e] = 0;
+		        }
+		      }
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.
 		    /// \n The algorithm should be executed before using them.
 		    /// @{
 		    /// \brief Return the total length of the found paths.
 		    ///
 		    /// This function returns the total length of the found paths, i.e.
 		    /// the total cost of the found flow.
 		    /// The complexity of the function is O(e).
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    Length totalLength() const {
 		      Length c = 0;
 		      for (ArcIt e(_graph); e != INVALID; ++e)
 		        c += (*_flow)[e] * _length[e];
 		      return c;
+		    }
 		    /// \brief Return the flow value on the given arc.
 		    ///
 		    /// This function returns the flow value on the given arc.
 		    /// It is \c 1 if the arc is involved in one of the found arc-disjoint
 		    /// paths, otherwise it is \c 0.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    int flow(const Arc& arc) const {
 		      return (*_flow)[arc];
+		    }
 		    /// \brief Return a const reference to an arc map storing the
 		    /// found flow.
 		    ///
 		    /// This function returns a const reference to an arc map storing
 		    /// the flow that is the union of the found arc-disjoint paths.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /// \brief Return the potential of the given node.
 		    ///
 		    /// This function returns the potential of the given node.
 		    /// The node potentials provide the dual solution of the
 		    /// underlying \ref min_cost_flow "minimum cost flow problem".
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    Length potential(const Node& node) const {
 		      return (*_potential)[node];
+		    }
 		    /// \brief Return a const reference to a node map storing the
 		    /// found potentials (the dual solution).
 		    ///
 		    /// This function returns a const reference to a node map storing
 		    /// the found potentials that provide the dual solution of the
 		    /// underlying \ref min_cost_flow "minimum cost flow problem".
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    const PotentialMap& potentialMap() const {
 		      return *_potential;
+		    }
 		    /// \brief Return the number of the found paths.
 		    ///
 		    /// This function returns the number of the found paths.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    int pathNum() const {
 		      return _path_num;
+		    }
 		    /// \brief Return a const reference to the specified path.
 		    ///
 		    /// This function returns a const reference to the specified path.
 		    ///
 		    /// \param i The function returns the <tt>i</tt>-th path.
 		    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
 		    ///
 		    /// \pre \ref run() or \ref findPaths() must be called before using
 		    /// this function.
 		    const Path& path(int i) const {
 		      return _paths[i];
+		    }
 		    /// @}
 		  }; //class Suurballe
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_SUURBALLE_H

0 comments (0 inline)

RhodeCode

Login to your account