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