COIN-OR::LEMON - Graph Library

Changeset 2457:8c791ee69a45 in lemon-0.x


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
Location:
lemon
Files:
3 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 ||
  • lemon/cycle_canceling.h

    r2440 r2457  
    2323///
    2424/// \file
    25 /// \brief A cycle canceling algorithm for finding a minimum cost flow.
     25/// \brief A cycle-canceling algorithm for finding a minimum cost flow.
    2626
    2727#include <vector>
     
    2929#include <lemon/graph_adaptor.h>
    3030
    31 /// \brief The used cycle canceling method.
     31/// \brief The used cycle-canceling method.
    3232#define LIMITED_CYCLE_CANCELING
    3333//#define MIN_MEAN_CYCLE_CANCELING
     
    3737  /// \brief The maximum number of iterations for the first execution
    3838  /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
     39  /// It should be at least 2.
    3940  #define STARTING_LIMIT        2
    4041  /// \brief The iteration limit for the
    4142  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
    42   /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
     43  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
     44  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
    4345  #define ALPHA_MUL             3
    4446  /// \brief The iteration limit for the
    4547  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
    46   /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
     48  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
     49  /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
    4750  #define ALPHA_DIV             2
    4851
    4952//#define _ONLY_ONE_CYCLE_
     53//#define _NO_BACK_STEP_
    5054//#define _DEBUG_ITER_
    5155#endif
     
    6165  /// @{
    6266
    63   /// \brief Implementation of a cycle canceling algorithm for finding
     67  /// \brief Implementation of a cycle-canceling algorithm for finding
    6468  /// a minimum cost flow.
    6569  ///
    66   /// \ref lemon::CycleCanceling "CycleCanceling" implements a cycle
    67   /// canceling algorithm for finding a minimum cost flow.
     70  /// \ref lemon::CycleCanceling "CycleCanceling" implements a
     71  /// cycle-canceling algorithm for finding a minimum cost flow.
    6872  ///
    6973  /// \param Graph The directed graph type the algorithm runs on.
     
    119123  protected:
    120124
    121     /// \brief Map adaptor class for demand map.
    122     class DemandMap : public MapBase<Node, Supply>
    123     {
    124     private:
    125 
    126       const SupplyMap *map;
    127 
    128     public:
    129 
    130       typedef typename MapBase<Node, Supply>::Value Value;
    131       typedef typename MapBase<Node, Supply>::Key Key;
    132 
    133       DemandMap(const SupplyMap &_map) : map(&_map) {}
    134 
    135       Value operator[](const Key &e) const {
    136         return -(*map)[e];
    137       }
    138 
    139     }; //class DemandMap
    140 
    141125    /// \brief Map adaptor class for handling residual edge costs.
    142126    class ResCostMap : public MapBase<ResEdge, Cost>
     
    171155    /// \brief The modified supply map.
    172156    SupplyRefMap supply;
    173     /// \brief The modified demand map.
    174     DemandMap demand;
    175157    /// \brief The sum of supply values equals zero.
    176158    bool valid_supply;
     
    200182                    const SupplyMap &_supply ) :
    201183      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    202       supply(_graph), demand(supply), flow(_graph, 0),
     184      supply(_graph), flow(_graph, 0),
    203185      res_graph(_graph, capacity, flow), res_cost(cost)
    204186    {
     
    230212                    const SupplyMap &_supply ) :
    231213      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    232       supply(_supply), demand(supply), flow(_graph, 0),
     214      supply(_supply), flow(_graph, 0),
    233215      res_graph(_graph, capacity, flow), res_cost(cost)
    234216    {
     
    260242                    Supply _flow_value ) :
    261243      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
    262       supply(_graph), demand(supply), flow(_graph, 0),
     244      supply(_graph), flow(_graph, 0),
    263245      res_graph(_graph, capacity, flow), res_cost(cost)
    264246    {
     
    296278                    Supply _flow_value ) :
    297279      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
    298       supply(_graph, 0), demand(supply), flow(_graph, 0),
     280      supply(_graph, 0), flow(_graph, 0),
    299281      res_graph(_graph, capacity, flow), res_cost(cost)
    300282    {
     
    346328      // Finding a feasible flow
    347329      Circulation< Graph, Capacity, FlowMap, ConstMap<Edge, Capacity>,
    348                    CapacityRefMap, DemandMap >
     330                   CapacityRefMap, SupplyMap >
    349331        circulation( graph, constMap<Edge>((Capacity)0),
    350                      capacity, demand, flow );
     332                     capacity, supply, flow );
    351333      return circulation.run() == -1;
    352334    }
    353335
    354336#ifdef LIMITED_CYCLE_CANCELING
    355     /// \brief Executes a cycle canceling algorithm using
     337    /// \brief Executes a cycle-canceling algorithm using
    356338    /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
    357339    /// iteration count.
     
    374356        bool cycle_found = false;
    375357        while (!cycle_found) {
     358#ifdef _NO_BACK_STEP_
     359          int curr_iter_num = length_bound <= node_num ?
     360                              length_bound - iter_num : node_num - iter_num;
     361#else
    376362          int curr_iter_num = iter_num + length_bound <= node_num ?
    377363                              length_bound : node_num - iter_num;
     364#endif
    378365          iter_num += curr_iter_num;
    379366          int real_iter_num = curr_iter_num;
     
    433420
    434421#ifdef _DEBUG_ITER_
    435       std::cout << "Limited cycle canceling algorithm finished. "
     422      std::cout << "Limited cycle-canceling algorithm finished. "
    436423                << "Found " << cycle_num << " negative cycles."
    437424                << std::endl;
     
    448435
    449436#ifdef MIN_MEAN_CYCLE_CANCELING
    450     /// \brief Executes the minimum mean cycle canceling algorithm
     437    /// \brief Executes the minimum mean cycle-canceling algorithm
    451438    /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
    452439    bool start() {
     
    487474
    488475#ifdef _DEBUG_ITER_
    489       std::cout << "Minimum mean cycle canceling algorithm finished. "
     476      std::cout << "Minimum mean cycle-canceling algorithm finished. "
    490477                << "Found " << cycle_num << " negative cycles."
    491478                << std::endl;
  • lemon/network_simplex.h

    r2444 r2457  
    276276
    277277      // Copying graph_ref to graph
     278      graph.reserveNode(countNodes(graph_ref) + 1);
     279      graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
    278280      copyGraph(graph, graph_ref)
    279281        .edgeMap(cost, _cost)
     
    478480      parent[root] = INVALID;
    479481      pred_edge[root] = INVALID;
    480       depth[root] = supply[root] = potential[root] = 0;
     482      depth[root] = 0;
     483      supply[root] = 0;
     484      potential[root] = 0;
    481485
    482486      // Adding artificial edges to the graph and initializing the node
     
    514518      // Initializing block_size for the edge block pivot rule
    515519      int edge_num = countEdges(graph);
    516       block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? 
     520      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
    517521                   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
    518522#endif
Note: See TracChangeset for help on using the changeset viewer.