lemon/concepts/path.h
author Balazs Dezso <deba@inf.elte.hu>
Fri, 17 Oct 2008 23:55:18 +0200
changeset 441 4f7224faf3bd
parent 280 e7f8647ce760
parent 278 931190050520
child 440 88ed40ad0d4f
permissions -rw-r--r--
Porting radix sorts from SVN #3509
     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-2008
     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 Classes for representing paths in digraphs.
    22 ///
    23 
    24 #ifndef LEMON_CONCEPT_PATH_H
    25 #define LEMON_CONCEPT_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     /// \tparam _Digraph The digraph type in which the path is.
    42     ///
    43     /// In a sense, the path can be treated as a list of arcs. The
    44     /// lemon path type stores just this list. As a consequence it
    45     /// cannot enumerate the nodes in the path and the zero length
    46     /// paths cannot store the source.
    47     ///
    48     template <typename _Digraph>
    49     class Path {
    50     public:
    51 
    52       /// Type of the underlying digraph.
    53       typedef _Digraph Digraph;
    54       /// Arc type of the underlying digraph.
    55       typedef typename Digraph::Arc Arc;
    56 
    57       class ArcIt;
    58 
    59       /// \brief Default constructor
    60       Path() {}
    61 
    62       /// \brief Template constructor
    63       template <typename CPath>
    64       Path(const CPath& cpath) {}
    65 
    66       /// \brief Template assigment
    67       template <typename CPath>
    68       Path& operator=(const CPath& cpath) {
    69         ignore_unused_variable_warning(cpath);
    70         return *this;
    71       }
    72 
    73       /// Length of the path ie. the number of arcs in the path.
    74       int length() const { return 0;}
    75 
    76       /// Returns whether the path is empty.
    77       bool empty() const { return true;}
    78 
    79       /// Resets the path to an empty path.
    80       void clear() {}
    81 
    82       /// \brief LEMON style iterator for path arcs
    83       ///
    84       /// This class is used to iterate on the arcs of the paths.
    85       class ArcIt {
    86       public:
    87         /// Default constructor
    88         ArcIt() {}
    89         /// Invalid constructor
    90         ArcIt(Invalid) {}
    91         /// Constructor for first arc
    92         ArcIt(const Path &) {}
    93 
    94         /// Conversion to Arc
    95         operator Arc() const { return INVALID; }
    96 
    97         /// Next arc
    98         ArcIt& operator++() {return *this;}
    99 
   100         /// Comparison operator
   101         bool operator==(const ArcIt&) const {return true;}
   102         /// Comparison operator
   103         bool operator!=(const ArcIt&) const {return true;}
   104         /// Comparison operator
   105         bool operator<(const ArcIt&) const {return false;}
   106 
   107       };
   108 
   109       template <typename _Path>
   110       struct Constraints {
   111         void constraints() {
   112           Path<Digraph> pc;
   113           _Path p, pp(pc);
   114           int l = p.length();
   115           int e = p.empty();
   116           p.clear();
   117 
   118           p = pc;
   119 
   120           typename _Path::ArcIt id, ii(INVALID), i(p);
   121 
   122           ++i;
   123           typename Digraph::Arc ed = i;
   124 
   125           e = (i == ii);
   126           e = (i != ii);
   127           e = (i < ii);
   128 
   129           ignore_unused_variable_warning(l);
   130           ignore_unused_variable_warning(pp);
   131           ignore_unused_variable_warning(e);
   132           ignore_unused_variable_warning(id);
   133           ignore_unused_variable_warning(ii);
   134           ignore_unused_variable_warning(ed);
   135         }
   136       };
   137 
   138     };
   139 
   140     namespace _path_bits {
   141 
   142       template <typename _Digraph, typename _Path, typename RevPathTag = void>
   143       struct PathDumperConstraints {
   144         void constraints() {
   145           int l = p.length();
   146           int e = p.empty();
   147 
   148           typename _Path::ArcIt id, i(p);
   149 
   150           ++i;
   151           typename _Digraph::Arc ed = i;
   152 
   153           e = (i == INVALID);
   154           e = (i != INVALID);
   155 
   156           ignore_unused_variable_warning(l);
   157           ignore_unused_variable_warning(e);
   158           ignore_unused_variable_warning(id);
   159           ignore_unused_variable_warning(ed);
   160         }
   161         _Path& p;
   162       };
   163 
   164       template <typename _Digraph, typename _Path>
   165       struct PathDumperConstraints<
   166         _Digraph, _Path,
   167         typename enable_if<typename _Path::RevPathTag, void>::type
   168       > {
   169         void constraints() {
   170           int l = p.length();
   171           int e = p.empty();
   172 
   173           typename _Path::RevArcIt id, i(p);
   174 
   175           ++i;
   176           typename _Digraph::Arc ed = i;
   177 
   178           e = (i == INVALID);
   179           e = (i != INVALID);
   180 
   181           ignore_unused_variable_warning(l);
   182           ignore_unused_variable_warning(e);
   183           ignore_unused_variable_warning(id);
   184           ignore_unused_variable_warning(ed);
   185         }
   186         _Path& p;
   187       };
   188 
   189     }
   190 
   191 
   192     /// \brief A skeleton structure for path dumpers.
   193     ///
   194     /// A skeleton structure for path dumpers. The path dumpers are
   195     /// the generalization of the paths. The path dumpers can
   196     /// enumerate the arcs of the path wheter in forward or in
   197     /// backward order.  In most time these classes are not used
   198     /// directly rather it used to assign a dumped class to a real
   199     /// path type.
   200     ///
   201     /// The main purpose of this concept is that the shortest path
   202     /// algorithms can enumerate easily the arcs in reverse order.
   203     /// If we would like to give back a real path from these
   204     /// algorithms then we should create a temporarly path object. In
   205     /// LEMON such algorithms gives back a path dumper what can
   206     /// assigned to a real path and the dumpers can be implemented as
   207     /// an adaptor class to the predecessor map.
   208 
   209     /// \tparam _Digraph  The digraph type in which the path is.
   210     ///
   211     /// The paths can be constructed from any path type by a
   212     /// template constructor or a template assignment operator.
   213     ///
   214     template <typename _Digraph>
   215     class PathDumper {
   216     public:
   217 
   218       /// Type of the underlying digraph.
   219       typedef _Digraph Digraph;
   220       /// Arc type of the underlying digraph.
   221       typedef typename Digraph::Arc Arc;
   222 
   223       /// Length of the path ie. the number of arcs in the path.
   224       int length() const { return 0;}
   225 
   226       /// Returns whether the path is empty.
   227       bool empty() const { return true;}
   228 
   229       /// \brief Forward or reverse dumping
   230       ///
   231       /// If the RevPathTag is defined and true then reverse dumping
   232       /// is provided in the path dumper. In this case instead of the
   233       /// ArcIt the RevArcIt iterator should be implemented in the
   234       /// dumper.
   235       typedef False RevPathTag;
   236 
   237       /// \brief LEMON style iterator for path arcs
   238       ///
   239       /// This class is used to iterate on the arcs of the paths.
   240       class ArcIt {
   241       public:
   242         /// Default constructor
   243         ArcIt() {}
   244         /// Invalid constructor
   245         ArcIt(Invalid) {}
   246         /// Constructor for first arc
   247         ArcIt(const PathDumper&) {}
   248 
   249         /// Conversion to Arc
   250         operator Arc() const { return INVALID; }
   251 
   252         /// Next arc
   253         ArcIt& operator++() {return *this;}
   254 
   255         /// Comparison operator
   256         bool operator==(const ArcIt&) const {return true;}
   257         /// Comparison operator
   258         bool operator!=(const ArcIt&) const {return true;}
   259         /// Comparison operator
   260         bool operator<(const ArcIt&) const {return false;}
   261 
   262       };
   263 
   264       /// \brief LEMON style iterator for path arcs
   265       ///
   266       /// This class is used to iterate on the arcs of the paths in
   267       /// reverse direction.
   268       class RevArcIt {
   269       public:
   270         /// Default constructor
   271         RevArcIt() {}
   272         /// Invalid constructor
   273         RevArcIt(Invalid) {}
   274         /// Constructor for first arc
   275         RevArcIt(const PathDumper &) {}
   276 
   277         /// Conversion to Arc
   278         operator Arc() const { return INVALID; }
   279 
   280         /// Next arc
   281         RevArcIt& operator++() {return *this;}
   282 
   283         /// Comparison operator
   284         bool operator==(const RevArcIt&) const {return true;}
   285         /// Comparison operator
   286         bool operator!=(const RevArcIt&) const {return true;}
   287         /// Comparison operator
   288         bool operator<(const RevArcIt&) const {return false;}
   289 
   290       };
   291 
   292       template <typename _Path>
   293       struct Constraints {
   294         void constraints() {
   295           function_requires<_path_bits::
   296             PathDumperConstraints<Digraph, _Path> >();
   297         }
   298       };
   299 
   300     };
   301 
   302 
   303     ///@}
   304   }
   305 
   306 } // namespace lemon
   307 
   308 #endif // LEMON_CONCEPT_PATH_H