Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/cost_scaling.h
changeset 2620 8f41a3129746
parent 2588 4d3bc1d04c1d
child 2623 90defb96ee61
equal deleted inserted replaced
2:7337a468dbbf 3:7ebd3c268c39 
    62   /// other minimum cost flow algorithms.
 
    62   /// other minimum cost flow algorithms.
 
    63   /// If it is available, <tt>long long int</tt> type is used instead of
 
    63   /// If it is available, <tt>long long int</tt> type is used instead of
 
    64   /// <tt>long int</tt> in the inside computations.
 
    64   /// <tt>long int</tt> in the inside computations.
 
    65   ///
 
    65   ///
 
    66   /// \author Peter Kovacs
 
    66   /// \author Peter Kovacs
 
    67 
       
    68   template < typename Graph,
 
    67   template < typename Graph,
 
    69              typename LowerMap = typename Graph::template EdgeMap<int>,
 
    68              typename LowerMap = typename Graph::template EdgeMap<int>,
 
    70              typename CapacityMap = typename Graph::template EdgeMap<int>,
 
    69              typename CapacityMap = typename Graph::template EdgeMap<int>,
 
    71              typename CostMap = typename Graph::template EdgeMap<int>,
 
    70              typename CostMap = typename Graph::template EdgeMap<int>,
 
    72              typename SupplyMap = typename Graph::template NodeMap<int> >
 
    71              typename SupplyMap = typename Graph::template NodeMap<int> >
 
   100 
    99 
   101   private:
 
   100   private:
 
   102 
   101 
   103     /// \brief Map adaptor class for handling residual edge costs.
 
   102     /// \brief Map adaptor class for handling residual edge costs.
 
   104     ///
 
   103     ///
 
   105     /// \ref ResidualCostMap is a map adaptor class for handling
 
   104     /// Map adaptor class for handling residual edge costs.
 
   106     /// residual edge costs.
 
       
   107     template <typename Map>
 
   105     template <typename Map>
 
   108     class ResidualCostMap : public MapBase<ResEdge, typename Map::Value>
 
   106     class ResidualCostMap : public MapBase<ResEdge, typename Map::Value>
 
   109     {
 
   107     {
 
   110     private:
 
   108     private:
 
   111 
   109 
   124 
   122 
   125     }; //class ResidualCostMap
 
   123     }; //class ResidualCostMap
 
   126 
   124 
   127     /// \brief Map adaptor class for handling reduced edge costs.
 
   125     /// \brief Map adaptor class for handling reduced edge costs.
 
   128     ///
 
   126     ///
 
   129     /// \ref ReducedCostMap is a map adaptor class for handling reduced
 
   127     /// Map adaptor class for handling reduced edge costs.
 
   130     /// edge costs.
 
       
   131     class ReducedCostMap : public MapBase<Edge, LCost>
 
   128     class ReducedCostMap : public MapBase<Edge, LCost>
 
   132     {
 
   129     {
 
   133     private:
 
   130     private:
 
   134 
   131 
   135       const Graph &_gr;
 
   132       const Graph &_gr;
 
   324       if (_local_potential) delete _potential;
 
   321       if (_local_potential) delete _potential;
 
   325       delete _res_graph;
 
   322       delete _res_graph;
 
   326       delete _red_cost;
 
   323       delete _red_cost;
 
   327     }
 
   324     }
 
   328 
   325 
   329     /// \brief Sets the flow map.
 
   326     /// \brief Set the flow map.
 
   330     ///
 
   327     ///
 
   331     /// Sets the flow map.
 
   328     /// Set the flow map.
 
   332     ///
 
   329     ///
 
   333     /// \return \c (*this)
 
   330     /// \return \c (*this)
 
   334     CostScaling& flowMap(FlowMap &map) {
 
   331     CostScaling& flowMap(FlowMap &map) {
 
   335       if (_local_flow) {
 
   332       if (_local_flow) {
 
   336         delete _flow;
 
   333         delete _flow;
 
   338       }
 
   335       }
 
   339       _flow = &map;
 
   336       _flow = &map;
 
   340       return *this;
 
   337       return *this;
 
   341     }
 
   338     }
 
   342 
   339 
   343     /// \brief Sets the potential map.
 
   340     /// \brief Set the potential map.
 
   344     ///
 
   341     ///
 
   345     /// Sets the potential map.
 
   342     /// Set the potential map.
 
   346     ///
 
   343     ///
 
   347     /// \return \c (*this)
 
   344     /// \return \c (*this)
 
   348     CostScaling& potentialMap(PotentialMap &map) {
 
   345     CostScaling& potentialMap(PotentialMap &map) {
 
   349       if (_local_potential) {
 
   346       if (_local_potential) {
 
   350         delete _potential;
 
   347         delete _potential;
 
   353       _potential = &map;
 
   350       _potential = &map;
 
   354       return *this;
 
   351       return *this;
 
   355     }
 
   352     }
 
   356 
   353 
   357     /// \name Execution control
 
   354     /// \name Execution control
 
   358     /// The only way to execute the algorithm is to call the run()
 
       
   359     /// function.
 
       
   360 
   355 
   361     /// @{
 
   356     /// @{
 
   362 
   357 
   363     /// \brief Runs the algorithm.
 
   358     /// \brief Run the algorithm.
 
   364     ///
 
   359     ///
 
   365     /// Runs the algorithm.
 
   360     /// Run the algorithm.
 
   366     ///
 
   361     ///
 
   367     /// \return \c true if a feasible flow can be found.
 
   362     /// \return \c true if a feasible flow can be found.
 
   368     bool run() {
 
   363     bool run() {
 
   369       return init() && start();
 
   364       return init() && start();
 
   370     }
 
   365     }
 
   371 
   366 
   372     /// @}
 
   367     /// @}
 
   373 
   368 
   374     /// \name Query Functions
 
   369     /// \name Query Functions
 
   375     /// The result of the algorithm can be obtained using these
 
   370     /// The result of the algorithm can be obtained using these
 
   376     /// functions.
 
   371     /// functions.\n
 
   377     /// \n run() must be called before using them.
 
   372     /// \ref lemon::CostScaling::run() "run()" must be called before
 
       
   373     /// using them.
 
   378 
   374 
   379     /// @{
 
   375     /// @{
 
   380 
   376 
   381     /// \brief Returns a const reference to the edge map storing the
 
   377     /// \brief Return a const reference to the edge map storing the
 
   382     /// found flow.
 
   378     /// found flow.
 
   383     ///
 
   379     ///
 
   384     /// Returns a const reference to the edge map storing the found flow.
 
   380     /// Return a const reference to the edge map storing the found flow.
 
   385     ///
 
   381     ///
 
   386     /// \pre \ref run() must be called before using this function.
 
   382     /// \pre \ref run() must be called before using this function.
 
   387     const FlowMap& flowMap() const {
 
   383     const FlowMap& flowMap() const {
 
   388       return *_flow;
 
   384       return *_flow;
 
   389     }
 
   385     }
 
   390 
   386 
   391     /// \brief Returns a const reference to the node map storing the
 
   387     /// \brief Return a const reference to the node map storing the
 
   392     /// found potentials (the dual solution).
 
   388     /// found potentials (the dual solution).
 
   393     ///
 
   389     ///
 
   394     /// Returns a const reference to the node map storing the found
 
   390     /// Return a const reference to the node map storing the found
 
   395     /// potentials (the dual solution).
 
   391     /// potentials (the dual solution).
 
   396     ///
 
   392     ///
 
   397     /// \pre \ref run() must be called before using this function.
 
   393     /// \pre \ref run() must be called before using this function.
 
   398     const PotentialMap& potentialMap() const {
 
   394     const PotentialMap& potentialMap() const {
 
   399       return *_potential;
 
   395       return *_potential;
 
   400     }
 
   396     }
 
   401 
   397 
   402     /// \brief Returns the flow on the given edge.
 
   398     /// \brief Return the flow on the given edge.
 
   403     ///
 
   399     ///
 
   404     /// Returns the flow on the given edge.
 
   400     /// Return the flow on the given edge.
 
   405     ///
 
   401     ///
 
   406     /// \pre \ref run() must be called before using this function.
 
   402     /// \pre \ref run() must be called before using this function.
 
   407     Capacity flow(const Edge& edge) const {
 
   403     Capacity flow(const Edge& edge) const {
 
   408       return (*_flow)[edge];
 
   404       return (*_flow)[edge];
 
   409     }
 
   405     }
 
   410 
   406 
   411     /// \brief Returns the potential of the given node.
 
   407     /// \brief Return the potential of the given node.
 
   412     ///
 
   408     ///
 
   413     /// Returns the potential of the given node.
 
   409     /// Return the potential of the given node.
 
   414     ///
 
   410     ///
 
   415     /// \pre \ref run() must be called before using this function.
 
   411     /// \pre \ref run() must be called before using this function.
 
   416     Cost potential(const Node& node) const {
 
   412     Cost potential(const Node& node) const {
 
   417       return (*_potential)[node];
 
   413       return (*_potential)[node];
 
   418     }
 
   414     }
 
   419 
   415 
   420     /// \brief Returns the total cost of the found flow.
 
   416     /// \brief Return the total cost of the found flow.
 
   421     ///
 
   417     ///
 
   422     /// Returns the total cost of the found flow. The complexity of the
 
   418     /// Return the total cost of the found flow. The complexity of the
 
   423     /// function is \f$ O(e) \f$.
 
   419     /// function is \f$ O(e) \f$.
 
   424     ///
 
   420     ///
 
   425     /// \pre \ref run() must be called before using this function.
 
   421     /// \pre \ref run() must be called before using this function.
 
   426     Cost totalCost() const {
 
   422     Cost totalCost() const {
 
   427       Cost c = 0;
 
   423       Cost c = 0;
 
   432 
   428 
   433     /// @}
 
   429     /// @}
 
   434 
   430 
   435   private:
 
   431   private:
 
   436 
   432 
   437     /// Initializes the algorithm.
 
   433     /// Initialize the algorithm.
 
   438     bool init() {
 
   434     bool init() {
 
   439       if (!_valid_supply) return false;
 
   435       if (!_valid_supply) return false;
 
   440 
   436 
   441       // Initializing flow and potential maps
 
   437       // Initializing flow and potential maps
 
   442       if (!_flow) {
 
   438       if (!_flow) {
 
   467                      _supply );
 
   463                      _supply );
 
   468       return circulation.flowMap(*_flow).run();
 
   464       return circulation.flowMap(*_flow).run();
 
   469     }
 
   465     }
 
   470 
   466 
   471 
   467 
   472     /// Executes the algorithm.
 
   468     /// Execute the algorithm.
 
   473     bool start() {
 
   469     bool start() {
 
   474       std::deque<Node> active_nodes;
 
   470       std::deque<Node> active_nodes;
 
   475       typename Graph::template NodeMap<bool> hyper(_graph, false);
 
   471       typename Graph::template NodeMap<bool> hyper(_graph, false);
 
   476 
   472 
   477       int node_num = countNodes(_graph);
 
   473       int node_num = countNodes(_graph);
lemon-0.x