Mercuriallemon-main / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bits/traits.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 936 ddd3c0d3d9bf
parent 440 88ed40ad0d4f
child 1019 4c89e925cfe2
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well. 
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library.

     4  *

     5  * Copyright (C) 2003-2009

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    18 

    19 #ifndef LEMON_BITS_TRAITS_H

    20 #define LEMON_BITS_TRAITS_H

    21 

    22 //\file

    23 //\brief Traits for graphs and maps

    24 //

    25 

    26 #include <lemon/bits/enable_if.h>

    27 

    28 namespace lemon {

    29 

    30   struct InvalidType {};

    31 

    32   template <typename GR, typename _Item>

    33   class ItemSetTraits {};

    34 

    35 

    36   template <typename GR, typename Enable = void>

    37   struct NodeNotifierIndicator {

    38     typedef InvalidType Type;

    39   };

    40   template <typename GR>

    41   struct NodeNotifierIndicator<

    42     GR,

    43     typename enable_if<typename GR::NodeNotifier::Notifier, void>::type

    44   > {

    45     typedef typename GR::NodeNotifier Type;

    46   };

    47 

    48   template <typename GR>

    49   class ItemSetTraits<GR, typename GR::Node> {

    50   public:

    51 

    52     typedef GR Graph;

    53     typedef GR Digraph;

    54 

    55     typedef typename GR::Node Item;

    56     typedef typename GR::NodeIt ItemIt;

    57 

    58     typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier;

    59 

    60     template <typename V>

    61     class Map : public GR::template NodeMap<V> {

    62       typedef typename GR::template NodeMap<V> Parent;

    63 

    64     public:

    65       typedef typename GR::template NodeMap<V> Type;

    66       typedef typename Parent::Value Value;

    67 

    68       Map(const GR& _digraph) : Parent(_digraph) {}

    69       Map(const GR& _digraph, const Value& _value)

    70         : Parent(_digraph, _value) {}

    71 

    72      };

    73 

    74   };

    75 

    76   template <typename GR, typename Enable = void>

    77   struct ArcNotifierIndicator {

    78     typedef InvalidType Type;

    79   };

    80   template <typename GR>

    81   struct ArcNotifierIndicator<

    82     GR,

    83     typename enable_if<typename GR::ArcNotifier::Notifier, void>::type

    84   > {

    85     typedef typename GR::ArcNotifier Type;

    86   };

    87 

    88   template <typename GR>

    89   class ItemSetTraits<GR, typename GR::Arc> {

    90   public:

    91 

    92     typedef GR Graph;

    93     typedef GR Digraph;

    94 

    95     typedef typename GR::Arc Item;

    96     typedef typename GR::ArcIt ItemIt;

    97 

    98     typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier;

    99 

   100     template <typename V>

   101     class Map : public GR::template ArcMap<V> {

   102       typedef typename GR::template ArcMap<V> Parent;

   103 

   104     public:

   105       typedef typename GR::template ArcMap<V> Type;

   106       typedef typename Parent::Value Value;

   107 

   108       Map(const GR& _digraph) : Parent(_digraph) {}

   109       Map(const GR& _digraph, const Value& _value)

   110         : Parent(_digraph, _value) {}

   111     };

   112 

   113   };

   114 

   115   template <typename GR, typename Enable = void>

   116   struct EdgeNotifierIndicator {

   117     typedef InvalidType Type;

   118   };

   119   template <typename GR>

   120   struct EdgeNotifierIndicator<

   121     GR,

   122     typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type

   123   > {

   124     typedef typename GR::EdgeNotifier Type;

   125   };

   126 

   127   template <typename GR>

   128   class ItemSetTraits<GR, typename GR::Edge> {

   129   public:

   130 

   131     typedef GR Graph;

   132     typedef GR Digraph;

   133 

   134     typedef typename GR::Edge Item;

   135     typedef typename GR::EdgeIt ItemIt;

   136 

   137     typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier;

   138 

   139     template <typename V>

   140     class Map : public GR::template EdgeMap<V> {

   141       typedef typename GR::template EdgeMap<V> Parent;

   142 

   143     public:

   144       typedef typename GR::template EdgeMap<V> Type;

   145       typedef typename Parent::Value Value;

   146 

   147       Map(const GR& _digraph) : Parent(_digraph) {}

   148       Map(const GR& _digraph, const Value& _value)

   149         : Parent(_digraph, _value) {}

   150     };

   151 

   152   };

   153 

   154   template <typename Map, typename Enable = void>

   155   struct MapTraits {

   156     typedef False ReferenceMapTag;

   157 

   158     typedef typename Map::Key Key;

   159     typedef typename Map::Value Value;

   160 

   161     typedef Value ConstReturnValue;

   162     typedef Value ReturnValue;

   163   };

   164 

   165   template <typename Map>

   166   struct MapTraits<

   167     Map, typename enable_if<typename Map::ReferenceMapTag, void>::type >

   168   {

   169     typedef True ReferenceMapTag;

   170 

   171     typedef typename Map::Key Key;

   172     typedef typename Map::Value Value;

   173 

   174     typedef typename Map::ConstReference ConstReturnValue;

   175     typedef typename Map::Reference ReturnValue;

   176 

   177     typedef typename Map::ConstReference ConstReference;

   178     typedef typename Map::Reference Reference;

   179  };

   180 

   181   template <typename MatrixMap, typename Enable = void>

   182   struct MatrixMapTraits {

   183     typedef False ReferenceMapTag;

   184 

   185     typedef typename MatrixMap::FirstKey FirstKey;

   186     typedef typename MatrixMap::SecondKey SecondKey;

   187     typedef typename MatrixMap::Value Value;

   188 

   189     typedef Value ConstReturnValue;

   190     typedef Value ReturnValue;

   191   };

   192 

   193   template <typename MatrixMap>

   194   struct MatrixMapTraits<

   195     MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag,

   196                                   void>::type >

   197   {

   198     typedef True ReferenceMapTag;

   199 

   200     typedef typename MatrixMap::FirstKey FirstKey;

   201     typedef typename MatrixMap::SecondKey SecondKey;

   202     typedef typename MatrixMap::Value Value;

   203 

   204     typedef typename MatrixMap::ConstReference ConstReturnValue;

   205     typedef typename MatrixMap::Reference ReturnValue;

   206 

   207     typedef typename MatrixMap::ConstReference ConstReference;

   208     typedef typename MatrixMap::Reference Reference;

   209  };

   210 

   211   // Indicators for the tags

   212 

   213   template <typename GR, typename Enable = void>

   214   struct NodeNumTagIndicator {

   215     static const bool value = false;

   216   };

   217 

   218   template <typename GR>

   219   struct NodeNumTagIndicator<

   220     GR,

   221     typename enable_if<typename GR::NodeNumTag, void>::type

   222   > {

   223     static const bool value = true;

   224   };

   225 

   226   template <typename GR, typename Enable = void>

   227   struct ArcNumTagIndicator {

   228     static const bool value = false;

   229   };

   230 

   231   template <typename GR>

   232   struct ArcNumTagIndicator<

   233     GR,

   234     typename enable_if<typename GR::ArcNumTag, void>::type

   235   > {

   236     static const bool value = true;

   237   };

   238 

   239   template <typename GR, typename Enable = void>

   240   struct EdgeNumTagIndicator {

   241     static const bool value = false;

   242   };

   243 

   244   template <typename GR>

   245   struct EdgeNumTagIndicator<

   246     GR,

   247     typename enable_if<typename GR::EdgeNumTag, void>::type

   248   > {

   249     static const bool value = true;

   250   };

   251 

   252   template <typename GR, typename Enable = void>

   253   struct FindArcTagIndicator {

   254     static const bool value = false;

   255   };

   256 

   257   template <typename GR>

   258   struct FindArcTagIndicator<

   259     GR,

   260     typename enable_if<typename GR::FindArcTag, void>::type

   261   > {

   262     static const bool value = true;

   263   };

   264 

   265   template <typename GR, typename Enable = void>

   266   struct FindEdgeTagIndicator {

   267     static const bool value = false;

   268   };

   269 

   270   template <typename GR>

   271   struct FindEdgeTagIndicator<

   272     GR,

   273     typename enable_if<typename GR::FindEdgeTag, void>::type

   274   > {

   275     static const bool value = true;

   276   };

   277 

   278   template <typename GR, typename Enable = void>

   279   struct UndirectedTagIndicator {

   280     static const bool value = false;

   281   };

   282 

   283   template <typename GR>

   284   struct UndirectedTagIndicator<

   285     GR,

   286     typename enable_if<typename GR::UndirectedTag, void>::type

   287   > {

   288     static const bool value = true;

   289   };

   290 

   291   template <typename GR, typename Enable = void>

   292   struct BuildTagIndicator {

   293     static const bool value = false;

   294   };

   295 

   296   template <typename GR>

   297   struct BuildTagIndicator<

   298     GR,

   299     typename enable_if<typename GR::BuildTag, void>::type

   300   > {

   301     static const bool value = true;

   302   };

   303 

   304 }

   305 

   306 #endif
lemon-main