lemon/concepts/path.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 01 Nov 2018 11:27:05 +0100
changeset 1416 f179aa1045a4
parent 1270 dceba191c00d
child 1417 2236d00ca778
permissions -rw-r--r--
Suppress unused typdef warnings (#615)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2013
     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 The concept of paths
    22 ///
    23 
    24 #ifndef LEMON_CONCEPTS_PATH_H
    25 #define LEMON_CONCEPTS_PATH_H
    26 
    27 #include <lemon/core.h>
    28 #include <lemon/concept_check.h>
    29 
    30 namespace lemon {
    31   namespace concepts {
    32 
    33     /// \addtogroup concept
    34     /// @{
    35 
    36     /// \brief A skeleton structure for representing directed paths in
    37     /// a digraph.
    38     ///
    39     /// A skeleton structure for representing directed paths in a
    40     /// digraph.
    41     /// In a sense, a path can be treated as a list of arcs.
    42     /// LEMON path types just store this list. As a consequence, they cannot
    43     /// enumerate the nodes on the path directly and a zero length path
    44     /// cannot store its source node.
    45     ///
    46     /// The arcs of a path should be stored in the order of their directions,
    47     /// i.e. the target node of each arc should be the same as the source
    48     /// node of the next arc. This consistency could be checked using
    49     /// \ref checkPath().
    50     /// The source and target nodes of a (consistent) path can be obtained
    51     /// using \ref pathSource() and \ref pathTarget().
    52     ///
    53     /// A path can be constructed from another path of any type using the
    54     /// copy constructor or the assignment operator.
    55     ///
    56     /// \tparam GR The digraph type in which the path is.
    57     template <typename GR>
    58     class Path {
    59     public:
    60 
    61       /// Type of the underlying digraph.
    62       typedef GR Digraph;
    63       /// Arc type of the underlying digraph.
    64       typedef typename Digraph::Arc Arc;
    65 
    66       class ArcIt;
    67 
    68       /// \brief Default constructor
    69       Path() {}
    70 
    71       /// \brief Template copy constructor
    72       template <typename CPath>
    73       Path(const CPath& cpath) {
    74         ::lemon::ignore_unused_variable_warning(cpath);
    75       }
    76 
    77       /// \brief Template assigment operator
    78       template <typename CPath>
    79       Path& operator=(const CPath& cpath) {
    80         ::lemon::ignore_unused_variable_warning(cpath);
    81         return *this;
    82       }
    83 
    84       /// Length of the path, i.e. the number of arcs on the path.
    85       int length() const { return 0;}
    86 
    87       /// Returns whether the path is empty.
    88       bool empty() const { return true;}
    89 
    90       /// Resets the path to an empty path.
    91       void clear() {}
    92 
    93       /// \brief LEMON style iterator for enumerating the arcs of a path.
    94       ///
    95       /// LEMON style iterator class for enumerating the arcs of a path.
    96       class ArcIt {
    97       public:
    98         /// Default constructor
    99         ArcIt() {}
   100         /// Invalid constructor
   101         ArcIt(Invalid) {}
   102         /// Sets the iterator to the first arc of the given path
   103         ArcIt(const Path &) {}
   104 
   105         /// Conversion to \c Arc
   106         operator Arc() const { return INVALID; }
   107 
   108         /// Next arc
   109         ArcIt& operator++() {return *this;}
   110 
   111         /// Comparison operator
   112         bool operator==(const ArcIt&) const {return true;}
   113         /// Comparison operator
   114         bool operator!=(const ArcIt&) const {return true;}
   115         /// Comparison operator
   116         bool operator<(const ArcIt&) const {return false;}
   117 
   118       };
   119 
   120       template <typename _Path>
   121       struct Constraints {
   122         void constraints() {
   123           Path<Digraph> pc;
   124           _Path p, pp(pc);
   125           int l = p.length();
   126           int e = p.empty();
   127           p.clear();
   128 
   129           p = pc;
   130 
   131           typename _Path::ArcIt id, ii(INVALID), i(p);
   132 
   133           ++i;
   134           typename Digraph::Arc ed = i;
   135 
   136           e = (i == ii);
   137           e = (i != ii);
   138           e = (i < ii);
   139 
   140           ::lemon::ignore_unused_variable_warning(l);
   141           ::lemon::ignore_unused_variable_warning(pp);
   142           ::lemon::ignore_unused_variable_warning(e);
   143           ::lemon::ignore_unused_variable_warning(id);
   144           ::lemon::ignore_unused_variable_warning(ii);
   145           ::lemon::ignore_unused_variable_warning(ed);
   146         }
   147       };
   148 
   149     };
   150 
   151     namespace _path_bits {
   152 
   153       template <typename _Digraph, typename _Path, typename RevPathTag = void>
   154       struct PathDumperConstraints {
   155         void constraints() {
   156           int l = p.length();
   157           int e = p.empty();
   158 
   159           typename _Path::ArcIt id, i(p);
   160 
   161           ++i;
   162           typename _Digraph::Arc ed = i;
   163 
   164           e = (i == INVALID);
   165           e = (i != INVALID);
   166 
   167           ::lemon::ignore_unused_variable_warning(l);
   168           ::lemon::ignore_unused_variable_warning(e);
   169           ::lemon::ignore_unused_variable_warning(id);
   170           ::lemon::ignore_unused_variable_warning(ed);
   171         }
   172         _Path& p;
   173         PathDumperConstraints() {}
   174       };
   175 
   176       template <typename _Digraph, typename _Path>
   177       struct PathDumperConstraints<
   178         _Digraph, _Path,
   179         typename enable_if<typename _Path::RevPathTag, void>::type
   180       > {
   181         void constraints() {
   182           int l = p.length();
   183           int e = p.empty();
   184 
   185           typename _Path::RevArcIt id, i(p);
   186 
   187           ++i;
   188           typename _Digraph::Arc ed = i;
   189 
   190           e = (i == INVALID);
   191           e = (i != INVALID);
   192 
   193           ::lemon::ignore_unused_variable_warning(l);
   194           ::lemon::ignore_unused_variable_warning(e);
   195           ::lemon::ignore_unused_variable_warning(id);
   196           ::lemon::ignore_unused_variable_warning(ed);
   197         }
   198         _Path& p;
   199         PathDumperConstraints() {}
   200       };
   201 
   202     }
   203 
   204 
   205     /// \brief A skeleton structure for path dumpers.
   206     ///
   207     /// A skeleton structure for path dumpers. The path dumpers are
   208     /// the generalization of the paths, they can enumerate the arcs
   209     /// of the path either in forward or in backward order.
   210     /// These classes are typically not used directly, they are rather
   211     /// used to be assigned to a real path type.
   212     ///
   213     /// The main purpose of this concept is that the shortest path
   214     /// algorithms can enumerate the arcs easily in reverse order.
   215     /// In LEMON, such algorithms give back a (reverse) path dumper that
   216     /// can be assigned to a real path. The dumpers can be implemented as
   217     /// an adaptor class to the predecessor map.
   218     ///
   219     /// \tparam GR The digraph type in which the path is.
   220     template <typename GR>
   221     class PathDumper {
   222     public:
   223 
   224       /// Type of the underlying digraph.
   225       typedef GR Digraph;
   226       /// Arc type of the underlying digraph.
   227       typedef typename Digraph::Arc Arc;
   228 
   229       /// Length of the path, i.e. the number of arcs on the path.
   230       int length() const { return 0;}
   231 
   232       /// Returns whether the path is empty.
   233       bool empty() const { return true;}
   234 
   235       /// \brief Forward or reverse dumping
   236       ///
   237       /// If this tag is defined to be \c True, then reverse dumping
   238       /// is provided in the path dumper. In this case, \c RevArcIt
   239       /// iterator should be implemented instead of \c ArcIt iterator.
   240       typedef False RevPathTag;
   241 
   242       /// \brief LEMON style iterator for enumerating the arcs of a path.
   243       ///
   244       /// LEMON style iterator class for enumerating the arcs of a path.
   245       class ArcIt {
   246       public:
   247         /// Default constructor
   248         ArcIt() {}
   249         /// Invalid constructor
   250         ArcIt(Invalid) {}
   251         /// Sets the iterator to the first arc of the given path
   252         ArcIt(const PathDumper&) {}
   253 
   254         /// Conversion to \c Arc
   255         operator Arc() const { return INVALID; }
   256 
   257         /// Next arc
   258         ArcIt& operator++() {return *this;}
   259 
   260         /// Comparison operator
   261         bool operator==(const ArcIt&) const {return true;}
   262         /// Comparison operator
   263         bool operator!=(const ArcIt&) const {return true;}
   264         /// Comparison operator
   265         bool operator<(const ArcIt&) const {return false;}
   266 
   267       };
   268 
   269       /// \brief LEMON style iterator for enumerating the arcs of a path
   270       /// in reverse direction.
   271       ///
   272       /// LEMON style iterator class for enumerating the arcs of a path
   273       /// in reverse direction.
   274       class RevArcIt {
   275       public:
   276         /// Default constructor
   277         RevArcIt() {}
   278         /// Invalid constructor
   279         RevArcIt(Invalid) {}
   280         /// Sets the iterator to the last arc of the given path
   281         RevArcIt(const PathDumper &) {}
   282 
   283         /// Conversion to \c Arc
   284         operator Arc() const { return INVALID; }
   285 
   286         /// Next arc
   287         RevArcIt& operator++() {return *this;}
   288 
   289         /// Comparison operator
   290         bool operator==(const RevArcIt&) const {return true;}
   291         /// Comparison operator
   292         bool operator!=(const RevArcIt&) const {return true;}
   293         /// Comparison operator
   294         bool operator<(const RevArcIt&) const {return false;}
   295 
   296       };
   297 
   298       template <typename _Path>
   299       struct Constraints {
   300         void constraints() {
   301           function_requires<_path_bits::
   302             PathDumperConstraints<Digraph, _Path> >();
   303         }
   304       };
   305 
   306     };
   307 
   308 
   309     ///@}
   310   }
   311 
   312 } // namespace lemon
   313 
   314 #endif