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