lemon/concepts/path.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 03 Aug 2008 13:34:57 +0200
changeset 244 c30731a37f91
parent 209 765619b7cbb2
child 220 a5d8c039f218
permissions -rw-r--r--
Many improvements in bfs.h, dfs.h and dijkstra.h
- Add run() function to Bfs and run(s,t) function to DfsVisit.
- Add debug checking to addSource() function of Dfs and DfsVisit.
- Add a few missing named parameters (according to \todo notes).
- Small fixes in the code (e.g. missing derivations).
- Many doc improvements.
- Remove \todo and \warning comments which are no longer valid.
- Remove \author commands (see ticket #39).
- Fixes in the the doc (e.g. wrong references).
- Hide the doc of most of the private and protected members.
- Use public typedefs instead of template parameters in public functions.
- Use better parameter names for some functions.
- Other small changes to make the doc more uniform.
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@96
     5
 * Copyright (C) 2003-2008
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
alpar@96
    21
///\brief Classes for representing paths in digraphs.
alpar@96
    22
///
alpar@96
    23
///\todo Iterators have obsolete style
alpar@96
    24
alpar@96
    25
#ifndef LEMON_CONCEPT_PATH_H
alpar@96
    26
#define LEMON_CONCEPT_PATH_H
alpar@96
    27
alpar@96
    28
#include <lemon/bits/invalid.h>
alpar@96
    29
#include <lemon/bits/utility.h>
alpar@96
    30
#include <lemon/concept_check.h>
alpar@96
    31
alpar@96
    32
namespace lemon {
alpar@96
    33
  namespace concepts {
alpar@96
    34
alpar@96
    35
    /// \addtogroup concept
alpar@96
    36
    /// @{
alpar@96
    37
alpar@96
    38
    /// \brief A skeleton structure for representing directed paths in
alpar@96
    39
    /// a digraph.
alpar@96
    40
    ///
alpar@96
    41
    /// A skeleton structure for representing directed paths in a
alpar@209
    42
    /// digraph.
kpeter@157
    43
    /// \tparam _Digraph The digraph type in which the path is.
alpar@96
    44
    ///
alpar@96
    45
    /// In a sense, the path can be treated as a list of arcs. The
alpar@96
    46
    /// lemon path type stores just this list. As a consequence it
alpar@96
    47
    /// cannot enumerate the nodes in the path and the zero length
alpar@96
    48
    /// paths cannot store the source.
alpar@96
    49
    ///
alpar@96
    50
    template <typename _Digraph>
alpar@96
    51
    class Path {
alpar@96
    52
    public:
alpar@96
    53
alpar@96
    54
      /// Type of the underlying digraph.
alpar@96
    55
      typedef _Digraph Digraph;
alpar@96
    56
      /// Arc type of the underlying digraph.
alpar@96
    57
      typedef typename Digraph::Arc Arc;
alpar@96
    58
alpar@96
    59
      class ArcIt;
alpar@96
    60
alpar@96
    61
      /// \brief Default constructor
alpar@96
    62
      Path() {}
alpar@96
    63
alpar@96
    64
      /// \brief Template constructor
alpar@96
    65
      template <typename CPath>
alpar@96
    66
      Path(const CPath& cpath) {}
alpar@96
    67
alpar@96
    68
      /// \brief Template assigment
alpar@96
    69
      template <typename CPath>
alpar@96
    70
      Path& operator=(const CPath& cpath) {}
alpar@96
    71
alpar@96
    72
      /// Length of the path ie. the number of arcs in the path.
alpar@96
    73
      int length() const { return 0;}
alpar@96
    74
alpar@96
    75
      /// Returns whether the path is empty.
alpar@96
    76
      bool empty() const { return true;}
alpar@96
    77
alpar@96
    78
      /// Resets the path to an empty path.
alpar@96
    79
      void clear() {}
alpar@96
    80
alpar@96
    81
      /// \brief Lemon style iterator for path arcs
alpar@96
    82
      ///
alpar@96
    83
      /// This class is used to iterate on the arcs of the paths.
alpar@96
    84
      class ArcIt {
alpar@96
    85
      public:
alpar@209
    86
        /// Default constructor
alpar@209
    87
        ArcIt() {}
alpar@209
    88
        /// Invalid constructor
alpar@209
    89
        ArcIt(Invalid) {}
alpar@209
    90
        /// Constructor for first arc
alpar@209
    91
        ArcIt(const Path &) {}
alpar@96
    92
alpar@96
    93
        /// Conversion to Arc
alpar@209
    94
        operator Arc() const { return INVALID; }
alpar@96
    95
alpar@209
    96
        /// Next arc
alpar@209
    97
        ArcIt& operator++() {return *this;}
alpar@96
    98
alpar@209
    99
        /// Comparison operator
alpar@209
   100
        bool operator==(const ArcIt&) const {return true;}
alpar@209
   101
        /// Comparison operator
alpar@209
   102
        bool operator!=(const ArcIt&) const {return true;}
kpeter@212
   103
        /// Comparison operator
kpeter@212
   104
        bool operator<(const ArcIt&) const {return false;}
alpar@96
   105
alpar@96
   106
      };
alpar@96
   107
alpar@96
   108
      template <typename _Path>
alpar@96
   109
      struct Constraints {
alpar@96
   110
        void constraints() {
alpar@96
   111
          Path<Digraph> pc;
alpar@96
   112
          _Path p, pp(pc);
alpar@96
   113
          int l = p.length();
alpar@96
   114
          int e = p.empty();
alpar@96
   115
          p.clear();
alpar@96
   116
alpar@96
   117
          p = pc;
alpar@96
   118
alpar@96
   119
          typename _Path::ArcIt id, ii(INVALID), i(p);
alpar@96
   120
alpar@96
   121
          ++i;
alpar@96
   122
          typename Digraph::Arc ed = i;
alpar@96
   123
alpar@96
   124
          e = (i == ii);
alpar@96
   125
          e = (i != ii);
alpar@96
   126
          e = (i < ii);
alpar@96
   127
alpar@96
   128
          ignore_unused_variable_warning(l);
alpar@96
   129
          ignore_unused_variable_warning(pp);
alpar@96
   130
          ignore_unused_variable_warning(e);
alpar@96
   131
          ignore_unused_variable_warning(id);
alpar@96
   132
          ignore_unused_variable_warning(ii);
alpar@96
   133
          ignore_unused_variable_warning(ed);
alpar@96
   134
        }
alpar@96
   135
      };
alpar@96
   136
alpar@96
   137
    };
alpar@96
   138
alpar@96
   139
    namespace _path_bits {
alpar@209
   140
alpar@96
   141
      template <typename _Digraph, typename _Path, typename RevPathTag = void>
alpar@96
   142
      struct PathDumperConstraints {
alpar@96
   143
        void constraints() {
alpar@96
   144
          int l = p.length();
alpar@96
   145
          int e = p.empty();
alpar@96
   146
alpar@96
   147
          typename _Path::ArcIt id, i(p);
alpar@96
   148
alpar@96
   149
          ++i;
alpar@96
   150
          typename _Digraph::Arc ed = i;
alpar@96
   151
alpar@96
   152
          e = (i == INVALID);
alpar@96
   153
          e = (i != INVALID);
alpar@96
   154
alpar@96
   155
          ignore_unused_variable_warning(l);
alpar@96
   156
          ignore_unused_variable_warning(e);
alpar@96
   157
          ignore_unused_variable_warning(id);
alpar@96
   158
          ignore_unused_variable_warning(ed);
alpar@96
   159
        }
alpar@96
   160
        _Path& p;
alpar@96
   161
      };
alpar@96
   162
alpar@96
   163
      template <typename _Digraph, typename _Path>
alpar@96
   164
      struct PathDumperConstraints<
alpar@209
   165
        _Digraph, _Path,
alpar@96
   166
        typename enable_if<typename _Path::RevPathTag, void>::type
alpar@96
   167
      > {
alpar@96
   168
        void constraints() {
alpar@96
   169
          int l = p.length();
alpar@96
   170
          int e = p.empty();
alpar@96
   171
alpar@96
   172
          typename _Path::RevArcIt id, i(p);
alpar@96
   173
alpar@96
   174
          ++i;
alpar@96
   175
          typename _Digraph::Arc ed = i;
alpar@96
   176
alpar@96
   177
          e = (i == INVALID);
alpar@96
   178
          e = (i != INVALID);
alpar@96
   179
alpar@96
   180
          ignore_unused_variable_warning(l);
alpar@96
   181
          ignore_unused_variable_warning(e);
alpar@96
   182
          ignore_unused_variable_warning(id);
alpar@96
   183
          ignore_unused_variable_warning(ed);
alpar@96
   184
        }
alpar@96
   185
        _Path& p;
alpar@96
   186
      };
alpar@209
   187
alpar@96
   188
    }
alpar@96
   189
alpar@96
   190
alpar@96
   191
    /// \brief A skeleton structure for path dumpers.
alpar@96
   192
    ///
alpar@96
   193
    /// A skeleton structure for path dumpers. The path dumpers are
alpar@96
   194
    /// the generalization of the paths. The path dumpers can
alpar@96
   195
    /// enumerate the arcs of the path wheter in forward or in
alpar@96
   196
    /// backward order.  In most time these classes are not used
alpar@96
   197
    /// directly rather it used to assign a dumped class to a real
alpar@96
   198
    /// path type.
alpar@96
   199
    ///
alpar@96
   200
    /// The main purpose of this concept is that the shortest path
alpar@96
   201
    /// algorithms can enumerate easily the arcs in reverse order.
alpar@96
   202
    /// If we would like to give back a real path from these
alpar@96
   203
    /// algorithms then we should create a temporarly path object. In
alpar@96
   204
    /// Lemon such algorithms gives back a path dumper what can
alpar@96
   205
    /// assigned to a real path and the dumpers can be implemented as
alpar@96
   206
    /// an adaptor class to the predecessor map.
alpar@96
   207
kpeter@157
   208
    /// \tparam _Digraph  The digraph type in which the path is.
alpar@96
   209
    ///
alpar@96
   210
    /// The paths can be constructed from any path type by a
alpar@96
   211
    /// template constructor or a template assignment operator.
alpar@209
   212
    ///
alpar@96
   213
    template <typename _Digraph>
alpar@96
   214
    class PathDumper {
alpar@96
   215
    public:
alpar@96
   216
alpar@96
   217
      /// Type of the underlying digraph.
alpar@96
   218
      typedef _Digraph Digraph;
alpar@96
   219
      /// Arc type of the underlying digraph.
alpar@96
   220
      typedef typename Digraph::Arc Arc;
alpar@96
   221
alpar@96
   222
      /// Length of the path ie. the number of arcs in the path.
alpar@96
   223
      int length() const { return 0;}
alpar@96
   224
alpar@96
   225
      /// Returns whether the path is empty.
alpar@96
   226
      bool empty() const { return true;}
alpar@96
   227
alpar@96
   228
      /// \brief Forward or reverse dumping
alpar@96
   229
      ///
alpar@96
   230
      /// If the RevPathTag is defined and true then reverse dumping
alpar@96
   231
      /// is provided in the path dumper. In this case instead of the
alpar@96
   232
      /// ArcIt the RevArcIt iterator should be implemented in the
alpar@96
   233
      /// dumper.
alpar@96
   234
      typedef False RevPathTag;
alpar@96
   235
alpar@96
   236
      /// \brief Lemon style iterator for path arcs
alpar@96
   237
      ///
alpar@96
   238
      /// This class is used to iterate on the arcs of the paths.
alpar@96
   239
      class ArcIt {
alpar@96
   240
      public:
alpar@209
   241
        /// Default constructor
alpar@209
   242
        ArcIt() {}
alpar@209
   243
        /// Invalid constructor
alpar@209
   244
        ArcIt(Invalid) {}
alpar@209
   245
        /// Constructor for first arc
alpar@209
   246
        ArcIt(const PathDumper&) {}
alpar@96
   247
alpar@96
   248
        /// Conversion to Arc
alpar@209
   249
        operator Arc() const { return INVALID; }
alpar@96
   250
alpar@209
   251
        /// Next arc
alpar@209
   252
        ArcIt& operator++() {return *this;}
alpar@96
   253
alpar@209
   254
        /// Comparison operator
alpar@209
   255
        bool operator==(const ArcIt&) const {return true;}
alpar@209
   256
        /// Comparison operator
alpar@209
   257
        bool operator!=(const ArcIt&) const {return true;}
kpeter@212
   258
        /// Comparison operator
kpeter@212
   259
        bool operator<(const ArcIt&) const {return false;}
alpar@96
   260
alpar@96
   261
      };
alpar@96
   262
alpar@96
   263
      /// \brief Lemon style iterator for path arcs
alpar@96
   264
      ///
alpar@96
   265
      /// This class is used to iterate on the arcs of the paths in
alpar@96
   266
      /// reverse direction.
alpar@96
   267
      class RevArcIt {
alpar@96
   268
      public:
alpar@209
   269
        /// Default constructor
alpar@209
   270
        RevArcIt() {}
alpar@209
   271
        /// Invalid constructor
alpar@209
   272
        RevArcIt(Invalid) {}
alpar@209
   273
        /// Constructor for first arc
alpar@209
   274
        RevArcIt(const PathDumper &) {}
alpar@96
   275
alpar@96
   276
        /// Conversion to Arc
alpar@209
   277
        operator Arc() const { return INVALID; }
alpar@96
   278
alpar@209
   279
        /// Next arc
alpar@209
   280
        RevArcIt& operator++() {return *this;}
alpar@96
   281
alpar@209
   282
        /// Comparison operator
alpar@209
   283
        bool operator==(const RevArcIt&) const {return true;}
alpar@209
   284
        /// Comparison operator
alpar@209
   285
        bool operator!=(const RevArcIt&) const {return true;}
kpeter@212
   286
        /// Comparison operator
kpeter@212
   287
        bool operator<(const RevArcIt&) const {return false;}
alpar@96
   288
alpar@96
   289
      };
alpar@96
   290
alpar@96
   291
      template <typename _Path>
alpar@96
   292
      struct Constraints {
alpar@96
   293
        void constraints() {
alpar@96
   294
          function_requires<_path_bits::
alpar@96
   295
            PathDumperConstraints<Digraph, _Path> >();
alpar@96
   296
        }
alpar@96
   297
      };
alpar@96
   298
alpar@96
   299
    };
alpar@96
   300
alpar@96
   301
alpar@96
   302
    ///@}
alpar@96
   303
  }
alpar@96
   304
alpar@96
   305
} // namespace lemon
alpar@96
   306
alpar@96
   307
#endif // LEMON_CONCEPT_PATH_H