COIN-OR::LEMON - Graph Library

Changeset 97:ee1324c91288 in lemon for lemon/path.h


Ignore:
Timestamp:
01/24/08 17:49:10 (17 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Doc improvements

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/path.h

    r96 r97  
    4444  ///
    4545  /// In a sense, the path can be treated as a list of arcs. The
    46   /// lemon path type stores just this list. As a consequence it
    47   /// cannot enumerate the nodes in the path and the zero length paths
    48   /// cannot store the source.
     46  /// lemon path type stores just this list. As a consequence, it
     47  /// cannot enumerate the nodes of the path and the source node of
     48  /// a zero length path is undefined.
    4949  ///
    5050  /// This implementation is a back and front insertable and erasable
    5151  /// path type. It can be indexed in O(1) time. The front and back
    52   /// insertion and erasure is amortized O(1) time. The
    53   /// impelementation is based on two opposite organized vectors.
     52  /// insertion and erase is done in O(1) (amortized) time. The
     53  /// implementation uses two vectors for storing the front and back
     54  /// insertions.
    5455  template <typename _Digraph>
    5556  class Path {
     
    6667    /// \brief Template copy constructor
    6768    ///
    68     /// This path can be initialized with any other path type. It just
    69     /// makes a copy of the given path.
     69    /// This constuctor initializes the path from any other path type.
     70    /// It simply makes a copy of the given path.
    7071    template <typename CPath>
    7172    Path(const CPath& cpath) {
     
    7576    /// \brief Template copy assignment
    7677    ///
    77     /// This path can be initialized with any other path type. It just
    78     /// makes a copy of the given path.
     78    /// This operator makes a copy of a path of any other type.
    7979    template <typename CPath>
    8080    Path& operator=(const CPath& cpath) {
     
    9393      /// \brief Invalid constructor
    9494      ArcIt(Invalid) : path(0), idx(-1) {}
    95       /// \brief Initializate the constructor to the first arc of path
     95      /// \brief Initializate the iterator to the first arc of path
    9696      ArcIt(const Path &_path)
    9797        : path(&_path), idx(_path.empty() ? -1 : 0) {}
     
    130130    /// \brief Length of the path.
    131131    int length() const { return head.size() + tail.size(); }
    132     /// \brief Returns whether the path is empty.
     132    /// \brief Return whether the path is empty.
    133133    bool empty() const { return head.empty() && tail.empty(); }
    134134
    135     /// \brief Resets the path to an empty path.
     135    /// \brief Reset the path to an empty one.
    136136    void clear() { head.clear(); tail.clear(); }
    137137
    138     /// \brief Gives back the nth arc.
     138    /// \brief The nth arc.
    139139    ///
    140140    /// \pre n is in the [0..length() - 1] range
     
    144144    }
    145145
    146     /// \brief Initializes arc iterator to point to the nth arc
     146    /// \brief Initialize arc iterator to point to the nth arc
    147147    ///
    148148    /// \pre n is in the [0..length() - 1] range
     
    151151    }
    152152
    153     /// \brief Gives back the first arc of the path
     153    /// \brief The first arc of the path
    154154    const Arc& front() const {
    155155      return head.empty() ? tail.front() : head.back();
     
    176176    }
    177177
    178     /// \brief Gives back the last arc of the path
     178    /// \brief The last arc of the path
    179179    const Arc& back() const {
    180180      return tail.empty() ? head.front() : tail.back();
     
    200200    }
    201201
    202 
    203 
    204202    typedef True BuildTag;
    205203
     
    324322    /// \brief Length of the path.
    325323    int length() const { return data.size(); }
    326     /// \brief Returns whether the path is empty.
     324    /// \brief Return true if the path is empty.
    327325    bool empty() const { return data.empty(); }
    328326
    329     /// \brief Resets the path to an empty path.
     327    /// \brief Reset the path to an empty one.
    330328    void clear() { data.clear(); }
    331329
    332     /// \brief Gives back the nth arc.
     330    /// \brief The nth arc.
    333331    ///
    334332    /// \pre n is in the [0..length() - 1] range
     
    342340    }
    343341
    344     /// \brief Gives back the first arc of the path.
     342    /// \brief The first arc of the path.
    345343    const Arc& front() const {
    346344      return data.front();
    347345    }
    348346
    349     /// \brief Gives back the last arc of the path.
     347    /// \brief The last arc of the path.
    350348    const Arc& back() const {
    351349      return data.back();
     
    507505    };
    508506
    509     /// \brief Gives back the nth arc.
    510     ///
    511     /// Gives back the nth arc in O(n) time.
     507    /// \brief The nth arc.
     508    ///
     509    /// This function looks for the nth arc in O(n) time.
    512510    /// \pre n is in the [0..length() - 1] range
    513511    const Arc& nth(int n) const {
     
    539537    }
    540538
    541     /// \brief Returns whether the path is empty.
     539    /// \brief Return true if the path is empty.
    542540    bool empty() const { return first == 0; }
    543541
    544     /// \brief Resets the path to an empty path.
     542    /// \brief Reset the path to an empty one.
    545543    void clear() {
    546544      while (first != 0) {
     
    552550    }
    553551
    554     /// \brief Gives back the first arc of the path
     552    /// \brief The first arc of the path
    555553    const Arc& front() const {
    556554      return first->arc;
     
    585583    }
    586584
    587     /// \brief Gives back the last arc of the path.
     585    /// \brief The last arc of the path.
    588586    const Arc& back() const {
    589587      return last->arc;
     
    618616    }
    619617
    620     /// \brief Splicing the given path to the current path.
    621     ///
    622     /// It splices the \c tpath to the back of the current path and \c
     618    /// \brief Splice a path to the back of the current path.
     619    ///
     620    /// It splices \c tpath to the back of the current path and \c
    623621    /// tpath becomes empty. The time complexity of this function is
    624622    /// O(1).
     
    637635    }
    638636
    639     /// \brief Splicing the given path to the current path.
    640     ///
    641     /// It splices the \c tpath before the current path and \c tpath
     637    /// \brief Splice a path to the front of the current path.
     638    ///
     639    /// It splices \c tpath before the current path and \c tpath
    642640    /// becomes empty. The time complexity of this function
    643641    /// is O(1).
     
    656654    }
    657655
    658     /// \brief Splicing the given path into the current path.
     656    /// \brief Splice a path into the current path.
    659657    ///
    660658    /// It splices the \c tpath into the current path before the
    661659    /// position of \c it iterator and \c tpath becomes empty. The
    662     /// time complexity of this function is O(1). If the \c it is \c
    663     /// INVALID then it will splice behind the current path.
     660    /// time complexity of this function is O(1). If the \c it is
     661    /// \c INVALID then it will splice behind the current path.
    664662    void splice(ArcIt it, ListPath& tpath) {
    665663      if (it.node) {
     
    689687    }
    690688
    691     /// \brief Spliting the current path.
    692     ///
    693     /// It splits the current path into two parts. The part before \c
    694     /// it iterator will remain in the current path and the part from
    695     /// the it will put into the \c tpath. If the \c tpath had arcs
    696     /// before the operation they will be removed first.  The time
    697     /// complexity of this function is O(1) plus the clearing of \c
    698     /// tpath. If the \c it is \c INVALID then it just clears \c
    699     /// tpath.
     689    /// \brief Split the current path.
     690    ///
     691    /// It splits the current path into two parts. The part before
     692    /// the iterator \c it will remain in the current path and the part
     693    /// starting with
     694    /// \c it will put into \c tpath. If \c tpath have arcs
     695    /// before the operation they are removed first.  The time
     696    /// complexity of this function is O(1) plus the the time of emtying
     697    /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
    700698    void split(ArcIt it, ListPath& tpath) {
    701699      tpath.clear();
     
    739737  /// In a sense, the path can be treated as a list of arcs. The
    740738  /// lemon path type stores just this list. As a consequence it
    741   /// cannot enumerate the nodes in the path and the zero length paths
    742   /// cannot store the source.
    743   ///
    744   /// This implementation is completly static, so it cannot be
    745   /// modified exclude the assign an other path. It is intented to be
    746   /// used when you want to store a large number of paths because it is
    747   /// the most memory efficient path type in the lemon.
     739  /// cannot enumerate the nodes in the path and the source node of
     740  /// a zero length path is undefined.
     741  ///
     742  /// This implementation is completly static, i.e. it can be copy constucted
     743  /// or copy assigned from another path, but otherwise it cannot be
     744  /// modified.
     745  ///
     746  /// Being the the most memory efficient path type in LEMON,
     747  /// it is intented to be
     748  /// used when you want to store a large number of paths.
    748749  template <typename _Digraph>
    749750  class StaticPath {
     
    760761    /// \brief Template copy constructor
    761762    ///
    762     /// This path can be initialized with any other path type. It just
    763     /// makes a copy of the given path.
     763    /// This path can be initialized from any other path type.
    764764    template <typename CPath>
    765765    StaticPath(const CPath& cpath) : arcs(0) {
     
    776776    /// \brief Template copy assignment
    777777    ///
    778     /// This path can be initialized with any other path type. It just
     778    /// This path can be made equal to any other path type. It simply
    779779    /// makes a copy of the given path.
    780780    template <typename CPath>
     
    832832    };
    833833
    834     /// \brief Gives back the nth arc.
     834    /// \brief The nth arc.
    835835    ///
    836836    /// \pre n is in the [0..length() - 1] range
     
    839839    }
    840840
    841     /// \brief Initializes arc iterator to point to the nth arc.
     841    /// \brief The arc iterator pointing to the nth arc.
    842842    ArcIt nthIt(int n) const {
    843843      return ArcIt(*this, n);
    844844    }
    845845
    846     /// \brief Gives back the length of the path.
     846    /// \brief The length of the path.
    847847    int length() const { return len; }
    848848
    849     /// \brief Returns true when the path is empty.
     849    /// \brief Return true when the path is empty.
    850850    int empty() const { return len == 0; }
    851851
    852     /// \break Erase all arc in the digraph.
     852    /// \break Erase all arcs in the digraph.
    853853    void clear() {
    854854      len = 0;
     
    857857    }
    858858
    859     /// \brief Gives back the first arc of the path.
     859    /// \brief The first arc of the path.
    860860    const Arc& front() const {
    861861      return arcs[0];
    862862    }
    863863
    864     /// \brief Gives back the last arc of the path.
     864    /// \brief The last arc of the path.
    865865    const Arc& back() const {
    866866      return arcs[len - 1];
Note: See TracChangeset for help on using the changeset viewer.