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