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
Tue, 17 Oct 2006 10:50:57 +0000
changeset 2247 269a0dcee70b
parent 1996 5dc13b93f8b4
child 2290 f30867b359a8
permissions -rw-r--r--
Update the Path concept
Concept check for paths

DirPath renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed
// I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation 
     1 /* -*- C++ -*-

     2  *

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

     4  *

     5  * Copyright (C) 2003-2006

     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 #include <lemon/bits/utility.h>

    23 

    24 ///\file

    25 ///\brief Traits for graphs and maps

    26 ///

    27 

    28 namespace lemon {

    29   template <typename _Graph, typename _Item>

    30   class ItemSetTraits {};

    31   

    32 

    33   template <typename Graph, typename Enable = void>

    34   struct NodeNotifierIndicator {

    35     typedef InvalidType Type;

    36   };

    37   template <typename Graph>

    38   struct NodeNotifierIndicator<

    39     Graph, 

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

    41   > { 

    42     typedef typename Graph::NodeNotifier Type;

    43   };

    44 

    45   template <typename _Graph>

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

    47   public:

    48     

    49     typedef _Graph Graph;

    50 

    51     typedef typename Graph::Node Item;

    52     typedef typename Graph::NodeIt ItemIt;

    53 

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

    55 

    56     template <typename _Value>

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

    58     public:

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

    60       typedef typename Parent::Value Value;

    61 

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

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

    64 	: Parent(_graph, _value) {}

    65 

    66      };

    67 

    68   };

    69 

    70   template <typename Graph, typename Enable = void>

    71   struct EdgeNotifierIndicator {

    72     typedef InvalidType Type;

    73   };

    74   template <typename Graph>

    75   struct EdgeNotifierIndicator<

    76     Graph, 

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

    78   > { 

    79     typedef typename Graph::EdgeNotifier Type;

    80   };

    81 

    82   template <typename _Graph>

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

    84   public:

    85     

    86     typedef _Graph Graph;

    87 

    88     typedef typename Graph::Edge Item;

    89     typedef typename Graph::EdgeIt ItemIt;

    90 

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

    92 

    93     template <typename _Value>

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

    95     public:

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

    97       typedef typename Parent::Value Value;

    98 

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

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

   101 	: Parent(_graph, _value) {}

   102     };

   103 

   104   };

   105 

   106   template <typename Graph, typename Enable = void>

   107   struct UEdgeNotifierIndicator {

   108     typedef InvalidType Type;

   109   };

   110   template <typename Graph>

   111   struct UEdgeNotifierIndicator<

   112     Graph, 

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

   114   > { 

   115     typedef typename Graph::UEdgeNotifier Type;

   116   };

   117 

   118   template <typename _Graph>

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

   120   public:

   121     

   122     typedef _Graph Graph;

   123 

   124     typedef typename Graph::UEdge Item;

   125     typedef typename Graph::UEdgeIt ItemIt;

   126 

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

   128 

   129     template <typename _Value>

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

   131     public:

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

   133       typedef typename Parent::Value Value;

   134 

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

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

   137 	: Parent(_graph, _value) {}

   138     };

   139 

   140   };

   141 

   142   template <typename Graph, typename Enable = void>

   143   struct ANodeNotifierIndicator {

   144     typedef InvalidType Type;

   145   };

   146   template <typename Graph>

   147   struct ANodeNotifierIndicator<

   148     Graph, 

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

   150   > { 

   151     typedef typename Graph::ANodeNotifier Type;

   152   };

   153 

   154   template <typename _Graph>

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

   156   public:

   157     

   158     typedef _Graph Graph;

   159 

   160     typedef typename Graph::ANode Item;

   161     typedef typename Graph::ANodeIt ItemIt;

   162 

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

   164 

   165     template <typename _Value>

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

   167     public:

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

   169       typedef typename Parent::Value Value;

   170 

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

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

   173 	: Parent(_graph, _value) {}

   174     };

   175 

   176   };

   177 

   178   template <typename Graph, typename Enable = void>

   179   struct BNodeNotifierIndicator {

   180     typedef InvalidType Type;

   181   };

   182   template <typename Graph>

   183   struct BNodeNotifierIndicator<

   184     Graph, 

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

   186   > { 

   187     typedef typename Graph::BNodeNotifier Type;

   188   };

   189 

   190   template <typename _Graph>

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

   192   public:

   193     

   194     typedef _Graph Graph;

   195 

   196     typedef typename Graph::BNode Item;

   197     typedef typename Graph::BNodeIt ItemIt;

   198 

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

   200 

   201     template <typename _Value>

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

   203     public:

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

   205       typedef typename Parent::Value Value;

   206 

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

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

   209 	: Parent(_graph, _value) {}

   210     };

   211 

   212   };

   213 

   214 

   215   template <typename Map, typename Enable = void>

   216   struct MapTraits {

   217     typedef False ReferenceMapTag;

   218 

   219     typedef typename Map::Key Key;

   220     typedef typename Map::Value Value;

   221 

   222     typedef const Value ConstReturnValue;

   223     typedef const Value ReturnValue;

   224   };

   225 

   226   template <typename Map>

   227   struct MapTraits<

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

   229   {

   230     typedef True ReferenceMapTag;

   231     

   232     typedef typename Map::Key Key;

   233     typedef typename Map::Value Value;

   234 

   235     typedef typename Map::ConstReference ConstReturnValue;

   236     typedef typename Map::Reference ReturnValue;

   237 

   238     typedef typename Map::ConstReference ConstReference; 

   239     typedef typename Map::Reference Reference;

   240  };

   241 

   242   template <typename MatrixMap, typename Enable = void>

   243   struct MatrixMapTraits {

   244     typedef False ReferenceMapTag;

   245 

   246     typedef typename MatrixMap::FirstKey FirstKey;

   247     typedef typename MatrixMap::SecondKey SecondKey;

   248     typedef typename MatrixMap::Value Value;

   249 

   250     typedef const Value ConstReturnValue;

   251     typedef const Value ReturnValue;

   252   };

   253 

   254   template <typename MatrixMap>

   255   struct MatrixMapTraits<

   256     MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag, 

   257                                   void>::type > 

   258   {

   259     typedef True ReferenceMapTag;

   260     

   261     typedef typename MatrixMap::FirstKey FirstKey;

   262     typedef typename MatrixMap::SecondKey SecondKey;

   263     typedef typename MatrixMap::Value Value;

   264 

   265     typedef typename MatrixMap::ConstReference ConstReturnValue;

   266     typedef typename MatrixMap::Reference ReturnValue;

   267 

   268     typedef typename MatrixMap::ConstReference ConstReference; 

   269     typedef typename MatrixMap::Reference Reference;

   270  };

   271 

   272   // Indicators for the tags

   273 

   274   template <typename Graph, typename Enable = void>

   275   struct NodeNumTagIndicator {

   276     static const bool value = false;

   277   };

   278 

   279   template <typename Graph>

   280   struct NodeNumTagIndicator<

   281     Graph, 

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

   283   > {

   284     static const bool value = true;

   285   };

   286 

   287   template <typename Graph, typename Enable = void>

   288   struct EdgeNumTagIndicator {

   289     static const bool value = false;

   290   };

   291 

   292   template <typename Graph>

   293   struct EdgeNumTagIndicator<

   294     Graph, 

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

   296   > {

   297     static const bool value = true;

   298   };

   299 

   300   template <typename Graph, typename Enable = void>

   301   struct FindEdgeTagIndicator {

   302     static const bool value = false;

   303   };

   304 

   305   template <typename Graph>

   306   struct FindEdgeTagIndicator<

   307     Graph, 

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

   309   > {

   310     static const bool value = true;

   311   };

   312 

   313   template <typename Graph, typename Enable = void>

   314   struct UndirectedTagIndicator {

   315     static const bool value = false;

   316   };

   317 

   318   template <typename Graph>

   319   struct UndirectedTagIndicator<

   320     Graph, 

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

   322   > {

   323     static const bool value = true;

   324   };

   325 

   326 

   327 

   328 }

   329 

   330 #endif
lemon-0.x