lemon/path.h
changeset 955 7f6eeffe3cd1
parent 877 141f9c0db4a3
child 991 a10624ed1997
equal deleted inserted replaced
20:058d12f101f5 21:f3cff5dd0f05
    41   ///
    41   ///
    42   /// A structure for representing directed path in a digraph.
    42   /// A structure for representing directed path in a digraph.
    43   /// \tparam GR The digraph type in which the path is.
    43   /// \tparam GR The digraph type in which the path is.
    44   ///
    44   ///
    45   /// In a sense, the path can be treated as a list of arcs. The
    45   /// 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
    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
    47   /// cannot enumerate the nodes of the path and the source node of
    48   /// a zero length path is undefined.
    48   /// a zero length path is undefined.
    49   ///
    49   ///
    50   /// This implementation is a back and front insertable and erasable
    50   /// This implementation is a back and front insertable and erasable
    51   /// path type. It can be indexed in O(1) time. The front and back
    51   /// path type. It can be indexed in O(1) time. The front and back
   133     bool empty() const { return head.empty() && tail.empty(); }
   133     bool empty() const { return head.empty() && tail.empty(); }
   134 
   134 
   135     /// \brief Reset the path to an empty one.
   135     /// \brief Reset the path to an empty one.
   136     void clear() { head.clear(); tail.clear(); }
   136     void clear() { head.clear(); tail.clear(); }
   137 
   137 
   138     /// \brief The nth arc.
   138     /// \brief The n-th arc.
   139     ///
   139     ///
   140     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   140     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   141     const Arc& nth(int n) const {
   141     const Arc& nth(int n) const {
   142       return n < int(head.size()) ? *(head.rbegin() + n) :
   142       return n < int(head.size()) ? *(head.rbegin() + n) :
   143         *(tail.begin() + (n - head.size()));
   143         *(tail.begin() + (n - head.size()));
   144     }
   144     }
   145 
   145 
   146     /// \brief Initialize arc iterator to point to the nth arc
   146     /// \brief Initialize arc iterator to point to the n-th arc
   147     ///
   147     ///
   148     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   148     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   149     ArcIt nthIt(int n) const {
   149     ArcIt nthIt(int n) const {
   150       return ArcIt(*this, n);
   150       return ArcIt(*this, n);
   151     }
   151     }
   229   ///
   229   ///
   230   /// A structure for representing directed path in a digraph.
   230   /// A structure for representing directed path in a digraph.
   231   /// \tparam GR The digraph type in which the path is.
   231   /// \tparam GR The digraph type in which the path is.
   232   ///
   232   ///
   233   /// In a sense, the path can be treated as a list of arcs. The
   233   /// In a sense, the path can be treated as a list of arcs. The
   234   /// lemon path type stores just this list. As a consequence it
   234   /// LEMON path type stores just this list. As a consequence it
   235   /// cannot enumerate the nodes in the path and the zero length paths
   235   /// cannot enumerate the nodes in the path and the zero length paths
   236   /// cannot store the source.
   236   /// cannot store the source.
   237   ///
   237   ///
   238   /// This implementation is a just back insertable and erasable path
   238   /// This implementation is a just back insertable and erasable path
   239   /// type. It can be indexed in O(1) time. The back insertion and
   239   /// type. It can be indexed in O(1) time. The back insertion and
   325     bool empty() const { return data.empty(); }
   325     bool empty() const { return data.empty(); }
   326 
   326 
   327     /// \brief Reset the path to an empty one.
   327     /// \brief Reset the path to an empty one.
   328     void clear() { data.clear(); }
   328     void clear() { data.clear(); }
   329 
   329 
   330     /// \brief The nth arc.
   330     /// \brief The n-th arc.
   331     ///
   331     ///
   332     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   332     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   333     const Arc& nth(int n) const {
   333     const Arc& nth(int n) const {
   334       return data[n];
   334       return data[n];
   335     }
   335     }
   336 
   336 
   337     /// \brief  Initializes arc iterator to point to the nth arc.
   337     /// \brief  Initializes arc iterator to point to the n-th arc.
   338     ArcIt nthIt(int n) const {
   338     ArcIt nthIt(int n) const {
   339       return ArcIt(*this, n);
   339       return ArcIt(*this, n);
   340     }
   340     }
   341 
   341 
   342     /// \brief The first arc of the path.
   342     /// \brief The first arc of the path.
   393   ///
   393   ///
   394   /// A structure for representing directed path in a digraph.
   394   /// A structure for representing directed path in a digraph.
   395   /// \tparam GR The digraph type in which the path is.
   395   /// \tparam GR The digraph type in which the path is.
   396   ///
   396   ///
   397   /// In a sense, the path can be treated as a list of arcs. The
   397   /// In a sense, the path can be treated as a list of arcs. The
   398   /// lemon path type stores just this list. As a consequence it
   398   /// LEMON path type stores just this list. As a consequence it
   399   /// cannot enumerate the nodes in the path and the zero length paths
   399   /// cannot enumerate the nodes in the path and the zero length paths
   400   /// cannot store the source.
   400   /// cannot store the source.
   401   ///
   401   ///
   402   /// This implementation is a back and front insertable and erasable
   402   /// This implementation is a back and front insertable and erasable
   403   /// path type. It can be indexed in O(k) time, where k is the rank
   403   /// path type. It can be indexed in O(k) time, where k is the rank
   502     private:
   502     private:
   503       const ListPath *path;
   503       const ListPath *path;
   504       Node *node;
   504       Node *node;
   505     };
   505     };
   506 
   506 
   507     /// \brief The nth arc.
   507     /// \brief The n-th arc.
   508     ///
   508     ///
   509     /// This function looks for the nth arc in O(n) time.
   509     /// This function looks for the n-th arc in O(n) time.
   510     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   510     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   511     const Arc& nth(int n) const {
   511     const Arc& nth(int n) const {
   512       Node *node = first;
   512       Node *node = first;
   513       for (int i = 0; i < n; ++i) {
   513       for (int i = 0; i < n; ++i) {
   514         node = node->next;
   514         node = node->next;
   515       }
   515       }
   516       return node->arc;
   516       return node->arc;
   517     }
   517     }
   518 
   518 
   519     /// \brief Initializes arc iterator to point to the nth arc.
   519     /// \brief Initializes arc iterator to point to the n-th arc.
   520     ArcIt nthIt(int n) const {
   520     ArcIt nthIt(int n) const {
   521       Node *node = first;
   521       Node *node = first;
   522       for (int i = 0; i < n; ++i) {
   522       for (int i = 0; i < n; ++i) {
   523         node = node->next;
   523         node = node->next;
   524       }
   524       }
   733   ///
   733   ///
   734   /// A structure for representing directed path in a digraph.
   734   /// A structure for representing directed path in a digraph.
   735   /// \tparam GR The digraph type in which the path is.
   735   /// \tparam GR The digraph type in which the path is.
   736   ///
   736   ///
   737   /// In a sense, the path can be treated as a list of arcs. The
   737   /// In a sense, the path can be treated as a list of arcs. The
   738   /// lemon path type stores just this list. As a consequence it
   738   /// LEMON path type stores just this list. As a consequence it
   739   /// cannot enumerate the nodes in the path and the source node of
   739   /// cannot enumerate the nodes in the path and the source node of
   740   /// a zero length path is undefined.
   740   /// a zero length path is undefined.
   741   ///
   741   ///
   742   /// This implementation is completly static, i.e. it can be copy constucted
   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
   743   /// or copy assigned from another path, but otherwise it cannot be
   829     private:
   829     private:
   830       const StaticPath *path;
   830       const StaticPath *path;
   831       int idx;
   831       int idx;
   832     };
   832     };
   833 
   833 
   834     /// \brief The nth arc.
   834     /// \brief The n-th arc.
   835     ///
   835     ///
   836     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   836     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   837     const Arc& nth(int n) const {
   837     const Arc& nth(int n) const {
   838       return arcs[n];
   838       return arcs[n];
   839     }
   839     }
   840 
   840 
   841     /// \brief The arc iterator pointing to the nth arc.
   841     /// \brief The arc iterator pointing to the n-th arc.
   842     ArcIt nthIt(int n) const {
   842     ArcIt nthIt(int n) const {
   843       return ArcIt(*this, n);
   843       return ArcIt(*this, n);
   844     }
   844     }
   845 
   845 
   846     /// \brief The length of the path.
   846     /// \brief The length of the path.
  1040   }
  1040   }
  1041 
  1041 
  1042   /// \brief Class which helps to iterate through the nodes of a path
  1042   /// \brief Class which helps to iterate through the nodes of a path
  1043   ///
  1043   ///
  1044   /// In a sense, the path can be treated as a list of arcs. The
  1044   /// In a sense, the path can be treated as a list of arcs. The
  1045   /// lemon path type stores only this list. As a consequence, it
  1045   /// LEMON path type stores only this list. As a consequence, it
  1046   /// cannot enumerate the nodes in the path and the zero length paths
  1046   /// cannot enumerate the nodes in the path and the zero length paths
  1047   /// cannot have a source node.
  1047   /// cannot have a source node.
  1048   ///
  1048   ///
  1049   /// This class implements the node iterator of a path structure. To
  1049   /// This class implements the node iterator of a path structure. To
  1050   /// provide this feature, the underlying digraph should be passed to
  1050   /// provide this feature, the underlying digraph should be passed to