COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2556:74c2c81055e1 in lemon-0.x for lemon/capacity_scaling.h


Ignore:
Timestamp:
01/13/08 11:32:14 (16 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3437
Message:

Cleanup in the minimum cost flow files.
The changes only affects the documentation and the look of the source codes.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/capacity_scaling.h

    r2553 r2556  
    2323///
    2424/// \file
    25 /// \brief The capacity scaling algorithm for finding a minimum cost
    26 /// flow.
     25/// \brief The capacity scaling algorithm for finding a minimum cost flow.
    2726
    2827#include <lemon/graph_adaptor.h>
    … …  
    5049  ///
    5150  /// \warning
    52   /// - Edge capacities and costs should be nonnegative integers.
     51  /// - Edge capacities and costs should be non-negative integers.
    5352  ///   However \c CostMap::Value should be signed type.
    5453  /// - Supply values should be signed integers.
    … …  
    6766  class CapacityScaling
    6867  {
    69     typedef typename Graph::Node Node;
    70     typedef typename Graph::NodeIt NodeIt;
    71     typedef typename Graph::Edge Edge;
    72     typedef typename Graph::EdgeIt EdgeIt;
    73     typedef typename Graph::InEdgeIt InEdgeIt;
    74     typedef typename Graph::OutEdgeIt OutEdgeIt;
     68    GRAPH_TYPEDEFS(typename Graph);
    7569
    7670    typedef typename LowerMap::Value Lower;
    … …  
    7872    typedef typename CostMap::Value Cost;
    7973    typedef typename SupplyMap::Value Supply;
    80     typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
    81     typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
     74    typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
     75    typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
    8276    typedef typename Graph::template NodeMap<Edge> PredMap;
    8377
    8478  public:
    8579
    86     /// \brief Type to enable or disable capacity scaling.
     80    /// Type to enable or disable capacity scaling.
    8781    enum ScalingEnum {
    8882      WITH_SCALING = 0,
    … …  
    9084    };
    9185
    92     /// \brief The type of the flow map.
    93     typedef CapacityRefMap FlowMap;
    94     /// \brief The type of the potential map.
     86    /// The type of the flow map.
     87    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
     88    /// The type of the potential map.
    9589    typedef typename Graph::template NodeMap<Cost> PotentialMap;
    9690
    … …  
    111105    protected:
    112106
    113       /// \brief The directed graph the algorithm runs on.
     107      /// The directed graph the algorithm runs on.
    114108      const Graph &graph;
    115109
    116       /// \brief The flow map.
     110      /// The flow map.
    117111      const FlowMap &flow;
    118       /// \brief The residual capacity map.
    119       const CapacityRefMap &res_cap;
    120       /// \brief The cost map.
     112      /// The residual capacity map.
     113      const CapacityEdgeMap &res_cap;
     114      /// The cost map.
    121115      const CostMap &cost;
    122       /// \brief The excess map.
    123       const SupplyRefMap &excess;
    124 
    125       /// \brief The potential map.
     116      /// The excess map.
     117      const SupplyNodeMap &excess;
     118
     119      /// The potential map.
    126120      PotentialMap &potential;
    127121
    128       /// \brief The distance map.
     122      /// The distance map.
    129123      CostNodeMap dist;
    130       /// \brief The map of predecessors edges.
     124      /// The map of predecessors edges.
    131125      PredMap &pred;
    132       /// \brief The processed (i.e. permanently labeled) nodes.
     126      /// The processed (i.e. permanently labeled) nodes.
    133127      std::vector<Node> proc_nodes;
    134128
    135129    public:
    136130
    137       /// \brief The constructor of the class.
     131      /// The constructor of the class.
    138132      ResidualDijkstra( const Graph &_graph,
    139133                        const FlowMap &_flow,
    140                         const CapacityRefMap &_res_cap,
     134                        const CapacityEdgeMap &_res_cap,
    141135                        const CostMap &_cost,
    142136                        const SupplyMap &_excess,
    … …  
    148142      {}
    149143
    150       /// \brief Runs the algorithm from the given source node.
     144      /// Runs the algorithm from the given source node.
    151145      Node run(Node s, Capacity delta) {
    152146        HeapCrossRef heap_cross_ref(graph, Heap::PRE_HEAP);
    … …  
    223217  protected:
    224218
    225     /// \brief The directed graph the algorithm runs on.
     219    /// The directed graph the algorithm runs on.
    226220    const Graph &graph;
    227     /// \brief The original lower bound map.
     221    /// The original lower bound map.
    228222    const LowerMap *lower;
    229     /// \brief The modified capacity map.
    230     CapacityRefMap capacity;
    231     /// \brief The cost map.
     223    /// The modified capacity map.
     224    CapacityEdgeMap capacity;
     225    /// The cost map.
    232226    const CostMap &cost;
    233     /// \brief The modified supply map.
    234     SupplyRefMap supply;
    235     /// \brief The sum of supply values equals zero.
     227    /// The modified supply map.
     228    SupplyNodeMap supply;
    236229    bool valid_supply;
    237230
    238     /// \brief The edge map of the current flow.
     231    /// The edge map of the current flow.
    239232    FlowMap flow;
    240     /// \brief The potential node map.
     233    /// The potential node map.
    241234    PotentialMap potential;
    242235
    243     /// \brief The residual capacity map.
    244     CapacityRefMap res_cap;
    245     /// \brief The excess map.
    246     SupplyRefMap excess;
    247     /// \brief The excess nodes (i.e. nodes with positive excess).
     236    /// The residual capacity map.
     237    CapacityEdgeMap res_cap;
     238    /// The excess map.
     239    SupplyNodeMap excess;
     240    /// The excess nodes (i.e. the nodes with positive excess).
    248241    std::vector<Node> excess_nodes;
    249     /// \brief The index of the next excess node.
    250     int next_node;
    251 
    252     /// \brief The scaling status (enabled or disabled).
     242    /// The deficit nodes (i.e. the nodes with negative excess).
     243    std::vector<Node> deficit_nodes;
     244
     245    /// The scaling status (enabled or disabled).
    253246    ScalingEnum scaling;
    254     /// \brief The delta parameter used for capacity scaling.
     247    /// The \c delta parameter used for capacity scaling.
    255248    Capacity delta;
    256     /// \brief The maximum number of phases.
    257     Capacity phase_num;
    258     /// \brief The deficit nodes.
    259     std::vector<Node> deficit_nodes;
     249    /// The maximum number of phases.
     250    int phase_num;
    260251
    261252    /// \brief Implementation of the \ref Dijkstra algorithm for
    262253    /// finding augmenting shortest paths in the residual network.
    263254    ResidualDijkstra dijkstra;
    264     /// \brief The map of predecessors edges.
     255    /// The map of predecessors edges.
    265256    PredMap pred;
    266257
    … …  
    286277      dijkstra(graph, flow, res_cap, cost, excess, potential, pred)
    287278    {
    288       // Removing nonzero lower bounds
     279      // Removing non-zero lower bounds
    289280      capacity = subMap(_capacity, _lower);
    290281      res_cap = capacity;
    … …  
    336327    /// \param _t The target node.
    337328    /// \param _flow_value The required amount of flow from node \c _s
    338     /// to node \c _t (i.e. the supply of \c _s and the demand of
    339     /// \c _t).
     329    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    340330    CapacityScaling( const Graph &_graph,
    341331                     const LowerMap &_lower,
    … …  
    349339      dijkstra(graph, flow, res_cap, cost, excess, potential)
    350340    {
    351       // Removing nonzero lower bounds
     341      // Removing non-zero lower bounds
    352342      capacity = subMap(_capacity, _lower);
    353343      res_cap = capacity;
    … …  
    375365    /// \param _t The target node.
    376366    /// \param _flow_value The required amount of flow from node \c _s
    377     /// to node \c _t (i.e. the supply of \c _s and the demand of
    378     /// \c _t).
     367    /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
    379368    CapacityScaling( const Graph &_graph,
    380369                     const CapacityMap &_capacity,
    … …  
    392381    }
    393382
     383    /// \brief Runs the algorithm.
     384    ///
     385    /// Runs the algorithm.
     386    ///
     387    /// \param scaling_mode The scaling mode. In case of WITH_SCALING
     388    /// capacity scaling is enabled in the algorithm (this is the
     389    /// default) otherwise it is disabled.
     390    /// If the maximum edge capacity and/or the amount of total supply
     391    /// is small, the algorithm could be slightly faster without
     392    /// scaling.
     393    ///
     394    /// \return \c true if a feasible flow can be found.
     395    bool run(int scaling_mode = WITH_SCALING) {
     396      return init(scaling_mode) && start();
     397    }
     398
    394399    /// \brief Returns a const reference to the flow map.
    395400    ///
    … …  
    425430    }
    426431
    427     /// \brief Runs the algorithm.
    428     ///
    429     /// Runs the algorithm.
    430     ///
    431     /// \param scaling_mode The scaling mode. In case of WITH_SCALING
    432     /// capacity scaling is enabled in the algorithm (this is the
    433     /// default value) otherwise it is disabled.
    434     /// If the maximum edge capacity and/or the amount of total supply
    435     /// is small, the algorithm could be faster without scaling.
    436     ///
    437     /// \return \c true if a feasible flow can be found.
    438     bool run(int scaling_mode = WITH_SCALING) {
    439       return init(scaling_mode) && start();
    440     }
    441 
    442432  protected:
    443433
    444     /// \brief Initializes the algorithm.
     434    /// Initializes the algorithm.
    445435    bool init(int scaling_mode) {
    446436      if (!valid_supply) return false;
    … …  
    466456    }
    467457
    468     /// \brief Executes the algorithm.
     458    /// Executes the algorithm.
    469459    bool start() {
    470460      if (delta > 1)
    … …  
    507497          if (excess[n] <= -delta) deficit_nodes.push_back(n);
    508498        }
    509         next_node = 0;
     499        int next_node = 0;
    510500
    511501        // Finding augmenting shortest paths
    … …  
    573563      }
    574564
    575       // Handling nonzero lower bounds
     565      // Handling non-zero lower bounds
    576566      if (lower) {
    577567        for (EdgeIt e(graph); e != INVALID; ++e)
    … …  
    585575    bool startWithoutScaling() {
    586576      // Finding excess nodes
    587       for (NodeIt n(graph); n != INVALID; ++n) {
     577      for (NodeIt n(graph); n != INVALID; ++n)
    588578        if (excess[n] > 0) excess_nodes.push_back(n);
    589       }
    590579      if (excess_nodes.size() == 0) return true;
    591       next_node = 0;
     580      int next_node = 0;
    592581
    593582      // Finding shortest paths
    … …  
    632621      }
    633622
    634       // Handling nonzero lower bounds
     623      // Handling non-zero lower bounds
    635624      if (lower) {
    636625        for (EdgeIt e(graph); e != INVALID; ++e)
Note: See TracChangeset for help on using the changeset viewer.