lemon/concepts/path.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 01 Nov 2018 19:49:51 +0100
changeset 1417 2236d00ca778
parent 1336 0759d974de81
parent 1416 f179aa1045a4
permissions -rw-r--r--
Merge #615
     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-2013
     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 #include <lemon/bits/stl_iterators.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     /// In a sense, a path can be treated as a list of arcs.
    43     /// LEMON path types just store this list. As a consequence, they cannot
    44     /// enumerate the nodes on the path directly and a zero length path
    45     /// cannot store its source node.
    46     ///
    47     /// The arcs of a path should be stored in the order of their directions,
    48     /// i.e. the target node of each arc should be the same as the source
    49     /// node of the next arc. This consistency could be checked using
    50     /// \ref checkPath().
    51     /// The source and target nodes of a (consistent) path can be obtained
    52     /// using \ref pathSource() and \ref pathTarget().
    53     ///
    54     /// A path can be constructed from another path of any type using the
    55     /// copy constructor or the assignment operator.
    56     ///
    57     /// \tparam GR The digraph type in which the path is.
    58     template <typename GR>
    59     class Path {
    60     public:
    61 
    62       /// Type of the underlying digraph.
    63       typedef GR Digraph;
    64       /// Arc type of the underlying digraph.
    65       typedef typename Digraph::Arc Arc;
    66 
    67       class ArcIt;
    68 
    69       /// \brief Default constructor
    70       Path() {}
    71 
    72       /// \brief Template copy constructor
    73       template <typename CPath>
    74       Path(const CPath& cpath) {
    75         ::lemon::ignore_unused_variable_warning(cpath);
    76       }
    77 
    78       /// \brief Template assigment operator
    79       template <typename CPath>
    80       Path& operator=(const CPath& cpath) {
    81         ::lemon::ignore_unused_variable_warning(cpath);
    82         return *this;
    83       }
    84 
    85       /// Length of the path, i.e. the number of arcs on the path.
    86       int length() const { return 0;}
    87 
    88       /// Returns whether the path is empty.
    89       bool empty() const { return true;}
    90 
    91       /// Resets the path to an empty path.
    92       void clear() {}
    93 
    94       /// \brief LEMON style iterator for enumerating the arcs of a path.
    95       ///
    96       /// LEMON style iterator class for enumerating the arcs of a path.
    97       class ArcIt {
    98       public:
    99         /// Default constructor
   100         ArcIt() {}
   101         /// Invalid constructor
   102         ArcIt(Invalid) {}
   103         /// Sets the iterator to the first arc of the given path
   104         ArcIt(const Path &) {}
   105 
   106         /// Conversion to \c Arc
   107         operator Arc() const { return INVALID; }
   108 
   109         /// Next arc
   110         ArcIt& operator++() {return *this;}
   111 
   112         /// Comparison operator
   113         bool operator==(const ArcIt&) const {return true;}
   114         /// Comparison operator
   115         bool operator!=(const ArcIt&) const {return true;}
   116         /// Comparison operator
   117         bool operator<(const ArcIt&) const {return false;}
   118 
   119       };
   120 
   121       /// \brief Gets the collection of the arcs of the path.
   122       ///
   123       /// This function can be used for iterating on the
   124       /// arcs of the path. It returns a wrapped
   125       /// ArcIt, which looks like an STL container
   126       /// (by having begin() and end()) which you can use in range-based
   127       /// for loops, STL algorithms, etc.
   128       /// For example you can write:
   129       ///\code
   130       /// for(auto a: p.arcs())
   131       ///   doSomething(a);
   132       ///\endcode
   133       LemonRangeWrapper1<ArcIt, Path> arcs() const {
   134         return LemonRangeWrapper1<ArcIt, Path>(*this);
   135       }
   136 
   137 
   138       template <typename _Path>
   139       struct Constraints {
   140         void constraints() {
   141           Path<Digraph> pc;
   142           _Path p, pp(pc);
   143           int l = p.length();
   144           int e = p.empty();
   145           p.clear();
   146 
   147           p = pc;
   148 
   149           typename _Path::ArcIt id, ii(INVALID), i(p);
   150 
   151           ++i;
   152           typename Digraph::Arc ed = i;
   153 
   154           e = (i == ii);
   155           e = (i != ii);
   156           e = (i < ii);
   157 
   158           ::lemon::ignore_unused_variable_warning(l);
   159           ::lemon::ignore_unused_variable_warning(pp);
   160           ::lemon::ignore_unused_variable_warning(e);
   161           ::lemon::ignore_unused_variable_warning(id);
   162           ::lemon::ignore_unused_variable_warning(ii);
   163           ::lemon::ignore_unused_variable_warning(ed);
   164         }
   165       };
   166 
   167     };
   168 
   169     namespace _path_bits {
   170 
   171       template <typename _Digraph, typename _Path, typename RevPathTag = void>
   172       struct PathDumperConstraints {
   173         void constraints() {
   174           int l = p.length();
   175           int e = p.empty();
   176 
   177           typename _Path::ArcIt id, i(p);
   178 
   179           ++i;
   180           typename _Digraph::Arc ed = i;
   181 
   182           e = (i == INVALID);
   183           e = (i != INVALID);
   184 
   185           ::lemon::ignore_unused_variable_warning(l);
   186           ::lemon::ignore_unused_variable_warning(e);
   187           ::lemon::ignore_unused_variable_warning(id);
   188           ::lemon::ignore_unused_variable_warning(ed);
   189         }
   190         _Path& p;
   191         PathDumperConstraints() {}
   192       };
   193 
   194       template <typename _Digraph, typename _Path>
   195       struct PathDumperConstraints<
   196         _Digraph, _Path,
   197         typename enable_if<typename _Path::RevPathTag, void>::type
   198       > {
   199         void constraints() {
   200           int l = p.length();
   201           int e = p.empty();
   202 
   203           typename _Path::RevArcIt id, i(p);
   204 
   205           ++i;
   206           typename _Digraph::Arc ed = i;
   207 
   208           e = (i == INVALID);
   209           e = (i != INVALID);
   210 
   211           ::lemon::ignore_unused_variable_warning(l);
   212           ::lemon::ignore_unused_variable_warning(e);
   213           ::lemon::ignore_unused_variable_warning(id);
   214           ::lemon::ignore_unused_variable_warning(ed);
   215         }
   216         _Path& p;
   217         PathDumperConstraints() {}
   218       };
   219 
   220     }
   221 
   222 
   223     /// \brief A skeleton structure for path dumpers.
   224     ///
   225     /// A skeleton structure for path dumpers. The path dumpers are
   226     /// the generalization of the paths, they can enumerate the arcs
   227     /// of the path either in forward or in backward order.
   228     /// These classes are typically not used directly, they are rather
   229     /// used to be assigned to a real path type.
   230     ///
   231     /// The main purpose of this concept is that the shortest path
   232     /// algorithms can enumerate the arcs easily in reverse order.
   233     /// In LEMON, such algorithms give back a (reverse) path dumper that
   234     /// can be assigned to a real path. The dumpers can be implemented as
   235     /// an adaptor class to the predecessor map.
   236     ///
   237     /// \tparam GR The digraph type in which the path is.
   238     template <typename GR>
   239     class PathDumper {
   240     public:
   241 
   242       /// Type of the underlying digraph.
   243       typedef GR Digraph;
   244       /// Arc type of the underlying digraph.
   245       typedef typename Digraph::Arc Arc;
   246 
   247       /// Length of the path, i.e. the number of arcs on the path.
   248       int length() const { return 0;}
   249 
   250       /// Returns whether the path is empty.
   251       bool empty() const { return true;}
   252 
   253       /// \brief Forward or reverse dumping
   254       ///
   255       /// If this tag is defined to be \c True, then reverse dumping
   256       /// is provided in the path dumper. In this case, \c RevArcIt
   257       /// iterator should be implemented instead of \c ArcIt iterator.
   258       typedef False RevPathTag;
   259 
   260       /// \brief LEMON style iterator for enumerating the arcs of a path.
   261       ///
   262       /// LEMON style iterator class for enumerating the arcs of a path.
   263       class ArcIt {
   264       public:
   265         /// Default constructor
   266         ArcIt() {}
   267         /// Invalid constructor
   268         ArcIt(Invalid) {}
   269         /// Sets the iterator to the first arc of the given path
   270         ArcIt(const PathDumper&) {}
   271 
   272         /// Conversion to \c Arc
   273         operator Arc() const { return INVALID; }
   274 
   275         /// Next arc
   276         ArcIt& operator++() {return *this;}
   277 
   278         /// Comparison operator
   279         bool operator==(const ArcIt&) const {return true;}
   280         /// Comparison operator
   281         bool operator!=(const ArcIt&) const {return true;}
   282         /// Comparison operator
   283         bool operator<(const ArcIt&) const {return false;}
   284 
   285       };
   286 
   287       /// \brief Gets the collection of the arcs of the path.
   288       ///
   289       /// This function can be used for iterating on the
   290       /// arcs of the path. It returns a wrapped
   291       /// ArcIt, which looks like an STL container
   292       /// (by having begin() and end()) which you can use in range-based
   293       /// for loops, STL algorithms, etc.
   294       /// For example you can write:
   295       ///\code
   296       /// for(auto a: p.arcs())
   297       ///   doSomething(a);
   298       ///\endcode
   299       LemonRangeWrapper1<ArcIt, PathDumper> arcs() const {
   300         return LemonRangeWrapper1<ArcIt, PathDumper>(*this);
   301       }
   302 
   303 
   304       /// \brief LEMON style iterator for enumerating the arcs of a path
   305       /// in reverse direction.
   306       ///
   307       /// LEMON style iterator class for enumerating the arcs of a path
   308       /// in reverse direction.
   309       class RevArcIt {
   310       public:
   311         /// Default constructor
   312         RevArcIt() {}
   313         /// Invalid constructor
   314         RevArcIt(Invalid) {}
   315         /// Sets the iterator to the last arc of the given path
   316         RevArcIt(const PathDumper &) {}
   317 
   318         /// Conversion to \c Arc
   319         operator Arc() const { return INVALID; }
   320 
   321         /// Next arc
   322         RevArcIt& operator++() {return *this;}
   323 
   324         /// Comparison operator
   325         bool operator==(const RevArcIt&) const {return true;}
   326         /// Comparison operator
   327         bool operator!=(const RevArcIt&) const {return true;}
   328         /// Comparison operator
   329         bool operator<(const RevArcIt&) const {return false;}
   330 
   331       };
   332 
   333       /// \brief Gets the collection of the arcs of the path
   334       /// in reverse direction.
   335       ///
   336       /// This function can be used for iterating on the
   337       /// arcs of the path in reverse direction. It returns a wrapped
   338       /// RevArcIt, which looks like an STL container
   339       /// (by having begin() and end()) which you can use in range-based
   340       /// for loops, STL algorithms, etc.
   341       /// For example you can write:
   342       ///\code
   343       /// for(auto a: p.revArcs())
   344       ///   doSomething(a);
   345       ///\endcode
   346       LemonRangeWrapper1<RevArcIt, PathDumper> revArcs() const {
   347         return LemonRangeWrapper1<RevArcIt, PathDumper>(*this);
   348       }
   349 
   350 
   351       template <typename _Path>
   352       struct Constraints {
   353         void constraints() {
   354           function_requires<_path_bits::
   355             PathDumperConstraints<Digraph, _Path> >();
   356         }
   357       };
   358 
   359     };
   360 
   361 
   362     ///@}
   363   }
   364 
   365 } // namespace lemon
   366 
   367 #endif