lemon/concepts/path.h
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 28 Feb 2011 10:19:34 +0100
changeset 924 a80381c43760
parent 559 c5fd2d996909
child 976 426a704d7483
permissions -rw-r--r--
Merge bugfix #414
     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-2009
     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 
    75       /// \brief Template assigment operator
    76       template <typename CPath>
    77       Path& operator=(const CPath& cpath) {
    78         ignore_unused_variable_warning(cpath);
    79         return *this;
    80       }
    81 
    82       /// Length of the path, i.e. the number of arcs on the path.
    83       int length() const { return 0;}
    84 
    85       /// Returns whether the path is empty.
    86       bool empty() const { return true;}
    87 
    88       /// Resets the path to an empty path.
    89       void clear() {}
    90 
    91       /// \brief LEMON style iterator for enumerating the arcs of a path.
    92       ///
    93       /// LEMON style iterator class for enumerating the arcs of a path.
    94       class ArcIt {
    95       public:
    96         /// Default constructor
    97         ArcIt() {}
    98         /// Invalid constructor
    99         ArcIt(Invalid) {}
   100         /// Sets the iterator to the first arc of the given path
   101         ArcIt(const Path &) {}
   102 
   103         /// Conversion to \c Arc
   104         operator Arc() const { return INVALID; }
   105 
   106         /// Next arc
   107         ArcIt& operator++() {return *this;}
   108 
   109         /// Comparison operator
   110         bool operator==(const ArcIt&) const {return true;}
   111         /// Comparison operator
   112         bool operator!=(const ArcIt&) const {return true;}
   113         /// Comparison operator
   114         bool operator<(const ArcIt&) const {return false;}
   115 
   116       };
   117 
   118       template <typename _Path>
   119       struct Constraints {
   120         void constraints() {
   121           Path<Digraph> pc;
   122           _Path p, pp(pc);
   123           int l = p.length();
   124           int e = p.empty();
   125           p.clear();
   126 
   127           p = pc;
   128 
   129           typename _Path::ArcIt id, ii(INVALID), i(p);
   130 
   131           ++i;
   132           typename Digraph::Arc ed = i;
   133 
   134           e = (i == ii);
   135           e = (i != ii);
   136           e = (i < ii);
   137 
   138           ignore_unused_variable_warning(l);
   139           ignore_unused_variable_warning(pp);
   140           ignore_unused_variable_warning(e);
   141           ignore_unused_variable_warning(id);
   142           ignore_unused_variable_warning(ii);
   143           ignore_unused_variable_warning(ed);
   144         }
   145       };
   146 
   147     };
   148 
   149     namespace _path_bits {
   150 
   151       template <typename _Digraph, typename _Path, typename RevPathTag = void>
   152       struct PathDumperConstraints {
   153         void constraints() {
   154           int l = p.length();
   155           int e = p.empty();
   156 
   157           typename _Path::ArcIt id, i(p);
   158 
   159           ++i;
   160           typename _Digraph::Arc ed = i;
   161 
   162           e = (i == INVALID);
   163           e = (i != INVALID);
   164 
   165           ignore_unused_variable_warning(l);
   166           ignore_unused_variable_warning(e);
   167           ignore_unused_variable_warning(id);
   168           ignore_unused_variable_warning(ed);
   169         }
   170         _Path& p;
   171       };
   172 
   173       template <typename _Digraph, typename _Path>
   174       struct PathDumperConstraints<
   175         _Digraph, _Path,
   176         typename enable_if<typename _Path::RevPathTag, void>::type
   177       > {
   178         void constraints() {
   179           int l = p.length();
   180           int e = p.empty();
   181 
   182           typename _Path::RevArcIt id, i(p);
   183 
   184           ++i;
   185           typename _Digraph::Arc ed = i;
   186 
   187           e = (i == INVALID);
   188           e = (i != INVALID);
   189 
   190           ignore_unused_variable_warning(l);
   191           ignore_unused_variable_warning(e);
   192           ignore_unused_variable_warning(id);
   193           ignore_unused_variable_warning(ed);
   194         }
   195         _Path& p;
   196       };
   197 
   198     }
   199 
   200 
   201     /// \brief A skeleton structure for path dumpers.
   202     ///
   203     /// A skeleton structure for path dumpers. The path dumpers are
   204     /// the generalization of the paths, they can enumerate the arcs
   205     /// of the path either in forward or in backward order.
   206     /// These classes are typically not used directly, they are rather
   207     /// used to be assigned to a real path type.
   208     ///
   209     /// The main purpose of this concept is that the shortest path
   210     /// algorithms can enumerate the arcs easily in reverse order.
   211     /// In LEMON, such algorithms give back a (reverse) path dumper that
   212     /// can be assigned to a real path. The dumpers can be implemented as
   213     /// an adaptor class to the predecessor map.
   214     ///
   215     /// \tparam GR The digraph type in which the path is.
   216     template <typename GR>
   217     class PathDumper {
   218     public:
   219 
   220       /// Type of the underlying digraph.
   221       typedef GR Digraph;
   222       /// Arc type of the underlying digraph.
   223       typedef typename Digraph::Arc Arc;
   224 
   225       /// Length of the path, i.e. the number of arcs on the path.
   226       int length() const { return 0;}
   227 
   228       /// Returns whether the path is empty.
   229       bool empty() const { return true;}
   230 
   231       /// \brief Forward or reverse dumping
   232       ///
   233       /// If this tag is defined to be \c True, then reverse dumping
   234       /// is provided in the path dumper. In this case, \c RevArcIt
   235       /// iterator should be implemented instead of \c ArcIt iterator.
   236       typedef False RevPathTag;
   237 
   238       /// \brief LEMON style iterator for enumerating the arcs of a path.
   239       ///
   240       /// LEMON style iterator class for enumerating the arcs of a path.
   241       class ArcIt {
   242       public:
   243         /// Default constructor
   244         ArcIt() {}
   245         /// Invalid constructor
   246         ArcIt(Invalid) {}
   247         /// Sets the iterator to the first arc of the given path
   248         ArcIt(const PathDumper&) {}
   249 
   250         /// Conversion to \c Arc
   251         operator Arc() const { return INVALID; }
   252 
   253         /// Next arc
   254         ArcIt& operator++() {return *this;}
   255 
   256         /// Comparison operator
   257         bool operator==(const ArcIt&) const {return true;}
   258         /// Comparison operator
   259         bool operator!=(const ArcIt&) const {return true;}
   260         /// Comparison operator
   261         bool operator<(const ArcIt&) const {return false;}
   262 
   263       };
   264 
   265       /// \brief LEMON style iterator for enumerating the arcs of a path
   266       /// in reverse direction.
   267       ///
   268       /// LEMON style iterator class for enumerating the arcs of a path
   269       /// in reverse direction.
   270       class RevArcIt {
   271       public:
   272         /// Default constructor
   273         RevArcIt() {}
   274         /// Invalid constructor
   275         RevArcIt(Invalid) {}
   276         /// Sets the iterator to the last arc of the given path
   277         RevArcIt(const PathDumper &) {}
   278 
   279         /// Conversion to \c Arc
   280         operator Arc() const { return INVALID; }
   281 
   282         /// Next arc
   283         RevArcIt& operator++() {return *this;}
   284 
   285         /// Comparison operator
   286         bool operator==(const RevArcIt&) const {return true;}
   287         /// Comparison operator
   288         bool operator!=(const RevArcIt&) const {return true;}
   289         /// Comparison operator
   290         bool operator<(const RevArcIt&) const {return false;}
   291 
   292       };
   293 
   294       template <typename _Path>
   295       struct Constraints {
   296         void constraints() {
   297           function_requires<_path_bits::
   298             PathDumperConstraints<Digraph, _Path> >();
   299         }
   300       };
   301 
   302     };
   303 
   304 
   305     ///@}
   306   }
   307 
   308 } // namespace lemon
   309 
   310 #endif