LEMON/LEMON-main Changeset - r97:ee1324c91288

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r97:ee1324c91288

« 96:b55e50

98:c4582f »

r97:ee1324c91288

Thu, 24 Jan 2008 17:49:10

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Doc improvements

0 2 0

default

2 files changed with 73 insertions and 72 deletions:

lemon/path.h

lemon/path_utils.h

↑ Collapse diff ↑

lemon/path.h

Show inline comments

@@ -38,66 +38,66 @@
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \param Digraph The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. 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.
+		  /// lemon path type stores just this list. As a consequence, it
 		  /// cannot enumerate the nodes of the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
 		  /// This implementation is a back and front insertable and erasable
 		  /// path type. It can be indexed in O(1) time. The front and back
 		  /// insertion and erasure is amortized O(1) time. The
 		  /// impelementation is based on two opposite organized vectors.
 		  /// insertion and erase is done in O(1) (amortized) time. The
 		  /// implementation uses two vectors for storing the front and back
 		  /// insertions.
 		  template <typename _Digraph>
 		  class Path {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    Path() {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    /// This constuctor initializes the path from any other path type.
 		    /// It simply makes a copy of the given path.
 		    template <typename CPath>
 		    Path(const CPath& cpath) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    /// This operator makes a copy of a path of any other type.
 		    template <typename CPath>
 		    Path& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Lemon style iterator for path arcs
 		    ///
 		    /// This class is used to iterate on the arcs of the paths.
 		    class ArcIt {
 		      friend class Path;
 		    public:
 		      /// \brief Default constructor
 		      ArcIt() {}
 		      /// \brief Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
-		      /// \brief Initializate the constructor to the first arc of path
+		      /// \brief Initializate the iterator to the first arc of path
 		      ArcIt(const Path &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      ArcIt(const Path &_path, int _idx)
 		        : path(&_path), idx(_idx) {}
@@ -124,38 +124,38 @@
 		    private:
 		      const Path *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return head.size() + tail.size(); }
-		    /// \brief Returns whether the path is empty.
+		    /// \brief Return whether the path is empty.
 		    bool empty() const { return head.empty() && tail.empty(); }
-		    /// \brief Resets the path to an empty path.
+		    /// \brief Reset the path to an empty one.
 		    void clear() { head.clear(); tail.clear(); }
-		    /// \brief Gives back the nth arc.
+		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return n < int(head.size()) ? *(head.rbegin() + n) :
 		        *(tail.begin() + (n - head.size()));
+		    }
-		    /// \brief Initializes arc iterator to point to the nth arc
+		    /// \brief Initialize arc iterator to point to the nth arc
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
-		    /// \brief Gives back the first arc of the path
+		    /// \brief The first arc of the path
 		    const Arc& front() const {
 		      return head.empty() ? tail.front() : head.back();
+		    }
 		    /// \brief Add a new arc before the current path
 		    void addFront(const Arc& arc) {
 		      head.push_back(arc);
+		    }
@@ -170,17 +170,17 @@
 		        head.resize(halfsize);
 		        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
 		                  head.rbegin());
 		        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
 		        tail.resize(tail.size() - halfsize - 1);
+		      }
+		    }
-		    /// \brief Gives back the last arc of the path
+		    /// \brief The last arc of the path
 		    const Arc& back() const {
 		      return tail.empty() ? head.front() : tail.back();
+		    }
 		    /// \brief Add a new arc behind the current path
 		    void addBack(const Arc& arc) {
 		      tail.push_back(arc);
+		    }
@@ -194,18 +194,16 @@
 		        tail.resize(halfsize);
 		        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
 		                  tail.rbegin());
 		        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
 		        head.resize(head.size() - halfsize - 1);
+		      }
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      int len = path.length();
 		      tail.reserve(len);
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        tail.push_back(it);
@@ -318,40 +316,40 @@
 		    private:
 		      const SimplePath *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return data.size(); }
-		    /// \brief Returns whether the path is empty.
+		    /// \brief Return true if the path is empty.
 		    bool empty() const { return data.empty(); }
-		    /// \brief Resets the path to an empty path.
+		    /// \brief Reset the path to an empty one.
 		    void clear() { data.clear(); }
-		    /// \brief Gives back the nth arc.
+		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return data[n];
+		    }
 		    /// \brief  Initializes arc iterator to point to the nth arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
-		    /// \brief Gives back the first arc of the path.
+		    /// \brief The first arc of the path.
 		    const Arc& front() const {
 		      return data.front();
+		    }
-		    /// \brief Gives back the last arc of the path.
+		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return data.back();
+		    }
 		    /// \brief Add a new arc behind the current path.
 		    void addBack(const Arc& arc) {
 		      data.push_back(arc);
+		    }
@@ -501,19 +499,19 @@
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return node<e.node; }
 		    private:
 		      const ListPath *path;
 		      Node *node;
 		    };
-		    /// \brief Gives back the nth arc.
+		    /// \brief The nth arc.
 		    ///
-		    /// Gives back the nth arc in O(n) time.
+		    /// This function looks for the nth arc in O(n) time.
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      Node *node = first;
 		      for (int i = 0; i < n; ++i) {
 		        node = node->next;
+		      }
 		      return node->arc;
