COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2509:a8081c9cd96a in lemon-0.x


Ignore:
Timestamp:
11/14/07 07:28:08 (17 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3374
Message:

Small changes in the min. cost flow classes.

Location:
lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • lemon/capacity_scaling.h

    r2507 r2509  
    2727
    2828#include <vector>
     29#include <lemon/graph_adaptor.h>
    2930#include <lemon/dijkstra.h>
    30 #include <lemon/graph_adaptor.h>
    3131
    3232#define WITH_SCALING
    … …  
    4444
    4545  /// \brief Implementation of the capacity scaling version of the
    46   /// successive shortest path algorithm for finding a minimum cost flow.
     46  /// successive shortest path algorithm for finding a minimum cost
     47  /// flow.
    4748  ///
    48   /// \ref lemon::CapacityScaling "CapacityScaling" implements a
    49   /// capacity scaling algorithm for finding a minimum cost flow.
     49  /// \ref lemon::CapacityScaling "CapacityScaling" implements the
     50  /// capacity scaling version of the successive shortest path
     51  /// algorithm for finding a minimum cost flow.
    5052  ///
    5153  /// \param Graph The directed graph type the algorithm runs on.
    … …  
    5860  /// - Edge capacities and costs should be nonnegative integers.
    5961  ///   However \c CostMap::Value should be signed type.
    60   /// - Supply values should be integers.
     62  /// - Supply values should be signed integers.
    6163  /// - \c LowerMap::Value must be convertible to
    6264  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    … …  
    114116    public:
    115117
    116       typedef typename MapBase<ResEdge, Cost>::Value Value;
    117       typedef typename MapBase<ResEdge, Cost>::Key Key;
    118 
    119118      ReducedCostMap( const ResGraph &_gr,
    120119                      const CostMap &_cost,
    … …  
    122121        gr(_gr), cost_map(_cost), pot_map(_pot) {}
    123122
    124       Value operator[](const Key &e) const {
     123      Cost operator[](const ResEdge &e) const {
    125124        return ResGraph::forward(e) ?
    126125           cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] :
    … …  
    130129    }; //class ReducedCostMap
    131130
    132     /// \brief Map adaptor for \ref lemon::Dijkstra "Dijkstra" class to
    133     /// update node potentials.
     131    /// \brief Map class for the \ref lemon::Dijkstra "Dijkstra"
     132    /// algorithm to update node potentials.
    134133    class PotentialUpdateMap : public MapBase<ResNode, Cost>
    135134    {
    … …  
    142141    public:
    143142
    144       typedef typename MapBase<ResNode, Cost>::Value Value;
    145       typedef typename MapBase<ResNode, Cost>::Key Key;
    146 
    147143      void potentialMap(PotentialMap &_pot) {
    148144        pot = &_pot;
    … …  
    153149      }
    154150
    155       void set(const Key &n, const Value &v) {
     151      void set(const ResNode &n, const Cost &v) {
    156152        data.push_back(Pair(n, v));
    157153      }
    … …  
    186182
    187183    /// \brief Map adaptor class for filtering edges with at least
    188     /// \c delta residual capacity
     184    /// \c delta residual capacity.
    189185    class DeltaFilterMap : public MapBase<ResEdge, bool>
    190186    {
    … …  
    196192    public:
    197193
    198       typedef typename MapBase<ResEdge, Cost>::Value Value;
    199       typedef typename MapBase<ResEdge, Cost>::Key Key;
    200 
    201194      DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) :
    202195        gr(_gr), delta(_delta) {}
    203196
    204       Value operator[](const Key &e) const {
     197      bool operator[](const ResEdge &e) const {
    205198        return gr.rescap(e) >= delta;
    206199      }
    … …  
    299292    /// \brief The delta parameter used for capacity scaling.
    300293    Capacity delta;
    301     /// \brief Edge filter map.
     294    /// \brief Edge filter map for filtering edges with at least
     295    /// \c delta residual capacity.
    302296    DeltaFilterMap delta_filter;
    303     /// \brief The delta residual graph.
     297    /// \brief The delta residual graph (i.e. the subgraph of the
     298    /// residual graph consisting of edges with at least \c delta
     299    /// residual capacity).
    304300    DeltaResGraph dres_graph;
    305301    /// \brief Map for identifing deficit nodes.
    … …  
    574570          if (red_cost[e] < 0) {
    575571            res_graph.augment(e, r = res_graph.rescap(e));
     572            imbalance[dres_graph.source(e)] -= r;
    576573            imbalance[dres_graph.target(e)] += r;
    577             imbalance[dres_graph.source(e)] -= r;
    578574          }
    579575        }

  • lemon/cycle_canceling.h

    r2457 r2509  
    2626
    2727#include <vector>
     28#include <lemon/graph_adaptor.h>
    2829#include <lemon/circulation.h>
    29 #include <lemon/graph_adaptor.h>
    3030
    3131/// \brief The used cycle-canceling method.
    … …  
    8080  /// - Edge capacities and costs should be nonnegative integers.
    8181  ///   However \c CostMap::Value should be signed type.
    82   /// - Supply values should be integers.
     82  /// - Supply values should be signed integers.
    8383  /// - \c LowerMap::Value must be convertible to
    8484  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    … …  
    132132    public:
    133133
    134       typedef typename MapBase<ResEdge, Cost>::Value Value;
    135       typedef typename MapBase<ResEdge, Cost>::Key Key;
    136 
    137134      ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
    138135
    139       Value operator[](const Key &e) const {
     136      Cost operator[](const ResEdge &e) const {
    140137        return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
    141138      }

  • lemon/min_cost_flow.h

    r2474 r2509  
    5757  /// - Edge capacities and costs should be nonnegative integers.
    5858  ///   However \c CostMap::Value should be signed type.
    59   /// - Supply values should be integers.
     59  /// - Supply values should be signed integers.
    6060  /// - \c LowerMap::Value must be convertible to
    6161  ///   \c CapacityMap::Value and \c CapacityMap::Value must be

  • lemon/min_mean_cycle.h

    r2437 r2509  
    2323///
    2424/// \file
    25 /// \brief Karp algorithm for finding a minimum mean cycle.
    26 
     25/// \brief Karp's algorithm for finding a minimum mean (directed) cycle.
     26
     27#include <vector>
    2728#include <lemon/graph_utils.h>
    2829#include <lemon/topology.h>
    … …  
    6465  protected:
    6566
    66     /// \brief Data sturcture for path data.
     67    /// \brief Data structure for path data.
    6768    struct PathData
    6869    {
    … …  
    151152      // Creating vectors for all nodes
    152153      int n = nodes.size();
    153       for (int i = 0; i < nodes.size(); ++i) {
     154      for (int i = 0; i < n; ++i) {
    154155        dmap[nodes[i]].resize(n + 1);
    155156      }

  • lemon/network_simplex.h

    r2471 r2509  
    2727
    2828#include <limits>
     29#include <lemon/graph_adaptor.h>
     30#include <lemon/graph_utils.h>
    2931#include <lemon/smart_graph.h>
    30 #include <lemon/graph_utils.h>
    3132
    3233/// \brief The pivot rule used in the algorithm.
    … …  
    8687  /// - Edge capacities and costs should be nonnegative integers.
    8788  ///   However \c CostMap::Value should be signed type.
    88   /// - Supply values should be integers.
     89  /// - Supply values should be signed integers.
    8990  /// - \c LowerMap::Value must be convertible to
    9091  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
    … …  
    149150    public:
    150151
    151       typedef typename MapBase<Edge, Cost>::Value Value;
    152       typedef typename MapBase<Edge, Cost>::Key Key;
    153 
    154152      ReducedCostMap( const SGraph &_gr,
    155153                      const SCostMap &_cm,
    … …  
    157155        gr(_gr), cost_map(_cm), pot_map(_pm) {}
    158156
    159       Value operator[](const Key &e) const {
     157      Cost operator[](const Edge &e) const {
    160158        return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
    161159      }
Note: See TracChangeset for help on using the changeset viewer.