Changeset 2335:27aa03cd3121 in lemon-0.x for lemon/concepts

Timestamp:

01/08/07 11:39:59 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3123

Message:

New path concept and path structures

TODO: BellmanFord::negativeCycle()

File:

• lemon/concepts/path.h (modified) (5 diffs)

lemon/concepts/path.h

@@ -27 +27 @@
 
 #include <lemon/bits/invalid.h>
+#include <lemon/bits/utility.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>
+    /// \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 list of edges. The
+    /// lemon path type stores just this list. As a consequence it
+    /// cannot enumerate the nodes in the path and the zero length
+    /// paths cannot store the source.
+    ///
+    template <typename _Graph>
     class Path {
     public:
@@ -51 +56 @@
       /// 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);
-      }
+      /// \brief Default constructor
+      Path() {}
+
+      /// \brief Template constructor
+      template <typename CPath>
+      Path(const CPath& cpath) {}
+
+      /// \brief Template assigment
+      template <typename CPath>
+      Path& operator=(const CPath& cpath) {}
 
       /// Length of the path ie. the number of edges in the path.
-      int length() const {return 0;}
+      int length() const { return 0;}
 
       /// Returns whether the path is empty.
@@ -72 +79 @@
       void clear() {}
 
-      /// \brief Starting point of the path.
+      /// \brief Lemon style iterator for path edges
       ///
-      /// 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
+      /// This class is used to iterate on the edges of the paths.
       class EdgeIt {
       public:
@@ -134 +88 @@
         /// Invalid constructor
         EdgeIt(Invalid) {}
-        /// Constructor with starting point
+        /// Constructor for first edge
         EdgeIt(const Path &) {}
 
+        /// Conversion to Edge
         operator Edge() const { return INVALID; }
 
@@ -151 +106 @@
       };
 
-
-      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);
-          
+        void constraints() {
+          Path<Graph> pc;
+          _Path p, pp(pc);
+          int l = p.length();
+          int e = p.empty();
+          p.clear();
+
+          p = pc;
+
+          typename _Path::EdgeIt id, ii(INVALID), i(p);
+
+          ++i;
+          typename Graph::Edge ed = i;
+
+          e = (i == ii);
+          e = (i != ii);
+          e = (i < ii);
+
           ignore_unused_variable_warning(l);
-          ignore_unused_variable_warning(b);
-        }
-
-        const Graph& graph;
-        const _Path& cpath;
-        _Path& path;
+          ignore_unused_variable_warning(pp);
+          ignore_unused_variable_warning(e);
+          ignore_unused_variable_warning(id);
+          ignore_unused_variable_warning(ii);
+          ignore_unused_variable_warning(ed);
+        }
       };
 
     };
 
-  ///@}
+    namespace _path_bits {
+      
+      template <typename _Graph, typename _Path, typename RevPathTag = void>
+      struct PathDumperConstraints {
+        void constraints() {
+          int l = p.length();
+          int e = p.empty();
+
+          typename _Path::EdgeIt id, ii(INVALID), i(p);
+
+          ++i;
+          typename _Graph::Edge ed = i;
+
+          e = (i == ii);
+          e = (i != ii);
+          e = (i < ii);
+
+          ignore_unused_variable_warning(l);
+          ignore_unused_variable_warning(e);
+          ignore_unused_variable_warning(id);
+          ignore_unused_variable_warning(ii);
+          ignore_unused_variable_warning(ed);
+        }
+        _Path& p;
+      };
+
+      template <typename _Graph, typename _Path>
+      struct PathDumperConstraints<
+        _Graph, _Path, 
+        typename enable_if<typename _Path::RevPathTag, void>::type
+      > {
+        void constraints() {
+          int l = p.length();
+          int e = p.empty();
+
+          typename _Path::RevIt id, ii(INVALID), i(p);
+
+          ++i;
+          typename _Graph::Edge ed = i;
+
+          e = (i == ii);
+          e = (i != ii);
+          e = (i < ii);
+
+          ignore_unused_variable_warning(l);
+          ignore_unused_variable_warning(e);
+          ignore_unused_variable_warning(id);
+          ignore_unused_variable_warning(ii);
+          ignore_unused_variable_warning(ed);
+        }
+        _Path& p;
+      };
+    
+    }
+
+
+    /// \brief A skeleton structure for path dumpers.
+    ///
+    /// A skeleton structure for path dumpers. The path dumpers are
+    /// the generalization of the paths. The path dumpers can
+    /// enumerate the edges of the path wheter in forward or in
+    /// backward order.  In most time these classes are not used
+    /// directly rather it used to assign a dumped class to a real
+    /// path type.
+    ///
+    /// The main purpose of this concept is that the shortest path
+    /// algorithms can enumerate easily the edges in reverse order.
+    /// If we would like to give back a real path from these
+    /// algorithms then we should create a temporarly path object. In
+    /// Lemon such algorithms gives back a path dumper what can
+    /// assigned to a real path and the dumpers can be implemented as
+    /// an adaptor class to the predecessor map.
+
+    /// \param _Graph  The graph type in which the path is.
+    ///
+    /// The paths can be constructed from any path type by a
+    /// template constructor or a template assignment operator.
+    /// 
+    template <typename _Graph>
+    class PathDumper {
+    public:
+
+      /// Type of the underlying graph.
+      typedef _Graph Graph;
+      /// Edge type of the underlying graph.
+      typedef typename Graph::Edge Edge;
+
+      /// 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;}
+
+      /// \brief Forward or reverse dumping
+      ///
+      /// If the RevPathTag is defined and true then reverse dumping
+      /// is provided in the path proxy. In this case instead of the
+      /// EdgeIt the RevIt iterator should be implemented in the
+      /// proxy.
+      typedef False RevPathTag;
+
+      /// \brief Lemon style iterator for path edges
+      ///
+      /// This class is used to iterate on the edges of the paths.
+      class EdgeIt {
+      public:
+        /// Default constructor
+        EdgeIt() {}
+        /// Invalid constructor
+        EdgeIt(Invalid) {}
+        /// Constructor for first edge
+        EdgeIt(const PathDumper&) {}
+
+        /// Conversion to Edge
+        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;}
+
+      };
+
+      /// \brief Lemon style iterator for path edges
+      ///
+      /// This class is used to iterate on the edges of the paths in
+      /// reverse direction.
+      class RevIt {
+      public:
+        /// Default constructor
+        RevIt() {}
+        /// Invalid constructor
+        RevIt(Invalid) {}
+        /// Constructor for first edge
+        RevIt(const PathDumper &) {}
+
+        /// Conversion to Edge
+        operator Edge() const { return INVALID; }
+
+        /// Next edge
+        RevIt& operator++() {return *this;}
+
+        /// Comparison operator
+        bool operator==(const RevIt&) const {return true;}
+        /// Comparison operator
+        bool operator!=(const RevIt&) const {return true;}
+        /// Comparison operator
+        bool operator<(const RevIt&) const {return false;}
+
+      };
+
+      template <typename _Path>
+      struct Constraints {
+        void constraints() {
+          function_requires<_path_bits::
+            PathDumperConstraints<Graph, _Path> >();
+        }
+      };
+
+    };
+
+
+    ///@}
   }