+		    }
@@ -533,30 +531,30 @@
 		      Node *node = first;
 		      while (node != 0) {
 		        node = node->next;
 		        ++len;
+		      }
 		      return len;
+		    }
-		    /// \brief Returns whether the path is empty.
+		    /// \brief Return true if the path is empty.
 		    bool empty() const { return first == 0; }
-		    /// \brief Resets the path to an empty path.
+		    /// \brief Reset the path to an empty one.
 		    void clear() {
 		      while (first != 0) {
 		        last = first->next;
 		        alloc.destroy(first);
 		        alloc.deallocate(first, 1);
 		        first = last;
+		      }
+		    }
-		    /// \brief Gives back the first arc of the path
+		    /// \brief The first arc of the path
 		    const Arc& front() const {
 		      return first->arc;
+		    }
 		    /// \brief Add a new arc before the current path
 		    void addFront(const Arc& arc) {
 		      Node *node = alloc.allocate(1);
 		      alloc.construct(node, Node());
@@ -579,17 +577,17 @@
 		        first->prev = 0;
 		      } else {
 		        last = 0;
+		      }
 		      alloc.destroy(node);
 		      alloc.deallocate(node, 1);
+		    }
-		    /// \brief Gives back the last arc of the path.
+		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return last->arc;
+		    }
 		    /// \brief Add a new arc behind the current path.
 		    void addBack(const Arc& arc) {
 		      Node *node = alloc.allocate(1);
 		      alloc.construct(node, Node());
@@ -612,60 +610,60 @@
 		        last->next = 0;
 		      } else {
 		        first = 0;
+		      }
 		      alloc.destroy(node);
 		      alloc.deallocate(node, 1);
+		    }
-		    /// \brief Splicing the given path to the current path.
+		    /// \brief Splice a path to the back of the current path.
 		    ///
-		    /// It splices the \c tpath to the back of the current path and \c
 		    /// It splices \c tpath to the back of the current path and \c
 		    /// tpath becomes empty. The time complexity of this function is
 		    /// O(1).
 		    void spliceBack(ListPath& tpath) {
 		      if (first) {
 		        if (tpath.first) {
 		          last->next = tpath.first;
 		          tpath.first->prev = last;
 		          last = tpath.last;
+		        }
 		      } else {
 		        first = tpath.first;
 		        last = tpath.last;
+		      }
 		      tpath.first = tpath.last = 0;
+		    }
-		    /// \brief Splicing the given path to the current path.
+		    /// \brief Splice a path to the front of the current path.
 		    ///
