COIN-OR::LEMON - Graph Library

Changeset 2576:ae092c63d3ba in lemon-0.x


Ignore:
Timestamp:
02/18/08 04:32:56 (16 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3458
Message:

Improvements in MinCostFlow? and MinCostMaxFlow?.

Main changes:

  • MinCostMaxFlow? also provides dual solution.
  • Change the name of private members to start with "_".
  • Change the name of function parameters not to start with "_".
  • Remove unnecessary documentation for private members.
  • Doc improvements.
Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/min_cost_flow.h

    r2556 r2576  
    3737  /// a minimum cost flow.
    3838  ///
    39   /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex,
    40   /// which is the most efficient implementation for the minimum cost
    41   /// flow problem in the LEMON library according to our benchmark
    42   /// tests.
    43   ///
    44   /// \note There are three implementations for the minimum cost flow
    45   /// problem, that can be used exactly the same way.
    46   /// - \ref CapacityScaling
    47   /// - \ref CycleCanceling
    48   /// - \ref NetworkSimplex
    49   ///
    50   /// \note For the detailed documentation of this class see
     39  /// This class is just an alias for \ref NetworkSimplex,
     40  /// which is the most efficient algorithm for the minimum cost
     41  /// flow problem in LEMON according to our benchmark tests.
     42  /// For the detailed documentation of this class see
    5143  /// \ref NetworkSimplex.
    5244  ///
    53   /// \param Graph The directed graph type the algorithm runs on.
    54   /// \param LowerMap The type of the lower bound map.
    55   /// \param CapacityMap The type of the capacity (upper bound) map.
    56   /// \param CostMap The type of the cost (length) map.
    57   /// \param SupplyMap The type of the supply map.
     45  /// There are four implementations for the minimum cost flow problem,
     46  /// which can be used exactly the same way except for the fact that
     47  /// \ref CycleCanceling does not provide dual solution (node
     48  /// potentials) since it is a pure primal method.
     49  /// - \ref CapacityScaling The capacity scaling algorithm.
     50  /// - \ref CostScaling The cost scaling algorithm.
     51  /// - \ref CycleCanceling A cycle-canceling algorithm.
     52  /// - \ref NetworkSimplex The network simplex algorithm.
     53  ///
     54  /// \tparam Graph The directed graph type the algorithm runs on.
     55  /// \tparam LowerMap The type of the lower bound map.
     56  /// \tparam CapacityMap The type of the capacity (upper bound) map.
     57  /// \tparam CostMap The type of the cost (length) map.
     58  /// \tparam SupplyMap The type of the supply map.
    5859  ///
    5960  /// \warning
    60   /// - Edge capacities and costs should be non-negative integers.
    61   ///   However \c CostMap::Value should be signed type.
    62   /// - Supply values should be signed integers.
    63   /// - \c LowerMap::Value must be convertible to
    64   ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    65   ///   convertible to \c SupplyMap::Value.
     61  /// - Edge capacities and costs should be \e non-negative \e integers.
     62  /// - Supply values should be \e signed \e integers.
     63  /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
     64  /// - \c CapacityMap::Value and \c SupplyMap::Value must be
     65  ///   convertible to each other.
     66  /// - All value types must be convertible to \c CostMap::Value, which
     67  ///   must be signed type.
    6668  ///
    6769  /// \author Peter Kovacs
  • lemon/min_cost_max_flow.h

    r2556 r2576  
    4141  /// source node to a given target node in a directed graph.
    4242  ///
    43   /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
    44   /// the maximum flow value and \ref NetworkSimplex algorithm for
    45   /// finding a minimum cost flow of that value.
     43  /// \ref MinCostMaxFlow uses \ref Preflow for finding the maximum
     44  /// flow value and \ref NetworkSimplex for finding a minimum cost
     45  /// flow of that value.
     46  /// According to our benchmark tests \ref Preflow is generally the
     47  /// most efficient algorithm for the maximum flow problem and
     48  /// \ref NetworkSimplex is the most efficient for the minimum cost
     49  /// flow problem in LEMON.
    4650  ///
    47   /// \param Graph The directed graph type the algorithm runs on.
    48   /// \param CapacityMap The type of the capacity (upper bound) map.
    49   /// \param CostMap The type of the cost (length) map.
     51  /// \tparam Graph The directed graph type the algorithm runs on.
     52  /// \tparam CapacityMap The type of the capacity (upper bound) map.
     53  /// \tparam CostMap The type of the cost (length) map.
    5054  ///
    5155  /// \warning
    52   /// - Edge capacities and costs should be non-negative integers.
    53   ///   However \c CostMap::Value should be signed type.
     56  /// - Edge capacities and costs should be \e non-negative \e integers.
     57  ///   However \c CostMap::Value must be signed type.
     58  /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.
    5459  ///
    5560  /// \author Peter Kovacs
     
    6570    typedef typename CapacityMap::Value Capacity;
    6671    typedef typename CostMap::Value Cost;
    67     typedef typename Graph::template NodeMap<Capacity> SupplyMap;
     72    typedef typename Graph::template NodeMap<Cost> SupplyMap;
     73
     74    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
    6875    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
    69                             CostMap, SupplyMap >
    70       MinCostFlowImpl;
     76                            CostMap, SupplyMap > MinCostFlowImpl;
    7177
    7278  public:
     
    7480    /// The type of the flow map.
    7581    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
     82    /// The type of the potential map.
     83    typedef typename Graph::template NodeMap<Cost> PotentialMap;
    7684
    7785  private:
    7886
    79     /// The directed graph the algorithm runs on.
    80     const Graph &graph;
    81     /// The modified capacity map.
    82     const CapacityMap &capacity;
    83     /// The cost map.
    84     const CostMap &cost;
    85     /// The edge map of the found flow.
    86     FlowMap flow;
    87     /// The source node.
    88     Node source;
    89     /// The target node.
    90     Node target;
     87    // The directed graph the algorithm runs on
     88    const Graph &_graph;
     89    // The modified capacity map
     90    const CapacityMap &_capacity;
     91    // The cost map
     92    const CostMap &_cost;
    9193
    92     typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
    93     /// \brief \ref Preflow class for finding the maximum flow value.
    94     MaxFlowImpl preflow;
     94    // Edge map of the found flow
     95    FlowMap _flow;
     96    // Node map of the found potentials
     97    PotentialMap _potential;
     98
     99    // The source node
     100    Node _source;
     101    // The target node
     102    Node _target;
    95103
    96104  public:
     
    105113    /// \param _s The source node.
    106114    /// \param _t The target node.
    107     MinCostMaxFlow( const Graph &_graph,
    108                     const CapacityMap &_capacity,
    109                     const CostMap &_cost,
    110                     Node _s, Node _t ) :
    111       graph(_graph), capacity(_capacity), cost(_cost),
    112       source(_s), target(_t), flow(_graph),
    113       preflow(_graph, _capacity, _s, _t)
     115    MinCostMaxFlow( const Graph &graph,
     116                    const CapacityMap &capacity,
     117                    const CostMap &cost,
     118                    Node s, Node t ) :
     119      _graph(graph), _capacity(capacity), _cost(cost), _flow(graph),
     120      _potential(graph), _source(s), _target(t)
    114121    {}
    115122
    116     /// \brief Returns a const reference to the flow map.
     123    /// \brief Runs the algorithm.
    117124    ///
    118     /// Returns a const reference to the flow map.
     125    /// Runs the algorithm.
     126    void run() {
     127      MaxFlowImpl preflow(_graph, _capacity, _source, _target);
     128      preflow.flowMap(_flow).runMinCut();
     129      MinCostFlowImpl mcf( _graph, _capacity, _cost,
     130                           _source, _target, preflow.flowValue() );
     131      mcf.run();
     132      _flow = mcf.flowMap();
     133      _potential = mcf.potentialMap();
     134    }
     135
     136    /// \brief Returns a const reference to the edge map storing the
     137    /// found flow.
     138    ///
     139    /// Returns a const reference to the edge map storing the found flow.
    119140    ///
    120141    /// \pre \ref run() must be called before using this function.
    121142    const FlowMap& flowMap() const {
    122       return flow;
     143      return _flow_result;
     144    }
     145
     146    /// \brief Returns a const reference to the node map storing the
     147    /// found potentials (the dual solution).
     148    ///
     149    /// Returns a const reference to the node map storing the found
     150    /// potentials (the dual solution).
     151    ///
     152    /// \pre \ref run() must be called before using this function.
     153    const PotentialMap& potentialMap() const {
     154      return _potential_result;
    123155    }
    124156
     
    132164      Cost c = 0;
    133165      for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
    134         c += flow[e] * cost[e];
     166        c += _flow[e] * _cost[e];
    135167      return c;
    136     }
    137 
    138     /// \brief Runs the algorithm.
    139     void run() {
    140       preflow.flowMap(flow);
    141       preflow.runMinCut();
    142       MinCostFlowImpl mcf_impl( graph, capacity, cost,
    143                                 source, target, preflow.flowValue() );
    144       mcf_impl.run();
    145       flow = mcf_impl.flowMap();
    146168    }
    147169
Note: See TracChangeset for help on using the changeset viewer.