COIN-OR::LEMON - Graph Library

Changeset 2581:054566ac0934 in lemon-0.x for lemon/network_simplex.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/network_simplex.h

    r2579 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 \ref NetworkSimplex provides six different pivot rule
     
    470467
    471468    // Members for handling the original graph
    472     FlowMap _flow_result;
    473     PotentialMap _potential_result;
     469    FlowMap *_flow_result;
     470    PotentialMap *_potential_result;
     471    bool _local_flow;
     472    bool _local_potential;
    474473    NodeRefMap _node_ref;
    475474    EdgeRefMap _edge_ref;
     
    488487  public :
    489488
    490     /// \brief General constructor of the class (with lower bounds).
    491     ///
    492     /// General constructor of the class (with lower bounds).
     489    /// \brief General constructor (with lower bounds).
     490    ///
     491    /// General constructor (with lower bounds).
    493492    ///
    494493    /// \param graph The directed graph the algorithm runs on.
     
    507506      _pred_edge(_graph), _thread(_graph), _forward(_graph),
    508507      _state(_graph), _red_cost(_graph, _cost, _potential),
    509       _flow_result(graph), _potential_result(graph),
     508      _flow_result(0), _potential_result(0),
     509      _local_flow(false), _local_potential(false),
    510510      _node_ref(graph), _edge_ref(graph)
    511511    {
     
    539539    }
    540540
    541     /// \brief General constructor of the class (without lower bounds).
    542     ///
    543     /// General constructor of the class (without lower bounds).
     541    /// \brief General constructor (without lower bounds).
     542    ///
     543    /// General constructor (without lower bounds).
    544544    ///
    545545    /// \param graph The directed graph the algorithm runs on.
     
    556556      _pred_edge(_graph), _thread(_graph), _forward(_graph),
    557557      _state(_graph), _red_cost(_graph, _cost, _potential),
    558       _flow_result(graph), _potential_result(graph),
     558      _flow_result(0), _potential_result(0),
     559      _local_flow(false), _local_potential(false),
    559560      _node_ref(graph), _edge_ref(graph)
    560561    {
     
    575576    }
    576577
    577     /// \brief Simple constructor of the class (with lower bounds).
    578     ///
    579     /// Simple constructor of the class (with lower bounds).
     578    /// \brief Simple constructor (with lower bounds).
     579    ///
     580    /// Simple constructor (with lower bounds).
    580581    ///
    581582    /// \param graph The directed graph the algorithm runs on.
     
    599600      _pred_edge(_graph), _thread(_graph), _forward(_graph),
    600601      _state(_graph), _red_cost(_graph, _cost, _potential),
    601       _flow_result(graph), _potential_result(graph),
     602      _flow_result(0), _potential_result(0),
     603      _local_flow(false), _local_potential(false),
    602604      _node_ref(graph), _edge_ref(graph)
    603605    {
     
    626628    }
    627629
    628     /// \brief Simple constructor of the class (without lower bounds).
    629     ///
    630     /// Simple constructor of the class (without lower bounds).
     630    /// \brief Simple constructor (without lower bounds).
     631    ///
     632    /// Simple constructor (without lower bounds).
    631633    ///
    632634    /// \param graph The directed graph the algorithm runs on.
     
    648650      _pred_edge(_graph), _thread(_graph), _forward(_graph),
    649651      _state(_graph), _red_cost(_graph, _cost, _potential),
    650       _flow_result(graph), _potential_result(graph),
     652      _flow_result(0), _potential_result(0),
     653      _local_flow(false), _local_potential(false),
    651654      _node_ref(graph), _edge_ref(graph)
    652655    {
     
    663666    }
    664667
     668    /// Destructor.
     669    ~NetworkSimplex() {
     670      if (_local_flow) delete _flow_result;
     671      if (_local_potential) delete _potential_result;
     672    }
     673
     674    /// \brief Sets the flow map.
     675    ///
     676    /// Sets the flow map.
     677    ///
     678    /// \return \c (*this)
     679    NetworkSimplex& flowMap(FlowMap &map) {
     680      if (_local_flow) {
     681        delete _flow_result;
     682        _local_flow = false;
     683      }
     684      _flow_result = ↦
     685      return *this;
     686    }
     687
     688    /// \brief Sets the potential map.
     689    ///
     690    /// Sets the potential map.
     691    ///
     692    /// \return \c (*this)
     693    NetworkSimplex& potentialMap(PotentialMap &map) {
     694      if (_local_potential) {
     695        delete _potential_result;
     696        _local_potential = false;
     697      }
     698      _potential_result = ↦
     699      return *this;
     700    }
     701
     702    /// \name Execution control
     703    /// The only way to execute the algorithm is to call the run()
     704    /// function.
     705
     706    /// @{
     707
    665708    /// \brief Runs the algorithm.
    666709    ///
     
    704747    }
    705748
     749    /// @}
     750
     751    /// \name Query Functions
     752    /// The result of the algorithm can be obtained using these
     753    /// functions.
     754    /// \n run() must be called before using them.
     755
     756    /// @{
     757
    706758    /// \brief Returns a const reference to the edge map storing the
    707759    /// found flow.
     
    711763    /// \pre \ref run() must be called before using this function.
    712764    const FlowMap& flowMap() const {
    713       return _flow_result;
     765      return *_flow_result;
    714766    }
    715767
     
    722774    /// \pre \ref run() must be called before using this function.
    723775    const PotentialMap& potentialMap() const {
    724       return _potential_result;
     776      return *_potential_result;
     777    }
     778
     779    /// \brief Returns the flow on the edge.
     780    ///
     781    /// Returns the flow on the edge.
     782    ///
     783    /// \pre \ref run() must be called before using this function.
     784    Capacity flow(const typename Graph::Edge& edge) const {
     785      return (*_flow_result)[edge];
     786    }
     787
     788    /// \brief Returns the potential of the node.
     789    ///
     790    /// Returns the potential of the node.
     791    ///
     792    /// \pre \ref run() must be called before using this function.
     793    Cost potential(const typename Graph::Node& node) const {
     794      return (*_potential_result)[node];
    725795    }
    726796
     
    734804      Cost c = 0;
    735805      for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
    736         c += _flow_result[e] * _cost[_edge_ref[e]];
     806        c += (*_flow_result)[e] * _cost[_edge_ref[e]];
    737807      return c;
    738808    }
     809
     810    /// @}
    739811
    740812  private:
     
    744816    bool init() {
    745817      if (!_valid_supply) return false;
     818
     819      // Initializing result maps
     820      if (!_flow_result) {
     821        _flow_result = new FlowMap(_graph_ref);
     822        _local_flow = true;
     823      }
     824      if (!_potential_result) {
     825        _potential_result = new PotentialMap(_graph_ref);
     826        _local_potential = true;
     827      }
    746828
    747829      // Initializing state and flow maps
     
    10161098      if (_lower) {
    10171099        for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
    1018           _flow_result[e] = (*_lower)[e] + _flow[_edge_ref[e]];
     1100          (*_flow_result)[e] = (*_lower)[e] + _flow[_edge_ref[e]];
    10191101      } else {
    10201102        for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
    1021           _flow_result[e] = _flow[_edge_ref[e]];
     1103          (*_flow_result)[e] = _flow[_edge_ref[e]];
    10221104      }
    10231105      // Copying potential values to _potential_result
    10241106      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
    1025         _potential_result[n] = _potential[_node_ref[n]];
     1107        (*_potential_result)[n] = _potential[_node_ref[n]];
    10261108
    10271109      return true;
Note: See TracChangeset for help on using the changeset viewer.