Changeset 2247:269a0dcee70b in lemon-0.x for lemon/concept

Timestamp:

10/17/06 12:50:57 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Update the Path concept
Concept check for paths

DirPath? renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed

I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation

File:

• lemon/concept/path.h (modified) (10 diffs)

lemon/concept/path.h

@@ -38 +38 @@
     //!
     //! A skeleton structure for representing directed paths in a graph.
-    //! \param GR The graph type in which the path is.
+    //! \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 GR>
+    template<typename _Graph>
     class Path {
     public:
 
       /// Type of the underlying graph.
-      typedef /*typename*/ GR Graph;
+      typedef _Graph Graph;
       /// Edge type of the underlying graph.
-      typedef typename Graph::Edge GraphEdge;
+      typedef typename Graph::Edge Edge;
       /// Node type of the underlying graph.
-     typedef typename Graph::Node GraphNode;
+      typedef typename Graph::Node Node;
+
       class NodeIt;
       class EdgeIt;
@@ -62 +63 @@
       }
 
-      /// Length of the path.
+      /// 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;}
@@ -74 +76 @@
       /// Starting point of the path.
       /// Returns INVALID if the path is empty.
-      GraphNode/*It*/ target() const {return INVALID;}
+      Node target() const {return INVALID;}
       /// \brief End point of the path.
       ///
       /// End point of the path.
       /// Returns INVALID if the path is empty.
-      GraphNode/*It*/ source() const {return INVALID;}
-
-      /// \brief First NodeIt/EdgeIt.
-      ///
-      /// Initializes node or edge iterator to point to the first
-      /// node or edge.
-      template<typename It>
-      It& first(It &i) const { return i=It(*this); }
+      Node source() const {return INVALID;}
 
       /// \brief The target of an edge.
@@ -100 +95 @@
       NodeIt source(const EdgeIt&) const {return INVALID;}
 
-
-      /* Iterator classes */
-
-      /**
-       * \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
-       *
-       */
+      /// \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:
@@ -120 +137 @@
         EdgeIt(const Path &) {}
 
-        operator GraphEdge () const {}
+        operator Edge() const { return INVALID; }
 
         /// Next edge
@@ -129 +146 @@
         /// Comparison operator
         bool operator!=(const EdgeIt&) const {return true;}
-//      /// Comparison operator
-//      /// \todo It is not clear what is the "natural" ordering.
-//      bool operator<(const EdgeIt& e) const {}
-
-      };
-
-      /**
-       * \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 const GraphNode& () const {}
-        /// 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
-//      /// \todo It is not clear what is the "natural" ordering.
-//      bool operator<(const NodeIt& e) const {}
-
-      };
+        /// 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).
-       */
+      /// \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:
 
-        Path &P;
-
-        ///\param _p the path you want to fill in.
+        /// Constructor
+
+        /// Constructor
+        /// \param _path the path you want to fill in.
         ///
 
-        Builder(Path &_p) : P(_p) {}
+        Builder(Path &_path) { ignore_unused_variable_warning(_path); }
 
         /// Sets the starting node of the path.
@@ -200 +184 @@
         /// \sa pushFront()
         /// \sa pushBack()
-        void setStartNode(const GraphNode &) {}
+        void setStartNode(const Node &) {}
 
         ///Push a new edge to the front of the path
@@ -207 +191 @@
         ///If the path is empty, you \em must call \ref setStartNode() before
         ///the first use of \ref pushFront().
-        void pushFront(const GraphEdge&) {}
+        void pushFront(const Edge&) {}
 
         ///Push a new edge to the back of the path
@@ -214 +198 @@
         ///If the path is empty, you \em must call \ref setStartNode() before
         ///the first use of \ref pushBack().
-        void pushBack(const GraphEdge&) {}
+        void pushBack(const Edge&) {}
 
         ///Commit the changes to the path.
+
+        ///Commit the changes to the path.
+        ///
         void commit() {}
 
@@ -232 +219 @@
         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;
+      };
+
     };