lemon/concepts/path.h
changeset 128 7cd965d2257f
child 157 2ccc1afc2c52
equal deleted inserted replaced
-1:000000000000 0:8255b106e083
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2008
       
     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 ///\ingroup concept
       
    20 ///\file
       
    21 ///\brief Classes for representing paths in digraphs.
       
    22 ///
       
    23 ///\todo Iterators have obsolete style
       
    24 
       
    25 #ifndef LEMON_CONCEPT_PATH_H
       
    26 #define LEMON_CONCEPT_PATH_H
       
    27 
       
    28 #include <lemon/bits/invalid.h>
       
    29 #include <lemon/bits/utility.h>
       
    30 #include <lemon/concept_check.h>
       
    31 
       
    32 namespace lemon {
       
    33   namespace concepts {
       
    34 
       
    35     /// \addtogroup concept
       
    36     /// @{
       
    37 
       
    38     /// \brief A skeleton structure for representing directed paths in
       
    39     /// a digraph.
       
    40     ///
       
    41     /// A skeleton structure for representing directed paths in a
       
    42     /// digraph.  
       
    43     /// \param _Digraph The digraph type in which the path is.
       
    44     ///
       
    45     /// In a sense, the path can be treated as a list of arcs. The
       
    46     /// lemon path type stores just this list. As a consequence it
       
    47     /// cannot enumerate the nodes in the path and the zero length
       
    48     /// paths cannot store the source.
       
    49     ///
       
    50     template <typename _Digraph>
       
    51     class Path {
       
    52     public:
       
    53 
       
    54       /// Type of the underlying digraph.
       
    55       typedef _Digraph Digraph;
       
    56       /// Arc type of the underlying digraph.
       
    57       typedef typename Digraph::Arc Arc;
       
    58 
       
    59       class ArcIt;
       
    60 
       
    61       /// \brief Default constructor
       
    62       Path() {}
       
    63 
       
    64       /// \brief Template constructor
       
    65       template <typename CPath>
       
    66       Path(const CPath& cpath) {}
       
    67 
       
    68       /// \brief Template assigment
       
    69       template <typename CPath>
       
    70       Path& operator=(const CPath& cpath) {}
       
    71 
       
    72       /// Length of the path ie. the number of arcs in the path.
       
    73       int length() const { return 0;}
       
    74 
       
    75       /// Returns whether the path is empty.
       
    76       bool empty() const { return true;}
       
    77 
       
    78       /// Resets the path to an empty path.
       
    79       void clear() {}
       
    80 
       
    81       /// \brief Lemon style iterator for path arcs
       
    82       ///
       
    83       /// This class is used to iterate on the arcs of the paths.
       
    84       class ArcIt {
       
    85       public:
       
    86 	/// Default constructor
       
    87 	ArcIt() {}
       
    88 	/// Invalid constructor
       
    89 	ArcIt(Invalid) {}
       
    90 	/// Constructor for first arc
       
    91 	ArcIt(const Path &) {}
       
    92 
       
    93         /// Conversion to Arc
       
    94 	operator Arc() const { return INVALID; }
       
    95 
       
    96 	/// Next arc
       
    97 	ArcIt& operator++() {return *this;}
       
    98 
       
    99 	/// Comparison operator
       
   100 	bool operator==(const ArcIt&) const {return true;}
       
   101 	/// Comparison operator
       
   102 	bool operator!=(const ArcIt&) const {return true;}
       
   103  	/// Comparison operator
       
   104  	bool operator<(const ArcIt&) const {return false;}
       
   105 
       
   106       };
       
   107 
       
   108       template <typename _Path>
       
   109       struct Constraints {
       
   110         void constraints() {
       
   111           Path<Digraph> pc;
       
   112           _Path p, pp(pc);
       
   113           int l = p.length();
       
   114           int e = p.empty();
       
   115           p.clear();
       
   116 
       
   117           p = pc;
       
   118 
       
   119           typename _Path::ArcIt id, ii(INVALID), i(p);
       
   120 
       
   121           ++i;
       
   122           typename Digraph::Arc ed = i;
       
   123 
       
   124           e = (i == ii);
       
   125           e = (i != ii);
       
   126           e = (i < ii);
       
   127 
       
   128           ignore_unused_variable_warning(l);
       
   129           ignore_unused_variable_warning(pp);
       
   130           ignore_unused_variable_warning(e);
       
   131           ignore_unused_variable_warning(id);
       
   132           ignore_unused_variable_warning(ii);
       
   133           ignore_unused_variable_warning(ed);
       
   134         }
       
   135       };
       
   136 
       
   137     };
       
   138 
       
   139     namespace _path_bits {
       
   140       
       
   141       template <typename _Digraph, typename _Path, typename RevPathTag = void>
       
   142       struct PathDumperConstraints {
       
   143         void constraints() {
       
   144           int l = p.length();
       
   145           int e = p.empty();
       
   146 
       
   147           typename _Path::ArcIt id, i(p);
       
   148 
       
   149           ++i;
       
   150           typename _Digraph::Arc ed = i;
       
   151 
       
   152           e = (i == INVALID);
       
   153           e = (i != INVALID);
       
   154 
       
   155           ignore_unused_variable_warning(l);
       
   156           ignore_unused_variable_warning(e);
       
   157           ignore_unused_variable_warning(id);
       
   158           ignore_unused_variable_warning(ed);
       
   159         }
       
   160         _Path& p;
       
   161       };
       
   162 
       
   163       template <typename _Digraph, typename _Path>
       
   164       struct PathDumperConstraints<
       
   165         _Digraph, _Path, 
       
   166         typename enable_if<typename _Path::RevPathTag, void>::type
       
   167       > {
       
   168         void constraints() {
       
   169           int l = p.length();
       
   170           int e = p.empty();
       
   171 
       
   172           typename _Path::RevArcIt id, i(p);
       
   173 
       
   174           ++i;
       
   175           typename _Digraph::Arc ed = i;
       
   176 
       
   177           e = (i == INVALID);
       
   178           e = (i != INVALID);
       
   179 
       
   180           ignore_unused_variable_warning(l);
       
   181           ignore_unused_variable_warning(e);
       
   182           ignore_unused_variable_warning(id);
       
   183           ignore_unused_variable_warning(ed);
       
   184         }
       
   185         _Path& p;
       
   186       };
       
   187     
       
   188     }
       
   189 
       
   190 
       
   191     /// \brief A skeleton structure for path dumpers.
       
   192     ///
       
   193     /// A skeleton structure for path dumpers. The path dumpers are
       
   194     /// the generalization of the paths. The path dumpers can
       
   195     /// enumerate the arcs of the path wheter in forward or in
       
   196     /// backward order.  In most time these classes are not used
       
   197     /// directly rather it used to assign a dumped class to a real
       
   198     /// path type.
       
   199     ///
       
   200     /// The main purpose of this concept is that the shortest path
       
   201     /// algorithms can enumerate easily the arcs in reverse order.
       
   202     /// If we would like to give back a real path from these
       
   203     /// algorithms then we should create a temporarly path object. In
       
   204     /// Lemon such algorithms gives back a path dumper what can
       
   205     /// assigned to a real path and the dumpers can be implemented as
       
   206     /// an adaptor class to the predecessor map.
       
   207 
       
   208     /// \param _Digraph  The digraph type in which the path is.
       
   209     ///
       
   210     /// The paths can be constructed from any path type by a
       
   211     /// template constructor or a template assignment operator.
       
   212     /// 
       
   213     template <typename _Digraph>
       
   214     class PathDumper {
       
   215     public:
       
   216 
       
   217       /// Type of the underlying digraph.
       
   218       typedef _Digraph Digraph;
       
   219       /// Arc type of the underlying digraph.
       
   220       typedef typename Digraph::Arc Arc;
       
   221 
       
   222       /// Length of the path ie. the number of arcs in the path.
       
   223       int length() const { return 0;}
       
   224 
       
   225       /// Returns whether the path is empty.
       
   226       bool empty() const { return true;}
       
   227 
       
   228       /// \brief Forward or reverse dumping
       
   229       ///
       
   230       /// If the RevPathTag is defined and true then reverse dumping
       
   231       /// is provided in the path dumper. In this case instead of the
       
   232       /// ArcIt the RevArcIt iterator should be implemented in the
       
   233       /// dumper.
       
   234       typedef False RevPathTag;
       
   235 
       
   236       /// \brief Lemon style iterator for path arcs
       
   237       ///
       
   238       /// This class is used to iterate on the arcs of the paths.
       
   239       class ArcIt {
       
   240       public:
       
   241 	/// Default constructor
       
   242 	ArcIt() {}
       
   243 	/// Invalid constructor
       
   244 	ArcIt(Invalid) {}
       
   245 	/// Constructor for first arc
       
   246 	ArcIt(const PathDumper&) {}
       
   247 
       
   248         /// Conversion to Arc
       
   249 	operator Arc() const { return INVALID; }
       
   250 
       
   251 	/// Next arc
       
   252 	ArcIt& operator++() {return *this;}
       
   253 
       
   254 	/// Comparison operator
       
   255 	bool operator==(const ArcIt&) const {return true;}
       
   256 	/// Comparison operator
       
   257 	bool operator!=(const ArcIt&) const {return true;}
       
   258  	/// Comparison operator
       
   259  	bool operator<(const ArcIt&) const {return false;}
       
   260 
       
   261       };
       
   262 
       
   263       /// \brief Lemon style iterator for path arcs
       
   264       ///
       
   265       /// This class is used to iterate on the arcs of the paths in
       
   266       /// reverse direction.
       
   267       class RevArcIt {
       
   268       public:
       
   269 	/// Default constructor
       
   270 	RevArcIt() {}
       
   271 	/// Invalid constructor
       
   272 	RevArcIt(Invalid) {}
       
   273 	/// Constructor for first arc
       
   274 	RevArcIt(const PathDumper &) {}
       
   275 
       
   276         /// Conversion to Arc
       
   277 	operator Arc() const { return INVALID; }
       
   278 
       
   279 	/// Next arc
       
   280 	RevArcIt& operator++() {return *this;}
       
   281 
       
   282 	/// Comparison operator
       
   283 	bool operator==(const RevArcIt&) const {return true;}
       
   284 	/// Comparison operator
       
   285 	bool operator!=(const RevArcIt&) const {return true;}
       
   286  	/// Comparison operator
       
   287  	bool operator<(const RevArcIt&) const {return false;}
       
   288 
       
   289       };
       
   290 
       
   291       template <typename _Path>
       
   292       struct Constraints {
       
   293         void constraints() {
       
   294           function_requires<_path_bits::
       
   295             PathDumperConstraints<Digraph, _Path> >();
       
   296         }
       
   297       };
       
   298 
       
   299     };
       
   300 
       
   301 
       
   302     ///@}
       
   303   }
       
   304 
       
   305 } // namespace lemon
       
   306 
       
   307 #endif // LEMON_CONCEPT_PATH_H