COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2588:4d3bc1d04c1d in lemon-0.x


Ignore:
Timestamp:
02/29/08 16:57:52 (16 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3470
Message:

Small improvements in min cost flow files.

Location:
lemon
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • lemon/capacity_scaling.h

    r2581 r2588  
    2626
    2727#include <vector>
    28 
    29 #include <lemon/graph_adaptor.h>
    3028#include <lemon/bin_heap.h>
    3129
    … …  
    9189    class ResidualDijkstra
    9290    {
    93       typedef typename Graph::template NodeMap<Cost> CostNodeMap;
    94       typedef typename Graph::template NodeMap<Edge> PredMap;
    95 
    9691      typedef typename Graph::template NodeMap<int> HeapCrossRef;
    9792      typedef BinHeap<Cost, HeapCrossRef> Heap;
    … …  
    110105
    111106      // The distance map
    112       CostNodeMap _dist;
     107      PotentialMap _dist;
    113108      // The pred edge map
    114109      PredMap &_pred;
    … …  
    132127
    133128      /// Runs the algorithm from the given source node.
    134       Node run(Node s, Capacity delta) {
     129      Node run(Node s, Capacity delta = 1) {
    135130        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
    136131        Heap heap(heap_cross_ref);
    … …  
    455450    }
    456451
    457     /// \brief Returns the flow on the edge.
    458     ///
    459     /// Returns the flow on the edge.
     452    /// \brief Returns the flow on the given edge.
     453    ///
     454    /// Returns the flow on the given edge.
    460455    ///
    461456    /// \pre \ref run() must be called before using this function.
    … …  
    464459    }
    465460
    466     /// \brief Returns the potential of the node.
    467     ///
    468     /// Returns the potential of the node.
     461    /// \brief Returns the potential of the given node.
     462    ///
     463    /// Returns the potential of the given node.
    469464    ///
    470465    /// \pre \ref run() must be called before using this function.
    … …  
    518513          if (-_supply[n] > max_dem) max_dem = -_supply[n];
    519514        }
    520         if (max_dem < max_sup) max_sup = max_dem;
     515        Capacity max_cap = 0;
     516        for (EdgeIt e(_graph); e != INVALID; ++e) {
     517          if (_capacity[e] > max_cap) max_cap = _capacity[e];
     518        }
     519        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
    521520        _phase_num = 0;
    522521        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
    … …  
    596595
    597596          // Augmenting along a shortest path from s to t.
    598           Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
     597          Capacity d = std::min(_excess[s], -_excess[t]);
    599598          Node u = t;
    600599          Edge e;
    … …  
    658657        // Running Dijkstra
    659658        s = _excess_nodes[next_node];
    660         if ((t = _dijkstra->run(s, 1)) == INVALID)
    661           return false;
     659        if ((t = _dijkstra->run(s)) == INVALID) break;
    662660
    663661        // Augmenting along a shortest path from s to t
    664         Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
     662        Capacity d = std::min(_excess[s], -_excess[t]);
    665663        Node u = t;
    666664        Edge e;
    667         while ((e = _pred[u]) != INVALID) {
    668           Capacity rc;
    669           if (u == _graph.target(e)) {
    670             rc = _res_cap[e];
    671             u = _graph.source(e);
    672           } else {
    673             rc = (*_flow)[e];
    674             u = _graph.target(e);
    675           }
    676           if (rc < d) d = rc;
     665        if (d > 1) {
     666          while ((e = _pred[u]) != INVALID) {
     667            Capacity rc;
     668            if (u == _graph.target(e)) {
     669              rc = _res_cap[e];
     670              u = _graph.source(e);
     671            } else {
     672              rc = (*_flow)[e];
     673              u = _graph.target(e);
     674            }
     675            if (rc < d) d = rc;
     676          }
    677677        }
    678678        u = t;

  • lemon/cost_scaling.h

    r2581 r2588  
    400400    }
    401401
    402     /// \brief Returns the flow on the edge.
    403     ///
    404     /// Returns the flow on the edge.
     402    /// \brief Returns the flow on the given edge.
     403    ///
     404    /// Returns the flow on the given edge.
    405405    ///
    406406    /// \pre \ref run() must be called before using this function.
    … …  
    409409    }
    410410
    411     /// \brief Returns the potential of the node.
    412     ///
    413     /// Returns the potential of the node.
     411    /// \brief Returns the potential of the given node.
     412    ///
     413    /// Returns the potential of the given node.
    414414    ///
    415415    /// \pre \ref run() must be called before using this function.

  • lemon/cycle_canceling.h

    r2581 r2588  
    356356    }
    357357
    358     /// \brief Returns the flow on the edge.
    359     ///
    360     /// Returns the flow on the edge.
     358    /// \brief Returns the flow on the given edge.
     359    ///
     360    /// Returns the flow on the given edge.
    361361    ///
    362362    /// \pre \ref run() must be called before using this function.
    … …  
    365365    }
    366366
    367     /// \brief Returns the potential of the node.
    368     ///
    369     /// Returns the potential of the node.
     367    /// \brief Returns the potential of the given node.
     368    ///
     369    /// Returns the potential of the given node.
    370370    ///
    371371    /// \pre \ref run() must be called before using this function.

  • lemon/min_cost_flow.h

    r2581 r2588  
    4545  /// There are four implementations for the minimum cost flow problem,
    4646  /// which can be used exactly the same way.
    47   /// - \ref CapacityScaling The capacity scaling algorithm.
    48   /// - \ref CostScaling The cost scaling algorithm.
    49   /// - \ref CycleCanceling A cycle-canceling algorithm.
    50   /// - \ref NetworkSimplex The network simplex algorithm.
     47  /// - \ref CapacityScaling
     48  /// - \ref CostScaling
     49  /// - \ref CycleCanceling
     50  /// - \ref NetworkSimplex
    5151  ///
    5252  /// \tparam Graph The directed graph type the algorithm runs on.

  • lemon/min_mean_cycle.h

    r2583 r2588  
    135135
    136136    /// \name Execution control
    137     /// The simplest way to execute the algorithm is to call run().
     137    /// The simplest way to execute the algorithm is to call the run()
     138    /// function.
    138139    /// \n
    139140    /// If you only need the minimum mean value, you may call init()
    … …  
    238239    /// The result of the algorithm can be obtained using these
    239240    /// functions.
    240     /// \n run() must be called before using them.
     241    /// \n The algorithm should be executed before using them.
    241242
    242243    /// @{

  • lemon/network_simplex.h

    r2581 r2588  
    777777    }
    778778
    779     /// \brief Returns the flow on the edge.
    780     ///
    781     /// Returns the flow on the edge.
     779    /// \brief Returns the flow on the given edge.
     780    ///
     781    /// Returns the flow on the given edge.
    782782    ///
    783783    /// \pre \ref run() must be called before using this function.
    … …  
    786786    }
    787787
    788     /// \brief Returns the potential of the node.
    789     ///
    790     /// Returns the potential of the node.
     788    /// \brief Returns the potential of the given node.
     789    ///
     790    /// Returns the potential of the given node.
    791791    ///
    792792    /// \pre \ref run() must be called before using this function.
Note: See TracChangeset for help on using the changeset viewer.