1.1 --- a/lemon/min_cost_flow.h	Mon Feb 18 03:32:06 2008 +0000
     1.2 +++ b/lemon/min_cost_flow.h	Mon Feb 18 03:32:56 2008 +0000
     1.3 @@ -36,33 +36,35 @@
     1.4    /// \ref MinCostFlow provides an efficient algorithm for finding
     1.5    /// a minimum cost flow.
     1.6    ///
     1.7 -  /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex,
     1.8 -  /// which is the most efficient implementation for the minimum cost
     1.9 -  /// flow problem in the LEMON library according to our benchmark
    1.10 -  /// tests.
    1.11 -  ///
    1.12 -  /// \note There are three implementations for the minimum cost flow
    1.13 -  /// problem, that can be used exactly the same way.
    1.14 -  /// - \ref CapacityScaling
    1.15 -  /// - \ref CycleCanceling
    1.16 -  /// - \ref NetworkSimplex
    1.17 -  ///
    1.18 -  /// \note For the detailed documentation of this class see
    1.19 +  /// This class is just an alias for \ref NetworkSimplex,
    1.20 +  /// which is the most efficient algorithm for the minimum cost
    1.21 +  /// flow problem in LEMON according to our benchmark tests.
    1.22 +  /// For the detailed documentation of this class see
    1.23    /// \ref NetworkSimplex.
    1.24    ///
    1.25 -  /// \param Graph The directed graph type the algorithm runs on.
    1.26 -  /// \param LowerMap The type of the lower bound map.
    1.27 -  /// \param CapacityMap The type of the capacity (upper bound) map.
    1.28 -  /// \param CostMap The type of the cost (length) map.
    1.29 -  /// \param SupplyMap The type of the supply map.
    1.30 +  /// There are four implementations for the minimum cost flow problem,
    1.31 +  /// which can be used exactly the same way except for the fact that
    1.32 +  /// \ref CycleCanceling does not provide dual solution (node
    1.33 +  /// potentials) since it is a pure primal method.
    1.34 +  /// - \ref CapacityScaling The capacity scaling algorithm.
    1.35 +  /// - \ref CostScaling The cost scaling algorithm.
    1.36 +  /// - \ref CycleCanceling A cycle-canceling algorithm.
    1.37 +  /// - \ref NetworkSimplex The network simplex algorithm.
    1.38 +  ///
    1.39 +  /// \tparam Graph The directed graph type the algorithm runs on.
    1.40 +  /// \tparam LowerMap The type of the lower bound map.
    1.41 +  /// \tparam CapacityMap The type of the capacity (upper bound) map.
    1.42 +  /// \tparam CostMap The type of the cost (length) map.
    1.43 +  /// \tparam SupplyMap The type of the supply map.
    1.44    ///
    1.45    /// \warning
    1.46 -  /// - Edge capacities and costs should be non-negative integers.
    1.47 -  ///   However \c CostMap::Value should be signed type.
    1.48 -  /// - Supply values should be signed integers.
    1.49 -  /// - \c LowerMap::Value must be convertible to
    1.50 -  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    1.51 -  ///   convertible to \c SupplyMap::Value.
    1.52 +  /// - Edge capacities and costs should be \e non-negative \e integers.
    1.53 +  /// - Supply values should be \e signed \e integers.
    1.54 +  /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
    1.55 +  /// - \c CapacityMap::Value and \c SupplyMap::Value must be
    1.56 +  ///   convertible to each other.
    1.57 +  /// - All value types must be convertible to \c CostMap::Value, which
    1.58 +  ///   must be signed type.
    1.59    ///
    1.60    /// \author Peter Kovacs
    1.61  

     2.1 --- a/lemon/min_cost_max_flow.h	Mon Feb 18 03:32:06 2008 +0000
     2.2 +++ b/lemon/min_cost_max_flow.h	Mon Feb 18 03:32:56 2008 +0000
     2.3 @@ -40,17 +40,22 @@
     2.4    /// finding a maximum flow having minimal total cost from a given
     2.5    /// source node to a given target node in a directed graph.
     2.6    ///
     2.7 -  /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
     2.8 -  /// the maximum flow value and \ref NetworkSimplex algorithm for
     2.9 -  /// finding a minimum cost flow of that value.
    2.10 +  /// \ref MinCostMaxFlow uses \ref Preflow for finding the maximum
    2.11 +  /// flow value and \ref NetworkSimplex for finding a minimum cost
    2.12 +  /// flow of that value.
    2.13 +  /// According to our benchmark tests \ref Preflow is generally the
    2.14 +  /// most efficient algorithm for the maximum flow problem and
    2.15 +  /// \ref NetworkSimplex is the most efficient for the minimum cost
    2.16 +  /// flow problem in LEMON.
    2.17    ///
    2.18 -  /// \param Graph The directed graph type the algorithm runs on.
    2.19 -  /// \param CapacityMap The type of the capacity (upper bound) map.
    2.20 -  /// \param CostMap The type of the cost (length) map.
    2.21 +  /// \tparam Graph The directed graph type the algorithm runs on.
    2.22 +  /// \tparam CapacityMap The type of the capacity (upper bound) map.
    2.23 +  /// \tparam CostMap The type of the cost (length) map.
    2.24    ///
    2.25    /// \warning
    2.26 -  /// - Edge capacities and costs should be non-negative integers.
    2.27 -  ///   However \c CostMap::Value should be signed type.
    2.28 +  /// - Edge capacities and costs should be \e non-negative \e integers.
    2.29 +  ///   However \c CostMap::Value must be signed type.
    2.30 +  /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.
    2.31    ///
    2.32    /// \author Peter Kovacs
    2.33  
    2.34 @@ -64,34 +69,37 @@
    2.35  
    2.36      typedef typename CapacityMap::Value Capacity;
    2.37      typedef typename CostMap::Value Cost;
    2.38 -    typedef typename Graph::template NodeMap<Capacity> SupplyMap;
    2.39 +    typedef typename Graph::template NodeMap<Cost> SupplyMap;
    2.40 +
    2.41 +    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
    2.42      typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
    2.43 -                            CostMap, SupplyMap >
    2.44 -      MinCostFlowImpl;
    2.45 +                            CostMap, SupplyMap > MinCostFlowImpl;
    2.46  
    2.47    public:
    2.48  
    2.49      /// The type of the flow map.
    2.50      typedef typename Graph::template EdgeMap<Capacity> FlowMap;
    2.51 +    /// The type of the potential map.
    2.52 +    typedef typename Graph::template NodeMap<Cost> PotentialMap;
    2.53  
    2.54    private:
    2.55  
    2.56 -    /// The directed graph the algorithm runs on.
    2.57 -    const Graph &graph;
    2.58 -    /// The modified capacity map.
    2.59 -    const CapacityMap &capacity;
    2.60 -    /// The cost map.
    2.61 -    const CostMap &cost;
    2.62 -    /// The edge map of the found flow.
    2.63 -    FlowMap flow;
    2.64 -    /// The source node.
    2.65 -    Node source;
    2.66 -    /// The target node.
    2.67 -    Node target;
    2.68 +    // The directed graph the algorithm runs on
    2.69 +    const Graph &_graph;
    2.70 +    // The modified capacity map
    2.71 +    const CapacityMap &_capacity;
    2.72 +    // The cost map
    2.73 +    const CostMap &_cost;
    2.74  
    2.75 -    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
    2.76 -    /// \brief \ref Preflow class for finding the maximum flow value.
    2.77 -    MaxFlowImpl preflow;
    2.78 +    // Edge map of the found flow
    2.79 +    FlowMap _flow;
    2.80 +    // Node map of the found potentials
    2.81 +    PotentialMap _potential;
    2.82 +
    2.83 +    // The source node
    2.84 +    Node _source;
    2.85 +    // The target node
    2.86 +    Node _target;
    2.87  
    2.88    public:
    2.89  
    2.90 @@ -104,22 +112,46 @@
    2.91      /// \param _cost The cost (length) values of the edges.
    2.92      /// \param _s The source node.
    2.93      /// \param _t The target node.
    2.94 -    MinCostMaxFlow( const Graph &_graph,
    2.95 -                    const CapacityMap &_capacity,
    2.96 -                    const CostMap &_cost,
    2.97 -                    Node _s, Node _t ) :
    2.98 -      graph(_graph), capacity(_capacity), cost(_cost),
    2.99 -      source(_s), target(_t), flow(_graph),
   2.100 -      preflow(_graph, _capacity, _s, _t)
   2.101 +    MinCostMaxFlow( const Graph &graph,
   2.102 +                    const CapacityMap &capacity,
   2.103 +                    const CostMap &cost,
   2.104 +                    Node s, Node t ) :
   2.105 +      _graph(graph), _capacity(capacity), _cost(cost), _flow(graph),
   2.106 +      _potential(graph), _source(s), _target(t)
   2.107      {}
   2.108  
   2.109 -    /// \brief Returns a const reference to the flow map.
   2.110 +    /// \brief Runs the algorithm.
   2.111      ///
   2.112 -    /// Returns a const reference to the flow map.
   2.113 +    /// Runs the algorithm.
   2.114 +    void run() {
   2.115 +      MaxFlowImpl preflow(_graph, _capacity, _source, _target);
   2.116 +      preflow.flowMap(_flow).runMinCut();
   2.117 +      MinCostFlowImpl mcf( _graph, _capacity, _cost,
   2.118 +                           _source, _target, preflow.flowValue() );
   2.119 +      mcf.run();
   2.120 +      _flow = mcf.flowMap();
   2.121 +      _potential = mcf.potentialMap();
   2.122 +    }
   2.123 +
   2.124 +    /// \brief Returns a const reference to the edge map storing the
   2.125 +    /// found flow.
   2.126 +    ///
   2.127 +    /// Returns a const reference to the edge map storing the found flow.
   2.128      ///
   2.129      /// \pre \ref run() must be called before using this function.
   2.130      const FlowMap& flowMap() const {
   2.131 -      return flow;
   2.132 +      return _flow_result;
   2.133 +    }
   2.134 +
   2.135 +    /// \brief Returns a const reference to the node map storing the
   2.136 +    /// found potentials (the dual solution).
   2.137 +    ///
   2.138 +    /// Returns a const reference to the node map storing the found
   2.139 +    /// potentials (the dual solution).
   2.140 +    ///
   2.141 +    /// \pre \ref run() must be called before using this function.
   2.142 +    const PotentialMap& potentialMap() const {
   2.143 +      return _potential_result;
   2.144      }
   2.145  
   2.146      /// \brief Returns the total cost of the found flow.
   2.147 @@ -131,20 +163,10 @@
   2.148      Cost totalCost() const {
   2.149        Cost c = 0;
   2.150        for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
   2.151 -        c += flow[e] * cost[e];
   2.152 +        c += _flow[e] * _cost[e];
   2.153        return c;
   2.154      }
   2.155  
   2.156 -    /// \brief Runs the algorithm.
   2.157 -    void run() {
   2.158 -      preflow.flowMap(flow);
   2.159 -      preflow.runMinCut();
   2.160 -      MinCostFlowImpl mcf_impl( graph, capacity, cost,
   2.161 -                                source, target, preflow.flowValue() );
   2.162 -      mcf_impl.run();
   2.163 -      flow = mcf_impl.flowMap();
   2.164 -    }
   2.165 -
   2.166    }; //class MinCostMaxFlow
   2.167  
   2.168    ///@}