lemon/concepts/path.h
author Balazs Dezso <deba@inf.elte.hu>
Tue, 22 Apr 2008 15:04:00 +0200
changeset 139 701c529ba737
child 157 2ccc1afc2c52
permissions -rw-r--r--
Renamings in the graph_utils.h + graph_utils_test added
     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