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>
alpar@2260: #include <lemon/concept_check.h>
alpar@2260: 
alpar@2260: namespace lemon {
alpar@2260:   namespace concepts {
alpar@2260:     /// \addtogroup concept
alpar@2260:     /// @{
alpar@2260: 
alpar@2260: 
alpar@2260:     //! \brief A skeleton structure for representing directed paths in a graph.
alpar@2260:     //!
alpar@2260:     //! A skeleton structure for representing directed paths in a graph.
alpar@2260:     //! \param _Graph The graph type in which the path is.
alpar@2260:     //!
alpar@2260:     //! In a sense, the path can be treated as a graph, for it has \c NodeIt
alpar@2260:     //! and \c EdgeIt with the same usage. These types converts to the \c Node
alpar@2260:     //! and \c Edge of the original graph.
alpar@2260:     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:       /// Node type of the underlying graph.
alpar@2260:       typedef typename Graph::Node Node;
alpar@2260: 
alpar@2260:       class NodeIt;
alpar@2260:       class EdgeIt;
alpar@2260: 
alpar@2260:       /// \param _g The graph in which the path is.
alpar@2260:       ///
alpar@2260:       Path(const Graph &_g) {
alpar@2260: 	ignore_unused_variable_warning(_g);
alpar@2260:       }
alpar@2260: 
alpar@2260:       /// Length of the path ie. the number of edges in the path.
alpar@2260:       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: 
alpar@2260:       /// \brief Starting point of the path.
alpar@2260:       ///
alpar@2260:       /// Starting point of the path.
alpar@2260:       /// Returns INVALID if the path is empty.
alpar@2260:       Node target() const {return INVALID;}
alpar@2260:       /// \brief End point of the path.
alpar@2260:       ///
alpar@2260:       /// End point of the path.
alpar@2260:       /// Returns INVALID if the path is empty.
alpar@2260:       Node source() const {return INVALID;}
alpar@2260: 
alpar@2260:       /// \brief The target of an edge.
alpar@2260:       ///
alpar@2260:       /// Returns node iterator pointing to the target node of the
alpar@2260:       /// given edge iterator.
alpar@2260:       NodeIt target(const EdgeIt&) const {return INVALID;}
alpar@2260: 
alpar@2260:       /// \brief The source of an edge.
alpar@2260:       ///
alpar@2260:       /// Returns node iterator pointing to the source node of the
alpar@2260:       /// given edge iterator.
alpar@2260:       NodeIt source(const EdgeIt&) const {return INVALID;}
alpar@2260: 
alpar@2260:       /// \brief Iterator class to iterate on the nodes of the paths
alpar@2260:       ///
alpar@2260:       /// This class is used to iterate on the nodes of the paths
alpar@2260:       ///
alpar@2260:       /// Of course it converts to Graph::Node.
alpar@2260:       class NodeIt {
alpar@2260:       public:
alpar@2260: 	/// Default constructor
alpar@2260: 	NodeIt() {}
alpar@2260: 	/// Invalid constructor
alpar@2260: 	NodeIt(Invalid) {}
alpar@2260: 	/// Constructor with starting point
alpar@2260: 	NodeIt(const Path &) {}
alpar@2260: 
alpar@2260: 	///Conversion to Graph::Node
alpar@2260: 	operator Node() const { return INVALID; }
alpar@2260: 	/// Next node
alpar@2260: 	NodeIt& operator++() {return *this;}
alpar@2260: 
alpar@2260: 	/// Comparison operator
alpar@2260: 	bool operator==(const NodeIt&) const {return true;}
alpar@2260: 	/// Comparison operator
alpar@2260: 	bool operator!=(const NodeIt&) const {return true;}
alpar@2260:  	/// Comparison operator
alpar@2260:  	bool operator<(const NodeIt&) const {return false;}
alpar@2260: 
alpar@2260:       };
alpar@2260: 
alpar@2260:       /// \brief Iterator class to iterate on the edges of the paths
alpar@2260:       ///
alpar@2260:       /// This class is used to iterate on the edges of the paths
alpar@2260:       ///
alpar@2260:       /// Of course it converts to Graph::Edge
alpar@2260:       class EdgeIt {
alpar@2260:       public:
alpar@2260: 	/// Default constructor
alpar@2260: 	EdgeIt() {}
alpar@2260: 	/// Invalid constructor
alpar@2260: 	EdgeIt(Invalid) {}
alpar@2260: 	/// Constructor with starting point
alpar@2260: 	EdgeIt(const Path &) {}
alpar@2260: 
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: 
alpar@2260: 
alpar@2260:       friend class Builder;
alpar@2260: 
alpar@2260:       /// \brief Class to build paths
alpar@2260:       ///
alpar@2260:       /// This class is used to fill a path with edges.
alpar@2260:       ///
alpar@2260:       /// You can push new edges to the front and to the back of the path in
alpar@2260:       /// arbitrary order then you should commit these changes to the graph.
alpar@2260:       ///
alpar@2260:       /// While the builder is active (after the first modifying
alpar@2260:       /// operation and until the call of \ref commit()) the
alpar@2260:       /// underlining Path is in a "transitional" state (operations on
alpar@2260:       /// it have undefined result).
alpar@2260:       class Builder {
alpar@2260:       public:
alpar@2260: 
alpar@2260:         /// Constructor
alpar@2260: 
alpar@2260:         /// Constructor
alpar@2260: 	/// \param _path the path you want to fill in.
alpar@2260: 	///
alpar@2260: 
alpar@2260: 	Builder(Path &_path) { ignore_unused_variable_warning(_path); }
alpar@2260: 
alpar@2260: 	/// Sets the starting node of the path.
alpar@2260: 
alpar@2260: 	/// Sets the starting node of the path. Edge added to the path
alpar@2260: 	/// afterwards have to be incident to this node.
alpar@2260: 	/// You \em must start building an empty path with these functions.
alpar@2260: 	/// (And you \em must \em not use it later).
alpar@2260: 	/// \sa pushFront()
alpar@2260: 	/// \sa pushBack()
alpar@2260: 	void setStartNode(const Node &) {}
alpar@2260: 
alpar@2260: 	///Push a new edge to the front of the path
alpar@2260: 
alpar@2260: 	///Push a new edge to the front of the path.
alpar@2260: 	///If the path is empty, you \em must call \ref setStartNode() before
alpar@2260: 	///the first use of \ref pushFront().
alpar@2260: 	void pushFront(const Edge&) {}
alpar@2260: 
alpar@2260: 	///Push a new edge to the back of the path
alpar@2260: 
alpar@2260: 	///Push a new edge to the back of the path.
alpar@2260: 	///If the path is empty, you \em must call \ref setStartNode() before
alpar@2260: 	///the first use of \ref pushBack().
alpar@2260: 	void pushBack(const Edge&) {}
alpar@2260: 
alpar@2260: 	///Commit the changes to the path.
alpar@2260: 
alpar@2260: 	///Commit the changes to the path.
alpar@2260:         ///
alpar@2260: 	void commit() {}
alpar@2260: 
alpar@2260: 	///Reserve (front) storage for the builder in advance.
alpar@2260: 
alpar@2260: 	///If you know a reasonable upper bound on the number of the edges
alpar@2260: 	///to add to the front of the path,
alpar@2260: 	///using this function you may speed up the building.
alpar@2260: 	void reserveFront(size_t) {}
alpar@2260: 	///Reserve (back) storage for the builder in advance.
alpar@2260: 
alpar@2260: 	///If you know a reasonable upper bound on the number of the edges
alpar@2260: 	///to add to the back of the path,
alpar@2260: 	///using this function you may speed up the building.
alpar@2260: 	void reserveBack(size_t) {}
alpar@2260:       };
alpar@2260: 
alpar@2260:       template <typename _Path>
alpar@2260:       struct Constraints {
alpar@2260: 	void constraints() {
alpar@2260:           typedef typename _Path::Node Node;
alpar@2260:           typedef typename _Path::NodeIt NodeIt;
alpar@2260:           typedef typename Graph::Node GraphNode;
alpar@2260: 
alpar@2260:           typedef typename _Path::Edge Edge;
alpar@2260:           typedef typename _Path::EdgeIt EdgeIt;
alpar@2260:           typedef typename Graph::Edge GraphEdge;
alpar@2260: 
alpar@2260:           typedef typename _Path::Builder Builder;
alpar@2260: 
alpar@2260:           path = _Path(graph);
alpar@2260: 
alpar@2260:           bool b = cpath.empty();
alpar@2260:           int l = cpath.length();
alpar@2260: 
alpar@2260:           Node gn;
alpar@2260:           Edge ge;
alpar@2260:           gn = cpath.source();
alpar@2260:           gn = cpath.target();
alpar@2260: 
alpar@2260:           NodeIt nit;
alpar@2260:           EdgeIt eit(INVALID);
alpar@2260:           nit = path.source(eit);
alpar@2260:           nit = path.target(eit);
alpar@2260:           
alpar@2260:           nit = NodeIt();
alpar@2260:           nit = NodeIt(cpath);
alpar@2260:           nit = INVALID;
alpar@2260:           gn = nit;
alpar@2260:           ++nit;
alpar@2260:           b = nit == nit;
alpar@2260:           b = nit != nit;
alpar@2260:           b = nit < nit;
alpar@2260: 
alpar@2260:           eit = EdgeIt();
alpar@2260:           eit = EdgeIt(cpath);
alpar@2260:           eit = INVALID;
alpar@2260:           ge = eit;
alpar@2260:           ++eit;
alpar@2260:           b = eit == eit;
alpar@2260:           b = eit != eit;
alpar@2260:           b = eit < eit;
alpar@2260: 
alpar@2260:           size_t st = 0;
alpar@2260: 
alpar@2260:           Builder builder(path); 
alpar@2260:           builder.setStartNode(gn);
alpar@2260:           builder.pushFront(ge);
alpar@2260:           builder.pushBack(ge);
alpar@2260:           builder.commit();
alpar@2260:           builder.reserveFront(st);
alpar@2260:           builder.reserveBack(st);
alpar@2260:           
alpar@2260:           ignore_unused_variable_warning(l);
alpar@2260:           ignore_unused_variable_warning(b);
alpar@2260: 	}
alpar@2260: 
alpar@2260:         const Graph& graph;
alpar@2260:         const _Path& cpath;
alpar@2260:         _Path& path;
alpar@2260:       };
alpar@2260: 
alpar@2260:     };
alpar@2260: 
alpar@2260:   ///@}
alpar@2260:   }
alpar@2260: 
alpar@2260: } // namespace lemon
alpar@2260: 
alpar@2260: #endif // LEMON_CONCEPT_PATH_H