Mercuriallemon-1.2 / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/concepts/path.h
changeset 209 765619b7cbb2
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 {
lemon-1.2