lemon/concepts/path.h
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 09 Aug 2013 11:07:27 +0200
changeset 1090 70b199792735
parent 975 b873350e6258
child 1084 8b2d4e5d96e4
permissions -rw-r--r--
Clarification in biNodeConnected() doc (#439)
     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 Classes for representing paths in digraphs.
    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     /// \tparam GR 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 GR>
    49     class Path {
    50     public:
    51 
    52       /// Type of the underlying digraph.
    53       typedef GR 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         ::lemon::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           ::lemon::ignore_unused_variable_warning(l);
   130           ::lemon::ignore_unused_variable_warning(pp);
   131           ::lemon::ignore_unused_variable_warning(e);
   132           ::lemon::ignore_unused_variable_warning(id);
   133           ::lemon::ignore_unused_variable_warning(ii);
   134           ::lemon::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           ::lemon::ignore_unused_variable_warning(l);
   157           ::lemon::ignore_unused_variable_warning(e);
   158           ::lemon::ignore_unused_variable_warning(id);
   159           ::lemon::ignore_unused_variable_warning(ed);
   160         }
   161         _Path& p;
   162         PathDumperConstraints() {}
   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           ::lemon::ignore_unused_variable_warning(l);
   183           ::lemon::ignore_unused_variable_warning(e);
   184           ::lemon::ignore_unused_variable_warning(id);
   185           ::lemon::ignore_unused_variable_warning(ed);
   186         }
   187         _Path& p;
   188         PathDumperConstraints() {}
   189       };
   190 
   191     }
   192 
   193 
   194     /// \brief A skeleton structure for path dumpers.
   195     ///
   196     /// A skeleton structure for path dumpers. The path dumpers are
   197     /// the generalization of the paths. The path dumpers can
   198     /// enumerate the arcs of the path wheter in forward or in
   199     /// backward order.  In most time these classes are not used
   200     /// directly rather it used to assign a dumped class to a real
   201     /// path type.
   202     ///
   203     /// The main purpose of this concept is that the shortest path
   204     /// algorithms can enumerate easily the arcs in reverse order.
   205     /// If we would like to give back a real path from these
   206     /// algorithms then we should create a temporarly path object. In
   207     /// LEMON such algorithms gives back a path dumper what can
   208     /// assigned to a real path and the dumpers can be implemented as
   209     /// an adaptor class to the predecessor map.
   210     ///
   211     /// \tparam GR The digraph type in which the path is.
   212     ///
   213     /// The paths can be constructed from any path type by a
   214     /// template constructor or a template assignment operator.
   215     template <typename GR>
   216     class PathDumper {
   217     public:
   218 
   219       /// Type of the underlying digraph.
   220       typedef GR 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