COIN-OR::LEMON - Graph Library

Changeset 2581:054566ac0934 in lemon-0.x for lemon/cycle_canceling.h


Ignore:
Timestamp:
02/28/08 03:54:27 (12 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3463
Message:

Query improvements in the min cost flow algorithms.

  • External flow and potential maps can be used.
  • New query functions: flow() and potential().
  • CycleCanceling? also provides dual solution (node potentials).
  • Doc improvements.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cycle_canceling.h

    r2573 r2581  
    5353  /// - Edge capacities and costs should be \e non-negative \e integers.
    5454  /// - Supply values should be \e signed \e integers.
    55   /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
    56   /// - \c CapacityMap::Value and \c SupplyMap::Value must be
    57   ///   convertible to each other.
    58   /// - All value types must be convertible to \c CostMap::Value, which
    59   ///   must be signed type.
     55  /// - The value types of the maps should be convertible to each other.
     56  /// - \c CostMap::Value must be signed type.
    6057  ///
    6158  /// \note By default the \ref BellmanFord "Bellman-Ford" algorithm is
     
    9592    /// The type of the flow map.
    9693    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
     94    /// The type of the potential map.
     95    typedef typename Graph::template NodeMap<Cost> PotentialMap;
    9796
    9897  private:
     
    144143
    145144    // Edge map of the current flow
    146     FlowMap _flow;
     145    FlowMap *_flow;
     146    bool _local_flow;
     147    // Node map of the current potentials
     148    PotentialMap *_potential;
     149    bool _local_potential;
    147150
    148151    // The residual graph
    149     ResGraph _res_graph;
     152    ResGraph *_res_graph;
    150153    // The residual cost map
    151154    ResidualCostMap _res_cost;
     
    153156  public:
    154157
    155     /// \brief General constructor of the class (with lower bounds).
    156     ///
    157     /// General constructor of the class (with lower bounds).
     158    /// \brief General constructor (with lower bounds).
     159    ///
     160    /// General constructor (with lower bounds).
    158161    ///
    159162    /// \param graph The directed graph the algorithm runs on.
     
    168171                    const SupplyMap &supply ) :
    169172      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    170       _supply(graph), _flow(graph, 0),
    171       _res_graph(graph, _capacity, _flow), _res_cost(_cost)
     173      _supply(graph), _flow(0), _local_flow(false),
     174      _potential(0), _local_potential(false), _res_cost(_cost)
    172175    {
    173176      // Removing non-zero lower bounds
     
    185188    }
    186189
    187     /// \brief General constructor of the class (without lower bounds).
    188     ///
    189     /// General constructor of the class (without lower bounds).
     190    /// \brief General constructor (without lower bounds).
     191    ///
     192    /// General constructor (without lower bounds).
    190193    ///
    191194    /// \param graph The directed graph the algorithm runs on.
     
    198201                    const SupplyMap &supply ) :
    199202      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
    200       _supply(supply), _flow(graph, 0),
    201       _res_graph(graph, _capacity, _flow), _res_cost(_cost)
     203      _supply(supply), _flow(0), _local_flow(false),
     204      _potential(0), _local_potential(false), _res_cost(_cost)
    202205    {
    203206      // Checking the sum of supply values
     
    207210    }
    208211
    209     /// \brief Simple constructor of the class (with lower bounds).
    210     ///
    211     /// Simple constructor of the class (with lower bounds).
     212    /// \brief Simple constructor (with lower bounds).
     213    ///
     214    /// Simple constructor (with lower bounds).
    212215    ///
    213216    /// \param graph The directed graph the algorithm runs on.
     
    226229                    Supply flow_value ) :
    227230      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    228       _supply(graph), _flow(graph, 0),
    229       _res_graph(graph, _capacity, _flow), _res_cost(_cost)
     231      _supply(graph), _flow(0), _local_flow(false),
     232      _potential(0), _local_potential(false), _res_cost(_cost)
    230233    {
    231234      // Removing non-zero lower bounds
     
    244247    }
    245248
    246     /// \brief Simple constructor of the class (without lower bounds).
    247     ///
    248     /// Simple constructor of the class (without lower bounds).
     249    /// \brief Simple constructor (without lower bounds).
     250    ///
     251    /// Simple constructor (without lower bounds).
    249252    ///
    250253    /// \param graph The directed graph the algorithm runs on.
     
    261264                    Supply flow_value ) :
    262265      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
    263       _supply(graph, 0), _flow(graph, 0),
    264       _res_graph(graph, _capacity, _flow), _res_cost(_cost)
     266      _supply(graph, 0), _flow(0), _local_flow(false),
     267      _potential(0), _local_potential(false), _res_cost(_cost)
    265268    {
    266269      _supply[s] =  flow_value;
     
    269272    }
    270273
     274    /// Destructor.
     275    ~CycleCanceling() {
     276      if (_local_flow) delete _flow;
     277      if (_local_potential) delete _potential;
     278      delete _res_graph;
     279    }
     280
     281    /// \brief Sets the flow map.
     282    ///
     283    /// Sets the flow map.
     284    ///
     285    /// \return \c (*this)
     286    CycleCanceling& flowMap(FlowMap &map) {
     287      if (_local_flow) {
     288        delete _flow;
     289        _local_flow = false;
     290      }
     291      _flow = &map;
     292      return *this;
     293    }
     294
     295    /// \brief Sets the potential map.
     296    ///
     297    /// Sets the potential map.
     298    ///
     299    /// \return \c (*this)
     300    CycleCanceling& potentialMap(PotentialMap &map) {
     301      if (_local_potential) {
     302        delete _potential;
     303        _local_potential = false;
     304      }
     305      _potential = &map;
     306      return *this;
     307    }
     308
     309    /// \name Execution control
     310    /// The only way to execute the algorithm is to call the run()
     311    /// function.
     312
     313    /// @{
     314
    271315    /// \brief Runs the algorithm.
    272316    ///
     
    282326    }
    283327
     328    /// @}
     329
     330    /// \name Query Functions
     331    /// The result of the algorithm can be obtained using these
     332    /// functions.
     333    /// \n run() must be called before using them.
     334
     335    /// @{
     336
    284337    /// \brief Returns a const reference to the edge map storing the
    285338    /// found flow.
     
    289342    /// \pre \ref run() must be called before using this function.
    290343    const FlowMap& flowMap() const {
    291       return _flow;
     344      return *_flow;
     345    }
     346
     347    /// \brief Returns a const reference to the node map storing the
     348    /// found potentials (the dual solution).
     349    ///
     350    /// Returns a const reference to the node map storing the found
     351    /// potentials (the dual solution).
     352    ///
     353    /// \pre \ref run() must be called before using this function.
     354    const PotentialMap& potentialMap() const {
     355      return *_potential;
     356    }
     357
     358    /// \brief Returns the flow on the edge.
     359    ///
     360    /// Returns the flow on the edge.
     361    ///
     362    /// \pre \ref run() must be called before using this function.
     363    Capacity flow(const Edge& edge) const {
     364      return (*_flow)[edge];
     365    }
     366
     367    /// \brief Returns the potential of the node.
     368    ///
     369    /// Returns the potential of the node.
     370    ///
     371    /// \pre \ref run() must be called before using this function.
     372    Cost potential(const Node& node) const {
     373      return (*_potential)[node];
    292374    }
    293375
     
    301383      Cost c = 0;
    302384      for (EdgeIt e(_graph); e != INVALID; ++e)
    303         c += _flow[e] * _cost[e];
     385        c += (*_flow)[e] * _cost[e];
    304386      return c;
    305387    }
     388
     389    /// @}
    306390
    307391  private:
     
    311395      if (!_valid_supply) return false;
    312396
     397      // Initializing flow and potential maps
     398      if (!_flow) {
     399        _flow = new FlowMap(_graph);
     400        _local_flow = true;
     401      }
     402      if (!_potential) {
     403        _potential = new PotentialMap(_graph);
     404        _local_potential = true;
     405      }
     406
     407      _res_graph = new ResGraph(_graph, _capacity, *_flow);
     408
    313409      // Finding a feasible flow using Circulation
    314410      Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
    315411                   SupplyMap >
    316         circulation( _graph, constMap<Edge>((Capacity)0), _capacity,
     412        circulation( _graph, constMap<Edge>(Capacity(0)), _capacity,
    317413                     _supply );
    318       return circulation.flowMap(_flow).run();
     414      return circulation.flowMap(*_flow).run();
    319415    }
    320416
    321417    bool start(bool min_mean_cc) {
    322418      if (min_mean_cc)
    323         return startMinMean();
     419        startMinMean();
    324420      else
    325         return start();
     421        start();
     422
     423      // Handling non-zero lower bounds
     424      if (_lower) {
     425        for (EdgeIt e(_graph); e != INVALID; ++e)
     426          (*_flow)[e] += (*_lower)[e];
     427      }
     428      return true;
    326429    }
    327430
     
    331434    /// "Bellman-Ford" algorithm for negative cycle detection with
    332435    /// successively larger limit for the number of iterations.
    333     bool start() {
    334       typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(_res_graph);
    335       typename ResGraph::template NodeMap<int> visited(_res_graph);
     436    void start() {
     437      typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(*_res_graph);
     438      typename ResGraph::template NodeMap<int> visited(*_res_graph);
    336439      std::vector<ResEdge> cycle;
    337440      int node_num = countNodes(_graph);
     
    340443      bool optimal = false;
    341444      while (!optimal) {
    342         BellmanFord<ResGraph, ResidualCostMap> bf(_res_graph, _res_cost);
     445        BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost);
    343446        bf.predMap(pred);
    344447        bf.init(0);
     
    357460          }
    358461          if (real_iter_num < curr_iter_num) {
     462            // Optimal flow is found
    359463            optimal = true;
     464            // Setting node potentials
     465            for (NodeIt n(_graph); n != INVALID; ++n)
     466              (*_potential)[n] = bf.dist(n);
    360467            break;
    361468          } else {
    362469            // Searching for node disjoint negative cycles
    363             for (ResNodeIt n(_res_graph); n != INVALID; ++n)
     470            for (ResNodeIt n(*_res_graph); n != INVALID; ++n)
    364471              visited[n] = 0;
    365472            int id = 0;
    366             for (ResNodeIt n(_res_graph); n != INVALID; ++n) {
     473            for (ResNodeIt n(*_res_graph); n != INVALID; ++n) {
    367474              if (visited[n] > 0) continue;
    368475              visited[n] = ++id;
    369476              ResNode u = pred[n] == INVALID ?
    370                           INVALID : _res_graph.source(pred[n]);
     477                          INVALID : _res_graph->source(pred[n]);
    371478              while (u != INVALID && visited[u] == 0) {
    372479                visited[u] = id;
    373480                u = pred[u] == INVALID ?
    374                     INVALID : _res_graph.source(pred[u]);
     481                    INVALID : _res_graph->source(pred[u]);
    375482              }
    376483              if (u != INVALID && visited[u] == id) {
     
    380487                ResEdge e = pred[u];
    381488                cycle.push_back(e);
    382                 Capacity d = _res_graph.rescap(e);
    383                 while (_res_graph.source(e) != u) {
    384                   cycle.push_back(e = pred[_res_graph.source(e)]);
    385                   if (_res_graph.rescap(e) < d)
    386                     d = _res_graph.rescap(e);
     489                Capacity d = _res_graph->rescap(e);
     490                while (_res_graph->source(e) != u) {
     491                  cycle.push_back(e = pred[_res_graph->source(e)]);
     492                  if (_res_graph->rescap(e) < d)
     493                    d = _res_graph->rescap(e);
    387494                }
    388495
    389496                // Augmenting along the cycle
    390497                for (int i = 0; i < int(cycle.size()); ++i)
    391                   _res_graph.augment(cycle[i], d);
     498                  _res_graph->augment(cycle[i], d);
    392499              }
    393500            }
     
    398505        }
    399506      }
    400 
    401       // Handling non-zero lower bounds
    402       if (_lower) {
    403         for (EdgeIt e(_graph); e != INVALID; ++e)
    404           _flow[e] += (*_lower)[e];
    405       }
    406       return true;
    407507    }
    408508
     
    411511    /// Executes the algorithm using \ref MinMeanCycle for negative
    412512    /// cycle detection.
    413     bool startMinMean() {
     513    void startMinMean() {
    414514      typedef Path<ResGraph> ResPath;
    415       MinMeanCycle<ResGraph, ResidualCostMap> mmc(_res_graph, _res_cost);
     515      MinMeanCycle<ResGraph, ResidualCostMap> mmc(*_res_graph, _res_cost);
    416516      ResPath cycle;
    417517
     
    426526          Capacity delta = 0;
    427527          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
    428             if (delta == 0 || _res_graph.rescap(e) < delta)
    429               delta = _res_graph.rescap(e);
     528            if (delta == 0 || _res_graph->rescap(e) < delta)
     529              delta = _res_graph->rescap(e);
    430530          }
    431531
    432532          // Augmenting along the cycle
    433533          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
    434             _res_graph.augment(e, delta);
     534            _res_graph->augment(e, delta);
    435535
    436536          // Finding the minimum cycle mean for the modified residual
     
    441541      }
    442542
    443       // Handling non-zero lower bounds
    444       if (_lower) {
    445         for (EdgeIt e(_graph); e != INVALID; ++e)
    446           _flow[e] += (*_lower)[e];
    447       }
    448       return true;
     543      // Computing node potentials
     544      BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost);
     545      bf.init(0); bf.start();
     546      for (NodeIt n(_graph); n != INVALID; ++n)
     547        (*_potential)[n] = bf.dist(n);
    449548    }
    450549
Note: See TracChangeset for help on using the changeset viewer.