COIN-OR::LEMON - Graph Library

Changeset 2457:8c791ee69a45 in lemon-0.x for lemon/capacity_scaling.h


Ignore:
Timestamp:
06/15/07 16:36:24 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3294
Message:

Improvments in min cost flow algorithms

  • improved cycle cancelling
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r2440 r2457  
    3232#define WITH_SCALING
    3333
     34//#define _DEBUG_ITER_
     35
    3436namespace lemon {
    3537
     
    3840
    3941  /// \brief Implementation of the capacity scaling version of the
    40   /// succesive shortest path algorithm for finding a minimum cost flow.
     42  /// successive shortest path algorithm for finding a minimum cost flow.
    4143  ///
    4244  /// \ref lemon::CapacityScaling "CapacityScaling" implements a
     
    299301    /// \brief Map for identifing deficit nodes.
    300302    DeficitBoolMap delta_deficit;
     303
     304    /// \brief The deficit nodes.
     305    std::vector<ResNode> deficit_nodes;
    301306
    302307#else //WITHOUT_CAPACITY_SCALING
     
    511516    }
    512517
    513     /// \brief Runs the successive shortest path algorithm.
    514     ///
    515     /// Runs the successive shortest path algorithm.
     518    /// \brief Runs the algorithm.
     519    ///
     520    /// Runs the algorithm.
    516521    ///
    517522    /// \return \c true if a feasible flow can be found.
     
    532537#ifdef WITH_SCALING
    533538      // Initilaizing delta value
    534       Capacity max_cap = 0;
    535       for (EdgeIt e(graph); e != INVALID; ++e) {
    536         if (capacity[e] > max_cap) max_cap = capacity[e];
    537       }
    538       for (delta = 1; 2 * delta < max_cap; delta *= 2) ;
     539      Supply max_sup = 0, max_dem = 0;
     540      for (NodeIt n(graph); n != INVALID; ++n) {
     541        if (supply[n] >  max_sup) max_sup =  supply[n];
     542        if (supply[n] < -max_dem) max_dem = -supply[n];
     543      }
     544      if (max_dem < max_sup) max_sup = max_dem;
     545      for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
    539546#endif
    540547      return true;
     
    547554      typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;
    548555      typedef typename DeltaResGraph::Edge DeltaResEdge;
     556#ifdef _DEBUG_ITER_
     557      int dijk_num = 0;
     558#endif
    549559
    550560      // Processing capacity scaling phases
     
    565575        // Finding excess nodes
    566576        excess_nodes.clear();
     577        deficit_nodes.clear();
    567578        for (ResNodeIt n(res_graph); n != INVALID; ++n) {
    568           if (imbalance[n] >= delta) excess_nodes.push_back(n);
     579          if (imbalance[n] >=  delta) excess_nodes.push_back(n);
     580          if (imbalance[n] <= -delta) deficit_nodes.push_back(n);
    569581        }
    570582        next_node = 0;
    571583
    572         // Finding successive shortest paths
     584        // Finding shortest paths
    573585        while (next_node < excess_nodes.size()) {
     586          // Checking deficit nodes
     587          if (delta > 1) {
     588            bool delta_def = false;
     589            for (int i = 0; i < deficit_nodes.size(); ++i) {
     590              if (imbalance[deficit_nodes[i]] <= -delta) {
     591                delta_def = true;
     592                break;
     593              }
     594            }
     595            if (!delta_def) break;
     596          }
     597
    574598          // Running Dijkstra
    575599          s = excess_nodes[next_node];
     
    577601          dijkstra.init();
    578602          dijkstra.addSource(s);
     603#ifdef _DEBUG_ITER_
     604          ++dijk_num;
     605#endif
    579606          if ((t = dijkstra.start(delta_deficit)) == INVALID) {
    580607            if (delta > 1) {
     
    609636        }
    610637      }
     638#ifdef _DEBUG_ITER_
     639      std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
     640        << dijk_num << " times." << std::endl;
     641#endif
    611642
    612643      // Handling nonzero lower bounds
     
    629660      next_node = 0;
    630661
    631       // Finding successive shortest paths
     662      // Finding shortest paths
    632663      ResNode s, t;
    633664      while ( imbalance[excess_nodes[next_node]] > 0 ||
Note: See TracChangeset for help on using the changeset viewer.