COIN-OR::LEMON - Graph Library

Changeset 956:141f9c0db4a3 in lemon for lemon/cycle_canceling.h


Ignore:
Timestamp:
03/06/10 15:35:12 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
957:f802439d2b58, 959:38213abd2911, 1041:f112c18bc304
Phase:
public
Message:

Unify the sources (#339)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cycle_canceling.h

    r942 r956  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    143143
    144144    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    145    
     145
    146146    typedef std::vector<int> IntVector;
    147147    typedef std::vector<double> DoubleVector;
     
    152152
    153153  private:
    154  
     154
    155155    template <typename KT, typename VT>
    156156    class StaticVectorMap {
     
    158158      typedef KT Key;
    159159      typedef VT Value;
    160      
     160
    161161      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
    162      
     162
    163163      const Value& operator[](const Key& key) const {
    164164        return _v[StaticDigraph::id(key)];
     
    168168        return _v[StaticDigraph::id(key)];
    169169      }
    170      
     170
    171171      void set(const Key& key, const Value& val) {
    172172        _v[StaticDigraph::id(key)] = val;
     
    222222    CostArcMap _cost_map;
    223223    CostNodeMap _pi_map;
    224  
     224
    225225  public:
    226  
     226
    227227    /// \brief Constant for infinite upper bounds (capacities).
    228228    ///
     
    367367      return *this;
    368368    }
    369    
     369
    370370    /// @}
    371371
     
    467467        _cost[j] = 0;
    468468        _cost[_reverse[j]] = 0;
    469       }     
     469      }
    470470      _have_lower = false;
    471471      return *this;
     
    509509      _cost.resize(_res_arc_num);
    510510      _supply.resize(_res_node_num);
    511      
     511
    512512      _res_cap.resize(_res_arc_num);
    513513      _pi.resize(_res_node_num);
     
    555555        _reverse[bi] = fi;
    556556      }
    557      
     557
    558558      // Reset parameters
    559559      resetParams();
     
    664664      }
    665665      if (_sum_supply > 0) return INFEASIBLE;
    666      
     666
    667667
    668668      // Initialize vectors
     
    671671      }
    672672      ValueVector excess(_supply);
    673      
     673
    674674      // Remove infinite upper bounds and check negative arcs
    675675      const Value MAX = std::numeric_limits<Value>::max();
     
    771771        }
    772772      }
    773      
     773
    774774      return OPTIMAL;
    775775    }
    776    
     776
    777777    // Build a StaticDigraph structure containing the current
    778778    // residual network
     
    830830      const int BF_FIRST_LIMIT  = 2;
    831831      const double BF_LIMIT_FACTOR = 1.5;
    832      
     832
    833833      typedef StaticVectorMap<StaticDigraph::Arc, Value> FilterMap;
    834834      typedef FilterArcs<StaticDigraph, FilterMap> ResDigraph;
     
    837837        ::template SetDistMap<CostNodeMap>
    838838        ::template SetPredMap<PredMap>::Create BF;
    839      
     839
    840840      // Build the residual network
    841841      _arc_vec.clear();
     
    927927      typedef typename HowardMmc<StaticDigraph, CostArcMap>
    928928        ::template SetPath<SPath>::Create MMC;
    929      
     929
    930930      SPath cycle;
    931931      MMC mmc(_sgr, _cost_map);
     
    950950        }
    951951
    952         // Rebuild the residual network       
     952        // Rebuild the residual network
    953953        buildResidualNetwork();
    954954      }
     
    11441144          Cost cycle_cost = mmc.cycleCost();
    11451145          int cycle_size = mmc.cycleSize();
    1146          
     1146
    11471147          // Compute feasible potentials for the current epsilon
    11481148          for (int i = 0; i != int(_cost_vec.size()); ++i) {
     
    11561156            pi[u] = static_cast<double>(_pi[u]) / cycle_size;
    11571157          }
    1158        
     1158
    11591159          iter = limit;
    11601160        }
Note: See TracChangeset for help on using the changeset viewer.