Mercuriallemon-1.3 / 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, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 360 75cf49ce5390
child 616 f2d6d3446adf
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index). 
     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 _Graph, typename _Item>

    33   class ItemSetTraits {};

    34 

    35 

    36   template <typename Graph, typename Enable = void>

    37   struct NodeNotifierIndicator {

    38     typedef InvalidType Type;

    39   };

    40   template <typename Graph>

    41   struct NodeNotifierIndicator<

    42     Graph,

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

    44   > {

    45     typedef typename Graph::NodeNotifier Type;

    46   };

    47 

    48   template <typename _Graph>

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

    50   public:

    51 

    52     typedef _Graph Graph;

    53 

    54     typedef typename Graph::Node Item;

    55     typedef typename Graph::NodeIt ItemIt;

    56 

    57     typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;

    58 

    59     template <typename _Value>

    60     class Map : public Graph::template NodeMap<_Value> {

    61     public:

    62       typedef typename Graph::template NodeMap<_Value> Parent;

    63       typedef typename Graph::template NodeMap<_Value> Type;

    64       typedef typename Parent::Value Value;

    65 

    66       Map(const Graph& _digraph) : Parent(_digraph) {}

    67       Map(const Graph& _digraph, const Value& _value)

    68         : Parent(_digraph, _value) {}

    69 

    70      };

    71 

    72   };

    73 

    74   template <typename Graph, typename Enable = void>

    75   struct ArcNotifierIndicator {

    76     typedef InvalidType Type;

    77   };

    78   template <typename Graph>

    79   struct ArcNotifierIndicator<

    80     Graph,

    81     typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type

    82   > {

    83     typedef typename Graph::ArcNotifier Type;

    84   };

    85 

    86   template <typename _Graph>

    87   class ItemSetTraits<_Graph, typename _Graph::Arc> {

    88   public:

    89 

    90     typedef _Graph Graph;

    91 

    92     typedef typename Graph::Arc Item;

    93     typedef typename Graph::ArcIt ItemIt;

    94 

    95     typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;

    96 

    97     template <typename _Value>

    98     class Map : public Graph::template ArcMap<_Value> {

    99     public:

   100       typedef typename Graph::template ArcMap<_Value> Parent;

   101       typedef typename Graph::template ArcMap<_Value> Type;

   102       typedef typename Parent::Value Value;

   103 

   104       Map(const Graph& _digraph) : Parent(_digraph) {}

   105       Map(const Graph& _digraph, const Value& _value)

   106         : Parent(_digraph, _value) {}

   107     };

   108 

   109   };

   110 

   111   template <typename Graph, typename Enable = void>

   112   struct EdgeNotifierIndicator {

   113     typedef InvalidType Type;

   114   };

   115   template <typename Graph>

   116   struct EdgeNotifierIndicator<

   117     Graph,

   118     typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type

   119   > {

   120     typedef typename Graph::EdgeNotifier Type;

   121   };

   122 

   123   template <typename _Graph>

   124   class ItemSetTraits<_Graph, typename _Graph::Edge> {

   125   public:

   126 

   127     typedef _Graph Graph;

   128 

   129     typedef typename Graph::Edge Item;

   130     typedef typename Graph::EdgeIt ItemIt;

   131 

   132     typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;

   133 

   134     template <typename _Value>

   135     class Map : public Graph::template EdgeMap<_Value> {

   136     public:

   137       typedef typename Graph::template EdgeMap<_Value> Parent;

   138       typedef typename Graph::template EdgeMap<_Value> Type;

   139       typedef typename Parent::Value Value;

   140 

   141       Map(const Graph& _digraph) : Parent(_digraph) {}

   142       Map(const Graph& _digraph, const Value& _value)

   143         : Parent(_digraph, _value) {}

   144     };

   145 

   146   };

   147 

   148   template <typename Map, typename Enable = void>

   149   struct MapTraits {

   150     typedef False ReferenceMapTag;

   151 

   152     typedef typename Map::Key Key;

   153     typedef typename Map::Value Value;

   154 

   155     typedef Value ConstReturnValue;

   156     typedef Value ReturnValue;

   157   };

   158 

   159   template <typename Map>

   160   struct MapTraits<

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

   162   {

   163     typedef True ReferenceMapTag;

   164 

   165     typedef typename Map::Key Key;

   166     typedef typename Map::Value Value;

   167 

   168     typedef typename Map::ConstReference ConstReturnValue;

   169     typedef typename Map::Reference ReturnValue;

   170 

   171     typedef typename Map::ConstReference ConstReference;

   172     typedef typename Map::Reference Reference;

   173  };

   174 

   175   template <typename MatrixMap, typename Enable = void>

   176   struct MatrixMapTraits {

   177     typedef False ReferenceMapTag;

   178 

   179     typedef typename MatrixMap::FirstKey FirstKey;

   180     typedef typename MatrixMap::SecondKey SecondKey;

   181     typedef typename MatrixMap::Value Value;

   182 

   183     typedef Value ConstReturnValue;

   184     typedef Value ReturnValue;

   185   };

   186 

   187   template <typename MatrixMap>

   188   struct MatrixMapTraits<

   189     MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag,

   190                                   void>::type >

   191   {

   192     typedef True ReferenceMapTag;

   193 

   194     typedef typename MatrixMap::FirstKey FirstKey;

   195     typedef typename MatrixMap::SecondKey SecondKey;

   196     typedef typename MatrixMap::Value Value;

   197 

   198     typedef typename MatrixMap::ConstReference ConstReturnValue;

   199     typedef typename MatrixMap::Reference ReturnValue;

   200 

   201     typedef typename MatrixMap::ConstReference ConstReference;

   202     typedef typename MatrixMap::Reference Reference;

   203  };

   204 

   205   // Indicators for the tags

   206 

   207   template <typename Graph, typename Enable = void>

   208   struct NodeNumTagIndicator {

   209     static const bool value = false;

   210   };

   211 

   212   template <typename Graph>

   213   struct NodeNumTagIndicator<

   214     Graph,

   215     typename enable_if<typename Graph::NodeNumTag, void>::type

   216   > {

   217     static const bool value = true;

   218   };

   219 

   220   template <typename Graph, typename Enable = void>

   221   struct ArcNumTagIndicator {

   222     static const bool value = false;

   223   };

   224 

   225   template <typename Graph>

   226   struct ArcNumTagIndicator<

   227     Graph,

   228     typename enable_if<typename Graph::ArcNumTag, void>::type

   229   > {

   230     static const bool value = true;

   231   };

   232 

   233   template <typename Graph, typename Enable = void>

   234   struct EdgeNumTagIndicator {

   235     static const bool value = false;

   236   };

   237 

   238   template <typename Graph>

   239   struct EdgeNumTagIndicator<

   240     Graph,

   241     typename enable_if<typename Graph::EdgeNumTag, void>::type

   242   > {

   243     static const bool value = true;

   244   };

   245 

   246   template <typename Graph, typename Enable = void>

   247   struct FindArcTagIndicator {

   248     static const bool value = false;

   249   };

   250 

   251   template <typename Graph>

   252   struct FindArcTagIndicator<

   253     Graph,

   254     typename enable_if<typename Graph::FindArcTag, void>::type

   255   > {

   256     static const bool value = true;

   257   };

   258 

   259   template <typename Graph, typename Enable = void>

   260   struct FindEdgeTagIndicator {

   261     static const bool value = false;

   262   };

   263 

   264   template <typename Graph>

   265   struct FindEdgeTagIndicator<

   266     Graph,

   267     typename enable_if<typename Graph::FindEdgeTag, void>::type

   268   > {

   269     static const bool value = true;

   270   };

   271 

   272   template <typename Graph, typename Enable = void>

   273   struct UndirectedTagIndicator {

   274     static const bool value = false;

   275   };

   276 

   277   template <typename Graph>

   278   struct UndirectedTagIndicator<

   279     Graph,

   280     typename enable_if<typename Graph::UndirectedTag, void>::type

   281   > {

   282     static const bool value = true;

   283   };

   284 

   285   template <typename Graph, typename Enable = void>

   286   struct BuildTagIndicator {

   287     static const bool value = false;

   288   };

   289 

   290   template <typename Graph>

   291   struct BuildTagIndicator<

   292     Graph,

   293     typename enable_if<typename Graph::BuildTag, void>::type

   294   > {

   295     static const bool value = true;

   296   };

   297 

   298 }

   299 

   300 #endif
lemon-1.3