Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bits/traits.h
author deba
Sat, 17 Nov 2007 20:58:11 +0000
changeset 2514 57143c09dc20
parent 2391 14a343be7a5a
child 2553 bfced05fa852
permissions -rw-r--r--
Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree) 
     1 

     2 /* -*- C++ -*-

     3  *

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

     5  *

     6  * Copyright (C) 2003-2007

     7  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

     9  *

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

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

    12  * precise terms see the accompanying LICENSE file.

    13  *

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

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

    16  * purpose.

    17  *

    18  */

    19 

    20 #ifndef LEMON_BITS_TRAITS_H

    21 #define LEMON_BITS_TRAITS_H

    22 

    23 #include <lemon/bits/utility.h>

    24 

    25 ///\file

    26 ///\brief Traits for graphs and maps

    27 ///

    28 

    29 namespace lemon {

    30   template <typename _Graph, typename _Item>

    31   class ItemSetTraits {};

    32   

    33 

    34   template <typename Graph, typename Enable = void>

    35   struct NodeNotifierIndicator {

    36     typedef InvalidType Type;

    37   };

    38   template <typename Graph>

    39   struct NodeNotifierIndicator<

    40     Graph, 

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

    42   > { 

    43     typedef typename Graph::NodeNotifier Type;

    44   };

    45 

    46   template <typename _Graph>

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

    48   public:

    49     

    50     typedef _Graph Graph;

    51 

    52     typedef typename Graph::Node Item;

    53     typedef typename Graph::NodeIt ItemIt;

    54 

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

    56 

    57     template <typename _Value>

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

    59     public:

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

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

    62       typedef typename Parent::Value Value;

    63 

    64       Map(const Graph& _graph) : Parent(_graph) {}

    65       Map(const Graph& _graph, const Value& _value) 

    66 	: Parent(_graph, _value) {}

    67 

    68      };

    69 

    70   };

    71 

    72   template <typename Graph, typename Enable = void>

    73   struct EdgeNotifierIndicator {

    74     typedef InvalidType Type;

    75   };

    76   template <typename Graph>

    77   struct EdgeNotifierIndicator<

    78     Graph, 

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

    80   > { 

    81     typedef typename Graph::EdgeNotifier Type;

    82   };

    83 

    84   template <typename _Graph>

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

    86   public:

    87     

    88     typedef _Graph Graph;

    89 

    90     typedef typename Graph::Edge Item;

    91     typedef typename Graph::EdgeIt ItemIt;

    92 

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

    94 

    95     template <typename _Value>

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

    97     public:

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

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

   100       typedef typename Parent::Value Value;

   101 

   102       Map(const Graph& _graph) : Parent(_graph) {}

   103       Map(const Graph& _graph, const Value& _value) 

   104 	: Parent(_graph, _value) {}

   105     };

   106 

   107   };

   108 

   109   template <typename Graph, typename Enable = void>

   110   struct UEdgeNotifierIndicator {

   111     typedef InvalidType Type;

   112   };

   113   template <typename Graph>

   114   struct UEdgeNotifierIndicator<

   115     Graph, 

   116     typename enable_if<typename Graph::UEdgeNotifier::Notifier, void>::type

   117   > { 

   118     typedef typename Graph::UEdgeNotifier Type;

   119   };

   120 

   121   template <typename _Graph>

   122   class ItemSetTraits<_Graph, typename _Graph::UEdge> {

   123   public:

   124     

   125     typedef _Graph Graph;

   126 

   127     typedef typename Graph::UEdge Item;

   128     typedef typename Graph::UEdgeIt ItemIt;

   129 

   130     typedef typename UEdgeNotifierIndicator<Graph>::Type ItemNotifier;

   131 

   132     template <typename _Value>

   133     class Map : public Graph::template UEdgeMap<_Value> {

   134     public:

   135       typedef typename Graph::template UEdgeMap<_Value> Parent; 

   136       typedef typename Graph::template UEdgeMap<_Value> Type; 

   137       typedef typename Parent::Value Value;

   138 

   139       Map(const Graph& _graph) : Parent(_graph) {}

   140       Map(const Graph& _graph, const Value& _value) 

   141 	: Parent(_graph, _value) {}

   142     };

   143 

   144   };

   145 

   146   template <typename Graph, typename Enable = void>

   147   struct ANodeNotifierIndicator {

   148     typedef InvalidType Type;

   149   };

   150   template <typename Graph>

   151   struct ANodeNotifierIndicator<

   152     Graph, 

   153     typename enable_if<typename Graph::ANodeNotifier::Notifier, void>::type

   154   > { 

   155     typedef typename Graph::ANodeNotifier Type;

   156   };

   157 

   158   template <typename _Graph>

   159   class ItemSetTraits<_Graph, typename _Graph::ANode> {

   160   public:

   161     

   162     typedef _Graph Graph;

   163 

   164     typedef typename Graph::ANode Item;

   165     typedef typename Graph::ANodeIt ItemIt;

   166 

   167     typedef typename ANodeNotifierIndicator<Graph>::Type ItemNotifier;

   168 

   169     template <typename _Value>

   170     class Map : public Graph::template ANodeMap<_Value> {

   171     public:

   172       typedef typename Graph::template ANodeMap<_Value> Parent; 

   173       typedef typename Graph::template ANodeMap<_Value> Type; 

   174       typedef typename Parent::Value Value;

   175 

   176       Map(const Graph& _graph) : Parent(_graph) {}

   177       Map(const Graph& _graph, const Value& _value) 

   178 	: Parent(_graph, _value) {}

   179     };

   180 

   181   };

   182 

   183   template <typename Graph, typename Enable = void>

   184   struct BNodeNotifierIndicator {

   185     typedef InvalidType Type;

   186   };

   187   template <typename Graph>

   188   struct BNodeNotifierIndicator<

   189     Graph, 

   190     typename enable_if<typename Graph::BNodeNotifier::Notifier, void>::type

   191   > { 

   192     typedef typename Graph::BNodeNotifier Type;

   193   };

   194 

   195   template <typename _Graph>

   196   class ItemSetTraits<_Graph, typename _Graph::BNode> {

   197   public:

   198     

   199     typedef _Graph Graph;

   200 

   201     typedef typename Graph::BNode Item;

   202     typedef typename Graph::BNodeIt ItemIt;

   203 

   204     typedef typename BNodeNotifierIndicator<Graph>::Type ItemNotifier;

   205 

   206     template <typename _Value>

   207     class Map : public Graph::template BNodeMap<_Value> {

   208     public:

   209       typedef typename Graph::template BNodeMap<_Value> Parent; 

   210       typedef typename Graph::template BNodeMap<_Value> Type; 

   211       typedef typename Parent::Value Value;

   212 

   213       Map(const Graph& _graph) : Parent(_graph) {}

   214       Map(const Graph& _graph, const Value& _value) 

   215 	: Parent(_graph, _value) {}

   216     };

   217 

   218   };

   219 

   220 

   221   template <typename Map, typename Enable = void>

   222   struct MapTraits {

   223     typedef False ReferenceMapTag;

   224 

   225     typedef typename Map::Key Key;

   226     typedef typename Map::Value Value;

   227 

   228     typedef const Value ConstReturnValue;

   229     typedef const Value ReturnValue;

   230   };

   231 

   232   template <typename Map>

   233   struct MapTraits<

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

   235   {

   236     typedef True ReferenceMapTag;

   237     

   238     typedef typename Map::Key Key;

   239     typedef typename Map::Value Value;

   240 

   241     typedef typename Map::ConstReference ConstReturnValue;

   242     typedef typename Map::Reference ReturnValue;

   243 

   244     typedef typename Map::ConstReference ConstReference; 

   245     typedef typename Map::Reference Reference;

   246  };

   247 

   248   template <typename MatrixMap, typename Enable = void>

   249   struct MatrixMapTraits {

   250     typedef False ReferenceMapTag;

   251 

   252     typedef typename MatrixMap::FirstKey FirstKey;

   253     typedef typename MatrixMap::SecondKey SecondKey;

   254     typedef typename MatrixMap::Value Value;

   255 

   256     typedef const Value ConstReturnValue;

   257     typedef const Value ReturnValue;

   258   };

   259 

   260   template <typename MatrixMap>

   261   struct MatrixMapTraits<

   262     MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag, 

   263                                   void>::type > 

   264   {

   265     typedef True ReferenceMapTag;

   266     

   267     typedef typename MatrixMap::FirstKey FirstKey;

   268     typedef typename MatrixMap::SecondKey SecondKey;

   269     typedef typename MatrixMap::Value Value;

   270 

   271     typedef typename MatrixMap::ConstReference ConstReturnValue;

   272     typedef typename MatrixMap::Reference ReturnValue;

   273 

   274     typedef typename MatrixMap::ConstReference ConstReference; 

   275     typedef typename MatrixMap::Reference Reference;

   276  };

   277 

   278   // Indicators for the tags

   279 

   280   template <typename Graph, typename Enable = void>

   281   struct NodeNumTagIndicator {

   282     static const bool value = false;

   283   };

   284 

   285   template <typename Graph>

   286   struct NodeNumTagIndicator<

   287     Graph, 

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

   289   > {

   290     static const bool value = true;

   291   };

   292 

   293   template <typename Graph, typename Enable = void>

   294   struct EdgeNumTagIndicator {

   295     static const bool value = false;

   296   };

   297 

   298   template <typename Graph>

   299   struct EdgeNumTagIndicator<

   300     Graph, 

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

   302   > {

   303     static const bool value = true;

   304   };

   305 

   306   template <typename Graph, typename Enable = void>

   307   struct FindEdgeTagIndicator {

   308     static const bool value = false;

   309   };

   310 

   311   template <typename Graph>

   312   struct FindEdgeTagIndicator<

   313     Graph, 

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

   315   > {

   316     static const bool value = true;

   317   };

   318 

   319   template <typename Graph, typename Enable = void>

   320   struct UndirectedTagIndicator {

   321     static const bool value = false;

   322   };

   323 

   324   template <typename Graph>

   325   struct UndirectedTagIndicator<

   326     Graph, 

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

   328   > {

   329     static const bool value = true;

   330   };

   331 

   332   template <typename Graph, typename Enable = void>

   333   struct BuildTagIndicator {

   334     static const bool value = false;

   335   };

   336 

   337   template <typename Graph>

   338   struct BuildTagIndicator<

   339     Graph, 

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

   341   > {

   342     static const bool value = true;

   343   };

   344 

   345 }

   346 

   347 #endif
lemon-0.x