-		    /// It splices the \c tpath before the current path and \c tpath
 		    /// It splices \c tpath before the current path and \c tpath
 		    /// becomes empty. The time complexity of this function
 		    /// is O(1).
 		    void spliceFront(ListPath& tpath) {
 		      if (first) {
 		        if (tpath.first) {
 		          first->prev = tpath.last;
 		          tpath.last->next = first;
 		          first = tpath.first;
+		        }
 		      } else {
 		        first = tpath.first;
 		        last = tpath.last;
+		      }
 		      tpath.first = tpath.last = 0;
+		    }
-		    /// \brief Splicing the given path into the current path.
+		    /// \brief Splice a path into the current path.
 		    ///
 		    /// It splices the \c tpath into the current path before the
 		    /// position of \c it iterator and \c tpath becomes empty. The
 		    /// time complexity of this function is O(1). If the \c it is \c
 		    /// INVALID then it will splice behind the current path.
 		    /// time complexity of this function is O(1). If the \c it is
 		    /// \c INVALID then it will splice behind the current path.
 		    void splice(ArcIt it, ListPath& tpath) {
 		      if (it.node) {
 		        if (tpath.first) {
 		          tpath.first->prev = it.node->prev;
 		          if (it.node->prev) {
 		            it.node->prev->next = tpath.first;
 		          } else {
 		            first = tpath.first;
@@ -683,25 +681,25 @@
 		        } else {
 		          first = tpath.first;
 		          last = tpath.last;
+		        }
+		      }
 		      tpath.first = tpath.last = 0;
+		    }
-		    /// \brief Spliting the current path.
+		    /// \brief Split the current path.
 		    ///
 		    /// It splits the current path into two parts. The part before \c
 		    /// it iterator will remain in the current path and the part from
 		    /// the it will put into the \c tpath. If the \c tpath had arcs
 		    /// before the operation they will be removed first.  The time
 		    /// complexity of this function is O(1) plus the clearing of \c
 		    /// tpath. If the \c it is \c INVALID then it just clears \c
-		    /// tpath.
+		    /// It splits the current path into two parts. The part before
 		    /// the iterator \c it will remain in the current path and the part
 		    /// starting with
 		    /// \c it will put into \c tpath. If \c tpath have arcs
 		    /// before the operation they are removed first.  The time
 		    /// complexity of this function is O(1) plus the the time of emtying
 		    /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
 		    void split(ArcIt it, ListPath& tpath) {
 		      tpath.clear();
 		      if (it.node) {
 		        tpath.first = it.node;
 		        tpath.last = last;
 		        if (it.node->prev) {
 		          last = it.node->prev;
 		          last->next = 0;
@@ -733,54 +731,56 @@
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \param Digraph The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. 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.
 		  /// cannot enumerate the nodes in the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
 		  /// This implementation is completly static, so it cannot be
 		  /// modified exclude the assign an other path. It is intented to be
 		  /// used when you want to store a large number of paths because it is
 		  /// the most memory efficient path type in the lemon.
 		  /// This implementation is completly static, i.e. it can be copy constucted
 		  /// or copy assigned from another path, but otherwise it cannot be
 		  /// modified.
 		  ///
 		  /// Being the the most memory efficient path type in LEMON,
 		  /// it is intented to be
 		  /// used when you want to store a large number of paths.
 		  template <typename _Digraph>
 		  class StaticPath {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    StaticPath() : len(0), arcs(0) {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    /// This path can be initialized from any other path type.
 		    template <typename CPath>
 		    StaticPath(const CPath& cpath) : arcs(0) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Destructor of the path
 		    ///
 		    /// Destructor of the path
 		    ~StaticPath() {
 		      if (arcs) delete[] arcs;
+		    }
 		    /// \brief Template copy assignment
 		    ///
-		    /// This path can be initialized with any other path type. It just
+		    /// This path can be made equal to any other path type. It simply
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    StaticPath& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
@@ -826,47 +826,47 @@
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const StaticPath *path;
 		      int idx;
 		    };
-		    /// \brief Gives back the nth arc.
+		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return arcs[n];
+		    }
-		    /// \brief Initializes arc iterator to point to the nth arc.
+		    /// \brief The arc iterator pointing to the nth arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
-		    /// \brief Gives back the length of the path.
+		    /// \brief The length of the path.
 		    int length() const { return len; }
-		    /// \brief Returns true when the path is empty.
+		    /// \brief Return true when the path is empty.
 		    int empty() const { return len == 0; }
-		    /// \break Erase all arc in the digraph.
+		    /// \break Erase all arcs in the digraph.
 		    void clear() {
 		      len = 0;
 		      if (arcs) delete[] arcs;
 		      arcs = 0;
+		    }
-		    /// \brief Gives back the first arc of the path.
+		    /// \brief The first arc of the path.
 		    const Arc& front() const {
 		      return arcs[0];
+		    }
-		    /// \brief Gives back the last arc of the path.
+		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return arcs[len - 1];
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>

lemon/path_utils.h

Show inline comments

@@ -85,68 +85,69 @@
 		        target.clear();
 		        target.buildRev(source);
+		      }
 		    };
+		  }
-		  /// \brief Make of copy of a path.
+		  /// \brief Make a copy of a path.
 		  ///
-		  ///  Make of copy of a path.
+		  ///  This function makes a copy of a path.
 		  template <typename Target, typename Source>
 		  void copyPath(Target& target, const Source& source) {
 		    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
 		    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
+		  }
-		  /// \brief Checks the path's consistency.
+		  /// \brief Check the consistency of a path.
 		  ///
-		  /// Checks that each arc's target is the next's source.
+		  /// This function checks that the target of each arc is the same
 		  /// as the source of the next one.
 		  ///
 		  template <typename Digraph, typename Path>
 		  bool checkPath(const Digraph& digraph, const Path& path) {
 		    typename Path::ArcIt it(path);
 		    if (it == INVALID) return true;
 		    typename Digraph::Node node = digraph.target(it);
 		    ++it;
 		    while (it != INVALID) {
 		      if (digraph.source(it) != node) return false;
 		      node = digraph.target(it);
 		      ++it;
+		    }
 		    return true;
+		  }
-		  /// \brief Gives back the source of the path
+		  /// \brief The source of a path
 		  ///
-		  /// Gives back the source of the path.
+		  /// This function returns the source of the given path.
 		  template <typename Digraph, typename Path>
 		  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
 		    return digraph.source(path.front());
+		  }
-		  /// \brief Gives back the target of the path
+		  /// \brief The target of a path
 		  ///
-		  /// Gives back the target of the path.
+		  /// This function returns the target of the given path.
 		  template <typename Digraph, typename Path>
 		  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
 		    return digraph.target(path.back());
+		  }
 		  /// \brief Class which helps to iterate the nodes of a path
+		  /// \brief Class which helps to iterate through the nodes of a path
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores just this list. As a consequence it
+		  /// lemon path type stores only this list. As a consequence, it
 		  /// cannot enumerate the nodes in the path and the zero length paths
-		  /// cannot store the node.
+		  /// cannot have a source node.
 		  ///
 		  /// This class implements the node iterator of a path structure. To
-		  /// provide this feature, the underlying digraph should be given to
+		  /// provide this feature, the underlying digraph should be passed to
 		  /// the constructor of the iterator.
 		  template <typename Path>
 		  class PathNodeIt {
 		  private:
 		    const typename Path::Digraph *_digraph;
 		    typename Path::ArcIt _it;
 		    typename Path::Digraph::Node _nd;

0 comments (0 inline)

RhodeCode

Login to your account