COIN-OR::LEMON - Graph Library

Changeset 857:abb95d48e89e in lemon-main


Ignore:
Timestamp:
10/16/09 09:35:46 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Add traits class + named parameters to Suurballe (#323)

The following types can be modified using named parameters:

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/suurballe.h

    r854 r857  
    3434
    3535namespace lemon {
     36
     37  /// \brief Default traits class of Suurballe algorithm.
     38  ///
     39  /// Default traits class of Suurballe algorithm.
     40  /// \tparam GR The digraph type the algorithm runs on.
     41  /// \tparam LEN The type of the length map.
     42  /// The default value is <tt>GR::ArcMap<int></tt>.
     43#ifdef DOXYGEN
     44  template <typename GR, typename LEN>
     45#else
     46  template < typename GR,
     47             typename LEN = typename GR::template ArcMap<int> >
     48#endif
     49  struct SuurballeDefaultTraits
     50  {
     51    /// The type of the digraph.
     52    typedef GR Digraph;
     53    /// The type of the length map.
     54    typedef LEN LengthMap;
     55    /// The type of the lengths.
     56    typedef typename LEN::Value Length;
     57    /// The type of the flow map.
     58    typedef typename GR::template ArcMap<int> FlowMap;
     59    /// The type of the potential map.
     60    typedef typename GR::template NodeMap<Length> PotentialMap;
     61
     62    /// \brief The path type
     63    ///
     64    /// The type used for storing the found arc-disjoint paths.
     65    /// It must conform to the \ref lemon::concepts::Path "Path" concept
     66    /// and it must have an \c addBack() function.
     67    typedef lemon::Path<Digraph> Path;
     68   
     69    /// The cross reference type used for the heap.
     70    typedef typename GR::template NodeMap<int> HeapCrossRef;
     71
     72    /// \brief The heap type used for internal Dijkstra computations.
     73    ///
     74    /// The type of the heap used for internal Dijkstra computations.
     75    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept
     76    /// and its priority type must be \c Length.
     77    typedef BinHeap<Length, HeapCrossRef> Heap;
     78  };
    3679
    3780  /// \addtogroup shortest_path
     
    62105  /// along with the \ref SplitNodes adaptor.
    63106#ifdef DOXYGEN
    64   template <typename GR, typename LEN>
     107  template <typename GR, typename LEN, typename TR>
    65108#else
    66109  template < typename GR,
    67              typename LEN = typename GR::template ArcMap<int> >
     110             typename LEN = typename GR::template ArcMap<int>,
     111             typename TR = SuurballeDefaultTraits<GR, LEN> >
    68112#endif
    69113  class Suurballe
     
    76120  public:
    77121
    78     /// The type of the digraph the algorithm runs on.
    79     typedef GR Digraph;
     122    /// The type of the digraph.
     123    typedef typename TR::Digraph Digraph;
    80124    /// The type of the length map.
    81     typedef LEN LengthMap;
     125    typedef typename TR::LengthMap LengthMap;
    82126    /// The type of the lengths.
    83     typedef typename LengthMap::Value Length;
    84 #ifdef DOXYGEN
     127    typedef typename TR::Length Length;
     128
    85129    /// The type of the flow map.
    86     typedef GR::ArcMap<int> FlowMap;
     130    typedef typename TR::FlowMap FlowMap;
    87131    /// The type of the potential map.
    88     typedef GR::NodeMap<Length> PotentialMap;
    89 #else
    90     /// The type of the flow map.
    91     typedef typename Digraph::template ArcMap<int> FlowMap;
    92     /// The type of the potential map.
    93     typedef typename Digraph::template NodeMap<Length> PotentialMap;
    94 #endif
    95 
     132    typedef typename TR::PotentialMap PotentialMap;
    96133    /// The type of the path structures.
    97     typedef SimplePath<GR> Path;
     134    typedef typename TR::Path Path;
     135    /// The cross reference type used for the heap.
     136    typedef typename TR::HeapCrossRef HeapCrossRef;
     137    /// The heap type used for internal Dijkstra computations.
     138    typedef typename TR::Heap Heap;
     139
     140    /// The \ref SuurballeDefaultTraits "traits class" of the algorithm.
     141    typedef TR Traits;
    98142
    99143  private:
    100 
    101     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    102     typedef BinHeap<Length, HeapCrossRef> Heap;
    103144
    104145    // ResidualDijkstra is a special implementation of the
     
    255296    }; //class ResidualDijkstra
    256297
     298  public:
     299
     300    /// \name Named Template Parameters
     301    /// @{
     302
     303    template <typename T>
     304    struct SetFlowMapTraits : public Traits {
     305      typedef T FlowMap;
     306    };
     307
     308    /// \brief \ref named-templ-param "Named parameter" for setting
     309    /// \c FlowMap type.
     310    ///
     311    /// \ref named-templ-param "Named parameter" for setting
     312    /// \c FlowMap type.
     313    template <typename T>
     314    struct SetFlowMap
     315      : public Suurballe<GR, LEN, SetFlowMapTraits<T> > {
     316      typedef Suurballe<GR, LEN, SetFlowMapTraits<T> > Create;
     317    };
     318
     319    template <typename T>
     320    struct SetPotentialMapTraits : public Traits {
     321      typedef T PotentialMap;
     322    };
     323
     324    /// \brief \ref named-templ-param "Named parameter" for setting
     325    /// \c PotentialMap type.
     326    ///
     327    /// \ref named-templ-param "Named parameter" for setting
     328    /// \c PotentialMap type.
     329    template <typename T>
     330    struct SetPotentialMap
     331      : public Suurballe<GR, LEN, SetPotentialMapTraits<T> > {
     332      typedef Suurballe<GR, LEN, SetPotentialMapTraits<T> > Create;
     333    };
     334
     335    template <typename T>
     336    struct SetPathTraits : public Traits {
     337      typedef T Path;
     338    };
     339
     340    /// \brief \ref named-templ-param "Named parameter" for setting
     341    /// \c %Path type.
     342    ///
     343    /// \ref named-templ-param "Named parameter" for setting \c %Path type.
     344    /// It must conform to the \ref lemon::concepts::Path "Path" concept
     345    /// and it must have an \c addBack() function.
     346    template <typename T>
     347    struct SetPath
     348      : public Suurballe<GR, LEN, SetPathTraits<T> > {
     349      typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;
     350    };
     351   
     352    template <typename H, typename CR>
     353    struct SetHeapTraits : public Traits {
     354      typedef H Heap;
     355      typedef CR HeapCrossRef;
     356    };
     357
     358    /// \brief \ref named-templ-param "Named parameter" for setting
     359    /// \c Heap and \c HeapCrossRef types.
     360    ///
     361    /// \ref named-templ-param "Named parameter" for setting \c Heap
     362    /// and \c HeapCrossRef types with automatic allocation.
     363    /// They will be used for internal Dijkstra computations.
     364    /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"
     365    /// concept and its priority type must be \c Length.
     366    template <typename H,
     367              typename CR = typename Digraph::template NodeMap<int> >
     368    struct SetHeap
     369      : public Suurballe<GR, LEN, SetHeapTraits<H, CR> > {
     370      typedef Suurballe<GR, LEN, SetHeapTraits<H, CR> > Create;
     371    };
     372
     373    /// @}
     374
    257375  private:
    258376
  • test/suurballe_test.cc

    r854 r857  
    2424#include <lemon/suurballe.h>
    2525#include <lemon/concepts/digraph.h>
     26#include <lemon/concepts/heap.h>
    2627
    2728#include "test_tools.h"
     
    8283  typedef concepts::ReadMap<Arc, VType> LengthMap;
    8384 
    84   typedef Suurballe<Digraph, LengthMap> SuurballeType;
     85  typedef Suurballe<Digraph, LengthMap> ST;
     86  typedef Suurballe<Digraph, LengthMap>
     87    ::SetFlowMap<ST::FlowMap>
     88    ::SetPotentialMap<ST::PotentialMap>
     89    ::SetPath<SimplePath<Digraph> >
     90    ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
     91    ::Create SuurballeType;
    8592
    8693  Digraph g;
Note: See TracChangeset for help on using the changeset viewer.