COIN-OR::LEMON - Graph Library

Changeset 807:78071e00de00 in lemon-main


Ignore:
Timestamp:
11/12/09 23:27:21 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Rebase:
33336539313938363364303661336366373764356634303962303164663663353665313137343963
Message:

Traits class + a named parameter for CapacityScaling? (#180)
to specify the heap used in internal Dijkstra computations.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r806 r807  
    3131
    3232namespace lemon {
     33
     34  /// \brief Default traits class of CapacityScaling algorithm.
     35  ///
     36  /// Default traits class of CapacityScaling algorithm.
     37  /// \tparam GR Digraph type.
     38  /// \tparam V The value type used for flow amounts, capacity bounds
     39  /// and supply values. By default it is \c int.
     40  /// \tparam C The value type used for costs and potentials.
     41  /// By default it is the same as \c V.
     42  template <typename GR, typename V = int, typename C = V>
     43  struct CapacityScalingDefaultTraits
     44  {
     45    /// The type of the digraph
     46    typedef GR Digraph;
     47    /// The type of the flow amounts, capacity bounds and supply values
     48    typedef V Value;
     49    /// The type of the arc costs
     50    typedef C Cost;
     51
     52    /// \brief The type of the heap used for internal Dijkstra computations.
     53    ///
     54    /// The type of the heap used for internal Dijkstra computations.
     55    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
     56    /// its priority type must be \c Cost and its cross reference type
     57    /// must be \ref RangeMap "RangeMap<int>".
     58    typedef BinHeap<Cost, RangeMap<int> > Heap;
     59  };
    3360
    3461  /// \addtogroup min_cost_flow_algs
     
    5885  /// \warning This algorithm does not support negative costs for such
    5986  /// arcs that have infinite upper bound.
    60   template <typename GR, typename V = int, typename C = V>
     87#ifdef DOXYGEN
     88  template <typename GR, typename V, typename C, typename TR>
     89#else
     90  template < typename GR, typename V = int, typename C = V,
     91             typename TR = CapacityScalingDefaultTraits<GR, V, C> >
     92#endif
    6193  class CapacityScaling
    6294  {
    6395  public:
    6496
     97    /// The type of the digraph
     98    typedef typename TR::Digraph Digraph;
    6599    /// The type of the flow amounts, capacity bounds and supply values
    66     typedef V Value;
     100    typedef typename TR::Value Value;
    67101    /// The type of the arc costs
    68     typedef C Cost;
     102    typedef typename TR::Cost Cost;
     103
     104    /// The type of the heap used for internal Dijkstra computations
     105    typedef typename TR::Heap Heap;
     106
     107    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
     108    typedef TR Traits;
    69109
    70110  public:
     
    93133    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    94134
    95     typedef std::vector<Arc> ArcVector;
    96     typedef std::vector<Node> NodeVector;
    97135    typedef std::vector<int> IntVector;
    98136    typedef std::vector<bool> BoolVector;
     
    156194    class ResidualDijkstra
    157195    {
    158       typedef RangeMap<int> HeapCrossRef;
    159       typedef BinHeap<Cost, HeapCrossRef> Heap;
    160 
    161196    private:
    162197
     
    183218
    184219      int run(int s, Value delta = 1) {
    185         HeapCrossRef heap_cross_ref(_node_num, Heap::PRE_HEAP);
     220        RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP);
    186221        Heap heap(heap_cross_ref);
    187222        heap.push(s, 0);
     
    234269  public:
    235270
     271    /// \name Named Template Parameters
     272    /// @{
     273
     274    template <typename T>
     275    struct SetHeapTraits : public Traits {
     276      typedef T Heap;
     277    };
     278
     279    /// \brief \ref named-templ-param "Named parameter" for setting
     280    /// \c Heap type.
     281    ///
     282    /// \ref named-templ-param "Named parameter" for setting \c Heap
     283    /// type, which is used for internal Dijkstra computations.
     284    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
     285    /// its priority type must be \c Cost and its cross reference type
     286    /// must be \ref RangeMap "RangeMap<int>".
     287    template <typename T>
     288    struct SetHeap
     289      : public CapacityScaling<GR, V, C, SetHeapTraits<T> > {
     290      typedef  CapacityScaling<GR, V, C, SetHeapTraits<T> > Create;
     291    };
     292
     293    /// @}
     294
     295  public:
     296
    236297    /// \brief Constructor.
    237298    ///
     
    432493
    433494    /// \name Execution control
     495    /// The algorithm can be executed using \ref run().
    434496
    435497    /// @{
     
    748810    // Execute the capacity scaling algorithm
    749811    ProblemType startWithScaling() {
    750       // Process capacity scaling phases
     812      // Perform capacity scaling phases
    751813      int s, t;
    752814      int phase_cnt = 0;
Note: See TracChangeset for help on using the changeset viewer.