diff -r da142c310d02 -r 4274224f8a7d lemon/concepts/path.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/concepts/path.h	Tue Oct 24 17:19:16 2006 +0000
@@ -0,0 +1,294 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+///\ingroup concept
+///\file
+///\brief Classes for representing paths in graphs.
+///
+///\todo Iterators have obsolete style
+
+#ifndef LEMON_CONCEPT_PATH_H
+#define LEMON_CONCEPT_PATH_H
+
+#include <lemon/bits/invalid.h>
+#include <lemon/concept_check.h>
+
+namespace lemon {
+  namespace concepts {
+    /// \addtogroup concept
+    /// @{
+
+
+    //! \brief A skeleton structure for representing directed paths in a graph.
+    //!
+    //! A skeleton structure for representing directed paths in a graph.
+    //! \param _Graph The graph type in which the path is.
+    //!
+    //! In a sense, the path can be treated as a graph, for it has \c NodeIt
+    //! and \c EdgeIt with the same usage. These types converts to the \c Node
+    //! and \c Edge of the original graph.
+    template<typename _Graph>
+    class Path {
+    public:
+
+      /// Type of the underlying graph.
+      typedef _Graph Graph;
+      /// Edge type of the underlying graph.
+      typedef typename Graph::Edge Edge;
+      /// Node type of the underlying graph.
+      typedef typename Graph::Node Node;
+
+      class NodeIt;
+      class EdgeIt;
+
+      /// \param _g The graph in which the path is.
+      ///
+      Path(const Graph &_g) {
+	ignore_unused_variable_warning(_g);
+      }
+
+      /// Length of the path ie. the number of edges in the path.
+      int length() const {return 0;}
+
+      /// Returns whether the path is empty.
+      bool empty() const { return true;}
+
+      /// Resets the path to an empty path.
+      void clear() {}
+
+      /// \brief Starting point of the path.
+      ///
+      /// Starting point of the path.
+      /// Returns INVALID if the path is empty.
+      Node target() const {return INVALID;}
+      /// \brief End point of the path.
+      ///
+      /// End point of the path.
+      /// Returns INVALID if the path is empty.
+      Node source() const {return INVALID;}
+
+      /// \brief The target of an edge.
+      ///
+      /// Returns node iterator pointing to the target node of the
+      /// given edge iterator.
+      NodeIt target(const EdgeIt&) const {return INVALID;}
+
+      /// \brief The source of an edge.
+      ///
+      /// Returns node iterator pointing to the source node of the
+      /// given edge iterator.
+      NodeIt source(const EdgeIt&) const {return INVALID;}
+
+      /// \brief Iterator class to iterate on the nodes of the paths
+      ///
+      /// This class is used to iterate on the nodes of the paths
+      ///
+      /// Of course it converts to Graph::Node.
+      class NodeIt {
+      public:
+	/// Default constructor
+	NodeIt() {}
+	/// Invalid constructor
+	NodeIt(Invalid) {}
+	/// Constructor with starting point
+	NodeIt(const Path &) {}
+
+	///Conversion to Graph::Node
+	operator Node() const { return INVALID; }
+	/// Next node
+	NodeIt& operator++() {return *this;}
+
+	/// Comparison operator
+	bool operator==(const NodeIt&) const {return true;}
+	/// Comparison operator
+	bool operator!=(const NodeIt&) const {return true;}
+ 	/// Comparison operator
+ 	bool operator<(const NodeIt&) const {return false;}
+
+      };
+
+      /// \brief Iterator class to iterate on the edges of the paths
+      ///
+      /// This class is used to iterate on the edges of the paths
+      ///
+      /// Of course it converts to Graph::Edge
+      class EdgeIt {
+      public:
+	/// Default constructor
+	EdgeIt() {}
+	/// Invalid constructor
+	EdgeIt(Invalid) {}
+	/// Constructor with starting point
+	EdgeIt(const Path &) {}
+
+	operator Edge() const { return INVALID; }
+
+	/// Next edge
+	EdgeIt& operator++() {return *this;}
+
+	/// Comparison operator
+	bool operator==(const EdgeIt&) const {return true;}
+	/// Comparison operator
+	bool operator!=(const EdgeIt&) const {return true;}
+ 	/// Comparison operator
+ 	bool operator<(const EdgeIt&) const {return false;}
+
+      };
+
+
+      friend class Builder;
+
+      /// \brief Class to build paths
+      ///
+      /// This class is used to fill a path with edges.
+      ///
+      /// You can push new edges to the front and to the back of the path in
+      /// arbitrary order then you should commit these changes to the graph.
+      ///
+      /// While the builder is active (after the first modifying
+      /// operation and until the call of \ref commit()) the
+      /// underlining Path is in a "transitional" state (operations on
+      /// it have undefined result).
+      class Builder {
+      public:
+
+        /// Constructor
+
+        /// Constructor
+	/// \param _path the path you want to fill in.
+	///
+
+	Builder(Path &_path) { ignore_unused_variable_warning(_path); }
+
+	/// Sets the starting node of the path.
+
+	/// Sets the starting node of the path. Edge added to the path
+	/// afterwards have to be incident to this node.
+	/// You \em must start building an empty path with these functions.
+	/// (And you \em must \em not use it later).
+	/// \sa pushFront()
+	/// \sa pushBack()
+	void setStartNode(const Node &) {}
+
+	///Push a new edge to the front of the path
+
+	///Push a new edge to the front of the path.
+	///If the path is empty, you \em must call \ref setStartNode() before
+	///the first use of \ref pushFront().
+	void pushFront(const Edge&) {}
+
+	///Push a new edge to the back of the path
+
+	///Push a new edge to the back of the path.
+	///If the path is empty, you \em must call \ref setStartNode() before
+	///the first use of \ref pushBack().
+	void pushBack(const Edge&) {}
+
+	///Commit the changes to the path.
+
+	///Commit the changes to the path.
+        ///
+	void commit() {}
+
+	///Reserve (front) storage for the builder in advance.
+
+	///If you know a reasonable upper bound on the number of the edges
+	///to add to the front of the path,
+	///using this function you may speed up the building.
+	void reserveFront(size_t) {}
+	///Reserve (back) storage for the builder in advance.
+
+	///If you know a reasonable upper bound on the number of the edges
+	///to add to the back of the path,
+	///using this function you may speed up the building.
+	void reserveBack(size_t) {}
+      };
+
+      template <typename _Path>
+      struct Constraints {
+	void constraints() {
+          typedef typename _Path::Node Node;
+          typedef typename _Path::NodeIt NodeIt;
+          typedef typename Graph::Node GraphNode;
+
+          typedef typename _Path::Edge Edge;
+          typedef typename _Path::EdgeIt EdgeIt;
+          typedef typename Graph::Edge GraphEdge;
+
+          typedef typename _Path::Builder Builder;
+
+          path = _Path(graph);
+
+          bool b = cpath.empty();
+          int l = cpath.length();
+
+          Node gn;
+          Edge ge;
+          gn = cpath.source();
+          gn = cpath.target();
+
+          NodeIt nit;
+          EdgeIt eit(INVALID);
+          nit = path.source(eit);
+          nit = path.target(eit);
+          
+          nit = NodeIt();
+          nit = NodeIt(cpath);
+          nit = INVALID;
+          gn = nit;
+          ++nit;
+          b = nit == nit;
+          b = nit != nit;
+          b = nit < nit;
+
+          eit = EdgeIt();
+          eit = EdgeIt(cpath);
+          eit = INVALID;
+          ge = eit;
+          ++eit;
+          b = eit == eit;
+          b = eit != eit;
+          b = eit < eit;
+
+          size_t st = 0;
+
+          Builder builder(path); 
+          builder.setStartNode(gn);
+          builder.pushFront(ge);
+          builder.pushBack(ge);
+          builder.commit();
+          builder.reserveFront(st);
+          builder.reserveBack(st);
+          
+          ignore_unused_variable_warning(l);
+          ignore_unused_variable_warning(b);
+	}
+
+        const Graph& graph;
+        const _Path& cpath;
+        _Path& path;
+      };
+
+    };
+
+  ///@}
+  }
+
+} // namespace lemon
+
+#endif // LEMON_CONCEPT_PATH_H