lemon/concepts/path.h
changeset 214 60eecd3fe37a
parent 157 2ccc1afc2c52
child 212 1ae84dea7d09
equal deleted inserted replaced
1:ae451340f528 2:2c14fa7627e2
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    37 
    37 
    38     /// \brief A skeleton structure for representing directed paths in
    38     /// \brief A skeleton structure for representing directed paths in
    39     /// a digraph.
    39     /// a digraph.
    40     ///
    40     ///
    41     /// A skeleton structure for representing directed paths in a
    41     /// A skeleton structure for representing directed paths in a
    42     /// digraph.  
    42     /// digraph.
    43     /// \tparam _Digraph The digraph type in which the path is.
    43     /// \tparam _Digraph The digraph type in which the path is.
    44     ///
    44     ///
    45     /// In a sense, the path can be treated as a list of arcs. The
    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
    46     /// lemon path type stores just this list. As a consequence it
    47     /// cannot enumerate the nodes in the path and the zero length
    47     /// cannot enumerate the nodes in the path and the zero length
    81       /// \brief Lemon style iterator for path arcs
    81       /// \brief Lemon style iterator for path arcs
    82       ///
    82       ///
    83       /// This class is used to iterate on the arcs of the paths.
    83       /// This class is used to iterate on the arcs of the paths.
    84       class ArcIt {
    84       class ArcIt {
    85       public:
    85       public:
    86 	/// Default constructor
    86         /// Default constructor
    87 	ArcIt() {}
    87         ArcIt() {}
    88 	/// Invalid constructor
    88         /// Invalid constructor
    89 	ArcIt(Invalid) {}
    89         ArcIt(Invalid) {}
    90 	/// Constructor for first arc
    90         /// Constructor for first arc
    91 	ArcIt(const Path &) {}
    91         ArcIt(const Path &) {}
    92 
    92 
    93         /// Conversion to Arc
    93         /// Conversion to Arc
    94 	operator Arc() const { return INVALID; }
    94         operator Arc() const { return INVALID; }
    95 
    95 
    96 	/// Next arc
    96         /// Next arc
    97 	ArcIt& operator++() {return *this;}
    97         ArcIt& operator++() {return *this;}
    98 
    98 
    99 	/// Comparison operator
    99         /// Comparison operator
   100 	bool operator==(const ArcIt&) const {return true;}
   100         bool operator==(const ArcIt&) const {return true;}
   101 	/// Comparison operator
   101         /// Comparison operator
   102 	bool operator!=(const ArcIt&) const {return true;}
   102         bool operator!=(const ArcIt&) const {return true;}
   103  	/// Comparison operator
   103          /// Comparison operator
   104  	bool operator<(const ArcIt&) const {return false;}
   104          bool operator<(const ArcIt&) const {return false;}
   105 
   105 
   106       };
   106       };
   107 
   107 
   108       template <typename _Path>
   108       template <typename _Path>
   109       struct Constraints {
   109       struct Constraints {
   135       };
   135       };
   136 
   136 
   137     };
   137     };
   138 
   138 
   139     namespace _path_bits {
   139     namespace _path_bits {
   140       
   140 
   141       template <typename _Digraph, typename _Path, typename RevPathTag = void>
   141       template <typename _Digraph, typename _Path, typename RevPathTag = void>
   142       struct PathDumperConstraints {
   142       struct PathDumperConstraints {
   143         void constraints() {
   143         void constraints() {
   144           int l = p.length();
   144           int l = p.length();
   145           int e = p.empty();
   145           int e = p.empty();
   160         _Path& p;
   160         _Path& p;
   161       };
   161       };
   162 
   162 
   163       template <typename _Digraph, typename _Path>
   163       template <typename _Digraph, typename _Path>
   164       struct PathDumperConstraints<
   164       struct PathDumperConstraints<
   165         _Digraph, _Path, 
   165         _Digraph, _Path,
   166         typename enable_if<typename _Path::RevPathTag, void>::type
   166         typename enable_if<typename _Path::RevPathTag, void>::type
   167       > {
   167       > {
   168         void constraints() {
   168         void constraints() {
   169           int l = p.length();
   169           int l = p.length();
   170           int e = p.empty();
   170           int e = p.empty();
   182           ignore_unused_variable_warning(id);
   182           ignore_unused_variable_warning(id);
   183           ignore_unused_variable_warning(ed);
   183           ignore_unused_variable_warning(ed);
   184         }
   184         }
   185         _Path& p;
   185         _Path& p;
   186       };
   186       };
   187     
   187 
   188     }
   188     }
   189 
   189 
   190 
   190 
   191     /// \brief A skeleton structure for path dumpers.
   191     /// \brief A skeleton structure for path dumpers.
   192     ///
   192     ///
   207 
   207 
   208     /// \tparam _Digraph  The digraph type in which the path is.
   208     /// \tparam _Digraph  The digraph type in which the path is.
   209     ///
   209     ///
   210     /// The paths can be constructed from any path type by a
   210     /// The paths can be constructed from any path type by a
   211     /// template constructor or a template assignment operator.
   211     /// template constructor or a template assignment operator.
   212     /// 
   212     ///
   213     template <typename _Digraph>
   213     template <typename _Digraph>
   214     class PathDumper {
   214     class PathDumper {
   215     public:
   215     public:
   216 
   216 
   217       /// Type of the underlying digraph.
   217       /// Type of the underlying digraph.
   236       /// \brief Lemon style iterator for path arcs
   236       /// \brief Lemon style iterator for path arcs
   237       ///
   237       ///
   238       /// This class is used to iterate on the arcs of the paths.
   238       /// This class is used to iterate on the arcs of the paths.
   239       class ArcIt {
   239       class ArcIt {
   240       public:
   240       public:
   241 	/// Default constructor
   241         /// Default constructor
   242 	ArcIt() {}
   242         ArcIt() {}
   243 	/// Invalid constructor
   243         /// Invalid constructor
   244 	ArcIt(Invalid) {}
   244         ArcIt(Invalid) {}
   245 	/// Constructor for first arc
   245         /// Constructor for first arc
   246 	ArcIt(const PathDumper&) {}
   246         ArcIt(const PathDumper&) {}
   247 
   247 
   248         /// Conversion to Arc
   248         /// Conversion to Arc
   249 	operator Arc() const { return INVALID; }
   249         operator Arc() const { return INVALID; }
   250 
   250 
   251 	/// Next arc
   251         /// Next arc
   252 	ArcIt& operator++() {return *this;}
   252         ArcIt& operator++() {return *this;}
   253 
   253 
   254 	/// Comparison operator
   254         /// Comparison operator
   255 	bool operator==(const ArcIt&) const {return true;}
   255         bool operator==(const ArcIt&) const {return true;}
   256 	/// Comparison operator
   256         /// Comparison operator
   257 	bool operator!=(const ArcIt&) const {return true;}
   257         bool operator!=(const ArcIt&) const {return true;}
   258  	/// Comparison operator
   258          /// Comparison operator
   259  	bool operator<(const ArcIt&) const {return false;}
   259          bool operator<(const ArcIt&) const {return false;}
   260 
   260 
   261       };
   261       };
   262 
   262 
   263       /// \brief Lemon style iterator for path arcs
   263       /// \brief Lemon style iterator for path arcs
   264       ///
   264       ///
   265       /// This class is used to iterate on the arcs of the paths in
   265       /// This class is used to iterate on the arcs of the paths in
   266       /// reverse direction.
   266       /// reverse direction.
   267       class RevArcIt {
   267       class RevArcIt {
   268       public:
   268       public:
   269 	/// Default constructor
   269         /// Default constructor
   270 	RevArcIt() {}
   270         RevArcIt() {}
   271 	/// Invalid constructor
   271         /// Invalid constructor
   272 	RevArcIt(Invalid) {}
   272         RevArcIt(Invalid) {}
   273 	/// Constructor for first arc
   273         /// Constructor for first arc
   274 	RevArcIt(const PathDumper &) {}
   274         RevArcIt(const PathDumper &) {}
   275 
   275 
   276         /// Conversion to Arc
   276         /// Conversion to Arc
   277 	operator Arc() const { return INVALID; }
   277         operator Arc() const { return INVALID; }
   278 
   278 
   279 	/// Next arc
   279         /// Next arc
   280 	RevArcIt& operator++() {return *this;}
   280         RevArcIt& operator++() {return *this;}
   281 
   281 
   282 	/// Comparison operator
   282         /// Comparison operator
   283 	bool operator==(const RevArcIt&) const {return true;}
   283         bool operator==(const RevArcIt&) const {return true;}
   284 	/// Comparison operator
   284         /// Comparison operator
   285 	bool operator!=(const RevArcIt&) const {return true;}
   285         bool operator!=(const RevArcIt&) const {return true;}
   286  	/// Comparison operator
   286          /// Comparison operator
   287  	bool operator<(const RevArcIt&) const {return false;}
   287          bool operator<(const RevArcIt&) const {return false;}
   288 
   288 
   289       };
   289       };
   290 
   290 
   291       template <typename _Path>
   291       template <typename _Path>
   292       struct Constraints {
   292       struct Constraints {