COIN-OR::LEMON - Graph Library

Changeset 2588:4d3bc1d04c1d in lemon-0.x for lemon/capacity_scaling.h


Ignore:
Timestamp:
02/29/08 16:57:52 (11 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.

File:
1 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;
Note: See TracChangeset for help on using the changeset viewer.