alpar@2260: /* -*- C++ -*-
alpar@2260:  *
alpar@2260:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2260:  *
alpar@2260:  * Copyright (C) 2003-2006
alpar@2260:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2260:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2260:  *
alpar@2260:  * Permission to use, modify and distribute this software is granted
alpar@2260:  * provided that this copyright notice appears in all copies. For
alpar@2260:  * precise terms see the accompanying LICENSE file.
alpar@2260:  *
alpar@2260:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2260:  * express or implied, and with no claim as to its suitability for any
alpar@2260:  * purpose.
alpar@2260:  *
alpar@2260:  */
alpar@2260: 
alpar@2260: ///\ingroup concept
alpar@2260: ///\file
alpar@2260: ///\brief Classes for representing paths in graphs.
alpar@2260: ///
alpar@2260: ///\todo Iterators have obsolete style
alpar@2260: 
alpar@2260: #ifndef LEMON_CONCEPT_PATH_H
alpar@2260: #define LEMON_CONCEPT_PATH_H
alpar@2260: 
alpar@2260: #include <lemon/bits/invalid.h>
deba@2335: #include <lemon/bits/utility.h>
alpar@2260: #include <lemon/concept_check.h>
alpar@2260: 
alpar@2260: namespace lemon {
alpar@2260:   namespace concepts {
deba@2335: 
alpar@2260:     /// \addtogroup concept
alpar@2260:     /// @{
alpar@2260: 
deba@2335:     /// \brief A skeleton structure for representing directed paths in
deba@2335:     /// a graph.
deba@2335:     ///
deba@2335:     /// A skeleton structure for representing directed paths in a
deba@2335:     /// graph.  
deba@2335:     /// \param _Graph The graph type in which the path is.
deba@2335:     ///
deba@2335:     /// In a sense, the path can be treated as a list of edges. The
deba@2335:     /// lemon path type stores just this list. As a consequence it
deba@2335:     /// cannot enumerate the nodes in the path and the zero length
deba@2335:     /// paths cannot store the source.
deba@2335:     ///
deba@2335:     template <typename _Graph>
alpar@2260:     class Path {
alpar@2260:     public:
alpar@2260: 
alpar@2260:       /// Type of the underlying graph.
alpar@2260:       typedef _Graph Graph;
alpar@2260:       /// Edge type of the underlying graph.
alpar@2260:       typedef typename Graph::Edge Edge;
alpar@2260: 
alpar@2260:       class EdgeIt;
alpar@2260: 
deba@2335:       /// \brief Default constructor
deba@2335:       Path() {}
deba@2335: 
deba@2335:       /// \brief Template constructor
deba@2335:       template <typename CPath>
deba@2335:       Path(const CPath& cpath) {}
deba@2335: 
deba@2335:       /// \brief Template assigment
deba@2335:       template <typename CPath>
deba@2335:       Path& operator=(const CPath& cpath) {}
alpar@2260: 
alpar@2260:       /// Length of the path ie. the number of edges in the path.
deba@2335:       int length() const { return 0;}
alpar@2260: 
alpar@2260:       /// Returns whether the path is empty.
alpar@2260:       bool empty() const { return true;}
alpar@2260: 
alpar@2260:       /// Resets the path to an empty path.
alpar@2260:       void clear() {}
alpar@2260: 
deba@2335:       /// \brief Lemon style iterator for path edges
alpar@2260:       ///
deba@2335:       /// This class is used to iterate on the edges of the paths.
alpar@2260:       class EdgeIt {
alpar@2260:       public:
alpar@2260: 	/// Default constructor
alpar@2260: 	EdgeIt() {}
alpar@2260: 	/// Invalid constructor
alpar@2260: 	EdgeIt(Invalid) {}
deba@2335: 	/// Constructor for first edge
alpar@2260: 	EdgeIt(const Path &) {}
alpar@2260: 
deba@2335:         /// Conversion to Edge
alpar@2260: 	operator Edge() const { return INVALID; }
alpar@2260: 
alpar@2260: 	/// Next edge
alpar@2260: 	EdgeIt& operator++() {return *this;}
alpar@2260: 
alpar@2260: 	/// Comparison operator
alpar@2260: 	bool operator==(const EdgeIt&) const {return true;}
alpar@2260: 	/// Comparison operator
alpar@2260: 	bool operator!=(const EdgeIt&) const {return true;}
alpar@2260:  	/// Comparison operator
alpar@2260:  	bool operator<(const EdgeIt&) const {return false;}
alpar@2260: 
alpar@2260:       };
alpar@2260: 
deba@2335:       template <typename _Path>
deba@2335:       struct Constraints {
deba@2335:         void constraints() {
deba@2335:           Path<Graph> pc;
deba@2335:           _Path p, pp(pc);
deba@2335:           int l = p.length();
deba@2335:           int e = p.empty();
deba@2335:           p.clear();
alpar@2260: 
deba@2335:           p = pc;
alpar@2260: 
deba@2335:           typename _Path::EdgeIt id, ii(INVALID), i(p);
deba@2335: 
deba@2335:           ++i;
deba@2335:           typename Graph::Edge ed = i;
deba@2335: 
deba@2335:           e = (i == ii);
deba@2335:           e = (i != ii);
deba@2335:           e = (i < ii);
deba@2335: 
deba@2335:           ignore_unused_variable_warning(l);
deba@2335:           ignore_unused_variable_warning(pp);
deba@2335:           ignore_unused_variable_warning(e);
deba@2335:           ignore_unused_variable_warning(id);
deba@2335:           ignore_unused_variable_warning(ii);
deba@2335:           ignore_unused_variable_warning(ed);
deba@2335:         }
deba@2335:       };
deba@2335: 
deba@2335:     };
deba@2335: 
deba@2335:     namespace _path_bits {
deba@2335:       
deba@2335:       template <typename _Graph, typename _Path, typename RevPathTag = void>
deba@2335:       struct PathDumperConstraints {
deba@2335:         void constraints() {
deba@2335:           int l = p.length();
deba@2335:           int e = p.empty();
deba@2335: 
deba@2335:           typename _Path::EdgeIt id, ii(INVALID), i(p);
deba@2335: 
deba@2335:           ++i;
deba@2335:           typename _Graph::Edge ed = i;
deba@2335: 
deba@2335:           e = (i == ii);
deba@2335:           e = (i != ii);
deba@2335:           e = (i < ii);
deba@2335: 
deba@2335:           ignore_unused_variable_warning(l);
deba@2335:           ignore_unused_variable_warning(e);
deba@2335:           ignore_unused_variable_warning(id);
deba@2335:           ignore_unused_variable_warning(ii);
deba@2335:           ignore_unused_variable_warning(ed);
deba@2335:         }
deba@2335:         _Path& p;
deba@2335:       };
deba@2335: 
deba@2335:       template <typename _Graph, typename _Path>
deba@2335:       struct PathDumperConstraints<
deba@2335:         _Graph, _Path, 
deba@2335:         typename enable_if<typename _Path::RevPathTag, void>::type
deba@2335:       > {
deba@2335:         void constraints() {
deba@2335:           int l = p.length();
deba@2335:           int e = p.empty();
deba@2335: 
deba@2335:           typename _Path::RevIt id, ii(INVALID), i(p);
deba@2335: 
deba@2335:           ++i;
deba@2335:           typename _Graph::Edge ed = i;
deba@2335: 
deba@2335:           e = (i == ii);
deba@2335:           e = (i != ii);
deba@2335:           e = (i < ii);
deba@2335: 
deba@2335:           ignore_unused_variable_warning(l);
deba@2335:           ignore_unused_variable_warning(e);
deba@2335:           ignore_unused_variable_warning(id);
deba@2335:           ignore_unused_variable_warning(ii);
deba@2335:           ignore_unused_variable_warning(ed);
deba@2335:         }
deba@2335:         _Path& p;
deba@2335:       };
deba@2335:     
deba@2335:     }
deba@2335: 
deba@2335: 
deba@2335:     /// \brief A skeleton structure for path dumpers.
deba@2335:     ///
deba@2335:     /// A skeleton structure for path dumpers. The path dumpers are
deba@2335:     /// the generalization of the paths. The path dumpers can
deba@2335:     /// enumerate the edges of the path wheter in forward or in
deba@2335:     /// backward order.  In most time these classes are not used
deba@2335:     /// directly rather it used to assign a dumped class to a real
deba@2335:     /// path type.
deba@2335:     ///
deba@2335:     /// The main purpose of this concept is that the shortest path
deba@2335:     /// algorithms can enumerate easily the edges in reverse order.
deba@2335:     /// If we would like to give back a real path from these
deba@2335:     /// algorithms then we should create a temporarly path object. In
deba@2335:     /// Lemon such algorithms gives back a path dumper what can
deba@2335:     /// assigned to a real path and the dumpers can be implemented as
deba@2335:     /// an adaptor class to the predecessor map.
deba@2335: 
deba@2335:     /// \param _Graph  The graph type in which the path is.
deba@2335:     ///
deba@2335:     /// The paths can be constructed from any path type by a
deba@2335:     /// template constructor or a template assignment operator.
deba@2335:     /// 
deba@2335:     template <typename _Graph>
deba@2335:     class PathDumper {
deba@2335:     public:
deba@2335: 
deba@2335:       /// Type of the underlying graph.
deba@2335:       typedef _Graph Graph;
deba@2335:       /// Edge type of the underlying graph.
deba@2335:       typedef typename Graph::Edge Edge;
deba@2335: 
deba@2335:       /// Length of the path ie. the number of edges in the path.
deba@2335:       int length() const { return 0;}
deba@2335: 
deba@2335:       /// Returns whether the path is empty.
deba@2335:       bool empty() const { return true;}
deba@2335: 
deba@2335:       /// \brief Forward or reverse dumping
alpar@2260:       ///
deba@2335:       /// If the RevPathTag is defined and true then reverse dumping
deba@2335:       /// is provided in the path proxy. In this case instead of the
deba@2335:       /// EdgeIt the RevIt iterator should be implemented in the
deba@2335:       /// proxy.
deba@2335:       typedef False RevPathTag;
deba@2335: 
deba@2335:       /// \brief Lemon style iterator for path edges
alpar@2260:       ///
deba@2335:       /// This class is used to iterate on the edges of the paths.
deba@2335:       class EdgeIt {
deba@2335:       public:
deba@2335: 	/// Default constructor
deba@2335: 	EdgeIt() {}
deba@2335: 	/// Invalid constructor
deba@2335: 	EdgeIt(Invalid) {}
deba@2335: 	/// Constructor for first edge
deba@2335: 	EdgeIt(const PathDumper&) {}
deba@2335: 
deba@2335:         /// Conversion to Edge
deba@2335: 	operator Edge() const { return INVALID; }
deba@2335: 
deba@2335: 	/// Next edge
deba@2335: 	EdgeIt& operator++() {return *this;}
deba@2335: 
deba@2335: 	/// Comparison operator
deba@2335: 	bool operator==(const EdgeIt&) const {return true;}
deba@2335: 	/// Comparison operator
deba@2335: 	bool operator!=(const EdgeIt&) const {return true;}
deba@2335:  	/// Comparison operator
deba@2335:  	bool operator<(const EdgeIt&) const {return false;}
deba@2335: 
deba@2335:       };
deba@2335: 
deba@2335:       /// \brief Lemon style iterator for path edges
alpar@2260:       ///
deba@2335:       /// This class is used to iterate on the edges of the paths in
deba@2335:       /// reverse direction.
deba@2335:       class RevIt {
alpar@2260:       public:
deba@2335: 	/// Default constructor
deba@2335: 	RevIt() {}
deba@2335: 	/// Invalid constructor
deba@2335: 	RevIt(Invalid) {}
deba@2335: 	/// Constructor for first edge
deba@2335: 	RevIt(const PathDumper &) {}
alpar@2260: 
deba@2335:         /// Conversion to Edge
deba@2335: 	operator Edge() const { return INVALID; }
alpar@2260: 
deba@2335: 	/// Next edge
deba@2335: 	RevIt& operator++() {return *this;}
alpar@2260: 
deba@2335: 	/// Comparison operator
deba@2335: 	bool operator==(const RevIt&) const {return true;}
deba@2335: 	/// Comparison operator
deba@2335: 	bool operator!=(const RevIt&) const {return true;}
deba@2335:  	/// Comparison operator
deba@2335:  	bool operator<(const RevIt&) const {return false;}
alpar@2260: 
alpar@2260:       };
alpar@2260: 
alpar@2260:       template <typename _Path>
alpar@2260:       struct Constraints {
deba@2335:         void constraints() {
deba@2335:           function_requires<_path_bits::
deba@2335:             PathDumperConstraints<Graph, _Path> >();
deba@2335:         }
alpar@2260:       };
alpar@2260: 
alpar@2260:     };
alpar@2260: 
deba@2335: 
deba@2335:     ///@}
alpar@2260:   }
alpar@2260: 
alpar@2260: } // namespace lemon
alpar@2260: 
alpar@2260: #endif // LEMON_CONCEPT_PATH_H