alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@96:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@96:  *
alpar@440:  * Copyright (C) 2003-2009
alpar@96:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@96:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@96:  *
alpar@96:  * Permission to use, modify and distribute this software is granted
alpar@96:  * provided that this copyright notice appears in all copies. For
alpar@96:  * precise terms see the accompanying LICENSE file.
alpar@96:  *
alpar@96:  * This software is provided "AS IS" with no warranty of any kind,
alpar@96:  * express or implied, and with no claim as to its suitability for any
alpar@96:  * purpose.
alpar@96:  *
alpar@96:  */
alpar@96: 
alpar@96: ///\ingroup concept
alpar@96: ///\file
kpeter@785: ///\brief The concept of paths
alpar@96: ///
alpar@96: 
deba@529: #ifndef LEMON_CONCEPTS_PATH_H
deba@529: #define LEMON_CONCEPTS_PATH_H
alpar@96: 
deba@220: #include <lemon/core.h>
alpar@96: #include <lemon/concept_check.h>
alpar@96: 
alpar@96: namespace lemon {
alpar@96:   namespace concepts {
alpar@96: 
alpar@96:     /// \addtogroup concept
alpar@96:     /// @{
alpar@96: 
alpar@96:     /// \brief A skeleton structure for representing directed paths in
alpar@96:     /// a digraph.
alpar@96:     ///
alpar@96:     /// A skeleton structure for representing directed paths in a
alpar@209:     /// digraph.
kpeter@785:     /// In a sense, a path can be treated as a list of arcs.
kpeter@785:     /// LEMON path types just store this list. As a consequence, they cannot
kpeter@785:     /// enumerate the nodes on the path directly and a zero length path
kpeter@785:     /// cannot store its source node.
kpeter@785:     ///
kpeter@785:     /// The arcs of a path should be stored in the order of their directions,
kpeter@785:     /// i.e. the target node of each arc should be the same as the source
kpeter@785:     /// node of the next arc. This consistency could be checked using
kpeter@785:     /// \ref checkPath().
kpeter@785:     /// The source and target nodes of a (consistent) path can be obtained
kpeter@785:     /// using \ref pathSource() and \ref pathTarget().
kpeter@785:     ///
kpeter@785:     /// A path can be constructed from another path of any type using the
kpeter@785:     /// copy constructor or the assignment operator.
kpeter@785:     ///
kpeter@559:     /// \tparam GR The digraph type in which the path is.
kpeter@559:     template <typename GR>
alpar@96:     class Path {
alpar@96:     public:
alpar@96: 
alpar@96:       /// Type of the underlying digraph.
kpeter@559:       typedef GR Digraph;
alpar@96:       /// Arc type of the underlying digraph.
alpar@96:       typedef typename Digraph::Arc Arc;
alpar@96: 
alpar@96:       class ArcIt;
alpar@96: 
alpar@96:       /// \brief Default constructor
alpar@96:       Path() {}
alpar@96: 
kpeter@785:       /// \brief Template copy constructor
alpar@96:       template <typename CPath>
alpar@96:       Path(const CPath& cpath) {}
alpar@96: 
kpeter@785:       /// \brief Template assigment operator
alpar@96:       template <typename CPath>
kpeter@278:       Path& operator=(const CPath& cpath) {
alpar@982:         ::lemon::ignore_unused_variable_warning(cpath);
kpeter@278:         return *this;
kpeter@278:       }
alpar@96: 
kpeter@785:       /// Length of the path, i.e. the number of arcs on the path.
alpar@96:       int length() const { return 0;}
alpar@96: 
alpar@96:       /// Returns whether the path is empty.
alpar@96:       bool empty() const { return true;}
alpar@96: 
alpar@96:       /// Resets the path to an empty path.
alpar@96:       void clear() {}
alpar@96: 
kpeter@785:       /// \brief LEMON style iterator for enumerating the arcs of a path.
alpar@96:       ///
kpeter@785:       /// LEMON style iterator class for enumerating the arcs of a path.
alpar@96:       class ArcIt {
alpar@96:       public:
alpar@209:         /// Default constructor
alpar@209:         ArcIt() {}
alpar@209:         /// Invalid constructor
alpar@209:         ArcIt(Invalid) {}
kpeter@785:         /// Sets the iterator to the first arc of the given path
alpar@209:         ArcIt(const Path &) {}
alpar@96: 
kpeter@785:         /// Conversion to \c Arc
alpar@209:         operator Arc() const { return INVALID; }
alpar@96: 
alpar@209:         /// Next arc
alpar@209:         ArcIt& operator++() {return *this;}
alpar@96: 
alpar@209:         /// Comparison operator
alpar@209:         bool operator==(const ArcIt&) const {return true;}
alpar@209:         /// Comparison operator
alpar@209:         bool operator!=(const ArcIt&) const {return true;}
kpeter@212:         /// Comparison operator
kpeter@212:         bool operator<(const ArcIt&) const {return false;}
alpar@96: 
alpar@96:       };
alpar@96: 
alpar@96:       template <typename _Path>
alpar@96:       struct Constraints {
alpar@96:         void constraints() {
alpar@96:           Path<Digraph> pc;
alpar@96:           _Path p, pp(pc);
alpar@96:           int l = p.length();
alpar@96:           int e = p.empty();
alpar@96:           p.clear();
alpar@96: 
alpar@96:           p = pc;
alpar@96: 
alpar@96:           typename _Path::ArcIt id, ii(INVALID), i(p);
alpar@96: 
alpar@96:           ++i;
alpar@96:           typename Digraph::Arc ed = i;
alpar@96: 
alpar@96:           e = (i == ii);
alpar@96:           e = (i != ii);
alpar@96:           e = (i < ii);
alpar@96: 
alpar@982:           ::lemon::ignore_unused_variable_warning(l);
alpar@982:           ::lemon::ignore_unused_variable_warning(pp);
alpar@982:           ::lemon::ignore_unused_variable_warning(e);
alpar@982:           ::lemon::ignore_unused_variable_warning(id);
alpar@982:           ::lemon::ignore_unused_variable_warning(ii);
alpar@982:           ::lemon::ignore_unused_variable_warning(ed);
alpar@96:         }
alpar@96:       };
alpar@96: 
alpar@96:     };
alpar@96: 
alpar@96:     namespace _path_bits {
alpar@209: 
alpar@96:       template <typename _Digraph, typename _Path, typename RevPathTag = void>
alpar@96:       struct PathDumperConstraints {
alpar@96:         void constraints() {
alpar@96:           int l = p.length();
alpar@96:           int e = p.empty();
alpar@96: 
alpar@96:           typename _Path::ArcIt id, i(p);
alpar@96: 
alpar@96:           ++i;
alpar@96:           typename _Digraph::Arc ed = i;
alpar@96: 
alpar@96:           e = (i == INVALID);
alpar@96:           e = (i != INVALID);
alpar@96: 
alpar@982:           ::lemon::ignore_unused_variable_warning(l);
alpar@982:           ::lemon::ignore_unused_variable_warning(e);
alpar@982:           ::lemon::ignore_unused_variable_warning(id);
alpar@982:           ::lemon::ignore_unused_variable_warning(ed);
alpar@96:         }
alpar@96:         _Path& p;
alpar@953:         PathDumperConstraints() {}
alpar@96:       };
alpar@96: 
alpar@96:       template <typename _Digraph, typename _Path>
alpar@96:       struct PathDumperConstraints<
alpar@209:         _Digraph, _Path,
alpar@96:         typename enable_if<typename _Path::RevPathTag, void>::type
alpar@96:       > {
alpar@96:         void constraints() {
alpar@96:           int l = p.length();
alpar@96:           int e = p.empty();
alpar@96: 
alpar@96:           typename _Path::RevArcIt id, i(p);
alpar@96: 
alpar@96:           ++i;
alpar@96:           typename _Digraph::Arc ed = i;
alpar@96: 
alpar@96:           e = (i == INVALID);
alpar@96:           e = (i != INVALID);
alpar@96: 
alpar@982:           ::lemon::ignore_unused_variable_warning(l);
alpar@982:           ::lemon::ignore_unused_variable_warning(e);
alpar@982:           ::lemon::ignore_unused_variable_warning(id);
alpar@982:           ::lemon::ignore_unused_variable_warning(ed);
alpar@96:         }
alpar@96:         _Path& p;
alpar@953:         PathDumperConstraints() {}
alpar@96:       };
alpar@209: 
alpar@96:     }
alpar@96: 
alpar@96: 
alpar@96:     /// \brief A skeleton structure for path dumpers.
alpar@96:     ///
alpar@96:     /// A skeleton structure for path dumpers. The path dumpers are
kpeter@785:     /// the generalization of the paths, they can enumerate the arcs
kpeter@785:     /// of the path either in forward or in backward order.
kpeter@785:     /// These classes are typically not used directly, they are rather
kpeter@785:     /// used to be assigned to a real path type.
alpar@96:     ///
alpar@96:     /// The main purpose of this concept is that the shortest path
kpeter@785:     /// algorithms can enumerate the arcs easily in reverse order.
kpeter@785:     /// In LEMON, such algorithms give back a (reverse) path dumper that
kpeter@785:     /// can be assigned to a real path. The dumpers can be implemented as
alpar@96:     /// an adaptor class to the predecessor map.
kpeter@559:     ///
kpeter@559:     /// \tparam GR The digraph type in which the path is.
kpeter@559:     template <typename GR>
alpar@96:     class PathDumper {
alpar@96:     public:
alpar@96: 
alpar@96:       /// Type of the underlying digraph.
kpeter@559:       typedef GR Digraph;
alpar@96:       /// Arc type of the underlying digraph.
alpar@96:       typedef typename Digraph::Arc Arc;
alpar@96: 
kpeter@785:       /// Length of the path, i.e. the number of arcs on the path.
alpar@96:       int length() const { return 0;}
alpar@96: 
alpar@96:       /// Returns whether the path is empty.
alpar@96:       bool empty() const { return true;}
alpar@96: 
alpar@96:       /// \brief Forward or reverse dumping
alpar@96:       ///
kpeter@785:       /// If this tag is defined to be \c True, then reverse dumping
kpeter@785:       /// is provided in the path dumper. In this case, \c RevArcIt
kpeter@785:       /// iterator should be implemented instead of \c ArcIt iterator.
alpar@96:       typedef False RevPathTag;
alpar@96: 
kpeter@785:       /// \brief LEMON style iterator for enumerating the arcs of a path.
alpar@96:       ///
kpeter@785:       /// LEMON style iterator class for enumerating the arcs of a path.
alpar@96:       class ArcIt {
alpar@96:       public:
alpar@209:         /// Default constructor
alpar@209:         ArcIt() {}
alpar@209:         /// Invalid constructor
alpar@209:         ArcIt(Invalid) {}
kpeter@785:         /// Sets the iterator to the first arc of the given path
alpar@209:         ArcIt(const PathDumper&) {}
alpar@96: 
kpeter@785:         /// Conversion to \c Arc
alpar@209:         operator Arc() const { return INVALID; }
alpar@96: 
alpar@209:         /// Next arc
alpar@209:         ArcIt& operator++() {return *this;}
alpar@96: 
alpar@209:         /// Comparison operator
alpar@209:         bool operator==(const ArcIt&) const {return true;}
alpar@209:         /// Comparison operator
alpar@209:         bool operator!=(const ArcIt&) const {return true;}
kpeter@212:         /// Comparison operator
kpeter@212:         bool operator<(const ArcIt&) const {return false;}
alpar@96: 
alpar@96:       };
alpar@96: 
kpeter@785:       /// \brief LEMON style iterator for enumerating the arcs of a path
kpeter@785:       /// in reverse direction.
alpar@96:       ///
kpeter@785:       /// LEMON style iterator class for enumerating the arcs of a path
kpeter@785:       /// in reverse direction.
alpar@96:       class RevArcIt {
alpar@96:       public:
alpar@209:         /// Default constructor
alpar@209:         RevArcIt() {}
alpar@209:         /// Invalid constructor
alpar@209:         RevArcIt(Invalid) {}
kpeter@785:         /// Sets the iterator to the last arc of the given path
alpar@209:         RevArcIt(const PathDumper &) {}
alpar@96: 
kpeter@785:         /// Conversion to \c Arc
alpar@209:         operator Arc() const { return INVALID; }
alpar@96: 
alpar@209:         /// Next arc
alpar@209:         RevArcIt& operator++() {return *this;}
alpar@96: 
alpar@209:         /// Comparison operator
alpar@209:         bool operator==(const RevArcIt&) const {return true;}
alpar@209:         /// Comparison operator
alpar@209:         bool operator!=(const RevArcIt&) const {return true;}
kpeter@212:         /// Comparison operator
kpeter@212:         bool operator<(const RevArcIt&) const {return false;}
alpar@96: 
alpar@96:       };
alpar@96: 
alpar@96:       template <typename _Path>
alpar@96:       struct Constraints {
alpar@96:         void constraints() {
alpar@96:           function_requires<_path_bits::
alpar@96:             PathDumperConstraints<Digraph, _Path> >();
alpar@96:         }
alpar@96:       };
alpar@96: 
alpar@96:     };
alpar@96: 
alpar@96: 
alpar@96:     ///@}
alpar@96:   }
alpar@96: 
alpar@96: } // namespace lemon
alpar@96: 
deba@529: #endif